From: Nikita Glukhov <n(dot)gluhov(at)postgrespro(dot)ru>
To: Andrey Borodin <x4mmm(at)yandex-team(dot)ru>
Cc: Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru>, David Steele <david(at)pgmasters(dot)net>, Andres Freund <andres(at)anarazel(dot)de>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: [HACKERS] [PATCH] kNN for SP-GiST
Date: 2018-07-13 21:31:50
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

Attached  6th version of the patches.

On 09.07.2018 20:47, Andrey Borodin wrote:

>> 4 июля 2018 г., в 3:21, Nikita Glukhov <n(dot)gluhov(at)postgrespro(dot)ru> написал(а):
>> Attached 5th version of the patches, where minor refactoring of distance
>> handling was done (see below).
> I'm reviewing this patch. Currently I'm trying to understand sp-gist scan
> deeeper, but as for now have some small notices.

Thank your for your review.

> Following directives can be omitted:
> #include "lib/rbtree.h"
> #include "storage/relfilenode.h"
> This message is not noly GiST related, is it?
> elog(ERROR, "GiST operator family's FOR ORDER BY operator must return float8 or float4 if the distance function is lossy");
> Some small typos:
> usefull -> useful
> nearest-neighbour -> nearest-neighbor (or do we use e.g. "colour"?)


On 10.07.2018 20:09, Andrey Borodin wrote:

> I've passed through the code one more time. Here are few more questions:
> 1. Logic behind division of the patch into steps is described last time
> 2017-01-30, but ISTM actual steps have changed since than? May I ask you
> to write a bit about steps of the patchset?

A brief description of the current patch set:
1. Exported two box functions that are used in patch 5.
2. Extracted subroutine index_store_float8_orderby_distances() from GiST code
 that is common for GiST, SP-GiST, and possibly other kNN implementations
 (used in patch 4).
3. Extracted two subroutines from GiST code common for gistproperty() and
spgistproperty() (used in path 4).
4. The main patch: added kNN support to SP-GiST.
This patch in theory can be split into two patches: refactoring and kNN
support, but it will require some additional effort.
Refactoring basically consists in the extraction of spgInnerTest(),
spgTestLeafTuple(), spgMakeInnerItem() subroutines.
A more detailed commit history can be found in my github [1].
5. Added ordering operator point <-> point to kd_point_ops and quad_point_ops.
6. Added ordering operator polygon <-> point to poly_ops.

> 2. The patch leaves contribs intact. Do extensions with sp-gist opclasses
> need to update it's behavior somehow to be used as-is? Or to support new
> functionality?

There are no SP-GiST opclasses in contrib/, so there is nothing to change in
contrib/. Moreover, existing extensions need to be updated only for support of
new distance-ordered searches -- they need to implement distances[][] array
calculation in their spgInnerConsistent() and spgLeafConsistent() support

> 3. There is a patch about predicate locking in SP-GiST [2] Is this KNN patch
> theoretically compatible with predicate locking? Seems like it is, I just
> want to note that this functionality may exist.

I think kNN is compatible with predicate locking. Patch [2] does not apply
cleanly on kNN but the conflict resolution is trivial.

> 4. Scan state now have scanStack and queue. May be it's better to name
> scanStack and scanQueue or stack and queue?

"queue" was renamed to "scanQueue".


Nikita Glukhov
Postgres Professional:
The Russian Postgres Company

Attachment Content-Type Size
0001-Export-box_fill-v06.patch text/x-patch 1.6 KB
0002-Extract-index_store_float8_orderby_distances-v06.patch text/x-patch 5.5 KB
0003-Extract-get_index_column_opclass-and-get_opclass_opfamily_and_input_type-v06.patch text/x-patch 5.1 KB
0004-Add-kNN-support-to-SP-GiST-v06.patch text/x-patch 50.6 KB
0005-Add-ordering-operators-to-SP-GiST-kd_point_ops-and-quad_point_ops-v06.patch text/x-patch 28.2 KB
0006-Add-ordering-operators-to-SP-GiST-poly_ops-v06.patch text/x-patch 9.7 KB

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Robert Haas 2018-07-13 21:56:40 Re: pgsql: Fix parallel index and index-only scans to fall back to serial.
Previous Message Tom Lane 2018-07-13 21:23:40 Re: cannot restore schema with is not distinct from on hstore since PG 9.6.8