Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hiNNO-0001Rt-8Y for pgsql-hackers@arkaria.postgresql.org; Tue, 02 Jul 2019 18:19:35 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1hiNNM-000492-WB for pgsql-hackers@arkaria.postgresql.org; Tue, 02 Jul 2019 18:19:33 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hiNNM-00048v-7H for pgsql-hackers@lists.postgresql.org; Tue, 02 Jul 2019 18:19:32 +0000 Received: from cyclops.postgrespro.ru ([93.174.131.138] helo=mail.postgrespro.ru) by makus.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1hiNNH-0002zT-HX for pgsql-hackers@postgresql.org; Tue, 02 Jul 2019 18:19:30 +0000 Received: from localhost (localhost [127.0.0.1]) by mail.postgrespro.ru (Postfix) with ESMTP id CBDF421C3FD9; Tue, 2 Jul 2019 21:19:24 +0300 (MSK) X-Virus-Scanned: Debian amavisd-new at postgrespro.ru X-Spam-Flag: NO X-Spam-Score: 0 X-Spam-Level: X-Spam-Status: No, score=x tagged_above=-99 required=4 WHITELISTED tests=[] autolearn=unavailable Received: from [10.100.236.29] (unknown [195.82.154.27]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) by mail.postgrespro.ru (Postfix) with ESMTPSA id 7783321C3FD4; Tue, 2 Jul 2019 21:19:24 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mail; t=1562091564; bh=zBeV0RvGIdsSWxd7xzWVjVbB4Z8RLMNaSjD2upj2GUY=; h=Subject:To:Cc:References:From:Date:In-Reply-To; b=V9/fPDJ1mu37cxdEVevrr7XnaoKd4NO9zW3i22u5pZhDB5Tu4W6TACmis9nKqGFKN uevFjQFi870b7GpkwtxNfQiaSvmJKLM8Ti1sCZMhHjYk+TXyHoM3qLLlk02WqqpGNG r1ORe9jF1dU8UiUj1IsllB8A9yaP3TzQINcBSAIw= Subject: Re: Add missing operator <->(box, point) To: Tom Lane , Fabien COELHO Cc: PostgreSQL Hackers References: <6935.1562040096@sss.pgh.pa.us> From: Nikita Glukhov Organization: Postgres Professional Message-ID: <2fe442bd-4e0c-56ba-eb62-f1b51f6b17f3@postgrespro.ru> Date: Tue, 2 Jul 2019 21:17:52 +0300 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.7.1 MIME-Version: 1.0 In-Reply-To: <6935.1562040096@sss.pgh.pa.us> Content-Type: multipart/mixed; boundary="------------07EE9595454874974EAD75E7" Content-Language: en-US List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk This is a multi-part message in MIME format. --------------07EE9595454874974EAD75E7 Content-Type: multipart/alternative; boundary="------------35F0525F74850DD1183EA3D2" --------------35F0525F74850DD1183EA3D2 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit 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 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 --------------35F0525F74850DD1183EA3D2 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 7bit 
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
--------------35F0525F74850DD1183EA3D2-- --------------07EE9595454874974EAD75E7 Content-Type: text/x-patch; name="0001-Add-operator-box-point-v02.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0001-Add-operator-box-point-v02.patch" From cff9fbdcd9d3633a28665c0636e6d3a5a0e8512b Mon Sep 17 00:00:00 2001 From: Nikita Glukhov 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 --------------07EE9595454874974EAD75E7 Content-Type: text/x-patch; name="0002-Add-operator-box-point-to-GiST-box_ops-v02.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0002-Add-operator-box-point-to-GiST-box_ops-v02.patch" From 211dfae5134287dcc5b81cfd23c2a9a3e31c329a Mon Sep 17 00:00:00 2001 From: Nikita Glukhov 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 @@ ~= + <-> 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 --------------07EE9595454874974EAD75E7 Content-Type: text/x-patch; name="0003-Add-operator-box-point-to-SP-GiST-box_ops-v02.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0003-Add-operator-box-point-to-SP-GiST-box_ops-v02.patch" From 6fc26b5c232397722b685f28b8bba8acbb9046a8 Mon Sep 17 00:00:00 2001 From: Nikita Glukhov 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 @@ |&> + <-> 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 --------------07EE9595454874974EAD75E7--