readme.hot

postgresql8.3.4源码,开源数据库

$PostgreSQL: pgsql/src/backend/access/heap/README.HOT,v 1.2 2007/09/21 21:25:42 tgl Exp $

                           Heap Only Tuples (HOT)

Introduction
------------

The Heap Only Tuple (HOT) feature eliminates redundant index entries and
allows the re-use of space taken by DELETEd or obsoleted UPDATEd tuples
without performing a table-wide vacuum.  It does this by allowing
single-page vacuuming, also called "defragmentation".

Note: there is a Glossary at the end of this document that may be helpful
for first-time readers.


Technical Challenges
--------------------

Page-at-a-time vacuuming is normally impractical because of the costs of
finding and removing the index entries that link to the tuples to be
reclaimed.  Standard vacuuming scans the indexes to ensure all such index
entries are removed, amortizing the index scan cost across as many dead
tuples as possible; this approach does not scale down well to the case of
reclaiming just a few tuples.  In principle one could recompute the index
keys and do standard index searches to find the index entries, but this is
risky in the presence of possibly-buggy user-defined functions in
functional indexes.  An allegedly immutable function that in fact is not
immutable might prevent us from re-finding an index entry (and we cannot
throw an error for not finding it, in view of the fact that dead index
entries are sometimes reclaimed early).  That would lead to a seriously
corrupt index, in the form of entries pointing to tuple slots that by now
contain some unrelated content.  In any case we would prefer to be able
to do vacuuming without invoking any user-written code.

HOT solves this problem for a restricted but useful special case:
where a tuple is repeatedly updated in ways that do not change its
indexed columns.  (Here, "indexed column" means any column referenced
at all in an index definition, including for example columns that are
tested in a partial-index predicate but are not stored in the index.)

An additional property of HOT is that it reduces index size by avoiding
the creation of identically-keyed index entries.  This improves search
speeds.


Update Chains With a Single Index Entry
---------------------------------------

Without HOT, every version of a row in an update chain has its own index
entries, even if all indexed columns are the same.  With HOT, a new tuple
placed on the same page and with all indexed columns the same as its
parent row version does not get new index entries.  This means there is
only one index entry for the entire update chain on the heap page.
An index-entry-less tuple is marked with the HEAP_ONLY_TUPLE flag.
The prior row version is marked HEAP_HOT_UPDATED, and (as always in an
update chain) its t_ctid field links forward to the newer version.

For example:

	Index points to 1
	lp [1]  [2]

	[111111111]->[2222222222]

In the above diagram, the index points to line pointer 1, and tuple 1 is
marked as HEAP_HOT_UPDATED.  Tuple 2 is a HOT tuple, meaning it has
no index entry pointing to it, and is marked as HEAP_ONLY_TUPLE.
Although tuple 2 is not directly referenced by the index, it can still be
found by an index search: after traversing from the index to tuple 1,
the index search proceeds forward to child tuples as long as it sees the
HEAP_HOT_UPDATED flag set.  Since we restrict the HOT chain to lie within
a single page, this requires no additional page fetches and doesn't
introduce much performance penalty.

Eventually, tuple 1 will no longer be visible to any transaction.
At that point its space could be reclaimed, but its line pointer cannot,
since the index still links to that line pointer and we still need to
be able to find tuple 2 in an index search.  HOT handles this by turning
line pointer 1 into a "redirecting line pointer", which links to tuple 2
but has no actual tuple attached.  This state of affairs looks like

	Index points to 1
	lp [1]->[2]

	[2222222222]

If now the row is updated again, to version 3, the page looks like this:

	Index points to 1
	lp [1]->[2]  [3]

	[2222222222]->[3333333333]

At some later time when no transaction can see tuple 2 in its snapshot,
tuple 2 and its line pointer can be pruned entirely:

	Index points to 1
	lp [1]------>[3]

	[3333333333]

This is safe because no index entry points to line pointer 2.  Subsequent
insertions into the page can now recycle both line pointer 2 and the
space formerly used by tuple 2.

If an update changes any indexed column, or there is not room on the
same page for the new tuple, then the HOT chain ends: the last member
has a regular t_ctid link to the next version and is not marked
HEAP_HOT_UPDATED.  (In principle we could continue a HOT chain across
pages, but this would destroy the desired property of being able to
reclaim space with just page-local manipulations.  Anyway, we don't
want to have to chase through multiple heap pages to get from an index
entry to the desired tuple, so it seems better to create a new index
entry for the new tuple.)  If further updates occur, the next version
could become the root of a new HOT chain.

Line pointer 1 has to remain as long as there is any non-dead member of
the chain on the page.  When there is not, it is marked "dead".
This lets us reclaim the last child line pointer and associated tuple
immediately.  The next regular VACUUM pass can reclaim the index entries
pointing at the line pointer and then the line pointer itself.  Since a
line pointer is small compared to a tuple, this does not represent an
undue space cost.

Note: we can use a "dead" line pointer for any DELETEd tuple,
whether it was part of a HOT chain or not.  This allows space reclamation
in advance of running VACUUM for plain DELETEs as well as HOT updates.

The requirement for doing a HOT update is that none of the indexed
columns are changed.  This is checked at execution time by comparing the
binary representation of the old and new values.  We insist on bitwise
equality rather than using datatype-specific equality routines.  The
main reason to avoid the latter is that there might be multiple notions
of equality for a datatype, and we don't know exactly which one is
relevant for the indexes at hand.  We assume that bitwise equality
guarantees equality for all purposes.


Abort Cases
-----------

If a heap-only tuple's xmin is aborted, then it can be removed immediately:
it was never visible to any other transaction, and all descendant row
versions must be aborted as well.  Therefore we need not consider it part
of a HOT chain.  By the same token, if a HOT-updated tuple's xmax is
aborted, there is no need to follow the chain link.  However, there is a
race condition here: the transaction that did the HOT update might abort
between the time we inspect the HOT-updated tuple and the time we reach
the descendant heap-only tuple.  It is conceivable that someone prunes
the heap-only tuple before that, and even conceivable that the line pointer
is re-used for another purpose.  Therefore, when following a HOT chain,
it is always necessary to be prepared for the possibility that the
linked-to item pointer is unused, dead, or redirected; and if it is a
normal item pointer, we still have to check that XMIN of the tuple matches
the XMAX of the tuple we left.  Otherwise we should assume that we have
come to the end of the HOT chain.  Note that this sort of XMIN/XMAX
matching is required when following ordinary update chains anyway.

(Early versions of the HOT code assumed that holding pin on the page
buffer while following a HOT link would prevent this type of problem,
but checking XMIN/XMAX matching is a much more robust solution.)


Index/Sequential Scans
----------------------

When doing an index scan, whenever we reach a HEAP_HOT_UPDATED tuple whose
xmax is not aborted, we need to follow its t_ctid link and check that
entry as well; possibly repeatedly until we reach the end of the HOT
chain.  (When using an MVCC snapshot it is possible to optimize this a
bit: there can be at most one visible tuple in the chain, so we can stop
when we find it.  This rule does not work for non-MVCC snapshots, though.)

Sequential scans do not need to pay attention to the HOT links because
they scan every item pointer on the page anyway.  The same goes for a
bitmap heap scan with a lossy bitmap.


Pruning
-------

HOT pruning means updating item pointers so that HOT chains are
reduced in length, by collapsing out line pointers for intermediate dead
tuples.  Although this makes those line pointers available for re-use,
it does not immediately make the space occupied by their tuples available.


Defragmentation
---------------

Defragmentation centralizes unused space.  After we have converted root
line pointers to redirected line pointers and pruned away any dead
intermediate line pointers, the tuples they linked to are free space.
But unless that space is adjacent to the central "hole" on the page
(the pd_lower-to-pd_upper area) it cannot be used by tuple insertion.
Defragmentation moves the surviving tuples to coalesce all the free
space into one "hole".  This is done with the same PageRepairFragmentation
function that regular VACUUM uses.


When can/should we prune or defragment?
---------------------------------------

This is the most interesting question in HOT implementation, since there
is no simple right answer: we must use heuristics to determine when it's
most efficient to perform pruning and/or defragmenting.

We cannot prune or defragment unless we can get a "buffer cleanup lock"
on the target page; otherwise, pruning might destroy line pointers that
other backends have live references to, and defragmenting might move
tuples that other backends have live pointers to.  Thus the general
approach must be to heuristically decide if we should try to prune
or defragment, and if so try to acquire the buffer cleanup lock without
blocking.  If we succeed we can proceed with our housekeeping work.
If we cannot get the lock (which should not happen often, except under
very heavy contention) then the housekeeping has to be postponed till
some other time.  The worst-case consequence of this is only that an
UPDATE cannot be made HOT but has to link to a new tuple version placed on
some other page, for lack of centralized space on the original page.

Ideally we would do defragmenting only when we are about to attempt
heap_update on a HOT-safe tuple.  The difficulty with this approach
is that the update query has certainly got a pin on the old tuple, and
therefore our attempt to acquire a buffer cleanup lock will always fail.
(This corresponds to the idea that we don't want to move the old tuple
out from under where the query's HeapTuple pointer points.  It might
be possible to finesse that, but it seems fragile.)

Pruning, however, is potentially useful even when we are not about to
insert a new tuple, since shortening a HOT chain reduces the cost of
subsequent index searches.  However it is unclear that this gain is
large enough to accept any extra maintenance burden for.

The currently planned heuristic is to prune and defrag when first accessing
a page that potentially has prunable tuples (as flagged by the pd_prune_xid
page hint field) and that either has free space less than MAX(fillfactor
target free space, BLCKSZ/10) *or* has recently had an UPDATE fail to
find enough free space to store an updated tuple version.  (These rules
are subject to change.)

We have effectively implemented the "truncate dead tuples to just line
pointer" idea that has been proposed and rejected before because of fear
of line pointer bloat: we might end up with huge numbers of line pointers
and just a few actual tuples on a page.  To limit the damage in the worst