Re: GIN improvements part 1: additional information

On 12/17/2013 12:22 AM, Alexander Korotkov wrote:
> 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:
>>
>> 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