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

On Mon, Mar 31, 2014 at 6:37 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Claudio Freire <klaussfreire@gmail.com> writes:
>> On Mon, Mar 31, 2014 at 6:21 PM, Robert Haas <robertmhaas@gmail.com> wrote:
>>> On Fri, Mar 28, 2014 at 11:30 AM, Alexander Korotkov
>>> <aekorotkov@gmail.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.

You still have lots of natural correlation in many real-world cases.

Still, I agree that the overhead of maintaining such delta-compressed
tid list can (and probably will) outweight the advantage.