Horton

Re: Yet another fast GiST build

Heikki Linnakangas <hlinnaka@iki.fi>

View thread View on postgr.es
From: Heikki Linnakangas <hlinnaka@iki.fi>
To: "Andrey M. Borodin" <x4mmm@yandex-team.ru>, Thomas Munro <thomas.munro@gmail.com>
Cc: Michael Paquier <michael@paquier.xyz>, Alexander Korotkov <a.korotkov@postgrespro.ru>, Darafei Komяpa Praliaskouski <me@komzpa.net>, pgsql-hackers <pgsql-hackers@postgresql.org>
Date: 2020-09-07T09:47:16Z
Lists: pgsql-hackers

Attachments

On 24/02/2020 10:50, Andrey M. Borodin wrote:
>> On 24 февр. 2020 г., at 01:58, Thomas Munro <thomas.munro@gmail.com> wrote:
>>
>> On Thu, Feb 20, 2020 at 10:14 AM Thomas Munro <thomas.munro@gmail.com> wrote:
>>> 1.  We expect floats to be in IEEE format, and the sort order of IEEE
>>> floats is mostly correlated to the binary sort order of the bits
>>> reinterpreted as an int.  It isn't in some special cases, but for this
>>> use case we don't really care about that, we're just trying to
>>> encourage locality.
>>
>> I suppose there is a big jump in integer value (whether signed or
>> unsigned) as you cross from positive to negative floats, and then the
>> sort order is reversed.  I have no idea if either of those things is a
>> problem worth fixing.  That made me wonder if there might also be an
>> endianness problem.  It seems from some quick googling that all
>> current architectures have integers and floats of the same endianness.
>> Apparently this wasn't always the case, and some ARMs have a weird
>> half-flipped arrangement for 64 bit floats, but not 32 bit floats as
>> you are using here.
> 
> Yes, this leap is a problem for point as generic data type. And I do not know
> how to fix it. It can cause inefficient Index Scans when searching near (0,0) and query
> window touches simultaneously all quadrants (4x slower).

I took a stab at fixing this, see attached patch (applies on top of your 
patch v14).

To evaluate this, I used the other attached patch to expose the zorder 
function to SQL, and plotted points around zero with gnuplot. See the 
attached two images, one with patch v14, and the other one with this patch.

I'll continue looking at these patches in whole tomorrow. I think it's 
getting close to a committable state.

> But everything will be just fine when all data is in 2nd quadrant.

Simon Riggs and friends would agree :-)

- Heikki

Commits

  1. Add sortsupport for gist_btree opclasses, for faster index builds.

  2. pageinspect: Fix relcache leak in gist_page_items().

  3. Fix test failure with wal_level=minimal.

  4. Enhance nbtree index tuple deletion.

  5. Fix portability issues in the new gist pageinspect test.

  6. Add functions to 'pageinspect' to inspect GiST indexes.

  7. Fix missing validation for the new GiST sortsupport functions.

  8. Fix compilation warning in xlog.c

  9. Set right-links during sorted GiST index build.

  10. Fix checksum calculation in the new sorting GiST build.

  11. Add support for building GiST index by sorting.