pg.ddx.io pgsql-hackers@postgresql.org mailing list archive help / color / mirror / Atom feed From: Nikita Glukhov <n.gluhov@postgrespro.ru>
To: PostgreSQL Hackers <pgsql-hackers@postgresql.org>
Subject: Add missing operator <->(box, point)
Date: Mon, 11 Mar 2019 02:49:07 +0300
Message-ID: <f71ba19d-d989-63b6-f04a-abf02ad9345d@postgrespro.ru> (raw )
Hi, hackers.
Attached patches add missing distance operator <->(box, point).
We already have reverse operator <->(point, box), but it can't be used for kNN
search in GiST and SP-GiST. GiST and SP-GiST now support kNN searches over more
complex polygons and circles, but do not support more simple boxes, which seems
to be inconsistent.
Description of the patches:
1. Add function dist_pb(box, point) and operator <->.
2. Add <-> to GiST box_ops.
Extracted gist_box_distance_helper() common for gist_box_distance() and
gist_bbox_distance().
3. Add <-> to SP-GiST.
Changed only catalog and tests. Box case is already checked in
spg_box_quad_leaf_consistent():
out->recheckDistances = distfnoid == F_DIST_POLYP;
--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Attachments:
[text/x-patch] 0001-Add-box-point-distance-operator-v01.patch (10.2K, ../f71ba19d-d989-63b6-f04a-abf02ad9345d@postgrespro.ru/3-0001-Add-box-point-distance-operator-v01.patch)
download | inline diff:
From c2655e83ae0bd7798e5cfa1a38ace01e38f7f43b Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.gluhov@postgrespro.ru>
Date: Thu, 7 Mar 2019 20:22:49 +0300
Subject: [PATCH 1/3] Add operator <->(box, point)
---
src/backend/utils/adt/geo_ops.c | 12 +++++
src/include/catalog/pg_operator.dat | 5 +-
src/include/catalog/pg_proc.dat | 3 ++
src/test/regress/expected/geometry.out | 96 +++++++++++++++++-----------------
src/test/regress/sql/geometry.sql | 2 +-
5 files changed, 68 insertions(+), 50 deletions(-)
diff --git a/src/backend/utils/adt/geo_ops.c b/src/backend/utils/adt/geo_ops.c
index 28e85e3..a8f9111 100644
--- a/src/backend/utils/adt/geo_ops.c
+++ b/src/backend/utils/adt/geo_ops.c
@@ -2419,6 +2419,18 @@ dist_pb(PG_FUNCTION_ARGS)
}
/*
+ * Distance from a box to a point
+ */
+Datum
+dist_bp(PG_FUNCTION_ARGS)
+{
+ BOX *box = PG_GETARG_BOX_P(0);
+ Point *pt = PG_GETARG_POINT_P(1);
+
+ PG_RETURN_FLOAT8(box_closept_point(NULL, box, pt));
+}
+
+/*
* Distance from a lseg to a line
*/
Datum
diff --git a/src/include/catalog/pg_operator.dat b/src/include/catalog/pg_operator.dat
index 06aec07..ebace5a 100644
--- a/src/include/catalog/pg_operator.dat
+++ b/src/include/catalog/pg_operator.dat
@@ -666,7 +666,10 @@
oprresult => 'float8', oprcode => 'dist_ps' },
{ oid => '615', descr => 'distance between',
oprname => '<->', oprleft => 'point', oprright => 'box',
- oprresult => 'float8', oprcode => 'dist_pb' },
+ oprresult => 'float8', oprcom => '<->(box,point)', oprcode => 'dist_pb' },
+{ oid => '606', descr => 'distance between',
+ oprname => '<->', oprleft => 'box', oprright => 'point',
+ oprresult => 'float8', oprcom => '<->(point,box)', oprcode => 'dist_bp' },
{ oid => '616', descr => 'distance between',
oprname => '<->', oprleft => 'lseg', oprright => 'line',
oprresult => 'float8', oprcode => 'dist_sl' },
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 562c540..3800150 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -1062,6 +1062,9 @@
{ oid => '364',
proname => 'dist_pb', prorettype => 'float8', proargtypes => 'point box',
prosrc => 'dist_pb' },
+{ oid => '357',
+ proname => 'dist_bp', prorettype => 'float8', proargtypes => 'box point',
+ prosrc => 'dist_bp' },
{ oid => '365',
proname => 'dist_sb', prorettype => 'float8', proargtypes => 'lseg box',
prosrc => 'dist_sb' },
diff --git a/src/test/regress/expected/geometry.out b/src/test/regress/expected/geometry.out
index 055d32c..5efe80a 100644
--- a/src/test/regress/expected/geometry.out
+++ b/src/test/regress/expected/geometry.out
@@ -602,54 +602,54 @@ SELECT p.f1, l.s, p.f1 <-> l.s FROM POINT_TBL p, LSEG_TBL l;
(72 rows)
-- Distance to box
-SELECT p.f1, b.f1, p.f1 <-> b.f1 FROM POINT_TBL p, BOX_TBL b;
- f1 | f1 | ?column?
--------------------+---------------------+--------------------
- (0,0) | (2,2),(0,0) | 0
- (0,0) | (3,3),(1,1) | 1.41421356237
- (0,0) | (-2,2),(-8,-10) | 2
- (0,0) | (2.5,3.5),(2.5,2.5) | 3.53553390593
- (0,0) | (3,3),(3,3) | 4.24264068712
- (-10,0) | (2,2),(0,0) | 10
- (-10,0) | (3,3),(1,1) | 11.0453610172
- (-10,0) | (-2,2),(-8,-10) | 2
- (-10,0) | (2.5,3.5),(2.5,2.5) | 12.747548784
- (-10,0) | (3,3),(3,3) | 13.3416640641
- (-3,4) | (2,2),(0,0) | 3.60555127546
- (-3,4) | (3,3),(1,1) | 4.12310562562
- (-3,4) | (-2,2),(-8,-10) | 2
- (-3,4) | (2.5,3.5),(2.5,2.5) | 5.52268050859
- (-3,4) | (3,3),(3,3) | 6.0827625303
- (5.1,34.5) | (2,2),(0,0) | 32.6475113906
- (5.1,34.5) | (3,3),(1,1) | 31.5699223946
- (5.1,34.5) | (-2,2),(-8,-10) | 33.2664996656
- (5.1,34.5) | (2.5,3.5),(2.5,2.5) | 31.108841187
- (5.1,34.5) | (3,3),(3,3) | 31.5699223946
- (-5,-12) | (2,2),(0,0) | 13
- (-5,-12) | (3,3),(1,1) | 14.3178210633
- (-5,-12) | (-2,2),(-8,-10) | 2
- (-5,-12) | (2.5,3.5),(2.5,2.5) | 16.3248277173
- (-5,-12) | (3,3),(3,3) | 17
- (1e-300,-1e-300) | (2,2),(0,0) | 1.41421356237e-300
- (1e-300,-1e-300) | (3,3),(1,1) | 1.41421356237
- (1e-300,-1e-300) | (-2,2),(-8,-10) | 2
- (1e-300,-1e-300) | (2.5,3.5),(2.5,2.5) | 3.53553390593
- (1e-300,-1e-300) | (3,3),(3,3) | 4.24264068712
- (1e+300,Infinity) | (2,2),(0,0) | Infinity
- (1e+300,Infinity) | (3,3),(1,1) | Infinity
- (1e+300,Infinity) | (-2,2),(-8,-10) | Infinity
- (1e+300,Infinity) | (2.5,3.5),(2.5,2.5) | Infinity
- (1e+300,Infinity) | (3,3),(3,3) | Infinity
- (NaN,NaN) | (2,2),(0,0) | NaN
- (NaN,NaN) | (3,3),(1,1) | NaN
- (NaN,NaN) | (-2,2),(-8,-10) | NaN
- (NaN,NaN) | (2.5,3.5),(2.5,2.5) | NaN
- (NaN,NaN) | (3,3),(3,3) | NaN
- (10,10) | (2,2),(0,0) | 11.313708499
- (10,10) | (3,3),(1,1) | 9.89949493661
- (10,10) | (-2,2),(-8,-10) | 14.4222051019
- (10,10) | (2.5,3.5),(2.5,2.5) | 9.92471662064
- (10,10) | (3,3),(3,3) | 9.89949493661
+SELECT p.f1, b.f1, p.f1 <-> b.f1, b.f1 <-> p.f1 FROM POINT_TBL p, BOX_TBL b;
+ f1 | f1 | ?column? | ?column?
+-------------------+---------------------+--------------------+--------------------
+ (0,0) | (2,2),(0,0) | 0 | 0
+ (0,0) | (3,3),(1,1) | 1.41421356237 | 1.41421356237
+ (0,0) | (-2,2),(-8,-10) | 2 | 2
+ (0,0) | (2.5,3.5),(2.5,2.5) | 3.53553390593 | 3.53553390593
+ (0,0) | (3,3),(3,3) | 4.24264068712 | 4.24264068712
+ (-10,0) | (2,2),(0,0) | 10 | 10
+ (-10,0) | (3,3),(1,1) | 11.0453610172 | 11.0453610172
+ (-10,0) | (-2,2),(-8,-10) | 2 | 2
+ (-10,0) | (2.5,3.5),(2.5,2.5) | 12.747548784 | 12.747548784
+ (-10,0) | (3,3),(3,3) | 13.3416640641 | 13.3416640641
+ (-3,4) | (2,2),(0,0) | 3.60555127546 | 3.60555127546
+ (-3,4) | (3,3),(1,1) | 4.12310562562 | 4.12310562562
+ (-3,4) | (-2,2),(-8,-10) | 2 | 2
+ (-3,4) | (2.5,3.5),(2.5,2.5) | 5.52268050859 | 5.52268050859
+ (-3,4) | (3,3),(3,3) | 6.0827625303 | 6.0827625303
+ (5.1,34.5) | (2,2),(0,0) | 32.6475113906 | 32.6475113906
+ (5.1,34.5) | (3,3),(1,1) | 31.5699223946 | 31.5699223946
+ (5.1,34.5) | (-2,2),(-8,-10) | 33.2664996656 | 33.2664996656
+ (5.1,34.5) | (2.5,3.5),(2.5,2.5) | 31.108841187 | 31.108841187
+ (5.1,34.5) | (3,3),(3,3) | 31.5699223946 | 31.5699223946
+ (-5,-12) | (2,2),(0,0) | 13 | 13
+ (-5,-12) | (3,3),(1,1) | 14.3178210633 | 14.3178210633
+ (-5,-12) | (-2,2),(-8,-10) | 2 | 2
+ (-5,-12) | (2.5,3.5),(2.5,2.5) | 16.3248277173 | 16.3248277173
+ (-5,-12) | (3,3),(3,3) | 17 | 17
+ (1e-300,-1e-300) | (2,2),(0,0) | 1.41421356237e-300 | 1.41421356237e-300
+ (1e-300,-1e-300) | (3,3),(1,1) | 1.41421356237 | 1.41421356237
+ (1e-300,-1e-300) | (-2,2),(-8,-10) | 2 | 2
+ (1e-300,-1e-300) | (2.5,3.5),(2.5,2.5) | 3.53553390593 | 3.53553390593
+ (1e-300,-1e-300) | (3,3),(3,3) | 4.24264068712 | 4.24264068712
+ (1e+300,Infinity) | (2,2),(0,0) | Infinity | Infinity
+ (1e+300,Infinity) | (3,3),(1,1) | Infinity | Infinity
+ (1e+300,Infinity) | (-2,2),(-8,-10) | Infinity | Infinity
+ (1e+300,Infinity) | (2.5,3.5),(2.5,2.5) | Infinity | Infinity
+ (1e+300,Infinity) | (3,3),(3,3) | Infinity | Infinity
+ (NaN,NaN) | (2,2),(0,0) | NaN | NaN
+ (NaN,NaN) | (3,3),(1,1) | NaN | NaN
+ (NaN,NaN) | (-2,2),(-8,-10) | NaN | NaN
+ (NaN,NaN) | (2.5,3.5),(2.5,2.5) | NaN | NaN
+ (NaN,NaN) | (3,3),(3,3) | NaN | NaN
+ (10,10) | (2,2),(0,0) | 11.313708499 | 11.313708499
+ (10,10) | (3,3),(1,1) | 9.89949493661 | 9.89949493661
+ (10,10) | (-2,2),(-8,-10) | 14.4222051019 | 14.4222051019
+ (10,10) | (2.5,3.5),(2.5,2.5) | 9.92471662064 | 9.92471662064
+ (10,10) | (3,3),(3,3) | 9.89949493661 | 9.89949493661
(45 rows)
-- Distance to path
diff --git a/src/test/regress/sql/geometry.sql b/src/test/regress/sql/geometry.sql
index ce98b3e..9fbd123 100644
--- a/src/test/regress/sql/geometry.sql
+++ b/src/test/regress/sql/geometry.sql
@@ -77,7 +77,7 @@ SELECT p.f1, l.s, p.f1 <-> l.s FROM POINT_TBL p, LINE_TBL l;
SELECT p.f1, l.s, p.f1 <-> l.s FROM POINT_TBL p, LSEG_TBL l;
-- Distance to box
-SELECT p.f1, b.f1, p.f1 <-> b.f1 FROM POINT_TBL p, BOX_TBL b;
+SELECT p.f1, b.f1, p.f1 <-> b.f1, b.f1 <-> p.f1 FROM POINT_TBL p, BOX_TBL b;
-- Distance to path
SELECT p.f1, p1.f1, p.f1 <-> p1.f1 FROM POINT_TBL p, PATH_TBL p1;
--
2.7.4
[text/x-patch] 0002-Add-box-point-distance-operator-to-GiST-box_ops-v01.patch (9.0K, ../f71ba19d-d989-63b6-f04a-abf02ad9345d@postgrespro.ru/4-0002-Add-box-point-distance-operator-to-GiST-box_ops-v01.patch)
download | inline diff:
From cde6307a7d45d4df6b00a867e83f8748a9c2bc4f Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.gluhov@postgrespro.ru>
Date: Thu, 7 Mar 2019 23:49:31 +0300
Subject: [PATCH 2/3] Add operator <->(box, point) to GiST box_ops
---
doc/src/sgml/gist.sgml | 1 +
src/backend/access/gist/gistproc.c | 53 ++++++++++++++++++--------
src/include/catalog/pg_amop.dat | 3 ++
src/include/catalog/pg_amproc.dat | 2 +
src/include/catalog/pg_proc.dat | 4 ++
src/test/regress/expected/gist.out | 76 ++++++++++++++++++++++++++++++++++++++
src/test/regress/sql/gist.sql | 16 ++++++++
7 files changed, 140 insertions(+), 15 deletions(-)
diff --git a/doc/src/sgml/gist.sgml b/doc/src/sgml/gist.sgml
index 44a3b2c..e903319 100644
--- a/doc/src/sgml/gist.sgml
+++ b/doc/src/sgml/gist.sgml
@@ -83,6 +83,7 @@
<literal>~=</literal>
</entry>
<entry>
+ <literal><-></literal>
</entry>
</row>
<row>
diff --git a/src/backend/access/gist/gistproc.c b/src/backend/access/gist/gistproc.c
index c9da230..89643b4 100644
--- a/src/backend/access/gist/gistproc.c
+++ b/src/backend/access/gist/gistproc.c
@@ -1464,26 +1464,13 @@ gist_point_distance(PG_FUNCTION_ARGS)
PG_RETURN_FLOAT8(distance);
}
-/*
- * The inexact GiST distance method for geometric types that store bounding
- * boxes.
- *
- * Compute lossy distance from point to index entries. The result is inexact
- * because index entries are bounding boxes, not the exact shapes of the
- * indexed geometric types. We use distance from point to MBR of index entry.
- * This is a lower bound estimate of distance from point to indexed geometric
- * type.
- */
static float8
-gist_bbox_distance(GISTENTRY *entry, Datum query,
- StrategyNumber strategy, bool *recheck)
+gist_box_distance_helper(GISTENTRY *entry, Datum query,
+ StrategyNumber strategy)
{
float8 distance;
StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
- /* Bounding box distance is always inexact. */
- *recheck = true;
-
switch (strategyGroup)
{
case PointStrategyNumberGroup:
@@ -1500,6 +1487,42 @@ gist_bbox_distance(GISTENTRY *entry, Datum query,
}
Datum
+gist_box_distance(PG_FUNCTION_ARGS)
+{
+ GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
+ Datum query = PG_GETARG_DATUM(1);
+ StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
+
+ /* Oid subtype = PG_GETARG_OID(3); */
+ /* bool *recheck = (bool *) PG_GETARG_POINTER(4); */
+ float8 distance;
+
+ distance = gist_box_distance_helper(entry, query, strategy);
+
+ PG_RETURN_FLOAT8(distance);
+}
+
+/*
+ * The inexact GiST distance method for geometric types that store bounding
+ * boxes.
+ *
+ * Compute lossy distance from point to index entries. The result is inexact
+ * because index entries are bounding boxes, not the exact shapes of the
+ * indexed geometric types. We use distance from point to MBR of index entry.
+ * This is a lower bound estimate of distance from point to indexed geometric
+ * type.
+ */
+static float8
+gist_bbox_distance(GISTENTRY *entry, Datum query,
+ StrategyNumber strategy, bool *recheck)
+{
+ /* Bounding box distance is always inexact. */
+ *recheck = true;
+
+ return gist_box_distance_helper(entry, query, strategy);
+}
+
+Datum
gist_circle_distance(PG_FUNCTION_ARGS)
{
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
diff --git a/src/include/catalog/pg_amop.dat b/src/include/catalog/pg_amop.dat
index 0ab95d8..8e74f86 100644
--- a/src/include/catalog/pg_amop.dat
+++ b/src/include/catalog/pg_amop.dat
@@ -1081,6 +1081,9 @@
amopstrategy => '13', amopopr => '~(box,box)', amopmethod => 'gist' },
{ amopfamily => 'gist/box_ops', amoplefttype => 'box', amoprighttype => 'box',
amopstrategy => '14', amopopr => '@(box,box)', amopmethod => 'gist' },
+{ amopfamily => 'gist/box_ops', amoplefttype => 'box', amoprighttype => 'point',
+ amopstrategy => '15', amoppurpose => 'o', amopopr => '<->(box,point)',
+ amopmethod => 'gist', amopsortfamily => 'btree/float_ops' },
# gist point_ops
{ amopfamily => 'gist/point_ops', amoplefttype => 'point',
diff --git a/src/include/catalog/pg_amproc.dat b/src/include/catalog/pg_amproc.dat
index 020b741..5567b7e 100644
--- a/src/include/catalog/pg_amproc.dat
+++ b/src/include/catalog/pg_amproc.dat
@@ -419,6 +419,8 @@
amprocrighttype => 'box', amprocnum => '6', amproc => 'gist_box_picksplit' },
{ amprocfamily => 'gist/box_ops', amproclefttype => 'box',
amprocrighttype => 'box', amprocnum => '7', amproc => 'gist_box_same' },
+{ amprocfamily => 'gist/box_ops', amproclefttype => 'box',
+ amprocrighttype => 'box', amprocnum => '8', amproc => 'gist_box_distance' },
{ amprocfamily => 'gist/poly_ops', amproclefttype => 'polygon',
amprocrighttype => 'polygon', amprocnum => '1',
amproc => 'gist_poly_consistent' },
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 3800150..d6477a3 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -7760,6 +7760,10 @@
{ oid => '2584', descr => 'GiST support',
proname => 'gist_box_same', prorettype => 'internal',
proargtypes => 'box box internal', prosrc => 'gist_box_same' },
+{ oid => '3998', descr => 'GiST support',
+ proname => 'gist_box_distance', prorettype => 'float8',
+ proargtypes => 'internal box int2 oid internal',
+ prosrc => 'gist_box_distance' },
{ oid => '2585', descr => 'GiST support',
proname => 'gist_poly_consistent', prorettype => 'bool',
proargtypes => 'internal polygon int2 oid internal',
diff --git a/src/test/regress/expected/gist.out b/src/test/regress/expected/gist.out
index f5a2993..e8c2685 100644
--- a/src/test/regress/expected/gist.out
+++ b/src/test/regress/expected/gist.out
@@ -205,6 +205,82 @@ select b from gist_tbl where b <@ box(point(5,5), point(6,6));
(6,6),(6,6)
(21 rows)
+-- Also test an index-only knn-search
+explain (costs off)
+select b from gist_tbl where b <@ box(point(5,5), point(6,6))
+order by b <-> point(5.2, 5.91);
+ QUERY PLAN
+------------------------------------------------------
+ Index Only Scan using gist_tbl_box_index on gist_tbl
+ Index Cond: (b <@ '(6,6),(5,5)'::box)
+ Order By: (b <-> '(5.2,5.91)'::point)
+(3 rows)
+
+select b from gist_tbl where b <@ box(point(5,5), point(6,6))
+order by b <-> point(5.2, 5.91);
+ b
+-------------------------
+ (5.55,5.55),(5.55,5.55)
+ (5.6,5.6),(5.6,5.6)
+ (5.5,5.5),(5.5,5.5)
+ (5.65,5.65),(5.65,5.65)
+ (5.45,5.45),(5.45,5.45)
+ (5.7,5.7),(5.7,5.7)
+ (5.4,5.4),(5.4,5.4)
+ (5.75,5.75),(5.75,5.75)
+ (5.35,5.35),(5.35,5.35)
+ (5.8,5.8),(5.8,5.8)
+ (5.3,5.3),(5.3,5.3)
+ (5.85,5.85),(5.85,5.85)
+ (5.25,5.25),(5.25,5.25)
+ (5.9,5.9),(5.9,5.9)
+ (5.2,5.2),(5.2,5.2)
+ (5.95,5.95),(5.95,5.95)
+ (5.15,5.15),(5.15,5.15)
+ (6,6),(6,6)
+ (5.1,5.1),(5.1,5.1)
+ (5.05,5.05),(5.05,5.05)
+ (5,5),(5,5)
+(21 rows)
+
+-- Check commuted case as well
+explain (costs off)
+select b from gist_tbl where b <@ box(point(5,5), point(6,6))
+order by point(5.2, 5.91) <-> b;
+ QUERY PLAN
+------------------------------------------------------
+ Index Only Scan using gist_tbl_box_index on gist_tbl
+ Index Cond: (b <@ '(6,6),(5,5)'::box)
+ Order By: (b <-> '(5.2,5.91)'::point)
+(3 rows)
+
+select b from gist_tbl where b <@ box(point(5,5), point(6,6))
+order by point(5.2, 5.91) <-> b;
+ b
+-------------------------
+ (5.55,5.55),(5.55,5.55)
+ (5.6,5.6),(5.6,5.6)
+ (5.5,5.5),(5.5,5.5)
+ (5.65,5.65),(5.65,5.65)
+ (5.45,5.45),(5.45,5.45)
+ (5.7,5.7),(5.7,5.7)
+ (5.4,5.4),(5.4,5.4)
+ (5.75,5.75),(5.75,5.75)
+ (5.35,5.35),(5.35,5.35)
+ (5.8,5.8),(5.8,5.8)
+ (5.3,5.3),(5.3,5.3)
+ (5.85,5.85),(5.85,5.85)
+ (5.25,5.25),(5.25,5.25)
+ (5.9,5.9),(5.9,5.9)
+ (5.2,5.2),(5.2,5.2)
+ (5.95,5.95),(5.95,5.95)
+ (5.15,5.15),(5.15,5.15)
+ (6,6),(6,6)
+ (5.1,5.1),(5.1,5.1)
+ (5.05,5.05),(5.05,5.05)
+ (5,5),(5,5)
+(21 rows)
+
drop index gist_tbl_box_index;
-- Test that an index-only scan is not chosen, when the query involves the
-- circle column (the circle opclass does not support index-only scans).
diff --git a/src/test/regress/sql/gist.sql b/src/test/regress/sql/gist.sql
index bae722f..406fb83 100644
--- a/src/test/regress/sql/gist.sql
+++ b/src/test/regress/sql/gist.sql
@@ -111,6 +111,22 @@ select b from gist_tbl where b <@ box(point(5,5), point(6,6));
-- execute the same
select b from gist_tbl where b <@ box(point(5,5), point(6,6));
+-- Also test an index-only knn-search
+explain (costs off)
+select b from gist_tbl where b <@ box(point(5,5), point(6,6))
+order by b <-> point(5.2, 5.91);
+
+select b from gist_tbl where b <@ box(point(5,5), point(6,6))
+order by b <-> point(5.2, 5.91);
+
+-- Check commuted case as well
+explain (costs off)
+select b from gist_tbl where b <@ box(point(5,5), point(6,6))
+order by point(5.2, 5.91) <-> b;
+
+select b from gist_tbl where b <@ box(point(5,5), point(6,6))
+order by point(5.2, 5.91) <-> b;
+
drop index gist_tbl_box_index;
-- Test that an index-only scan is not chosen, when the query involves the
--
2.7.4
[text/x-patch] 0003-Add-box-point-distance-operator-to-SP-GiST-box_ops-v01.patch (9.4K, ../f71ba19d-d989-63b6-f04a-abf02ad9345d@postgrespro.ru/5-0003-Add-box-point-distance-operator-to-SP-GiST-box_ops-v01.patch)
download | inline diff:
From 8308cde7d015549b173bc69a1279ff519ccdf811 Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.gluhov@postgrespro.ru>
Date: Thu, 7 Mar 2019 23:49:47 +0300
Subject: [PATCH 3/3] Add operator <->(box, point) to SP-GiST box_ops
---
doc/src/sgml/spgist.sgml | 1 +
src/include/catalog/pg_amop.dat | 4 ++
src/test/regress/expected/box.out | 82 +++++++++++++++++++++++++-----
src/test/regress/expected/sanity_check.out | 2 +
src/test/regress/sql/box.sql | 70 ++++++++++++++++++++-----
5 files changed, 135 insertions(+), 24 deletions(-)
diff --git a/doc/src/sgml/spgist.sgml b/doc/src/sgml/spgist.sgml
index 126d1f6..8bc8ad7 100644
--- a/doc/src/sgml/spgist.sgml
+++ b/doc/src/sgml/spgist.sgml
@@ -139,6 +139,7 @@
<literal>|&></literal>
</entry>
<entry>
+ <literal><-></literal>
</entry>
</row>
<row>
diff --git a/src/include/catalog/pg_amop.dat b/src/include/catalog/pg_amop.dat
index 8e74f86..797223d 100644
--- a/src/include/catalog/pg_amop.dat
+++ b/src/include/catalog/pg_amop.dat
@@ -1534,6 +1534,10 @@
amopstrategy => '11', amopopr => '|>>(box,box)', amopmethod => 'spgist' },
{ amopfamily => 'spgist/box_ops', amoplefttype => 'box', amoprighttype => 'box',
amopstrategy => '12', amopopr => '|&>(box,box)', amopmethod => 'spgist' },
+{ amopfamily => 'spgist/box_ops', amoplefttype => 'box',
+ amoprighttype => 'point', amopstrategy => '15', amoppurpose => 'o',
+ amopopr => '<->(box,point)', amopmethod => 'spgist',
+ amopsortfamily => 'btree/float_ops' },
# SP-GiST poly_ops (supports polygons)
{ amopfamily => 'spgist/poly_ops', amoplefttype => 'polygon',
diff --git a/src/test/regress/expected/box.out b/src/test/regress/expected/box.out
index 998b522..4d0f169 100644
--- a/src/test/regress/expected/box.out
+++ b/src/test/regress/expected/box.out
@@ -480,23 +480,33 @@ DROP INDEX box_spgist;
--
-- Test the SP-GiST index on the larger volume of data
--
-CREATE TABLE quad_box_tbl (b box);
+CREATE TABLE quad_box_tbl (id int, b box);
INSERT INTO quad_box_tbl
- SELECT box(point(x * 10, y * 10), point(x * 10 + 5, y * 10 + 5))
- FROM generate_series(1, 100) x,
- generate_series(1, 100) y;
+ SELECT (x - 1) * 100 + y, box(point(x * 10, y * 10), point(x * 10 + 5, y * 10 + 5))
+ FROM generate_series(1, 100) x,
+ generate_series(1, 100) y;
-- insert repeating data to test allTheSame
INSERT INTO quad_box_tbl
- SELECT '((200, 300),(210, 310))'
- FROM generate_series(1, 1000);
+ SELECT i, '((200, 300),(210, 310))'
+ FROM generate_series(10001, 11000) AS i;
INSERT INTO quad_box_tbl
- VALUES
- (NULL),
- (NULL),
- ('((-infinity,-infinity),(infinity,infinity))'),
- ('((-infinity,100),(-infinity,500))'),
- ('((-infinity,-infinity),(700,infinity))');
+VALUES
+ (11001, NULL),
+ (11002, NULL),
+ (11003, '((-infinity,-infinity),(infinity,infinity))'),
+ (11004, '((-infinity,100),(-infinity,500))'),
+ (11005, '((-infinity,-infinity),(700,infinity))');
CREATE INDEX quad_box_tbl_idx ON quad_box_tbl USING spgist(b);
+-- get reference results for ORDER BY distance from seq scan
+SET enable_seqscan = ON;
+SET enable_indexscan = OFF;
+SET enable_bitmapscan = OFF;
+CREATE TABLE quad_box_tbl_ord_seq1 AS
+SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id
+FROM quad_box_tbl;
+CREATE TABLE quad_box_tbl_ord_seq2 AS
+SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id
+FROM quad_box_tbl WHERE b <@ box '((200,300),(500,600))';
SET enable_seqscan = OFF;
SET enable_indexscan = ON;
SET enable_bitmapscan = ON;
@@ -578,6 +588,54 @@ SELECT count(*) FROM quad_box_tbl WHERE b ~= box '((200,300),(205,305))';
1
(1 row)
+-- test ORDER BY distance
+SET enable_indexscan = ON;
+SET enable_bitmapscan = OFF;
+EXPLAIN (COSTS OFF)
+SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id
+FROM quad_box_tbl;
+ QUERY PLAN
+---------------------------------------------------------
+ WindowAgg
+ -> Index Scan using quad_box_tbl_idx on quad_box_tbl
+ Order By: (b <-> '(123,456)'::point)
+(3 rows)
+
+CREATE TEMP TABLE quad_box_tbl_ord_idx1 AS
+SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id
+FROM quad_box_tbl;
+SELECT *
+FROM quad_box_tbl_ord_seq1 seq FULL JOIN quad_box_tbl_ord_idx1 idx
+ ON seq.n = idx.n AND seq.id = idx.id AND
+ (seq.dist = idx.dist OR seq.dist IS NULL AND idx.dist IS NULL)
+WHERE seq.id IS NULL OR idx.id IS NULL;
+ n | dist | id | n | dist | id
+---+------+----+---+------+----
+(0 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id
+FROM quad_box_tbl WHERE b <@ box '((200,300),(500,600))';
+ QUERY PLAN
+---------------------------------------------------------
+ WindowAgg
+ -> Index Scan using quad_box_tbl_idx on quad_box_tbl
+ Index Cond: (b <@ '(500,600),(200,300)'::box)
+ Order By: (b <-> '(123,456)'::point)
+(4 rows)
+
+CREATE TEMP TABLE quad_box_tbl_ord_idx2 AS
+SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id
+FROM quad_box_tbl WHERE b <@ box '((200,300),(500,600))';
+SELECT *
+FROM quad_box_tbl_ord_seq2 seq FULL JOIN quad_box_tbl_ord_idx2 idx
+ ON seq.n = idx.n AND seq.id = idx.id AND
+ (seq.dist = idx.dist OR seq.dist IS NULL AND idx.dist IS NULL)
+WHERE seq.id IS NULL OR idx.id IS NULL;
+ n | dist | id | n | dist | id
+---+------+----+---+------+----
+(0 rows)
+
RESET enable_seqscan;
RESET enable_indexscan;
RESET enable_bitmapscan;
diff --git a/src/test/regress/expected/sanity_check.out b/src/test/regress/expected/sanity_check.out
index aaaa488..850de0c 100644
--- a/src/test/regress/expected/sanity_check.out
+++ b/src/test/regress/expected/sanity_check.out
@@ -167,6 +167,8 @@ pg_user_mapping|t
point_tbl|t
polygon_tbl|t
quad_box_tbl|t
+quad_box_tbl_ord_seq1|f
+quad_box_tbl_ord_seq2|f
quad_point_tbl|t
quad_poly_tbl|t
quad_poly_tbl_ord_seq1|f
diff --git a/src/test/regress/sql/box.sql b/src/test/regress/sql/box.sql
index 6710fc9..cd3e002 100644
--- a/src/test/regress/sql/box.sql
+++ b/src/test/regress/sql/box.sql
@@ -192,28 +192,41 @@ DROP INDEX box_spgist;
--
-- Test the SP-GiST index on the larger volume of data
--
-CREATE TABLE quad_box_tbl (b box);
+CREATE TABLE quad_box_tbl (id int, b box);
INSERT INTO quad_box_tbl
- SELECT box(point(x * 10, y * 10), point(x * 10 + 5, y * 10 + 5))
- FROM generate_series(1, 100) x,
- generate_series(1, 100) y;
+ SELECT (x - 1) * 100 + y, box(point(x * 10, y * 10), point(x * 10 + 5, y * 10 + 5))
+ FROM generate_series(1, 100) x,
+ generate_series(1, 100) y;
-- insert repeating data to test allTheSame
INSERT INTO quad_box_tbl
- SELECT '((200, 300),(210, 310))'
- FROM generate_series(1, 1000);
+ SELECT i, '((200, 300),(210, 310))'
+ FROM generate_series(10001, 11000) AS i;
INSERT INTO quad_box_tbl
- VALUES
- (NULL),
- (NULL),
- ('((-infinity,-infinity),(infinity,infinity))'),
- ('((-infinity,100),(-infinity,500))'),
- ('((-infinity,-infinity),(700,infinity))');
+VALUES
+ (11001, NULL),
+ (11002, NULL),
+ (11003, '((-infinity,-infinity),(infinity,infinity))'),
+ (11004, '((-infinity,100),(-infinity,500))'),
+ (11005, '((-infinity,-infinity),(700,infinity))');
CREATE INDEX quad_box_tbl_idx ON quad_box_tbl USING spgist(b);
+-- get reference results for ORDER BY distance from seq scan
+SET enable_seqscan = ON;
+SET enable_indexscan = OFF;
+SET enable_bitmapscan = OFF;
+
+CREATE TABLE quad_box_tbl_ord_seq1 AS
+SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id
+FROM quad_box_tbl;
+
+CREATE TABLE quad_box_tbl_ord_seq2 AS
+SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id
+FROM quad_box_tbl WHERE b <@ box '((200,300),(500,600))';
+
SET enable_seqscan = OFF;
SET enable_indexscan = ON;
SET enable_bitmapscan = ON;
@@ -232,6 +245,39 @@ SELECT count(*) FROM quad_box_tbl WHERE b @> box '((201,301),(202,303))';
SELECT count(*) FROM quad_box_tbl WHERE b <@ box '((100,200),(300,500))';
SELECT count(*) FROM quad_box_tbl WHERE b ~= box '((200,300),(205,305))';
+-- test ORDER BY distance
+SET enable_indexscan = ON;
+SET enable_bitmapscan = OFF;
+
+EXPLAIN (COSTS OFF)
+SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id
+FROM quad_box_tbl;
+
+CREATE TEMP TABLE quad_box_tbl_ord_idx1 AS
+SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id
+FROM quad_box_tbl;
+
+SELECT *
+FROM quad_box_tbl_ord_seq1 seq FULL JOIN quad_box_tbl_ord_idx1 idx
+ ON seq.n = idx.n AND seq.id = idx.id AND
+ (seq.dist = idx.dist OR seq.dist IS NULL AND idx.dist IS NULL)
+WHERE seq.id IS NULL OR idx.id IS NULL;
+
+
+EXPLAIN (COSTS OFF)
+SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id
+FROM quad_box_tbl WHERE b <@ box '((200,300),(500,600))';
+
+CREATE TEMP TABLE quad_box_tbl_ord_idx2 AS
+SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id
+FROM quad_box_tbl WHERE b <@ box '((200,300),(500,600))';
+
+SELECT *
+FROM quad_box_tbl_ord_seq2 seq FULL JOIN quad_box_tbl_ord_idx2 idx
+ ON seq.n = idx.n AND seq.id = idx.id AND
+ (seq.dist = idx.dist OR seq.dist IS NULL AND idx.dist IS NULL)
+WHERE seq.id IS NULL OR idx.id IS NULL;
+
RESET enable_seqscan;
RESET enable_indexscan;
RESET enable_bitmapscan;
--
2.7.4
view thread (10+ messages) latest in thread
Message-ID: <f71ba19d-d989-63b6-f04a-abf02ad9345d@postgrespro.ru>
Permalink: ../f71ba19d-d989-63b6-f04a-abf02ad9345d@postgrespro.ru/
Also on: postgresql.org/message-id/f71ba19d-d989-63b6-f04a-abf02ad9345d@postgrespro.ru
copy link · copy postgr.es · copy git am
reply Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: n.gluhov@postgrespro.ru
Subject: Re: Add missing operator <->(box, point)
In-Reply-To: <f71ba19d-d989-63b6-f04a-abf02ad9345d@postgrespro.ru>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox