Message-ID: <52B2B1D7.2050802@vmware.com>
Date: Thu, 19 Dec 2013 10:44:07 +0200
From: Heikki Linnakangas <hlinnakangas@vmware.com>
Organization: VMware
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
 rv:17.0) Gecko/20131005 Icedove/17.0.9
MIME-Version: 1.0
To: obartunov@gmail.com
CC: Alexander Korotkov <aekorotkov@gmail.com>,
 Alvaro Herrera <alvherre@2ndquadrant.com>,
 Tomas Vondra <tv@fuzzy.cz>, pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: GIN improvements part 1: additional information
References: 
 <CAPpHfdutJEC9+6vWX579afZKzdHKCT2wzDkAEom1XmiXEwF3pw@mail.gmail.com>
 <527A03AF.9010501@vmware.com> <20131106153604.GM5809@eldon.alvh.no-ip.org>
 <528CEB34.7080702@vmware.com>
 <CAPpHfdvG+EvY26-bRAj=FzUUSm+O+9gc0g7PmM1fupxy2Ycv3g@mail.gmail.com>
 <52950F46.2080009@vmware.com>
 <CAPpHfds7rT_+6oTyPOQ+XH7dfb6ucnBVrfJc-mbAFrctNy847Q@mail.gmail.com>
 <5298615C.7060102@vmware.com> <5298E834.4090408@vmware.com>
 <CAPpHfdvP3G2k04tpCyEA0mAd2e8xOQyuj=2wwAj0UVhB1_oe+g@mail.gmail.com>
 <52A58AD5.6030808@vmware.com>
 <CAPpHfdvKC9HE_D+BYBUpxqyWSE4UD_=ykZgfSxkAv4P3LBFQjg@mail.gmail.com>
 <52A62771.3070800@vmware.com>
 <CAPpHfdu2nXxxNCmtMBBiS+3CRdgF8AHCLt2w9Z4s2kKisJSPuA@mail.gmail.com>
 <52AEE445.1060206@vmware.com>
 <CAPpHfdvK3eZr8iQJtp9ax9k80MKRKkPKgqcc0SB1bn+_KVq-Xg@mail.gmail.com>
 <52AF837C.3040201@vmware.com>
 <CAPpHfdvmRhW_rSCo90Hcu+0xBUVvxmtgW0arKRQDbXcDdNANgw@mail.gmail.com>
 <52B1B63F.6030104@vmware.com>
 <CAF4Au4zf4Nc1=SqeLa4HVY8QJS5sxjvFcJw2a+HHHNi8ERy9AA@mail.gmail.com>
In-Reply-To: 
 <CAF4Au4zf4Nc1=SqeLa4HVY8QJS5sxjvFcJw2a+HHHNi8ERy9AA@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

On 12/19/2013 08:37 AM, Oleg Bartunov wrote:
> Guys,
>
> before digging deep into the art of comp/decomp world I'd like to know
> if you familiar with results of
> http://wwwconference.org/www2008/papers/pdf/p387-zhangA.pdf paper and
> some newer research ?

Yeah, I saw that paper.

> Do we agree in what we really want ? Basically,
> there are three main features: size, compression, decompression speed
> - we should take two :)

According to that Zhang et al paper you linked, the Vbyte method 
actually performs the worst on all of those measures. The other 
algorithms are quite similar in terms of size (PForDelta being the most 
efficient), while PForDelta is significantly faster to compress/decompress.

Just by looking at those numbers, PForDelta looks like a clear winner. 
However, it operates on much bigger batches than the other algorithms; I 
haven't looked at it in detail, but Zhang et al used 128 integer 
batches, and they say that 32 integers is the minimum batch size. If we 
want to use it for the inline posting lists stored in entry tuples, that 
would be quite wasteful if there are only a few item pointers on the tuple.

Also, in the tests I've run, the compression/decompression speed is not 
a significant factor in total performance, with either varbyte encoding 
or Simple9-like encoding I hacked together.

Actually, now that I think about this a bit more, maybe we should go 
with Rice encoding after all? It's the most efficient in terms of size, 
and I believe it would be fast enough.

> Should we design sort of plugin, which could support independent
> storage on disk, so users can apply different techniques, depending on
> data.
>
> What I want to say is that we certainly can play with this very
> challenged task, but we have limited time  before 9.4 and we should
> think in positive direction.

Once we have the code in place to deal with one encoding, it's easy to 
switch the implementation. Making it user-configurable or pluggable 
would be overkill IMHO.

What I'm saying is that we should make sure we get the page format right 
(in particular, I strongly feel we should use the self-contained 
PostingListSegment struct instead of item-indees that I mentioned in the 
other post), with the implementation details hidden in the functions in 
ginpostinglist.c. Then we can easily experiment with different algorithms.

- Heikki


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers