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

On Mon, Jul 24, 2017 at 10:13 AM, Claudio Freire <klaussfreire(at)gmail(dot)com> wrote:
> In most cases, the TID itself can be omitted when the key itself
> differs already.
>
> When a split happens, a TID will be added referring to a real tid from
> a child page iff necessary.
>
> This gives a lot of leeway in choosing the cutoff point, since a
> cutoff point is only added when necessary.

I agree with all that. That just sounds like a basic implementation of
suffix truncation, to support making heap TID a part of the keyspace
without paying a big cost in fan-in.

> Vacuum *might* be able to redistribute tuples too, while holding locks
> to all 3 pages (the two children and the parent page), since it can
> move the TID to the middle point of two actual child TIDs, mindlessly,
> without checking to see if such TID actually exists - it just needs to
> choose a TID cutoff point that will distribute item pointers evently.
> I haven't tried this, but it is theoretically possible.

I don't understand what you mean here. As long as the TIDs are a first
class part of the keyspace, what VACUUM does or doesn't do should not
matter. Page deletion stashes a TID in the highkey position of a leaf
page within _bt_mark_page_halfdead(), but that shouldn't matter to
you.

I guess you're talking about contriving a TID value that is the mean
of two real TID values -- the two that are on each side of the split
point during a leaf page split. While that seems possible, I don't see
much value in it. Unless you have normalized keys, you can only really
truncate whole attributes. And, I think it's a bad idea to truncate
anything other than the new high key for leaf pages, with or without
normalized keys. Changing the keys once they're in internal pages is
never going to be worth it.

--
Peter Geoghegan