Re: btree split logic is fragile in the presence of lar ge index items

"Hiroshi Inoue" <Inoue(at)tpf(dot)co(dot)jp> writes:
>>>> Do not add TID to key but store key anywhere in duplicate chain and
>>>> just read lefter child page while positioning index scan, as we do
>>>> right now for partial keys?
>>
>>>> This will result in additional reads but I like it much more than
>>>> current "logic"...

> What about unique key insertions ?

What about 'em? Doesn't seem to make any difference as far as I can
see. You still need to be prepared to scan right to see all of the
potential matches.

I have been digging in the index code and am thinking of reinstating
another aspect of the older implementation. Once upon a time, the code
was set up to treat the leftmost key on any non-leaf tree level as
minus-infinity. That seems to me to agree with the data structure
Lehman and Yao have in mind: in their drawings, each down-link pointer
on a non-leaf level is "between" two keys, except that the leftmost
downlink has no key to its left. Their drawings all show n+1 downlinks
in an n-key non-leaf node. We didn't match that representation, so we
need to fake it with a dummy key associated with the first downlink.
The original code did that, but it got taken out at some point and
replaced with pretty ugly code to propagate minimum-key changes back up
the tree when the leftmost child node has to be split. But I think the
only thing wrong with it was that not all the comparison routines knew
they needed to do that. btree seems to be suffering from an abundance
of comparison routines ... I'm going to try to eliminate some of the
redundancy.

Actually, we could shave some storage by not storing a key in the
first data item of any non-leaf page, whether leftmost on its level
or not. That would correspond exactly to L&Y's drawings.

regards, tom lane