diff --git a/doc/src/sgml/spgist.sgml b/doc/src/sgml/spgist.sgml
index b0d1cb3..491e417 100644
--- a/doc/src/sgml/spgist.sgml
+++ b/doc/src/sgml/spgist.sgml
@@ -142,6 +142,48 @@
+ circle_ops
+ circle
+
+ <<
+ &<
+ &&
+ &>
+ >>
+ ~=
+ @>
+ <@
+ &<|
+ <<|
+ |>>
+ |&>
+
+
+ <->
+
+
+
+ poly_ops
+ polygon
+
+ <<
+ &<
+ &&
+ &>
+ >>
+ ~=
+ @>
+ <@
+ &<|
+ <<|
+ |>>
+ |&>
+
+
+ <->
+
+
+
text_ops
text
diff --git a/src/backend/utils/adt/geo_spgist.c b/src/backend/utils/adt/geo_spgist.c
index c95ec1c..bd0284f 100644
--- a/src/backend/utils/adt/geo_spgist.c
+++ b/src/backend/utils/adt/geo_spgist.c
@@ -74,9 +74,11 @@
#include "postgres.h"
#include "access/spgist.h"
+#include "access/spgist_private.h"
#include "access/stratnum.h"
#include "catalog/pg_type.h"
#include "utils/builtins.h"
+#include "utils/fmgroids.h"
#include "utils/geo_decls.h"
/*
@@ -366,6 +368,31 @@ overAbove4D(RectBox *rect_box, RangeBox *query)
return overHigher2D(&rect_box->range_box_y, &query->right);
}
+/* Lower bound for the distance between point and rect_box */
+static double
+pointToRectBoxDistance(Point *point, RectBox *rect_box)
+{
+ double dx;
+ double dy;
+
+ if (point->x < rect_box->range_box_x.left.low)
+ dx = rect_box->range_box_x.left.low - point->x;
+ else if (point->x > rect_box->range_box_x.right.high)
+ dx = point->x - rect_box->range_box_x.right.high;
+ else
+ dx = 0;
+
+ if (point->y < rect_box->range_box_y.left.low)
+ dy = rect_box->range_box_y.left.low - point->y;
+ else if (point->y > rect_box->range_box_y.right.high)
+ dy = point->y - rect_box->range_box_y.right.high;
+ else
+ dy = 0;
+
+ return HYPOT(dx, dy);
+}
+
+
/*
* SP-GiST config function
*/
@@ -473,6 +500,64 @@ spg_box_quad_picksplit(PG_FUNCTION_ARGS)
PG_RETURN_VOID();
}
+/* get circle bounding box */
+static BOX *
+circle_bbox(CIRCLE *circle)
+{
+ BOX *bbox = (BOX *) palloc(sizeof(BOX));
+
+ bbox->high.x = circle->center.x + circle->radius;
+ bbox->low.x = circle->center.x - circle->radius;
+ bbox->high.y = circle->center.y + circle->radius;
+ bbox->low.y = circle->center.y - circle->radius;
+
+ return bbox;
+}
+
+static bool
+is_bounding_box_test_exact(StrategyNumber strategy)
+{
+ switch (strategy)
+ {
+ case RTLeftStrategyNumber:
+ case RTOverLeftStrategyNumber:
+ case RTOverRightStrategyNumber:
+ case RTRightStrategyNumber:
+ case RTOverBelowStrategyNumber:
+ case RTBelowStrategyNumber:
+ case RTAboveStrategyNumber:
+ case RTOverAboveStrategyNumber:
+ return true;
+
+ default:
+ return false;
+ }
+}
+
+static BOX *
+spg_box_quad_get_scankey_bbox(ScanKey sk, bool *recheck)
+{
+ switch (sk->sk_subtype)
+ {
+ case BOXOID:
+ return DatumGetBoxP(sk->sk_argument);
+
+ case CIRCLEOID:
+ if (recheck && !is_bounding_box_test_exact(sk->sk_strategy))
+ *recheck = true;
+ return circle_bbox(DatumGetCircleP(sk->sk_argument));
+
+ case POLYGONOID:
+ if (recheck && !is_bounding_box_test_exact(sk->sk_strategy))
+ *recheck = true;
+ return &DatumGetPolygonP(sk->sk_argument)->boundbox;
+
+ default:
+ elog(ERROR, "unrecognized scankey subtype: %d", sk->sk_subtype);
+ return NULL;
+ }
+}
+
/*
* SP-GiST inner consistent function
*/
@@ -488,6 +573,15 @@ spg_box_quad_inner_consistent(PG_FUNCTION_ARGS)
RangeBox *centroid,
**queries;
+ /*
+ * We are saving the traversal value or initialize it an unbounded one, if
+ * we have just begun to walk the tree.
+ */
+ if (in->traversalValue)
+ rect_box = in->traversalValue;
+ else
+ rect_box = initRectBox();
+
if (in->allTheSame)
{
/* Report that all nodes should be visited */
@@ -496,31 +590,51 @@ spg_box_quad_inner_consistent(PG_FUNCTION_ARGS)
for (i = 0; i < in->nNodes; i++)
out->nodeNumbers[i] = i;
+ if (in->norderbys > 0 && in->nNodes > 0)
+ {
+ double *distances = palloc(sizeof(double) * in->norderbys);
+ int j;
+
+ for (j = 0; j < in->norderbys; j++)
+ {
+ Point *pt = DatumGetPointP(in->orderbyKeys[j].sk_argument);
+
+ distances[j] = pointToRectBoxDistance(pt, rect_box);
+ }
+
+ out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
+ out->distances[0] = distances;
+
+ for (i = 1; i < in->nNodes; i++)
+ {
+ out->distances[i] = palloc(sizeof(double) * in->norderbys);
+ memcpy(out->distances[i], distances,
+ sizeof(double) * in->norderbys);
+ }
+ }
+
PG_RETURN_VOID();
}
/*
- * We are saving the traversal value or initialize it an unbounded one, if
- * we have just begun to walk the tree.
- */
- if (in->traversalValue)
- rect_box = in->traversalValue;
- else
- rect_box = initRectBox();
-
- /*
* We are casting the prefix and queries to RangeBoxes for ease of the
* following operations.
*/
centroid = getRangeBox(DatumGetBoxP(in->prefixDatum));
queries = (RangeBox **) palloc(in->nkeys * sizeof(RangeBox *));
for (i = 0; i < in->nkeys; i++)
- queries[i] = getRangeBox(DatumGetBoxP(in->scankeys[i].sk_argument));
+ {
+ BOX *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i], NULL);
+
+ queries[i] = getRangeBox(box);
+ }
/* Allocate enough memory for nodes */
out->nNodes = 0;
out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
+ if (in->norderbys > 0)
+ out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
/*
* We switch memory context, because we want to allocate memory for new
@@ -598,6 +712,22 @@ spg_box_quad_inner_consistent(PG_FUNCTION_ARGS)
{
out->traversalValues[out->nNodes] = next_rect_box;
out->nodeNumbers[out->nNodes] = quadrant;
+
+ if (in->norderbys > 0)
+ {
+ double *distances = palloc(sizeof(double) * in->norderbys);
+ int j;
+
+ out->distances[out->nNodes] = distances;
+
+ for (j = 0; j < in->norderbys; j++)
+ {
+ Point *pt = DatumGetPointP(in->orderbyKeys[j].sk_argument);
+
+ distances[j] = pointToRectBoxDistance(pt, next_rect_box);
+ }
+ }
+
out->nNodes++;
}
else
@@ -638,7 +768,9 @@ spg_box_quad_leaf_consistent(PG_FUNCTION_ARGS)
for (i = 0; i < in->nkeys; i++)
{
StrategyNumber strategy = in->scankeys[i].sk_strategy;
- Datum query = in->scankeys[i].sk_argument;
+ BOX *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i],
+ &out->recheck);
+ Datum query = BoxPGetDatum(box);
switch (strategy)
{
@@ -711,5 +843,63 @@ spg_box_quad_leaf_consistent(PG_FUNCTION_ARGS)
break;
}
+ if (flag && in->norderbys > 0)
+ {
+ Oid distfnoid = in->orderbykeys[0].sk_func.fn_oid;
+
+ spg_point_distance(leaf, in->norderbys, in->orderbykeys,
+ &out->distances, false);
+
+ /* Recheck is necessary when computing distance to polygon or circle */
+ out->recheckDistances = distfnoid == F_DIST_CPOINT ||
+ distfnoid == F_DIST_POLYP;
+ }
+
PG_RETURN_BOOL(flag);
}
+
+
+/*
+ * SP-GiST config function for 2-D types that are lossy represented by their
+ * bounding boxes
+ */
+Datum
+spg_bbox_quad_config(PG_FUNCTION_ARGS)
+{
+ spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
+
+ cfg->prefixType = BOXOID; /* A type represented by its bounding box */
+ cfg->labelType = VOIDOID; /* We don't need node labels. */
+ cfg->canReturnData = false;
+ cfg->longValuesOK = false;
+
+ PG_RETURN_VOID();
+}
+
+/*
+ * SP-GiST compress function for circles
+ */
+Datum
+spg_circle_quad_compress(PG_FUNCTION_ARGS)
+{
+ spgCompressIn *in = (spgCompressIn *) PG_GETARG_POINTER(0);
+ spgCompressOut *out = (spgCompressOut *) PG_GETARG_POINTER(1);
+
+ out->datum = BoxPGetDatum(circle_bbox(DatumGetCircleP(in->datum)));
+
+ PG_RETURN_VOID();
+}
+
+/*
+ * SP-GiST compress function for polygons
+ */
+Datum
+spg_poly_quad_compress(PG_FUNCTION_ARGS)
+{
+ spgCompressIn *in = (spgCompressIn *) PG_GETARG_POINTER(0);
+ spgCompressOut *out = (spgCompressOut *) PG_GETARG_POINTER(1);
+
+ out->datum = BoxPGetDatum(box_copy(&DatumGetPolygonP(in->datum)->boundbox));
+
+ PG_RETURN_VOID();
+}
diff --git a/src/include/catalog/pg_amop.h b/src/include/catalog/pg_amop.h
index 066cb46..722e5b4 100644
--- a/src/include/catalog/pg_amop.h
+++ b/src/include/catalog/pg_amop.h
@@ -848,6 +848,40 @@ DATA(insert ( 5000 603 603 11 s 2573 4000 0 ));
DATA(insert ( 5000 603 603 12 s 2572 4000 0 ));
/*
+ * SP-GiST circle_ops
+ */
+DATA(insert ( 5007 718 718 1 s 1506 4000 0 ));
+DATA(insert ( 5007 718 718 2 s 1507 4000 0 ));
+DATA(insert ( 5007 718 718 3 s 1513 4000 0 ));
+DATA(insert ( 5007 718 718 4 s 1508 4000 0 ));
+DATA(insert ( 5007 718 718 5 s 1509 4000 0 ));
+DATA(insert ( 5007 718 718 6 s 1512 4000 0 ));
+DATA(insert ( 5007 718 718 7 s 1511 4000 0 ));
+DATA(insert ( 5007 718 718 8 s 1510 4000 0 ));
+DATA(insert ( 5007 718 718 9 s 2589 4000 0 ));
+DATA(insert ( 5007 718 718 10 s 1515 4000 0 ));
+DATA(insert ( 5007 718 718 11 s 1514 4000 0 ));
+DATA(insert ( 5007 718 718 12 s 2590 4000 0 ));
+DATA(insert ( 5007 718 600 15 o 3291 4000 1970 ));
+
+/*
+ * SP-GiST poly_ops (supports polygons)
+ */
+DATA(insert ( 5008 604 604 1 s 485 4000 0 ));
+DATA(insert ( 5008 604 604 2 s 486 4000 0 ));
+DATA(insert ( 5008 604 604 3 s 492 4000 0 ));
+DATA(insert ( 5008 604 604 4 s 487 4000 0 ));
+DATA(insert ( 5008 604 604 5 s 488 4000 0 ));
+DATA(insert ( 5008 604 604 6 s 491 4000 0 ));
+DATA(insert ( 5008 604 604 7 s 490 4000 0 ));
+DATA(insert ( 5008 604 604 8 s 489 4000 0 ));
+DATA(insert ( 5008 604 604 9 s 2575 4000 0 ));
+DATA(insert ( 5008 604 604 10 s 2574 4000 0 ));
+DATA(insert ( 5008 604 604 11 s 2577 4000 0 ));
+DATA(insert ( 5008 604 604 12 s 2576 4000 0 ));
+DATA(insert ( 5008 604 600 15 o 3289 4000 1970 ));
+
+/*
* GiST inet_ops
*/
DATA(insert ( 3550 869 869 3 s 3552 783 0 ));
diff --git a/src/include/catalog/pg_amproc.h b/src/include/catalog/pg_amproc.h
index f1a52ce..2de94f3 100644
--- a/src/include/catalog/pg_amproc.h
+++ b/src/include/catalog/pg_amproc.h
@@ -306,6 +306,18 @@ DATA(insert ( 5000 603 603 2 5013 ));
DATA(insert ( 5000 603 603 3 5014 ));
DATA(insert ( 5000 603 603 4 5015 ));
DATA(insert ( 5000 603 603 5 5016 ));
+DATA(insert ( 5007 718 718 1 5009 ));
+DATA(insert ( 5007 718 718 2 5013 ));
+DATA(insert ( 5007 718 718 3 5014 ));
+DATA(insert ( 5007 718 718 4 5015 ));
+DATA(insert ( 5007 718 718 5 5016 ));
+DATA(insert ( 5007 718 718 6 5010 ));
+DATA(insert ( 5008 604 604 1 5009 ));
+DATA(insert ( 5008 604 604 2 5013 ));
+DATA(insert ( 5008 604 604 3 5014 ));
+DATA(insert ( 5008 604 604 4 5015 ));
+DATA(insert ( 5008 604 604 5 5016 ));
+DATA(insert ( 5008 604 604 6 5011 ));
/* BRIN opclasses */
/* minmax bytea */
diff --git a/src/include/catalog/pg_opclass.h b/src/include/catalog/pg_opclass.h
index 0cde14c..d8eded9 100644
--- a/src/include/catalog/pg_opclass.h
+++ b/src/include/catalog/pg_opclass.h
@@ -203,6 +203,8 @@ DATA(insert ( 4000 box_ops PGNSP PGUID 5000 603 t 0 ));
DATA(insert ( 4000 quad_point_ops PGNSP PGUID 4015 600 t 0 ));
DATA(insert ( 4000 kd_point_ops PGNSP PGUID 4016 600 f 0 ));
DATA(insert ( 4000 text_ops PGNSP PGUID 4017 25 t 0 ));
+DATA(insert ( 4000 circle_ops PGNSP PGUID 5007 718 t 603 ));
+DATA(insert ( 4000 poly_ops PGNSP PGUID 5008 604 t 603 ));
DATA(insert ( 403 jsonb_ops PGNSP PGUID 4033 3802 t 0 ));
DATA(insert ( 405 jsonb_ops PGNSP PGUID 4034 3802 t 0 ));
DATA(insert ( 2742 jsonb_ops PGNSP PGUID 4036 3802 t 25 ));
diff --git a/src/include/catalog/pg_opfamily.h b/src/include/catalog/pg_opfamily.h
index bd673fe..4bb26cd 100644
--- a/src/include/catalog/pg_opfamily.h
+++ b/src/include/catalog/pg_opfamily.h
@@ -183,5 +183,7 @@ DATA(insert OID = 4103 ( 3580 range_inclusion_ops PGNSP PGUID ));
DATA(insert OID = 4082 ( 3580 pg_lsn_minmax_ops PGNSP PGUID ));
DATA(insert OID = 4104 ( 3580 box_inclusion_ops PGNSP PGUID ));
DATA(insert OID = 5000 ( 4000 box_ops PGNSP PGUID ));
+DATA(insert OID = 5007 ( 4000 circle_ops PGNSP PGUID ));
+DATA(insert OID = 5008 ( 4000 poly_ops PGNSP PGUID ));
#endif /* PG_OPFAMILY_H */
diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h
index 05652e8..2817606 100644
--- a/src/include/catalog/pg_proc.h
+++ b/src/include/catalog/pg_proc.h
@@ -5186,6 +5186,13 @@ DESCR("SP-GiST support for quad tree over box");
DATA(insert OID = 5016 ( spg_box_quad_leaf_consistent PGNSP PGUID 12 1 0 0 0 f f f f t f i s 2 0 16 "2281 2281" _null_ _null_ _null_ _null_ _null_ spg_box_quad_leaf_consistent _null_ _null_ _null_ ));
DESCR("SP-GiST support for quad tree over box");
+DATA(insert OID = 5009 ( spg_bbox_quad_config PGNSP PGUID 12 1 0 0 0 f f f f t f i s 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ _null_ spg_bbox_quad_config _null_ _null_ _null_ ));
+DESCR("SP-GiST support for quad tree over 2-D types represented by their bounding boxes");
+DATA(insert OID = 5010 ( spg_circle_quad_compress PGNSP PGUID 12 1 0 0 0 f f f f t f i s 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ _null_ spg_circle_quad_compress _null_ _null_ _null_ ));
+DESCR("SP-GiST support for quad tree over circle");
+DATA(insert OID = 5011 ( spg_poly_quad_compress PGNSP PGUID 12 1 0 0 0 f f f f t f i s 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ _null_ spg_poly_quad_compress _null_ _null_ _null_ ));
+DESCR("SP-GiST support for quad tree over polygons");
+
/* replication slots */
DATA(insert OID = 3779 ( pg_create_physical_replication_slot PGNSP PGUID 12 1 0 0 0 f f f f t f v u 3 0 2249 "19 16 16" "{19,16,16,19,3220}" "{i,i,i,o,o}" "{slot_name,immediately_reserve,temporary,slot_name,xlog_position}" _null_ _null_ pg_create_physical_replication_slot _null_ _null_ _null_ ));
DESCR("create a physical replication slot");
diff --git a/src/test/regress/expected/circle.out b/src/test/regress/expected/circle.out
index 9ba4a04..2d4bf70 100644
--- a/src/test/regress/expected/circle.out
+++ b/src/test/regress/expected/circle.out
@@ -97,3 +97,291 @@ SELECT '' as five, c1.f1 AS one, c2.f1 AS two, (c1.f1 <-> c2.f1) AS distance
| <(1,2),3> | <(100,200),10> | 208.370729772479
(5 rows)
+--
+-- Test the SP-GiST index
+--
+CREATE TEMPORARY TABLE quad_circle_tbl (id int, c circle);
+INSERT INTO quad_circle_tbl
+ SELECT (x - 1) * 100 + y, circle(point(x * 10, y * 10), 1 + (x + y) % 10)
+ FROM generate_series(1, 100) x,
+ generate_series(1, 100) y;
+INSERT INTO quad_circle_tbl
+ SELECT i, '<(200, 300), 5>'
+ FROM generate_series(10001, 11000) AS i;
+INSERT INTO quad_circle_tbl
+ VALUES
+ (11001, NULL),
+ (11002, NULL),
+ (11003, '<(0,100), infinity>'),
+ (11004, '<(-infinity,0),1000>'),
+ (11005, '<(infinity,-infinity),infinity>');
+CREATE INDEX quad_circle_tbl_idx ON quad_circle_tbl USING spgist(c);
+-- get reference results for ORDER BY distance from seq scan
+SET enable_seqscan = ON;
+SET enable_indexscan = OFF;
+SET enable_bitmapscan = OFF;
+CREATE TEMP TABLE quad_cirle_tbl_ord_seq1 AS
+SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id
+FROM quad_circle_tbl;
+CREATE TEMP TABLE quad_cirle_tbl_ord_seq2 AS
+SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id
+FROM quad_circle_tbl WHERE c <@ circle '<(300,400),200>';
+-- check results results from index scan
+SET enable_seqscan = OFF;
+SET enable_indexscan = OFF;
+SET enable_bitmapscan = ON;
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c << circle '<(300,400),200>';
+ QUERY PLAN
+------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_circle_tbl
+ Recheck Cond: (c << '<(300,400),200>'::circle)
+ -> Bitmap Index Scan on quad_circle_tbl_idx
+ Index Cond: (c << '<(300,400),200>'::circle)
+(5 rows)
+
+SELECT count(*) FROM quad_circle_tbl WHERE c << circle '<(300,400),200>';
+ count
+-------
+ 891
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c &< circle '<(300,400),200>';
+ QUERY PLAN
+------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_circle_tbl
+ Recheck Cond: (c &< '<(300,400),200>'::circle)
+ -> Bitmap Index Scan on quad_circle_tbl_idx
+ Index Cond: (c &< '<(300,400),200>'::circle)
+(5 rows)
+
+SELECT count(*) FROM quad_circle_tbl WHERE c &< circle '<(300,400),200>';
+ count
+-------
+ 5901
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c && circle '<(300,400),200>';
+ QUERY PLAN
+------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_circle_tbl
+ Recheck Cond: (c && '<(300,400),200>'::circle)
+ -> Bitmap Index Scan on quad_circle_tbl_idx
+ Index Cond: (c && '<(300,400),200>'::circle)
+(5 rows)
+
+SELECT count(*) FROM quad_circle_tbl WHERE c && circle '<(300,400),200>';
+ count
+-------
+ 2334
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c &> circle '<(300,400),200>';
+ QUERY PLAN
+------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_circle_tbl
+ Recheck Cond: (c &> '<(300,400),200>'::circle)
+ -> Bitmap Index Scan on quad_circle_tbl_idx
+ Index Cond: (c &> '<(300,400),200>'::circle)
+(5 rows)
+
+SELECT count(*) FROM quad_circle_tbl WHERE c &> circle '<(300,400),200>';
+ count
+-------
+ 10000
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c >> circle '<(300,400),200>';
+ QUERY PLAN
+------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_circle_tbl
+ Recheck Cond: (c >> '<(300,400),200>'::circle)
+ -> Bitmap Index Scan on quad_circle_tbl_idx
+ Index Cond: (c >> '<(300,400),200>'::circle)
+(5 rows)
+
+SELECT count(*) FROM quad_circle_tbl WHERE c >> circle '<(300,400),200>';
+ count
+-------
+ 4990
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c <<| circle '<(300,400),200>';
+ QUERY PLAN
+-------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_circle_tbl
+ Recheck Cond: (c <<| '<(300,400),200>'::circle)
+ -> Bitmap Index Scan on quad_circle_tbl_idx
+ Index Cond: (c <<| '<(300,400),200>'::circle)
+(5 rows)
+
+SELECT count(*) FROM quad_circle_tbl WHERE c <<| circle '<(300,400),200>';
+ count
+-------
+ 1890
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c &<| circle '<(300,400),200>';
+ QUERY PLAN
+-------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_circle_tbl
+ Recheck Cond: (c &<| '<(300,400),200>'::circle)
+ -> Bitmap Index Scan on quad_circle_tbl_idx
+ Index Cond: (c &<| '<(300,400),200>'::circle)
+(5 rows)
+
+SELECT count(*) FROM quad_circle_tbl WHERE c &<| circle '<(300,400),200>';
+ count
+-------
+ 6900
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c |&> circle '<(300,400),200>';
+ QUERY PLAN
+-------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_circle_tbl
+ Recheck Cond: (c |&> '<(300,400),200>'::circle)
+ -> Bitmap Index Scan on quad_circle_tbl_idx
+ Index Cond: (c |&> '<(300,400),200>'::circle)
+(5 rows)
+
+SELECT count(*) FROM quad_circle_tbl WHERE c |&> circle '<(300,400),200>';
+ count
+-------
+ 9000
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c |>> circle '<(300,400),200>';
+ QUERY PLAN
+-------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_circle_tbl
+ Recheck Cond: (c |>> '<(300,400),200>'::circle)
+ -> Bitmap Index Scan on quad_circle_tbl_idx
+ Index Cond: (c |>> '<(300,400),200>'::circle)
+(5 rows)
+
+SELECT count(*) FROM quad_circle_tbl WHERE c |>> circle '<(300,400),200>';
+ count
+-------
+ 3990
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c @> circle '<(300,400),1>';
+ QUERY PLAN
+----------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_circle_tbl
+ Recheck Cond: (c @> '<(300,400),1>'::circle)
+ -> Bitmap Index Scan on quad_circle_tbl_idx
+ Index Cond: (c @> '<(300,400),1>'::circle)
+(5 rows)
+
+SELECT count(*) FROM quad_circle_tbl WHERE c @> circle '<(300,400),1>';
+ count
+-------
+ 2
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c <@ circle '<(300,400),200>';
+ QUERY PLAN
+------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_circle_tbl
+ Recheck Cond: (c <@ '<(300,400),200>'::circle)
+ -> Bitmap Index Scan on quad_circle_tbl_idx
+ Index Cond: (c <@ '<(300,400),200>'::circle)
+(5 rows)
+
+SELECT count(*) FROM quad_circle_tbl WHERE c <@ circle '<(300,400),200>';
+ count
+-------
+ 2181
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c ~= circle '<(300,400),1>';
+ QUERY PLAN
+----------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_circle_tbl
+ Recheck Cond: (c ~= '<(300,400),1>'::circle)
+ -> Bitmap Index Scan on quad_circle_tbl_idx
+ Index Cond: (c ~= '<(300,400),1>'::circle)
+(5 rows)
+
+SELECT count(*) FROM quad_circle_tbl WHERE c ~= circle '<(300,400),1>';
+ count
+-------
+ 1
+(1 row)
+
+-- test ORDER BY distance
+SET enable_indexscan = ON;
+SET enable_bitmapscan = OFF;
+EXPLAIN (COSTS OFF)
+SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id
+FROM quad_circle_tbl;
+ QUERY PLAN
+---------------------------------------------------------------
+ WindowAgg
+ -> Index Scan using quad_circle_tbl_idx on quad_circle_tbl
+ Order By: (c <-> '(123,456)'::point)
+(3 rows)
+
+CREATE TEMP TABLE quad_cirle_tbl_ord_idx1 AS
+SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id
+FROM quad_circle_tbl;
+SELECT *
+FROM quad_cirle_tbl_ord_seq1 seq FULL JOIN quad_cirle_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 c <-> point '123,456') n, c <-> point '123,456' dist, id
+FROM quad_circle_tbl WHERE c <@ circle '<(300,400),200>';
+ QUERY PLAN
+---------------------------------------------------------------
+ WindowAgg
+ -> Index Scan using quad_circle_tbl_idx on quad_circle_tbl
+ Index Cond: (c <@ '<(300,400),200>'::circle)
+ Order By: (c <-> '(123,456)'::point)
+(4 rows)
+
+CREATE TEMP TABLE quad_cirle_tbl_ord_idx2 AS
+SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id
+FROM quad_circle_tbl WHERE c <@ circle '<(300,400),200>';
+SELECT *
+FROM quad_cirle_tbl_ord_seq2 seq FULL JOIN quad_cirle_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/polygon.out b/src/test/regress/expected/polygon.out
index 2361274..7a623be 100644
--- a/src/test/regress/expected/polygon.out
+++ b/src/test/regress/expected/polygon.out
@@ -227,3 +227,289 @@ SELECT '(0,0)'::point <-> '((0,0),(1,2),(2,1))'::polygon as on_corner,
0 | 0 | 0 | 1.4142135623731 | 3.2
(1 row)
+--
+-- Test the SP-GiST index
+--
+CREATE TEMPORARY TABLE quad_poly_tbl (id int, p polygon);
+INSERT INTO quad_poly_tbl
+ SELECT (x - 1) * 100 + y, polygon(circle(point(x * 10, y * 10), 1 + (x + y) % 10))
+ FROM generate_series(1, 100) x,
+ generate_series(1, 100) y;
+INSERT INTO quad_poly_tbl
+ SELECT i, polygon '((200, 300),(210, 310),(230, 290))'
+ FROM generate_series(10001, 11000) AS i;
+INSERT INTO quad_poly_tbl
+ VALUES
+ (11001, NULL),
+ (11002, NULL),
+ (11003, NULL);
+CREATE INDEX quad_poly_tbl_idx ON quad_poly_tbl USING spgist(p);
+-- get reference results for ORDER BY distance from seq scan
+SET enable_seqscan = ON;
+SET enable_indexscan = OFF;
+SET enable_bitmapscan = OFF;
+CREATE TEMP TABLE quad_poly_tbl_ord_seq1 AS
+SELECT rank() OVER (ORDER BY p <-> point '123,456') n, p <-> point '123,456' dist, id
+FROM quad_poly_tbl;
+CREATE TEMP TABLE quad_poly_tbl_ord_seq2 AS
+SELECT rank() OVER (ORDER BY p <-> point '123,456') n, p <-> point '123,456' dist, id
+FROM quad_poly_tbl WHERE p <@ polygon '((300,300),(400,600),(600,500),(700,200))';
+-- check results results from index scan
+SET enable_seqscan = OFF;
+SET enable_indexscan = OFF;
+SET enable_bitmapscan = ON;
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p << polygon '((300,300),(400,600),(600,500),(700,200))';
+ QUERY PLAN
+---------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_poly_tbl
+ Recheck Cond: (p << '((300,300),(400,600),(600,500),(700,200))'::polygon)
+ -> Bitmap Index Scan on quad_poly_tbl_idx
+ Index Cond: (p << '((300,300),(400,600),(600,500),(700,200))'::polygon)
+(5 rows)
+
+SELECT count(*) FROM quad_poly_tbl WHERE p << polygon '((300,300),(400,600),(600,500),(700,200))';
+ count
+-------
+ 3890
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p &< polygon '((300,300),(400,600),(600,500),(700,200))';
+ QUERY PLAN
+---------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_poly_tbl
+ Recheck Cond: (p &< '((300,300),(400,600),(600,500),(700,200))'::polygon)
+ -> Bitmap Index Scan on quad_poly_tbl_idx
+ Index Cond: (p &< '((300,300),(400,600),(600,500),(700,200))'::polygon)
+(5 rows)
+
+SELECT count(*) FROM quad_poly_tbl WHERE p &< polygon '((300,300),(400,600),(600,500),(700,200))';
+ count
+-------
+ 7900
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p && polygon '((300,300),(400,600),(600,500),(700,200))';
+ QUERY PLAN
+---------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_poly_tbl
+ Recheck Cond: (p && '((300,300),(400,600),(600,500),(700,200))'::polygon)
+ -> Bitmap Index Scan on quad_poly_tbl_idx
+ Index Cond: (p && '((300,300),(400,600),(600,500),(700,200))'::polygon)
+(5 rows)
+
+SELECT count(*) FROM quad_poly_tbl WHERE p && polygon '((300,300),(400,600),(600,500),(700,200))';
+ count
+-------
+ 977
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p &> polygon '((300,300),(400,600),(600,500),(700,200))';
+ QUERY PLAN
+---------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_poly_tbl
+ Recheck Cond: (p &> '((300,300),(400,600),(600,500),(700,200))'::polygon)
+ -> Bitmap Index Scan on quad_poly_tbl_idx
+ Index Cond: (p &> '((300,300),(400,600),(600,500),(700,200))'::polygon)
+(5 rows)
+
+SELECT count(*) FROM quad_poly_tbl WHERE p &> polygon '((300,300),(400,600),(600,500),(700,200))';
+ count
+-------
+ 7000
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p >> polygon '((300,300),(400,600),(600,500),(700,200))';
+ QUERY PLAN
+---------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_poly_tbl
+ Recheck Cond: (p >> '((300,300),(400,600),(600,500),(700,200))'::polygon)
+ -> Bitmap Index Scan on quad_poly_tbl_idx
+ Index Cond: (p >> '((300,300),(400,600),(600,500),(700,200))'::polygon)
+(5 rows)
+
+SELECT count(*) FROM quad_poly_tbl WHERE p >> polygon '((300,300),(400,600),(600,500),(700,200))';
+ count
+-------
+ 2990
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p <<| polygon '((300,300),(400,600),(600,500),(700,200))';
+ QUERY PLAN
+----------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_poly_tbl
+ Recheck Cond: (p <<| '((300,300),(400,600),(600,500),(700,200))'::polygon)
+ -> Bitmap Index Scan on quad_poly_tbl_idx
+ Index Cond: (p <<| '((300,300),(400,600),(600,500),(700,200))'::polygon)
+(5 rows)
+
+SELECT count(*) FROM quad_poly_tbl WHERE p <<| polygon '((300,300),(400,600),(600,500),(700,200))';
+ count
+-------
+ 1890
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p &<| polygon '((300,300),(400,600),(600,500),(700,200))';
+ QUERY PLAN
+----------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_poly_tbl
+ Recheck Cond: (p &<| '((300,300),(400,600),(600,500),(700,200))'::polygon)
+ -> Bitmap Index Scan on quad_poly_tbl_idx
+ Index Cond: (p &<| '((300,300),(400,600),(600,500),(700,200))'::polygon)
+(5 rows)
+
+SELECT count(*) FROM quad_poly_tbl WHERE p &<| polygon '((300,300),(400,600),(600,500),(700,200))';
+ count
+-------
+ 6900
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p |&> polygon '((300,300),(400,600),(600,500),(700,200))';
+ QUERY PLAN
+----------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_poly_tbl
+ Recheck Cond: (p |&> '((300,300),(400,600),(600,500),(700,200))'::polygon)
+ -> Bitmap Index Scan on quad_poly_tbl_idx
+ Index Cond: (p |&> '((300,300),(400,600),(600,500),(700,200))'::polygon)
+(5 rows)
+
+SELECT count(*) FROM quad_poly_tbl WHERE p |&> polygon '((300,300),(400,600),(600,500),(700,200))';
+ count
+-------
+ 9000
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p |>> polygon '((300,300),(400,600),(600,500),(700,200))';
+ QUERY PLAN
+----------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_poly_tbl
+ Recheck Cond: (p |>> '((300,300),(400,600),(600,500),(700,200))'::polygon)
+ -> Bitmap Index Scan on quad_poly_tbl_idx
+ Index Cond: (p |>> '((300,300),(400,600),(600,500),(700,200))'::polygon)
+(5 rows)
+
+SELECT count(*) FROM quad_poly_tbl WHERE p |>> polygon '((300,300),(400,600),(600,500),(700,200))';
+ count
+-------
+ 3990
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p <@ polygon '((300,300),(400,600),(600,500),(700,200))';
+ QUERY PLAN
+---------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_poly_tbl
+ Recheck Cond: (p <@ '((300,300),(400,600),(600,500),(700,200))'::polygon)
+ -> Bitmap Index Scan on quad_poly_tbl_idx
+ Index Cond: (p <@ '((300,300),(400,600),(600,500),(700,200))'::polygon)
+(5 rows)
+
+SELECT count(*) FROM quad_poly_tbl WHERE p <@ polygon '((300,300),(400,600),(600,500),(700,200))';
+ count
+-------
+ 831
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p @> polygon '((340,550),(343,552),(341,553))';
+ QUERY PLAN
+-----------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_poly_tbl
+ Recheck Cond: (p @> '((340,550),(343,552),(341,553))'::polygon)
+ -> Bitmap Index Scan on quad_poly_tbl_idx
+ Index Cond: (p @> '((340,550),(343,552),(341,553))'::polygon)
+(5 rows)
+
+SELECT count(*) FROM quad_poly_tbl WHERE p @> polygon '((340,550),(343,552),(341,553))';
+ count
+-------
+ 1
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p ~= polygon '((200, 300),(210, 310),(230, 290))';
+ QUERY PLAN
+-----------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on quad_poly_tbl
+ Recheck Cond: (p ~= '((200,300),(210,310),(230,290))'::polygon)
+ -> Bitmap Index Scan on quad_poly_tbl_idx
+ Index Cond: (p ~= '((200,300),(210,310),(230,290))'::polygon)
+(5 rows)
+
+SELECT count(*) FROM quad_poly_tbl WHERE p ~= polygon '((200, 300),(210, 310),(230, 290))';
+ count
+-------
+ 1000
+(1 row)
+
+-- test ORDER BY distance
+SET enable_indexscan = ON;
+SET enable_bitmapscan = OFF;
+EXPLAIN (COSTS OFF)
+SELECT rank() OVER (ORDER BY p <-> point '123,456') n, p <-> point '123,456' dist, id
+FROM quad_poly_tbl;
+ QUERY PLAN
+-----------------------------------------------------------
+ WindowAgg
+ -> Index Scan using quad_poly_tbl_idx on quad_poly_tbl
+ Order By: (p <-> '(123,456)'::point)
+(3 rows)
+
+CREATE TEMP TABLE quad_poly_tbl_ord_idx1 AS
+SELECT rank() OVER (ORDER BY p <-> point '123,456') n, p <-> point '123,456' dist, id
+FROM quad_poly_tbl;
+SELECT *
+FROM quad_poly_tbl_ord_seq1 seq FULL JOIN quad_poly_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 p <-> point '123,456') n, p <-> point '123,456' dist, id
+FROM quad_poly_tbl WHERE p <@ polygon '((300,300),(400,600),(600,500),(700,200))';
+ QUERY PLAN
+---------------------------------------------------------------------------------
+ WindowAgg
+ -> Index Scan using quad_poly_tbl_idx on quad_poly_tbl
+ Index Cond: (p <@ '((300,300),(400,600),(600,500),(700,200))'::polygon)
+ Order By: (p <-> '(123,456)'::point)
+(4 rows)
+
+CREATE TEMP TABLE quad_poly_tbl_ord_idx2 AS
+SELECT rank() OVER (ORDER BY p <-> point '123,456') n, p <-> point '123,456' dist, id
+FROM quad_poly_tbl WHERE p <@ polygon '((300,300),(400,600),(600,500),(700,200))';
+SELECT *
+FROM quad_poly_tbl_ord_seq2 seq FULL JOIN quad_poly_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/sql/circle.sql b/src/test/regress/sql/circle.sql
index c0284b2..16fa514 100644
--- a/src/test/regress/sql/circle.sql
+++ b/src/test/regress/sql/circle.sql
@@ -43,3 +43,131 @@ SELECT '' as five, c1.f1 AS one, c2.f1 AS two, (c1.f1 <-> c2.f1) AS distance
FROM CIRCLE_TBL c1, CIRCLE_TBL c2
WHERE (c1.f1 < c2.f1) AND ((c1.f1 <-> c2.f1) > 0)
ORDER BY distance, area(c1.f1), area(c2.f1);
+
+--
+-- Test the SP-GiST index
+--
+
+CREATE TEMPORARY TABLE quad_circle_tbl (id int, c circle);
+
+INSERT INTO quad_circle_tbl
+ SELECT (x - 1) * 100 + y, circle(point(x * 10, y * 10), 1 + (x + y) % 10)
+ FROM generate_series(1, 100) x,
+ generate_series(1, 100) y;
+
+INSERT INTO quad_circle_tbl
+ SELECT i, '<(200, 300), 5>'
+ FROM generate_series(10001, 11000) AS i;
+
+INSERT INTO quad_circle_tbl
+ VALUES
+ (11001, NULL),
+ (11002, NULL),
+ (11003, '<(0,100), infinity>'),
+ (11004, '<(-infinity,0),1000>'),
+ (11005, '<(infinity,-infinity),infinity>');
+
+CREATE INDEX quad_circle_tbl_idx ON quad_circle_tbl USING spgist(c);
+
+-- get reference results for ORDER BY distance from seq scan
+SET enable_seqscan = ON;
+SET enable_indexscan = OFF;
+SET enable_bitmapscan = OFF;
+
+CREATE TEMP TABLE quad_cirle_tbl_ord_seq1 AS
+SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id
+FROM quad_circle_tbl;
+
+CREATE TEMP TABLE quad_cirle_tbl_ord_seq2 AS
+SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id
+FROM quad_circle_tbl WHERE c <@ circle '<(300,400),200>';
+
+-- check results results from index scan
+SET enable_seqscan = OFF;
+SET enable_indexscan = OFF;
+SET enable_bitmapscan = ON;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c << circle '<(300,400),200>';
+SELECT count(*) FROM quad_circle_tbl WHERE c << circle '<(300,400),200>';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c &< circle '<(300,400),200>';
+SELECT count(*) FROM quad_circle_tbl WHERE c &< circle '<(300,400),200>';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c && circle '<(300,400),200>';
+SELECT count(*) FROM quad_circle_tbl WHERE c && circle '<(300,400),200>';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c &> circle '<(300,400),200>';
+SELECT count(*) FROM quad_circle_tbl WHERE c &> circle '<(300,400),200>';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c >> circle '<(300,400),200>';
+SELECT count(*) FROM quad_circle_tbl WHERE c >> circle '<(300,400),200>';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c <<| circle '<(300,400),200>';
+SELECT count(*) FROM quad_circle_tbl WHERE c <<| circle '<(300,400),200>';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c &<| circle '<(300,400),200>';
+SELECT count(*) FROM quad_circle_tbl WHERE c &<| circle '<(300,400),200>';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c |&> circle '<(300,400),200>';
+SELECT count(*) FROM quad_circle_tbl WHERE c |&> circle '<(300,400),200>';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c |>> circle '<(300,400),200>';
+SELECT count(*) FROM quad_circle_tbl WHERE c |>> circle '<(300,400),200>';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c @> circle '<(300,400),1>';
+SELECT count(*) FROM quad_circle_tbl WHERE c @> circle '<(300,400),1>';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c <@ circle '<(300,400),200>';
+SELECT count(*) FROM quad_circle_tbl WHERE c <@ circle '<(300,400),200>';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_circle_tbl WHERE c ~= circle '<(300,400),1>';
+SELECT count(*) FROM quad_circle_tbl WHERE c ~= circle '<(300,400),1>';
+
+-- test ORDER BY distance
+SET enable_indexscan = ON;
+SET enable_bitmapscan = OFF;
+
+EXPLAIN (COSTS OFF)
+SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id
+FROM quad_circle_tbl;
+
+CREATE TEMP TABLE quad_cirle_tbl_ord_idx1 AS
+SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id
+FROM quad_circle_tbl;
+
+SELECT *
+FROM quad_cirle_tbl_ord_seq1 seq FULL JOIN quad_cirle_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 c <-> point '123,456') n, c <-> point '123,456' dist, id
+FROM quad_circle_tbl WHERE c <@ circle '<(300,400),200>';
+
+CREATE TEMP TABLE quad_cirle_tbl_ord_idx2 AS
+SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id
+FROM quad_circle_tbl WHERE c <@ circle '<(300,400),200>';
+
+SELECT *
+FROM quad_cirle_tbl_ord_seq2 seq FULL JOIN quad_cirle_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;
diff --git a/src/test/regress/sql/polygon.sql b/src/test/regress/sql/polygon.sql
index 7ac8079..8b8b434 100644
--- a/src/test/regress/sql/polygon.sql
+++ b/src/test/regress/sql/polygon.sql
@@ -116,3 +116,129 @@ SELECT '(0,0)'::point <-> '((0,0),(1,2),(2,1))'::polygon as on_corner,
'(2,2)'::point <-> '((0,0),(1,4),(3,1))'::polygon as inside,
'(3,3)'::point <-> '((0,2),(2,0),(2,2))'::polygon as near_corner,
'(4,4)'::point <-> '((0,0),(0,3),(4,0))'::polygon as near_segment;
+
+--
+-- Test the SP-GiST index
+--
+
+CREATE TEMPORARY TABLE quad_poly_tbl (id int, p polygon);
+
+INSERT INTO quad_poly_tbl
+ SELECT (x - 1) * 100 + y, polygon(circle(point(x * 10, y * 10), 1 + (x + y) % 10))
+ FROM generate_series(1, 100) x,
+ generate_series(1, 100) y;
+
+INSERT INTO quad_poly_tbl
+ SELECT i, polygon '((200, 300),(210, 310),(230, 290))'
+ FROM generate_series(10001, 11000) AS i;
+
+INSERT INTO quad_poly_tbl
+ VALUES
+ (11001, NULL),
+ (11002, NULL),
+ (11003, NULL);
+
+CREATE INDEX quad_poly_tbl_idx ON quad_poly_tbl USING spgist(p);
+
+-- get reference results for ORDER BY distance from seq scan
+SET enable_seqscan = ON;
+SET enable_indexscan = OFF;
+SET enable_bitmapscan = OFF;
+
+CREATE TEMP TABLE quad_poly_tbl_ord_seq1 AS
+SELECT rank() OVER (ORDER BY p <-> point '123,456') n, p <-> point '123,456' dist, id
+FROM quad_poly_tbl;
+
+CREATE TEMP TABLE quad_poly_tbl_ord_seq2 AS
+SELECT rank() OVER (ORDER BY p <-> point '123,456') n, p <-> point '123,456' dist, id
+FROM quad_poly_tbl WHERE p <@ polygon '((300,300),(400,600),(600,500),(700,200))';
+
+-- check results results from index scan
+SET enable_seqscan = OFF;
+SET enable_indexscan = OFF;
+SET enable_bitmapscan = ON;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p << polygon '((300,300),(400,600),(600,500),(700,200))';
+SELECT count(*) FROM quad_poly_tbl WHERE p << polygon '((300,300),(400,600),(600,500),(700,200))';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p &< polygon '((300,300),(400,600),(600,500),(700,200))';
+SELECT count(*) FROM quad_poly_tbl WHERE p &< polygon '((300,300),(400,600),(600,500),(700,200))';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p && polygon '((300,300),(400,600),(600,500),(700,200))';
+SELECT count(*) FROM quad_poly_tbl WHERE p && polygon '((300,300),(400,600),(600,500),(700,200))';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p &> polygon '((300,300),(400,600),(600,500),(700,200))';
+SELECT count(*) FROM quad_poly_tbl WHERE p &> polygon '((300,300),(400,600),(600,500),(700,200))';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p >> polygon '((300,300),(400,600),(600,500),(700,200))';
+SELECT count(*) FROM quad_poly_tbl WHERE p >> polygon '((300,300),(400,600),(600,500),(700,200))';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p <<| polygon '((300,300),(400,600),(600,500),(700,200))';
+SELECT count(*) FROM quad_poly_tbl WHERE p <<| polygon '((300,300),(400,600),(600,500),(700,200))';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p &<| polygon '((300,300),(400,600),(600,500),(700,200))';
+SELECT count(*) FROM quad_poly_tbl WHERE p &<| polygon '((300,300),(400,600),(600,500),(700,200))';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p |&> polygon '((300,300),(400,600),(600,500),(700,200))';
+SELECT count(*) FROM quad_poly_tbl WHERE p |&> polygon '((300,300),(400,600),(600,500),(700,200))';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p |>> polygon '((300,300),(400,600),(600,500),(700,200))';
+SELECT count(*) FROM quad_poly_tbl WHERE p |>> polygon '((300,300),(400,600),(600,500),(700,200))';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p <@ polygon '((300,300),(400,600),(600,500),(700,200))';
+SELECT count(*) FROM quad_poly_tbl WHERE p <@ polygon '((300,300),(400,600),(600,500),(700,200))';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p @> polygon '((340,550),(343,552),(341,553))';
+SELECT count(*) FROM quad_poly_tbl WHERE p @> polygon '((340,550),(343,552),(341,553))';
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM quad_poly_tbl WHERE p ~= polygon '((200, 300),(210, 310),(230, 290))';
+SELECT count(*) FROM quad_poly_tbl WHERE p ~= polygon '((200, 300),(210, 310),(230, 290))';
+
+-- test ORDER BY distance
+SET enable_indexscan = ON;
+SET enable_bitmapscan = OFF;
+
+EXPLAIN (COSTS OFF)
+SELECT rank() OVER (ORDER BY p <-> point '123,456') n, p <-> point '123,456' dist, id
+FROM quad_poly_tbl;
+
+CREATE TEMP TABLE quad_poly_tbl_ord_idx1 AS
+SELECT rank() OVER (ORDER BY p <-> point '123,456') n, p <-> point '123,456' dist, id
+FROM quad_poly_tbl;
+
+SELECT *
+FROM quad_poly_tbl_ord_seq1 seq FULL JOIN quad_poly_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 p <-> point '123,456') n, p <-> point '123,456' dist, id
+FROM quad_poly_tbl WHERE p <@ polygon '((300,300),(400,600),(600,500),(700,200))';
+
+CREATE TEMP TABLE quad_poly_tbl_ord_idx2 AS
+SELECT rank() OVER (ORDER BY p <-> point '123,456') n, p <-> point '123,456' dist, id
+FROM quad_poly_tbl WHERE p <@ polygon '((300,300),(400,600),(600,500),(700,200))';
+
+SELECT *
+FROM quad_poly_tbl_ord_seq2 seq FULL JOIN quad_poly_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;