1-- 2-- BOX 3-- 4-- 5-- box logic 6-- o 7-- 3 o--|X 8-- | o| 9-- 2 +-+-+ | 10-- | | | | 11-- 1 | o-+-o 12-- | | 13-- 0 +---+ 14-- 15-- 0 1 2 3 16-- 17-- boxes are specified by two points, given by four floats x1,y1,x2,y2 18CREATE TABLE BOX_TBL (f1 box); 19INSERT INTO BOX_TBL (f1) VALUES ('(2.0,2.0,0.0,0.0)'); 20INSERT INTO BOX_TBL (f1) VALUES ('(1.0,1.0,3.0,3.0)'); 21INSERT INTO BOX_TBL (f1) VALUES ('((-8, 2), (-2, -10))'); 22-- degenerate cases where the box is a line or a point 23-- note that lines and points boxes all have zero area 24INSERT INTO BOX_TBL (f1) VALUES ('(2.5, 2.5, 2.5,3.5)'); 25INSERT INTO BOX_TBL (f1) VALUES ('(3.0, 3.0,3.0,3.0)'); 26-- badly formatted box inputs 27INSERT INTO BOX_TBL (f1) VALUES ('(2.3, 4.5)'); 28ERROR: invalid input syntax for type box: "(2.3, 4.5)" 29LINE 1: INSERT INTO BOX_TBL (f1) VALUES ('(2.3, 4.5)'); 30 ^ 31INSERT INTO BOX_TBL (f1) VALUES ('[1, 2, 3, 4)'); 32ERROR: invalid input syntax for type box: "[1, 2, 3, 4)" 33LINE 1: INSERT INTO BOX_TBL (f1) VALUES ('[1, 2, 3, 4)'); 34 ^ 35INSERT INTO BOX_TBL (f1) VALUES ('(1, 2, 3, 4]'); 36ERROR: invalid input syntax for type box: "(1, 2, 3, 4]" 37LINE 1: INSERT INTO BOX_TBL (f1) VALUES ('(1, 2, 3, 4]'); 38 ^ 39INSERT INTO BOX_TBL (f1) VALUES ('(1, 2, 3, 4) x'); 40ERROR: invalid input syntax for type box: "(1, 2, 3, 4) x" 41LINE 1: INSERT INTO BOX_TBL (f1) VALUES ('(1, 2, 3, 4) x'); 42 ^ 43INSERT INTO BOX_TBL (f1) VALUES ('asdfasdf(ad'); 44ERROR: invalid input syntax for type box: "asdfasdf(ad" 45LINE 1: INSERT INTO BOX_TBL (f1) VALUES ('asdfasdf(ad'); 46 ^ 47SELECT * FROM BOX_TBL; 48 f1 49--------------------- 50 (2,2),(0,0) 51 (3,3),(1,1) 52 (-2,2),(-8,-10) 53 (2.5,3.5),(2.5,2.5) 54 (3,3),(3,3) 55(5 rows) 56 57SELECT b.*, area(b.f1) as barea 58 FROM BOX_TBL b; 59 f1 | barea 60---------------------+------- 61 (2,2),(0,0) | 4 62 (3,3),(1,1) | 4 63 (-2,2),(-8,-10) | 72 64 (2.5,3.5),(2.5,2.5) | 0 65 (3,3),(3,3) | 0 66(5 rows) 67 68-- overlap 69SELECT b.f1 70 FROM BOX_TBL b 71 WHERE b.f1 && box '(2.5,2.5,1.0,1.0)'; 72 f1 73--------------------- 74 (2,2),(0,0) 75 (3,3),(1,1) 76 (2.5,3.5),(2.5,2.5) 77(3 rows) 78 79-- left-or-overlap (x only) 80SELECT b1.* 81 FROM BOX_TBL b1 82 WHERE b1.f1 &< box '(2.0,2.0,2.5,2.5)'; 83 f1 84--------------------- 85 (2,2),(0,0) 86 (-2,2),(-8,-10) 87 (2.5,3.5),(2.5,2.5) 88(3 rows) 89 90-- right-or-overlap (x only) 91SELECT b1.* 92 FROM BOX_TBL b1 93 WHERE b1.f1 &> box '(2.0,2.0,2.5,2.5)'; 94 f1 95--------------------- 96 (2.5,3.5),(2.5,2.5) 97 (3,3),(3,3) 98(2 rows) 99 100-- left of 101SELECT b.f1 102 FROM BOX_TBL b 103 WHERE b.f1 << box '(3.0,3.0,5.0,5.0)'; 104 f1 105--------------------- 106 (2,2),(0,0) 107 (-2,2),(-8,-10) 108 (2.5,3.5),(2.5,2.5) 109(3 rows) 110 111-- area <= 112SELECT b.f1 113 FROM BOX_TBL b 114 WHERE b.f1 <= box '(3.0,3.0,5.0,5.0)'; 115 f1 116--------------------- 117 (2,2),(0,0) 118 (3,3),(1,1) 119 (2.5,3.5),(2.5,2.5) 120 (3,3),(3,3) 121(4 rows) 122 123-- area < 124SELECT b.f1 125 FROM BOX_TBL b 126 WHERE b.f1 < box '(3.0,3.0,5.0,5.0)'; 127 f1 128--------------------- 129 (2.5,3.5),(2.5,2.5) 130 (3,3),(3,3) 131(2 rows) 132 133-- area = 134SELECT b.f1 135 FROM BOX_TBL b 136 WHERE b.f1 = box '(3.0,3.0,5.0,5.0)'; 137 f1 138------------- 139 (2,2),(0,0) 140 (3,3),(1,1) 141(2 rows) 142 143-- area > 144SELECT b.f1 145 FROM BOX_TBL b -- zero area 146 WHERE b.f1 > box '(3.5,3.0,4.5,3.0)'; 147 f1 148----------------- 149 (2,2),(0,0) 150 (3,3),(1,1) 151 (-2,2),(-8,-10) 152(3 rows) 153 154-- area >= 155SELECT b.f1 156 FROM BOX_TBL b -- zero area 157 WHERE b.f1 >= box '(3.5,3.0,4.5,3.0)'; 158 f1 159--------------------- 160 (2,2),(0,0) 161 (3,3),(1,1) 162 (-2,2),(-8,-10) 163 (2.5,3.5),(2.5,2.5) 164 (3,3),(3,3) 165(5 rows) 166 167-- right of 168SELECT b.f1 169 FROM BOX_TBL b 170 WHERE box '(3.0,3.0,5.0,5.0)' >> b.f1; 171 f1 172--------------------- 173 (2,2),(0,0) 174 (-2,2),(-8,-10) 175 (2.5,3.5),(2.5,2.5) 176(3 rows) 177 178-- contained in 179SELECT b.f1 180 FROM BOX_TBL b 181 WHERE b.f1 <@ box '(0,0,3,3)'; 182 f1 183------------- 184 (2,2),(0,0) 185 (3,3),(1,1) 186 (3,3),(3,3) 187(3 rows) 188 189-- contains 190SELECT b.f1 191 FROM BOX_TBL b 192 WHERE box '(0,0,3,3)' @> b.f1; 193 f1 194------------- 195 (2,2),(0,0) 196 (3,3),(1,1) 197 (3,3),(3,3) 198(3 rows) 199 200-- box equality 201SELECT b.f1 202 FROM BOX_TBL b 203 WHERE box '(1,1,3,3)' ~= b.f1; 204 f1 205------------- 206 (3,3),(1,1) 207(1 row) 208 209-- center of box, left unary operator 210SELECT @@(b1.f1) AS p 211 FROM BOX_TBL b1; 212 p 213--------- 214 (1,1) 215 (2,2) 216 (-5,-4) 217 (2.5,3) 218 (3,3) 219(5 rows) 220 221-- wholly-contained 222SELECT b1.*, b2.* 223 FROM BOX_TBL b1, BOX_TBL b2 224 WHERE b1.f1 @> b2.f1 and not b1.f1 ~= b2.f1; 225 f1 | f1 226-------------+------------- 227 (3,3),(1,1) | (3,3),(3,3) 228(1 row) 229 230SELECT height(f1), width(f1) FROM BOX_TBL; 231 height | width 232--------+------- 233 2 | 2 234 2 | 2 235 12 | 6 236 1 | 0 237 0 | 0 238(5 rows) 239 240-- 241-- Test the SP-GiST index 242-- 243CREATE TEMPORARY TABLE box_temp (f1 box); 244INSERT INTO box_temp 245 SELECT box(point(i, i), point(i * 2, i * 2)) 246 FROM generate_series(1, 50) AS i; 247CREATE INDEX box_spgist ON box_temp USING spgist (f1); 248INSERT INTO box_temp 249 VALUES (NULL), 250 ('(0,0)(0,100)'), 251 ('(-3,4.3333333333)(40,1)'), 252 ('(0,100)(0,infinity)'), 253 ('(-infinity,0)(0,infinity)'), 254 ('(-infinity,-infinity)(infinity,infinity)'); 255SET enable_seqscan = false; 256SELECT * FROM box_temp WHERE f1 << '(10,20),(30,40)'; 257 f1 258---------------------------- 259 (2,2),(1,1) 260 (4,4),(2,2) 261 (6,6),(3,3) 262 (8,8),(4,4) 263 (0,100),(0,0) 264 (0,Infinity),(0,100) 265 (0,Infinity),(-Infinity,0) 266(7 rows) 267 268EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 << '(10,20),(30,40)'; 269 QUERY PLAN 270---------------------------------------------- 271 Index Only Scan using box_spgist on box_temp 272 Index Cond: (f1 << '(30,40),(10,20)'::box) 273(2 rows) 274 275SELECT * FROM box_temp WHERE f1 &< '(10,4.333334),(5,100)'; 276 f1 277---------------------------- 278 (2,2),(1,1) 279 (4,4),(2,2) 280 (6,6),(3,3) 281 (8,8),(4,4) 282 (10,10),(5,5) 283 (0,100),(0,0) 284 (0,Infinity),(0,100) 285 (0,Infinity),(-Infinity,0) 286(8 rows) 287 288EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 &< '(10,4.333334),(5,100)'; 289 QUERY PLAN 290---------------------------------------------------- 291 Index Only Scan using box_spgist on box_temp 292 Index Cond: (f1 &< '(10,100),(5,4.333334)'::box) 293(2 rows) 294 295SELECT * FROM box_temp WHERE f1 && '(15,20),(25,30)'; 296 f1 297------------------------------------------- 298 (20,20),(10,10) 299 (22,22),(11,11) 300 (24,24),(12,12) 301 (26,26),(13,13) 302 (28,28),(14,14) 303 (30,30),(15,15) 304 (32,32),(16,16) 305 (34,34),(17,17) 306 (36,36),(18,18) 307 (38,38),(19,19) 308 (40,40),(20,20) 309 (42,42),(21,21) 310 (44,44),(22,22) 311 (46,46),(23,23) 312 (48,48),(24,24) 313 (50,50),(25,25) 314 (Infinity,Infinity),(-Infinity,-Infinity) 315(17 rows) 316 317EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 && '(15,20),(25,30)'; 318 QUERY PLAN 319---------------------------------------------- 320 Index Only Scan using box_spgist on box_temp 321 Index Cond: (f1 && '(25,30),(15,20)'::box) 322(2 rows) 323 324SELECT * FROM box_temp WHERE f1 &> '(40,30),(45,50)'; 325 f1 326------------------- 327 (80,80),(40,40) 328 (82,82),(41,41) 329 (84,84),(42,42) 330 (86,86),(43,43) 331 (88,88),(44,44) 332 (90,90),(45,45) 333 (92,92),(46,46) 334 (94,94),(47,47) 335 (96,96),(48,48) 336 (98,98),(49,49) 337 (100,100),(50,50) 338(11 rows) 339 340EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 &> '(40,30),(45,50)'; 341 QUERY PLAN 342---------------------------------------------- 343 Index Only Scan using box_spgist on box_temp 344 Index Cond: (f1 &> '(45,50),(40,30)'::box) 345(2 rows) 346 347SELECT * FROM box_temp WHERE f1 >> '(30,40),(40,30)'; 348 f1 349------------------- 350 (82,82),(41,41) 351 (84,84),(42,42) 352 (86,86),(43,43) 353 (88,88),(44,44) 354 (90,90),(45,45) 355 (92,92),(46,46) 356 (94,94),(47,47) 357 (96,96),(48,48) 358 (98,98),(49,49) 359 (100,100),(50,50) 360(10 rows) 361 362EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 >> '(30,40),(40,30)'; 363 QUERY PLAN 364---------------------------------------------- 365 Index Only Scan using box_spgist on box_temp 366 Index Cond: (f1 >> '(40,40),(30,30)'::box) 367(2 rows) 368 369SELECT * FROM box_temp WHERE f1 <<| '(10,4.33334),(5,100)'; 370 f1 371-------------------------- 372 (2,2),(1,1) 373 (4,4),(2,2) 374 (40,4.3333333333),(-3,1) 375(3 rows) 376 377EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 <<| '(10,4.33334),(5,100)'; 378 QUERY PLAN 379---------------------------------------------------- 380 Index Only Scan using box_spgist on box_temp 381 Index Cond: (f1 <<| '(10,100),(5,4.33334)'::box) 382(2 rows) 383 384SELECT * FROM box_temp WHERE f1 &<| '(10,4.3333334),(5,1)'; 385 f1 386-------------------------- 387 (2,2),(1,1) 388 (4,4),(2,2) 389 (40,4.3333333333),(-3,1) 390(3 rows) 391 392EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 &<| '(10,4.3333334),(5,1)'; 393 QUERY PLAN 394---------------------------------------------------- 395 Index Only Scan using box_spgist on box_temp 396 Index Cond: (f1 &<| '(10,4.3333334),(5,1)'::box) 397(2 rows) 398 399SELECT * FROM box_temp WHERE f1 |&> '(49.99,49.99),(49.99,49.99)'; 400 f1 401---------------------- 402 (100,100),(50,50) 403 (0,Infinity),(0,100) 404(2 rows) 405 406EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 |&> '(49.99,49.99),(49.99,49.99)'; 407 QUERY PLAN 408----------------------------------------------------------- 409 Index Only Scan using box_spgist on box_temp 410 Index Cond: (f1 |&> '(49.99,49.99),(49.99,49.99)'::box) 411(2 rows) 412 413SELECT * FROM box_temp WHERE f1 |>> '(37,38),(39,40)'; 414 f1 415---------------------- 416 (82,82),(41,41) 417 (84,84),(42,42) 418 (86,86),(43,43) 419 (88,88),(44,44) 420 (90,90),(45,45) 421 (92,92),(46,46) 422 (94,94),(47,47) 423 (96,96),(48,48) 424 (98,98),(49,49) 425 (100,100),(50,50) 426 (0,Infinity),(0,100) 427(11 rows) 428 429EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 |>> '(37,38),(39,40)'; 430 QUERY PLAN 431----------------------------------------------- 432 Index Only Scan using box_spgist on box_temp 433 Index Cond: (f1 |>> '(39,40),(37,38)'::box) 434(2 rows) 435 436SELECT * FROM box_temp WHERE f1 @> '(10,11),(15,16)'; 437 f1 438------------------------------------------- 439 (16,16),(8,8) 440 (18,18),(9,9) 441 (20,20),(10,10) 442 (Infinity,Infinity),(-Infinity,-Infinity) 443(4 rows) 444 445EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 @> '(10,11),(15,15)'; 446 QUERY PLAN 447---------------------------------------------- 448 Index Only Scan using box_spgist on box_temp 449 Index Cond: (f1 @> '(15,15),(10,11)'::box) 450(2 rows) 451 452SELECT * FROM box_temp WHERE f1 <@ '(10,15),(30,35)'; 453 f1 454----------------- 455 (30,30),(15,15) 456(1 row) 457 458EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 <@ '(10,15),(30,35)'; 459 QUERY PLAN 460---------------------------------------------- 461 Index Only Scan using box_spgist on box_temp 462 Index Cond: (f1 <@ '(30,35),(10,15)'::box) 463(2 rows) 464 465SELECT * FROM box_temp WHERE f1 ~= '(20,20),(40,40)'; 466 f1 467----------------- 468 (40,40),(20,20) 469(1 row) 470 471EXPLAIN (COSTS OFF) SELECT * FROM box_temp WHERE f1 ~= '(20,20),(40,40)'; 472 QUERY PLAN 473---------------------------------------------- 474 Index Only Scan using box_spgist on box_temp 475 Index Cond: (f1 ~= '(40,40),(20,20)'::box) 476(2 rows) 477 478RESET enable_seqscan; 479DROP INDEX box_spgist; 480-- 481-- Test the SP-GiST index on the larger volume of data 482-- 483CREATE TABLE quad_box_tbl (id int, b box); 484INSERT INTO quad_box_tbl 485 SELECT (x - 1) * 100 + y, box(point(x * 10, y * 10), point(x * 10 + 5, y * 10 + 5)) 486 FROM generate_series(1, 100) x, 487 generate_series(1, 100) y; 488-- insert repeating data to test allTheSame 489INSERT INTO quad_box_tbl 490 SELECT i, '((200, 300),(210, 310))' 491 FROM generate_series(10001, 11000) AS i; 492INSERT INTO quad_box_tbl 493VALUES 494 (11001, NULL), 495 (11002, NULL), 496 (11003, '((-infinity,-infinity),(infinity,infinity))'), 497 (11004, '((-infinity,100),(-infinity,500))'), 498 (11005, '((-infinity,-infinity),(700,infinity))'); 499CREATE INDEX quad_box_tbl_idx ON quad_box_tbl USING spgist(b); 500-- get reference results for ORDER BY distance from seq scan 501SET enable_seqscan = ON; 502SET enable_indexscan = OFF; 503SET enable_bitmapscan = OFF; 504CREATE TABLE quad_box_tbl_ord_seq1 AS 505SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id 506FROM quad_box_tbl; 507CREATE TABLE quad_box_tbl_ord_seq2 AS 508SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id 509FROM quad_box_tbl WHERE b <@ box '((200,300),(500,600))'; 510SET enable_seqscan = OFF; 511SET enable_indexscan = ON; 512SET enable_bitmapscan = ON; 513SELECT count(*) FROM quad_box_tbl WHERE b << box '((100,200),(300,500))'; 514 count 515------- 516 901 517(1 row) 518 519SELECT count(*) FROM quad_box_tbl WHERE b &< box '((100,200),(300,500))'; 520 count 521------- 522 3901 523(1 row) 524 525SELECT count(*) FROM quad_box_tbl WHERE b && box '((100,200),(300,500))'; 526 count 527------- 528 1653 529(1 row) 530 531SELECT count(*) FROM quad_box_tbl WHERE b &> box '((100,200),(300,500))'; 532 count 533------- 534 10100 535(1 row) 536 537SELECT count(*) FROM quad_box_tbl WHERE b >> box '((100,200),(300,500))'; 538 count 539------- 540 7000 541(1 row) 542 543SELECT count(*) FROM quad_box_tbl WHERE b >> box '((100,200),(300,500))'; 544 count 545------- 546 7000 547(1 row) 548 549SELECT count(*) FROM quad_box_tbl WHERE b <<| box '((100,200),(300,500))'; 550 count 551------- 552 1900 553(1 row) 554 555SELECT count(*) FROM quad_box_tbl WHERE b &<| box '((100,200),(300,500))'; 556 count 557------- 558 5901 559(1 row) 560 561SELECT count(*) FROM quad_box_tbl WHERE b |&> box '((100,200),(300,500))'; 562 count 563------- 564 9100 565(1 row) 566 567SELECT count(*) FROM quad_box_tbl WHERE b |>> box '((100,200),(300,500))'; 568 count 569------- 570 5000 571(1 row) 572 573SELECT count(*) FROM quad_box_tbl WHERE b @> box '((201,301),(202,303))'; 574 count 575------- 576 1003 577(1 row) 578 579SELECT count(*) FROM quad_box_tbl WHERE b <@ box '((100,200),(300,500))'; 580 count 581------- 582 1600 583(1 row) 584 585SELECT count(*) FROM quad_box_tbl WHERE b ~= box '((200,300),(205,305))'; 586 count 587------- 588 1 589(1 row) 590 591-- test ORDER BY distance 592SET enable_indexscan = ON; 593SET enable_bitmapscan = OFF; 594EXPLAIN (COSTS OFF) 595SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id 596FROM quad_box_tbl; 597 QUERY PLAN 598--------------------------------------------------------- 599 WindowAgg 600 -> Index Scan using quad_box_tbl_idx on quad_box_tbl 601 Order By: (b <-> '(123,456)'::point) 602(3 rows) 603 604CREATE TEMP TABLE quad_box_tbl_ord_idx1 AS 605SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id 606FROM quad_box_tbl; 607SELECT * 608FROM quad_box_tbl_ord_seq1 seq FULL JOIN quad_box_tbl_ord_idx1 idx 609 ON seq.n = idx.n AND seq.id = idx.id AND 610 (seq.dist = idx.dist OR seq.dist IS NULL AND idx.dist IS NULL) 611WHERE seq.id IS NULL OR idx.id IS NULL; 612 n | dist | id | n | dist | id 613---+------+----+---+------+---- 614(0 rows) 615 616EXPLAIN (COSTS OFF) 617SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id 618FROM quad_box_tbl WHERE b <@ box '((200,300),(500,600))'; 619 QUERY PLAN 620--------------------------------------------------------- 621 WindowAgg 622 -> Index Scan using quad_box_tbl_idx on quad_box_tbl 623 Index Cond: (b <@ '(500,600),(200,300)'::box) 624 Order By: (b <-> '(123,456)'::point) 625(4 rows) 626 627CREATE TEMP TABLE quad_box_tbl_ord_idx2 AS 628SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id 629FROM quad_box_tbl WHERE b <@ box '((200,300),(500,600))'; 630SELECT * 631FROM quad_box_tbl_ord_seq2 seq FULL JOIN quad_box_tbl_ord_idx2 idx 632 ON seq.n = idx.n AND seq.id = idx.id AND 633 (seq.dist = idx.dist OR seq.dist IS NULL AND idx.dist IS NULL) 634WHERE seq.id IS NULL OR idx.id IS NULL; 635 n | dist | id | n | dist | id 636---+------+----+---+------+---- 637(0 rows) 638 639RESET enable_seqscan; 640RESET enable_indexscan; 641RESET enable_bitmapscan; 642