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

On Thu, Aug 4, 2016 at 11:15 PM, Bruce Momjian <bruce@momjian.us> wrote:
> On Thu, Aug  4, 2016 at 09:53:31PM -0300, Claudio Freire wrote:
>> It's the other way around. A WARM chain has to span whole HOT chains.
>> The WARM chain always begins in the head of a HOT chain (or non-HOT
>> tuple of course), and cannot end before the HOT chain ends.
>>
>> That is, all within a single page:
>>
>>   [  v1 .. v2 .. v3  .. v4 .. v5 .. v6  v7 ]
>>   [ hot chain 1   ][ hot chain 2 ] [NH]
>>   [         WARM CHAIN          ] [NW]
>>
>> (NH = non-HOT)
>> (NW = non-WARM)
>>
>> The flag could be useful for the upgrade path, but if you ignore
>> having to live with old-format indexes, it's not necessary.
>>
>> A WARM chain starts at any index item pointer. It ends when there's a
>> key change or a page change (ie: the WARM chain cannot span multiple
>> pages). That cannot happen within a HOT chain, so that point will also
>> be the end of a HOT chain.
>>
>> You can think of a WARM chain as a chain of HOT chains.
>
> OK, that's a lot of text, and I am confused.  Please tell me the
> advantage of having an index point to a string of HOT chains, rather
> than a single one?  Is the advantage that the index points into the
> middle of the HOT chain rather than at the beginning?  I can see some
> value to that, but having more ctid HOT headers that can't be removed
> except by VACUUM seems bad, plus the need for index rechecks as you
> cross to the next HOT chain seems bad.
>
> The value of WARM is to avoid index bloat --- right now we traverse the
> HOT chain on a single page just fine with no complaints about speed so I
> don't see a value to optimizing that traversal, and I think the key
> rechecks and ctid bloat will make it all much slower.
>
> It also seems much more complicated.

The point is avoiding duplicate rows in the output of index scans.

I don't think you can avoid it simply by applying index condition
rechecks as the original proposal implies, in this case:

CREATE TABLE t (id integer not null primary key, someid integer, dat integer);
CREATE INDEX i1 ON t (someid);

INSERT INTO t (id, someid, dat) VALUES (1, 2, 100);
UPDATE t SET dat = dat + 1 where id = 1;
UPDATE t SET dat = dat + 1, id = 2 where id = 1;
UPDATE t SET dat = dat + 1, id = 3, someid = 3 where id = 2;
UPDATE t SET dat = dat + 1, id = 1, someid = 2 where id = 3;
SELECT * FROM t WHERE someid = 2;

That, I believe, will cause the problematic chains where the condition
recheck passes both times the last visible tuple is visited during the
scan. It will return more than one tuple when in reality there is only
one.

Not to mention the cost of scanning the chain of N tuples N times,
making it quadratic - bound by the number of tuples that can fit a
page, but still high.

Solving that, I believe, will remove all the simplicity of pointing to
root tuples.

This is done in my proposals by adding boundaries to WARM chains such
that potential matches are visited only once (first variant) or
guaranteeing that visible tuples with a particular key will be
reachable from only one index entry (second variant). Pointing to the
middle of the chain also allows skipping the recheck for the first HOT
chain, which could improve scan performance a lot, especially in the
second variant that has no condition rechecks on invisible tuples.

I don't really see how you'd do that on yours. You seem to assume
finding a particular key-item pointer pair in an index would be
efficient, but IMHO that's not the case.