Re: GIN improvements part 1: additional information

On Mon, Dec 16, 2013 at 3:30 PM, Heikki Linnakangas <hlinnakangas(at)vmware(dot)com
> wrote:

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

Good idea. But:
1) We'll still need item indexes in the end of page for fast scan.
2) Storage would be easily extendable to hold additional information as
well.
Better compression shouldn't block more serious improvements.

------
With best regards,
Alexander Korotkov.