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: Wed, 18 Dec 2013 16:50:39 +0200
Message-ID: <52B1B63F.6030104@vmware.com> (raw)
In-Reply-To: <CAPpHfdvmRhW_rSCo90Hcu+0xBUVvxmtgW0arKRQDbXcDdNANgw@mail.gmail.com>
References: <CAPpHfdutJEC9+6vWX579afZKzdHKCT2wzDkAEom1XmiXEwF3pw@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>
<52AF837C.3040201@vmware.com>
<CAPpHfdvmRhW_rSCo90Hcu+0xBUVvxmtgW0arKRQDbXcDdNANgw@mail.gmail.com>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
On 12/18/2013 01:45 PM, Alexander Korotkov wrote:
> On Tue, Dec 17, 2013 at 2:49 AM, Heikki Linnakangas <hlinnakangas@vmware.com
>> wrote:
>
>> On 12/17/2013 12:22 AM, Alexander Korotkov wrote:
>> 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?
>
> I was planned to store additional information datums between
> varbyte-encoded tids. I was expected it would be hard to do with PFOR.
> However, I don't see significant problems in your implementation of Simple9
> encoding. I'm going to dig deeper in your version of patch.
Ok, thanks.
I had another idea about the page format this morning. Instead of having
the item-indexes at the end of the page, it would be more flexible to
store a bunch of self-contained posting list "segments" on the page. So
I propose that we get rid of the item-indexes, and instead store a bunch
of independent posting lists on the page:
typedef struct
{
ItemPointerData first; /* first item in this segment (unpacked) */
uint16 nwords; /* number of words that follow */
uint64 words[1]; /* var length */
} PostingListSegment;
Each segment can be encoded and decoded independently. When searching
for a particular item (like on insertion), you skip over segments where
'first' > the item you're searching for.
This format offers a lot more flexibility compared to the separate item
indexes. First, we don't need to have another fixed sized area on the
page, which simplifies the page format. Second, we can more easily
re-encode only one segment on the page, on insertion or vacuum. The
latter is particularly important with the Simple-9 encoding, which
operates one word at a time rather than one item at a time; removing or
inserting an item in the middle can require a complete re-encoding of
everything that follows. Third, when a page is being inserted into and
contains only uncompressed items, you don't waste any space for unused
item indexes.
While we're at it, I think we should use the above struct in the inline
posting lists stored directly in entry tuples. That wastes a few bytes
compared to the current approach in the patch (more alignment, and
'words' is redundant with the number of items stored on the tuple
header), but it simplifies the functions handling these lists.
- Heikki
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
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: <52B1B63F.6030104@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