Re: Yet another fast GiST build

From: Heikki Linnakangas <hlinnaka(at)iki(dot)fi>
To: "Andrey M(dot) Borodin" <x4mmm(at)yandex-team(dot)ru>, Thomas Munro <thomas(dot)munro(at)gmail(dot)com>
Cc: Michael Paquier <michael(at)paquier(dot)xyz>, Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru>, Darafei Komяpa Praliaskouski <me(at)komzpa(dot)net>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Yet another fast GiST build
Date: 2020-09-07 09:47:16
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

On 24/02/2020 10:50, Andrey M. Borodin wrote:
>> On 24 февр. 2020 г., at 01:58, Thomas Munro <thomas(dot)munro(at)gmail(dot)com> wrote:
>> On Thu, Feb 20, 2020 at 10:14 AM Thomas Munro <thomas(dot)munro(at)gmail(dot)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

Attachment Content-Type Size
v15-0003-Expose-point_zorder-to-SQL.patch text/x-patch 1.7 KB
v15-0004-Map-negative-values-better.patch text/x-patch 7.1 KB
image/png 45.9 KB
image/png 42.1 KB
gist-point-test.sql application/sql 487 bytes

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Asif Rehman 2020-09-07 10:02:49 Re: Allow CURRENT_ROLE in GRANTED BY
Previous Message Magnus Hagander 2020-09-07 09:42:04 Re: A micro-optimisation for walkdir()