Re: [HACKERS] row reuse while UPDATE and vacuum analyze problem

After thinking about the row reuse problem for a while, this is the best
I could come up with.  I don't think it is well enough thought out to be
worth implementing yet, but maybe the ideas are a step in the right
direction.

A partial solution to row-reuse is to allow writing commands (commands
with write locks on a buffer) to purge expendable tuples as they find
them.  When a transaction starts it could look at the snapshots of
concurrent transactions and compute a tide-mark equal to the oldest TID
in all the concurrent snapshots.  Any deleted tuple in a heap relation
with a committed tmax value that is smaller than the tide-mark is
invisible to any of the concurrent or future transactions, and is
expendable. The write command that discovers the expendable transaction
can then delete it, and reclaim the tuple space.  

Unfortunately this solves only half the problem.  Deleting the tuple
means that other scans no longer have to read and then discard it,  but
the space that the tuple uses is not really reclaimed because the way
that insertions work is that they always add to the end of the heap.  If
all the tuples in a 
table are of fixed size then one solution would be to keep a list of
empty tuple slots in the heap, and insert new tuples in these slots
first.  This would allow inserts to keep the table well packed.

In the case of tables with variable length tuples the problem seems
harder. Since the actual tuples in a table are always accessed through
ItemIds, it is possible for a process with a write lock on a buffer to
rearrange the tuples in the page to remove free space without affecting
concurrent processes' views of the data within the buffer.  After
freeing the tuple, and compacting the space in the page, the process
would have to update the free space list 
by removing any previous pointer to space on the page, and then
re-inserting a pointer to the new space on the page.  The free space
list becomes quite a bit more complicated in this case, as it has to
keep track of the sizes of the free space segments, and it needs to be
indexed by the block in which the free space resides, and the size of
the space available.  This would seem to indicate the need for both a
tree-structure and a hash structure associated with the free space list.

Comments anyone?

Bernie