Обсуждение: Re: posting tree compression (WAS: Proposal: fix range queries in btree_gin)

Поиск
Список
Период
Сортировка

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

От
Robert Haas
Дата:
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)

От
Claudio Freire
Дата:
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.



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

От
Tom Lane
Дата:
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)

От
Claudio Freire
Дата:
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.