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