src/backend/utils/adt/tsgistidx.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * tsgistidx.c
   4  *        GiST support functions for tsvector_ops
   5  *
   6  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $PostgreSQL$
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14
  15 #include "postgres.h"
  16
  17 #include "access/gist.h"
  18 #include "access/tuptoaster.h"
  19 #include "tsearch/ts_type.h"
  20 #include "tsearch/ts_utils.h"
  21 #include "utils/pg_crc.h"
  22
  23
  24 #define SIGLENINT  31                   /* >121 => key will toast, so it will not work
  25                                                                  * !!! */
  26
  27 #define SIGLEN  ( sizeof(int4) * SIGLENINT )
  28 #define SIGLENBIT (SIGLEN * BITS_PER_BYTE)
  29
  30 typedef char BITVEC[SIGLEN];
  31 typedef char *BITVECP;
  32
  33 #define LOOPBYTE \
  34                         for(i=0;i<SIGLEN;i++)
  35
  36 #define GETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITS_PER_BYTE ) ) )
  37 #define GETBITBYTE(x,i) ( ((char)(x)) >> (i) & 0x01 )
  38 #define CLRBIT(x,i)   GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITS_PER_BYTE ) )
  39 #define SETBIT(x,i)   GETBYTE(x,i) |=  ( 0x01 << ( (i) % BITS_PER_BYTE ) )
  40 #define GETBIT(x,i) ( (GETBYTE(x,i) >> ( (i) % BITS_PER_BYTE )) & 0x01 )
  41
  42 #define HASHVAL(val) (((unsigned int)(val)) % SIGLENBIT)
  43 #define HASH(sign, val) SETBIT((sign), HASHVAL(val))
  44
  45 #define GETENTRY(vec,pos) ((SignTSVector *) DatumGetPointer((vec)->vector[(pos)].key))
  46
  47 /*
  48  * type of GiST index key
  49  */
  50
  51 typedef struct
  52 {
  53         int32           vl_len_;                /* varlena header (do not touch directly!) */
  54         int4            flag;
  55         char            data[1];
  56 } SignTSVector;
  57
  58 #define ARRKEY          0x01
  59 #define SIGNKEY         0x02
  60 #define ALLISTRUE       0x04
  61
  62 #define ISARRKEY(x) ( ((SignTSVector*)(x))->flag & ARRKEY )
  63 #define ISSIGNKEY(x)    ( ((SignTSVector*)(x))->flag & SIGNKEY )
  64 #define ISALLTRUE(x)    ( ((SignTSVector*)(x))->flag & ALLISTRUE )
  65
  66 #define GTHDRSIZE       ( VARHDRSZ + sizeof(int4) )
  67 #define CALCGTSIZE(flag, len) ( GTHDRSIZE + ( ( (flag) & ARRKEY ) ? ((len)*sizeof(int4)) : (((flag) & ALLISTRUE) ? 0 : SIGLEN) ) )
  68
  69 #define GETSIGN(x)      ( (BITVECP)( (char*)(x)+GTHDRSIZE ) )
  70 #define GETARR(x)       ( (int4*)( (char*)(x)+GTHDRSIZE ) )
  71 #define ARRNELEM(x) ( ( VARSIZE(x) - GTHDRSIZE )/sizeof(int4) )
  72
  73 /* Number of one-bits in an unsigned byte */
  74 static const uint8 number_of_ones[256] = {
  75         0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  76         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  77         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  78         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  79         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  80         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  81         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  82         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  83         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  84         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  85         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  86         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  87         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  88         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  89         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  90         4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
  91 };
  92
  93 static int4 sizebitvec(BITVECP sign);
  94
  95 Datum
  96 gtsvectorin(PG_FUNCTION_ARGS)
  97 {
  98         ereport(ERROR,
  99                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 100                          errmsg("gtsvector_in not implemented")));
 101         PG_RETURN_DATUM(0);
 102 }
 103
 104 #define SINGOUTSTR      "%d true bits, %d false bits"
 105 #define ARROUTSTR       "%d unique words"
 106 #define EXTRALEN        ( 2*13 )
 107
 108 static int      outbuf_maxlen = 0;
 109
 110 Datum
 111 gtsvectorout(PG_FUNCTION_ARGS)
 112 {
 113         SignTSVector *key = (SignTSVector *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_POINTER(0)));
 114         char       *outbuf;
 115
 116         if (outbuf_maxlen == 0)
 117                 outbuf_maxlen = 2 * EXTRALEN + Max(strlen(SINGOUTSTR), strlen(ARROUTSTR)) + 1;
 118         outbuf = palloc(outbuf_maxlen);
 119
 120         if (ISARRKEY(key))
 121                 sprintf(outbuf, ARROUTSTR, (int) ARRNELEM(key));
 122         else
 123         {
 124                 int                     cnttrue = (ISALLTRUE(key)) ? SIGLENBIT : sizebitvec(GETSIGN(key));
 125
 126                 sprintf(outbuf, SINGOUTSTR, cnttrue, (int) SIGLENBIT - cnttrue);
 127         }
 128
 129         PG_FREE_IF_COPY(key, 0);
 130         PG_RETURN_POINTER(outbuf);
 131 }
 132
 133 static int
 134 compareint(const void *va, const void *vb)
 135 {
 136         int4            a = *((int4 *) va);
 137         int4            b = *((int4 *) vb);
 138
 139         if (a == b)
 140                 return 0;
 141         return (a > b) ? 1 : -1;
 142 }
 143
 144 /*
 145  * Removes duplicates from an array of int4. 'l' is
 146  * size of the input array. Returns the new size of the array.
 147  */
 148 static int
 149 uniqueint(int4 *a, int4 l)
 150 {
 151         int4       *ptr,
 152                            *res;
 153
 154         if (l <= 1)
 155                 return l;
 156
 157         ptr = res = a;
 158
 159         qsort((void *) a, l, sizeof(int4), compareint);
 160
 161         while (ptr - a < l)
 162                 if (*ptr != *res)
 163                         *(++res) = *ptr++;
 164                 else
 165                         ptr++;
 166         return res + 1 - a;
 167 }
 168
 169 static void
 170 makesign(BITVECP sign, SignTSVector *a)
 171 {
 172         int4            k,
 173                                 len = ARRNELEM(a);
 174         int4       *ptr = GETARR(a);
 175
 176         MemSet((void *) sign, 0, sizeof(BITVEC));
 177         for (k = 0; k < len; k++)
 178                 HASH(sign, ptr[k]);
 179 }
 180
 181 Datum
 182 gtsvector_compress(PG_FUNCTION_ARGS)
 183 {
 184         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 185         GISTENTRY  *retval = entry;
 186
 187         if (entry->leafkey)
 188         {                                                       /* tsvector */
 189                 SignTSVector *res;
 190                 TSVector        val = DatumGetTSVector(entry->key);
 191                 int4            len;
 192                 int4       *arr;
 193                 WordEntry  *ptr = ARRPTR(val);
 194                 char       *words = STRPTR(val);
 195
 196                 len = CALCGTSIZE(ARRKEY, val->size);
 197                 res = (SignTSVector *) palloc(len);
 198                 SET_VARSIZE(res, len);
 199                 res->flag = ARRKEY;
 200                 arr = GETARR(res);
 201                 len = val->size;
 202                 while (len--)
 203                 {
 204                         pg_crc32        c;
 205
 206                         INIT_CRC32(c);
 207                         COMP_CRC32(c, words + ptr->pos, ptr->len);
 208                         FIN_CRC32(c);
 209
 210                         *arr = *(int4 *) &c;
 211                         arr++;
 212                         ptr++;
 213                 }
 214
 215                 len = uniqueint(GETARR(res), val->size);
 216                 if (len != val->size)
 217                 {
 218                         /*
 219                          * there is a collision of hash-function; len is always less than
 220                          * val->size
 221                          */
 222                         len = CALCGTSIZE(ARRKEY, len);
 223                         res = (SignTSVector *) repalloc((void *) res, len);
 224                         SET_VARSIZE(res, len);
 225                 }
 226
 227                 /* make signature, if array is too long */
 228                 if (VARSIZE(res) > TOAST_INDEX_TARGET)
 229                 {
 230                         SignTSVector *ressign;
 231
 232                         len = CALCGTSIZE(SIGNKEY, 0);
 233                         ressign = (SignTSVector *) palloc(len);
 234                         SET_VARSIZE(ressign, len);
 235                         ressign->flag = SIGNKEY;
 236                         makesign(GETSIGN(ressign), res);
 237                         res = ressign;
 238                 }
 239
 240                 retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
 241                 gistentryinit(*retval, PointerGetDatum(res),
 242                                           entry->rel, entry->page,
 243                                           entry->offset, FALSE);
 244         }
 245         else if (ISSIGNKEY(DatumGetPointer(entry->key)) &&
 246                          !ISALLTRUE(DatumGetPointer(entry->key)))
 247         {
 248                 int4            i,
 249                                         len;
 250                 SignTSVector *res;
 251                 BITVECP         sign = GETSIGN(DatumGetPointer(entry->key));
 252
 253                 LOOPBYTE
 254                 {
 255                         if ((sign[i] & 0xff) != 0xff)
 256                                 PG_RETURN_POINTER(retval);
 257                 }
 258
 259                 len = CALCGTSIZE(SIGNKEY | ALLISTRUE, 0);
 260                 res = (SignTSVector *) palloc(len);
 261                 SET_VARSIZE(res, len);
 262                 res->flag = SIGNKEY | ALLISTRUE;
 263
 264                 retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
 265                 gistentryinit(*retval, PointerGetDatum(res),
 266                                           entry->rel, entry->page,
 267                                           entry->offset, FALSE);
 268         }
 269         PG_RETURN_POINTER(retval);
 270 }
 271
 272 Datum
 273 gtsvector_decompress(PG_FUNCTION_ARGS)
 274 {
 275         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 276         SignTSVector *key = (SignTSVector *) DatumGetPointer(PG_DETOAST_DATUM(entry->key));
 277
 278         if (key != (SignTSVector *) DatumGetPointer(entry->key))
 279         {
 280                 GISTENTRY  *retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
 281
 282                 gistentryinit(*retval, PointerGetDatum(key),
 283                                           entry->rel, entry->page,
 284                                           entry->offset, FALSE);
 285
 286                 PG_RETURN_POINTER(retval);
 287         }
 288
 289         PG_RETURN_POINTER(entry);
 290 }
 291
 292 typedef struct
 293 {
 294         int4       *arrb;
 295         int4       *arre;
 296 } CHKVAL;
 297
 298 /*
 299  * is there value 'val' in array or not ?
 300  */
 301 static bool
 302 checkcondition_arr(void *checkval, QueryOperand *val)
 303 {
 304         int4       *StopLow = ((CHKVAL *) checkval)->arrb;
 305         int4       *StopHigh = ((CHKVAL *) checkval)->arre;
 306         int4       *StopMiddle;
 307
 308         /* Loop invariant: StopLow <= val < StopHigh */
 309
 310         /*
 311          * we are not able to find a a prefix by hash value
 312          */
 313         if (val->prefix)
 314                 return true;
 315
 316         while (StopLow < StopHigh)
 317         {
 318                 StopMiddle = StopLow + (StopHigh - StopLow) / 2;
 319                 if (*StopMiddle == val->valcrc)
 320                         return (true);
 321                 else if (*StopMiddle < val->valcrc)
 322                         StopLow = StopMiddle + 1;
 323                 else
 324                         StopHigh = StopMiddle;
 325         }
 326
 327         return (false);
 328 }
 329
 330 static bool
 331 checkcondition_bit(void *checkval, QueryOperand *val)
 332 {
 333         /*
 334          * we are not able to find a a prefix in signature tree
 335          */
 336         if (val->prefix)
 337                 return true;
 338         return GETBIT(checkval, HASHVAL(val->valcrc));
 339 }
 340
 341 Datum
 342 gtsvector_consistent(PG_FUNCTION_ARGS)
 343 {
 344         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 345         TSQuery         query = PG_GETARG_TSQUERY(1);
 346
 347         /* StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); */
 348         /* Oid          subtype = PG_GETARG_OID(3); */
 349         bool       *recheck = (bool *) PG_GETARG_POINTER(4);
 350         SignTSVector *key = (SignTSVector *) DatumGetPointer(entry->key);
 351
 352         /* All cases served by this function are inexact */
 353         *recheck = true;
 354
 355         if (!query->size)
 356                 PG_RETURN_BOOL(false);
 357
 358         if (ISSIGNKEY(key))
 359         {
 360                 if (ISALLTRUE(key))
 361                         PG_RETURN_BOOL(true);
 362
 363                 PG_RETURN_BOOL(TS_execute(
 364                                                                   GETQUERY(query),
 365                                                                   (void *) GETSIGN(key), false,
 366                                                                   checkcondition_bit
 367                                                                   ));
 368         }
 369         else
 370         {                                                       /* only leaf pages */
 371                 CHKVAL          chkval;
 372
 373                 chkval.arrb = GETARR(key);
 374                 chkval.arre = chkval.arrb + ARRNELEM(key);
 375                 PG_RETURN_BOOL(TS_execute(
 376                                                                   GETQUERY(query),
 377                                                                   (void *) &chkval, true,
 378                                                                   checkcondition_arr
 379                                                                   ));
 380         }
 381 }
 382
 383 static int4
 384 unionkey(BITVECP sbase, SignTSVector *add)
 385 {
 386         int4            i;
 387
 388         if (ISSIGNKEY(add))
 389         {
 390                 BITVECP         sadd = GETSIGN(add);
 391
 392                 if (ISALLTRUE(add))
 393                         return 1;
 394
 395                 LOOPBYTE
 396                         sbase[i] |= sadd[i];
 397         }
 398         else
 399         {
 400                 int4       *ptr = GETARR(add);
 401
 402                 for (i = 0; i < ARRNELEM(add); i++)
 403                         HASH(sbase, ptr[i]);
 404         }
 405         return 0;
 406 }
 407
 408
 409 Datum
 410 gtsvector_union(PG_FUNCTION_ARGS)
 411 {
 412         GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 413         int                *size = (int *) PG_GETARG_POINTER(1);
 414         BITVEC          base;
 415         int4            i,
 416                                 len;
 417         int4            flag = 0;
 418         SignTSVector *result;
 419
 420         MemSet((void *) base, 0, sizeof(BITVEC));
 421         for (i = 0; i < entryvec->n; i++)
 422         {
 423                 if (unionkey(base, GETENTRY(entryvec, i)))
 424                 {
 425                         flag = ALLISTRUE;
 426                         break;
 427                 }
 428         }
 429
 430         flag |= SIGNKEY;
 431         len = CALCGTSIZE(flag, 0);
 432         result = (SignTSVector *) palloc(len);
 433         *size = len;
 434         SET_VARSIZE(result, len);
 435         result->flag = flag;
 436         if (!ISALLTRUE(result))
 437                 memcpy((void *) GETSIGN(result), (void *) base, sizeof(BITVEC));
 438
 439         PG_RETURN_POINTER(result);
 440 }
 441
 442 Datum
 443 gtsvector_same(PG_FUNCTION_ARGS)
 444 {
 445         SignTSVector *a = (SignTSVector *) PG_GETARG_POINTER(0);
 446         SignTSVector *b = (SignTSVector *) PG_GETARG_POINTER(1);
 447         bool       *result = (bool *) PG_GETARG_POINTER(2);
 448
 449         if (ISSIGNKEY(a))
 450         {                                                       /* then b also ISSIGNKEY */
 451                 if (ISALLTRUE(a) && ISALLTRUE(b))
 452                         *result = true;
 453                 else if (ISALLTRUE(a))
 454                         *result = false;
 455                 else if (ISALLTRUE(b))
 456                         *result = false;
 457                 else
 458                 {
 459                         int4            i;
 460                         BITVECP         sa = GETSIGN(a),
 461                                                 sb = GETSIGN(b);
 462
 463                         *result = true;
 464                         LOOPBYTE
 465                         {
 466                                 if (sa[i] != sb[i])
 467                                 {
 468                                         *result = false;
 469                                         break;
 470                                 }
 471                         }
 472                 }
 473         }
 474         else
 475         {                                                       /* a and b ISARRKEY */
 476                 int4            lena = ARRNELEM(a),
 477                                         lenb = ARRNELEM(b);
 478
 479                 if (lena != lenb)
 480                         *result = false;
 481                 else
 482                 {
 483                         int4       *ptra = GETARR(a),
 484                                            *ptrb = GETARR(b);
 485                         int4            i;
 486
 487                         *result = true;
 488                         for (i = 0; i < lena; i++)
 489                                 if (ptra[i] != ptrb[i])
 490                                 {
 491                                         *result = false;
 492                                         break;
 493                                 }
 494                 }
 495         }
 496
 497         PG_RETURN_POINTER(result);
 498 }
 499
 500 static int4
 501 sizebitvec(BITVECP sign)
 502 {
 503         int4            size = 0,
 504                                 i;
 505
 506         LOOPBYTE
 507                 size += number_of_ones[(unsigned char) sign[i]];
 508         return size;
 509 }
 510
 511 static int
 512 hemdistsign(BITVECP a, BITVECP b)
 513 {
 514         int                     i,
 515                                 diff,
 516                                 dist = 0;
 517
 518         LOOPBYTE
 519         {
 520                 diff = (unsigned char) (a[i] ^ b[i]);
 521                 dist += number_of_ones[diff];
 522         }
 523         return dist;
 524 }
 525
 526 static int
 527 hemdist(SignTSVector *a, SignTSVector *b)
 528 {
 529         if (ISALLTRUE(a))
 530         {
 531                 if (ISALLTRUE(b))
 532                         return 0;
 533                 else
 534                         return SIGLENBIT - sizebitvec(GETSIGN(b));
 535         }
 536         else if (ISALLTRUE(b))
 537                 return SIGLENBIT - sizebitvec(GETSIGN(a));
 538
 539         return hemdistsign(GETSIGN(a), GETSIGN(b));
 540 }
 541
 542 Datum
 543 gtsvector_penalty(PG_FUNCTION_ARGS)
 544 {
 545         GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
 546         GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
 547         float      *penalty = (float *) PG_GETARG_POINTER(2);
 548         SignTSVector *origval = (SignTSVector *) DatumGetPointer(origentry->key);
 549         SignTSVector *newval = (SignTSVector *) DatumGetPointer(newentry->key);
 550         BITVECP         orig = GETSIGN(origval);
 551
 552         *penalty = 0.0;
 553
 554         if (ISARRKEY(newval))
 555         {
 556                 BITVEC          sign;
 557
 558                 makesign(sign, newval);
 559
 560                 if (ISALLTRUE(origval))
 561                         *penalty = ((float) (SIGLENBIT - sizebitvec(sign))) / (float) (SIGLENBIT + 1);
 562                 else
 563                         *penalty = hemdistsign(sign, orig);
 564         }
 565         else
 566                 *penalty = hemdist(origval, newval);
 567         PG_RETURN_POINTER(penalty);
 568 }
 569
 570 typedef struct
 571 {
 572         bool            allistrue;
 573         BITVEC          sign;
 574 } CACHESIGN;
 575
 576 static void
 577 fillcache(CACHESIGN *item, SignTSVector *key)
 578 {
 579         item->allistrue = false;
 580         if (ISARRKEY(key))
 581                 makesign(item->sign, key);
 582         else if (ISALLTRUE(key))
 583                 item->allistrue = true;
 584         else
 585                 memcpy((void *) item->sign, (void *) GETSIGN(key), sizeof(BITVEC));
 586 }
 587
 588 #define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
 589 typedef struct
 590 {
 591         OffsetNumber pos;
 592         int4            cost;
 593 } SPLITCOST;
 594
 595 static int
 596 comparecost(const void *va, const void *vb)
 597 {
 598         SPLITCOST  *a = (SPLITCOST *) va;
 599         SPLITCOST  *b = (SPLITCOST *) vb;
 600
 601         if (a->cost == b->cost)
 602                 return 0;
 603         else
 604                 return (a->cost > b->cost) ? 1 : -1;
 605 }
 606
 607
 608 static int
 609 hemdistcache(CACHESIGN *a, CACHESIGN *b)
 610 {
 611         if (a->allistrue)
 612         {
 613                 if (b->allistrue)
 614                         return 0;
 615                 else
 616                         return SIGLENBIT - sizebitvec(b->sign);
 617         }
 618         else if (b->allistrue)
 619                 return SIGLENBIT - sizebitvec(a->sign);
 620
 621         return hemdistsign(a->sign, b->sign);
 622 }
 623
 624 Datum
 625 gtsvector_picksplit(PG_FUNCTION_ARGS)
 626 {
 627         GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 628         GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
 629         OffsetNumber k,
 630                                 j;
 631         SignTSVector *datum_l,
 632                            *datum_r;
 633         BITVECP         union_l,
 634                                 union_r;
 635         int4            size_alpha,
 636                                 size_beta;
 637         int4            size_waste,
 638                                 waste = -1;
 639         int4            nbytes;
 640         OffsetNumber seed_1 = 0,
 641                                 seed_2 = 0;
 642         OffsetNumber *left,
 643                            *right;
 644         OffsetNumber maxoff;
 645         BITVECP         ptr;
 646         int                     i;
 647         CACHESIGN  *cache;
 648         SPLITCOST  *costvector;
 649
 650         maxoff = entryvec->n - 2;
 651         nbytes = (maxoff + 2) * sizeof(OffsetNumber);
 652         v->spl_left = (OffsetNumber *) palloc(nbytes);
 653         v->spl_right = (OffsetNumber *) palloc(nbytes);
 654
 655         cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (maxoff + 2));
 656         fillcache(&cache[FirstOffsetNumber], GETENTRY(entryvec, FirstOffsetNumber));
 657
 658         for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
 659         {
 660                 for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
 661                 {
 662                         if (k == FirstOffsetNumber)
 663                                 fillcache(&cache[j], GETENTRY(entryvec, j));
 664
 665                         size_waste = hemdistcache(&(cache[j]), &(cache[k]));
 666                         if (size_waste > waste)
 667                         {
 668                                 waste = size_waste;
 669                                 seed_1 = k;
 670                                 seed_2 = j;
 671                         }
 672                 }
 673         }
 674
 675         left = v->spl_left;
 676         v->spl_nleft = 0;
 677         right = v->spl_right;
 678         v->spl_nright = 0;
 679
 680         if (seed_1 == 0 || seed_2 == 0)
 681         {
 682                 seed_1 = 1;
 683                 seed_2 = 2;
 684         }
 685
 686         /* form initial .. */
 687         if (cache[seed_1].allistrue)
 688         {
 689                 datum_l = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
 690                 SET_VARSIZE(datum_l, CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
 691                 datum_l->flag = SIGNKEY | ALLISTRUE;
 692         }
 693         else
 694         {
 695                 datum_l = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY, 0));
 696                 SET_VARSIZE(datum_l, CALCGTSIZE(SIGNKEY, 0));
 697                 datum_l->flag = SIGNKEY;
 698                 memcpy((void *) GETSIGN(datum_l), (void *) cache[seed_1].sign, sizeof(BITVEC));
 699         }
 700         if (cache[seed_2].allistrue)
 701         {
 702                 datum_r = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
 703                 SET_VARSIZE(datum_r, CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
 704                 datum_r->flag = SIGNKEY | ALLISTRUE;
 705         }
 706         else
 707         {
 708                 datum_r = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY, 0));
 709                 SET_VARSIZE(datum_r, CALCGTSIZE(SIGNKEY, 0));
 710                 datum_r->flag = SIGNKEY;
 711                 memcpy((void *) GETSIGN(datum_r), (void *) cache[seed_2].sign, sizeof(BITVEC));
 712         }
 713
 714         union_l = GETSIGN(datum_l);
 715         union_r = GETSIGN(datum_r);
 716         maxoff = OffsetNumberNext(maxoff);
 717         fillcache(&cache[maxoff], GETENTRY(entryvec, maxoff));
 718         /* sort before ... */
 719         costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
 720         for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
 721         {
 722                 costvector[j - 1].pos = j;
 723                 size_alpha = hemdistcache(&(cache[seed_1]), &(cache[j]));
 724                 size_beta = hemdistcache(&(cache[seed_2]), &(cache[j]));
 725                 costvector[j - 1].cost = Abs(size_alpha - size_beta);
 726         }
 727         qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
 728
 729         for (k = 0; k < maxoff; k++)
 730         {
 731                 j = costvector[k].pos;
 732                 if (j == seed_1)
 733                 {
 734                         *left++ = j;
 735                         v->spl_nleft++;
 736                         continue;
 737                 }
 738                 else if (j == seed_2)
 739                 {
 740                         *right++ = j;
 741                         v->spl_nright++;
 742                         continue;
 743                 }
 744
 745                 if (ISALLTRUE(datum_l) || cache[j].allistrue)
 746                 {
 747                         if (ISALLTRUE(datum_l) && cache[j].allistrue)
 748                                 size_alpha = 0;
 749                         else
 750                                 size_alpha = SIGLENBIT - sizebitvec(
 751                                                                                                         (cache[j].allistrue) ? GETSIGN(datum_l) : GETSIGN(cache[j].sign)
 752                                         );
 753                 }
 754                 else
 755                         size_alpha = hemdistsign(cache[j].sign, GETSIGN(datum_l));
 756
 757                 if (ISALLTRUE(datum_r) || cache[j].allistrue)
 758                 {
 759                         if (ISALLTRUE(datum_r) && cache[j].allistrue)
 760                                 size_beta = 0;
 761                         else
 762                                 size_beta = SIGLENBIT - sizebitvec(
 763                                                                                                    (cache[j].allistrue) ? GETSIGN(datum_r) : GETSIGN(cache[j].sign)
 764                                         );
 765                 }
 766                 else
 767                         size_beta = hemdistsign(cache[j].sign, GETSIGN(datum_r));
 768
 769                 if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.1))
 770                 {
 771                         if (ISALLTRUE(datum_l) || cache[j].allistrue)
 772                         {
 773                                 if (!ISALLTRUE(datum_l))
 774                                         MemSet((void *) GETSIGN(datum_l), 0xff, sizeof(BITVEC));
 775                         }
 776                         else
 777                         {
 778                                 ptr = cache[j].sign;
 779                                 LOOPBYTE
 780                                         union_l[i] |= ptr[i];
 781                         }
 782                         *left++ = j;
 783                         v->spl_nleft++;
 784                 }
 785                 else
 786                 {
 787                         if (ISALLTRUE(datum_r) || cache[j].allistrue)
 788                         {
 789                                 if (!ISALLTRUE(datum_r))
 790                                         MemSet((void *) GETSIGN(datum_r), 0xff, sizeof(BITVEC));
 791                         }
 792                         else
 793                         {
 794                                 ptr = cache[j].sign;
 795                                 LOOPBYTE
 796                                         union_r[i] |= ptr[i];
 797                         }
 798                         *right++ = j;
 799                         v->spl_nright++;
 800                 }
 801         }
 802
 803         *right = *left = FirstOffsetNumber;
 804         v->spl_ldatum = PointerGetDatum(datum_l);
 805         v->spl_rdatum = PointerGetDatum(datum_r);
 806
 807         PG_RETURN_POINTER(v);
 808 }