Re: RFC: Key normalization for nbtree

On Mon, Jul 10, 2017 at 3:40 PM, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> It might appear excessive to talk about several different techniques
> in one place, but that seemed like the best way to me, because there
> are subtle dependencies. If most of the optimizations are pursued as a
> project all at once (say, key normalization, suffix truncation, and
> treating heap TID as a unique-ifier), that may actually be more likely
> to succeed than a project to do just one. The techniques don't appear
> to be related at first, but they really are.

I do have a patch that attacks suffix truncation, heap tid unification
and prefix compression all at once.

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.

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.