Horton

Re: Yet another fast GiST build

Thomas Munro <thomas.munro@gmail.com>

View thread View on postgr.es
From: Thomas Munro <thomas.munro@gmail.com>
To: Andrey Borodin <x4mmm@yandex-team.ru>
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-02-19T21:14:02Z
Lists: pgsql-hackers 
On Wed, Feb 19, 2020 at 8:00 PM Thomas Munro <thomas.munro@gmail.com> wrote:
> Could this function please have a comment that explains why it works?
> I mean, just a breadcrumb... the name of the technique or something...
> so that uninitiated hackers can google their way to a clue (is it
> "Morton encoding"?)

Ok I think I get it now after doing some homework.

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.
2.  We generate a Morton code that interleaves the bits of N integers
to produce a single integer that preserves locality: things that were
close in the N dimensional space are close in the resulting integer.

Cool.

+static int
+my_fastcmp(Datum x, Datum y, SortSupport ssup)
+{
+    /* esteblish order between x and y */
+
+    return z1 == z2 ? 0 : z1 > z2 ? 1 : -1;
+}

This example code from the documentation looks wrong, probably missing
eg int64 z1 = DatumGetInt64(x).

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.