pg.ddx.io  pgsql-hackers@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Heikki Linnakangas <hlinnakangas@vmware.com>
To: obartunov@gmail.com
Cc: Alexander Korotkov <aekorotkov@gmail.com>
Cc: Alvaro Herrera <alvherre@2ndquadrant.com>
Cc: Tomas Vondra <tv@fuzzy.cz>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: GIN improvements part 1: additional information
Date: Thu, 19 Dec 2013 10:44:07 +0200
Message-ID: <52B2B1D7.2050802@vmware.com> (raw)
In-Reply-To: <CAF4Au4zf4Nc1=SqeLa4HVY8QJS5sxjvFcJw2a+HHHNi8ERy9AA@mail.gmail.com>
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>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>

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



view thread (119+ messages)  latest in thread

Message-ID: <52B2B1D7.2050802@vmware.com>
Permalink:  ../52B2B1D7.2050802@vmware.com/
Also on:    postgresql.org/message-id/52B2B1D7.2050802@vmware.com

 · 

reply
Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-hackers@postgresql.org
  Cc: hlinnakangas@vmware.com, obartunov@gmail.com, aekorotkov@gmail.com, alvherre@2ndquadrant.com, tv@fuzzy.cz
  Subject: Re: GIN improvements part 1: additional information
  In-Reply-To: <52B2B1D7.2050802@vmware.com>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox