granicus.if.org Git - postgresql/blob - contrib/ltree/_ltree_gist.c

   1 /*
   2  * contrib/ltree/_ltree_gist.c
   3  *
   4  *
   5  * GiST support for ltree[]
   6  * Teodor Sigaev <teodor@stack.net>
   7  */
   8 #include "postgres.h"
   9
  10 #include "access/gist.h"
  11 #include "access/stratnum.h"
  12 #include "crc32.h"
  13 #include "ltree.h"
  14 #include "port/pg_bitutils.h"
  15
  16 PG_FUNCTION_INFO_V1(_ltree_compress);
  17 PG_FUNCTION_INFO_V1(_ltree_same);
  18 PG_FUNCTION_INFO_V1(_ltree_union);
  19 PG_FUNCTION_INFO_V1(_ltree_penalty);
  20 PG_FUNCTION_INFO_V1(_ltree_picksplit);
  21 PG_FUNCTION_INFO_V1(_ltree_consistent);
  22
  23 #define GETENTRY(vec,pos) ((ltree_gist *) DatumGetPointer((vec)->vector[(pos)].key))
  24 #define NEXTVAL(x) ( (ltree*)( (char*)(x) + INTALIGN( VARSIZE(x) ) ) )
  25
  26 #define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
  27
  28
  29 static void
  30 hashing(BITVECP sign, ltree *t)
  31 {
  32         int                     tlen = t->numlevel;
  33         ltree_level *cur = LTREE_FIRST(t);
  34         int                     hash;
  35
  36         while (tlen > 0)
  37         {
  38                 hash = ltree_crc32_sz(cur->name, cur->len);
  39                 AHASH(sign, hash);
  40                 cur = LEVEL_NEXT(cur);
  41                 tlen--;
  42         }
  43 }
  44
  45 Datum
  46 _ltree_compress(PG_FUNCTION_ARGS)
  47 {
  48         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
  49         GISTENTRY  *retval = entry;
  50
  51         if (entry->leafkey)
  52         {                                                       /* ltree */
  53                 ltree_gist *key;
  54                 ArrayType  *val = DatumGetArrayTypeP(entry->key);
  55                 int32           len = LTG_HDRSIZE + ASIGLEN;
  56                 int                     num = ArrayGetNItems(ARR_NDIM(val), ARR_DIMS(val));
  57                 ltree      *item = (ltree *) ARR_DATA_PTR(val);
  58
  59                 if (ARR_NDIM(val) > 1)
  60                         ereport(ERROR,
  61                                         (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
  62                                          errmsg("array must be one-dimensional")));
  63                 if (array_contains_nulls(val))
  64                         ereport(ERROR,
  65                                         (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
  66                                          errmsg("array must not contain nulls")));
  67
  68                 key = (ltree_gist *) palloc0(len);
  69                 SET_VARSIZE(key, len);
  70                 key->flag = 0;
  71
  72                 MemSet(LTG_SIGN(key), 0, ASIGLEN);
  73                 while (num > 0)
  74                 {
  75                         hashing(LTG_SIGN(key), item);
  76                         num--;
  77                         item = NEXTVAL(item);
  78                 }
  79
  80                 retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
  81                 gistentryinit(*retval, PointerGetDatum(key),
  82                                           entry->rel, entry->page,
  83                                           entry->offset, false);
  84         }
  85         else if (!LTG_ISALLTRUE(entry->key))
  86         {
  87                 int32           i,
  88                                         len;
  89                 ltree_gist *key;
  90
  91                 BITVECP         sign = LTG_SIGN(DatumGetPointer(entry->key));
  92
  93                 ALOOPBYTE
  94                 {
  95                         if ((sign[i] & 0xff) != 0xff)
  96                                 PG_RETURN_POINTER(retval);
  97                 }
  98                 len = LTG_HDRSIZE;
  99                 key = (ltree_gist *) palloc0(len);
 100                 SET_VARSIZE(key, len);
 101                 key->flag = LTG_ALLTRUE;
 102
 103                 retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
 104                 gistentryinit(*retval, PointerGetDatum(key),
 105                                           entry->rel, entry->page,
 106                                           entry->offset, false);
 107         }
 108         PG_RETURN_POINTER(retval);
 109 }
 110
 111 Datum
 112 _ltree_same(PG_FUNCTION_ARGS)
 113 {
 114         ltree_gist *a = (ltree_gist *) PG_GETARG_POINTER(0);
 115         ltree_gist *b = (ltree_gist *) PG_GETARG_POINTER(1);
 116         bool       *result = (bool *) PG_GETARG_POINTER(2);
 117
 118         if (LTG_ISALLTRUE(a) && LTG_ISALLTRUE(b))
 119                 *result = true;
 120         else if (LTG_ISALLTRUE(a))
 121                 *result = false;
 122         else if (LTG_ISALLTRUE(b))
 123                 *result = false;
 124         else
 125         {
 126                 int32           i;
 127                 BITVECP         sa = LTG_SIGN(a),
 128                                         sb = LTG_SIGN(b);
 129
 130                 *result = true;
 131                 ALOOPBYTE
 132                 {
 133                         if (sa[i] != sb[i])
 134                         {
 135                                 *result = false;
 136                                 break;
 137                         }
 138                 }
 139         }
 140         PG_RETURN_POINTER(result);
 141 }
 142
 143 static int32
 144 unionkey(BITVECP sbase, ltree_gist *add)
 145 {
 146         int32           i;
 147         BITVECP         sadd = LTG_SIGN(add);
 148
 149         if (LTG_ISALLTRUE(add))
 150                 return 1;
 151
 152         ALOOPBYTE
 153                 sbase[i] |= sadd[i];
 154         return 0;
 155 }
 156
 157 Datum
 158 _ltree_union(PG_FUNCTION_ARGS)
 159 {
 160         GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 161         int                *size = (int *) PG_GETARG_POINTER(1);
 162         ABITVEC         base;
 163         int32           i,
 164                                 len;
 165         int32           flag = 0;
 166         ltree_gist *result;
 167
 168         MemSet((void *) base, 0, sizeof(ABITVEC));
 169         for (i = 0; i < entryvec->n; i++)
 170         {
 171                 if (unionkey(base, GETENTRY(entryvec, i)))
 172                 {
 173                         flag = LTG_ALLTRUE;
 174                         break;
 175                 }
 176         }
 177
 178         len = LTG_HDRSIZE + ((flag & LTG_ALLTRUE) ? 0 : ASIGLEN);
 179         result = (ltree_gist *) palloc0(len);
 180         SET_VARSIZE(result, len);
 181         result->flag = flag;
 182         if (!LTG_ISALLTRUE(result))
 183                 memcpy((void *) LTG_SIGN(result), (void *) base, sizeof(ABITVEC));
 184         *size = len;
 185
 186         PG_RETURN_POINTER(result);
 187 }
 188
 189 static int32
 190 sizebitvec(BITVECP sign)
 191 {
 192         return pg_popcount((const char *) sign, ASIGLEN);
 193 }
 194
 195 static int
 196 hemdistsign(BITVECP a, BITVECP b)
 197 {
 198         int                     i,
 199                                 diff,
 200                                 dist = 0;
 201
 202         ALOOPBYTE
 203         {
 204                 diff = (unsigned char) (a[i] ^ b[i]);
 205                 /* Using the popcount functions here isn't likely to win */
 206                 dist += pg_number_of_ones[diff];
 207         }
 208         return dist;
 209 }
 210
 211 static int
 212 hemdist(ltree_gist *a, ltree_gist *b)
 213 {
 214         if (LTG_ISALLTRUE(a))
 215         {
 216                 if (LTG_ISALLTRUE(b))
 217                         return 0;
 218                 else
 219                         return ASIGLENBIT - sizebitvec(LTG_SIGN(b));
 220         }
 221         else if (LTG_ISALLTRUE(b))
 222                 return ASIGLENBIT - sizebitvec(LTG_SIGN(a));
 223
 224         return hemdistsign(LTG_SIGN(a), LTG_SIGN(b));
 225 }
 226
 227
 228 Datum
 229 _ltree_penalty(PG_FUNCTION_ARGS)
 230 {
 231         ltree_gist *origval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(0))->key);
 232         ltree_gist *newval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(1))->key);
 233         float      *penalty = (float *) PG_GETARG_POINTER(2);
 234
 235         *penalty = hemdist(origval, newval);
 236         PG_RETURN_POINTER(penalty);
 237 }
 238
 239 typedef struct
 240 {
 241         OffsetNumber pos;
 242         int32           cost;
 243 } SPLITCOST;
 244
 245 static int
 246 comparecost(const void *a, const void *b)
 247 {
 248         return ((const SPLITCOST *) a)->cost - ((const SPLITCOST *) b)->cost;
 249 }
 250
 251 Datum
 252 _ltree_picksplit(PG_FUNCTION_ARGS)
 253 {
 254         GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 255         GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
 256         OffsetNumber k,
 257                                 j;
 258         ltree_gist *datum_l,
 259                            *datum_r;
 260         BITVECP         union_l,
 261                                 union_r;
 262         int32           size_alpha,
 263                                 size_beta;
 264         int32           size_waste,
 265                                 waste = -1;
 266         int32           nbytes;
 267         OffsetNumber seed_1 = 0,
 268                                 seed_2 = 0;
 269         OffsetNumber *left,
 270                            *right;
 271         OffsetNumber maxoff;
 272         BITVECP         ptr;
 273         int                     i;
 274         SPLITCOST  *costvector;
 275         ltree_gist *_k,
 276                            *_j;
 277
 278         maxoff = entryvec->n - 2;
 279         nbytes = (maxoff + 2) * sizeof(OffsetNumber);
 280         v->spl_left = (OffsetNumber *) palloc(nbytes);
 281         v->spl_right = (OffsetNumber *) palloc(nbytes);
 282
 283         for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
 284         {
 285                 _k = GETENTRY(entryvec, k);
 286                 for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
 287                 {
 288                         size_waste = hemdist(_k, GETENTRY(entryvec, j));
 289                         if (size_waste > waste)
 290                         {
 291                                 waste = size_waste;
 292                                 seed_1 = k;
 293                                 seed_2 = j;
 294                         }
 295                 }
 296         }
 297
 298         left = v->spl_left;
 299         v->spl_nleft = 0;
 300         right = v->spl_right;
 301         v->spl_nright = 0;
 302
 303         if (seed_1 == 0 || seed_2 == 0)
 304         {
 305                 seed_1 = 1;
 306                 seed_2 = 2;
 307         }
 308
 309         /* form initial .. */
 310         if (LTG_ISALLTRUE(GETENTRY(entryvec, seed_1)))
 311         {
 312                 datum_l = (ltree_gist *) palloc0(LTG_HDRSIZE);
 313                 SET_VARSIZE(datum_l, LTG_HDRSIZE);
 314                 datum_l->flag = LTG_ALLTRUE;
 315         }
 316         else
 317         {
 318                 datum_l = (ltree_gist *) palloc0(LTG_HDRSIZE + ASIGLEN);
 319                 SET_VARSIZE(datum_l, LTG_HDRSIZE + ASIGLEN);
 320                 datum_l->flag = 0;
 321                 memcpy((void *) LTG_SIGN(datum_l), (void *) LTG_SIGN(GETENTRY(entryvec, seed_1)), sizeof(ABITVEC));
 322         }
 323         if (LTG_ISALLTRUE(GETENTRY(entryvec, seed_2)))
 324         {
 325                 datum_r = (ltree_gist *) palloc0(LTG_HDRSIZE);
 326                 SET_VARSIZE(datum_r, LTG_HDRSIZE);
 327                 datum_r->flag = LTG_ALLTRUE;
 328         }
 329         else
 330         {
 331                 datum_r = (ltree_gist *) palloc0(LTG_HDRSIZE + ASIGLEN);
 332                 SET_VARSIZE(datum_r, LTG_HDRSIZE + ASIGLEN);
 333                 datum_r->flag = 0;
 334                 memcpy((void *) LTG_SIGN(datum_r), (void *) LTG_SIGN(GETENTRY(entryvec, seed_2)), sizeof(ABITVEC));
 335         }
 336
 337         maxoff = OffsetNumberNext(maxoff);
 338         /* sort before ... */
 339         costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
 340         for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
 341         {
 342                 costvector[j - 1].pos = j;
 343                 _j = GETENTRY(entryvec, j);
 344                 size_alpha = hemdist(datum_l, _j);
 345                 size_beta = hemdist(datum_r, _j);
 346                 costvector[j - 1].cost = Abs(size_alpha - size_beta);
 347         }
 348         qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
 349
 350         union_l = LTG_SIGN(datum_l);
 351         union_r = LTG_SIGN(datum_r);
 352
 353         for (k = 0; k < maxoff; k++)
 354         {
 355                 j = costvector[k].pos;
 356                 if (j == seed_1)
 357                 {
 358                         *left++ = j;
 359                         v->spl_nleft++;
 360                         continue;
 361                 }
 362                 else if (j == seed_2)
 363                 {
 364                         *right++ = j;
 365                         v->spl_nright++;
 366                         continue;
 367                 }
 368                 _j = GETENTRY(entryvec, j);
 369                 size_alpha = hemdist(datum_l, _j);
 370                 size_beta = hemdist(datum_r, _j);
 371
 372                 if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.00001))
 373                 {
 374                         if (LTG_ISALLTRUE(datum_l) || LTG_ISALLTRUE(_j))
 375                         {
 376                                 if (!LTG_ISALLTRUE(datum_l))
 377                                         MemSet((void *) union_l, 0xff, sizeof(ABITVEC));
 378                         }
 379                         else
 380                         {
 381                                 ptr = LTG_SIGN(_j);
 382                                 ALOOPBYTE
 383                                         union_l[i] |= ptr[i];
 384                         }
 385                         *left++ = j;
 386                         v->spl_nleft++;
 387                 }
 388                 else
 389                 {
 390                         if (LTG_ISALLTRUE(datum_r) || LTG_ISALLTRUE(_j))
 391                         {
 392                                 if (!LTG_ISALLTRUE(datum_r))
 393                                         MemSet((void *) union_r, 0xff, sizeof(ABITVEC));
 394                         }
 395                         else
 396                         {
 397                                 ptr = LTG_SIGN(_j);
 398                                 ALOOPBYTE
 399                                         union_r[i] |= ptr[i];
 400                         }
 401                         *right++ = j;
 402                         v->spl_nright++;
 403                 }
 404         }
 405
 406         *right = *left = FirstOffsetNumber;
 407
 408         v->spl_ldatum = PointerGetDatum(datum_l);
 409         v->spl_rdatum = PointerGetDatum(datum_r);
 410
 411         PG_RETURN_POINTER(v);
 412 }
 413
 414 static bool
 415 gist_te(ltree_gist *key, ltree *query)
 416 {
 417         ltree_level *curq = LTREE_FIRST(query);
 418         BITVECP         sign = LTG_SIGN(key);
 419         int                     qlen = query->numlevel;
 420         unsigned int hv;
 421
 422         if (LTG_ISALLTRUE(key))
 423                 return true;
 424
 425         while (qlen > 0)
 426         {
 427                 hv = ltree_crc32_sz(curq->name, curq->len);
 428                 if (!GETBIT(sign, AHASHVAL(hv)))
 429                         return false;
 430                 curq = LEVEL_NEXT(curq);
 431                 qlen--;
 432         }
 433
 434         return true;
 435 }
 436
 437 static bool
 438 checkcondition_bit(void *checkval, ITEM *val)
 439 {
 440         return (FLG_CANLOOKSIGN(val->flag)) ? GETBIT(checkval, AHASHVAL(val->val)) : true;
 441 }
 442
 443 static bool
 444 gist_qtxt(ltree_gist *key, ltxtquery *query)
 445 {
 446         if (LTG_ISALLTRUE(key))
 447                 return true;
 448
 449         return ltree_execute(
 450                                                  GETQUERY(query),
 451                                                  (void *) LTG_SIGN(key), false,
 452                                                  checkcondition_bit
 453                 );
 454 }
 455
 456 static bool
 457 gist_qe(ltree_gist *key, lquery *query)
 458 {
 459         lquery_level *curq = LQUERY_FIRST(query);
 460         BITVECP         sign = LTG_SIGN(key);
 461         int                     qlen = query->numlevel;
 462
 463         if (LTG_ISALLTRUE(key))
 464                 return true;
 465
 466         while (qlen > 0)
 467         {
 468                 if (curq->numvar && LQL_CANLOOKSIGN(curq))
 469                 {
 470                         bool            isexist = false;
 471                         int                     vlen = curq->numvar;
 472                         lquery_variant *curv = LQL_FIRST(curq);
 473
 474                         while (vlen > 0)
 475                         {
 476                                 if (GETBIT(sign, AHASHVAL(curv->val)))
 477                                 {
 478                                         isexist = true;
 479                                         break;
 480                                 }
 481                                 curv = LVAR_NEXT(curv);
 482                                 vlen--;
 483                         }
 484                         if (!isexist)
 485                                 return false;
 486                 }
 487
 488                 curq = LQL_NEXT(curq);
 489                 qlen--;
 490         }
 491
 492         return true;
 493 }
 494
 495 static bool
 496 _arrq_cons(ltree_gist *key, ArrayType *_query)
 497 {
 498         lquery     *query = (lquery *) ARR_DATA_PTR(_query);
 499         int                     num = ArrayGetNItems(ARR_NDIM(_query), ARR_DIMS(_query));
 500
 501         if (ARR_NDIM(_query) > 1)
 502                 ereport(ERROR,
 503                                 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
 504                                  errmsg("array must be one-dimensional")));
 505         if (array_contains_nulls(_query))
 506                 ereport(ERROR,
 507                                 (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
 508                                  errmsg("array must not contain nulls")));
 509
 510         while (num > 0)
 511         {
 512                 if (gist_qe(key, query))
 513                         return true;
 514                 num--;
 515                 query = (lquery *) NEXTVAL(query);
 516         }
 517         return false;
 518 }
 519
 520 Datum
 521 _ltree_consistent(PG_FUNCTION_ARGS)
 522 {
 523         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 524         void       *query = (void *) PG_DETOAST_DATUM(PG_GETARG_DATUM(1));
 525         StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
 526
 527         /* Oid          subtype = PG_GETARG_OID(3); */
 528         bool       *recheck = (bool *) PG_GETARG_POINTER(4);
 529         ltree_gist *key = (ltree_gist *) DatumGetPointer(entry->key);
 530         bool            res = false;
 531
 532         /* All cases served by this function are inexact */
 533         *recheck = true;
 534
 535         switch (strategy)
 536         {
 537                 case 10:
 538                 case 11:
 539                         res = gist_te(key, (ltree *) query);
 540                         break;
 541                 case 12:
 542                 case 13:
 543                         res = gist_qe(key, (lquery *) query);
 544                         break;
 545                 case 14:
 546                 case 15:
 547                         res = gist_qtxt(key, (ltxtquery *) query);
 548                         break;
 549                 case 16:
 550                 case 17:
 551                         res = _arrq_cons(key, (ArrayType *) query);
 552                         break;
 553                 default:
 554                         /* internal error */
 555                         elog(ERROR, "unrecognized StrategyNumber: %d", strategy);
 556         }
 557         PG_FREE_IF_COPY(query, 1);
 558         PG_RETURN_BOOL(res);
 559 }