pg.ddx.io pgsql-hackers@postgresql.org mailing list archive help / color / mirror / Atom feed From: Nikita Glukhov <n.gluhov@postgrespro.ru>
To: Tom Lane <tgl@sss.pgh.pa.us>
To: Fabien COELHO <coelho@cri.ensmp.fr>
Cc: PostgreSQL Hackers <pgsql-hackers@postgresql.org>
Subject: Re: Add missing operator <->(box, point)
Date: Tue, 2 Jul 2019 21:17:52 +0300
Message-ID: <2fe442bd-4e0c-56ba-eb62-f1b51f6b17f3@postgrespro.ru> (raw )
In-Reply-To: <6935.1562040096@sss.pgh.pa.us >
References: <f71ba19d-d989-63b6-f04a-abf02ad9345d@postgrespro.ru >
<alpine.DEB.2.21.1904201526100.29102@lancre >
<6935.1562040096@sss.pgh.pa.us >
Attached 2nd version of the patches.
On 20.04.2019 16:41, Fabien COELHO wrote:
> About the test, I'd suggest to name the result columns, eg "pt to box
> dist" and "box to pt dist", otherwise why all is repeated is unclear.
Fixed.
On 02.07.2019 7:01, Tom Lane wrote:
> [ warning, drive-by comment ahead ]
>
> Fabien COELHO <coelho@cri.ensmp.fr> writes:
>> I notice that other distance tests do not test for commutativity. Are they
>> also not implemented, or just not tested? If not implemented, I'd suggest
>> to add them in the same batch.
> Yeah ... just looking at operators named <->, I see
>
> regression=# select oid, oid::regoperator, oprcom, oprcode from pg_operator where oprname = '<->';
> oid | oid | oprcom | oprcode
> ------+----------------------+--------+---------------------------
> 517 | <->(point,point) | 517 | point_distance
> 613 | <->(point,line) | 0 | dist_pl
> 614 | <->(point,lseg) | 0 | dist_ps
> 615 | <->(point,box) | 0 | dist_pb
> 616 | <->(lseg,line) | 0 | dist_sl
> 617 | <->(lseg,box) | 0 | dist_sb
> 618 | <->(point,path) | 0 | dist_ppath
> 706 | <->(box,box) | 706 | box_distance
> 707 | <->(path,path) | 707 | path_distance
> 708 | <->(line,line) | 708 | line_distance
> 709 | <->(lseg,lseg) | 709 | lseg_distance
> 712 | <->(polygon,polygon) | 712 | poly_distance
> 1520 | <->(circle,circle) | 1520 | circle_distance
> 1522 | <->(point,circle) | 3291 | dist_pc
> 3291 | <->(circle,point) | 1522 | dist_cpoint
> 3276 | <->(point,polygon) | 3289 | dist_ppoly
> 3289 | <->(polygon,point) | 3276 | dist_polyp
> 1523 | <->(circle,polygon) | 0 | dist_cpoly
> 1524 | <->(line,box) | 0 | dist_lb
> 5005 | <->(tsquery,tsquery) | 0 | pg_catalog.tsquery_phrase
> (20 rows)
>
> It's not clear to me why to be particularly more excited about
> <->(box, point) than about the other missing cases here.
>
> regards, tom lane
The original goal was to add support of ordering by distance to point to
all geometric opclasses. As you can see, GiST and SP-GiST box_ops has no
distance operator while more complex circle_ops and poly_ops have it:
SELECT
amname,
opcname,
amopopr::regoperator AS dist_opr
FROM
pg_opclass LEFT JOIN
pg_amop ON amopfamily = opcfamily AND amoppurpose = 'o',
pg_am,
pg_type
WHERE
opcmethod = pg_am.oid AND
opcintype = pg_type.oid AND
typcategory = 'G'
ORDER BY 1, 2;
amname | opcname | dist_opr
--------+-------------------+--------------------
brin | box_inclusion_ops |
gist | box_ops |
gist | circle_ops | <->(circle,point)
gist | point_ops | <->(point,point)
gist | poly_ops | <->(polygon,point)
spgist | box_ops |
spgist | kd_point_ops | <->(point,point)
spgist | poly_ops | <->(polygon,point)
spgist | quad_point_ops | <->(point,point)
(9 rows)
We could use commuted "const <-> var" operators for kNN searches, but the
current implementation requires the existence of "var <-> const" operators, and
order-by-op clauses are rebuilt using them (see match_clause_to_ordering_op()
at /src/backend/optimizer/path/indxpath.c).
--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Attachments:
[text/x-patch] 0001-Add-operator-box-point-v02.patch (10.3K, ../2fe442bd-4e0c-56ba-eb62-f1b51f6b17f3@postgrespro.ru/3-0001-Add-operator-box-point-v02.patch)
download | inline diff:
From cff9fbdcd9d3633a28665c0636e6d3a5a0e8512b 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 373784f..d8ecfe3 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 bacafa5..ae5ed1e 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 8733524..54327bf 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -1065,6 +1065,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..6be3a39 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 AS pt_box_dist, b.f1 <-> p.f1 AS box_pt_dist FROM POINT_TBL p, BOX_TBL b;
+ f1 | f1 | pt_box_dist | box_pt_dist
+-------------------+---------------------+--------------------+--------------------
+ (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..8fd02cf 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 AS pt_box_dist, b.f1 <-> p.f1 AS box_pt_dist 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-operator-box-point-to-GiST-box_ops-v02.patch (9.0K, ../2fe442bd-4e0c-56ba-eb62-f1b51f6b17f3@postgrespro.ru/4-0002-Add-operator-box-point-to-GiST-box_ops-v02.patch)
download | inline diff:
From 211dfae5134287dcc5b81cfd23c2a9a3e31c329a 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 1826b51..89bd656 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 cf63eb7..ebc38ae 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 54327bf..d15f94a 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -7816,6 +7816,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 0a43449..2234876 100644
--- a/src/test/regress/expected/gist.out
+++ b/src/test/regress/expected/gist.out
@@ -203,6 +203,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 657b195..b9d398e 100644
--- a/src/test/regress/sql/gist.sql
+++ b/src/test/regress/sql/gist.sql
@@ -109,6 +109,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-operator-box-point-to-SP-GiST-box_ops-v02.patch (9.4K, ../2fe442bd-4e0c-56ba-eb62-f1b51f6b17f3@postgrespro.ru/5-0003-Add-operator-box-point-to-SP-GiST-box_ops-v02.patch)
download | inline diff:
From 6fc26b5c232397722b685f28b8bba8acbb9046a8 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 7cf9d0e..9070914 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 ebc38ae..232557e 100644
--- a/src/include/catalog/pg_amop.dat
+++ b/src/include/catalog/pg_amop.dat
@@ -1546,6 +1546,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 8ff0da1..d6e75ff 100644
--- a/src/test/regress/expected/sanity_check.out
+++ b/src/test/regress/expected/sanity_check.out
@@ -165,6 +165,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
radix_text_tbl|t
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: <2fe442bd-4e0c-56ba-eb62-f1b51f6b17f3@postgrespro.ru>
Permalink: ../2fe442bd-4e0c-56ba-eb62-f1b51f6b17f3@postgrespro.ru/
Also on: postgresql.org/message-id/2fe442bd-4e0c-56ba-eb62-f1b51f6b17f3@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, tgl@sss.pgh.pa.us, coelho@cri.ensmp.fr
Subject: Re: Add missing operator <->(box, point)
In-Reply-To: <2fe442bd-4e0c-56ba-eb62-f1b51f6b17f3@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