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

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