Skip to content

Commit b90f8f2

Browse files
tglsfdctglsfdc
committed
Extend r-tree operator classes to handle Y-direction tests equivalent
to the existing X-direction tests. An rtree class now includes 4 actual 2-D tests, 4 1-D X-direction tests, and 4 1-D Y-direction tests. This involved adding four new Y-direction test operators for each of box and polygon; I followed the PostGIS project's lead as to the names of these operators. NON BACKWARDS COMPATIBLE CHANGE: the poly_overleft (&<) and poly_overright (&>) operators now have semantics comparable to box_overleft and box_overright. This is necessary to make r-tree indexes work correctly on polygons. Also, I changed circle_left and circle_right to agree with box_left and box_right --- formerly they allowed the boundaries to touch. This isn't actually essential given the lack of any r-tree opclass for circles, but it seems best to sync all the definitions while we are at it.
1 parent 39f3c5d commit b90f8f2

File tree

17 files changed

+394
-99
lines changed

17 files changed

+394
-99
lines changed

‎contrib/rtree_gist/rtree_gist.c

Lines changed: 32 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,13 @@
11
/*-------------------------------------------------------------------------
22
*
33
* rtree_gist.c
4-
* pg_amproc entries for GiSTs over 2-D boxes.
4+
* pg_amproc entries for GiSTs over 2-D boxes and polygons.
55
*
66
* This gives R-tree behavior, with Guttman's poly-time split algorithm.
77
*
88
*
99
* IDENTIFICATION
10-
* $PostgreSQL: pgsql/contrib/rtree_gist/rtree_gist.c,v 1.13 2005/06/24 00:18:52 tgl Exp $
10+
* $PostgreSQL: pgsql/contrib/rtree_gist/rtree_gist.c,v 1.14 2005/06/24 20:53:29 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -23,8 +23,8 @@ typedef Datum (*BINARY_UNION) (Datum, Datum, int *);
2323
typedef float (*SIZE_BOX) (Datum);
2424

2525
/*
26-
** box ops
27-
*/
26+
* box ops
27+
*/
2828
PG_FUNCTION_INFO_V1(gbox_compress);
2929
PG_FUNCTION_INFO_V1(gbox_union);
3030
PG_FUNCTION_INFO_V1(gbox_picksplit);
@@ -43,17 +43,17 @@ static bool gbox_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy);
4343
static float size_box(Datum box);
4444

4545
/*
46-
** Polygon ops
47-
*/
46+
* Polygon ops
47+
*/
4848
PG_FUNCTION_INFO_V1(gpoly_compress);
4949
PG_FUNCTION_INFO_V1(gpoly_consistent);
5050

5151
Datum gpoly_compress(PG_FUNCTION_ARGS);
5252
Datum gpoly_consistent(PG_FUNCTION_ARGS);
5353

5454
/*
55-
** Common rtree-function (for all ops)
56-
*/
55+
* Common rtree-function (for all ops)
56+
*/
5757
static bool rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy);
5858

5959
PG_FUNCTION_INFO_V1(rtree_decompress);
@@ -441,6 +441,18 @@ gbox_leaf_consistent(BOX *key,
441441
case RTContainedByStrategyNumber:
442442
retval = DatumGetBool(DirectFunctionCall2(box_contained, PointerGetDatum(key), PointerGetDatum(query)));
443443
break;
444+
case RTOverBelowStrategyNumber:
445+
retval = DatumGetBool(DirectFunctionCall2(box_overbelow, PointerGetDatum(key), PointerGetDatum(query)));
446+
break;
447+
case RTBelowStrategyNumber:
448+
retval = DatumGetBool(DirectFunctionCall2(box_below, PointerGetDatum(key), PointerGetDatum(query)));
449+
break;
450+
case RTAboveStrategyNumber:
451+
retval = DatumGetBool(DirectFunctionCall2(box_above, PointerGetDatum(key), PointerGetDatum(query)));
452+
break;
453+
case RTOverAboveStrategyNumber:
454+
retval = DatumGetBool(DirectFunctionCall2(box_overabove, PointerGetDatum(key), PointerGetDatum(query)));
455+
break;
444456
default:
445457
retval = FALSE;
446458
}
@@ -558,6 +570,18 @@ rtree_internal_consistent(BOX *key,
558570
case RTContainedByStrategyNumber:
559571
retval = DatumGetBool(DirectFunctionCall2(box_overlap, PointerGetDatum(key), PointerGetDatum(query)));
560572
break;
573+
case RTOverBelowStrategyNumber:
574+
retval = !DatumGetBool(DirectFunctionCall2(box_above, PointerGetDatum(key), PointerGetDatum(query)));
575+
break;
576+
case RTBelowStrategyNumber:
577+
retval = !DatumGetBool(DirectFunctionCall2(box_overabove, PointerGetDatum(key), PointerGetDatum(query)));
578+
break;
579+
case RTAboveStrategyNumber:
580+
retval = !DatumGetBool(DirectFunctionCall2(box_overbelow, PointerGetDatum(key), PointerGetDatum(query)));
581+
break;
582+
case RTOverAboveStrategyNumber:
583+
retval = !DatumGetBool(DirectFunctionCall2(box_below, PointerGetDatum(key), PointerGetDatum(query)));
584+
break;
561585
default:
562586
retval = FALSE;
563587
}

‎contrib/rtree_gist/rtree_gist.sql.in

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,7 @@ LANGUAGE 'C';
2727
CREATE FUNCTION gbox_penalty(internal,internal,internal)
2828
RETURNS internal
2929
AS 'MODULE_PATHNAME'
30-
LANGUAGE 'C' with (isstrict);
30+
LANGUAGE 'C' STRICT;
3131

3232
CREATE FUNCTION gbox_picksplit(internal, internal)
3333
RETURNS internal
@@ -56,6 +56,10 @@ AS
5656
OPERATOR 6 ~= ,
5757
OPERATOR 7 ~ ,
5858
OPERATOR 8 @ ,
59+
OPERATOR 9 &<| ,
60+
OPERATOR 10 <<| ,
61+
OPERATOR 11 |>> ,
62+
OPERATOR 12 |&> ,
5963
FUNCTION 1 gbox_consistent (internal, box, int4),
6064
FUNCTION 2 gbox_union (internal, internal),
6165
FUNCTION 3 gbox_compress (internal),
@@ -95,6 +99,10 @@ AS
9599
OPERATOR 6 ~= RECHECK,
96100
OPERATOR 7 ~ RECHECK,
97101
OPERATOR 8 @ RECHECK,
102+
OPERATOR 9 &<| RECHECK,
103+
OPERATOR 10 <<| RECHECK,
104+
OPERATOR 11 |>> RECHECK,
105+
OPERATOR 12 |&> RECHECK,
98106
FUNCTION 1 gpoly_consistent (internal, polygon, int4),
99107
FUNCTION 2 gbox_union (internal, internal),
100108
FUNCTION 3 gpoly_compress (internal),

‎doc/src/sgml/func.sgml

Lines changed: 40 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
<!--
2-
$PostgreSQL: pgsql/doc/src/sgml/func.sgml,v 1.258 2005/06/15 06:29:25 neilc Exp $
2+
$PostgreSQL: pgsql/doc/src/sgml/func.sgml,v 1.259 2005/06/24 20:53:29 tgl Exp $
33
PostgreSQL documentation
44
-->
55

@@ -5854,6 +5854,17 @@ SELECT TIMESTAMP 'now'; -- incorrect for use with DEFAULT
58545854
linkend="functions-geometry-conv-table">.
58555855
</para>
58565856

5857+
<caution>
5858+
<para>
5859+
Note that the <quote>same as</> operator, <literal>~=</>, represents
5860+
the usual notion of equality for the <type>point</type>,
5861+
<type>box</type>, <type>polygon</type>, and <type>circle</type> types.
5862+
Some of these types also have an <literal>=</> operator, but it compares
5863+
for equal <emphasis>areas</> only. The other scalar comparison operators
5864+
(<literal>&lt;=</> and so on) likewise compare areas for these types.
5865+
</para>
5866+
</caution>
5867+
58575868
<table id="functions-geometry-op-table">
58585869
<title>Geometric Operators</title>
58595870
<tgroup cols="3">
@@ -5920,6 +5931,16 @@ SELECT TIMESTAMP 'now'; -- incorrect for use with DEFAULT
59205931
<entry>Overlaps?</entry>
59215932
<entry><literal>box '((0,0),(1,1))' &amp;&amp; box '((0,0),(2,2))'</literal></entry>
59225933
</row>
5934+
<row>
5935+
<entry> <literal>&lt;&lt;</literal> </entry>
5936+
<entry>Is strictly left of?</entry>
5937+
<entry><literal>circle '((0,0),1)' &lt;&lt; circle '((5,0),1)'</literal></entry>
5938+
</row>
5939+
<row>
5940+
<entry> <literal>&gt;&gt;</literal> </entry>
5941+
<entry>Is strictly right of?</entry>
5942+
<entry><literal>circle '((5,0),1)' &gt;&gt; circle '((0,0),1)'</literal></entry>
5943+
</row>
59235944
<row>
59245945
<entry> <literal>&amp;&lt;</literal> </entry>
59255946
<entry>Does not extend to the right of?</entry>
@@ -5931,23 +5952,33 @@ SELECT TIMESTAMP 'now'; -- incorrect for use with DEFAULT
59315952
<entry><literal>box '((0,0),(3,3))' &amp;&gt; box '((0,0),(2,2))'</literal></entry>
59325953
</row>
59335954
<row>
5934-
<entry> <literal>&lt;&lt;</literal> </entry>
5935-
<entry>Is left of?</entry>
5936-
<entry><literal>circle '((0,0),1)' &lt;&lt; circle '((5,0),1)'</literal></entry>
5955+
<entry> <literal>&lt;&lt;|</literal> </entry>
5956+
<entry>Is strictly below?</entry>
5957+
<entry><literal>box '((0,0),(3,3))' &lt;&lt;| box '((3,4),(5,5))'</literal></entry>
59375958
</row>
59385959
<row>
5939-
<entry> <literal>&gt;&gt;</literal> </entry>
5940-
<entry>Is right of?</entry>
5941-
<entry><literal>circle '((5,0),1)' &gt;&gt; circle '((0,0),1)'</literal></entry>
5960+
<entry> <literal>|&gt;&gt;</literal> </entry>
5961+
<entry>Is strictly above?</entry>
5962+
<entry><literal>box '((3,4),(5,5))' |&gt;&gt; box '((0,0),(3,3))'</literal></entry>
5963+
</row>
5964+
<row>
5965+
<entry> <literal>&amp;&lt;|</literal> </entry>
5966+
<entry>Does not extend above?</entry>
5967+
<entry><literal>box '((0,0),(1,1))' &amp;&lt;| box '((0,0),(2,2))'</literal></entry>
5968+
</row>
5969+
<row>
5970+
<entry> <literal>|&amp;&gt;</literal> </entry>
5971+
<entry>Does not extend below?</entry>
5972+
<entry><literal>box '((0,0),(3,3))' |&amp;&gt; box '((0,0),(2,2))'</literal></entry>
59425973
</row>
59435974
<row>
59445975
<entry> <literal>&lt;^</literal> </entry>
5945-
<entry>Is below?</entry>
5976+
<entry>Is below (allows touching)?</entry>
59465977
<entry><literal>circle '((0,0),1)' &lt;^ circle '((0,5),1)'</literal></entry>
59475978
</row>
59485979
<row>
59495980
<entry> <literal>&gt;^</literal> </entry>
5950-
<entry>Is above?</entry>
5981+
<entry>Is above (allows touching)?</entry>
59515982
<entry><literal>circle '((0,5),1)' &gt;^ circle '((0,0),1)'</literal></entry>
59525983
</row>
59535984
<row>

‎doc/src/sgml/indices.sgml

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
<!-- $PostgreSQL: pgsql/doc/src/sgml/indices.sgml,v 1.50 2005/01/22 22:56:36 momjian Exp $ -->
1+
<!-- $PostgreSQL: pgsql/doc/src/sgml/indices.sgml,v 1.51 2005/06/24 20:53:30 tgl Exp $ -->
22

33
<chapter id="indexes">
44
<title id="indexes-title">Indexes</title>
@@ -177,6 +177,11 @@ CREATE INDEX <replaceable>name</replaceable> ON <replaceable>table</replaceable>
177177
<member><literal>&amp;&lt;</literal></member>
178178
<member><literal>&amp;&gt;</literal></member>
179179
<member><literal>&gt;&gt;</literal></member>
180+
<member><literal>&lt;&lt;|</literal></member>
181+
<member><literal>&amp;&lt;|</literal></member>
182+
<member><literal>|&amp;&gt;</literal></member>
183+
<member><literal>|&gt;&gt;</literal></member>
184+
<member><literal>~</literal></member>
180185
<member><literal>@</literal></member>
181186
<member><literal>~=</literal></member>
182187
<member><literal>&amp;&amp;</literal></member>

‎doc/src/sgml/xindex.sgml

Lines changed: 29 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
<!--
2-
$PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.39 2005/02/13 03:04:15 tgl Exp $
2+
$PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.40 2005/06/24 20:53:30 tgl Exp $
33
-->
44

55
<sect1 id="xindex">
@@ -169,8 +169,12 @@ $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.39 2005/02/13 03:04:15 tgl Exp $
169169
</table>
170170

171171
<para>
172-
R-tree indexes express rectangle-containment relationships.
173-
They use eight strategies, shown in <xref linkend="xindex-rtree-strat-table">.
172+
R-tree indexes express relationships in two-dimensional space.
173+
They use twelve strategies, shown in
174+
<xref linkend="xindex-rtree-strat-table">. Four of these are true
175+
two-dimensional tests (overlaps, same, contains, contained by);
176+
four of them consider only the X direction; and the other four
177+
provide the same tests in the Y direction.
174178
</para>
175179

176180
<table tocentry="1" id="xindex-rtree-strat-table">
@@ -184,23 +188,23 @@ $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.39 2005/02/13 03:04:15 tgl Exp $
184188
</thead>
185189
<tbody>
186190
<row>
187-
<entry>left of</entry>
191+
<entry>strictly left of</entry>
188192
<entry>1</entry>
189193
</row>
190194
<row>
191-
<entry>left of or overlapping</entry>
195+
<entry>does not extend to right of</entry>
192196
<entry>2</entry>
193197
</row>
194198
<row>
195-
<entry>overlapping</entry>
199+
<entry>overlaps</entry>
196200
<entry>3</entry>
197201
</row>
198202
<row>
199-
<entry>right of or overlapping</entry>
203+
<entry>does not extend to left of</entry>
200204
<entry>4</entry>
201205
</row>
202206
<row>
203-
<entry>right of</entry>
207+
<entry>strictly right of</entry>
204208
<entry>5</entry>
205209
</row>
206210
<row>
@@ -215,6 +219,22 @@ $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.39 2005/02/13 03:04:15 tgl Exp $
215219
<entry>contained by</entry>
216220
<entry>8</entry>
217221
</row>
222+
<row>
223+
<entry>does not extend above</entry>
224+
<entry>9</entry>
225+
</row>
226+
<row>
227+
<entry>strictly below</entry>
228+
<entry>10</entry>
229+
</row>
230+
<row>
231+
<entry>strictly above</entry>
232+
<entry>11</entry>
233+
</row>
234+
<row>
235+
<entry>does not extend below</entry>
236+
<entry>12</entry>
237+
</row>
218238
</tbody>
219239
</tgroup>
220240
</table>
@@ -398,7 +418,7 @@ $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.39 2005/02/13 03:04:15 tgl Exp $
398418

399419
<para>
400420
Unlike strategy operators, support functions return whichever data
401-
type the particular index method expects, for example in the case
421+
type the particular index method expects; for example in the case
402422
of the comparison function for B-trees, a signed integer.
403423
</para>
404424
</sect2>

‎src/backend/access/rtree/rtstrat.c

Lines changed: 11 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/access/rtree/rtstrat.c,v 1.26 2005/06/24 00:18:52 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/access/rtree/rtstrat.c,v 1.27 2005/06/24 20:53:30 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -37,7 +37,11 @@ static const StrategyNumber RTOperMap[RTNStrategies] = {
3737
RTOverLeftStrategyNumber, /* right */
3838
RTContainsStrategyNumber, /* same */
3939
RTContainsStrategyNumber, /* contains */
40-
RTOverlapStrategyNumber /* contained-by */
40+
RTOverlapStrategyNumber, /* contained-by */
41+
RTAboveStrategyNumber, /* overbelow */
42+
RTOverAboveStrategyNumber, /* below */
43+
RTOverBelowStrategyNumber, /* above */
44+
RTBelowStrategyNumber /* overabove */
4145
};
4246

4347
/*
@@ -52,7 +56,11 @@ static const bool RTNegateMap[RTNStrategies] = {
5256
true, /* right */
5357
false, /* same */
5458
false, /* contains */
55-
false /* contained-by */
59+
false, /* contained-by */
60+
true, /* overbelow */
61+
true, /* below */
62+
true, /* above */
63+
true /* overabove */
5664
};
5765

5866

0 commit comments

Comments
 (0)