Horton

Re: Yet another fast GiST build

Darafei Komяpa Praliaskouski <me@komzpa.net>

View thread View on postgr.es
From: Darafei "Komяpa" Praliaskouski <me@komzpa.net>
To: Yuri Astrakhan <yuriastrakhan@gmail.com>
Cc: PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>, Andrey Borodin <x4mmm@yandex-team.ru>
Date: 2020-04-05T09:48:33Z
Lists: pgsql-hackers 
Hello Yuri,

PDEP is indeed first thing that comes up when you start googling
z-curve and bit interleaving :)
We had the code with z-curve generating PDEP instruction in PostGIS,
and dropped it since. In sorting, we now utilize sort support / prefix
search, and key generated as Hilbert curve, with fine tuning it for
different projections' geometric properties.

From this patch the most valuable thing for us is the sorting build
infrastructure itself. Maybe to get it a bit more understandable for
people not deep in geometry it makes sense to first expose the
btree_gist datatypes to this thing? So that btree_gist index on
integer will be built exactly the same way the btree index on integer
is built. This will also get everyone a reference point on the
bottlenecks and optimality of patch.

On Fri, Apr 3, 2020 at 10:56 AM Yuri Astrakhan <yuriastrakhan@gmail.com> wrote:
>
> Awesome addition!  Would it make sense to use x86's BMI2's PDEP instruction, or is the interleave computation too small of a percentage to introduce not-so-easy-to-port code?  Also, I think it needs a bit more documentation to explain the logic, i.e. a link to https://stackoverflow.com/questions/39490345/interleave-bits-efficiently ?  Thx for making it faster :)



-- 
Darafei Praliaskouski
Support me: http://patreon.com/komzpa

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.