Re: Heap WARM Tuples - Design Draft

On Thu, Aug 4, 2016 at 2:14 PM, Claudio Freire <klaussfreire(at)gmail(dot)com> wrote:
> To fix this, what I was pondering, and I believe it would be viable,
> is to teach heap_hot_search_buffer about the WARM invariant. It will
> make correctness heavily depend on the invariant being true, which
> means either flagging item pointers as WARM chains, or requiring a
> reindex during upgrade to make sure all indexes verify the invariant -
> as old indices won't.
>
> When an item pointer is WARM (either implicit or explicit),
> heap_hot_search_buffer will only stop following the update chain if it
> reaches not the end of a HOT chain, but rather a key change. For this,
> it will need to recheck the key of all but the first TID in the chain,
> so singleton chains (ie: not-updated or frozen tuples) won't incurr
> this extra cost. When walking the chain, it will need to form an index
> tuple for both the old and new versions, and compare them, and follow
> the chain *only* if the keys are equal.
>
> As an optimization, if the tuple is marked HOT-updated, the key check
> may be skipped.
>
> Vacuum will need to be taught not to break the invariant, but I
> believe this is viable and efficient.

And I didn't mention the invariant.

The invariant would be that all WARM chains:

* contain entire HOT chains (ie: no item pointers pointing to the
middle of a HOT chain)
* start at the item pointer, and end when the t_ctid of the heap
tuple either points to another page, or a tuple with a different index
key
* there is exactly one WARM chain containing any heap tuple,
including the singleton chain represented by a tuple whose WARM chain
contains only itself

This is maintained by:

* No item pointer will be created for row versions whose immediately
previous version is already on the index with the same key

Cleanup can only proceed by applying cleanup on HOT chains, by moving
the head of a WARM chain forward, or by removing it entirely. It may
be that VACUUM already works like that, but I'm unsure.