pgsql: HOT updates.

Log Message:
-----------
HOT updates. When we update a tuple without changing any of its indexed
columns, and the new version can be stored on the same heap page, we no longer
generate extra index entries for the new version. Instead, index searches
follow the HOT-chain links to ensure they find the correct tuple version.

In addition, this patch introduces the ability to "prune" dead tuples on a
per-page basis, without having to do a complete VACUUM pass to recover space.
VACUUM is still needed to clean up dead index entries, however.

Pavan Deolasee, with help from a bunch of other people.

Modified Files:
--------------
pgsql/contrib/pgstattuple:
pgstattuple.c (r1.29 -> r1.30)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/contrib/pgstattuple/pgstattuple.c?r1=1.29&r2=1.30)
pgsql/doc/src/sgml:
catalogs.sgml (r2.157 -> r2.158)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/doc/src/sgml/catalogs.sgml?r1=2.157&r2=2.158)
monitoring.sgml (r1.51 -> r1.52)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/doc/src/sgml/monitoring.sgml?r1=1.51&r2=1.52)
pgsql/doc/src/sgml/ref:
create_index.sgml (r1.64 -> r1.65)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/doc/src/sgml/ref/create_index.sgml?r1=1.64&r2=1.65)
pgsql/src/backend/access/gin:
ginentrypage.c (r1.8 -> r1.9)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/gin/ginentrypage.c?r1=1.8&r2=1.9)
ginvacuum.c (r1.16 -> r1.17)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/gin/ginvacuum.c?r1=1.16&r2=1.17)
ginxlog.c (r1.8 -> r1.9)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/gin/ginxlog.c?r1=1.8&r2=1.9)
pgsql/src/backend/access/gist:
gist.c (r1.146 -> r1.147)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/gist/gist.c?r1=1.146&r2=1.147)
gistutil.c (r1.23 -> r1.24)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/gist/gistutil.c?r1=1.23&r2=1.24)
gistvacuum.c (r1.31 -> r1.32)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/gist/gistvacuum.c?r1=1.31&r2=1.32)
pgsql/src/backend/access/hash:
hashinsert.c (r1.46 -> r1.47)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/hash/hashinsert.c?r1=1.46&r2=1.47)
hashovfl.c (r1.59 -> r1.60)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/hash/hashovfl.c?r1=1.59&r2=1.60)
hashpage.c (r1.69 -> r1.70)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/hash/hashpage.c?r1=1.69&r2=1.70)
pgsql/src/backend/access/heap:
Makefile (r1.16 -> r1.17)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/heap/Makefile?r1=1.16&r2=1.17)
heapam.c (r1.240 -> r1.241)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/heap/heapam.c?r1=1.240&r2=1.241)
hio.c (r1.66 -> r1.67)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/heap/hio.c?r1=1.66&r2=1.67)
rewriteheap.c (r1.6 -> r1.7)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/heap/rewriteheap.c?r1=1.6&r2=1.7)
pgsql/src/backend/access/index:
genam.c (r1.62 -> r1.63)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/index/genam.c?r1=1.62&r2=1.63)
indexam.c (r1.98 -> r1.99)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/index/indexam.c?r1=1.98&r2=1.99)
pgsql/src/backend/access/nbtree:
nbtinsert.c (r1.159 -> r1.160)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/nbtree/nbtinsert.c?r1=1.159&r2=1.160)
nbtsort.c (r1.112 -> r1.113)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/nbtree/nbtsort.c?r1=1.112&r2=1.113)
nbtxlog.c (r1.45 -> r1.46)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/nbtree/nbtxlog.c?r1=1.45&r2=1.46)
pgsql/src/backend/catalog:
index.c (r1.284 -> r1.285)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/catalog/index.c?r1=1.284&r2=1.285)
indexing.c (r1.114 -> r1.115)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/catalog/indexing.c?r1=1.114&r2=1.115)
system_views.sql (r1.44 -> r1.45)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/catalog/system_views.sql?r1=1.44&r2=1.45)
toasting.c (r1.7 -> r1.8)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/catalog/toasting.c?r1=1.7&r2=1.8)
pgsql/src/backend/commands:
indexcmds.c (r1.165 -> r1.166)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/commands/indexcmds.c?r1=1.165&r2=1.166)
sequence.c (r1.145 -> r1.146)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/commands/sequence.c?r1=1.145&r2=1.146)
vacuum.c (r1.358 -> r1.359)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/commands/vacuum.c?r1=1.358&r2=1.359)
vacuumlazy.c (r1.96 -> r1.97)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/commands/vacuumlazy.c?r1=1.96&r2=1.97)
pgsql/src/backend/executor:
execMain.c (r1.297 -> r1.298)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/executor/execMain.c?r1=1.297&r2=1.298)
execUtils.c (r1.150 -> r1.151)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/executor/execUtils.c?r1=1.150&r2=1.151)
nodeBitmapHeapscan.c (r1.19 -> r1.20)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/executor/nodeBitmapHeapscan.c?r1=1.19&r2=1.20)
spi.c (r1.180 -> r1.181)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/executor/spi.c?r1=1.180&r2=1.181)
pgsql/src/backend/nodes:
tidbitmap.c (r1.12 -> r1.13)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/nodes/tidbitmap.c?r1=1.12&r2=1.13)
pgsql/src/backend/optimizer/plan:
planner.c (r1.221 -> r1.222)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/plan/planner.c?r1=1.221&r2=1.222)
pgsql/src/backend/optimizer/util:
plancat.c (r1.136 -> r1.137)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/util/plancat.c?r1=1.136&r2=1.137)
var.c (r1.70 -> r1.71)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/util/var.c?r1=1.70&r2=1.71)
pgsql/src/backend/postmaster:
pgstat.c (r1.163 -> r1.164)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/postmaster/pgstat.c?r1=1.163&r2=1.164)
pgsql/src/backend/storage/buffer:
bufmgr.c (r1.223 -> r1.224)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/storage/buffer/bufmgr.c?r1=1.223&r2=1.224)
pgsql/src/backend/storage/page:
bufpage.c (r1.73 -> r1.74)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/storage/page/bufpage.c?r1=1.73&r2=1.74)
pgsql/src/backend/utils/adt:
pgstatfuncs.c (r1.44 -> r1.45)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/utils/adt/pgstatfuncs.c?r1=1.44&r2=1.45)
pgsql/src/backend/utils/cache:
plancache.c (r1.10 -> r1.11)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/utils/cache/plancache.c?r1=1.10&r2=1.11)
relcache.c (r1.262 -> r1.263)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/utils/cache/relcache.c?r1=1.262&r2=1.263)
pgsql/src/include/access:
heapam.h (r1.126 -> r1.127)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/access/heapam.h?r1=1.126&r2=1.127)
htup.h (r1.93 -> r1.94)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/access/htup.h?r1=1.93&r2=1.94)
relscan.h (r1.56 -> r1.57)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/access/relscan.h?r1=1.56&r2=1.57)
pgsql/src/include/catalog:
catversion.h (r1.425 -> r1.426)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/catalog/catversion.h?r1=1.425&r2=1.426)
pg_attribute.h (r1.132 -> r1.133)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/catalog/pg_attribute.h?r1=1.132&r2=1.133)
pg_index.h (r1.43 -> r1.44)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/catalog/pg_index.h?r1=1.43&r2=1.44)
pg_proc.h (r1.470 -> r1.471)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/catalog/pg_proc.h?r1=1.470&r2=1.471)
pgsql/src/include/nodes:
execnodes.h (r1.177 -> r1.178)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/nodes/execnodes.h?r1=1.177&r2=1.178)
plannodes.h (r1.94 -> r1.95)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/nodes/plannodes.h?r1=1.94&r2=1.95)
relation.h (r1.145 -> r1.146)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/nodes/relation.h?r1=1.145&r2=1.146)
pgsql/src/include/optimizer:
var.h (r1.35 -> r1.36)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/optimizer/var.h?r1=1.35&r2=1.36)
pgsql/src/include:
pgstat.h (r1.65 -> r1.66)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/pgstat.h?r1=1.65&r2=1.66)
pgsql/src/include/storage:
bufmgr.h (r1.106 -> r1.107)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/storage/bufmgr.h?r1=1.106&r2=1.107)
bufpage.h (r1.73 -> r1.74)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/storage/bufpage.h?r1=1.73&r2=1.74)
pgsql/src/include/utils:
plancache.h (r1.7 -> r1.8)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/utils/plancache.h?r1=1.7&r2=1.8)
rel.h (r1.101 -> r1.102)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/utils/rel.h?r1=1.101&r2=1.102)
relcache.h (r1.59 -> r1.60)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/utils/relcache.h?r1=1.59&r2=1.60)
pgsql/src/test/regress/expected:
create_index.out (r1.25 -> r1.26)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/test/regress/expected/create_index.out?r1=1.25&r2=1.26)
rules.out (r1.133 -> r1.134)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/test/regress/expected/rules.out?r1=1.133&r2=1.134)

Added Files:
-----------
pgsql/src/backend/access/heap:
README.HOT (r1.1)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/heap/README.HOT?rev=1.1&content-type=text/x-cvsweb-markup)
pruneheap.c (r1.1)
(http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/heap/pruneheap.c?rev=1.1&content-type=text/x-cvsweb-markup)