Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit65217de

Browse files
committed
Implement restriction selectivity estimators for <@(spoint, scircle)
This implements restriction selectivity estimation for the <@ @> !<@ !@>family of operators on spoint and scircle. The selectivity is estimatedto be (area of sphere circle) / (4 pi).Queries like `select * from sky where sky.star <@ scircle(const, radius)`will be able to properly estimate if using an index is appropriatedepending on the size of radius.Secondly, a function spoint_dwithin(p1 spoint, p2 spoint, radius float8)is added that effectively returns `p1 <-> p2 <= radius`. But other thanthis two-operator expression, it has GIST index support so the optimizercan rewrite it to either `p1 <@ scircle(p2, radius)` or `p2 <@scircle(p1, radius)`, i.e. it is symmetric in the first two arguments.This allows efficient matching queries without the user having to encodethe join ordering in the query.On PostgreSQL 10/11, the spoint_dwithin function is created, but withoutthe GIST support since that only appeared in PG12.The file expected/selectivity_1.out is used on PG10/11; it has <@flipped around to @> in some plans.
1 parentf7ab4c4 commit65217de

18 files changed

+1132
-10
lines changed

‎Makefile

Lines changed: 17 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -10,8 +10,8 @@ SRC_DIR = $(shell basename $(shell pwd))
1010

1111
MODULE_big = pg_sphere
1212
OBJS = src/sscan.o src/sparse.o src/sbuffer.o src/vector3d.o src/point.o\
13-
src/euler.o src/circle.o src/line.o src/ellipse.o src/polygon.o\
14-
src/path.o src/box.o src/output.o src/gq_cache.o src/gist.o\
13+
src/euler.o src/circle.o src/circle_sel.o src/line.o src/ellipse.o src/polygon.o\
14+
src/path.o src/box.o src/output.o src/gq_cache.o src/gist.osrc/gist_support.o\
1515
src/key.o src/gnomo.o src/epochprop.o src/brin.o
1616

1717
ifneq ($(USE_HEALPIX),0)
@@ -35,11 +35,11 @@ DATA_built = $(RELEASE_SQL) \
3535
DOCS = README.pg_sphere COPYRIGHT.pg_sphere
3636
REGRESS = init tables points euler circle line ellipse poly path box index\
3737
contains_ops contains_ops_compat bounding_box_gist gnomo epochprop\
38-
contains overlaps spoint_brin sbox_brin
38+
contains overlaps spoint_brin sbox_brin selectivity
3939

4040
TESTS = init_test tables points euler circle line ellipse poly path box\
4141
index contains_ops contains_ops_compat bounding_box_gist gnomo\
42-
epochprop contains overlaps spoint_brin sbox_brin
42+
epochprop contains overlaps spoint_brin sbox_brin selectivity
4343

4444
PG_CFLAGS+= -DPGSPHERE_VERSION=$(PGSPHERE_VERSION)
4545
PG_CPPFLAGS+= -DPGSPHERE_VERSION=$(PGSPHERE_VERSION)
@@ -58,7 +58,7 @@ CRUSH_TESTS = init_extended circle_extended
5858
PGS_SQL = pgs_types.sql pgs_point.sql pgs_euler.sql pgs_circle.sql\
5959
pgs_line.sql pgs_ellipse.sql pgs_polygon.sql pgs_path.sql\
6060
pgs_box.sql pgs_contains_ops.sql pgs_contains_ops_compat.sql\
61-
pgs_gist.sql gnomo.sql pgs_brin.sql
61+
pgs_gist.sql gnomo.sql pgs_brin.sql pgs_circle_sel.sql
6262

6363
ifneq ($(USE_HEALPIX),0)
6464
REGRESS += healpix moc moc1 moc100 mocautocast
@@ -102,10 +102,17 @@ healpix_bare/healpix_bare.o : healpix_bare/healpix_bare.c
102102
$(COMPILE.c) -Wno-declaration-after-statement -o$@$^
103103

104104
pg_version :=$(word 2,$(shell$(PG_CONFIG) --version))
105+
has_support_functions =$(if$(filter-out 9.% 10.% 11.%,$(pg_version)),y,n)
105106

106107
crushtest: REGRESS +=$(CRUSH_TESTS)
107108
crushtest: installcheck
108109

110+
ifeq ($(has_support_functions),y)
111+
PGS_SQL += pgs_gist_support.sql
112+
REGRESS += gist_support
113+
TESTS += gist_support
114+
endif
115+
109116
test: pg_sphere.test.sql
110117
$(pg_regress_installcheck) --temp-instance=tmp_check$(REGRESS_OPTS)$(TESTS)
111118

@@ -180,8 +187,11 @@ pg_sphere--1.2.3--1.3.0.sql: pgs_brin.sql.in
180187
pg_sphere--1.3.0--1.3.1.sql:
181188
cat upgrade_scripts/$@.in>$@
182189

183-
pg_sphere--1.3.1--1.3.2.sql:
184-
cat upgrade_scripts/$@.in>$@
190+
ifeq ($(has_support_functions),y)
191+
pg_sphere--1.3.1--1.3.2.sql: pgs_gist_support.sql.in
192+
endif
193+
pg_sphere--1.3.1--1.3.2.sql: pgs_circle_sel.sql.in
194+
cat upgrade_scripts/$@.in$^>$@
185195

186196
# end of local stuff
187197

‎doc/functions.sgm

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -149,6 +149,41 @@
149149
</example>
150150
</sect2>
151151

152+
<sect2 id="func.spoint_dwithin">
153+
<title>
154+
Point-within-distance function
155+
</title>
156+
<para>
157+
The function
158+
</para>
159+
<funcsynopsis>
160+
<funcprototype>
161+
<funcdef><function>spoint_dwithin</function></funcdef>
162+
<paramdef>spoint <parameter>p1</parameter></paramdef>
163+
<paramdef>spoint <parameter>p2</parameter></paramdef>
164+
<paramdef>float8 <parameter>radius</parameter></paramdef>
165+
</funcprototype>
166+
</funcsynopsis>
167+
<para>
168+
returns a boolean value that signifies whether the points
169+
<parameter>p1</parameter> and <parameter>p2</parameter>
170+
lie within distance <parameter>radius</parameter> (in radians) of each other, i.e.
171+
it computes the boolean expression <literal>p1 &lt;-> p2 &lt;= radius</literal>.
172+
On PostgreSQL 12 and later, the function has <literal>GiST</literal>
173+
support and the PostgreSQL optimizer will transform it to either
174+
<literal>p1 &lt;@ scircle(p2, radius)</literal> or
175+
<literal>p2 &lt;@ scircle(p1, radius)</literal> where appropriate.
176+
</para>
177+
<example>
178+
<title>
179+
Efficiently join two tables of points with some fuzziness permitted
180+
</title>
181+
<programlisting>
182+
<![CDATA[sql> SELECT * FROM stars1 JOIN stars2 WHERE spoint_dwithin(stars1.s, stars2.s, 1e-5);]]>
183+
</programlisting>
184+
</example>
185+
</sect2>
186+
152187
</sect1>
153188

154189
<sect1 id="funcs.strans">

‎expected/gist_support.out

Lines changed: 155 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,155 @@
1+
-- spoint_dwithin function selectivity
2+
set jit = off; -- suppress extra planning output
3+
select explain('select * from spoint10k where spoint_dwithin(star, spoint(1,1), 1)');
4+
explain
5+
-----------------------------------------------------------------------------------------------
6+
Bitmap Heap Scan on spoint10k (rows=2298 width=16) (actual rows=3009 loops=1)
7+
Filter: spoint_dwithin(star, '(1 , 1)'::spoint, '1'::double precision)
8+
Rows Removed by Filter: 1560
9+
Heap Blocks: exact=55
10+
-> Bitmap Index Scan on spoint10k_star_idx (rows=2298 width=0) (actual rows=4569 loops=1)
11+
Index Cond: (star <@ '<(1 , 1) , 1>'::scircle)
12+
(6 rows)
13+
14+
select explain('select * from spoint10k where spoint_dwithin(star, spoint(1,1), .1)');
15+
explain
16+
-------------------------------------------------------------------------------------------
17+
Bitmap Heap Scan on spoint10k (rows=25 width=16) (actual rows=29 loops=1)
18+
Filter: spoint_dwithin(star, '(1 , 1)'::spoint, '0.1'::double precision)
19+
Rows Removed by Filter: 19
20+
Heap Blocks: exact=32
21+
-> Bitmap Index Scan on spoint10k_star_idx (rows=25 width=0) (actual rows=48 loops=1)
22+
Index Cond: (star <@ '<(1 , 1) , 0.1>'::scircle)
23+
(6 rows)
24+
25+
select explain('select * from spoint10k where spoint_dwithin(star, spoint(1,1), .01)');
26+
explain
27+
---------------------------------------------------------------------------------------------
28+
Index Scan using spoint10k_star_idx on spoint10k (rows=1 width=16) (actual rows=1 loops=1)
29+
Index Cond: (star <@ '<(1 , 1) , 0.01>'::scircle)
30+
(2 rows)
31+
32+
select explain('select * from spoint10k where spoint_dwithin(spoint(1,1), star, 1)');
33+
explain
34+
-----------------------------------------------------------------------------------------------
35+
Bitmap Heap Scan on spoint10k (rows=2298 width=16) (actual rows=3009 loops=1)
36+
Filter: spoint_dwithin('(1 , 1)'::spoint, star, '1'::double precision)
37+
Rows Removed by Filter: 1560
38+
Heap Blocks: exact=55
39+
-> Bitmap Index Scan on spoint10k_star_idx (rows=2298 width=0) (actual rows=4569 loops=1)
40+
Index Cond: (star <@ '<(1 , 1) , 1>'::scircle)
41+
(6 rows)
42+
43+
select explain('select * from spoint10k where spoint_dwithin(spoint(1,1), star, .1)');
44+
explain
45+
-------------------------------------------------------------------------------------------
46+
Bitmap Heap Scan on spoint10k (rows=25 width=16) (actual rows=29 loops=1)
47+
Filter: spoint_dwithin('(1 , 1)'::spoint, star, '0.1'::double precision)
48+
Rows Removed by Filter: 19
49+
Heap Blocks: exact=32
50+
-> Bitmap Index Scan on spoint10k_star_idx (rows=25 width=0) (actual rows=48 loops=1)
51+
Index Cond: (star <@ '<(1 , 1) , 0.1>'::scircle)
52+
(6 rows)
53+
54+
select explain('select * from spoint10k where spoint_dwithin(spoint(1,1), star, .01)');
55+
explain
56+
---------------------------------------------------------------------------------------------
57+
Index Scan using spoint10k_star_idx on spoint10k (rows=1 width=16) (actual rows=1 loops=1)
58+
Index Cond: (star <@ '<(1 , 1) , 0.01>'::scircle)
59+
(2 rows)
60+
61+
select explain('select * from spoint10k a join spoint10k b on spoint_dwithin(a.star, b.star, 1)', do_analyze := 'false');
62+
explain
63+
---------------------------------------------------------------------------------------
64+
Nested Loop (rows=22984885 width=32)
65+
-> Seq Scan on spoint10k a (rows=10000 width=16)
66+
-> Index Scan using spoint10k_star_idx on spoint10k b (rows=2298 width=16)
67+
Index Cond: (star OPERATOR(public.<@) scircle(a.star, '1'::double precision))
68+
(4 rows)
69+
70+
select explain('select * from spoint10k a join spoint10k b on spoint_dwithin(a.star, b.star, .1)');
71+
explain
72+
-----------------------------------------------------------------------------------------------------------
73+
Nested Loop (rows=249792 width=32) (actual rows=505342 loops=1)
74+
-> Seq Scan on spoint10k a (rows=10000 width=16) (actual rows=10000 loops=1)
75+
-> Index Scan using spoint10k_star_idx on spoint10k b (rows=25 width=16) (actual rows=51 loops=10000)
76+
Index Cond: (star OPERATOR(public.<@) scircle(a.star, '0.1'::double precision))
77+
Rows Removed by Index Recheck: 31
78+
(5 rows)
79+
80+
select explain('select * from spoint10k a join spoint10k b on spoint_dwithin(a.star, b.star, .01)');
81+
explain
82+
---------------------------------------------------------------------------------------------------------
83+
Nested Loop (rows=2500 width=32) (actual rows=17614 loops=1)
84+
-> Seq Scan on spoint10k a (rows=10000 width=16) (actual rows=10000 loops=1)
85+
-> Index Scan using spoint10k_star_idx on spoint10k b (rows=1 width=16) (actual rows=2 loops=10000)
86+
Index Cond: (star OPERATOR(public.<@) scircle(a.star, '0.01'::double precision))
87+
Rows Removed by Index Recheck: 1
88+
(5 rows)
89+
90+
-- spoint_dwithin is symmetric in the first two arguments
91+
select explain('select * from spoint10k a join spoint10k b on spoint_dwithin(a.star, b.star, .01)
92+
where spoint_dwithin(a.star, spoint(1,1), .1)');
93+
explain
94+
------------------------------------------------------------------------------------------------------
95+
Nested Loop (rows=6 width=32) (actual rows=33 loops=1)
96+
-> Bitmap Heap Scan on spoint10k a (rows=25 width=16) (actual rows=29 loops=1)
97+
Filter: spoint_dwithin(star, '(1 , 1)'::spoint, '0.1'::double precision)
98+
Rows Removed by Filter: 19
99+
Heap Blocks: exact=32
100+
-> Bitmap Index Scan on spoint10k_star_idx (rows=25 width=0) (actual rows=48 loops=1)
101+
Index Cond: (star <@ '<(1 , 1) , 0.1>'::scircle)
102+
-> Index Scan using spoint10k_star_idx on spoint10k b (rows=1 width=16) (actual rows=1 loops=29)
103+
Index Cond: (star OPERATOR(public.<@) scircle(a.star, '0.01'::double precision))
104+
Rows Removed by Index Recheck: 0
105+
(10 rows)
106+
107+
select explain('select * from spoint10k a join spoint10k b on spoint_dwithin(b.star, a.star, .01)
108+
where spoint_dwithin(a.star, spoint(1,1), .1)');
109+
explain
110+
------------------------------------------------------------------------------------------------------
111+
Nested Loop (rows=6 width=32) (actual rows=33 loops=1)
112+
-> Bitmap Heap Scan on spoint10k a (rows=25 width=16) (actual rows=29 loops=1)
113+
Filter: spoint_dwithin(star, '(1 , 1)'::spoint, '0.1'::double precision)
114+
Rows Removed by Filter: 19
115+
Heap Blocks: exact=32
116+
-> Bitmap Index Scan on spoint10k_star_idx (rows=25 width=0) (actual rows=48 loops=1)
117+
Index Cond: (star <@ '<(1 , 1) , 0.1>'::scircle)
118+
-> Index Scan using spoint10k_star_idx on spoint10k b (rows=1 width=16) (actual rows=1 loops=29)
119+
Index Cond: (star OPERATOR(public.<@) scircle(a.star, '0.01'::double precision))
120+
Rows Removed by Index Recheck: 0
121+
(10 rows)
122+
123+
-- both sides indexable, check if the planner figures out the better choice
124+
select explain('select * from spoint10k a join spoint10k b on spoint_dwithin(a.star, b.star, .01)
125+
where spoint_dwithin(a.star, spoint(1,1), .1) and spoint_dwithin(b.star, spoint(1,1), .05)');
126+
explain
127+
-------------------------------------------------------------------------------------------------------------------------------------
128+
Nested Loop (rows=1 width=32) (actual rows=16 loops=1)
129+
-> Bitmap Heap Scan on spoint10k b (rows=6 width=16) (actual rows=12 loops=1)
130+
Filter: spoint_dwithin(star, '(1 , 1)'::spoint, '0.05'::double precision)
131+
Rows Removed by Filter: 4
132+
Heap Blocks: exact=14
133+
-> Bitmap Index Scan on spoint10k_star_idx (rows=6 width=0) (actual rows=16 loops=1)
134+
Index Cond: (star <@ '<(1 , 1) , 0.05>'::scircle)
135+
-> Index Scan using spoint10k_star_idx on spoint10k a (rows=1 width=16) (actual rows=1 loops=12)
136+
Index Cond: ((star OPERATOR(public.<@) scircle(b.star, '0.01'::double precision)) AND (star <@ '<(1 , 1) , 0.1>'::scircle))
137+
Rows Removed by Index Recheck: 0
138+
(10 rows)
139+
140+
select explain('select * from spoint10k a join spoint10k b on spoint_dwithin(a.star, b.star, .01)
141+
where spoint_dwithin(a.star, spoint(1,1), .05) and spoint_dwithin(b.star, spoint(1,1), .1)');
142+
explain
143+
-------------------------------------------------------------------------------------------------------------------------------------
144+
Nested Loop (rows=1 width=32) (actual rows=16 loops=1)
145+
-> Bitmap Heap Scan on spoint10k a (rows=6 width=16) (actual rows=12 loops=1)
146+
Filter: spoint_dwithin(star, '(1 , 1)'::spoint, '0.05'::double precision)
147+
Rows Removed by Filter: 4
148+
Heap Blocks: exact=14
149+
-> Bitmap Index Scan on spoint10k_star_idx (rows=6 width=0) (actual rows=16 loops=1)
150+
Index Cond: (star <@ '<(1 , 1) , 0.05>'::scircle)
151+
-> Index Scan using spoint10k_star_idx on spoint10k b (rows=1 width=16) (actual rows=1 loops=12)
152+
Index Cond: ((star OPERATOR(public.<@) scircle(a.star, '0.01'::double precision)) AND (star <@ '<(1 , 1) , 0.1>'::scircle))
153+
Rows Removed by Index Recheck: 0
154+
(10 rows)
155+

‎expected/index.out

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,7 @@ SELECT count(*) FROM spheretmp4 WHERE l && scircle '<(1,1),0.3>';
5555

5656
-- create idx
5757
CREATE TABLE spheretmp1b AS TABLE spheretmp1;
58+
ANALYZE spheretmp1;
5859
CREATE INDEX aaaidx ON spheretmp1 USING gist ( p );
5960
CREATE INDEX spoint3_idx ON spheretmp1b USING gist (p spoint3);
6061
CREATE INDEX bbbidx ON spheretmp2 USING gist ( c );
@@ -165,7 +166,6 @@ EXPLAIN (COSTS OFF) SELECT count(*) FROM spheretmp1b WHERE p = spoint '(3.09 , 1
165166
4
166167
(1 row)
167168

168-
SET enable_bitmapscan = ON;
169169
SET enable_indexonlyscan = OFF;
170170
EXPLAIN (COSTS OFF) SELECT count(*) FROM spheretmp1b WHERE p <@ scircle '<(1,1),0.3>';
171171
QUERY PLAN

‎expected/points.out

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -666,3 +666,19 @@ SELECT '( 0h 2m 30s , -90d 0m 0s)'::spoint<->'( 12h 2m 30s , -90d 0m 0s)'::spoin
666666
0
667667
(1 row)
668668

669+
-- spoint_dwithin function ----------
670+
SELECT a, b, radius, a <-> b AS "<->", spoint_dwithin(a, b, radius)
671+
FROM (VALUES
672+
('(0, 0)'::spoint, '(0, 0)'::spoint, 0),
673+
('(0, 0)', '(0, 1)', 1),
674+
('(0, 0)', '(0.1, 0.1)', 0.14),
675+
('(0, 0)', '(0.1, 0.1)', 0.15)
676+
) sub (a, b, radius);
677+
a | b | radius | <-> | spoint_dwithin
678+
---------+-------------+--------+-----------------+----------------
679+
(0 , 0) | (0 , 0) | 0 | 0 | t
680+
(0 , 0) | (0 , 1) | 1 | 1 | t
681+
(0 , 0) | (0.1 , 0.1) | 0.14 | 0.1413032986961 | f
682+
(0 , 0) | (0.1 , 0.1) | 0.15 | 0.1413032986961 | t
683+
(4 rows)
684+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp