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

Generated by: LCOV version 1.13