granicus.if.org Git - postgresql/blob - src/backend/access/spgist/spgkdtreeproc.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * spgkdtreeproc.c
   4  *        implementation of k-d tree over points for SP-GiST
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * IDENTIFICATION
  11  *                      src/backend/access/spgist/spgkdtreeproc.c
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include "access/gist.h"                /* for RTree strategy numbers */
  19 #include "access/spgist.h"
  20 #include "catalog/pg_type.h"
  21 #include "utils/builtins.h"
  22 #include "utils/geo_decls.h"
  23
  24
  25 Datum
  26 spg_kd_config(PG_FUNCTION_ARGS)
  27 {
  28         /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
  29         spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
  30
  31         cfg->prefixType = FLOAT8OID;
  32         cfg->labelType = VOIDOID;       /* we don't need node labels */
  33         cfg->canReturnData = true;
  34         cfg->longValuesOK = false;
  35         PG_RETURN_VOID();
  36 }
  37
  38 static int
  39 getSide(double coord, bool isX, Point *tst)
  40 {
  41         double          tstcoord = (isX) ? tst->x : tst->y;
  42
  43         if (coord == tstcoord)
  44                 return 0;
  45         else if (coord > tstcoord)
  46                 return 1;
  47         else
  48                 return -1;
  49 }
  50
  51 Datum
  52 spg_kd_choose(PG_FUNCTION_ARGS)
  53 {
  54         spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
  55         spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
  56         Point      *inPoint = DatumGetPointP(in->datum);
  57         double          coord;
  58
  59         if (in->allTheSame)
  60                 elog(ERROR, "allTheSame should not occur for k-d trees");
  61
  62         Assert(in->hasPrefix);
  63         coord = DatumGetFloat8(in->prefixDatum);
  64
  65         Assert(in->nNodes == 2);
  66
  67         out->resultType = spgMatchNode;
  68         out->result.matchNode.nodeN =
  69                 (getSide(coord, in->level % 2, inPoint) > 0) ? 0 : 1;
  70         out->result.matchNode.levelAdd = 1;
  71         out->result.matchNode.restDatum = PointPGetDatum(inPoint);
  72
  73         PG_RETURN_VOID();
  74 }
  75
  76 typedef struct SortedPoint
  77 {
  78         Point      *p;
  79         int                     i;
  80 } SortedPoint;
  81
  82 static int
  83 x_cmp(const void *a, const void *b)
  84 {
  85         SortedPoint *pa = (SortedPoint *) a;
  86         SortedPoint *pb = (SortedPoint *) b;
  87
  88         if (pa->p->x == pb->p->x)
  89                 return 0;
  90         return (pa->p->x > pb->p->x) ? 1 : -1;
  91 }
  92
  93 static int
  94 y_cmp(const void *a, const void *b)
  95 {
  96         SortedPoint *pa = (SortedPoint *) a;
  97         SortedPoint *pb = (SortedPoint *) b;
  98
  99         if (pa->p->y == pb->p->y)
 100                 return 0;
 101         return (pa->p->y > pb->p->y) ? 1 : -1;
 102 }
 103
 104
 105 Datum
 106 spg_kd_picksplit(PG_FUNCTION_ARGS)
 107 {
 108         spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
 109         spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
 110         int                     i;
 111         int                     middle;
 112         SortedPoint *sorted;
 113         double          coord;
 114
 115         sorted = palloc(sizeof(*sorted) * in->nTuples);
 116         for (i = 0; i < in->nTuples; i++)
 117         {
 118                 sorted[i].p = DatumGetPointP(in->datums[i]);
 119                 sorted[i].i = i;
 120         }
 121
 122         qsort(sorted, in->nTuples, sizeof(*sorted),
 123                   (in->level % 2) ? x_cmp : y_cmp);
 124         middle = in->nTuples >> 1;
 125         coord = (in->level % 2) ? sorted[middle].p->x : sorted[middle].p->y;
 126
 127         out->hasPrefix = true;
 128         out->prefixDatum = Float8GetDatum(coord);
 129
 130         out->nNodes = 2;
 131         out->nodeLabels = NULL;         /* we don't need node labels */
 132
 133         out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
 134         out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
 135
 136         /*
 137          * Note: points that have coordinates exactly equal to coord may get
 138          * classified into either node, depending on where they happen to fall in
 139          * the sorted list.  This is okay as long as the inner_consistent function
 140          * descends into both sides for such cases.  This is better than the
 141          * alternative of trying to have an exact boundary, because it keeps the
 142          * tree balanced even when we have many instances of the same point value.
 143          * So we should never trigger the allTheSame logic.
 144          */
 145         for (i = 0; i < in->nTuples; i++)
 146         {
 147                 Point      *p = sorted[i].p;
 148                 int                     n = sorted[i].i;
 149
 150                 out->mapTuplesToNodes[n] = (i < middle) ? 0 : 1;
 151                 out->leafTupleDatums[n] = PointPGetDatum(p);
 152         }
 153
 154         PG_RETURN_VOID();
 155 }
 156
 157 Datum
 158 spg_kd_inner_consistent(PG_FUNCTION_ARGS)
 159 {
 160         spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
 161         spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
 162         double          coord;
 163         int                     which;
 164         int                     i;
 165
 166         Assert(in->hasPrefix);
 167         coord = DatumGetFloat8(in->prefixDatum);
 168
 169         if (in->allTheSame)
 170                 elog(ERROR, "allTheSame should not occur for k-d trees");
 171
 172         Assert(in->nNodes == 2);
 173
 174         /* "which" is a bitmask of children that satisfy all constraints */
 175         which = (1 << 1) | (1 << 2);
 176
 177         for (i = 0; i < in->nkeys; i++)
 178         {
 179                 Point      *query = DatumGetPointP(in->scankeys[i].sk_argument);
 180                 BOX                *boxQuery;
 181
 182                 switch (in->scankeys[i].sk_strategy)
 183                 {
 184                         case RTLeftStrategyNumber:
 185                                 if ((in->level % 2) != 0 && FPlt(query->x, coord))
 186                                         which &= (1 << 1);
 187                                 break;
 188                         case RTRightStrategyNumber:
 189                                 if ((in->level % 2) != 0 && FPgt(query->x, coord))
 190                                         which &= (1 << 2);
 191                                 break;
 192                         case RTSameStrategyNumber:
 193                                 if ((in->level % 2) != 0)
 194                                 {
 195                                         if (FPlt(query->x, coord))
 196                                                 which &= (1 << 1);
 197                                         else if (FPgt(query->x, coord))
 198                                                 which &= (1 << 2);
 199                                 }
 200                                 else
 201                                 {
 202                                         if (FPlt(query->y, coord))
 203                                                 which &= (1 << 1);
 204                                         else if (FPgt(query->y, coord))
 205                                                 which &= (1 << 2);
 206                                 }
 207                                 break;
 208                         case RTBelowStrategyNumber:
 209                                 if ((in->level % 2) == 0 && FPlt(query->y, coord))
 210                                         which &= (1 << 1);
 211                                 break;
 212                         case RTAboveStrategyNumber:
 213                                 if ((in->level % 2) == 0 && FPgt(query->y, coord))
 214                                         which &= (1 << 2);
 215                                 break;
 216                         case RTContainedByStrategyNumber:
 217
 218                                 /*
 219                                  * For this operator, the query is a box not a point.  We
 220                                  * cheat to the extent of assuming that DatumGetPointP won't
 221                                  * do anything that would be bad for a pointer-to-box.
 222                                  */
 223                                 boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
 224
 225                                 if ((in->level % 2) != 0)
 226                                 {
 227                                         if (FPlt(boxQuery->high.x, coord))
 228                                                 which &= (1 << 1);
 229                                         else if (FPgt(boxQuery->low.x, coord))
 230                                                 which &= (1 << 2);
 231                                 }
 232                                 else
 233                                 {
 234                                         if (FPlt(boxQuery->high.y, coord))
 235                                                 which &= (1 << 1);
 236                                         else if (FPgt(boxQuery->low.y, coord))
 237                                                 which &= (1 << 2);
 238                                 }
 239                                 break;
 240                         default:
 241                                 elog(ERROR, "unrecognized strategy number: %d",
 242                                          in->scankeys[i].sk_strategy);
 243                                 break;
 244                 }
 245
 246                 if (which == 0)
 247                         break;                          /* no need to consider remaining conditions */
 248         }
 249
 250         /* We must descend into the children identified by which */
 251         out->nodeNumbers = (int *) palloc(sizeof(int) * 2);
 252         out->nNodes = 0;
 253         for (i = 1; i <= 2; i++)
 254         {
 255                 if (which & (1 << i))
 256                         out->nodeNumbers[out->nNodes++] = i - 1;
 257         }
 258
 259         /* Set up level increments, too */
 260         out->levelAdds = (int *) palloc(sizeof(int) * 2);
 261         out->levelAdds[0] = 1;
 262         out->levelAdds[1] = 1;
 263
 264         PG_RETURN_VOID();
 265 }
 266
 267 /*
 268  * spg_kd_leaf_consistent() is the same as spg_quad_leaf_consistent(),
 269  * since we support the same operators and the same leaf data type.
 270  * So we just borrow that function.
 271  */