Re: posting tree compression (WAS: Proposal: fix range queries in btree_gin)

Claudio Freire <klaussfreire(at)gmail(dot)com> writes:
> On Mon, Mar 31, 2014 at 6:21 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> On Fri, Mar 28, 2014 at 11:30 AM, Alexander Korotkov
>> <aekorotkov(at)gmail(dot)com> wrote:
>>> after reading Heikki Linnakangas presentation about GIN from Nordic PGDay, I
>>> figure out that btree_gin became much more attractive.
>>> http://hlinnaka.iki.fi/presentations/NordicPGDay2014-GIN.pdf

>> This is a mighty interesting presentation. Could the posting tree
>> compression described on the "posting tree page format" slides (pp.
>> 16-17, I think) be used for btree also? Would we get similar
>> benefits? How much more expensive are updates with the new system?

> I'd believe so, but it can make updates quite complicated.

> I was going to take a stab at prefix-compression in b-tree, I could
> explore delta compression of the tids as well.

Prefix compression definitely seems like it could be a win thanks to
index ordering (although note that on little-endian machines, you need to
be careful about which end of an integer is the "prefix"). I'm pretty
dubious about tid deltas being useful for btree, though. GIN has the
luxury of being able to sort a lot of tids into tid order, btree doesn't.

regards, tom lane