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

help / color / mirror / Atom feed
From: Heikki Linnakangas <hlinnakangas@vmware.com>
To: 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: Tue, 17 Dec 2013 00:49:32 +0200
Message-ID: <52AF837C.3040201@vmware.com> (raw)
In-Reply-To: <CAPpHfdvK3eZr8iQJtp9ax9k80MKRKkPKgqcc0SB1bn+_KVq-Xg@mail.gmail.com>
References: <CAPpHfdutJEC9+6vWX579afZKzdHKCT2wzDkAEom1XmiXEwF3pw@mail.gmail.com>
	<52548F79.6030407@fuzzy.cz>
	<52569635.5090808@vmware.com>
	<CAPpHfduXkYv4uUHHFrCntNQD=JyB=xQXtutXeY_KYs6CBLJN0w@mail.gmail.com>
	<CAPpHfdvXET0Jk=-oWNGGywMZqbiWML4kg9=GvGY8Yruvbhe4BQ@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>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>

On 12/17/2013 12:22 AM, Alexander Korotkov wrote:
> On Mon, Dec 16, 2013 at 3:30 PM, Heikki Linnakangas <hlinnakangas@vmware.com
>> wrote:
>
>> On 12/12/2013 06:44 PM, Alexander Korotkov wrote:
>>
>>   When values are packed into small groups, we have to either insert
>>> inefficiently encoded value or re-encode whole right part of values.
>>
>> It would probably be simplest to store newly inserted items uncompressed,
>> in a separate area in the page. For example, grow the list of uncompressed
>> items downwards from pg_upper, and the compressed items upwards from
>> pg_lower. When the page fills up, re-encode the whole page.

I hacked together an implementation of a variant of Simple9, to see how 
it performs. Insertions are handled per the above scheme.

In a limited pg_trgm test case I've been using a lot for this, this 
reduces the index size about 20%, compared to varbyte encoding. It might 
be possible to squeeze it a bit more, I handcrafted the "selectors" in 
the encoding algorithm to suite our needs, but I don't actually have a 
good idea of how to choose them optimally. Also, the encoding can encode 
0 values, but we never need to do that, so you could take advantage of 
that to pack items tighter.

Compression and decompression speed seems to be about the same.

Patch attached if you want to play with it. WAL replay is still broken, 
and there are probably bugs.

> Good idea. But:
> 1) We'll still need item indexes in the end of page for fast scan.

Sure.

> 2) Storage would be easily extendable to hold additional information as
> well.
> Better compression shouldn't block more serious improvements.

I'm not sure I agree with that. For all the cases where you don't care 
about additional information - which covers all existing users for 
example - reducing disk size is pretty important. How are you planning 
to store the additional information, and how does using another encoding 
gets in the way of that?

- Heikki

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

Attachments:

  [application/x-gzip] gin-packed-postinglists-simple9-1.patch.gz (27.7K, ../52AF837C.3040201@vmware.com/2-gin-packed-postinglists-simple9-1.patch.gz)
  download

view thread (119+ messages)  latest in thread

Message-ID: <52AF837C.3040201@vmware.com>
Permalink:  ../52AF837C.3040201@vmware.com/
Also on:    postgresql.org/message-id/52AF837C.3040201@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, aekorotkov@gmail.com, alvherre@2ndquadrant.com, tv@fuzzy.cz
  Subject: Re: GIN improvements part 1: additional information
  In-Reply-To: <52AF837C.3040201@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