Re: [WIP] [B-Tree] Keep indexes sorted by heap physical location

On Thu, Aug 18, 2016 at 6:15 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> On Thu, Aug 18, 2016 at 1:41 PM, Claudio Freire <klaussfreire(at)gmail(dot)com> wrote:
>> In fact, that's why non-leaf index tuples need a different format,
>> because while leaf index tuples contain the heap pointer already,
>> non-leaf ones contain only the downlink, not the pointer into the
>> heap. To be able to do comparisons and pick the right downlink, the
>> original heap pointer in the leaf index tuple is copied into the
>> downlink index tuple when splitting pages into an additional
>> IndexTupleData header that is prepended only to non-leaf index tuples.
>
> I think that this is a bad idea. We need to implement suffix
> truncation of internal page index tuples at some point, to make them
> contain less information from the original leaf page index tuple.
> That's an important optimization, because it increases fan-in. This
> seems like a move in the opposite direction.

I see that. I could try to measure average depth to measure the impact
this had on fan-in.

While it should cut it in half for narrow indexes, half of very high
is still high. Wide indexes, which are are the ones that would suffer
from poor fan-in, would feel this far less, since the overhead is
constant.

Even if it does have an impact, I don't see an alternative, without
also implementing suffix truncation. Perhaps I could try to avoid
adding the leaf tid header if it isn't necessary, though I would have
to use up the last available flag bit in t_info for that.

> ISTM that the way to address this problem is with a duplicate list
> and/or prefix compression in leaf pages.

Prefix compression is another one I will be looking into eventually,
but last time I tried it was far more invasive so I abandoned until I
could find a less invasive way to do it.