Message-ID: <52AEE445.1060206@vmware.com>
Date: Mon, 16 Dec 2013 13:30:13 +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: Alexander Korotkov <aekorotkov@gmail.com>
CC: 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>
 <CAPpHfdu5ODt1UB5SSpMHHD6LCB+k_t6XCsLBozZP_dyVm1ieLQ@mail.gmail.com>
 <52546434.1000303@vmware.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>
In-Reply-To: 
 <CAPpHfdu2nXxxNCmtMBBiS+3CRdgF8AHCLt2w9Z4s2kKisJSPuA@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

On 12/12/2013 06:44 PM, Alexander Korotkov wrote:
> I've thought about different algorithms little more. General problem I see
> is online update. We need it while it is typically not covered by
> researches at all. We already have to invent small index in the end of
> page. Different encoding methods adds more challenges. In general, methods
> can be classified in two groups:
> 1) Values aren't aligned by bytes (gamma-codes, PFOR etc.)
> 2) Multiple values are packed together in small group (simple-9, simple-18)

Ok.

> For the first group of methods when inserting in the middle of the page we
> would have to do not byte-aligned shift of right part of values. I don't
> know how expensive is this shift but I expect that it would be much slower
> than memmove.

Agreed.

> 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.

- Heikki


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