Re: RFC: Key normalization for nbtree

On Mon, Jul 10, 2017 at 12:53 PM, Claudio Freire <klaussfreire(at)gmail(dot)com> wrote:
> I do have a patch that attacks suffix truncation, heap tid unification
> and prefix compression all at once.

That's great! I'll certainly be able to review it.

> It's on a hiatus ATM, but, as you say, the implementations are highly
> correlated so attacking them at once makes a lot of sense. Or, at
> least, attacking one having the other in the back of your mind.
>
> Key normalization would simplify prefix compression considerably, for instance.

The stuff that I go into detail about is the stuff I think you'd need
to do up front. Prefix compression would be a "nice to have", but I
think you'd specifically do key normalization, suffix truncation, and
adding the heap TID to the key space all up front.

> A missing optimization is that having tid unification allows VACUUM to
> implement a different strategy when it needs to clean up only a tiny
> fraction of the index. It can do the lookup by key-tid instead of
> scanning the whole index, which can be a win if the index is large and
> the number of index pointers to kill is small.

I do mention that on the Wiki page. I also describe ways that these
techniques have some non-obvious benefits for VACUUM B-Tree page
deletion, which you should get "for free" once you do the 3 things I
mentioned. A lot of the benefits for VACUUM are seen in the worst
case, which is when they're really needed.

--
Peter Geoghegan