Re: GIN improvements part 1: additional information

On Tue, Dec 17, 2013 at 2:49 AM, Heikki Linnakangas <hlinnakangas(at)vmware(dot)com
> wrote:

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

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.

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