granicus.if.org Git - postgresql/blob - src/backend/access/gist/gistproc.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * gistproc.c
   4  *        Support procedures for GiSTs over 2-D objects (boxes, polygons, circles,
   5  *        points).
   6  *
   7  * This gives R-tree behavior, with Guttman's poly-time split algorithm.
   8  *
   9  *
  10  * Portions Copyright (c) 1996-2015, PostgreSQL Global Development Group
  11  * Portions Copyright (c) 1994, Regents of the University of California
  12  *
  13  * IDENTIFICATION
  14  *      src/backend/access/gist/gistproc.c
  15  *
  16  *-------------------------------------------------------------------------
  17  */
  18 #include "postgres.h"
  19
  20 #include "access/gist.h"
  21 #include "access/skey.h"
  22 #include "utils/geo_decls.h"
  23
  24
  25 static bool gist_box_leaf_consistent(BOX *key, BOX *query,
  26                                                  StrategyNumber strategy);
  27 static double size_box(BOX *box);
  28 static bool rtree_internal_consistent(BOX *key, BOX *query,
  29                                                   StrategyNumber strategy);
  30
  31 /* Minimum accepted ratio of split */
  32 #define LIMIT_RATIO 0.3
  33
  34
  35 /**************************************************
  36  * Box ops
  37  **************************************************/
  38
  39 /*
  40  * Calculates union of two boxes, a and b. The result is stored in *n.
  41  */
  42 static void
  43 rt_box_union(BOX *n, BOX *a, BOX *b)
  44 {
  45         n->high.x = Max(a->high.x, b->high.x);
  46         n->high.y = Max(a->high.y, b->high.y);
  47         n->low.x = Min(a->low.x, b->low.x);
  48         n->low.y = Min(a->low.y, b->low.y);
  49 }
  50
  51 /*
  52  * The GiST Consistent method for boxes
  53  *
  54  * Should return false if for all data items x below entry,
  55  * the predicate x op query must be FALSE, where op is the oper
  56  * corresponding to strategy in the pg_amop table.
  57  */
  58 Datum
  59 gist_box_consistent(PG_FUNCTION_ARGS)
  60 {
  61         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
  62         BOX                *query = PG_GETARG_BOX_P(1);
  63         StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
  64
  65         /* Oid          subtype = PG_GETARG_OID(3); */
  66         bool       *recheck = (bool *) PG_GETARG_POINTER(4);
  67
  68         /* All cases served by this function are exact */
  69         *recheck = false;
  70
  71         if (DatumGetBoxP(entry->key) == NULL || query == NULL)
  72                 PG_RETURN_BOOL(FALSE);
  73
  74         /*
  75          * if entry is not leaf, use rtree_internal_consistent, else use
  76          * gist_box_leaf_consistent
  77          */
  78         if (GIST_LEAF(entry))
  79                 PG_RETURN_BOOL(gist_box_leaf_consistent(DatumGetBoxP(entry->key),
  80                                                                                                 query,
  81                                                                                                 strategy));
  82         else
  83                 PG_RETURN_BOOL(rtree_internal_consistent(DatumGetBoxP(entry->key),
  84                                                                                                  query,
  85                                                                                                  strategy));
  86 }
  87
  88 static void
  89 adjustBox(BOX *b, BOX *addon)
  90 {
  91         if (b->high.x < addon->high.x)
  92                 b->high.x = addon->high.x;
  93         if (b->low.x > addon->low.x)
  94                 b->low.x = addon->low.x;
  95         if (b->high.y < addon->high.y)
  96                 b->high.y = addon->high.y;
  97         if (b->low.y > addon->low.y)
  98                 b->low.y = addon->low.y;
  99 }
 100
 101 /*
 102  * The GiST Union method for boxes
 103  *
 104  * returns the minimal bounding box that encloses all the entries in entryvec
 105  */
 106 Datum
 107 gist_box_union(PG_FUNCTION_ARGS)
 108 {
 109         GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 110         int                *sizep = (int *) PG_GETARG_POINTER(1);
 111         int                     numranges,
 112                                 i;
 113         BOX                *cur,
 114                            *pageunion;
 115
 116         numranges = entryvec->n;
 117         pageunion = (BOX *) palloc(sizeof(BOX));
 118         cur = DatumGetBoxP(entryvec->vector[0].key);
 119         memcpy((void *) pageunion, (void *) cur, sizeof(BOX));
 120
 121         for (i = 1; i < numranges; i++)
 122         {
 123                 cur = DatumGetBoxP(entryvec->vector[i].key);
 124                 adjustBox(pageunion, cur);
 125         }
 126         *sizep = sizeof(BOX);
 127
 128         PG_RETURN_POINTER(pageunion);
 129 }
 130
 131 /*
 132  * GiST Compress methods for boxes
 133  *
 134  * do not do anything.
 135  */
 136 Datum
 137 gist_box_compress(PG_FUNCTION_ARGS)
 138 {
 139         PG_RETURN_POINTER(PG_GETARG_POINTER(0));
 140 }
 141
 142 /*
 143  * GiST DeCompress method for boxes (also used for points, polygons
 144  * and circles)
 145  *
 146  * do not do anything --- we just use the stored box as is.
 147  */
 148 Datum
 149 gist_box_decompress(PG_FUNCTION_ARGS)
 150 {
 151         PG_RETURN_POINTER(PG_GETARG_POINTER(0));
 152 }
 153
 154 /*
 155  * The GiST Penalty method for boxes (also used for points)
 156  *
 157  * As in the R-tree paper, we use change in area as our penalty metric
 158  */
 159 Datum
 160 gist_box_penalty(PG_FUNCTION_ARGS)
 161 {
 162         GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
 163         GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
 164         float      *result = (float *) PG_GETARG_POINTER(2);
 165         BOX                *origbox = DatumGetBoxP(origentry->key);
 166         BOX                *newbox = DatumGetBoxP(newentry->key);
 167         BOX                     unionbox;
 168
 169         rt_box_union(&unionbox, origbox, newbox);
 170         *result = (float) (size_box(&unionbox) - size_box(origbox));
 171         PG_RETURN_POINTER(result);
 172 }
 173
 174 /*
 175  * Trivial split: half of entries will be placed on one page
 176  * and another half - to another
 177  */
 178 static void
 179 fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
 180 {
 181         OffsetNumber i,
 182                                 maxoff;
 183         BOX                *unionL = NULL,
 184                            *unionR = NULL;
 185         int                     nbytes;
 186
 187         maxoff = entryvec->n - 1;
 188
 189         nbytes = (maxoff + 2) * sizeof(OffsetNumber);
 190         v->spl_left = (OffsetNumber *) palloc(nbytes);
 191         v->spl_right = (OffsetNumber *) palloc(nbytes);
 192         v->spl_nleft = v->spl_nright = 0;
 193
 194         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
 195         {
 196                 BOX                *cur = DatumGetBoxP(entryvec->vector[i].key);
 197
 198                 if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
 199                 {
 200                         v->spl_left[v->spl_nleft] = i;
 201                         if (unionL == NULL)
 202                         {
 203                                 unionL = (BOX *) palloc(sizeof(BOX));
 204                                 *unionL = *cur;
 205                         }
 206                         else
 207                                 adjustBox(unionL, cur);
 208
 209                         v->spl_nleft++;
 210                 }
 211                 else
 212                 {
 213                         v->spl_right[v->spl_nright] = i;
 214                         if (unionR == NULL)
 215                         {
 216                                 unionR = (BOX *) palloc(sizeof(BOX));
 217                                 *unionR = *cur;
 218                         }
 219                         else
 220                                 adjustBox(unionR, cur);
 221
 222                         v->spl_nright++;
 223                 }
 224         }
 225
 226         v->spl_ldatum = BoxPGetDatum(unionL);
 227         v->spl_rdatum = BoxPGetDatum(unionR);
 228 }
 229
 230 /*
 231  * Represents information about an entry that can be placed to either group
 232  * without affecting overlap over selected axis ("common entry").
 233  */
 234 typedef struct
 235 {
 236         /* Index of entry in the initial array */
 237         int                     index;
 238         /* Delta between penalties of entry insertion into different groups */
 239         double          delta;
 240 } CommonEntry;
 241
 242 /*
 243  * Context for g_box_consider_split. Contains information about currently
 244  * selected split and some general information.
 245  */
 246 typedef struct
 247 {
 248         int                     entriesCount;   /* total number of entries being split */
 249         BOX                     boundingBox;    /* minimum bounding box across all entries */
 250
 251         /* Information about currently selected split follows */
 252
 253         bool            first;                  /* true if no split was selected yet */
 254
 255         double          leftUpper;              /* upper bound of left interval */
 256         double          rightLower;             /* lower bound of right interval */
 257
 258         float4          ratio;
 259         float4          overlap;
 260         int                     dim;                    /* axis of this split */
 261         double          range;                  /* width of general MBR projection to the
 262                                                                  * selected axis */
 263 } ConsiderSplitContext;
 264
 265 /*
 266  * Interval represents projection of box to axis.
 267  */
 268 typedef struct
 269 {
 270         double          lower,
 271                                 upper;
 272 } SplitInterval;
 273
 274 /*
 275  * Interval comparison function by lower bound of the interval;
 276  */
 277 static int
 278 interval_cmp_lower(const void *i1, const void *i2)
 279 {
 280         double          lower1 = ((const SplitInterval *) i1)->lower,
 281                                 lower2 = ((const SplitInterval *) i2)->lower;
 282
 283         if (lower1 < lower2)
 284                 return -1;
 285         else if (lower1 > lower2)
 286                 return 1;
 287         else
 288                 return 0;
 289 }
 290
 291 /*
 292  * Interval comparison function by upper bound of the interval;
 293  */
 294 static int
 295 interval_cmp_upper(const void *i1, const void *i2)
 296 {
 297         double          upper1 = ((const SplitInterval *) i1)->upper,
 298                                 upper2 = ((const SplitInterval *) i2)->upper;
 299
 300         if (upper1 < upper2)
 301                 return -1;
 302         else if (upper1 > upper2)
 303                 return 1;
 304         else
 305                 return 0;
 306 }
 307
 308 /*
 309  * Replace negative value with zero.
 310  */
 311 static inline float
 312 non_negative(float val)
 313 {
 314         if (val >= 0.0f)
 315                 return val;
 316         else
 317                 return 0.0f;
 318 }
 319
 320 /*
 321  * Consider replacement of currently selected split with the better one.
 322  */
 323 static inline void
 324 g_box_consider_split(ConsiderSplitContext *context, int dimNum,
 325                                          double rightLower, int minLeftCount,
 326                                          double leftUpper, int maxLeftCount)
 327 {
 328         int                     leftCount,
 329                                 rightCount;
 330         float4          ratio,
 331                                 overlap;
 332         double          range;
 333
 334         /*
 335          * Calculate entries distribution ratio assuming most uniform distribution
 336          * of common entries.
 337          */
 338         if (minLeftCount >= (context->entriesCount + 1) / 2)
 339         {
 340                 leftCount = minLeftCount;
 341         }
 342         else
 343         {
 344                 if (maxLeftCount <= context->entriesCount / 2)
 345                         leftCount = maxLeftCount;
 346                 else
 347                         leftCount = context->entriesCount / 2;
 348         }
 349         rightCount = context->entriesCount - leftCount;
 350
 351         /*
 352          * Ratio of split - quotient between size of lesser group and total
 353          * entries count.
 354          */
 355         ratio = ((float4) Min(leftCount, rightCount)) /
 356                 ((float4) context->entriesCount);
 357
 358         if (ratio > LIMIT_RATIO)
 359         {
 360                 bool            selectthis = false;
 361
 362                 /*
 363                  * The ratio is acceptable, so compare current split with previously
 364                  * selected one. Between splits of one dimension we search for minimal
 365                  * overlap (allowing negative values) and minimal ration (between same
 366                  * overlaps. We switch dimension if find less overlap (non-negative)
 367                  * or less range with same overlap.
 368                  */
 369                 if (dimNum == 0)
 370                         range = context->boundingBox.high.x - context->boundingBox.low.x;
 371                 else
 372                         range = context->boundingBox.high.y - context->boundingBox.low.y;
 373
 374                 overlap = (leftUpper - rightLower) / range;
 375
 376                 /* If there is no previous selection, select this */
 377                 if (context->first)
 378                         selectthis = true;
 379                 else if (context->dim == dimNum)
 380                 {
 381                         /*
 382                          * Within the same dimension, choose the new split if it has a
 383                          * smaller overlap, or same overlap but better ratio.
 384                          */
 385                         if (overlap < context->overlap ||
 386                                 (overlap == context->overlap && ratio > context->ratio))
 387                                 selectthis = true;
 388                 }
 389                 else
 390                 {
 391                         /*
 392                          * Across dimensions, choose the new split if it has a smaller
 393                          * *non-negative* overlap, or same *non-negative* overlap but
 394                          * bigger range. This condition differs from the one described in
 395                          * the article. On the datasets where leaf MBRs don't overlap
 396                          * themselves, non-overlapping splits (i.e. splits which have zero
 397                          * *non-negative* overlap) are frequently possible. In this case
 398                          * splits tends to be along one dimension, because most distant
 399                          * non-overlapping splits (i.e. having lowest negative overlap)
 400                          * appears to be in the same dimension as in the previous split.
 401                          * Therefore MBRs appear to be very prolonged along another
 402                          * dimension, which leads to bad search performance. Using range
 403                          * as the second split criteria makes MBRs more quadratic. Using
 404                          * *non-negative* overlap instead of overlap as the first split
 405                          * criteria gives to range criteria a chance to matter, because
 406                          * non-overlapping splits are equivalent in this criteria.
 407                          */
 408                         if (non_negative(overlap) < non_negative(context->overlap) ||
 409                                 (range > context->range &&
 410                                  non_negative(overlap) <= non_negative(context->overlap)))
 411                                 selectthis = true;
 412                 }
 413
 414                 if (selectthis)
 415                 {
 416                         /* save information about selected split */
 417                         context->first = false;
 418                         context->ratio = ratio;
 419                         context->range = range;
 420                         context->overlap = overlap;
 421                         context->rightLower = rightLower;
 422                         context->leftUpper = leftUpper;
 423                         context->dim = dimNum;
 424                 }
 425         }
 426 }
 427
 428 /*
 429  * Return increase of original BOX area by new BOX area insertion.
 430  */
 431 static double
 432 box_penalty(BOX *original, BOX *new)
 433 {
 434         double          union_width,
 435                                 union_height;
 436
 437         union_width = Max(original->high.x, new->high.x) -
 438                 Min(original->low.x, new->low.x);
 439         union_height = Max(original->high.y, new->high.y) -
 440                 Min(original->low.y, new->low.y);
 441         return union_width * union_height - (original->high.x - original->low.x) *
 442                 (original->high.y - original->low.y);
 443 }
 444
 445 /*
 446  * Compare common entries by their deltas.
 447  */
 448 static int
 449 common_entry_cmp(const void *i1, const void *i2)
 450 {
 451         double          delta1 = ((const CommonEntry *) i1)->delta,
 452                                 delta2 = ((const CommonEntry *) i2)->delta;
 453
 454         if (delta1 < delta2)
 455                 return -1;
 456         else if (delta1 > delta2)
 457                 return 1;
 458         else
 459                 return 0;
 460 }
 461
 462 /*
 463  * --------------------------------------------------------------------------
 464  * Double sorting split algorithm. This is used for both boxes and points.
 465  *
 466  * The algorithm finds split of boxes by considering splits along each axis.
 467  * Each entry is first projected as an interval on the X-axis, and different
 468  * ways to split the intervals into two groups are considered, trying to
 469  * minimize the overlap of the groups. Then the same is repeated for the
 470  * Y-axis, and the overall best split is chosen. The quality of a split is
 471  * determined by overlap along that axis and some other criteria (see
 472  * g_box_consider_split).
 473  *
 474  * After that, all the entries are divided into three groups:
 475  *
 476  * 1) Entries which should be placed to the left group
 477  * 2) Entries which should be placed to the right group
 478  * 3) "Common entries" which can be placed to any of groups without affecting
 479  *        of overlap along selected axis.
 480  *
 481  * The common entries are distributed by minimizing penalty.
 482  *
 483  * For details see:
 484  * "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov
 485  * http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
 486  * --------------------------------------------------------------------------
 487  */
 488 Datum
 489 gist_box_picksplit(PG_FUNCTION_ARGS)
 490 {
 491         GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 492         GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
 493         OffsetNumber i,
 494                                 maxoff;
 495         ConsiderSplitContext context;
 496         BOX                *box,
 497                            *leftBox,
 498                            *rightBox;
 499         int                     dim,
 500                                 commonEntriesCount;
 501         SplitInterval *intervalsLower,
 502                            *intervalsUpper;
 503         CommonEntry *commonEntries;
 504         int                     nentries;
 505
 506         memset(&context, 0, sizeof(ConsiderSplitContext));
 507
 508         maxoff = entryvec->n - 1;
 509         nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
 510
 511         /* Allocate arrays for intervals along axes */
 512         intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
 513         intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
 514
 515         /*
 516          * Calculate the overall minimum bounding box over all the entries.
 517          */
 518         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
 519         {
 520                 box = DatumGetBoxP(entryvec->vector[i].key);
 521                 if (i == FirstOffsetNumber)
 522                         context.boundingBox = *box;
 523                 else
 524                         adjustBox(&context.boundingBox, box);
 525         }
 526
 527         /*
 528          * Iterate over axes for optimal split searching.
 529          */
 530         context.first = true;           /* nothing selected yet */
 531         for (dim = 0; dim < 2; dim++)
 532         {
 533                 double          leftUpper,
 534                                         rightLower;
 535                 int                     i1,
 536                                         i2;
 537
 538                 /* Project each entry as an interval on the selected axis. */
 539                 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
 540                 {
 541                         box = DatumGetBoxP(entryvec->vector[i].key);
 542                         if (dim == 0)
 543                         {
 544                                 intervalsLower[i - FirstOffsetNumber].lower = box->low.x;
 545                                 intervalsLower[i - FirstOffsetNumber].upper = box->high.x;
 546                         }
 547                         else
 548                         {
 549                                 intervalsLower[i - FirstOffsetNumber].lower = box->low.y;
 550                                 intervalsLower[i - FirstOffsetNumber].upper = box->high.y;
 551                         }
 552                 }
 553
 554                 /*
 555                  * Make two arrays of intervals: one sorted by lower bound and another
 556                  * sorted by upper bound.
 557                  */
 558                 memcpy(intervalsUpper, intervalsLower,
 559                            sizeof(SplitInterval) * nentries);
 560                 qsort(intervalsLower, nentries, sizeof(SplitInterval),
 561                           interval_cmp_lower);
 562                 qsort(intervalsUpper, nentries, sizeof(SplitInterval),
 563                           interval_cmp_upper);
 564
 565                 /*----
 566                  * The goal is to form a left and right interval, so that every entry
 567                  * interval is contained by either left or right interval (or both).
 568                  *
 569                  * For example, with the intervals (0,1), (1,3), (2,3), (2,4):
 570                  *
 571                  * 0 1 2 3 4
 572                  * +-+
 573                  *       +---+
 574                  *         +-+
 575                  *         +---+
 576                  *
 577                  * The left and right intervals are of the form (0,a) and (b,4).
 578                  * We first consider splits where b is the lower bound of an entry.
 579                  * We iterate through all entries, and for each b, calculate the
 580                  * smallest possible a. Then we consider splits where a is the
 581                  * uppper bound of an entry, and for each a, calculate the greatest
 582                  * possible b.
 583                  *
 584                  * In the above example, the first loop would consider splits:
 585                  * b=0: (0,1)-(0,4)
 586                  * b=1: (0,1)-(1,4)
 587                  * b=2: (0,3)-(2,4)
 588                  *
 589                  * And the second loop:
 590                  * a=1: (0,1)-(1,4)
 591                  * a=3: (0,3)-(2,4)
 592                  * a=4: (0,4)-(2,4)
 593                  */
 594
 595                 /*
 596                  * Iterate over lower bound of right group, finding smallest possible
 597                  * upper bound of left group.
 598                  */
 599                 i1 = 0;
 600                 i2 = 0;
 601                 rightLower = intervalsLower[i1].lower;
 602                 leftUpper = intervalsUpper[i2].lower;
 603                 while (true)
 604                 {
 605                         /*
 606                          * Find next lower bound of right group.
 607                          */
 608                         while (i1 < nentries && rightLower == intervalsLower[i1].lower)
 609                         {
 610                                 leftUpper = Max(leftUpper, intervalsLower[i1].upper);
 611                                 i1++;
 612                         }
 613                         if (i1 >= nentries)
 614                                 break;
 615                         rightLower = intervalsLower[i1].lower;
 616
 617                         /*
 618                          * Find count of intervals which anyway should be placed to the
 619                          * left group.
 620                          */
 621                         while (i2 < nentries && intervalsUpper[i2].upper <= leftUpper)
 622                                 i2++;
 623
 624                         /*
 625                          * Consider found split.
 626                          */
 627                         g_box_consider_split(&context, dim, rightLower, i1, leftUpper, i2);
 628                 }
 629
 630                 /*
 631                  * Iterate over upper bound of left group finding greates possible
 632                  * lower bound of right group.
 633                  */
 634                 i1 = nentries - 1;
 635                 i2 = nentries - 1;
 636                 rightLower = intervalsLower[i1].upper;
 637                 leftUpper = intervalsUpper[i2].upper;
 638                 while (true)
 639                 {
 640                         /*
 641                          * Find next upper bound of left group.
 642                          */
 643                         while (i2 >= 0 && leftUpper == intervalsUpper[i2].upper)
 644                         {
 645                                 rightLower = Min(rightLower, intervalsUpper[i2].lower);
 646                                 i2--;
 647                         }
 648                         if (i2 < 0)
 649                                 break;
 650                         leftUpper = intervalsUpper[i2].upper;
 651
 652                         /*
 653                          * Find count of intervals which anyway should be placed to the
 654                          * right group.
 655                          */
 656                         while (i1 >= 0 && intervalsLower[i1].lower >= rightLower)
 657                                 i1--;
 658
 659                         /*
 660                          * Consider found split.
 661                          */
 662                         g_box_consider_split(&context, dim,
 663                                                                  rightLower, i1 + 1, leftUpper, i2 + 1);
 664                 }
 665         }
 666
 667         /*
 668          * If we failed to find any acceptable splits, use trivial split.
 669          */
 670         if (context.first)
 671         {
 672                 fallbackSplit(entryvec, v);
 673                 PG_RETURN_POINTER(v);
 674         }
 675
 676         /*
 677          * Ok, we have now selected the split across one axis.
 678          *
 679          * While considering the splits, we already determined that there will be
 680          * enough entries in both groups to reach the desired ratio, but we did
 681          * not memorize which entries go to which group. So determine that now.
 682          */
 683
 684         /* Allocate vectors for results */
 685         v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
 686         v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
 687         v->spl_nleft = 0;
 688         v->spl_nright = 0;
 689
 690         /* Allocate bounding boxes of left and right groups */
 691         leftBox = palloc0(sizeof(BOX));
 692         rightBox = palloc0(sizeof(BOX));
 693
 694         /*
 695          * Allocate an array for "common entries" - entries which can be placed to
 696          * either group without affecting overlap along selected axis.
 697          */
 698         commonEntriesCount = 0;
 699         commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
 700
 701         /* Helper macros to place an entry in the left or right group */
 702 #define PLACE_LEFT(box, off)                                    \
 703         do {                                                                            \
 704                 if (v->spl_nleft > 0)                                   \
 705                         adjustBox(leftBox, box);                        \
 706                 else                                                                    \
 707                         *leftBox = *(box);                                      \
 708                 v->spl_left[v->spl_nleft++] = off;              \
 709         } while(0)
 710
 711 #define PLACE_RIGHT(box, off)                                   \
 712         do {                                                                            \
 713                 if (v->spl_nright > 0)                                  \
 714                         adjustBox(rightBox, box);                       \
 715                 else                                                                    \
 716                         *rightBox = *(box);                                     \
 717                 v->spl_right[v->spl_nright++] = off;    \
 718         } while(0)
 719
 720         /*
 721          * Distribute entries which can be distributed unambiguously, and collect
 722          * common entries.
 723          */
 724         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
 725         {
 726                 double          lower,
 727                                         upper;
 728
 729                 /*
 730                  * Get upper and lower bounds along selected axis.
 731                  */
 732                 box = DatumGetBoxP(entryvec->vector[i].key);
 733                 if (context.dim == 0)
 734                 {
 735                         lower = box->low.x;
 736                         upper = box->high.x;
 737                 }
 738                 else
 739                 {
 740                         lower = box->low.y;
 741                         upper = box->high.y;
 742                 }
 743
 744                 if (upper <= context.leftUpper)
 745                 {
 746                         /* Fits to the left group */
 747                         if (lower >= context.rightLower)
 748                         {
 749                                 /* Fits also to the right group, so "common entry" */
 750                                 commonEntries[commonEntriesCount++].index = i;
 751                         }
 752                         else
 753                         {
 754                                 /* Doesn't fit to the right group, so join to the left group */
 755                                 PLACE_LEFT(box, i);
 756                         }
 757                 }
 758                 else
 759                 {
 760                         /*
 761                          * Each entry should fit on either left or right group. Since this
 762                          * entry didn't fit on the left group, it better fit in the right
 763                          * group.
 764                          */
 765                         Assert(lower >= context.rightLower);
 766
 767                         /* Doesn't fit to the left group, so join to the right group */
 768                         PLACE_RIGHT(box, i);
 769                 }
 770         }
 771
 772         /*
 773          * Distribute "common entries", if any.
 774          */
 775         if (commonEntriesCount > 0)
 776         {
 777                 /*
 778                  * Calculate minimum number of entries that must be placed in both
 779                  * groups, to reach LIMIT_RATIO.
 780                  */
 781                 int                     m = ceil(LIMIT_RATIO * (double) nentries);
 782
 783                 /*
 784                  * Calculate delta between penalties of join "common entries" to
 785                  * different groups.
 786                  */
 787                 for (i = 0; i < commonEntriesCount; i++)
 788                 {
 789                         box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key);
 790                         commonEntries[i].delta = Abs(box_penalty(leftBox, box) -
 791                                                                                  box_penalty(rightBox, box));
 792                 }
 793
 794                 /*
 795                  * Sort "common entries" by calculated deltas in order to distribute
 796                  * the most ambiguous entries first.
 797                  */
 798                 qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp);
 799
 800                 /*
 801                  * Distribute "common entries" between groups.
 802                  */
 803                 for (i = 0; i < commonEntriesCount; i++)
 804                 {
 805                         box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key);
 806
 807                         /*
 808                          * Check if we have to place this entry in either group to achieve
 809                          * LIMIT_RATIO.
 810                          */
 811                         if (v->spl_nleft + (commonEntriesCount - i) <= m)
 812                                 PLACE_LEFT(box, commonEntries[i].index);
 813                         else if (v->spl_nright + (commonEntriesCount - i) <= m)
 814                                 PLACE_RIGHT(box, commonEntries[i].index);
 815                         else
 816                         {
 817                                 /* Otherwise select the group by minimal penalty */
 818                                 if (box_penalty(leftBox, box) < box_penalty(rightBox, box))
 819                                         PLACE_LEFT(box, commonEntries[i].index);
 820                                 else
 821                                         PLACE_RIGHT(box, commonEntries[i].index);
 822                         }
 823                 }
 824         }
 825
 826         v->spl_ldatum = PointerGetDatum(leftBox);
 827         v->spl_rdatum = PointerGetDatum(rightBox);
 828         PG_RETURN_POINTER(v);
 829 }
 830
 831 /*
 832  * Equality method
 833  *
 834  * This is used for boxes, points, circles, and polygons, all of which store
 835  * boxes as GiST index entries.
 836  *
 837  * Returns true only when boxes are exactly the same.  We can't use fuzzy
 838  * comparisons here without breaking index consistency; therefore, this isn't
 839  * equivalent to box_same().
 840  */
 841 Datum
 842 gist_box_same(PG_FUNCTION_ARGS)
 843 {
 844         BOX                *b1 = PG_GETARG_BOX_P(0);
 845         BOX                *b2 = PG_GETARG_BOX_P(1);
 846         bool       *result = (bool *) PG_GETARG_POINTER(2);
 847
 848         if (b1 && b2)
 849                 *result = (b1->low.x == b2->low.x && b1->low.y == b2->low.y &&
 850                                    b1->high.x == b2->high.x && b1->high.y == b2->high.y);
 851         else
 852                 *result = (b1 == NULL && b2 == NULL);
 853         PG_RETURN_POINTER(result);
 854 }
 855
 856 /*
 857  * Leaf-level consistency for boxes: just apply the query operator
 858  */
 859 static bool
 860 gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy)
 861 {
 862         bool            retval;
 863
 864         switch (strategy)
 865         {
 866                 case RTLeftStrategyNumber:
 867                         retval = DatumGetBool(DirectFunctionCall2(box_left,
 868                                                                                                           PointerGetDatum(key),
 869                                                                                                         PointerGetDatum(query)));
 870                         break;
 871                 case RTOverLeftStrategyNumber:
 872                         retval = DatumGetBool(DirectFunctionCall2(box_overleft,
 873                                                                                                           PointerGetDatum(key),
 874                                                                                                         PointerGetDatum(query)));
 875                         break;
 876                 case RTOverlapStrategyNumber:
 877                         retval = DatumGetBool(DirectFunctionCall2(box_overlap,
 878                                                                                                           PointerGetDatum(key),
 879                                                                                                         PointerGetDatum(query)));
 880                         break;
 881                 case RTOverRightStrategyNumber:
 882                         retval = DatumGetBool(DirectFunctionCall2(box_overright,
 883                                                                                                           PointerGetDatum(key),
 884                                                                                                         PointerGetDatum(query)));
 885                         break;
 886                 case RTRightStrategyNumber:
 887                         retval = DatumGetBool(DirectFunctionCall2(box_right,
 888                                                                                                           PointerGetDatum(key),
 889                                                                                                         PointerGetDatum(query)));
 890                         break;
 891                 case RTSameStrategyNumber:
 892                         retval = DatumGetBool(DirectFunctionCall2(box_same,
 893                                                                                                           PointerGetDatum(key),
 894                                                                                                         PointerGetDatum(query)));
 895                         break;
 896                 case RTContainsStrategyNumber:
 897                 case RTOldContainsStrategyNumber:
 898                         retval = DatumGetBool(DirectFunctionCall2(box_contain,
 899                                                                                                           PointerGetDatum(key),
 900                                                                                                         PointerGetDatum(query)));
 901                         break;
 902                 case RTContainedByStrategyNumber:
 903                 case RTOldContainedByStrategyNumber:
 904                         retval = DatumGetBool(DirectFunctionCall2(box_contained,
 905                                                                                                           PointerGetDatum(key),
 906                                                                                                         PointerGetDatum(query)));
 907                         break;
 908                 case RTOverBelowStrategyNumber:
 909                         retval = DatumGetBool(DirectFunctionCall2(box_overbelow,
 910                                                                                                           PointerGetDatum(key),
 911                                                                                                         PointerGetDatum(query)));
 912                         break;
 913                 case RTBelowStrategyNumber:
 914                         retval = DatumGetBool(DirectFunctionCall2(box_below,
 915                                                                                                           PointerGetDatum(key),
 916                                                                                                         PointerGetDatum(query)));
 917                         break;
 918                 case RTAboveStrategyNumber:
 919                         retval = DatumGetBool(DirectFunctionCall2(box_above,
 920                                                                                                           PointerGetDatum(key),
 921                                                                                                         PointerGetDatum(query)));
 922                         break;
 923                 case RTOverAboveStrategyNumber:
 924                         retval = DatumGetBool(DirectFunctionCall2(box_overabove,
 925                                                                                                           PointerGetDatum(key),
 926                                                                                                         PointerGetDatum(query)));
 927                         break;
 928                 default:
 929                         elog(ERROR, "unrecognized strategy number: %d", strategy);
 930                         retval = false;         /* keep compiler quiet */
 931                         break;
 932         }
 933         return retval;
 934 }
 935
 936 static double
 937 size_box(BOX *box)
 938 {
 939         if (box->high.x <= box->low.x || box->high.y <= box->low.y)
 940                 return 0.0;
 941         return (box->high.x - box->low.x) * (box->high.y - box->low.y);
 942 }
 943
 944 /*****************************************
 945  * Common rtree functions (for boxes, polygons, and circles)
 946  *****************************************/
 947
 948 /*
 949  * Internal-page consistency for all these types
 950  *
 951  * We can use the same function since all types use bounding boxes as the
 952  * internal-page representation.
 953  */
 954 static bool
 955 rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy)
 956 {
 957         bool            retval;
 958
 959         switch (strategy)
 960         {
 961                 case RTLeftStrategyNumber:
 962                         retval = !DatumGetBool(DirectFunctionCall2(box_overright,
 963                                                                                                            PointerGetDatum(key),
 964                                                                                                         PointerGetDatum(query)));
 965                         break;
 966                 case RTOverLeftStrategyNumber:
 967                         retval = !DatumGetBool(DirectFunctionCall2(box_right,
 968                                                                                                            PointerGetDatum(key),
 969                                                                                                         PointerGetDatum(query)));
 970                         break;
 971                 case RTOverlapStrategyNumber:
 972                         retval = DatumGetBool(DirectFunctionCall2(box_overlap,
 973                                                                                                           PointerGetDatum(key),
 974                                                                                                         PointerGetDatum(query)));
 975                         break;
 976                 case RTOverRightStrategyNumber:
 977                         retval = !DatumGetBool(DirectFunctionCall2(box_left,
 978                                                                                                            PointerGetDatum(key),
 979                                                                                                         PointerGetDatum(query)));
 980                         break;
 981                 case RTRightStrategyNumber:
 982                         retval = !DatumGetBool(DirectFunctionCall2(box_overleft,
 983                                                                                                            PointerGetDatum(key),
 984                                                                                                         PointerGetDatum(query)));
 985                         break;
 986                 case RTSameStrategyNumber:
 987                 case RTContainsStrategyNumber:
 988                 case RTOldContainsStrategyNumber:
 989                         retval = DatumGetBool(DirectFunctionCall2(box_contain,
 990                                                                                                           PointerGetDatum(key),
 991                                                                                                         PointerGetDatum(query)));
 992                         break;
 993                 case RTContainedByStrategyNumber:
 994                 case RTOldContainedByStrategyNumber:
 995                         retval = DatumGetBool(DirectFunctionCall2(box_overlap,
 996                                                                                                           PointerGetDatum(key),
 997                                                                                                         PointerGetDatum(query)));
 998                         break;
 999                 case RTOverBelowStrategyNumber:
1000                         retval = !DatumGetBool(DirectFunctionCall2(box_above,
1001                                                                                                            PointerGetDatum(key),
1002                                                                                                         PointerGetDatum(query)));
1003                         break;
1004                 case RTBelowStrategyNumber:
1005                         retval = !DatumGetBool(DirectFunctionCall2(box_overabove,
1006                                                                                                            PointerGetDatum(key),
1007                                                                                                         PointerGetDatum(query)));
1008                         break;
1009                 case RTAboveStrategyNumber:
1010                         retval = !DatumGetBool(DirectFunctionCall2(box_overbelow,
1011                                                                                                            PointerGetDatum(key),
1012                                                                                                         PointerGetDatum(query)));
1013                         break;
1014                 case RTOverAboveStrategyNumber:
1015                         retval = !DatumGetBool(DirectFunctionCall2(box_below,
1016                                                                                                            PointerGetDatum(key),
1017                                                                                                         PointerGetDatum(query)));
1018                         break;
1019                 default:
1020                         elog(ERROR, "unrecognized strategy number: %d", strategy);
1021                         retval = false;         /* keep compiler quiet */
1022                         break;
1023         }
1024         return retval;
1025 }
1026
1027 /**************************************************
1028  * Polygon ops
1029  **************************************************/
1030
1031 /*
1032  * GiST compress for polygons: represent a polygon by its bounding box
1033  */
1034 Datum
1035 gist_poly_compress(PG_FUNCTION_ARGS)
1036 {
1037         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1038         GISTENTRY  *retval;
1039
1040         if (entry->leafkey)
1041         {
1042                 POLYGON    *in = DatumGetPolygonP(entry->key);
1043                 BOX                *r;
1044
1045                 r = (BOX *) palloc(sizeof(BOX));
1046                 memcpy((void *) r, (void *) &(in->boundbox), sizeof(BOX));
1047
1048                 retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
1049                 gistentryinit(*retval, PointerGetDatum(r),
1050                                           entry->rel, entry->page,
1051                                           entry->offset, FALSE);
1052         }
1053         else
1054                 retval = entry;
1055         PG_RETURN_POINTER(retval);
1056 }
1057
1058 /*
1059  * The GiST Consistent method for polygons
1060  */
1061 Datum
1062 gist_poly_consistent(PG_FUNCTION_ARGS)
1063 {
1064         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1065         POLYGON    *query = PG_GETARG_POLYGON_P(1);
1066         StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1067
1068         /* Oid          subtype = PG_GETARG_OID(3); */
1069         bool       *recheck = (bool *) PG_GETARG_POINTER(4);
1070         bool            result;
1071
1072         /* All cases served by this function are inexact */
1073         *recheck = true;
1074
1075         if (DatumGetBoxP(entry->key) == NULL || query == NULL)
1076                 PG_RETURN_BOOL(FALSE);
1077
1078         /*
1079          * Since the operators require recheck anyway, we can just use
1080          * rtree_internal_consistent even at leaf nodes.  (This works in part
1081          * because the index entries are bounding boxes not polygons.)
1082          */
1083         result = rtree_internal_consistent(DatumGetBoxP(entry->key),
1084                                                                            &(query->boundbox), strategy);
1085
1086         /* Avoid memory leak if supplied poly is toasted */
1087         PG_FREE_IF_COPY(query, 1);
1088
1089         PG_RETURN_BOOL(result);
1090 }
1091
1092 /**************************************************
1093  * Circle ops
1094  **************************************************/
1095
1096 /*
1097  * GiST compress for circles: represent a circle by its bounding box
1098  */
1099 Datum
1100 gist_circle_compress(PG_FUNCTION_ARGS)
1101 {
1102         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1103         GISTENTRY  *retval;
1104
1105         if (entry->leafkey)
1106         {
1107                 CIRCLE     *in = DatumGetCircleP(entry->key);
1108                 BOX                *r;
1109
1110                 r = (BOX *) palloc(sizeof(BOX));
1111                 r->high.x = in->center.x + in->radius;
1112                 r->low.x = in->center.x - in->radius;
1113                 r->high.y = in->center.y + in->radius;
1114                 r->low.y = in->center.y - in->radius;
1115
1116                 retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
1117                 gistentryinit(*retval, PointerGetDatum(r),
1118                                           entry->rel, entry->page,
1119                                           entry->offset, FALSE);
1120         }
1121         else
1122                 retval = entry;
1123         PG_RETURN_POINTER(retval);
1124 }
1125
1126 /*
1127  * The GiST Consistent method for circles
1128  */
1129 Datum
1130 gist_circle_consistent(PG_FUNCTION_ARGS)
1131 {
1132         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1133         CIRCLE     *query = PG_GETARG_CIRCLE_P(1);
1134         StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1135
1136         /* Oid          subtype = PG_GETARG_OID(3); */
1137         bool       *recheck = (bool *) PG_GETARG_POINTER(4);
1138         BOX                     bbox;
1139         bool            result;
1140
1141         /* All cases served by this function are inexact */
1142         *recheck = true;
1143
1144         if (DatumGetBoxP(entry->key) == NULL || query == NULL)
1145                 PG_RETURN_BOOL(FALSE);
1146
1147         /*
1148          * Since the operators require recheck anyway, we can just use
1149          * rtree_internal_consistent even at leaf nodes.  (This works in part
1150          * because the index entries are bounding boxes not circles.)
1151          */
1152         bbox.high.x = query->center.x + query->radius;
1153         bbox.low.x = query->center.x - query->radius;
1154         bbox.high.y = query->center.y + query->radius;
1155         bbox.low.y = query->center.y - query->radius;
1156
1157         result = rtree_internal_consistent(DatumGetBoxP(entry->key),
1158                                                                            &bbox, strategy);
1159
1160         PG_RETURN_BOOL(result);
1161 }
1162
1163 /**************************************************
1164  * Point ops
1165  **************************************************/
1166
1167 Datum
1168 gist_point_compress(PG_FUNCTION_ARGS)
1169 {
1170         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1171
1172         if (entry->leafkey)                     /* Point, actually */
1173         {
1174                 BOX                *box = palloc(sizeof(BOX));
1175                 Point      *point = DatumGetPointP(entry->key);
1176                 GISTENTRY  *retval = palloc(sizeof(GISTENTRY));
1177
1178                 box->high = box->low = *point;
1179
1180                 gistentryinit(*retval, BoxPGetDatum(box),
1181                                           entry->rel, entry->page, entry->offset, FALSE);
1182
1183                 PG_RETURN_POINTER(retval);
1184         }
1185
1186         PG_RETURN_POINTER(entry);
1187 }
1188
1189 #define point_point_distance(p1,p2) \
1190         DatumGetFloat8(DirectFunctionCall2(point_distance, \
1191                                                                            PointPGetDatum(p1), PointPGetDatum(p2)))
1192
1193 static double
1194 computeDistance(bool isLeaf, BOX *box, Point *point)
1195 {
1196         double          result = 0.0;
1197
1198         if (isLeaf)
1199         {
1200                 /* simple point to point distance */
1201                 result = point_point_distance(point, &box->low);
1202         }
1203         else if (point->x <= box->high.x && point->x >= box->low.x &&
1204                          point->y <= box->high.y && point->y >= box->low.y)
1205         {
1206                 /* point inside the box */
1207                 result = 0.0;
1208         }
1209         else if (point->x <= box->high.x && point->x >= box->low.x)
1210         {
1211                 /* point is over or below box */
1212                 Assert(box->low.y <= box->high.y);
1213                 if (point->y > box->high.y)
1214                         result = point->y - box->high.y;
1215                 else if (point->y < box->low.y)
1216                         result = box->low.y - point->y;
1217                 else
1218                         elog(ERROR, "inconsistent point values");
1219         }
1220         else if (point->y <= box->high.y && point->y >= box->low.y)
1221         {
1222                 /* point is to left or right of box */
1223                 Assert(box->low.x <= box->high.x);
1224                 if (point->x > box->high.x)
1225                         result = point->x - box->high.x;
1226                 else if (point->x < box->low.x)
1227                         result = box->low.x - point->x;
1228                 else
1229                         elog(ERROR, "inconsistent point values");
1230         }
1231         else
1232         {
1233                 /* closest point will be a vertex */
1234                 Point           p;
1235                 double          subresult;
1236
1237                 result = point_point_distance(point, &box->low);
1238
1239                 subresult = point_point_distance(point, &box->high);
1240                 if (result > subresult)
1241                         result = subresult;
1242
1243                 p.x = box->low.x;
1244                 p.y = box->high.y;
1245                 subresult = point_point_distance(point, &p);
1246                 if (result > subresult)
1247                         result = subresult;
1248
1249                 p.x = box->high.x;
1250                 p.y = box->low.y;
1251                 subresult = point_point_distance(point, &p);
1252                 if (result > subresult)
1253                         result = subresult;
1254         }
1255
1256         return result;
1257 }
1258
1259 static bool
1260 gist_point_consistent_internal(StrategyNumber strategy,
1261                                                            bool isLeaf, BOX *key, Point *query)
1262 {
1263         bool            result = false;
1264
1265         switch (strategy)
1266         {
1267                 case RTLeftStrategyNumber:
1268                         result = FPlt(key->low.x, query->x);
1269                         break;
1270                 case RTRightStrategyNumber:
1271                         result = FPgt(key->high.x, query->x);
1272                         break;
1273                 case RTAboveStrategyNumber:
1274                         result = FPgt(key->high.y, query->y);
1275                         break;
1276                 case RTBelowStrategyNumber:
1277                         result = FPlt(key->low.y, query->y);
1278                         break;
1279                 case RTSameStrategyNumber:
1280                         if (isLeaf)
1281                         {
1282                                 /* key.high must equal key.low, so we can disregard it */
1283                                 result = (FPeq(key->low.x, query->x) &&
1284                                                   FPeq(key->low.y, query->y));
1285                         }
1286                         else
1287                         {
1288                                 result = (FPle(query->x, key->high.x) &&
1289                                                   FPge(query->x, key->low.x) &&
1290                                                   FPle(query->y, key->high.y) &&
1291                                                   FPge(query->y, key->low.y));
1292                         }
1293                         break;
1294                 default:
1295                         elog(ERROR, "unrecognized strategy number: %d", strategy);
1296                         result = false;         /* keep compiler quiet */
1297                         break;
1298         }
1299
1300         return result;
1301 }
1302
1303 #define GeoStrategyNumberOffset         20
1304 #define PointStrategyNumberGroup        0
1305 #define BoxStrategyNumberGroup          1
1306 #define PolygonStrategyNumberGroup      2
1307 #define CircleStrategyNumberGroup       3
1308
1309 Datum
1310 gist_point_consistent(PG_FUNCTION_ARGS)
1311 {
1312         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1313         StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1314         bool       *recheck = (bool *) PG_GETARG_POINTER(4);
1315         bool            result;
1316         StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1317
1318         switch (strategyGroup)
1319         {
1320                 case PointStrategyNumberGroup:
1321                         result = gist_point_consistent_internal(strategy % GeoStrategyNumberOffset,
1322                                                                                                         GIST_LEAF(entry),
1323                                                                                                         DatumGetBoxP(entry->key),
1324                                                                                                         PG_GETARG_POINT_P(1));
1325                         *recheck = false;
1326                         break;
1327                 case BoxStrategyNumberGroup:
1328                         {
1329                                 /*
1330                                  * The only operator in this group is point <@ box (on_pb), so
1331                                  * we needn't examine strategy again.
1332                                  *
1333                                  * For historical reasons, on_pb uses exact rather than fuzzy
1334                                  * comparisons.  We could use box_overlap when at an internal
1335                                  * page, but that would lead to possibly visiting child pages
1336                                  * uselessly, because box_overlap uses fuzzy comparisons.
1337                                  * Instead we write a non-fuzzy overlap test.  The same code
1338                                  * will also serve for leaf-page tests, since leaf keys have
1339                                  * high == low.
1340                                  */
1341                                 BOX                *query,
1342                                                    *key;
1343
1344                                 query = PG_GETARG_BOX_P(1);
1345                                 key = DatumGetBoxP(entry->key);
1346
1347                                 result = (key->high.x >= query->low.x &&
1348                                                   key->low.x <= query->high.x &&
1349                                                   key->high.y >= query->low.y &&
1350                                                   key->low.y <= query->high.y);
1351                                 *recheck = false;
1352                         }
1353                         break;
1354                 case PolygonStrategyNumberGroup:
1355                         {
1356                                 POLYGON    *query = PG_GETARG_POLYGON_P(1);
1357
1358                                 result = DatumGetBool(DirectFunctionCall5(
1359                                                                                                                 gist_poly_consistent,
1360                                                                                                           PointerGetDatum(entry),
1361                                                                                                          PolygonPGetDatum(query),
1362                                                                           Int16GetDatum(RTOverlapStrategyNumber),
1363                                                                                            0, PointerGetDatum(recheck)));
1364
1365                                 if (GIST_LEAF(entry) && result)
1366                                 {
1367                                         /*
1368                                          * We are on leaf page and quick check shows overlapping
1369                                          * of polygon's bounding box and point
1370                                          */
1371                                         BOX                *box = DatumGetBoxP(entry->key);
1372
1373                                         Assert(box->high.x == box->low.x
1374                                                    && box->high.y == box->low.y);
1375                                         result = DatumGetBool(DirectFunctionCall2(
1376                                                                                                                           poly_contain_pt,
1377                                                                                                          PolygonPGetDatum(query),
1378                                                                                                 PointPGetDatum(&box->high)));
1379                                         *recheck = false;
1380                                 }
1381                         }
1382                         break;
1383                 case CircleStrategyNumberGroup:
1384                         {
1385                                 CIRCLE     *query = PG_GETARG_CIRCLE_P(1);
1386
1387                                 result = DatumGetBool(DirectFunctionCall5(
1388                                                                                                           gist_circle_consistent,
1389                                                                                                           PointerGetDatum(entry),
1390                                                                                                           CirclePGetDatum(query),
1391                                                                           Int16GetDatum(RTOverlapStrategyNumber),
1392                                                                                            0, PointerGetDatum(recheck)));
1393
1394                                 if (GIST_LEAF(entry) && result)
1395                                 {
1396                                         /*
1397                                          * We are on leaf page and quick check shows overlapping
1398                                          * of polygon's bounding box and point
1399                                          */
1400                                         BOX                *box = DatumGetBoxP(entry->key);
1401
1402                                         Assert(box->high.x == box->low.x
1403                                                    && box->high.y == box->low.y);
1404                                         result = DatumGetBool(DirectFunctionCall2(
1405                                                                                                                    circle_contain_pt,
1406                                                                                                           CirclePGetDatum(query),
1407                                                                                                 PointPGetDatum(&box->high)));
1408                                         *recheck = false;
1409                                 }
1410                         }
1411                         break;
1412                 default:
1413                         elog(ERROR, "unrecognized strategy number: %d", strategy);
1414                         result = false;         /* keep compiler quiet */
1415                         break;
1416         }
1417
1418         PG_RETURN_BOOL(result);
1419 }
1420
1421 Datum
1422 gist_point_distance(PG_FUNCTION_ARGS)
1423 {
1424         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1425         StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1426         double          distance;
1427         StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1428
1429         switch (strategyGroup)
1430         {
1431                 case PointStrategyNumberGroup:
1432                         distance = computeDistance(GIST_LEAF(entry),
1433                                                                            DatumGetBoxP(entry->key),
1434                                                                            PG_GETARG_POINT_P(1));
1435                         break;
1436                 default:
1437                         elog(ERROR, "unrecognized strategy number: %d", strategy);
1438                         distance = 0.0;         /* keep compiler quiet */
1439                         break;
1440         }
1441
1442         PG_RETURN_FLOAT8(distance);
1443 }