pgsql: Allow GiST distance function to return merely a lower-bound.

Allow GiST distance function to return merely a lower-bound.

The distance function can now set *recheck = false, like index quals. The
executor will then re-check the ORDER BY expressions, and use a queue to
reorder the results on the fly.

This makes it possible to do kNN-searches on polygons and circles, which
don't store the exact value in the index, but just a bounding box.

Alexander Korotkov and me

Branch
------
master

Details
-------
http://git.postgresql.org/pg/commitdiff/35fcb1b3d038a501f3f4c87c05630095abaaadab

Modified Files
--------------
doc/src/sgml/gist.sgml                     |   35 ++-
src/backend/access/gist/gistget.c          |   30 ++-
src/backend/access/gist/gistproc.c         |   37 +++
src/backend/access/gist/gistscan.c         |    5 +
src/backend/executor/nodeIndexscan.c       |  379 +++++++++++++++++++++++++++-
src/backend/optimizer/plan/createplan.c    |   73 ++++--
src/backend/utils/adt/geo_ops.c            |   27 ++
src/include/access/genam.h                 |    3 +
src/include/access/relscan.h               |    9 +
src/include/catalog/catversion.h           |    2 +-
src/include/catalog/pg_amop.h              |    2 +
src/include/catalog/pg_amproc.h            |    2 +
src/include/catalog/pg_operator.h          |    8 +-
src/include/catalog/pg_proc.h              |    4 +
src/include/nodes/execnodes.h              |   20 ++
src/include/nodes/plannodes.h              |   10 +-
src/include/utils/geo_decls.h              |    3 +
src/test/regress/expected/create_index.out |   78 ++++++
src/test/regress/sql/create_index.sql      |   12 +
19 files changed, 699 insertions(+), 40 deletions(-)