Yet another fast GiST build

> On 29 февр. 2020 г., at 17:20, Erik Rijkers <[hidden email]> wrote:
>
> Small typo alert:
> In v5-0002-Implement-GiST-build-using-sort-support.patch there is:
>
> +   method is also optional and is used diring fast GiST build.
>
> 'diring' should be 'during'
>

Thanks!

I've fixed this and added patch with GiST reloption to provide sort support function.

Best regards, Andrey Borodin.

Hello,

Thanks for the patch and working on GiST infrastructure, it's really
valuable for PostGIS use cases and I wait to see this improvement in
PG13.

On Sat, Feb 29, 2020 at 3:13 PM Andrey M. Borodin <[hidden email]> wrote:

> Thomas, I've used your wording almost exactly with explanation how
> point_zorder_internal() works. It has more explanation power than my attempts
> to compose good comment.

PostGIS uses this trick to ensure locality. In PostGIS 3 we enhanced
that trick to have the Hilbert curve instead of Z Order curve.

For visual representation have a look at these links:
 - http://blog.cleverelephant.ca/2019/08/postgis-3-sorting.html - as
it's implemented in PostGIS btree sorting opclass
 - https://observablehq.com/@mourner/hilbert-curve-packing - to
explore general approach.

Indeed if it feels insecure to work with bit magic that implementation
can be left out to extensions.

> There is one design decision that worries me most:
> should we use opclass function or index option to provide this sorting information?
> It is needed only during index creation, actually. And having extra i-class only for fast build
> seems excessive.
> I think we can provide both ways and let opclass developers decide?

Reloption variant looks dirty. It won't cover an index on (id uuid,
geom geometry) where id is duplicated (say, tracked car identifier)
but present in every query - no way to pass such thing as reloption.
I'm also concerned about security of passing a sortsupport function
manually during index creation (what if that's not from the same
extension or even (wrong-)user defined something).

We know for sure it's a good idea for all btree_gist types and
geometry and I don't see a case where user would want to disable it.
Just make it part of operator class, and that would also allow fast
creation of multi-column index.

Thanks.

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

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 :)

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 <[hidden email]> 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

> On 29 Feb 2020, at 18:24, Andrey M. Borodin <[hidden email]> wrote:

> I've fixed this and added patch with GiST reloption to provide sort support function.

0002 in this patchset fails to apply, please submit a rebased version.  I've
marked the entry Waiting for Author in the meantime.

cheers ./daniel

> 1 июля 2020 г., в 17:05, Daniel Gustafsson <[hidden email]> написал(а):
>
>> On 29 Feb 2020, at 18:24, Andrey M. Borodin <[hidden email]> wrote:
>
>> I've fixed this and added patch with GiST reloption to provide sort support function.
>
> 0002 in this patchset fails to apply, please submit a rebased version.  I've
> marked the entry Waiting for Author in the meantime.

Thanks, Daniel!

PFA v7.

Best regards, Andrey Borodin.

Oops. I've mismerged docs and did not notice this with check world. PFA v8 with fixed docs.

Best regards, Andrey Borodin.

On Tue, Jul 7, 2020 at 7:03 PM Andrey M. Borodin <[hidden email]> wrote:
> Oops. I've mismerged docs and did not notice this with check world. PFA v8 with fixed docs.

It looks like point_zorder_internal() has the check for NaN in the wrong place.

> 10 июля 2020 г., в 10:53, Thomas Munro <[hidden email]> написал(а):
>
> On Tue, Jul 7, 2020 at 7:03 PM Andrey M. Borodin <[hidden email]> wrote:
>> Oops. I've mismerged docs and did not notice this with check world. PFA v8 with fixed docs.
>
> It looks like point_zorder_internal() has the check for NaN in the wrong place.
Thanks! Fixed.

Best regards, Andrey Borodin.

On Fri, Jul 10, 2020 at 6:55 PM Andrey M. Borodin <[hidden email]> wrote:
> Thanks! Fixed.

It's not a bug, but I think those 64 bit constants should be wrapped
in UINT64CONST(), following our convention.

I'm confused about these two patches: 0001 introduces
gist_point_fastcmp(), but then 0002 changes it to gist_bbox_fastcmp().
Maybe you intended to keep both of them?  Also 0002 seems to have
fixups for 0001 squashed into it.

> 30 июля 2020 г., в 06:26, Thomas Munro <[hidden email]> написал(а):
>
> On Fri, Jul 10, 2020 at 6:55 PM Andrey M. Borodin <[hidden email]> wrote:
>> Thanks! Fixed.
>
> It's not a bug, but I think those 64 bit constants should be wrapped
> in UINT64CONST(), following our convention.
Thanks, fixed!

> I'm confused about these two patches: 0001 introduces
> gist_point_fastcmp(), but then 0002 changes it to gist_bbox_fastcmp().
> Maybe you intended to keep both of them?  Also 0002 seems to have
> fixups for 0001 squashed into it.
Indeed, that were fixups: point converted to GiST representation is a bbox already, and the function expects only bboxes.

Also I've fixed some mismerges in documentation.

Thanks!

Best regards, Andrey Borodin.

--

The following review has been posted through the commitfest application:
make installcheck-world:  tested, passed
Implements feature:       tested, passed
Spec compliant:           not tested
Documentation:            not tested

I consider this patch almost ready for commit with minor corrections (see previous message)

The new status of this patch is: Waiting on Author

> 14 авг. 2020 г., в 14:21, Pavel Borisov <[hidden email]> написал(а):
>
> I see this feature quite useful in concept and decided to test it.

Thanks for reviewing and benchmarking, Pavel!

I agree with your suggestions. PFA patch with relevant changes.

Thanks a lot.

Best regards, Andrey Borodin.

> 23 авг. 2020 г., в 14:39, Andrey M. Borodin <[hidden email]> написал(а):
>
> Thanks for reviewing and benchmarking, Pavel!

Pavel sent me few typos offlist. PFA v12 fixing these typos.
Thanks!

Best regards, Andrey Borodin.

On 30/08/2020 15:04, Andrey M. Borodin wrote:
>> 23 авг. 2020 г., в 14:39, Andrey M. Borodin <[hidden email]> написал(а):
>>
>> Thanks for reviewing and benchmarking, Pavel!
>
> Pavel sent me few typos offlist. PFA v12 fixing these typos.

In gist_indexsortbuild(), you first build all the leaf pages. Then, you
read through all the index pages you just built, to form the tuples for
the next level, and repeat for all the upper levels. That seems
inefficient, it would be more better to form the tuples for the
downlinks as you go, when you build the leaf pages in the first place.
That's how nbtsort.c works. Also, you could WAL-log the pages as you go.

In gist_indexsortbuild_flush(), can't you just memcpy() the page from
memory to the buffer?

- Heikki

But I've found out that logging page-by-page slows down GiST build by approximately 15% (when CPU constrained).
Though In think that this is IO-wise.

Thanks!

Best regards, Andrey Borodin.

On 05/09/2020 14:53, Andrey M. Borodin wrote:
> Thanks for ideas, Heikki. Please see v13 with proposed changes.

Thanks, that was quick!

> But I've found out that logging page-by-page slows down GiST build by
> approximately 15% (when CPU constrained). Though In think that this
> is IO-wise.
Hmm, any ideas why that is? log_newpage_range() writes one WAL record
for 32 pages, while now you're writing one record per page, so you'll
have a little bit more overhead from that. But 15% seems like a lot.

- Heikki

Nevertheless, here's the patch identical to v13, but with 3rd part: log flushed pages with bunches of 32.
This brings CPU performance back and slightly better than before page-by-page logging.

Some details about test:
MacOS, 6-core i7
psql -c '\timing' -c "create table x as select point (random(),random()) from generate_series(1,10000000,1);" -c "create index on x using gist (point);"

With patch v13 this takes 20,567 seconds, with v14 18,149 seconds, v12 ~18,3s (which is closer to 10% btw, sorry for miscomputation). This was not statistically significant testing, just a quick laptop benchmark with 2-3 tests to verify stability.

Best regards, Andrey Borodin.