From ff963b393ca93a71d2f398c4c584b322cd351c2c Mon Sep 17 00:00:00 2001 From: Teodor Sigaev Date: Mon, 25 Dec 2017 18:59:38 +0300 Subject: Add polygon opclass for SP-GiST Polygon opclass uses compress method feature of SP-GiST added earlier. For now it's a single operator class which uses this feature. SP-GiST actually indexes a bounding boxes of input polygons, so part of supported operations are lossy. Opclass uses most methods of corresponding opclass over boxes of SP-GiST and treats bounding boxes as point in 4D-space. Bump catalog version. Authors: Nikita Glukhov, Alexander Korotkov with minor editorization by me Reviewed-By: all authors + Darafei Praliaskouski Discussion: https://www.postgresql.org/message-id/flat/54907069.1030506@sigaev.ru --- src/test/regress/expected/polygon.out | 238 +++++++++++++++++++++++++++++ src/test/regress/expected/sanity_check.out | 3 + src/test/regress/sql/polygon.sql | 93 +++++++++++ 3 files changed, 334 insertions(+) (limited to 'src/test') diff --git a/src/test/regress/expected/polygon.out b/src/test/regress/expected/polygon.out index 2361274f9e..4a1f60427a 100644 --- a/src/test/regress/expected/polygon.out +++ b/src/test/regress/expected/polygon.out @@ -227,3 +227,241 @@ 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 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 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 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) + +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 e996640593..ac0fb539e9 100644 --- a/src/test/regress/expected/sanity_check.out +++ b/src/test/regress/expected/sanity_check.out @@ -166,6 +166,9 @@ point_tbl|t polygon_tbl|t quad_box_tbl|t quad_point_tbl|t +quad_poly_tbl|t +quad_poly_tbl_ord_seq1|f +quad_poly_tbl_ord_seq2|f radix_text_tbl|t ramp|f real_city|f diff --git a/src/test/regress/sql/polygon.sql b/src/test/regress/sql/polygon.sql index 7ac8079465..7e8cb08cd8 100644 --- a/src/test/regress/sql/polygon.sql +++ b/src/test/regress/sql/polygon.sql @@ -116,3 +116,96 @@ 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 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 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 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))'; + +RESET enable_seqscan; +RESET enable_indexscan; +RESET enable_bitmapscan; -- cgit v1.2.3