Re: Heap WARM Tuples - Design Draft - Mailing list pgsql-hackers

On Fri, Aug 5, 2016 at 4:26 PM, Bruce Momjian <bruce@momjian.us> wrote:
> On Fri, Aug  5, 2016 at 11:30:26PM +0530, Pavan Deolasee wrote:
>> On Fri, Aug 5, 2016 at 11:26 PM, Bruce Momjian <bruce@momjian.us> wrote:
>>
>>     On Fri, Aug  5, 2016 at 02:43:37PM -0300, Claudio Freire wrote:
>>     > But doing the WARM chain backtracking and checking for previous
>>     > versions with appropriate keys should be enough to support this use
>>     > case too, it just needs to be well optimized to avoid seriously
>>     > impacting performance on the average case.
>>
>>     Yes, that was an idea I had to --- if the in-page HOT chain already has
>>     the key, we know it is already in the index and we can skip the index
>>     addition.
>>
>> I just don't know how would you do that without delaying/not-doing HOT chain
>> prune. As soon as root and intermediate HOT tuples are gone, all information is
>> lost. You may delay that, but that will defeat the whole purpose. If chains are
>> not pruned in-time, you may not find any free space in the page and end up
>> doing a cold update anyways. But may be I am missing something and Claudio has
>> a different idea.
>
> Yes, pruning would be a problem.  :-(
>
> A check only needs to happen when the indexed key changes, right?  So we
> are comparing the cost of adding an index key vs. the cost of trying to
> find a matching key/ctid in the index.  Seems the later is cheaper, but
> it is not obvious.
>
> I think I see Claudio's idea now --- from his diagram, you can have WARM
> chains span multiple HOT chains.  What he is doing is creating a new HOT
> chain everytime _any_ key changes, and he knows the entire HOT chain has
> idential values for all indexes.  He moves from one HOT chain to another
> during an index scan by checking if the index value is the same in the
> old and new HOT chain (that is the same WARM chain).
>
> This does create more HOT chains where the root ctid cannot be removed,
> but it does avoid the index key/ctid check because any entry in the HOT
> chain has identical keys.  What this would not handle is when an entire
> HOT chain is pruned, as the keys would be gone.

I believe the only solution is to use bitmap index scans with WARM indexes.

Doing so simplifies things considerably.

For one, it isolates the new functionality and makes it opt-in.

Then, WARM indexes can always point to the root of the HOT chain, and
be ignored for satisfies HOT. The planner will only consider bitmap
index scans with WARM indexes, and always issue a recheck.

The bitmap is needed to remove duplicate item pointers, and the
recheck, as usual, to filter out unwanted versions.

On update, one only needs a pointer to the HOT head, which would
arguably be at hand, or at worst reachable by backtracking t_ctid
pointers. No key checks of any kind, and no weird flags required.

I don't see another solution to the information loss when pruning
whole HOT chains.

Suppose we start with this situation:

lp:  1  2h 3h 4w 5h 6h 7h
k1:  a  a  a  b  b  a  a
k2:  c  c  c  c  c  c  c

So we have 2 HOT chains, 1-3, 4-7, two indexes, one never updated, the
other with an update and then returning to the same key.

The first index will have two index entries, one for key a, another
for b, both pointing at 1.

a -> (p,1)
b -> (p,1)

Now versions 1-3 are dead, so we want to prune them.

We end up with a redirect on the LP for 1 -> 4, LPs 2 and 3 unused
because they were HOT
   r4  u  u
lp:  1  2  3  4w 5h 6  7h
k1:  _  _  _  b  b  a  a
k2:  _  _  _  c  c  c  c

Now suppose versions 4 and 5 die. So we end up with:
   r6  u  u  u  u
lp:  1  2  3  4  5  6  7h
k1:  _  _  _  _  _  a  a
k2:  _  _  _  _  _  c  c

We just forgot that "b" was in k1, yet we still have an index entry
pointing to the chain.

Should an update come:
   r6  u  u  u  u
lp:  1  2  3  4  5  6  7h 8?
k1:  _  _  _  _  _  a  a  b
k2:  _  _  _  _  _  c  c  c

Is an index entry b->(p,1) needed for 8?

According to the logic, it is, k1 would need a new entry b -> (p,1),
but the entry is already there. It's just unverifiable in reasonable
time.

So a simpler solution is to always add such entries, and let the
bitmap index scan filter duplicates.