granicus.if.org Git - postgresql/blob - src/backend/utils/adt/geo_spgist.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * geo_spgist.c
   4  *        SP-GiST implementation of 4-dimensional quad tree over boxes
   5  *
   6  * This module provides SP-GiST implementation for boxes using quad tree
   7  * analogy in 4-dimensional space.  SP-GiST doesn't allow indexing of
   8  * overlapping objects.  We are making 2D objects never-overlapping in
   9  * 4D space.  This technique has some benefits compared to traditional
  10  * R-Tree which is implemented as GiST.  The performance tests reveal
  11  * that this technique especially beneficial with too much overlapping
  12  * objects, so called "spaghetti data".
  13  *
  14  * Unlike the original quad tree, we are splitting the tree into 16
  15  * quadrants in 4D space.  It is easier to imagine it as splitting space
  16  * two times into 4:
  17  *
  18  *                              |          |
  19  *                              |          |
  20  *                              | -----+-----
  21  *                              |          |
  22  *                              |          |
  23  * -------------+-------------
  24  *                              |
  25  *                              |
  26  *                              |
  27  *                              |
  28  *                              |
  29  *
  30  * We are using box datatype as the prefix, but we are treating them
  31  * as points in 4-dimensional space, because 2D boxes are not enough
  32  * to represent the quadrant boundaries in 4D space.  They however are
  33  * sufficient to point out the additional boundaries of the next
  34  * quadrant.
  35  *
  36  * We are using traversal values provided by SP-GiST to calculate and
  37  * to store the bounds of the quadrants, while traversing into the tree.
  38  * Traversal value has all the boundaries in the 4D space, and is is
  39  * capable of transferring the required boundaries to the following
  40  * traversal values.  In conclusion, three things are necessary
  41  * to calculate the next traversal value:
  42  *
  43  *      (1) the traversal value of the parent
  44  *      (2) the quadrant of the current node
  45  *      (3) the prefix of the current node
  46  *
  47  * If we visualize them on our simplified drawing (see the drawing above);
  48  * transferred boundaries of (1) would be the outer axis, relevant part
  49  * of (2) would be the up right part of the other axis, and (3) would be
  50  * the inner axis.
  51  *
  52  * For example, consider the case of overlapping.  When recursion
  53  * descends deeper and deeper down the tree, all quadrants in
  54  * the current node will be checked for overlapping.  The boundaries
  55  * will be re-calculated for all quadrants.  Overlap check answers
  56  * the question: can any box from this quadrant overlap with the given
  57  * box?  If yes, then this quadrant will be walked.  If no, then this
  58  * quadrant will be skipped.
  59  *
  60  * This method provides restrictions for minimum and maximum values of
  61  * every dimension of every corner of the box on every level of the tree
  62  * except the root.  For the root node, we are setting the boundaries
  63  * that we don't yet have as infinity.
  64  *
  65  * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
  66  * Portions Copyright (c) 1994, Regents of the University of California
  67  *
  68  * IDENTIFICATION
  69  *                      src/backend/utils/adt/geo_spgist.c
  70  *
  71  *-------------------------------------------------------------------------
  72  */
  73
  74 #include "postgres.h"
  75
  76 #include "access/spgist.h"
  77 #include "access/stratnum.h"
  78 #include "catalog/pg_type.h"
  79 #include "utils/builtins.h"
  80 #include "utils/geo_decls.h"
  81
  82 /*
  83  * Comparator for qsort
  84  *
  85  * We don't need to use the floating point macros in here, because this
  86  * is going only going to be used in a place to effect the performance
  87  * of the index, not the correctness.
  88  */
  89 static int
  90 compareDoubles(const void *a, const void *b)
  91 {
  92         double          x = *(double *) a;
  93         double          y = *(double *) b;
  94
  95         if (x == y)
  96                 return 0;
  97         return (x > y) ? 1 : -1;
  98 }
  99
 100 typedef struct
 101 {
 102         double          low;
 103         double          high;
 104 } Range;
 105
 106 typedef struct
 107 {
 108         Range           left;
 109         Range           right;
 110 } RangeBox;
 111
 112 typedef struct
 113 {
 114         RangeBox        range_box_x;
 115         RangeBox        range_box_y;
 116 } RectBox;
 117
 118 /*
 119  * Calculate the quadrant
 120  *
 121  * The quadrant is 8 bit unsigned integer with 4 least bits in use.
 122  * This function accepts BOXes as input.  They are not casted to
 123  * RangeBoxes, yet.  All 4 bits are set by comparing a corner of the box.
 124  * This makes 16 quadrants in total.
 125  */
 126 static uint8
 127 getQuadrant(BOX *centroid, BOX *inBox)
 128 {
 129         uint8           quadrant = 0;
 130
 131         if (inBox->low.x > centroid->low.x)
 132                 quadrant |= 0x8;
 133
 134         if (inBox->high.x > centroid->high.x)
 135                 quadrant |= 0x4;
 136
 137         if (inBox->low.y > centroid->low.y)
 138                 quadrant |= 0x2;
 139
 140         if (inBox->high.y > centroid->high.y)
 141                 quadrant |= 0x1;
 142
 143         return quadrant;
 144 }
 145
 146 /*
 147  * Get RangeBox using BOX
 148  *
 149  * We are turning the BOX to our structures to emphasize their function
 150  * of representing points in 4D space.  It also is more convenient to
 151  * access the values with this structure.
 152  */
 153 static RangeBox *
 154 getRangeBox(BOX *box)
 155 {
 156         RangeBox   *range_box = (RangeBox *) palloc(sizeof(RangeBox));
 157
 158         range_box->left.low = box->low.x;
 159         range_box->left.high = box->high.x;
 160
 161         range_box->right.low = box->low.y;
 162         range_box->right.high = box->high.y;
 163
 164         return range_box;
 165 }
 166
 167 /*
 168  * Initialize the traversal value
 169  *
 170  * In the beginning, we don't have any restrictions.  We have to
 171  * initialize the struct to cover the whole 4D space.
 172  */
 173 static RectBox *
 174 initRectBox(void)
 175 {
 176         RectBox    *rect_box = (RectBox *) palloc(sizeof(RectBox));
 177         double          infinity = get_float8_infinity();
 178
 179         rect_box->range_box_x.left.low = -infinity;
 180         rect_box->range_box_x.left.high = infinity;
 181
 182         rect_box->range_box_x.right.low = -infinity;
 183         rect_box->range_box_x.right.high = infinity;
 184
 185         rect_box->range_box_y.left.low = -infinity;
 186         rect_box->range_box_y.left.high = infinity;
 187
 188         rect_box->range_box_y.right.low = -infinity;
 189         rect_box->range_box_y.right.high = infinity;
 190
 191         return rect_box;
 192 }
 193
 194 /*
 195  * Calculate the next traversal value
 196  *
 197  * All centroids are bounded by RectBox, but SP-GiST only keeps
 198  * boxes.  When we are traversing the tree, we must calculate RectBox,
 199  * using centroid and quadrant.
 200  */
 201 static RectBox *
 202 nextRectBox(RectBox *rect_box, RangeBox *centroid, uint8 quadrant)
 203 {
 204         RectBox    *next_rect_box = (RectBox *) palloc(sizeof(RectBox));
 205
 206         memcpy(next_rect_box, rect_box, sizeof(RectBox));
 207
 208         if (quadrant & 0x8)
 209                 next_rect_box->range_box_x.left.low = centroid->left.low;
 210         else
 211                 next_rect_box->range_box_x.left.high = centroid->left.low;
 212
 213         if (quadrant & 0x4)
 214                 next_rect_box->range_box_x.right.low = centroid->left.high;
 215         else
 216                 next_rect_box->range_box_x.right.high = centroid->left.high;
 217
 218         if (quadrant & 0x2)
 219                 next_rect_box->range_box_y.left.low = centroid->right.low;
 220         else
 221                 next_rect_box->range_box_y.left.high = centroid->right.low;
 222
 223         if (quadrant & 0x1)
 224                 next_rect_box->range_box_y.right.low = centroid->right.high;
 225         else
 226                 next_rect_box->range_box_y.right.high = centroid->right.high;
 227
 228         return next_rect_box;
 229 }
 230
 231 /* Can any range from range_box overlap with this argument? */
 232 static bool
 233 overlap2D(RangeBox *range_box, Range *query)
 234 {
 235         return FPge(range_box->right.high, query->low) &&
 236                 FPle(range_box->left.low, query->high);
 237 }
 238
 239 /* Can any rectangle from rect_box overlap with this argument? */
 240 static bool
 241 overlap4D(RectBox *rect_box, RangeBox *query)
 242 {
 243         return overlap2D(&rect_box->range_box_x, &query->left) &&
 244                 overlap2D(&rect_box->range_box_y, &query->right);
 245 }
 246
 247 /* Can any range from range_box contain this argument? */
 248 static bool
 249 contain2D(RangeBox *range_box, Range *query)
 250 {
 251         return FPge(range_box->right.high, query->high) &&
 252                 FPle(range_box->left.low, query->low);
 253 }
 254
 255 /* Can any rectangle from rect_box contain this argument? */
 256 static bool
 257 contain4D(RectBox *rect_box, RangeBox *query)
 258 {
 259         return contain2D(&rect_box->range_box_x, &query->left) &&
 260                 contain2D(&rect_box->range_box_y, &query->right);
 261 }
 262
 263 /* Can any range from range_box be contained by this argument? */
 264 static bool
 265 contained2D(RangeBox *range_box, Range *query)
 266 {
 267         return FPle(range_box->left.low, query->high) &&
 268                 FPge(range_box->left.high, query->low) &&
 269                 FPle(range_box->right.low, query->high) &&
 270                 FPge(range_box->right.high, query->low);
 271 }
 272
 273 /* Can any rectangle from rect_box be contained by this argument? */
 274 static bool
 275 contained4D(RectBox *rect_box, RangeBox *query)
 276 {
 277         return contained2D(&rect_box->range_box_x, &query->left) &&
 278                 contained2D(&rect_box->range_box_y, &query->right);
 279 }
 280
 281 /* Can any range from range_box to be lower than this argument? */
 282 static bool
 283 lower2D(RangeBox *range_box, Range *query)
 284 {
 285         return FPlt(range_box->left.low, query->low) &&
 286                 FPlt(range_box->right.low, query->low);
 287 }
 288
 289 /* Can any range from range_box not extend to the right side of the query? */
 290 static bool
 291 overLower2D(RangeBox *range_box, Range *query)
 292 {
 293         return FPle(range_box->left.low, query->high) &&
 294                 FPle(range_box->right.low, query->high);
 295 }
 296
 297 /* Can any range from range_box to be higher than this argument? */
 298 static bool
 299 higher2D(RangeBox *range_box, Range *query)
 300 {
 301         return FPgt(range_box->left.high, query->high) &&
 302                 FPgt(range_box->right.high, query->high);
 303 }
 304
 305 /* Can any range from range_box not extend to the left side of the query? */
 306 static bool
 307 overHigher2D(RangeBox *range_box, Range *query)
 308 {
 309         return FPge(range_box->left.high, query->low) &&
 310                 FPge(range_box->right.high, query->low);
 311 }
 312
 313 /* Can any rectangle from rect_box be left of this argument? */
 314 static bool
 315 left4D(RectBox *rect_box, RangeBox *query)
 316 {
 317         return lower2D(&rect_box->range_box_x, &query->left);
 318 }
 319
 320 /* Can any rectangle from rect_box does not extend the right of this argument? */
 321 static bool
 322 overLeft4D(RectBox *rect_box, RangeBox *query)
 323 {
 324         return overLower2D(&rect_box->range_box_x, &query->left);
 325 }
 326
 327 /* Can any rectangle from rect_box be right of this argument? */
 328 static bool
 329 right4D(RectBox *rect_box, RangeBox *query)
 330 {
 331         return higher2D(&rect_box->range_box_x, &query->left);
 332 }
 333
 334 /* Can any rectangle from rect_box does not extend the left of this argument? */
 335 static bool
 336 overRight4D(RectBox *rect_box, RangeBox *query)
 337 {
 338         return overHigher2D(&rect_box->range_box_x, &query->left);
 339 }
 340
 341 /* Can any rectangle from rect_box be below of this argument? */
 342 static bool
 343 below4D(RectBox *rect_box, RangeBox *query)
 344 {
 345         return lower2D(&rect_box->range_box_y, &query->right);
 346 }
 347
 348 /* Can any rectangle from rect_box does not extend above this argument? */
 349 static bool
 350 overBelow4D(RectBox *rect_box, RangeBox *query)
 351 {
 352         return overLower2D(&rect_box->range_box_y, &query->right);
 353 }
 354
 355 /* Can any rectangle from rect_box be above of this argument? */
 356 static bool
 357 above4D(RectBox *rect_box, RangeBox *query)
 358 {
 359         return higher2D(&rect_box->range_box_y, &query->right);
 360 }
 361
 362 /* Can any rectangle from rect_box does not extend below of this argument? */
 363 static bool
 364 overAbove4D(RectBox *rect_box, RangeBox *query)
 365 {
 366         return overHigher2D(&rect_box->range_box_y, &query->right);
 367 }
 368
 369 /*
 370  * SP-GiST config function
 371  */
 372 Datum
 373 spg_box_quad_config(PG_FUNCTION_ARGS)
 374 {
 375         spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
 376
 377         cfg->prefixType = BOXOID;
 378         cfg->labelType = VOIDOID;       /* We don't need node labels. */
 379         cfg->canReturnData = true;
 380         cfg->longValuesOK = false;
 381
 382         PG_RETURN_VOID();
 383 }
 384
 385 /*
 386  * SP-GiST choose function
 387  */
 388 Datum
 389 spg_box_quad_choose(PG_FUNCTION_ARGS)
 390 {
 391         spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
 392         spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
 393         BOX                *centroid = DatumGetBoxP(in->prefixDatum),
 394                            *box = DatumGetBoxP(in->leafDatum);
 395
 396         out->resultType = spgMatchNode;
 397         out->result.matchNode.restDatum = BoxPGetDatum(box);
 398
 399         /* nodeN will be set by core, when allTheSame. */
 400         if (!in->allTheSame)
 401                 out->result.matchNode.nodeN = getQuadrant(centroid, box);
 402
 403         PG_RETURN_VOID();
 404 }
 405
 406 /*
 407  * SP-GiST pick-split function
 408  *
 409  * It splits a list of boxes into quadrants by choosing a central 4D
 410  * point as the median of the coordinates of the boxes.
 411  */
 412 Datum
 413 spg_box_quad_picksplit(PG_FUNCTION_ARGS)
 414 {
 415         spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
 416         spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
 417         BOX                *centroid;
 418         int                     median,
 419                                 i;
 420         double     *lowXs = palloc(sizeof(double) * in->nTuples);
 421         double     *highXs = palloc(sizeof(double) * in->nTuples);
 422         double     *lowYs = palloc(sizeof(double) * in->nTuples);
 423         double     *highYs = palloc(sizeof(double) * in->nTuples);
 424
 425         /* Calculate median of all 4D coordinates */
 426         for (i = 0; i < in->nTuples; i++)
 427         {
 428                 BOX                *box = DatumGetBoxP(in->datums[i]);
 429
 430                 lowXs[i] = box->low.x;
 431                 highXs[i] = box->high.x;
 432                 lowYs[i] = box->low.y;
 433                 highYs[i] = box->high.y;
 434         }
 435
 436         qsort(lowXs, in->nTuples, sizeof(double), compareDoubles);
 437         qsort(highXs, in->nTuples, sizeof(double), compareDoubles);
 438         qsort(lowYs, in->nTuples, sizeof(double), compareDoubles);
 439         qsort(highYs, in->nTuples, sizeof(double), compareDoubles);
 440
 441         median = in->nTuples / 2;
 442
 443         centroid = palloc(sizeof(BOX));
 444
 445         centroid->low.x = lowXs[median];
 446         centroid->high.x = highXs[median];
 447         centroid->low.y = lowYs[median];
 448         centroid->high.y = highYs[median];
 449
 450         /* Fill the output */
 451         out->hasPrefix = true;
 452         out->prefixDatum = BoxPGetDatum(centroid);
 453
 454         out->nNodes = 16;
 455         out->nodeLabels = NULL;         /* We don't need node labels. */
 456
 457         out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
 458         out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
 459
 460         /*
 461          * Assign ranges to corresponding nodes according to quadrants relative to
 462          * the "centroid" range
 463          */
 464         for (i = 0; i < in->nTuples; i++)
 465         {
 466                 BOX                *box = DatumGetBoxP(in->datums[i]);
 467                 uint8           quadrant = getQuadrant(centroid, box);
 468
 469                 out->leafTupleDatums[i] = BoxPGetDatum(box);
 470                 out->mapTuplesToNodes[i] = quadrant;
 471         }
 472
 473         PG_RETURN_VOID();
 474 }
 475
 476 /*
 477  * Check if result of consistent method based on bounding box is exact.
 478  */
 479 static bool
 480 is_bounding_box_test_exact(StrategyNumber strategy)
 481 {
 482         switch (strategy)
 483         {
 484                 case RTLeftStrategyNumber:
 485                 case RTOverLeftStrategyNumber:
 486                 case RTOverRightStrategyNumber:
 487                 case RTRightStrategyNumber:
 488                 case RTOverBelowStrategyNumber:
 489                 case RTBelowStrategyNumber:
 490                 case RTAboveStrategyNumber:
 491                 case RTOverAboveStrategyNumber:
 492                         return true;
 493
 494                 default:
 495                         return false;
 496         }
 497 }
 498
 499 /*
 500  * Get bounding box for ScanKey.
 501  */
 502 static BOX *
 503 spg_box_quad_get_scankey_bbox(ScanKey sk, bool *recheck)
 504 {
 505         switch (sk->sk_subtype)
 506         {
 507                 case BOXOID:
 508                         return DatumGetBoxP(sk->sk_argument);
 509
 510                 case POLYGONOID:
 511                         if (recheck && !is_bounding_box_test_exact(sk->sk_strategy))
 512                                 *recheck = true;
 513                         return &DatumGetPolygonP(sk->sk_argument)->boundbox;
 514
 515                 default:
 516                         elog(ERROR, "unrecognized scankey subtype: %d", sk->sk_subtype);
 517                         return NULL;
 518         }
 519 }
 520
 521 /*
 522  * SP-GiST inner consistent function
 523  */
 524 Datum
 525 spg_box_quad_inner_consistent(PG_FUNCTION_ARGS)
 526 {
 527         spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
 528         spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
 529         int                     i;
 530         MemoryContext old_ctx;
 531         RectBox    *rect_box;
 532         uint8           quadrant;
 533         RangeBox   *centroid,
 534                           **queries;
 535
 536         if (in->allTheSame)
 537         {
 538                 /* Report that all nodes should be visited */
 539                 out->nNodes = in->nNodes;
 540                 out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
 541                 for (i = 0; i < in->nNodes; i++)
 542                         out->nodeNumbers[i] = i;
 543
 544                 PG_RETURN_VOID();
 545         }
 546
 547         /*
 548          * We are saving the traversal value or initialize it an unbounded one, if
 549          * we have just begun to walk the tree.
 550          */
 551         if (in->traversalValue)
 552                 rect_box = in->traversalValue;
 553         else
 554                 rect_box = initRectBox();
 555
 556         /*
 557          * We are casting the prefix and queries to RangeBoxes for ease of the
 558          * following operations.
 559          */
 560         centroid = getRangeBox(DatumGetBoxP(in->prefixDatum));
 561         queries = (RangeBox **) palloc(in->nkeys * sizeof(RangeBox *));
 562         for (i = 0; i < in->nkeys; i++)
 563         {
 564                 BOX                *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i], NULL);
 565
 566                 queries[i] = getRangeBox(box);
 567         }
 568
 569         /* Allocate enough memory for nodes */
 570         out->nNodes = 0;
 571         out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
 572         out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
 573
 574         /*
 575          * We switch memory context, because we want to allocate memory for new
 576          * traversal values (next_rect_box) and pass these pieces of memory to
 577          * further call of this function.
 578          */
 579         old_ctx = MemoryContextSwitchTo(in->traversalMemoryContext);
 580
 581         for (quadrant = 0; quadrant < in->nNodes; quadrant++)
 582         {
 583                 RectBox    *next_rect_box = nextRectBox(rect_box, centroid, quadrant);
 584                 bool            flag = true;
 585
 586                 for (i = 0; i < in->nkeys; i++)
 587                 {
 588                         StrategyNumber strategy = in->scankeys[i].sk_strategy;
 589
 590                         switch (strategy)
 591                         {
 592                                 case RTOverlapStrategyNumber:
 593                                         flag = overlap4D(next_rect_box, queries[i]);
 594                                         break;
 595
 596                                 case RTContainsStrategyNumber:
 597                                         flag = contain4D(next_rect_box, queries[i]);
 598                                         break;
 599
 600                                 case RTSameStrategyNumber:
 601                                 case RTContainedByStrategyNumber:
 602                                         flag = contained4D(next_rect_box, queries[i]);
 603                                         break;
 604
 605                                 case RTLeftStrategyNumber:
 606                                         flag = left4D(next_rect_box, queries[i]);
 607                                         break;
 608
 609                                 case RTOverLeftStrategyNumber:
 610                                         flag = overLeft4D(next_rect_box, queries[i]);
 611                                         break;
 612
 613                                 case RTRightStrategyNumber:
 614                                         flag = right4D(next_rect_box, queries[i]);
 615                                         break;
 616
 617                                 case RTOverRightStrategyNumber:
 618                                         flag = overRight4D(next_rect_box, queries[i]);
 619                                         break;
 620
 621                                 case RTAboveStrategyNumber:
 622                                         flag = above4D(next_rect_box, queries[i]);
 623                                         break;
 624
 625                                 case RTOverAboveStrategyNumber:
 626                                         flag = overAbove4D(next_rect_box, queries[i]);
 627                                         break;
 628
 629                                 case RTBelowStrategyNumber:
 630                                         flag = below4D(next_rect_box, queries[i]);
 631                                         break;
 632
 633                                 case RTOverBelowStrategyNumber:
 634                                         flag = overBelow4D(next_rect_box, queries[i]);
 635                                         break;
 636
 637                                 default:
 638                                         elog(ERROR, "unrecognized strategy: %d", strategy);
 639                         }
 640
 641                         /* If any check is failed, we have found our answer. */
 642                         if (!flag)
 643                                 break;
 644                 }
 645
 646                 if (flag)
 647                 {
 648                         out->traversalValues[out->nNodes] = next_rect_box;
 649                         out->nodeNumbers[out->nNodes] = quadrant;
 650                         out->nNodes++;
 651                 }
 652                 else
 653                 {
 654                         /*
 655                          * If this node is not selected, we don't need to keep the next
 656                          * traversal value in the memory context.
 657                          */
 658                         pfree(next_rect_box);
 659                 }
 660         }
 661
 662         /* Switch back */
 663         MemoryContextSwitchTo(old_ctx);
 664
 665         PG_RETURN_VOID();
 666 }
 667
 668 /*
 669  * SP-GiST inner consistent function
 670  */
 671 Datum
 672 spg_box_quad_leaf_consistent(PG_FUNCTION_ARGS)
 673 {
 674         spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
 675         spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
 676         Datum           leaf = in->leafDatum;
 677         bool            flag = true;
 678         int                     i;
 679
 680         /* All tests are exact. */
 681         out->recheck = false;
 682
 683         /* leafDatum is what it is... */
 684         out->leafValue = in->leafDatum;
 685
 686         /* Perform the required comparison(s) */
 687         for (i = 0; i < in->nkeys; i++)
 688         {
 689                 StrategyNumber strategy = in->scankeys[i].sk_strategy;
 690                 BOX                *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i],
 691                                                                                                                 &out->recheck);
 692                 Datum           query = BoxPGetDatum(box);
 693
 694                 switch (strategy)
 695                 {
 696                         case RTOverlapStrategyNumber:
 697                                 flag = DatumGetBool(DirectFunctionCall2(box_overlap, leaf,
 698                                                                                                                 query));
 699                                 break;
 700
 701                         case RTContainsStrategyNumber:
 702                                 flag = DatumGetBool(DirectFunctionCall2(box_contain, leaf,
 703                                                                                                                 query));
 704                                 break;
 705
 706                         case RTContainedByStrategyNumber:
 707                                 flag = DatumGetBool(DirectFunctionCall2(box_contained, leaf,
 708                                                                                                                 query));
 709                                 break;
 710
 711                         case RTSameStrategyNumber:
 712                                 flag = DatumGetBool(DirectFunctionCall2(box_same, leaf,
 713                                                                                                                 query));
 714                                 break;
 715
 716                         case RTLeftStrategyNumber:
 717                                 flag = DatumGetBool(DirectFunctionCall2(box_left, leaf,
 718                                                                                                                 query));
 719                                 break;
 720
 721                         case RTOverLeftStrategyNumber:
 722                                 flag = DatumGetBool(DirectFunctionCall2(box_overleft, leaf,
 723                                                                                                                 query));
 724                                 break;
 725
 726                         case RTRightStrategyNumber:
 727                                 flag = DatumGetBool(DirectFunctionCall2(box_right, leaf,
 728                                                                                                                 query));
 729                                 break;
 730
 731                         case RTOverRightStrategyNumber:
 732                                 flag = DatumGetBool(DirectFunctionCall2(box_overright, leaf,
 733                                                                                                                 query));
 734                                 break;
 735
 736                         case RTAboveStrategyNumber:
 737                                 flag = DatumGetBool(DirectFunctionCall2(box_above, leaf,
 738                                                                                                                 query));
 739                                 break;
 740
 741                         case RTOverAboveStrategyNumber:
 742                                 flag = DatumGetBool(DirectFunctionCall2(box_overabove, leaf,
 743                                                                                                                 query));
 744                                 break;
 745
 746                         case RTBelowStrategyNumber:
 747                                 flag = DatumGetBool(DirectFunctionCall2(box_below, leaf,
 748                                                                                                                 query));
 749                                 break;
 750
 751                         case RTOverBelowStrategyNumber:
 752                                 flag = DatumGetBool(DirectFunctionCall2(box_overbelow, leaf,
 753                                                                                                                 query));
 754                                 break;
 755
 756                         default:
 757                                 elog(ERROR, "unrecognized strategy: %d", strategy);
 758                 }
 759
 760                 /* If any check is failed, we have found our answer. */
 761                 if (!flag)
 762                         break;
 763         }
 764
 765         PG_RETURN_BOOL(flag);
 766 }
 767
 768
 769 /*
 770  * SP-GiST config function for 2-D types that are lossy represented by their
 771  * bounding boxes
 772  */
 773 Datum
 774 spg_bbox_quad_config(PG_FUNCTION_ARGS)
 775 {
 776         spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
 777
 778         cfg->prefixType = BOXOID;       /* A type represented by its bounding box */
 779         cfg->labelType = VOIDOID;       /* We don't need node labels. */
 780         cfg->leafType = BOXOID;
 781         cfg->canReturnData = false;
 782         cfg->longValuesOK = false;
 783
 784         PG_RETURN_VOID();
 785 }
 786
 787 /*
 788  * SP-GiST compress function for polygons
 789  */
 790 Datum
 791 spg_poly_quad_compress(PG_FUNCTION_ARGS)
 792 {
 793         POLYGON    *polygon = PG_GETARG_POLYGON_P(0);
 794         BOX                *box;
 795
 796         box = (BOX *) palloc(sizeof(BOX));
 797         *box = polygon->boundbox;
 798
 799         PG_RETURN_BOX_P(box);
 800 }