LCOV - code coverage report
Current view: top level - src/backend/access/gist - gistproc.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 422 492 85.8 %
Date: 2019-11-13 21:06:57 Functions: 30 31 96.8 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13