Subject: Re: Yet another fast GiST build
To: "Andrey M. Borodin" <x4mmm@yandex-team.ru>,
 =?UTF-8?Q?Darafei_Kom=d1=8fpa_Praliaskouski?= <me@komzpa.net>
Cc: Pavel Borisov <pashkin.elfe@gmail.com>,
 Thomas Munro <thomas.munro@gmail.com>, Michael Paquier
 <michael@paquier.xyz>, Alexander Korotkov <a.korotkov@postgrespro.ru>,
 pgsql-hackers <pgsql-hackers@postgresql.org>
References: <1A36620E-CAD8-4267-9067-FB31385E7C0D@yandex-team.ru>
 <A4FC0488-FA18-4F06-A299-5BD4A1F64574@yandex-team.ru>
 <20191201020635.GL2355@paquier.xyz>
 <68F82C0C-F4E4-475B-BD25-386CF1FA2009@yandex-team.ru>
 <CA+hUKGKZzJhYMOHHMqXJX-yif20VieYE8vYU_irycLksvem0JA@mail.gmail.com>
 <CA+hUKGJbc3smQiyxef-mbJOo64u2DYdc6yZY7ess0Je5kytRpg@mail.gmail.com>
 <CA+hUKGK3D-X0ZvhLRUJf0wfpLKUuntj1ULc1V9_F0Ay5tNV+Jw@mail.gmail.com>
 <F2825F5A-B051-4F87-BD92-5FBBF036A385@yandex-team.ru>
 <efbd4ec6-80af-6fda-5c96-4209c25b0247@iki.fi>
 <CALT9ZEEtc67W6ypNcyOwwgryA+QjOFdL6M2+LhdkLpkzwtUbdQ@mail.gmail.com>
 <08173bd0-488d-da76-a904-912c35da446b@iki.fi>
 <1B32CF2B-4BB6-46DF-A84B-24CC22608EEA@yandex-team.ru>
 <CALT9ZEF_DHwJ+SmTj4t=3Oy2ErM6T-x17QsV=PhcME9e_CaoNQ@mail.gmail.com>
 <92dceca4-28f0-2f37-7d3f-71b5e8f0bf92@iki.fi>
 <457812DD-A619-4742-80F3-7EFC7AF6521C@yandex-team.ru>
 <CAC8Q8t+0sHUWZTpk23QnW5UFAn1kuNq+YhM6encWxZXWz32e4Q@mail.gmail.com>
 <21D103AD-E510-4699-8BE5-D462B42A64C8@yandex-team.ru>
From: Heikki Linnakangas <hlinnaka@iki.fi>
Message-ID: <7d9158ca-d7cb-88f0-dbbd-1d5cec32b1ae@iki.fi>
Date: Wed, 9 Sep 2020 15:09:16 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
 Thunderbird/68.11.0
MIME-Version: 1.0
In-Reply-To: <21D103AD-E510-4699-8BE5-D462B42A64C8@yandex-team.ru>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Precedence: bulk

On 09/09/2020 13:28, Andrey M. Borodin wrote:
> Thanks Darafei!
> 
>> 9 сент. 2020 г., в 12:05, Darafei Komяpa Praliaskouski
>> <me@komzpa.net> написал(а):
>> 
>>> How does the 'sortsupport' routine interact with
>>> 'compress'/'decompress'? Which representation is passed to the
>>> comparator routine: the original value from the table, the
>>> compressed representation, or the decompressed representation? Do
>>> the comparetup_index_btree() and readtup_index() routines agree
>>> with that?
>> 
>> Currently we pass compressed values, which seems not very good. But
>> there was a request from PostGIS maintainers to pass values before
>> decompression. Darafei, please, correct me if I'm wrong. Also can
>> you please provide link on PostGIS B-tree sorting functions?
>> 
>> We were expecting to reuse btree opclass for this thing. This way
>> btree_gist extension will become a lot thinner. :)
> 
> I think if we aim at reusing B-tree sort support functions we have to
> pass uncompressed values. They can be a lot bigger and slower in case
> of PostGIS. We will be sorting actual geometries instead of MBRs.
> 
> In my view it's better to implement GiST-specific sort support in
> btree_gist, rather than trying to reuse existing sort supports.

Yeah, I don't think reusing existing sortsupport functions directly is 
important. The comparison function should be short anyway for 
performance reasons, so it won't be a lot of code to copy-paste. And if 
there are some common subroutines, you can put them in a separate 
internal functions for reuse.

Using the 'compressed' format seems reasonable to me. It's natural to 
the gistbuild.c code, and the comparison routine can 'decompress' itself 
if it wishes. If the decompressions is somewhat expensive, it's 
unfortunate if you need to do it repeatedly in the comparator, but 
tuplesort.c would need pretty big changes to keep around a separate 
in-memory representation compare. However, you could use the sort 
"abbreviation" functionality to mitigate that.

Come to think of it, the point z-order comparator could benefit a lot 
from key abbreviation, too. You could do the point -> zorder conversion 
in the abbreviation routine.

- Heikki