Hi,
This patch series is to add support for spgist quadtree @<(point,circle)
operator. The first two patches are to refactor existing code before
implemention the new feature. The third commit is the actual implementation
provided with a set of simple unit tests.
Changes since v2:
- fix coding style
- add comment to spg_quad_inner_consistent_circle_helper()
- rework spg_quad_inner_consistent_circle_helper() using HYPOT() to make the
search consistent with filter scan
Matwey V. Kornilov (3):
Introduce helper variable in spgquadtreeproc.c
Introduce spg_quad_inner_consistent_box_helper() in spgquadtreeproc.c
Add initial support for spgist quadtree @<(point,circle) operator
src/backend/access/spgist/spgquadtreeproc.c | 147 +++++++++++++++-------
src/include/catalog/pg_amop.dat | 3 +
src/test/regress/expected/create_index_spgist.out | 96 ++++++++++++++
src/test/regress/sql/create_index_spgist.sql | 32 +++++
4 files changed, 234 insertions(+), 44 deletions(-)
--
2.13.7
--
With best regards,
Matwey V. Kornilov
From 912a5d76107fc2597b951d2e2f3c22400a6c0cf6 Mon Sep 17 00:00:00 2001
From: "Matwey V. Kornilov" <matwey.korni...@gmail.com>
Date: Fri, 1 Feb 2019 12:14:18 +0300
Subject: [PATCH v2 2/3] Introduce spg_quad_inner_consistent_box_helper() in
spgquadtreeproc.c
This helper function makes spg_quad_inner_consistent() more readable when
changes from the next commit is introduced.
Signed-off-by: Matwey V. Kornilov <matwey.korni...@gmail.com>
---
src/backend/access/spgist/spgquadtreeproc.c | 64 ++++++++++++++---------------
1 file changed, 32 insertions(+), 32 deletions(-)
diff --git a/src/backend/access/spgist/spgquadtreeproc.c b/src/backend/access/spgist/spgquadtreeproc.c
index f2e980b758..41e7fe5c81 100644
--- a/src/backend/access/spgist/spgquadtreeproc.c
+++ b/src/backend/access/spgist/spgquadtreeproc.c
@@ -112,6 +112,37 @@ getQuadrantArea(BOX *bbox, Point *centroid, int quadrant)
return result;
}
+static int
+spg_quad_inner_consistent_box_helper(ScanKey sk, Point *centroid)
+{
+ /*
+ * For this operator, the query is a box not a point. We
+ * cheat to the extent of assuming that DatumGetPointP won't
+ * do anything that would be bad for a pointer-to-box.
+ */
+ BOX *boxQuery = DatumGetBoxP(sk->sk_argument);
+ Point p;
+ int r = 0;
+
+ if (DatumGetBool(DirectFunctionCall2(box_contain_pt, PointerGetDatum(boxQuery), PointerGetDatum(centroid))))
+ {
+ /* centroid is in box, so all quadrants are OK */
+ return (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
+ }
+
+ /* identify quadrant(s) containing all corners of box */
+ p = boxQuery->low;
+ r |= 1 << getQuadrant(centroid, &p);
+ p.y = boxQuery->high.y;
+ r |= 1 << getQuadrant(centroid, &p);
+ p = boxQuery->high;
+ r |= 1 << getQuadrant(centroid, &p);
+ p.x = boxQuery->low.x;
+ r |= 1 << getQuadrant(centroid, &p);
+
+ return r;
+}
+
Datum
spg_quad_choose(PG_FUNCTION_ARGS)
{
@@ -302,7 +333,6 @@ spg_quad_inner_consistent(PG_FUNCTION_ARGS)
{
const ScanKey sk = in->scankeys + i;
Point *query = DatumGetPointP(sk->sk_argument);
- BOX *boxQuery;
switch (sk->sk_strategy)
{
@@ -326,37 +356,7 @@ spg_quad_inner_consistent(PG_FUNCTION_ARGS)
which &= (1 << 1) | (1 << 4);
break;
case RTContainedByStrategyNumber:
-
- /*
- * For this operator, the query is a box not a point. We
- * cheat to the extent of assuming that DatumGetPointP won't
- * do anything that would be bad for a pointer-to-box.
- */
- boxQuery = DatumGetBoxP(sk->sk_argument);
-
- if (DatumGetBool(DirectFunctionCall2(box_contain_pt,
- PointerGetDatum(boxQuery),
- PointerGetDatum(centroid))))
- {
- /* centroid is in box, so all quadrants are OK */
- }
- else
- {
- /* identify quadrant(s) containing all corners of box */
- Point p;
- int r = 0;
-
- p = boxQuery->low;
- r |= 1 << getQuadrant(centroid, &p);
- p.y = boxQuery->high.y;
- r |= 1 << getQuadrant(centroid, &p);
- p = boxQuery->high;
- r |= 1 << getQuadrant(centroid, &p);
- p.x = boxQuery->low.x;
- r |= 1 << getQuadrant(centroid, &p);
-
- which &= r;
- }
+ which &= spg_quad_inner_consistent_box_helper(sk, centroid);
break;
default:
elog(ERROR, "unrecognized strategy number: %d", sk->sk_strategy);
--
2.13.7
From 60bd01b8752def70685cfb67fe47bf0ae9be3f02 Mon Sep 17 00:00:00 2001
From: "Matwey V. Kornilov" <matwey.korni...@gmail.com>
Date: Thu, 31 Jan 2019 13:20:40 +0300
Subject: [PATCH v2 3/3] Add initial support for spgist quadtree
@<(point,circle) operator
Signed-off-by: Matwey V. Kornilov <matwey.korni...@gmail.com>
---
src/backend/access/spgist/spgquadtreeproc.c | 73 +++++++++++++++--
src/include/catalog/pg_amop.dat | 3 +
src/test/regress/expected/create_index_spgist.out | 96 +++++++++++++++++++++++
src/test/regress/sql/create_index_spgist.sql | 32 ++++++++
4 files changed, 197 insertions(+), 7 deletions(-)
diff --git a/src/backend/access/spgist/spgquadtreeproc.c b/src/backend/access/spgist/spgquadtreeproc.c
index 41e7fe5c81..4dd2246a92 100644
--- a/src/backend/access/spgist/spgquadtreeproc.c
+++ b/src/backend/access/spgist/spgquadtreeproc.c
@@ -143,6 +143,44 @@ spg_quad_inner_consistent_box_helper(ScanKey sk, Point *centroid)
return r;
}
+static int
+spg_quad_inner_consistent_circle_helper(ScanKey sk, Point *centroid)
+{
+ /*
+ * Evaluate distances between the query center point and the quadrants.
+ * The distance between a set and a point is the minimal possible distance
+ * between any set point and the point. There are three possible cases: the
+ * point belongs to the quandrand, the point projection is on the quadrant
+ * edge, the point projections is on the quadrant vertex.
+ */
+ CIRCLE *circleQuery = DatumGetCircleP(sk->sk_argument);
+ int r = 0;
+
+ const Point cp = {
+ .x = float8_mi(centroid->x, circleQuery->center.x),
+ .y = float8_mi(centroid->y, circleQuery->center.y)
+ };
+
+ const float8 x_p0 = (0. > cp.x ? 0. : cp.x);
+ const float8 y_p0 = (0. > cp.y ? 0. : cp.y);
+ const float8 x_n0 = (0. < cp.x ? 0. : cp.x);
+ const float8 y_n0 = (0. < cp.y ? 0. : cp.y);
+
+ const float8 d[4] = {
+ HYPOT(x_p0, y_p0),
+ HYPOT(x_p0, y_n0),
+ HYPOT(x_n0, y_n0),
+ HYPOT(x_n0, y_p0)
+ };
+
+ for (int i = 0; i < 4; i++) {
+ if (d[i] <= circleQuery->radius)
+ r |= (1 << (i + 1));
+ }
+
+ return r;
+}
+
Datum
spg_quad_choose(PG_FUNCTION_ARGS)
{
@@ -356,7 +394,18 @@ spg_quad_inner_consistent(PG_FUNCTION_ARGS)
which &= (1 << 1) | (1 << 4);
break;
case RTContainedByStrategyNumber:
- which &= spg_quad_inner_consistent_box_helper(sk, centroid);
+
+ switch (sk->sk_subtype) {
+ case BOXOID:
+ which &= spg_quad_inner_consistent_box_helper(sk, centroid);
+ break;
+ case CIRCLEOID:
+ which &= spg_quad_inner_consistent_circle_helper(sk, centroid);
+ break;
+ default:
+ elog(ERROR, "unrecognized right type OID: %d", sk->sk_subtype);
+ break;
+ }
break;
default:
elog(ERROR, "unrecognized strategy number: %d", sk->sk_strategy);
@@ -443,12 +492,22 @@ spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
break;
case RTContainedByStrategyNumber:
- /*
- * For this operator, the query is a box not a point. We
- * cheat to the extent of assuming that DatumGetPointP won't
- * do anything that would be bad for a pointer-to-box.
- */
- res = SPTEST(box_contain_pt, query, datum);
+ switch (sk->sk_subtype) {
+ case BOXOID:
+ /*
+ * For this operator, the query is a box not a point. We
+ * cheat to the extent of assuming that DatumGetPointP won't
+ * do anything that would be bad for a pointer-to-box.
+ */
+ res = SPTEST(box_contain_pt, query, datum);
+ break;
+ case CIRCLEOID:
+ res = SPTEST(circle_contain_pt, query, datum);
+ break;
+ default:
+ elog(ERROR, "unrecognized right type OID: %d", sk->sk_subtype);
+ break;
+ }
break;
default:
elog(ERROR, "unrecognized strategy number: %d", sk->sk_strategy);
diff --git a/src/include/catalog/pg_amop.dat b/src/include/catalog/pg_amop.dat
index cf63eb7d54..6ea7e21aa1 100644
--- a/src/include/catalog/pg_amop.dat
+++ b/src/include/catalog/pg_amop.dat
@@ -1373,6 +1373,9 @@
amoprighttype => 'box', amopstrategy => '8', amopopr => '<@(point,box)',
amopmethod => 'spgist' },
{ amopfamily => 'spgist/quad_point_ops', amoplefttype => 'point',
+ amoprighttype => 'circle', amopstrategy => '8', amopopr => '<@(point,circle)',
+ amopmethod => 'spgist' },
+{ amopfamily => 'spgist/quad_point_ops', amoplefttype => 'point',
amoprighttype => 'point', amopstrategy => '15', amoppurpose => 'o',
amopopr => '<->(point,point)', amopmethod => 'spgist',
amopsortfamily => 'btree/float_ops' },
diff --git a/src/test/regress/expected/create_index_spgist.out b/src/test/regress/expected/create_index_spgist.out
index 81b4a67c39..191e3088af 100644
--- a/src/test/regress/expected/create_index_spgist.out
+++ b/src/test/regress/expected/create_index_spgist.out
@@ -50,6 +50,102 @@ SELECT count(*) FROM quad_point_tbl WHERE box '(200,200,1000,1000)' @> p;
1057
(1 row)
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(332,399),1.41>';
+ count
+-------
+ 0
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(332,399),1.42>';
+ count
+-------
+ 1000
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(332,401),1.41>';
+ count
+-------
+ 0
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(332,401),1.42>';
+ count
+-------
+ 1000
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(334,399),1.41>';
+ count
+-------
+ 0
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(334,399),1.42>';
+ count
+-------
+ 1000
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(334,401),1.41>';
+ count
+-------
+ 0
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(334,401),1.42>';
+ count
+-------
+ 1000
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(333,399),0.99>';
+ count
+-------
+ 0
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(333,399),1.01>';
+ count
+-------
+ 1000
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(333,401),0.99>';
+ count
+-------
+ 0
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(333,401),1.01>';
+ count
+-------
+ 1000
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(332,400),0.99>';
+ count
+-------
+ 0
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(332,400),1.01>';
+ count
+-------
+ 1000
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(334,400),0.99>';
+ count
+-------
+ 0
+(1 row)
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(334,400),1.01>';
+ count
+-------
+ 1000
+(1 row)
+
SELECT count(*) FROM quad_point_tbl WHERE p << '(5000, 4000)';
count
-------
diff --git a/src/test/regress/sql/create_index_spgist.sql b/src/test/regress/sql/create_index_spgist.sql
index 8e6c453307..25881387c3 100644
--- a/src/test/regress/sql/create_index_spgist.sql
+++ b/src/test/regress/sql/create_index_spgist.sql
@@ -42,6 +42,38 @@ SELECT count(*) FROM quad_point_tbl WHERE p <@ box '(200,200,1000,1000)';
SELECT count(*) FROM quad_point_tbl WHERE box '(200,200,1000,1000)' @> p;
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(332,399),1.41>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(332,399),1.42>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(332,401),1.41>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(332,401),1.42>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(334,399),1.41>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(334,399),1.42>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(334,401),1.41>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(334,401),1.42>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(333,399),0.99>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(333,399),1.01>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(333,401),0.99>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(333,401),1.01>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(332,400),0.99>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(332,400),1.01>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(334,400),0.99>';
+
+SELECT count(*) FROM quad_point_tbl WHERE p <@ circle '<(334,400),1.01>';
+
SELECT count(*) FROM quad_point_tbl WHERE p << '(5000, 4000)';
SELECT count(*) FROM quad_point_tbl WHERE p >> '(5000, 4000)';
--
2.13.7
From 971657194b7c9d2e797823ea3ed03c42d6d04a7a Mon Sep 17 00:00:00 2001
From: "Matwey V. Kornilov" <matwey.korni...@gmail.com>
Date: Thu, 31 Jan 2019 12:56:48 +0300
Subject: [PATCH v2 1/3] Introduce helper variable in spgquadtreeproc.c
Use shorter variable name instead of repeating in->scankeys[i] in
spg_quad_leaf_consistent() and spg_quad_inner_consistent().
Signed-off-by: Matwey V. Kornilov <matwey.korni...@gmail.com>
---
src/backend/access/spgist/spgquadtreeproc.c | 18 +++++++++---------
1 file changed, 9 insertions(+), 9 deletions(-)
diff --git a/src/backend/access/spgist/spgquadtreeproc.c b/src/backend/access/spgist/spgquadtreeproc.c
index e50108e1ca..f2e980b758 100644
--- a/src/backend/access/spgist/spgquadtreeproc.c
+++ b/src/backend/access/spgist/spgquadtreeproc.c
@@ -300,10 +300,11 @@ spg_quad_inner_consistent(PG_FUNCTION_ARGS)
for (i = 0; i < in->nkeys; i++)
{
- Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
+ const ScanKey sk = in->scankeys + i;
+ Point *query = DatumGetPointP(sk->sk_argument);
BOX *boxQuery;
- switch (in->scankeys[i].sk_strategy)
+ switch (sk->sk_strategy)
{
case RTLeftStrategyNumber:
if (SPTEST(point_right, centroid, query))
@@ -331,7 +332,7 @@ spg_quad_inner_consistent(PG_FUNCTION_ARGS)
* cheat to the extent of assuming that DatumGetPointP won't
* do anything that would be bad for a pointer-to-box.
*/
- boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
+ boxQuery = DatumGetBoxP(sk->sk_argument);
if (DatumGetBool(DirectFunctionCall2(box_contain_pt,
PointerGetDatum(boxQuery),
@@ -358,8 +359,7 @@ spg_quad_inner_consistent(PG_FUNCTION_ARGS)
}
break;
default:
- elog(ERROR, "unrecognized strategy number: %d",
- in->scankeys[i].sk_strategy);
+ elog(ERROR, "unrecognized strategy number: %d", sk->sk_strategy);
break;
}
@@ -421,9 +421,10 @@ spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
res = true;
for (i = 0; i < in->nkeys; i++)
{
- Point *query = DatumGetPointP(in->scankeys[i].sk_argument);
+ const ScanKey sk = in->scankeys + i;
+ Point *query = DatumGetPointP(sk->sk_argument);
- switch (in->scankeys[i].sk_strategy)
+ switch (sk->sk_strategy)
{
case RTLeftStrategyNumber:
res = SPTEST(point_left, datum, query);
@@ -450,8 +451,7 @@ spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
res = SPTEST(box_contain_pt, query, datum);
break;
default:
- elog(ERROR, "unrecognized strategy number: %d",
- in->scankeys[i].sk_strategy);
+ elog(ERROR, "unrecognized strategy number: %d", sk->sk_strategy);
break;
}
--
2.13.7
