Re: Prefix compression of B-Tree keys

On Fri, Jan 31, 2014 at 3:51 AM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
>> 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.

Well, for multi-column it should be really simple. You already have
all the necessary information to decide on the prefix (the common
prefix columns of leftmost and rightmost keys). It's harder for text
columns, since you must abstract out the "common prefix check","append
prefix", and "remove prefix" operations. That would probably require
extending opclasses.