granicus.if.org Git - postgresql/blob - contrib/intarray/_intbig_gist.c

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