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