LCOV - code coverage report
Current view: top level - src/backend/access/spgist - spgquadtreeproc.c (source / functions) Hit Total Coverage
Test: PostgreSQL 15devel Lines: 199 205 97.1 %
Date: 2021-12-09 03:08:47 Functions: 7 7 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * spgquadtreeproc.c
       4             :  *    implementation of quad tree over points for SP-GiST
       5             :  *
       6             :  *
       7             :  * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
       8             :  * Portions Copyright (c) 1994, Regents of the University of California
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *          src/backend/access/spgist/spgquadtreeproc.c
      12             :  *
      13             :  *-------------------------------------------------------------------------
      14             :  */
      15             : 
      16             : #include "postgres.h"
      17             : 
      18             : #include "access/spgist.h"
      19             : #include "access/spgist_private.h"
      20             : #include "access/stratnum.h"
      21             : #include "catalog/pg_type.h"
      22             : #include "utils/builtins.h"
      23             : #include "utils/float.h"
      24             : #include "utils/geo_decls.h"
      25             : 
      26             : Datum
      27          70 : spg_quad_config(PG_FUNCTION_ARGS)
      28             : {
      29             :     /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
      30          70 :     spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
      31             : 
      32          70 :     cfg->prefixType = POINTOID;
      33          70 :     cfg->labelType = VOIDOID;    /* we don't need node labels */
      34          70 :     cfg->canReturnData = true;
      35          70 :     cfg->longValuesOK = false;
      36          70 :     PG_RETURN_VOID();
      37             : }
      38             : 
      39             : #define SPTEST(f, x, y) \
      40             :     DatumGetBool(DirectFunctionCall2(f, PointPGetDatum(x), PointPGetDatum(y)))
      41             : 
      42             : /*
      43             :  * Determine which quadrant a point falls into, relative to the centroid.
      44             :  *
      45             :  * Quadrants are identified like this:
      46             :  *
      47             :  *   4  |  1
      48             :  *  ----+-----
      49             :  *   3  |  2
      50             :  *
      51             :  * Points on one of the axes are taken to lie in the lowest-numbered
      52             :  * adjacent quadrant.
      53             :  */
      54             : static int16
      55    11098326 : getQuadrant(Point *centroid, Point *tst)
      56             : {
      57    11326654 :     if ((SPTEST(point_above, tst, centroid) ||
      58    11104506 :          SPTEST(point_horiz, tst, centroid)) &&
      59    11008096 :         (SPTEST(point_right, tst, centroid) ||
      60      131918 :          SPTEST(point_vert, tst, centroid)))
      61    10750440 :         return 1;
      62             : 
      63      570034 :     if (SPTEST(point_below, tst, centroid) &&
      64      420098 :         (SPTEST(point_right, tst, centroid) ||
      65      197950 :          SPTEST(point_vert, tst, centroid)))
      66       24200 :         return 2;
      67             : 
      68      449424 :     if ((SPTEST(point_below, tst, centroid) ||
      69      323686 :          SPTEST(point_horiz, tst, centroid)) &&
      70      197948 :         SPTEST(point_left, tst, centroid))
      71      197948 :         return 3;
      72             : 
      73      251476 :     if (SPTEST(point_above, tst, centroid) &&
      74      125738 :         SPTEST(point_left, tst, centroid))
      75      125738 :         return 4;
      76             : 
      77           0 :     elog(ERROR, "getQuadrant: impossible case");
      78             :     return 0;
      79             : }
      80             : 
      81             : /* Returns bounding box of a given quadrant inside given bounding box */
      82             : static BOX *
      83        2268 : getQuadrantArea(BOX *bbox, Point *centroid, int quadrant)
      84             : {
      85        2268 :     BOX        *result = (BOX *) palloc(sizeof(BOX));
      86             : 
      87        2268 :     switch (quadrant)
      88             :     {
      89         560 :         case 1:
      90         560 :             result->high = bbox->high;
      91         560 :             result->low = *centroid;
      92         560 :             break;
      93         564 :         case 2:
      94         564 :             result->high.x = bbox->high.x;
      95         564 :             result->high.y = centroid->y;
      96         564 :             result->low.x = centroid->x;
      97         564 :             result->low.y = bbox->low.y;
      98         564 :             break;
      99         572 :         case 3:
     100         572 :             result->high = *centroid;
     101         572 :             result->low = bbox->low;
     102         572 :             break;
     103         572 :         case 4:
     104         572 :             result->high.x = centroid->x;
     105         572 :             result->high.y = bbox->high.y;
     106         572 :             result->low.x = bbox->low.x;
     107         572 :             result->low.y = centroid->y;
     108         572 :             break;
     109             :     }
     110             : 
     111        2268 :     return result;
     112             : }
     113             : 
     114             : Datum
     115    10921908 : spg_quad_choose(PG_FUNCTION_ARGS)
     116             : {
     117    10921908 :     spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
     118    10921908 :     spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
     119    10921908 :     Point      *inPoint = DatumGetPointP(in->datum),
     120             :                *centroid;
     121             : 
     122    10921908 :     if (in->allTheSame)
     123             :     {
     124       70896 :         out->resultType = spgMatchNode;
     125             :         /* nodeN will be set by core */
     126       70896 :         out->result.matchNode.levelAdd = 0;
     127       70896 :         out->result.matchNode.restDatum = PointPGetDatum(inPoint);
     128       70896 :         PG_RETURN_VOID();
     129             :     }
     130             : 
     131             :     Assert(in->hasPrefix);
     132    10851012 :     centroid = DatumGetPointP(in->prefixDatum);
     133             : 
     134             :     Assert(in->nNodes == 4);
     135             : 
     136    10851012 :     out->resultType = spgMatchNode;
     137    10851012 :     out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
     138    10851012 :     out->result.matchNode.levelAdd = 0;
     139    10851012 :     out->result.matchNode.restDatum = PointPGetDatum(inPoint);
     140             : 
     141    10851012 :     PG_RETURN_VOID();
     142             : }
     143             : 
     144             : #ifdef USE_MEDIAN
     145             : static int
     146             : x_cmp(const void *a, const void *b, void *arg)
     147             : {
     148             :     Point      *pa = *(Point **) a;
     149             :     Point      *pb = *(Point **) b;
     150             : 
     151             :     if (pa->x == pb->x)
     152             :         return 0;
     153             :     return (pa->x > pb->x) ? 1 : -1;
     154             : }
     155             : 
     156             : static int
     157             : y_cmp(const void *a, const void *b, void *arg)
     158             : {
     159             :     Point      *pa = *(Point **) a;
     160             :     Point      *pb = *(Point **) b;
     161             : 
     162             :     if (pa->y == pb->y)
     163             :         return 0;
     164             :     return (pa->y > pb->y) ? 1 : -1;
     165             : }
     166             : #endif
     167             : 
     168             : Datum
     169        1764 : spg_quad_picksplit(PG_FUNCTION_ARGS)
     170             : {
     171        1764 :     spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
     172        1764 :     spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
     173             :     int         i;
     174             :     Point      *centroid;
     175             : 
     176             : #ifdef USE_MEDIAN
     177             :     /* Use the median values of x and y as the centroid point */
     178             :     Point     **sorted;
     179             : 
     180             :     sorted = palloc(sizeof(*sorted) * in->nTuples);
     181             :     for (i = 0; i < in->nTuples; i++)
     182             :         sorted[i] = DatumGetPointP(in->datums[i]);
     183             : 
     184             :     centroid = palloc(sizeof(*centroid));
     185             : 
     186             :     qsort(sorted, in->nTuples, sizeof(*sorted), x_cmp);
     187             :     centroid->x = sorted[in->nTuples >> 1]->x;
     188             :     qsort(sorted, in->nTuples, sizeof(*sorted), y_cmp);
     189             :     centroid->y = sorted[in->nTuples >> 1]->y;
     190             : #else
     191             :     /* Use the average values of x and y as the centroid point */
     192        1764 :     centroid = palloc0(sizeof(*centroid));
     193             : 
     194      248734 :     for (i = 0; i < in->nTuples; i++)
     195             :     {
     196      246970 :         centroid->x += DatumGetPointP(in->datums[i])->x;
     197      246970 :         centroid->y += DatumGetPointP(in->datums[i])->y;
     198             :     }
     199             : 
     200        1764 :     centroid->x /= in->nTuples;
     201        1764 :     centroid->y /= in->nTuples;
     202             : #endif
     203             : 
     204        1764 :     out->hasPrefix = true;
     205        1764 :     out->prefixDatum = PointPGetDatum(centroid);
     206             : 
     207        1764 :     out->nNodes = 4;
     208        1764 :     out->nodeLabels = NULL;      /* we don't need node labels */
     209             : 
     210        1764 :     out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
     211        1764 :     out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
     212             : 
     213      248734 :     for (i = 0; i < in->nTuples; i++)
     214             :     {
     215      246970 :         Point      *p = DatumGetPointP(in->datums[i]);
     216      246970 :         int         quadrant = getQuadrant(centroid, p) - 1;
     217             : 
     218      246970 :         out->leafTupleDatums[i] = PointPGetDatum(p);
     219      246970 :         out->mapTuplesToNodes[i] = quadrant;
     220             :     }
     221             : 
     222        1764 :     PG_RETURN_VOID();
     223             : }
     224             : 
     225             : 
     226             : Datum
     227        3830 : spg_quad_inner_consistent(PG_FUNCTION_ARGS)
     228             : {
     229        3830 :     spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
     230        3830 :     spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
     231             :     Point      *centroid;
     232             :     BOX         infbbox;
     233        3830 :     BOX        *bbox = NULL;
     234             :     int         which;
     235             :     int         i;
     236             : 
     237             :     Assert(in->hasPrefix);
     238        3830 :     centroid = DatumGetPointP(in->prefixDatum);
     239             : 
     240             :     /*
     241             :      * When ordering scan keys are specified, we've to calculate distance for
     242             :      * them.  In order to do that, we need calculate bounding boxes for all
     243             :      * children nodes.  Calculation of those bounding boxes on non-zero level
     244             :      * require knowledge of bounding box of upper node.  So, we save bounding
     245             :      * boxes to traversalValues.
     246             :      */
     247        3830 :     if (in->norderbys > 0)
     248             :     {
     249         654 :         out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
     250         654 :         out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
     251             : 
     252         654 :         if (in->level == 0)
     253             :         {
     254          16 :             double      inf = get_float8_infinity();
     255             : 
     256          16 :             infbbox.high.x = inf;
     257          16 :             infbbox.high.y = inf;
     258          16 :             infbbox.low.x = -inf;
     259          16 :             infbbox.low.y = -inf;
     260          16 :             bbox = &infbbox;
     261             :         }
     262             :         else
     263             :         {
     264         638 :             bbox = in->traversalValue;
     265             :             Assert(bbox);
     266             :         }
     267             :     }
     268             : 
     269        3830 :     if (in->allTheSame)
     270             :     {
     271             :         /* Report that all nodes should be visited */
     272         390 :         out->nNodes = in->nNodes;
     273         390 :         out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
     274        3510 :         for (i = 0; i < in->nNodes; i++)
     275             :         {
     276        3120 :             out->nodeNumbers[i] = i;
     277             : 
     278        3120 :             if (in->norderbys > 0)
     279             :             {
     280         624 :                 MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
     281             : 
     282             :                 /* Use parent quadrant box as traversalValue */
     283         624 :                 BOX        *quadrant = box_copy(bbox);
     284             : 
     285         624 :                 MemoryContextSwitchTo(oldCtx);
     286             : 
     287         624 :                 out->traversalValues[i] = quadrant;
     288         624 :                 out->distances[i] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
     289             :                                                                in->orderbys, in->norderbys);
     290             :             }
     291             :         }
     292         390 :         PG_RETURN_VOID();
     293             :     }
     294             : 
     295             :     Assert(in->nNodes == 4);
     296             : 
     297             :     /* "which" is a bitmask of quadrants that satisfy all constraints */
     298        3440 :     which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
     299             : 
     300        5240 :     for (i = 0; i < in->nkeys; i++)
     301             :     {
     302        1800 :         Point      *query = DatumGetPointP(in->scankeys[i].sk_argument);
     303             :         BOX        *boxQuery;
     304             : 
     305        1800 :         switch (in->scankeys[i].sk_strategy)
     306             :         {
     307         312 :             case RTLeftStrategyNumber:
     308         312 :                 if (SPTEST(point_right, centroid, query))
     309          40 :                     which &= (1 << 3) | (1 << 4);
     310         312 :                 break;
     311         280 :             case RTRightStrategyNumber:
     312         280 :                 if (SPTEST(point_left, centroid, query))
     313           8 :                     which &= (1 << 1) | (1 << 2);
     314         280 :                 break;
     315          24 :             case RTSameStrategyNumber:
     316          24 :                 which &= (1 << getQuadrant(centroid, query));
     317          24 :                 break;
     318         536 :             case RTBelowStrategyNumber:
     319             :             case RTOldBelowStrategyNumber:
     320         536 :                 if (SPTEST(point_above, centroid, query))
     321         224 :                     which &= (1 << 2) | (1 << 3);
     322         536 :                 break;
     323         528 :             case RTAboveStrategyNumber:
     324             :             case RTOldAboveStrategyNumber:
     325         528 :                 if (SPTEST(point_below, centroid, query))
     326         296 :                     which &= (1 << 1) | (1 << 4);
     327         528 :                 break;
     328         120 :             case RTContainedByStrategyNumber:
     329             : 
     330             :                 /*
     331             :                  * For this operator, the query is a box not a point.  We
     332             :                  * cheat to the extent of assuming that DatumGetPointP won't
     333             :                  * do anything that would be bad for a pointer-to-box.
     334             :                  */
     335         120 :                 boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
     336             : 
     337         120 :                 if (DatumGetBool(DirectFunctionCall2(box_contain_pt,
     338             :                                                      PointerGetDatum(boxQuery),
     339             :                                                      PointerGetDatum(centroid))))
     340             :                 {
     341             :                     /* centroid is in box, so all quadrants are OK */
     342             :                 }
     343             :                 else
     344             :                 {
     345             :                     /* identify quadrant(s) containing all corners of box */
     346             :                     Point       p;
     347          80 :                     int         r = 0;
     348             : 
     349          80 :                     p = boxQuery->low;
     350          80 :                     r |= 1 << getQuadrant(centroid, &p);
     351          80 :                     p.y = boxQuery->high.y;
     352          80 :                     r |= 1 << getQuadrant(centroid, &p);
     353          80 :                     p = boxQuery->high;
     354          80 :                     r |= 1 << getQuadrant(centroid, &p);
     355          80 :                     p.x = boxQuery->low.x;
     356          80 :                     r |= 1 << getQuadrant(centroid, &p);
     357             : 
     358          80 :                     which &= r;
     359             :                 }
     360         120 :                 break;
     361           0 :             default:
     362           0 :                 elog(ERROR, "unrecognized strategy number: %d",
     363             :                      in->scankeys[i].sk_strategy);
     364             :                 break;
     365             :         }
     366             : 
     367        1800 :         if (which == 0)
     368           0 :             break;              /* no need to consider remaining conditions */
     369             :     }
     370             : 
     371        3440 :     out->levelAdds = palloc(sizeof(int) * 4);
     372       17200 :     for (i = 0; i < 4; ++i)
     373       13760 :         out->levelAdds[i] = 1;
     374             : 
     375             :     /* We must descend into the quadrant(s) identified by which */
     376        3440 :     out->nodeNumbers = (int *) palloc(sizeof(int) * 4);
     377        3440 :     out->nNodes = 0;
     378             : 
     379       17200 :     for (i = 1; i <= 4; i++)
     380             :     {
     381       13760 :         if (which & (1 << i))
     382             :         {
     383       12372 :             out->nodeNumbers[out->nNodes] = i - 1;
     384             : 
     385       12372 :             if (in->norderbys > 0)
     386             :             {
     387        2268 :                 MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
     388        2268 :                 BOX        *quadrant = getQuadrantArea(bbox, centroid, i);
     389             : 
     390        2268 :                 MemoryContextSwitchTo(oldCtx);
     391             : 
     392        2268 :                 out->traversalValues[out->nNodes] = quadrant;
     393             : 
     394        2268 :                 out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
     395             :                                                                          in->orderbys, in->norderbys);
     396             :             }
     397             : 
     398       12372 :             out->nNodes++;
     399             :         }
     400             :     }
     401             : 
     402        3440 :     PG_RETURN_VOID();
     403             : }
     404             : 
     405             : 
     406             : Datum
     407      820534 : spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
     408             : {
     409      820534 :     spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
     410      820534 :     spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
     411      820534 :     Point      *datum = DatumGetPointP(in->leafDatum);
     412             :     bool        res;
     413             :     int         i;
     414             : 
     415             :     /* all tests are exact */
     416      820534 :     out->recheck = false;
     417             : 
     418             :     /* leafDatum is what it is... */
     419      820534 :     out->leafValue = in->leafDatum;
     420             : 
     421             :     /* Perform the required comparison(s) */
     422      820534 :     res = true;
     423     1214798 :     for (i = 0; i < in->nkeys; i++)
     424             :     {
     425      466776 :         Point      *query = DatumGetPointP(in->scankeys[i].sk_argument);
     426             : 
     427      466776 :         switch (in->scankeys[i].sk_strategy)
     428             :         {
     429      101272 :             case RTLeftStrategyNumber:
     430      101272 :                 res = SPTEST(point_left, datum, query);
     431      101272 :                 break;
     432       82168 :             case RTRightStrategyNumber:
     433       82168 :                 res = SPTEST(point_right, datum, query);
     434       82168 :                 break;
     435        1360 :             case RTSameStrategyNumber:
     436        1360 :                 res = SPTEST(point_eq, datum, query);
     437        1360 :                 break;
     438      116232 :             case RTBelowStrategyNumber:
     439             :             case RTOldBelowStrategyNumber:
     440      116232 :                 res = SPTEST(point_below, datum, query);
     441      116232 :                 break;
     442      115704 :             case RTAboveStrategyNumber:
     443             :             case RTOldAboveStrategyNumber:
     444      115704 :                 res = SPTEST(point_above, datum, query);
     445      115704 :                 break;
     446       50040 :             case RTContainedByStrategyNumber:
     447             : 
     448             :                 /*
     449             :                  * For this operator, the query is a box not a point.  We
     450             :                  * cheat to the extent of assuming that DatumGetPointP won't
     451             :                  * do anything that would be bad for a pointer-to-box.
     452             :                  */
     453       50040 :                 res = SPTEST(box_contain_pt, query, datum);
     454       50040 :                 break;
     455           0 :             default:
     456           0 :                 elog(ERROR, "unrecognized strategy number: %d",
     457             :                      in->scankeys[i].sk_strategy);
     458             :                 break;
     459             :         }
     460             : 
     461      466776 :         if (!res)
     462       72512 :             break;
     463             :     }
     464             : 
     465      820534 :     if (res && in->norderbys > 0)
     466             :         /* ok, it passes -> let's compute the distances */
     467      186214 :         out->distances = spg_key_orderbys_distances(in->leafDatum, true,
     468             :                                                     in->orderbys, in->norderbys);
     469             : 
     470      820534 :     PG_RETURN_BOOL(res);
     471             : }

Generated by: LCOV version 1.14