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