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

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

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/2a6368343ff43743ddd90d0f4c2d0ac03e18aa85

Modified Files
--------------
doc/src/sgml/indices.sgml                   |   7 +
doc/src/sgml/spgist.sgml                    |  58 +-
doc/src/sgml/xindex.sgml                    |   2 +-
src/backend/access/gist/gistget.c           |  46 +-
src/backend/access/gist/gistutil.c          |  37 +-
src/backend/access/index/indexam.c          |  70 +++
src/backend/access/spgist/Makefile          |   3 +-
src/backend/access/spgist/README            |   6 +-
src/backend/access/spgist/spgkdtreeproc.c   |  82 ++-
src/backend/access/spgist/spgproc.c         |  88 +++
src/backend/access/spgist/spgquadtreeproc.c | 115 +++-
src/backend/access/spgist/spgscan.c         | 875 +++++++++++++++++++---------
src/backend/access/spgist/spgutils.c        |  92 ++-
src/backend/access/spgist/spgvalidate.c     |  27 +-
src/backend/utils/adt/geo_spgist.c          |  97 ++-
src/backend/utils/cache/lsyscache.c         |  68 +++
src/include/access/genam.h                  |   3 +
src/include/access/spgist.h                 |  13 +-
src/include/access/spgist_private.h         |  48 +-
src/include/catalog/catversion.h            |   2 +-
src/include/catalog/pg_amop.dat             |  12 +
src/include/utils/lsyscache.h               |   3 +
src/test/regress/expected/amutils.out       |  27 +-
src/test/regress/expected/create_index.out  | 139 +++++
src/test/regress/expected/opr_sanity.out    |   3 +-
src/test/regress/expected/polygon.out       |  48 ++
src/test/regress/sql/amutils.sql            |   3 +-
src/test/regress/sql/create_index.sql       |  78 +++
src/test/regress/sql/polygon.sql            |  33 ++
29 files changed, 1669 insertions(+), 416 deletions(-)