Subject: Re: Yet another fast GiST build
To: Andrey Borodin <x4mmm@yandex-team.ru>
Cc: Peter Geoghegan <pg@bowt.ie>, Tom Lane <tgl@sss.pgh.pa.us>,
 Justin Pryzby <pryzby@telsasoft.com>,
 =?UTF-8?Q?Darafei_Kom=d1=8fpa_Praliaskouski?= <me@komzpa.net>,
 Pavel Borisov <pashkin.elfe@gmail.com>, Thomas Munro
 <thomas.munro@gmail.com>, Michael Paquier <michael@paquier.xyz>,
 Alexander Korotkov <a.korotkov@postgrespro.ru>,
 PostgreSQL Hackers <pgsql-hackers@postgresql.org>,
 Ibrar Ahmed <ibrar.ahmad@gmail.com>
References: <7d9158ca-d7cb-88f0-dbbd-1d5cec32b1ae@iki.fi>
 <059BD785-A6CE-4E34-B80B-38E9E0309B78@yandex-team.ru>
 <CAH2-WzkBwtk0Np0oZvpiywqjrVwZQtDHSjatJ54ofyezLBxzeQ@mail.gmail.com>
 <8ACF61CC-32ED-4B4B-A2BC-15264E02D24E@yandex-team.ru>
 <3E4F9093-A1B5-4DF8-A292-0B48692E3954@yandex-team.ru>
 <ea7d112f-755e-d194-1777-f10ca6f372b7@iki.fi>
 <9FCEC1DC-86FB-4A57-88EF-DD13663B36AF@yandex-team.ru>
 <c0a679f3-fc3f-4ab0-bb18-b848cd6e9aa6@iki.fi>
 <234863.1610916631@sss.pgh.pa.us>
 <CAH2-WznnqS7HcPhT5F-vFY82iBe4c6eboKB044Tc1N2bWRzuXw@mail.gmail.com>
 <5678c114-c298-ac70-8fba-8bd5c87b048a@iki.fi>
 <CALtqXTeRwyxvdB-fRcMnn4vD5A2rVyLp7+ZNtAuya7Y_u88QHg@mail.gmail.com>
 <CAH2-Wzn4LRvS8GpTrKZKL=s0brg9zm33qTkGMv4Regn6t6DjhQ@mail.gmail.com>
 <CALtqXTcExeND0cjtPiFNiUyANv2V9xfsr4axcnnyGJUYnsReiw@mail.gmail.com>
 <2F3F7265-0D22-44DB-AD71-8554C743D943@yandex-team.ru>
 <6d795a95-bb6b-b993-7c21-64bb7acd3648@iki.fi>
 <c0846e34-8b3a-e1bf-c88e-021eb241a481@iki.fi>
 <1D139BAE-C734-400C-85EA-B68C4E6EDA73@yandex-team.ru>
From: Heikki Linnakangas <hlinnaka@iki.fi>
Message-ID: <7386285b-0e2f-e89e-81f4-f63775becb2e@iki.fi>
Date: Wed, 7 Apr 2021 16:18:53 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101
 Thunderbird/78.9.0
MIME-Version: 1.0
In-Reply-To: <1D139BAE-C734-400C-85EA-B68C4E6EDA73@yandex-team.ru>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: 
 <https://www.postgresql.org/message-id/7386285b-0e2f-e89e-81f4-f63775becb2e%40iki.fi>
Precedence: bulk

On 07/04/2021 15:12, Andrey Borodin wrote:
>> 7 апр. 2021 г., в 14:56, Heikki Linnakangas <hlinnaka@iki.fi>
>> написал(а):
>> 
>> Ok, I think I understand that now. In btree_gist, the *_cmp()
>> function operates on non-leaf values, and *_lt(), *_gt() et al
>> operate on leaf values. For all other datatypes, the leaf and
>> non-leaf representation is the same, but for bit/varbit, the
>> non-leaf representation is different. The leaf representation is
>> VarBit, and non-leaf is just the bits without the 'bit_len' field.
>> That's why it is indeed correct for gbt_bitcmp() to just use
>> byteacmp(), whereas gbt_bitlt() et al compares the 'bit_len' field
>> separately. That's subtle, and 100% uncommented.
>> 
>> What that means for this patch is that gbt_bit_sort_build_cmp()
>> should *not* call byteacmp(), but bitcmp(). Because it operates on
>> the original datatype stored in the table.
> 
> +1 Thanks for investigating this. If I understand things right,
> adding test values with different lengths of bit sequences would not
> uncover the problem anyway?

That's right, the only consequence of a "wrong" sort order is that the 
quality of the tree suffers, and scans need to scan more pages 
unnecessarily.

I tried to investigate this by creating a varbit index with and without 
sorting, and compared them with pageinspect, but in quick testing, I 
wasn't able to find cases where the sorted version was badly ordered. I 
guess I didn't find the right data set yet.

- Heikki