-- -- BOX -- -- -- box logic -- o -- 3 o--|X -- | o| -- 2 +-+-+ | -- | | | | -- 1 | o-+-o -- | | -- 0 +---+ -- -- 0 1 2 3 -- -- boxes are specified by two points, given by four floats x1,y1,x2,y2 CREATE TABLE BOX_TBL (f1 box); INSERT INTO BOX_TBL (f1) VALUES ('(2.0,2.0,0.0,0.0)'); INSERT INTO BOX_TBL (f1) VALUES ('(1.0,1.0,3.0,3.0)'); INSERT INTO BOX_TBL (f1) VALUES ('((-8, 2), (-2, -10))'); -- degenerate cases where the box is a line or a point -- note that lines and points boxes all have zero area INSERT INTO BOX_TBL (f1) VALUES ('(2.5, 2.5, 2.5,3.5)'); INSERT INTO BOX_TBL (f1) VALUES ('(3.0, 3.0,3.0,3.0)'); -- badly formatted box inputs INSERT INTO BOX_TBL (f1) VALUES ('(2.3, 4.5)'); ERROR: invalid input syntax for type box: "(2.3, 4.5)" LINE 1: INSERT INTO BOX_TBL (f1) VALUES ('(2.3, 4.5)'); ^ INSERT INTO BOX_TBL (f1) VALUES ('[1, 2, 3, 4)'); ERROR: invalid input syntax for type box: "[1, 2, 3, 4)" LINE 1: INSERT INTO BOX_TBL (f1) VALUES ('[1, 2, 3, 4)'); ^ INSERT INTO BOX_TBL (f1) VALUES ('(1, 2, 3, 4]'); ERROR: invalid input syntax for type box: "(1, 2, 3, 4]" LINE 1: INSERT INTO BOX_TBL (f1) VALUES ('(1, 2, 3, 4]'); ^ INSERT INTO BOX_TBL (f1) VALUES ('(1, 2, 3, 4) x'); ERROR: invalid input syntax for type box: "(1, 2, 3, 4) x" LINE 1: INSERT INTO BOX_TBL (f1) VALUES ('(1, 2, 3, 4) x'); ^ INSERT INTO BOX_TBL (f1) VALUES ('asdfasdf(ad'); ERROR: invalid input syntax for type box: "asdfasdf(ad" LINE 1: INSERT INTO BOX_TBL (f1) VALUES ('asdfasdf(ad'); ^ SELECT * FROM BOX_TBL; f1 --------------------- (2,2),(0,0) (3,3),(1,1) (-2,2),(-8,-10) (2.5,3.5),(2.5,2.5) (3,3),(3,3) (5 rows) SELECT b.*, area(b.f1) as barea FROM BOX_TBL b; f1 | barea ---------------------+------- (2,2),(0,0) | 4 (3,3),(1,1) | 4 (-2,2),(-8,-10) | 72 (2.5,3.5),(2.5,2.5) | 0 (3,3),(3,3) | 0 (5 rows) -- overlap SELECT b.f1 FROM BOX_TBL b WHERE b.f1 && box '(2.5,2.5,1.0,1.0)'; f1 --------------------- (2,2),(0,0) (3,3),(1,1) (2.5,3.5),(2.5,2.5) (3 rows) -- left-or-overlap (x only) SELECT b1.* FROM BOX_TBL b1 WHERE b1.f1 &< box '(2.0,2.0,2.5,2.5)'; f1 --------------------- (2,2),(0,0) (-2,2),(-8,-10) (2.5,3.5),(2.5,2.5) (3 rows) -- right-or-overlap (x only) SELECT b1.* FROM BOX_TBL b1 WHERE b1.f1 &> box '(2.0,2.0,2.5,2.5)'; f1 --------------------- (2.5,3.5),(2.5,2.5) (3,3),(3,3) (2 rows) -- left of SELECT b.f1 FROM BOX_TBL b WHERE b.f1 << box '(3.0,3.0,5.0,5.0)'; f1 --------------------- (2,2),(0,0) (-2,2),(-8,-10) (2.5,3.5),(2.5,2.5) (3 rows) -- area <= SELECT b.f1 FROM BOX_TBL b WHERE b.f1 <= box '(3.0,3.0,5.0,5.0)'; f1 --------------------- (2,2),(0,0) (3,3),(1,1) (2.5,3.5),(2.5,2.5) (3,3),(3,3) (4 rows) -- area < SELECT b.f1 FROM BOX_TBL b WHERE b.f1 < box '(3.0,3.0,5.0,5.0)'; f1 --------------------- (2.5,3.5),(2.5,2.5) (3,3),(3,3) (2 rows) -- area = SELECT b.f1 FROM BOX_TBL b WHERE b.f1 = box '(3.0,3.0,5.0,5.0)'; f1 ------------- (2,2),(0,0) (3,3),(1,1) (2 rows) -- area > SELECT b.f1 FROM BOX_TBL b -- zero area WHERE b.f1 > box '(3.5,3.0,4.5,3.0)'; f1 ----------------- (2,2),(0,0) (3,3),(1,1) (-2,2),(-8,-10) (3 rows) -- area >= SELECT b.f1 FROM BOX_TBL b -- zero area WHERE b.f1 >= box '(3.5,3.0,4.5,3.0)'; f1 --------------------- (2,2),(0,0) (3,3),(1,1) (-2,2),(-8,-10) (2.5,3.5),(2.5,2.5) (3,3),(3,3) (5 rows) -- right of SELECT b.f1 FROM BOX_TBL b WHERE box '(3.0,3.0,5.0,5.0)' >> b.f1; f1 --------------------- (2,2),(0,0) (-2,2),(-8,-10) (2.5,3.5),(2.5,2.5) (3 rows) -- contained in SELECT b.f1 FROM BOX_TBL b WHERE b.f1 <@ box '(0,0,3,3)'; f1 ------------- (2,2),(0,0) (3,3),(1,1) (3,3),(3,3) (3 rows) -- contains SELECT b.f1 FROM BOX_TBL b WHERE box '(0,0,3,3)' @> b.f1; f1 ------------- (2,2),(0,0) (3,3),(1,1) (3,3),(3,3) (3 rows) -- box equality SELECT b.f1 FROM BOX_TBL b WHERE box '(1,1,3,3)' ~= b.f1; f1 ------------- (3,3),(1,1) (1 row) -- center of box, left unary operator SELECT @@(b1.f1) AS p FROM BOX_TBL b1; p --------- (1,1) (2,2) (-5,-4) (2.5,3) (3,3) (5 rows) -- wholly-contained SELECT b1.*, b2.* FROM BOX_TBL b1, BOX_TBL b2 WHERE b1.f1 @> b2.f1 and not b1.f1 ~= b2.f1; f1 | f1 -------------+------------- (3,3),(1,1) | (3,3),(3,3) (1 row) SELECT height(f1), width(f1) FROM BOX_TBL; height | width --------+------- 2 | 2 2 | 2 12 | 6 1 | 0 0 | 0 (5 rows) -- -- Test the SP-GiST index -- CREATE TEMPORARY TABLE box_temp (f1 box); INSERT INTO box_temp SELECT box(point(i, i), point(i * 2, i * 2)) FROM generate_series(1, 50) AS i; CREATE INDEX box_spgist ON box_temp USING spgist (f1); INSERT INTO box_temp VALUES (NULL), ('(0,0)(0,100)'), ('(-3,4.3333333333)(40,1)'), ('(0,100)(0,infinity)'), ('(-infinity,0)(0,infinity)'), ('(-infinity,-infinity)(infinity,infinity)'); SET enable_seqscan = false; SELECT * FROM box_temp WHERE f1 << '(10,20),(30,40)'; f1 ---------------------------- (2,2),(1,1) (4,4),(2,2) (6,6),(3,3) (8,8),(4,4) (0,100),(0,0) (0,Infinity),(0,100) (0,Infinity),(-Infinity,0) (7 rows) EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 << '(10,20),(30,40)'; QUERY PLAN ---------------------------------------------- Index Only Scan using box_spgist on box_temp Index Cond: (f1 << '(30,40),(10,20)'::box) (2 rows) SELECT * FROM box_temp WHERE f1 &< '(10,4.333334),(5,100)'; f1 ---------------------------- (2,2),(1,1) (4,4),(2,2) (6,6),(3,3) (8,8),(4,4) (10,10),(5,5) (0,100),(0,0) (0,Infinity),(0,100) (0,Infinity),(-Infinity,0) (8 rows) EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 &< '(10,4.333334),(5,100)'; QUERY PLAN ---------------------------------------------------- Index Only Scan using box_spgist on box_temp Index Cond: (f1 &< '(10,100),(5,4.333334)'::box) (2 rows) SELECT * FROM box_temp WHERE f1 && '(15,20),(25,30)'; f1 ------------------------------------------- (20,20),(10,10) (22,22),(11,11) (24,24),(12,12) (26,26),(13,13) (28,28),(14,14) (30,30),(15,15) (32,32),(16,16) (34,34),(17,17) (36,36),(18,18) (38,38),(19,19) (40,40),(20,20) (42,42),(21,21) (44,44),(22,22) (46,46),(23,23) (48,48),(24,24) (50,50),(25,25) (Infinity,Infinity),(-Infinity,-Infinity) (17 rows) EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 && '(15,20),(25,30)'; QUERY PLAN ---------------------------------------------- Index Only Scan using box_spgist on box_temp Index Cond: (f1 && '(25,30),(15,20)'::box) (2 rows) SELECT * FROM box_temp WHERE f1 &> '(40,30),(45,50)'; f1 ------------------- (80,80),(40,40) (82,82),(41,41) (84,84),(42,42) (86,86),(43,43) (88,88),(44,44) (90,90),(45,45) (92,92),(46,46) (94,94),(47,47) (96,96),(48,48) (98,98),(49,49) (100,100),(50,50) (11 rows) EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 &> '(40,30),(45,50)'; QUERY PLAN ---------------------------------------------- Index Only Scan using box_spgist on box_temp Index Cond: (f1 &> '(45,50),(40,30)'::box) (2 rows) SELECT * FROM box_temp WHERE f1 >> '(30,40),(40,30)'; f1 ------------------- (82,82),(41,41) (84,84),(42,42) (86,86),(43,43) (88,88),(44,44) (90,90),(45,45) (92,92),(46,46) (94,94),(47,47) (96,96),(48,48) (98,98),(49,49) (100,100),(50,50) (10 rows) EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 >> '(30,40),(40,30)'; QUERY PLAN ---------------------------------------------- Index Only Scan using box_spgist on box_temp Index Cond: (f1 >> '(40,40),(30,30)'::box) (2 rows) SELECT * FROM box_temp WHERE f1 <<| '(10,4.33334),(5,100)'; f1 -------------------------- (2,2),(1,1) (4,4),(2,2) (40,4.3333333333),(-3,1) (3 rows) EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 <<| '(10,4.33334),(5,100)'; QUERY PLAN ---------------------------------------------------- Index Only Scan using box_spgist on box_temp Index Cond: (f1 <<| '(10,100),(5,4.33334)'::box) (2 rows) SELECT * FROM box_temp WHERE f1 &<| '(10,4.3333334),(5,1)'; f1 -------------------------- (2,2),(1,1) (4,4),(2,2) (40,4.3333333333),(-3,1) (3 rows) EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 &<| '(10,4.3333334),(5,1)'; QUERY PLAN ---------------------------------------------------- Index Only Scan using box_spgist on box_temp Index Cond: (f1 &<| '(10,4.3333334),(5,1)'::box) (2 rows) SELECT * FROM box_temp WHERE f1 |&> '(49.99,49.99),(49.99,49.99)'; f1 ---------------------- (100,100),(50,50) (0,Infinity),(0,100) (2 rows) EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 |&> '(49.99,49.99),(49.99,49.99)'; QUERY PLAN ----------------------------------------------------------- Index Only Scan using box_spgist on box_temp Index Cond: (f1 |&> '(49.99,49.99),(49.99,49.99)'::box) (2 rows) SELECT * FROM box_temp WHERE f1 |>> '(37,38),(39,40)'; f1 ---------------------- (82,82),(41,41) (84,84),(42,42) (86,86),(43,43) (88,88),(44,44) (90,90),(45,45) (92,92),(46,46) (94,94),(47,47) (96,96),(48,48) (98,98),(49,49) (100,100),(50,50) (0,Infinity),(0,100) (11 rows) EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 |>> '(37,38),(39,40)'; QUERY PLAN ----------------------------------------------- Index Only Scan using box_spgist on box_temp Index Cond: (f1 |>> '(39,40),(37,38)'::box) (2 rows) SELECT * FROM box_temp WHERE f1 @> '(10,11),(15,16)'; f1 ------------------------------------------- (16,16),(8,8) (18,18),(9,9) (20,20),(10,10) (Infinity,Infinity),(-Infinity,-Infinity) (4 rows) EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 @> '(10,11),(15,15)'; QUERY PLAN ---------------------------------------------- Index Only Scan using box_spgist on box_temp Index Cond: (f1 @> '(15,15),(10,11)'::box) (2 rows) SELECT * FROM box_temp WHERE f1 <@ '(10,15),(30,35)'; f1 ----------------- (30,30),(15,15) (1 row) EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 <@ '(10,15),(30,35)'; QUERY PLAN ---------------------------------------------- Index Only Scan using box_spgist on box_temp Index Cond: (f1 <@ '(30,35),(10,15)'::box) (2 rows) SELECT * FROM box_temp WHERE f1 ~= '(20,20),(40,40)'; f1 ----------------- (40,40),(20,20) (1 row) EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 ~= '(20,20),(40,40)'; QUERY PLAN ---------------------------------------------- Index Only Scan using box_spgist on box_temp Index Cond: (f1 ~= '(40,40),(20,20)'::box) (2 rows) RESET enable_seqscan; DROP INDEX box_spgist; -- -- Test the SP-GiST index on the larger volume of data -- CREATE TABLE quad_box_tbl (id int, b box); INSERT INTO quad_box_tbl SELECT (x - 1) * 100 + y, box(point(x * 10, y * 10), point(x * 10 + 5, y * 10 + 5)) FROM generate_series(1, 100) x, generate_series(1, 100) y; -- insert repeating data to test allTheSame INSERT INTO quad_box_tbl SELECT i, '((200, 300),(210, 310))' FROM generate_series(10001, 11000) AS i; INSERT INTO quad_box_tbl VALUES (11001, NULL), (11002, NULL), (11003, '((-infinity,-infinity),(infinity,infinity))'), (11004, '((-infinity,100),(-infinity,500))'), (11005, '((-infinity,-infinity),(700,infinity))'); CREATE INDEX quad_box_tbl_idx ON quad_box_tbl USING spgist(b); -- 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_box_tbl_ord_seq1 AS SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id FROM quad_box_tbl; CREATE TABLE quad_box_tbl_ord_seq2 AS SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id FROM quad_box_tbl WHERE b <@ box '((200,300),(500,600))'; SET enable_seqscan = OFF; SET enable_indexscan = ON; SET enable_bitmapscan = ON; SELECT count(*) FROM quad_box_tbl WHERE b << box '((100,200),(300,500))'; count ------- 901 (1 row) SELECT count(*) FROM quad_box_tbl WHERE b &< box '((100,200),(300,500))'; count ------- 3901 (1 row) SELECT count(*) FROM quad_box_tbl WHERE b && box '((100,200),(300,500))'; count ------- 1653 (1 row) SELECT count(*) FROM quad_box_tbl WHERE b &> box '((100,200),(300,500))'; count ------- 10100 (1 row) SELECT count(*) FROM quad_box_tbl WHERE b >> box '((100,200),(300,500))'; count ------- 7000 (1 row) SELECT count(*) FROM quad_box_tbl WHERE b >> box '((100,200),(300,500))'; count ------- 7000 (1 row) SELECT count(*) FROM quad_box_tbl WHERE b <<| box '((100,200),(300,500))'; count ------- 1900 (1 row) SELECT count(*) FROM quad_box_tbl WHERE b &<| box '((100,200),(300,500))'; count ------- 5901 (1 row) SELECT count(*) FROM quad_box_tbl WHERE b |&> box '((100,200),(300,500))'; count ------- 9100 (1 row) SELECT count(*) FROM quad_box_tbl WHERE b |>> box '((100,200),(300,500))'; count ------- 5000 (1 row) SELECT count(*) FROM quad_box_tbl WHERE b @> box '((201,301),(202,303))'; count ------- 1003 (1 row) SELECT count(*) FROM quad_box_tbl WHERE b <@ box '((100,200),(300,500))'; count ------- 1600 (1 row) SELECT count(*) FROM quad_box_tbl WHERE b ~= box '((200,300),(205,305))'; count ------- 1 (1 row) -- test ORDER BY distance SET enable_indexscan = ON; SET enable_bitmapscan = OFF; EXPLAIN (COSTS OFF) SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id FROM quad_box_tbl; QUERY PLAN --------------------------------------------------------- WindowAgg -> Index Scan using quad_box_tbl_idx on quad_box_tbl Order By: (b <-> '(123,456)'::point) (3 rows) CREATE TEMP TABLE quad_box_tbl_ord_idx1 AS SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id FROM quad_box_tbl; SELECT * FROM quad_box_tbl_ord_seq1 seq FULL JOIN quad_box_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 b <-> point '123,456') n, b <-> point '123,456' dist, id FROM quad_box_tbl WHERE b <@ box '((200,300),(500,600))'; QUERY PLAN --------------------------------------------------------- WindowAgg -> Index Scan using quad_box_tbl_idx on quad_box_tbl Index Cond: (b <@ '(500,600),(200,300)'::box) Order By: (b <-> '(123,456)'::point) (4 rows) CREATE TEMP TABLE quad_box_tbl_ord_idx2 AS SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id FROM quad_box_tbl WHERE b <@ box '((200,300),(500,600))'; SELECT * FROM quad_box_tbl_ord_seq2 seq FULL JOIN quad_box_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;