Horton

Add support for nearest-neighbor (KNN) searches to SP-GiST

Alexander Korotkov <akorotkov@postgresql.org>

View on postgr.es
Commit: 2a6368343ff43743ddd90d0f4c2d0ac03e18aa85
Author: Alexander Korotkov <akorotkov@postgresql.org>
Date: 2018-09-18T22:54:10Z
Releases: 12.0 
Add support for nearest-neighbor (KNN) searches to SP-GiST

Currently, KNN searches were supported only by GiST.  SP-GiST also capable to
support them.  This commit implements that support.  SP-GiST scan stack is
replaced with queue, which serves as stack if no ordering is specified.  KNN
support is provided for three SP-GIST opclasses: quad_point_ops, kd_point_ops
and poly_ops (catversion is bumped).  Some common parts between GiST and SP-GiST
KNNs are extracted into separate functions.

Discussion: https://postgr.es/m/570825e8-47d0-4732-2bf6-88d67d2d51c8%40postgrespro.ru
Author: Nikita Glukhov, Alexander Korotkov based on GSoC work by Vlad Sterzhanov
Review: Andrey Borodin, Alexander Korotkov

Files

PathChange+/−
doc/src/sgml/indices.sgml modified +7 −0
doc/src/sgml/spgist.sgml modified +53 −5
doc/src/sgml/xindex.sgml modified +1 −1
src/backend/access/gist/gistget.c modified +5 −41
src/backend/access/gist/gistutil.c modified +6 −31
src/backend/access/index/indexam.c modified +70 −0
src/backend/access/spgist/Makefile modified +2 −1
src/backend/access/spgist/README modified +5 −1
src/backend/access/spgist/spgkdtreeproc.c modified +80 −2
src/backend/access/spgist/spgproc.c added +88 −0
src/backend/access/spgist/spgquadtreeproc.c modified +114 −1
src/backend/access/spgist/spgscan.c modified +584 −291
src/backend/access/spgist/spgutils.c modified +90 −2
src/backend/access/spgist/spgvalidate.c modified +17 −10
src/backend/utils/adt/geo_spgist.c modified +88 −9
src/backend/utils/cache/lsyscache.c modified +68 −0
src/include/access/genam.h modified +3 −0
src/include/access/spgist.h modified +11 −2
src/include/access/spgist_private.h modified +45 −3
src/include/catalog/catversion.h modified +1 −1
src/include/catalog/pg_amop.dat modified +12 −0
src/include/utils/lsyscache.h modified +3 −0
src/test/regress/expected/amutils.out modified +14 −13
src/test/regress/expected/create_index.out modified +139 −0
src/test/regress/expected/opr_sanity.out modified +2 −1
src/test/regress/expected/polygon.out modified +48 −0
src/test/regress/sql/amutils.sql modified +2 −1
src/test/regress/sql/create_index.sql modified +78 −0
src/test/regress/sql/polygon.sql modified +33 −0

Documentation touched

Discussion