LCOV - code coverage report
Current view: top level - src/backend/access/spgist - spgquadtreeproc.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13beta1 Lines: 200 206 97.1 %
Date: 2020-05-29 00:07:09 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-2020, 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          62 : spg_quad_config(PG_FUNCTION_ARGS)
      28             : {
      29             :     /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
      30          62 :     spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
      31             : 
      32          62 :     cfg->prefixType = POINTOID;
      33          62 :     cfg->labelType = VOIDOID;    /* we don't need node labels */
      34          62 :     cfg->canReturnData = true;
      35          62 :     cfg->longValuesOK = false;
      36          62 :     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     8627566 : getQuadrant(Point *centroid, Point *tst)
      56             : {
      57     8800590 :     if ((SPTEST(point_above, tst, centroid) ||
      58     8630756 :          SPTEST(point_horiz, tst, centroid)) &&
      59     8572586 :         (SPTEST(point_right, tst, centroid) ||
      60      114854 :          SPTEST(point_vert, tst, centroid)))
      61     8346068 :         return 1;
      62             : 
      63      451332 :     if (SPTEST(point_below, tst, centroid) &&
      64      330136 :         (SPTEST(point_right, tst, centroid) ||
      65      160302 :          SPTEST(point_vert, tst, centroid)))
      66        9532 :         return 2;
      67             : 
      68      383630 :     if ((SPTEST(point_below, tst, centroid) ||
      69      271966 :          SPTEST(point_horiz, tst, centroid)) &&
      70      160302 :         SPTEST(point_left, tst, centroid))
      71      160302 :         return 3;
      72             : 
      73      223328 :     if (SPTEST(point_above, tst, centroid) &&
      74      111664 :         SPTEST(point_left, tst, centroid))
      75      111664 :         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        2236 : getQuadrantArea(BOX *bbox, Point *centroid, int quadrant)
      84             : {
      85        2236 :     BOX        *result = (BOX *) palloc(sizeof(BOX));
      86             : 
      87        2236 :     switch (quadrant)
      88             :     {
      89         552 :         case 1:
      90         552 :             result->high = bbox->high;
      91         552 :             result->low = *centroid;
      92         552 :             break;
      93         556 :         case 2:
      94         556 :             result->high.x = bbox->high.x;
      95         556 :             result->high.y = centroid->y;
      96         556 :             result->low.x = centroid->x;
      97         556 :             result->low.y = bbox->low.y;
      98         556 :             break;
      99         564 :         case 3:
     100         564 :             result->high = *centroid;
     101         564 :             result->low = bbox->low;
     102         564 :             break;
     103         564 :         case 4:
     104         564 :             result->high.x = centroid->x;
     105         564 :             result->high.y = bbox->high.y;
     106         564 :             result->low.x = bbox->low.x;
     107         564 :             result->low.y = centroid->y;
     108         564 :             break;
     109             :     }
     110             : 
     111        2236 :     return result;
     112             : }
     113             : 
     114             : Datum
     115     8443006 : spg_quad_choose(PG_FUNCTION_ARGS)
     116             : {
     117     8443006 :     spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
     118     8443006 :     spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
     119     8443006 :     Point      *inPoint = DatumGetPointP(in->datum),
     120             :                *centroid;
     121             : 
     122     8443006 :     if (in->allTheSame)
     123             :     {
     124        3776 :         out->resultType = spgMatchNode;
     125             :         /* nodeN will be set by core */
     126        3776 :         out->result.matchNode.levelAdd = 0;
     127        3776 :         out->result.matchNode.restDatum = PointPGetDatum(inPoint);
     128        3776 :         PG_RETURN_VOID();
     129             :     }
     130             : 
     131             :     Assert(in->hasPrefix);
     132     8439230 :     centroid = DatumGetPointP(in->prefixDatum);
     133             : 
     134             :     Assert(in->nNodes == 4);
     135             : 
     136     8439230 :     out->resultType = spgMatchNode;
     137     8439230 :     out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
     138     8439230 :     out->result.matchNode.levelAdd = 0;
     139     8439230 :     out->result.matchNode.restDatum = PointPGetDatum(inPoint);
     140             : 
     141     8439230 :     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        1302 : spg_quad_picksplit(PG_FUNCTION_ARGS)
     170             : {
     171        1302 :     spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
     172        1302 :     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        1302 :     centroid = palloc0(sizeof(*centroid));
     193             : 
     194      189294 :     for (i = 0; i < in->nTuples; i++)
     195             :     {
     196      187992 :         centroid->x += DatumGetPointP(in->datums[i])->x;
     197      187992 :         centroid->y += DatumGetPointP(in->datums[i])->y;
     198             :     }
     199             : 
     200        1302 :     centroid->x /= in->nTuples;
     201        1302 :     centroid->y /= in->nTuples;
     202             : #endif
     203             : 
     204        1302 :     out->hasPrefix = true;
     205        1302 :     out->prefixDatum = PointPGetDatum(centroid);
     206             : 
     207        1302 :     out->nNodes = 4;
     208        1302 :     out->nodeLabels = NULL;      /* we don't need node labels */
     209             : 
     210        1302 :     out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
     211        1302 :     out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
     212             : 
     213      189294 :     for (i = 0; i < in->nTuples; i++)
     214             :     {
     215      187992 :         Point      *p = DatumGetPointP(in->datums[i]);
     216      187992 :         int         quadrant = getQuadrant(centroid, p) - 1;
     217             : 
     218      187992 :         out->leafTupleDatums[i] = PointPGetDatum(p);
     219      187992 :         out->mapTuplesToNodes[i] = quadrant;
     220             :     }
     221             : 
     222        1302 :     PG_RETURN_VOID();
     223             : }
     224             : 
     225             : 
     226             : Datum
     227        3792 : spg_quad_inner_consistent(PG_FUNCTION_ARGS)
     228             : {
     229        3792 :     spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
     230        3792 :     spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
     231             :     Point      *centroid;
     232             :     BOX         infbbox;
     233        3792 :     BOX        *bbox = NULL;
     234             :     int         which;
     235             :     int         i;
     236             : 
     237             :     Assert(in->hasPrefix);
     238        3792 :     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        3792 :     if (in->norderbys > 0)
     248             :     {
     249         640 :         out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
     250         640 :         out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
     251             : 
     252         640 :         if (in->level == 0)
     253             :         {
     254          12 :             double      inf = get_float8_infinity();
     255             : 
     256          12 :             infbbox.high.x = inf;
     257          12 :             infbbox.high.y = inf;
     258          12 :             infbbox.low.x = -inf;
     259          12 :             infbbox.low.y = -inf;
     260          12 :             bbox = &infbbox;
     261             :         }
     262             :         else
     263             :         {
     264         628 :             bbox = in->traversalValue;
     265             :             Assert(bbox);
     266             :         }
     267             :     }
     268             : 
     269        3792 :     if (in->allTheSame)
     270             :     {
     271             :         /* Report that all nodes should be visited */
     272         360 :         out->nNodes = in->nNodes;
     273         360 :         out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
     274        3240 :         for (i = 0; i < in->nNodes; i++)
     275             :         {
     276        2880 :             out->nodeNumbers[i] = i;
     277             : 
     278        2880 :             if (in->norderbys > 0)
     279             :             {
     280         576 :                 MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
     281             : 
     282             :                 /* Use parent quadrant box as traversalValue */
     283         576 :                 BOX        *quadrant = box_copy(bbox);
     284             : 
     285         576 :                 MemoryContextSwitchTo(oldCtx);
     286             : 
     287         576 :                 out->traversalValues[i] = quadrant;
     288         576 :                 out->distances[i] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
     289             :                                                                in->orderbys, in->norderbys);
     290             :             }
     291             :         }
     292         360 :         PG_RETURN_VOID();
     293             :     }
     294             : 
     295             :     Assert(in->nNodes == 4);
     296             : 
     297             :     /* "which" is a bitmask of quadrants that satisfy all constraints */
     298        3432 :     which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
     299             : 
     300        5232 :     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         536 :                 if (SPTEST(point_above, centroid, query))
     320         224 :                     which &= (1 << 2) | (1 << 3);
     321         536 :                 break;
     322         528 :             case RTAboveStrategyNumber:
     323         528 :                 if (SPTEST(point_below, centroid, query))
     324         296 :                     which &= (1 << 1) | (1 << 4);
     325         528 :                 break;
     326         120 :             case RTContainedByStrategyNumber:
     327             : 
     328             :                 /*
     329             :                  * For this operator, the query is a box not a point.  We
     330             :                  * cheat to the extent of assuming that DatumGetPointP won't
     331             :                  * do anything that would be bad for a pointer-to-box.
     332             :                  */
     333         120 :                 boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
     334             : 
     335         120 :                 if (DatumGetBool(DirectFunctionCall2(box_contain_pt,
     336             :                                                      PointerGetDatum(boxQuery),
     337             :                                                      PointerGetDatum(centroid))))
     338             :                 {
     339             :                     /* centroid is in box, so all quadrants are OK */
     340             :                 }
     341             :                 else
     342          80 :                 {
     343             :                     /* identify quadrant(s) containing all corners of box */
     344             :                     Point       p;
     345          80 :                     int         r = 0;
     346             : 
     347          80 :                     p = boxQuery->low;
     348          80 :                     r |= 1 << getQuadrant(centroid, &p);
     349          80 :                     p.y = boxQuery->high.y;
     350          80 :                     r |= 1 << getQuadrant(centroid, &p);
     351          80 :                     p = boxQuery->high;
     352          80 :                     r |= 1 << getQuadrant(centroid, &p);
     353          80 :                     p.x = boxQuery->low.x;
     354          80 :                     r |= 1 << getQuadrant(centroid, &p);
     355             : 
     356          80 :                     which &= r;
     357             :                 }
     358         120 :                 break;
     359           0 :             default:
     360           0 :                 elog(ERROR, "unrecognized strategy number: %d",
     361             :                      in->scankeys[i].sk_strategy);
     362             :                 break;
     363             :         }
     364             : 
     365        1800 :         if (which == 0)
     366           0 :             break;              /* no need to consider remaining conditions */
     367             :     }
     368             : 
     369        3432 :     out->levelAdds = palloc(sizeof(int) * 4);
     370       17160 :     for (i = 0; i < 4; ++i)
     371       13728 :         out->levelAdds[i] = 1;
     372             : 
     373             :     /* We must descend into the quadrant(s) identified by which */
     374        3432 :     out->nodeNumbers = (int *) palloc(sizeof(int) * 4);
     375        3432 :     out->nNodes = 0;
     376             : 
     377       17160 :     for (i = 1; i <= 4; i++)
     378             :     {
     379       13728 :         if (which & (1 << i))
     380             :         {
     381       12340 :             out->nodeNumbers[out->nNodes] = i - 1;
     382             : 
     383       12340 :             if (in->norderbys > 0)
     384             :             {
     385        2236 :                 MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
     386        2236 :                 BOX        *quadrant = getQuadrantArea(bbox, centroid, i);
     387             : 
     388        2236 :                 MemoryContextSwitchTo(oldCtx);
     389             : 
     390        2236 :                 out->traversalValues[out->nNodes] = quadrant;
     391             : 
     392        2236 :                 out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
     393             :                                                                          in->orderbys, in->norderbys);
     394             :             }
     395             : 
     396       12340 :             out->nNodes++;
     397             :         }
     398             :     }
     399             : 
     400        3432 :     PG_RETURN_VOID();
     401             : }
     402             : 
     403             : 
     404             : Datum
     405      820396 : spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
     406             : {
     407      820396 :     spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
     408      820396 :     spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
     409      820396 :     Point      *datum = DatumGetPointP(in->leafDatum);
     410             :     bool        res;
     411             :     int         i;
     412             : 
     413             :     /* all tests are exact */
     414      820396 :     out->recheck = false;
     415             : 
     416             :     /* leafDatum is what it is... */
     417      820396 :     out->leafValue = in->leafDatum;
     418             : 
     419             :     /* Perform the required comparison(s) */
     420      820396 :     res = true;
     421     1214660 :     for (i = 0; i < in->nkeys; i++)
     422             :     {
     423      466776 :         Point      *query = DatumGetPointP(in->scankeys[i].sk_argument);
     424             : 
     425      466776 :         switch (in->scankeys[i].sk_strategy)
     426             :         {
     427      101272 :             case RTLeftStrategyNumber:
     428      101272 :                 res = SPTEST(point_left, datum, query);
     429      101272 :                 break;
     430       82168 :             case RTRightStrategyNumber:
     431       82168 :                 res = SPTEST(point_right, datum, query);
     432       82168 :                 break;
     433        1360 :             case RTSameStrategyNumber:
     434        1360 :                 res = SPTEST(point_eq, datum, query);
     435        1360 :                 break;
     436      116232 :             case RTBelowStrategyNumber:
     437      116232 :                 res = SPTEST(point_below, datum, query);
     438      116232 :                 break;
     439      115704 :             case RTAboveStrategyNumber:
     440      115704 :                 res = SPTEST(point_above, datum, query);
     441      115704 :                 break;
     442       50040 :             case RTContainedByStrategyNumber:
     443             : 
     444             :                 /*
     445             :                  * For this operator, the query is a box not a point.  We
     446             :                  * cheat to the extent of assuming that DatumGetPointP won't
     447             :                  * do anything that would be bad for a pointer-to-box.
     448             :                  */
     449       50040 :                 res = SPTEST(box_contain_pt, query, datum);
     450       50040 :                 break;
     451           0 :             default:
     452           0 :                 elog(ERROR, "unrecognized strategy number: %d",
     453             :                      in->scankeys[i].sk_strategy);
     454             :                 break;
     455             :         }
     456             : 
     457      466776 :         if (!res)
     458       72512 :             break;
     459             :     }
     460             : 
     461      820396 :     if (res && in->norderbys > 0)
     462             :         /* ok, it passes -> let's compute the distances */
     463      186076 :         out->distances = spg_key_orderbys_distances(in->leafDatum, true,
     464             :                                                     in->orderbys, in->norderbys);
     465             : 
     466      820396 :     PG_RETURN_BOOL(res);
     467             : }

Generated by: LCOV version 1.13