Thread: Re: posting tree compression (WAS: Proposal: fix range queries in btree_gin)
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? -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
Re: posting tree compression (WAS: Proposal: fix range queries in btree_gin)
From
Claudio Freire
Date:
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.
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. regards, tom lane
Re: posting tree compression (WAS: Proposal: fix range queries in btree_gin)
From
Claudio Freire
Date:
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.