LCOV - code coverage report
Current view: top level - src/backend/utils/adt - rangetypes_spgist.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13beta1 Lines: 279 328 85.1 %
Date: 2020-06-01 09:07:10 Functions: 9 9 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * rangetypes_spgist.c
       4             :  *    implementation of quad tree over ranges mapped to 2d-points for SP-GiST.
       5             :  *
       6             :  * Quad tree is a data structure similar to a binary tree, but is adapted to
       7             :  * 2d data. Each inner node of a quad tree contains a point (centroid) which
       8             :  * divides the 2d-space into 4 quadrants. Each quadrant is associated with a
       9             :  * child node.
      10             :  *
      11             :  * Ranges are mapped to 2d-points so that the lower bound is one dimension,
      12             :  * and the upper bound is another. By convention, we visualize the lower bound
      13             :  * to be the horizontal axis, and upper bound the vertical axis.
      14             :  *
      15             :  * One quirk with this mapping is the handling of empty ranges. An empty range
      16             :  * doesn't have lower and upper bounds, so it cannot be mapped to 2d space in
      17             :  * a straightforward way. To cope with that, the root node can have a 5th
      18             :  * quadrant, which is reserved for empty ranges. Furthermore, there can be
      19             :  * inner nodes in the tree with no centroid. They contain only two child nodes,
      20             :  * one for empty ranges and another for non-empty ones. Such a node can appear
      21             :  * as the root node, or in the tree under the 5th child of the root node (in
      22             :  * which case it will only contain empty nodes).
      23             :  *
      24             :  * The SP-GiST picksplit function uses medians along both axes as the centroid.
      25             :  * This implementation only uses the comparison function of the range element
      26             :  * datatype, therefore it works for any range type.
      27             :  *
      28             :  * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
      29             :  * Portions Copyright (c) 1994, Regents of the University of California
      30             :  *
      31             :  * IDENTIFICATION
      32             :  *          src/backend/utils/adt/rangetypes_spgist.c
      33             :  *
      34             :  *-------------------------------------------------------------------------
      35             :  */
      36             : 
      37             : #include "postgres.h"
      38             : 
      39             : #include "access/spgist.h"
      40             : #include "access/stratnum.h"
      41             : #include "catalog/pg_type.h"
      42             : #include "utils/builtins.h"
      43             : #include "utils/datum.h"
      44             : #include "utils/rangetypes.h"
      45             : 
      46             : static int16 getQuadrant(TypeCacheEntry *typcache, const RangeType *centroid,
      47             :                          const RangeType *tst);
      48             : static int  bound_cmp(const void *a, const void *b, void *arg);
      49             : 
      50             : static int  adjacent_inner_consistent(TypeCacheEntry *typcache,
      51             :                                       const RangeBound *arg, const RangeBound *centroid,
      52             :                                       const RangeBound *prev);
      53             : static int  adjacent_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *arg,
      54             :                                 const RangeBound *centroid);
      55             : 
      56             : /*
      57             :  * SP-GiST 'config' interface function.
      58             :  */
      59             : Datum
      60          26 : spg_range_quad_config(PG_FUNCTION_ARGS)
      61             : {
      62             :     /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
      63          26 :     spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
      64             : 
      65          26 :     cfg->prefixType = ANYRANGEOID;
      66          26 :     cfg->labelType = VOIDOID;    /* we don't need node labels */
      67          26 :     cfg->canReturnData = true;
      68          26 :     cfg->longValuesOK = false;
      69          26 :     PG_RETURN_VOID();
      70             : }
      71             : 
      72             : /*----------
      73             :  * Determine which quadrant a 2d-mapped range falls into, relative to the
      74             :  * centroid.
      75             :  *
      76             :  * Quadrants are numbered like this:
      77             :  *
      78             :  *   4  |  1
      79             :  *  ----+----
      80             :  *   3  |  2
      81             :  *
      82             :  * Where the lower bound of range is the horizontal axis and upper bound the
      83             :  * vertical axis.
      84             :  *
      85             :  * Ranges on one of the axes are taken to lie in the quadrant with higher value
      86             :  * along perpendicular axis. That is, a value on the horizontal axis is taken
      87             :  * to belong to quadrant 1 or 4, and a value on the vertical axis is taken to
      88             :  * belong to quadrant 1 or 2. A range equal to centroid is taken to lie in
      89             :  * quadrant 1.
      90             :  *
      91             :  * Empty ranges are taken to lie in the special quadrant 5.
      92             :  *----------
      93             :  */
      94             : static int16
      95      808292 : getQuadrant(TypeCacheEntry *typcache, const RangeType *centroid, const RangeType *tst)
      96             : {
      97             :     RangeBound  centroidLower,
      98             :                 centroidUpper;
      99             :     bool        centroidEmpty;
     100             :     RangeBound  lower,
     101             :                 upper;
     102             :     bool        empty;
     103             : 
     104      808292 :     range_deserialize(typcache, centroid, &centroidLower, &centroidUpper,
     105             :                       &centroidEmpty);
     106      808292 :     range_deserialize(typcache, tst, &lower, &upper, &empty);
     107             : 
     108      808292 :     if (empty)
     109        8000 :         return 5;
     110             : 
     111      800292 :     if (range_cmp_bounds(typcache, &lower, &centroidLower) >= 0)
     112             :     {
     113      756830 :         if (range_cmp_bounds(typcache, &upper, &centroidUpper) >= 0)
     114      756742 :             return 1;
     115             :         else
     116          88 :             return 2;
     117             :     }
     118             :     else
     119             :     {
     120       43462 :         if (range_cmp_bounds(typcache, &upper, &centroidUpper) >= 0)
     121        9588 :             return 4;
     122             :         else
     123       33874 :             return 3;
     124             :     }
     125             : }
     126             : 
     127             : /*
     128             :  * Choose SP-GiST function: choose path for addition of new range.
     129             :  */
     130             : Datum
     131      781022 : spg_range_quad_choose(PG_FUNCTION_ARGS)
     132             : {
     133      781022 :     spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
     134      781022 :     spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
     135      781022 :     RangeType  *inRange = DatumGetRangeTypeP(in->datum),
     136             :                *centroid;
     137             :     int16       quadrant;
     138             :     TypeCacheEntry *typcache;
     139             : 
     140      781022 :     if (in->allTheSame)
     141             :     {
     142        8404 :         out->resultType = spgMatchNode;
     143             :         /* nodeN will be set by core */
     144        8404 :         out->result.matchNode.levelAdd = 0;
     145        8404 :         out->result.matchNode.restDatum = RangeTypePGetDatum(inRange);
     146        8404 :         PG_RETURN_VOID();
     147             :     }
     148             : 
     149      772618 :     typcache = range_get_typcache(fcinfo, RangeTypeGetOid(inRange));
     150             : 
     151             :     /*
     152             :      * A node with no centroid divides ranges purely on whether they're empty
     153             :      * or not. All empty ranges go to child node 0, all non-empty ranges go to
     154             :      * node 1.
     155             :      */
     156      772618 :     if (!in->hasPrefix)
     157             :     {
     158           0 :         out->resultType = spgMatchNode;
     159           0 :         if (RangeIsEmpty(inRange))
     160           0 :             out->result.matchNode.nodeN = 0;
     161             :         else
     162           0 :             out->result.matchNode.nodeN = 1;
     163           0 :         out->result.matchNode.levelAdd = 1;
     164           0 :         out->result.matchNode.restDatum = RangeTypePGetDatum(inRange);
     165           0 :         PG_RETURN_VOID();
     166             :     }
     167             : 
     168      772618 :     centroid = DatumGetRangeTypeP(in->prefixDatum);
     169      772618 :     quadrant = getQuadrant(typcache, centroid, inRange);
     170             : 
     171             :     Assert(quadrant <= in->nNodes);
     172             : 
     173             :     /* Select node matching to quadrant number */
     174      772618 :     out->resultType = spgMatchNode;
     175      772618 :     out->result.matchNode.nodeN = quadrant - 1;
     176      772618 :     out->result.matchNode.levelAdd = 1;
     177      772618 :     out->result.matchNode.restDatum = RangeTypePGetDatum(inRange);
     178             : 
     179      772618 :     PG_RETURN_VOID();
     180             : }
     181             : 
     182             : /*
     183             :  * Bound comparison for sorting.
     184             :  */
     185             : static int
     186      584542 : bound_cmp(const void *a, const void *b, void *arg)
     187             : {
     188      584542 :     RangeBound *ba = (RangeBound *) a;
     189      584542 :     RangeBound *bb = (RangeBound *) b;
     190      584542 :     TypeCacheEntry *typcache = (TypeCacheEntry *) arg;
     191             : 
     192      584542 :     return range_cmp_bounds(typcache, ba, bb);
     193             : }
     194             : 
     195             : /*
     196             :  * Picksplit SP-GiST function: split ranges into nodes. Select "centroid"
     197             :  * range and distribute ranges according to quadrants.
     198             :  */
     199             : Datum
     200         440 : spg_range_quad_picksplit(PG_FUNCTION_ARGS)
     201             : {
     202         440 :     spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
     203         440 :     spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
     204             :     int         i;
     205             :     int         j;
     206             :     int         nonEmptyCount;
     207             :     RangeType  *centroid;
     208             :     bool        empty;
     209             :     TypeCacheEntry *typcache;
     210             : 
     211             :     /* Use the median values of lower and upper bounds as the centroid range */
     212             :     RangeBound *lowerBounds,
     213             :                *upperBounds;
     214             : 
     215         440 :     typcache = range_get_typcache(fcinfo,
     216         440 :                                   RangeTypeGetOid(DatumGetRangeTypeP(in->datums[0])));
     217             : 
     218             :     /* Allocate memory for bounds */
     219         440 :     lowerBounds = palloc(sizeof(RangeBound) * in->nTuples);
     220         440 :     upperBounds = palloc(sizeof(RangeBound) * in->nTuples);
     221         440 :     j = 0;
     222             : 
     223             :     /* Deserialize bounds of ranges, count non-empty ranges */
     224       41322 :     for (i = 0; i < in->nTuples; i++)
     225             :     {
     226       40882 :         range_deserialize(typcache, DatumGetRangeTypeP(in->datums[i]),
     227       40882 :                           &lowerBounds[j], &upperBounds[j], &empty);
     228       40882 :         if (!empty)
     229       35658 :             j++;
     230             :     }
     231         440 :     nonEmptyCount = j;
     232             : 
     233             :     /*
     234             :      * All the ranges are empty. The best we can do is to construct an inner
     235             :      * node with no centroid, and put all ranges into node 0. If non-empty
     236             :      * ranges are added later, they will be routed to node 1.
     237             :      */
     238         440 :     if (nonEmptyCount == 0)
     239             :     {
     240          52 :         out->nNodes = 2;
     241          52 :         out->hasPrefix = false;
     242             :         /* Prefix is empty */
     243          52 :         out->prefixDatum = PointerGetDatum(NULL);
     244          52 :         out->nodeLabels = NULL;
     245             : 
     246          52 :         out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
     247          52 :         out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
     248             : 
     249             :         /* Place all ranges into node 0 */
     250        5276 :         for (i = 0; i < in->nTuples; i++)
     251             :         {
     252        5224 :             RangeType  *range = DatumGetRangeTypeP(in->datums[i]);
     253             : 
     254        5224 :             out->leafTupleDatums[i] = RangeTypePGetDatum(range);
     255        5224 :             out->mapTuplesToNodes[i] = 0;
     256             :         }
     257          52 :         PG_RETURN_VOID();
     258             :     }
     259             : 
     260             :     /* Sort range bounds in order to find medians */
     261         388 :     qsort_arg(lowerBounds, nonEmptyCount, sizeof(RangeBound),
     262             :               bound_cmp, typcache);
     263         388 :     qsort_arg(upperBounds, nonEmptyCount, sizeof(RangeBound),
     264             :               bound_cmp, typcache);
     265             : 
     266             :     /* Construct "centroid" range from medians of lower and upper bounds */
     267         388 :     centroid = range_serialize(typcache, &lowerBounds[nonEmptyCount / 2],
     268         388 :                                &upperBounds[nonEmptyCount / 2], false);
     269         388 :     out->hasPrefix = true;
     270         388 :     out->prefixDatum = RangeTypePGetDatum(centroid);
     271             : 
     272             :     /* Create node for empty ranges only if it is a root node */
     273         388 :     out->nNodes = (in->level == 0) ? 5 : 4;
     274         388 :     out->nodeLabels = NULL;      /* we don't need node labels */
     275             : 
     276         388 :     out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
     277         388 :     out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
     278             : 
     279             :     /*
     280             :      * Assign ranges to corresponding nodes according to quadrants relative to
     281             :      * "centroid" range.
     282             :      */
     283       36046 :     for (i = 0; i < in->nTuples; i++)
     284             :     {
     285       35658 :         RangeType  *range = DatumGetRangeTypeP(in->datums[i]);
     286       35658 :         int16       quadrant = getQuadrant(typcache, centroid, range);
     287             : 
     288       35658 :         out->leafTupleDatums[i] = RangeTypePGetDatum(range);
     289       35658 :         out->mapTuplesToNodes[i] = quadrant - 1;
     290             :     }
     291             : 
     292         388 :     PG_RETURN_VOID();
     293             : }
     294             : 
     295             : /*
     296             :  * SP-GiST consistent function for inner nodes: check which nodes are
     297             :  * consistent with given set of queries.
     298             :  */
     299             : Datum
     300        1564 : spg_range_quad_inner_consistent(PG_FUNCTION_ARGS)
     301             : {
     302        1564 :     spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
     303        1564 :     spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
     304             :     int         which;
     305             :     int         i;
     306             :     MemoryContext oldCtx;
     307             : 
     308             :     /*
     309             :      * For adjacent search we need also previous centroid (if any) to improve
     310             :      * the precision of the consistent check. In this case needPrevious flag
     311             :      * is set and centroid is passed into traversalValue.
     312             :      */
     313        1564 :     bool        needPrevious = false;
     314             : 
     315        1564 :     if (in->allTheSame)
     316             :     {
     317             :         /* Report that all nodes should be visited */
     318         104 :         out->nNodes = in->nNodes;
     319         104 :         out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
     320         936 :         for (i = 0; i < in->nNodes; i++)
     321         832 :             out->nodeNumbers[i] = i;
     322         104 :         PG_RETURN_VOID();
     323             :     }
     324             : 
     325        1460 :     if (!in->hasPrefix)
     326             :     {
     327             :         /*
     328             :          * No centroid on this inner node. Such a node has two child nodes,
     329             :          * the first for empty ranges, and the second for non-empty ones.
     330             :          */
     331             :         Assert(in->nNodes == 2);
     332             : 
     333             :         /*
     334             :          * Nth bit of which variable means that (N - 1)th node should be
     335             :          * visited. Initially all bits are set. Bits of nodes which should be
     336             :          * skipped will be unset.
     337             :          */
     338           0 :         which = (1 << 1) | (1 << 2);
     339           0 :         for (i = 0; i < in->nkeys; i++)
     340             :         {
     341           0 :             StrategyNumber strategy = in->scankeys[i].sk_strategy;
     342             :             bool        empty;
     343             : 
     344             :             /*
     345             :              * The only strategy when second argument of operator is not range
     346             :              * is RANGESTRAT_CONTAINS_ELEM.
     347             :              */
     348           0 :             if (strategy != RANGESTRAT_CONTAINS_ELEM)
     349           0 :                 empty = RangeIsEmpty(DatumGetRangeTypeP(in->scankeys[i].sk_argument));
     350             :             else
     351           0 :                 empty = false;
     352             : 
     353           0 :             switch (strategy)
     354             :             {
     355           0 :                 case RANGESTRAT_BEFORE:
     356             :                 case RANGESTRAT_OVERLEFT:
     357             :                 case RANGESTRAT_OVERLAPS:
     358             :                 case RANGESTRAT_OVERRIGHT:
     359             :                 case RANGESTRAT_AFTER:
     360             :                 case RANGESTRAT_ADJACENT:
     361             :                     /* These strategies return false if any argument is empty */
     362           0 :                     if (empty)
     363           0 :                         which = 0;
     364             :                     else
     365           0 :                         which &= (1 << 2);
     366           0 :                     break;
     367             : 
     368           0 :                 case RANGESTRAT_CONTAINS:
     369             : 
     370             :                     /*
     371             :                      * All ranges contain an empty range. Only non-empty
     372             :                      * ranges can contain a non-empty range.
     373             :                      */
     374           0 :                     if (!empty)
     375           0 :                         which &= (1 << 2);
     376           0 :                     break;
     377             : 
     378           0 :                 case RANGESTRAT_CONTAINED_BY:
     379             : 
     380             :                     /*
     381             :                      * Only an empty range is contained by an empty range.
     382             :                      * Both empty and non-empty ranges can be contained by a
     383             :                      * non-empty range.
     384             :                      */
     385           0 :                     if (empty)
     386           0 :                         which &= (1 << 1);
     387           0 :                     break;
     388             : 
     389           0 :                 case RANGESTRAT_CONTAINS_ELEM:
     390           0 :                     which &= (1 << 2);
     391           0 :                     break;
     392             : 
     393           0 :                 case RANGESTRAT_EQ:
     394           0 :                     if (empty)
     395           0 :                         which &= (1 << 1);
     396             :                     else
     397           0 :                         which &= (1 << 2);
     398           0 :                     break;
     399             : 
     400           0 :                 default:
     401           0 :                     elog(ERROR, "unrecognized range strategy: %d", strategy);
     402             :                     break;
     403             :             }
     404           0 :             if (which == 0)
     405           0 :                 break;          /* no need to consider remaining conditions */
     406             :         }
     407             :     }
     408             :     else
     409             :     {
     410             :         RangeBound  centroidLower,
     411             :                     centroidUpper;
     412             :         bool        centroidEmpty;
     413             :         TypeCacheEntry *typcache;
     414             :         RangeType  *centroid;
     415             : 
     416             :         /* This node has a centroid. Fetch it. */
     417        1460 :         centroid = DatumGetRangeTypeP(in->prefixDatum);
     418        1460 :         typcache = range_get_typcache(fcinfo,
     419        1460 :                                       RangeTypeGetOid(DatumGetRangeTypeP(centroid)));
     420        1460 :         range_deserialize(typcache, centroid, &centroidLower, &centroidUpper,
     421             :                           &centroidEmpty);
     422             : 
     423             :         Assert(in->nNodes == 4 || in->nNodes == 5);
     424             : 
     425             :         /*
     426             :          * Nth bit of which variable means that (N - 1)th node (Nth quadrant)
     427             :          * should be visited. Initially all bits are set. Bits of nodes which
     428             :          * can be skipped will be unset.
     429             :          */
     430        1460 :         which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5);
     431             : 
     432        2920 :         for (i = 0; i < in->nkeys; i++)
     433             :         {
     434             :             StrategyNumber strategy;
     435             :             RangeBound  lower,
     436             :                         upper;
     437             :             bool        empty;
     438        1460 :             RangeType  *range = NULL;
     439             : 
     440        1460 :             RangeType  *prevCentroid = NULL;
     441             :             RangeBound  prevLower,
     442             :                         prevUpper;
     443             :             bool        prevEmpty;
     444             : 
     445             :             /* Restrictions on range bounds according to scan strategy */
     446        1460 :             RangeBound *minLower = NULL,
     447        1460 :                        *maxLower = NULL,
     448        1460 :                        *minUpper = NULL,
     449        1460 :                        *maxUpper = NULL;
     450             : 
     451             :             /* Are the restrictions on range bounds inclusive? */
     452        1460 :             bool        inclusive = true;
     453        1460 :             bool        strictEmpty = true;
     454             :             int         cmp,
     455             :                         which1,
     456             :                         which2;
     457             : 
     458        1460 :             strategy = in->scankeys[i].sk_strategy;
     459             : 
     460             :             /*
     461             :              * RANGESTRAT_CONTAINS_ELEM is just like RANGESTRAT_CONTAINS, but
     462             :              * the argument is a single element. Expand the single element to
     463             :              * a range containing only the element, and treat it like
     464             :              * RANGESTRAT_CONTAINS.
     465             :              */
     466        1460 :             if (strategy == RANGESTRAT_CONTAINS_ELEM)
     467             :             {
     468          24 :                 lower.inclusive = true;
     469          24 :                 lower.infinite = false;
     470          24 :                 lower.lower = true;
     471          24 :                 lower.val = in->scankeys[i].sk_argument;
     472             : 
     473          24 :                 upper.inclusive = true;
     474          24 :                 upper.infinite = false;
     475          24 :                 upper.lower = false;
     476          24 :                 upper.val = in->scankeys[i].sk_argument;
     477             : 
     478          24 :                 empty = false;
     479             : 
     480          24 :                 strategy = RANGESTRAT_CONTAINS;
     481             :             }
     482             :             else
     483             :             {
     484        1436 :                 range = DatumGetRangeTypeP(in->scankeys[i].sk_argument);
     485        1436 :                 range_deserialize(typcache, range, &lower, &upper, &empty);
     486             :             }
     487             : 
     488             :             /*
     489             :              * Most strategies are handled by forming a bounding box from the
     490             :              * search key, defined by a minLower, maxLower, minUpper,
     491             :              * maxUpper. Some modify 'which' directly, to specify exactly
     492             :              * which quadrants need to be visited.
     493             :              *
     494             :              * For most strategies, nothing matches an empty search key, and
     495             :              * an empty range never matches a non-empty key. If a strategy
     496             :              * does not behave like that wrt. empty ranges, set strictEmpty to
     497             :              * false.
     498             :              */
     499        1460 :             switch (strategy)
     500             :             {
     501          24 :                 case RANGESTRAT_BEFORE:
     502             : 
     503             :                     /*
     504             :                      * Range A is before range B if upper bound of A is lower
     505             :                      * than lower bound of B.
     506             :                      */
     507          24 :                     maxUpper = &lower;
     508          24 :                     inclusive = false;
     509          24 :                     break;
     510             : 
     511         104 :                 case RANGESTRAT_OVERLEFT:
     512             : 
     513             :                     /*
     514             :                      * Range A is overleft to range B if upper bound of A is
     515             :                      * less or equal to upper bound of B.
     516             :                      */
     517         104 :                     maxUpper = &upper;
     518         104 :                     break;
     519             : 
     520          24 :                 case RANGESTRAT_OVERLAPS:
     521             : 
     522             :                     /*
     523             :                      * Non-empty ranges overlap, if lower bound of each range
     524             :                      * is lower or equal to upper bound of the other range.
     525             :                      */
     526          24 :                     maxLower = &upper;
     527          24 :                     minUpper = &lower;
     528          24 :                     break;
     529             : 
     530         364 :                 case RANGESTRAT_OVERRIGHT:
     531             : 
     532             :                     /*
     533             :                      * Range A is overright to range B if lower bound of A is
     534             :                      * greater or equal to lower bound of B.
     535             :                      */
     536         364 :                     minLower = &lower;
     537         364 :                     break;
     538             : 
     539         364 :                 case RANGESTRAT_AFTER:
     540             : 
     541             :                     /*
     542             :                      * Range A is after range B if lower bound of A is greater
     543             :                      * than upper bound of B.
     544             :                      */
     545         364 :                     minLower = &upper;
     546         364 :                     inclusive = false;
     547         364 :                     break;
     548             : 
     549         108 :                 case RANGESTRAT_ADJACENT:
     550         108 :                     if (empty)
     551           0 :                         break;  /* Skip to strictEmpty check. */
     552             : 
     553             :                     /*
     554             :                      * Previously selected quadrant could exclude possibility
     555             :                      * for lower or upper bounds to be adjacent. Deserialize
     556             :                      * previous centroid range if present for checking this.
     557             :                      */
     558         108 :                     if (in->traversalValue)
     559             :                     {
     560          96 :                         prevCentroid = DatumGetRangeTypeP(in->traversalValue);
     561          96 :                         range_deserialize(typcache, prevCentroid,
     562             :                                           &prevLower, &prevUpper, &prevEmpty);
     563             :                     }
     564             : 
     565             :                     /*
     566             :                      * For a range's upper bound to be adjacent to the
     567             :                      * argument's lower bound, it will be found along the line
     568             :                      * adjacent to (and just below) Y=lower. Therefore, if the
     569             :                      * argument's lower bound is less than the centroid's
     570             :                      * upper bound, the line falls in quadrants 2 and 3; if
     571             :                      * greater, the line falls in quadrants 1 and 4. (see
     572             :                      * adjacent_cmp_bounds for description of edge cases).
     573             :                      */
     574         108 :                     cmp = adjacent_inner_consistent(typcache, &lower,
     575             :                                                     &centroidUpper,
     576             :                                                     prevCentroid ? &prevUpper : NULL);
     577         108 :                     if (cmp > 0)
     578          16 :                         which1 = (1 << 1) | (1 << 4);
     579          92 :                     else if (cmp < 0)
     580          16 :                         which1 = (1 << 2) | (1 << 3);
     581             :                     else
     582          76 :                         which1 = 0;
     583             : 
     584             :                     /*
     585             :                      * Also search for ranges's adjacent to argument's upper
     586             :                      * bound. They will be found along the line adjacent to
     587             :                      * (and just right of) X=upper, which falls in quadrants 3
     588             :                      * and 4, or 1 and 2.
     589             :                      */
     590         108 :                     cmp = adjacent_inner_consistent(typcache, &upper,
     591             :                                                     &centroidLower,
     592             :                                                     prevCentroid ? &prevLower : NULL);
     593         108 :                     if (cmp > 0)
     594          84 :                         which2 = (1 << 1) | (1 << 2);
     595          24 :                     else if (cmp < 0)
     596          16 :                         which2 = (1 << 3) | (1 << 4);
     597             :                     else
     598           8 :                         which2 = 0;
     599             : 
     600             :                     /* We must chase down ranges adjacent to either bound. */
     601         108 :                     which &= which1 | which2;
     602             : 
     603         108 :                     needPrevious = true;
     604         108 :                     break;
     605             : 
     606         436 :                 case RANGESTRAT_CONTAINS:
     607             : 
     608             :                     /*
     609             :                      * Non-empty range A contains non-empty range B if lower
     610             :                      * bound of A is lower or equal to lower bound of range B
     611             :                      * and upper bound of range A is greater or equal to upper
     612             :                      * bound of range A.
     613             :                      *
     614             :                      * All non-empty ranges contain an empty range.
     615             :                      */
     616         436 :                     strictEmpty = false;
     617         436 :                     if (!empty)
     618             :                     {
     619          48 :                         which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
     620          48 :                         maxLower = &lower;
     621          48 :                         minUpper = &upper;
     622             :                     }
     623         436 :                     break;
     624             : 
     625          20 :                 case RANGESTRAT_CONTAINED_BY:
     626             :                     /* The opposite of contains. */
     627          20 :                     strictEmpty = false;
     628          20 :                     if (empty)
     629             :                     {
     630             :                         /* An empty range is only contained by an empty range */
     631           0 :                         which &= (1 << 5);
     632             :                     }
     633             :                     else
     634             :                     {
     635          20 :                         minLower = &lower;
     636          20 :                         maxUpper = &upper;
     637             :                     }
     638          20 :                     break;
     639             : 
     640          16 :                 case RANGESTRAT_EQ:
     641             : 
     642             :                     /*
     643             :                      * Equal range can be only in the same quadrant where
     644             :                      * argument would be placed to.
     645             :                      */
     646          16 :                     strictEmpty = false;
     647          16 :                     which &= (1 << getQuadrant(typcache, centroid, range));
     648          16 :                     break;
     649             : 
     650           0 :                 default:
     651           0 :                     elog(ERROR, "unrecognized range strategy: %d", strategy);
     652             :                     break;
     653             :             }
     654             : 
     655        1460 :             if (strictEmpty)
     656             :             {
     657         988 :                 if (empty)
     658             :                 {
     659             :                     /* Scan key is empty, no branches are satisfying */
     660           0 :                     which = 0;
     661           0 :                     break;
     662             :                 }
     663             :                 else
     664             :                 {
     665             :                     /* Shouldn't visit tree branch with empty ranges */
     666         988 :                     which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
     667             :                 }
     668             :             }
     669             : 
     670             :             /*
     671             :              * Using the bounding box, see which quadrants we have to descend
     672             :              * into.
     673             :              */
     674        1460 :             if (minLower)
     675             :             {
     676             :                 /*
     677             :                  * If the centroid's lower bound is less than or equal to the
     678             :                  * minimum lower bound, anything in the 3rd and 4th quadrants
     679             :                  * will have an even smaller lower bound, and thus can't
     680             :                  * match.
     681             :                  */
     682         748 :                 if (range_cmp_bounds(typcache, &centroidLower, minLower) <= 0)
     683          80 :                     which &= (1 << 1) | (1 << 2) | (1 << 5);
     684             :             }
     685        1460 :             if (maxLower)
     686             :             {
     687             :                 /*
     688             :                  * If the centroid's lower bound is greater than the maximum
     689             :                  * lower bound, anything in the 1st and 2nd quadrants will
     690             :                  * also have a greater than or equal lower bound, and thus
     691             :                  * can't match. If the centroid's lower bound is equal to the
     692             :                  * maximum lower bound, we can still exclude the 1st and 2nd
     693             :                  * quadrants if we're looking for a value strictly greater
     694             :                  * than the maximum.
     695             :                  */
     696             :                 int         cmp;
     697             : 
     698          72 :                 cmp = range_cmp_bounds(typcache, &centroidLower, maxLower);
     699          72 :                 if (cmp > 0 || (!inclusive && cmp == 0))
     700          68 :                     which &= (1 << 3) | (1 << 4) | (1 << 5);
     701             :             }
     702        1460 :             if (minUpper)
     703             :             {
     704             :                 /*
     705             :                  * If the centroid's upper bound is less than or equal to the
     706             :                  * minimum upper bound, anything in the 2nd and 3rd quadrants
     707             :                  * will have an even smaller upper bound, and thus can't
     708             :                  * match.
     709             :                  */
     710          72 :                 if (range_cmp_bounds(typcache, &centroidUpper, minUpper) <= 0)
     711           0 :                     which &= (1 << 1) | (1 << 4) | (1 << 5);
     712             :             }
     713        1460 :             if (maxUpper)
     714             :             {
     715             :                 /*
     716             :                  * If the centroid's upper bound is greater than the maximum
     717             :                  * upper bound, anything in the 1st and 4th quadrants will
     718             :                  * also have a greater than or equal upper bound, and thus
     719             :                  * can't match. If the centroid's upper bound is equal to the
     720             :                  * maximum upper bound, we can still exclude the 1st and 4th
     721             :                  * quadrants if we're looking for a value strictly greater
     722             :                  * than the maximum.
     723             :                  */
     724             :                 int         cmp;
     725             : 
     726         148 :                 cmp = range_cmp_bounds(typcache, &centroidUpper, maxUpper);
     727         148 :                 if (cmp > 0 || (!inclusive && cmp == 0))
     728          40 :                     which &= (1 << 2) | (1 << 3) | (1 << 5);
     729             :             }
     730             : 
     731        1460 :             if (which == 0)
     732           0 :                 break;          /* no need to consider remaining conditions */
     733             :         }
     734             :     }
     735             : 
     736             :     /* We must descend into the quadrant(s) identified by 'which' */
     737        1460 :     out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
     738        1460 :     if (needPrevious)
     739         108 :         out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
     740        1460 :     out->nNodes = 0;
     741             : 
     742             :     /*
     743             :      * Elements of traversalValues should be allocated in
     744             :      * traversalMemoryContext
     745             :      */
     746        1460 :     oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
     747             : 
     748        7392 :     for (i = 1; i <= in->nNodes; i++)
     749             :     {
     750        5932 :         if (which & (1 << i))
     751             :         {
     752             :             /* Save previous prefix if needed */
     753        5240 :             if (needPrevious)
     754             :             {
     755             :                 Datum       previousCentroid;
     756             : 
     757             :                 /*
     758             :                  * We know, that in->prefixDatum in this place is varlena,
     759             :                  * because it's range
     760             :                  */
     761         240 :                 previousCentroid = datumCopy(in->prefixDatum, false, -1);
     762         240 :                 out->traversalValues[out->nNodes] = (void *) previousCentroid;
     763             :             }
     764        5240 :             out->nodeNumbers[out->nNodes] = i - 1;
     765        5240 :             out->nNodes++;
     766             :         }
     767             :     }
     768             : 
     769        1460 :     MemoryContextSwitchTo(oldCtx);
     770             : 
     771        1460 :     PG_RETURN_VOID();
     772             : }
     773             : 
     774             : /*
     775             :  * adjacent_cmp_bounds
     776             :  *
     777             :  * Given an argument and centroid bound, this function determines if any
     778             :  * bounds that are adjacent to the argument are smaller than, or greater than
     779             :  * or equal to centroid. For brevity, we call the arg < centroid "left", and
     780             :  * arg >= centroid case "right". This corresponds to how the quadrants are
     781             :  * arranged, if you imagine that "left" is equivalent to "down" and "right"
     782             :  * is equivalent to "up".
     783             :  *
     784             :  * For the "left" case, returns -1, and for the "right" case, returns 1.
     785             :  */
     786             : static int
     787         324 : adjacent_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *arg,
     788             :                     const RangeBound *centroid)
     789             : {
     790             :     int         cmp;
     791             : 
     792             :     Assert(arg->lower != centroid->lower);
     793             : 
     794         324 :     cmp = range_cmp_bounds(typcache, arg, centroid);
     795             : 
     796         324 :     if (centroid->lower)
     797             :     {
     798             :         /*------
     799             :          * The argument is an upper bound, we are searching for adjacent lower
     800             :          * bounds. A matching adjacent lower bound must be *larger* than the
     801             :          * argument, but only just.
     802             :          *
     803             :          * The following table illustrates the desired result with a fixed
     804             :          * argument bound, and different centroids. The CMP column shows
     805             :          * the value of 'cmp' variable, and ADJ shows whether the argument
     806             :          * and centroid are adjacent, per bounds_adjacent(). (N) means we
     807             :          * don't need to check for that case, because it's implied by CMP.
     808             :          * With the argument range [..., 500), the adjacent range we're
     809             :          * searching for is [500, ...):
     810             :          *
     811             :          *  ARGUMENT   CENTROID     CMP   ADJ
     812             :          *  [..., 500) [498, ...)    >     (N)   [500, ...) is to the right
     813             :          *  [..., 500) [499, ...)    =    (N)   [500, ...) is to the right
     814             :          *  [..., 500) [500, ...)    <      Y    [500, ...) is to the right
     815             :          *  [..., 500) [501, ...)    <      N    [500, ...) is to the left
     816             :          *
     817             :          * So, we must search left when the argument is smaller than, and not
     818             :          * adjacent, to the centroid. Otherwise search right.
     819             :          *------
     820             :          */
     821         196 :         if (cmp < 0 && !bounds_adjacent(typcache, *arg, *centroid))
     822          24 :             return -1;
     823             :         else
     824         172 :             return 1;
     825             :     }
     826             :     else
     827             :     {
     828             :         /*------
     829             :          * The argument is a lower bound, we are searching for adjacent upper
     830             :          * bounds. A matching adjacent upper bound must be *smaller* than the
     831             :          * argument, but only just.
     832             :          *
     833             :          *  ARGUMENT   CENTROID     CMP   ADJ
     834             :          *  [500, ...) [..., 499)    >     (N)   [..., 500) is to the right
     835             :          *  [500, ...) [..., 500)    >     (Y)   [..., 500) is to the right
     836             :          *  [500, ...) [..., 501)    =    (N)   [..., 500) is to the left
     837             :          *  [500, ...) [..., 502)    <     (N)   [..., 500) is to the left
     838             :          *
     839             :          * We must search left when the argument is smaller than or equal to
     840             :          * the centroid. Otherwise search right. We don't need to check
     841             :          * whether the argument is adjacent with the centroid, because it
     842             :          * doesn't matter.
     843             :          *------
     844             :          */
     845         128 :         if (cmp <= 0)
     846         104 :             return -1;
     847             :         else
     848          24 :             return 1;
     849             :     }
     850             : }
     851             : 
     852             : /*----------
     853             :  * adjacent_inner_consistent
     854             :  *
     855             :  * Like adjacent_cmp_bounds, but also takes into account the previous
     856             :  * level's centroid. We might've traversed left (or right) at the previous
     857             :  * node, in search for ranges adjacent to the other bound, even though we
     858             :  * already ruled out the possibility for any matches in that direction for
     859             :  * this bound. By comparing the argument with the previous centroid, and
     860             :  * the previous centroid with the current centroid, we can determine which
     861             :  * direction we should've moved in at previous level, and which direction we
     862             :  * actually moved.
     863             :  *
     864             :  * If there can be any matches to the left, returns -1. If to the right,
     865             :  * returns 1. If there can be no matches below this centroid, because we
     866             :  * already ruled them out at the previous level, returns 0.
     867             :  *
     868             :  * XXX: Comparing just the previous and current level isn't foolproof; we
     869             :  * might still search some branches unnecessarily. For example, imagine that
     870             :  * we are searching for value 15, and we traverse the following centroids
     871             :  * (only considering one bound for the moment):
     872             :  *
     873             :  * Level 1: 20
     874             :  * Level 2: 50
     875             :  * Level 3: 25
     876             :  *
     877             :  * At this point, previous centroid is 50, current centroid is 25, and the
     878             :  * target value is to the left. But because we already moved right from
     879             :  * centroid 20 to 50 in the first level, there cannot be any values < 20 in
     880             :  * the current branch. But we don't know that just by looking at the previous
     881             :  * and current centroid, so we traverse left, unnecessarily. The reason we are
     882             :  * down this branch is that we're searching for matches with the *other*
     883             :  * bound. If we kept track of which bound we are searching for explicitly,
     884             :  * instead of deducing that from the previous and current centroid, we could
     885             :  * avoid some unnecessary work.
     886             :  *----------
     887             :  */
     888             : static int
     889         216 : adjacent_inner_consistent(TypeCacheEntry *typcache, const RangeBound *arg,
     890             :                           const RangeBound *centroid, const RangeBound *prev)
     891             : {
     892         216 :     if (prev)
     893             :     {
     894             :         int         prevcmp;
     895             :         int         cmp;
     896             : 
     897             :         /*
     898             :          * Which direction were we supposed to traverse at previous level,
     899             :          * left or right?
     900             :          */
     901         192 :         prevcmp = adjacent_cmp_bounds(typcache, arg, prev);
     902             : 
     903             :         /* and which direction did we actually go? */
     904         192 :         cmp = range_cmp_bounds(typcache, centroid, prev);
     905             : 
     906             :         /* if the two don't agree, there's nothing to see here */
     907         192 :         if ((prevcmp < 0 && cmp >= 0) || (prevcmp > 0 && cmp < 0))
     908          84 :             return 0;
     909             :     }
     910             : 
     911         132 :     return adjacent_cmp_bounds(typcache, arg, centroid);
     912             : }
     913             : 
     914             : /*
     915             :  * SP-GiST consistent function for leaf nodes: check leaf value against query
     916             :  * using corresponding function.
     917             :  */
     918             : Datum
     919      148308 : spg_range_quad_leaf_consistent(PG_FUNCTION_ARGS)
     920             : {
     921      148308 :     spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
     922      148308 :     spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
     923      148308 :     RangeType  *leafRange = DatumGetRangeTypeP(in->leafDatum);
     924             :     TypeCacheEntry *typcache;
     925             :     bool        res;
     926             :     int         i;
     927             : 
     928             :     /* all tests are exact */
     929      148308 :     out->recheck = false;
     930             : 
     931             :     /* leafDatum is what it is... */
     932      148308 :     out->leafValue = in->leafDatum;
     933             : 
     934      148308 :     typcache = range_get_typcache(fcinfo, RangeTypeGetOid(leafRange));
     935             : 
     936             :     /* Perform the required comparison(s) */
     937      148308 :     res = true;
     938      286192 :     for (i = 0; i < in->nkeys; i++)
     939             :     {
     940      148308 :         Datum       keyDatum = in->scankeys[i].sk_argument;
     941             : 
     942             :         /* Call the function corresponding to the scan strategy */
     943      148308 :         switch (in->scankeys[i].sk_strategy)
     944             :         {
     945        1568 :             case RANGESTRAT_BEFORE:
     946        1568 :                 res = range_before_internal(typcache, leafRange,
     947        1568 :                                             DatumGetRangeTypeP(keyDatum));
     948        1568 :                 break;
     949       12330 :             case RANGESTRAT_OVERLEFT:
     950       12330 :                 res = range_overleft_internal(typcache, leafRange,
     951       12330 :                                               DatumGetRangeTypeP(keyDatum));
     952       12330 :                 break;
     953        1940 :             case RANGESTRAT_OVERLAPS:
     954        1940 :                 res = range_overlaps_internal(typcache, leafRange,
     955        1940 :                                               DatumGetRangeTypeP(keyDatum));
     956        1940 :                 break;
     957       38496 :             case RANGESTRAT_OVERRIGHT:
     958       38496 :                 res = range_overright_internal(typcache, leafRange,
     959       38496 :                                                DatumGetRangeTypeP(keyDatum));
     960       38496 :                 break;
     961       29420 :             case RANGESTRAT_AFTER:
     962       29420 :                 res = range_after_internal(typcache, leafRange,
     963       29420 :                                            DatumGetRangeTypeP(keyDatum));
     964       29420 :                 break;
     965        2294 :             case RANGESTRAT_ADJACENT:
     966        2294 :                 res = range_adjacent_internal(typcache, leafRange,
     967        2294 :                                               DatumGetRangeTypeP(keyDatum));
     968        2294 :                 break;
     969       51202 :             case RANGESTRAT_CONTAINS:
     970       51202 :                 res = range_contains_internal(typcache, leafRange,
     971       51202 :                                               DatumGetRangeTypeP(keyDatum));
     972       51202 :                 break;
     973        8888 :             case RANGESTRAT_CONTAINED_BY:
     974        8888 :                 res = range_contained_by_internal(typcache, leafRange,
     975        8888 :                                                   DatumGetRangeTypeP(keyDatum));
     976        8888 :                 break;
     977        1602 :             case RANGESTRAT_CONTAINS_ELEM:
     978        1602 :                 res = range_contains_elem_internal(typcache, leafRange,
     979             :                                                    keyDatum);
     980        1602 :                 break;
     981         568 :             case RANGESTRAT_EQ:
     982         568 :                 res = range_eq_internal(typcache, leafRange,
     983         568 :                                         DatumGetRangeTypeP(keyDatum));
     984         568 :                 break;
     985           0 :             default:
     986           0 :                 elog(ERROR, "unrecognized range strategy: %d",
     987             :                      in->scankeys[i].sk_strategy);
     988             :                 break;
     989             :         }
     990             : 
     991             :         /*
     992             :          * If leaf datum doesn't match to a query key, no need to check
     993             :          * subsequent keys.
     994             :          */
     995      148308 :         if (!res)
     996       10424 :             break;
     997             :     }
     998             : 
     999      148308 :     PG_RETURN_BOOL(res);
    1000             : }

Generated by: LCOV version 1.13