Re: Prefix compression of B-Tree keys

On Thu, Jan 30, 2014 at 9:26 PM, Claudio Freire <klaussfreire(at)gmail(dot)com> wrote:
> Maybe not TOAST compression, but prefix compression.

I've thought about it as well. It's totally feasible, and likely
worthwhile, but a little more tricky.

> I've been wondering lately, whether a format change in the B-Tree
> could be worth the effort: store values with prefix compression. It
> would certainly help indexes of many kinds (text-valued, multi-column,
> etc...).

You can play tricks with the AM version, generally stored in the meta
page, as in the recent commit
36a35c550ac114caa423bcbe339d3515db0cd957, without breaking pg_upgrade.
Although a lot of these techniques may not actually require that kind
of additional effort.

> Now, I haven't checked if it's already done. Sorry if it is. I did
> mock around btree code a lot and don't remember any of this, but I do
> remember stuff that could be used to achieve it (specifically, all the
> index-only-scan machinery, which allows for implicit info).

I think it would make sense to do it on leaf pages, where there is
frequently a lot of redundancy. The reason that I myself wouldn't do
it first is that offhand I think that it'd be harder to come up with a
very generic infrastructure to make it work across diverse types, and
it isn't that useful where there isn't much redundancy in prefixes.
The B-Tree code doesn't really know anything about the type indexed,
and that's a useful property. But it's still definitely a useful goal.

--
Peter Geoghegan