pgsql: Implement sharable row-level locks, and use them for foreign key

Log Message:
-----------
Implement sharable row-level locks, and use them for foreign key references
to eliminate unnecessary deadlocks. This commit adds SELECT ... FOR SHARE
paralleling SELECT ... FOR UPDATE. The implementation uses a new SLRU
data structure (managed much like pg_subtrans) to represent multiple-
transaction-ID sets. When more than one transaction is holding a shared
lock on a particular row, we create a MultiXactId representing that set
of transactions and store its ID in the row's XMAX. This scheme allows
an effectively unlimited number of row locks, just as we did before,
while not costing any extra overhead except when a shared lock actually
has to be shared. Still TODO: use the regular lock manager to control
the grant order when multiple backends are waiting for a row lock.

Alvaro Herrera and Tom Lane.

Modified Files:
--------------
pgsql/doc/src/sgml:
mvcc.sgml (r2.49 -> r2.50)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/doc/src/sgml/mvcc.sgml.diff?r1=2.49&r2=2.50)
sql.sgml (r1.35 -> r1.36)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/doc/src/sgml/sql.sgml.diff?r1=1.35&r2=1.36)
storage.sgml (r1.5 -> r1.6)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/doc/src/sgml/storage.sgml.diff?r1=1.5&r2=1.6)
pgsql/doc/src/sgml/ref:
grant.sgml (r1.45 -> r1.46)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/doc/src/sgml/ref/grant.sgml.diff?r1=1.45&r2=1.46)
lock.sgml (r1.46 -> r1.47)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/doc/src/sgml/ref/lock.sgml.diff?r1=1.46&r2=1.47)
pg_resetxlog.sgml (r1.9 -> r1.10)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/doc/src/sgml/ref/pg_resetxlog.sgml.diff?r1=1.9&r2=1.10)
select.sgml (r1.85 -> r1.86)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/doc/src/sgml/ref/select.sgml.diff?r1=1.85&r2=1.86)
select_into.sgml (r1.34 -> r1.35)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/doc/src/sgml/ref/select_into.sgml.diff?r1=1.34&r2=1.35)
pgsql/src/backend/access/heap:
heapam.c (r1.187 -> r1.188)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/heap/heapam.c.diff?r1=1.187&r2=1.188)
pgsql/src/backend/access/transam:
Makefile (r1.19 -> r1.20)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/transam/Makefile.diff?r1=1.19&r2=1.20)
xact.c (r1.199 -> r1.200)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/transam/xact.c.diff?r1=1.199&r2=1.200)
xlog.c (r1.188 -> r1.189)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/transam/xlog.c.diff?r1=1.188&r2=1.189)
pgsql/src/backend/catalog:
index.c (r1.252 -> r1.253)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/catalog/index.c.diff?r1=1.252&r2=1.253)
pgsql/src/backend/commands:
portalcmds.c (r1.40 -> r1.41)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/commands/portalcmds.c.diff?r1=1.40&r2=1.41)
trigger.c (r1.186 -> r1.187)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/commands/trigger.c.diff?r1=1.186&r2=1.187)
vacuum.c (r1.306 -> r1.307)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/commands/vacuum.c.diff?r1=1.306&r2=1.307)
pgsql/src/backend/executor:
README (r1.4 -> r1.5)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/executor/README.diff?r1=1.4&r2=1.5)
execMain.c (r1.246 -> r1.247)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/executor/execMain.c.diff?r1=1.246&r2=1.247)
execUtils.c (r1.122 -> r1.123)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/executor/execUtils.c.diff?r1=1.122&r2=1.123)
pgsql/src/backend/nodes:
copyfuncs.c (r1.303 -> r1.304)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/nodes/copyfuncs.c.diff?r1=1.303&r2=1.304)
equalfuncs.c (r1.240 -> r1.241)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/nodes/equalfuncs.c.diff?r1=1.240&r2=1.241)
outfuncs.c (r1.250 -> r1.251)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/nodes/outfuncs.c.diff?r1=1.250&r2=1.251)
readfuncs.c (r1.176 -> r1.177)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/nodes/readfuncs.c.diff?r1=1.176&r2=1.177)
pgsql/src/backend/optimizer/path:
allpaths.c (r1.128 -> r1.129)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/path/allpaths.c.diff?r1=1.128&r2=1.129)
pgsql/src/backend/optimizer/plan:
initsplan.c (r1.104 -> r1.105)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/plan/initsplan.c.diff?r1=1.104&r2=1.105)
planner.c (r1.184 -> r1.185)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/plan/planner.c.diff?r1=1.184&r2=1.185)
pgsql/src/backend/optimizer/prep:
prepjointree.c (r1.26 -> r1.27)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/prep/prepjointree.c.diff?r1=1.26&r2=1.27)
preptlist.c (r1.74 -> r1.75)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/prep/preptlist.c.diff?r1=1.74&r2=1.75)
pgsql/src/backend/parser:
analyze.c (r1.320 -> r1.321)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/parser/analyze.c.diff?r1=1.320&r2=1.321)
gram.y (r2.488 -> r2.489)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/parser/gram.y.diff?r1=2.488&r2=2.489)
parse_relation.c (r1.106 -> r1.107)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/parser/parse_relation.c.diff?r1=1.106&r2=1.107)
parse_type.c (r1.73 -> r1.74)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/parser/parse_type.c.diff?r1=1.73&r2=1.74)
pgsql/src/backend/rewrite:
rewriteHandler.c (r1.150 -> r1.151)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/rewrite/rewriteHandler.c.diff?r1=1.150&r2=1.151)
pgsql/src/backend/storage/ipc:
ipci.c (r1.74 -> r1.75)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/storage/ipc/ipci.c.diff?r1=1.74&r2=1.75)
pgsql/src/backend/storage/lmgr:
lwlock.c (r1.27 -> r1.28)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/storage/lmgr/lwlock.c.diff?r1=1.27&r2=1.28)
pgsql/src/backend/tcop:
utility.c (r1.235 -> r1.236)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/tcop/utility.c.diff?r1=1.235&r2=1.236)
pgsql/src/backend/utils/adt:
ri_triggers.c (r1.76 -> r1.77)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/utils/adt/ri_triggers.c.diff?r1=1.76&r2=1.77)
pgsql/src/backend/utils/time:
tqual.c (r1.86 -> r1.87)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/utils/time/tqual.c.diff?r1=1.86&r2=1.87)
pgsql/src/bin/initdb:
initdb.c (r1.81 -> r1.82)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/bin/initdb/initdb.c.diff?r1=1.81&r2=1.82)
pgsql/src/bin/pg_controldata:
pg_controldata.c (r1.22 -> r1.23)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/bin/pg_controldata/pg_controldata.c.diff?r1=1.22&r2=1.23)
pgsql/src/bin/pg_resetxlog:
pg_resetxlog.c (r1.31 -> r1.32)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/bin/pg_resetxlog/pg_resetxlog.c.diff?r1=1.31&r2=1.32)
pgsql/src/include/access:
heapam.h (r1.99 -> r1.100)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/access/heapam.h.diff?r1=1.99&r2=1.100)
htup.h (r1.73 -> r1.74)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/access/htup.h.diff?r1=1.73&r2=1.74)
xlog.h (r1.59 -> r1.60)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/access/xlog.h.diff?r1=1.59&r2=1.60)
pgsql/src/include:
c.h (r1.181 -> r1.182)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/c.h.diff?r1=1.181&r2=1.182)
pgsql/src/include/catalog:
pg_control.h (r1.20 -> r1.21)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/catalog/pg_control.h.diff?r1=1.20&r2=1.21)
pgsql/src/include/nodes:
execnodes.h (r1.129 -> r1.130)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/nodes/execnodes.h.diff?r1=1.129&r2=1.130)
parsenodes.h (r1.277 -> r1.278)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/nodes/parsenodes.h.diff?r1=1.277&r2=1.278)
pgsql/src/include/parser:
analyze.h (r1.29 -> r1.30)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/parser/analyze.h.diff?r1=1.29&r2=1.30)
parse_node.h (r1.42 -> r1.43)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/parser/parse_node.h.diff?r1=1.42&r2=1.43)
pgsql/src/include/storage:
bufpage.h (r1.64 -> r1.65)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/storage/bufpage.h.diff?r1=1.64&r2=1.65)
lmgr.h (r1.45 -> r1.46)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/storage/lmgr.h.diff?r1=1.45&r2=1.46)
lwlock.h (r1.17 -> r1.18)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/storage/lwlock.h.diff?r1=1.17&r2=1.18)

Added Files:
-----------
pgsql/src/backend/access/transam:
multixact.c (r1.1)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/transam/multixact.c?rev=1.1&content-type=text/x-cvsweb-markup)
pgsql/src/include/access:
multixact.h (r1.1)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/access/multixact.h?rev=1.1&content-type=text/x-cvsweb-markup)