src/backend/utils/adt/tsgistidx.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * tsgistidx.c
   4  *        GiST support functions for tsvector_ops
   5  *
   6  * Portions Copyright (c) 1996-2008, 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         /* StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); */
 347         /* Oid          subtype = PG_GETARG_OID(3); */
 348         bool       *recheck = (bool *) PG_GETARG_POINTER(4);
 349         SignTSVector *key = (SignTSVector *) DatumGetPointer(entry->key);
 350
 351         /* All cases served by this function are inexact */
 352         *recheck = true;
 353
 354         if (!query->size)
 355                 PG_RETURN_BOOL(false);
 356
 357         if (ISSIGNKEY(key))
 358         {
 359                 if (ISALLTRUE(key))
 360                         PG_RETURN_BOOL(true);
 361
 362                 PG_RETURN_BOOL(TS_execute(
 363                                                                   GETQUERY(query),
 364                                                                   (void *) GETSIGN(key), false,
 365                                                                   checkcondition_bit
 366                                                                   ));
 367         }
 368         else
 369         {                                                       /* only leaf pages */
 370                 CHKVAL          chkval;
 371
 372                 chkval.arrb = GETARR(key);
 373                 chkval.arre = chkval.arrb + ARRNELEM(key);
 374                 PG_RETURN_BOOL(TS_execute(
 375                                                                   GETQUERY(query),
 376                                                                   (void *) &chkval, true,
 377                                                                   checkcondition_arr
 378                                                                   ));
 379         }
 380 }
 381
 382 static int4
 383 unionkey(BITVECP sbase, SignTSVector *add)
 384 {
 385         int4            i;
 386
 387         if (ISSIGNKEY(add))
 388         {
 389                 BITVECP         sadd = GETSIGN(add);
 390
 391                 if (ISALLTRUE(add))
 392                         return 1;
 393
 394                 LOOPBYTE
 395                         sbase[i] |= sadd[i];
 396         }
 397         else
 398         {
 399                 int4       *ptr = GETARR(add);
 400
 401                 for (i = 0; i < ARRNELEM(add); i++)
 402                         HASH(sbase, ptr[i]);
 403         }
 404         return 0;
 405 }
 406
 407
 408 Datum
 409 gtsvector_union(PG_FUNCTION_ARGS)
 410 {
 411         GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 412         int                *size = (int *) PG_GETARG_POINTER(1);
 413         BITVEC          base;
 414         int4            i,
 415                                 len;
 416         int4            flag = 0;
 417         SignTSVector *result;
 418
 419         MemSet((void *) base, 0, sizeof(BITVEC));
 420         for (i = 0; i < entryvec->n; i++)
 421         {
 422                 if (unionkey(base, GETENTRY(entryvec, i)))
 423                 {
 424                         flag = ALLISTRUE;
 425                         break;
 426                 }
 427         }
 428
 429         flag |= SIGNKEY;
 430         len = CALCGTSIZE(flag, 0);
 431         result = (SignTSVector *) palloc(len);
 432         *size = len;
 433         SET_VARSIZE(result, len);
 434         result->flag = flag;
 435         if (!ISALLTRUE(result))
 436                 memcpy((void *) GETSIGN(result), (void *) base, sizeof(BITVEC));
 437
 438         PG_RETURN_POINTER(result);
 439 }
 440
 441 Datum
 442 gtsvector_same(PG_FUNCTION_ARGS)
 443 {
 444         SignTSVector *a = (SignTSVector *) PG_GETARG_POINTER(0);
 445         SignTSVector *b = (SignTSVector *) PG_GETARG_POINTER(1);
 446         bool       *result = (bool *) PG_GETARG_POINTER(2);
 447
 448         if (ISSIGNKEY(a))
 449         {                                                       /* then b also ISSIGNKEY */
 450                 if (ISALLTRUE(a) && ISALLTRUE(b))
 451                         *result = true;
 452                 else if (ISALLTRUE(a))
 453                         *result = false;
 454                 else if (ISALLTRUE(b))
 455                         *result = false;
 456                 else
 457                 {
 458                         int4            i;
 459                         BITVECP         sa = GETSIGN(a),
 460                                                 sb = GETSIGN(b);
 461
 462                         *result = true;
 463                         LOOPBYTE
 464                         {
 465                                 if (sa[i] != sb[i])
 466                                 {
 467                                         *result = false;
 468                                         break;
 469                                 }
 470                         }
 471                 }
 472         }
 473         else
 474         {                                                       /* a and b ISARRKEY */
 475                 int4            lena = ARRNELEM(a),
 476                                         lenb = ARRNELEM(b);
 477
 478                 if (lena != lenb)
 479                         *result = false;
 480                 else
 481                 {
 482                         int4       *ptra = GETARR(a),
 483                                            *ptrb = GETARR(b);
 484                         int4            i;
 485
 486                         *result = true;
 487                         for (i = 0; i < lena; i++)
 488                                 if (ptra[i] != ptrb[i])
 489                                 {
 490                                         *result = false;
 491                                         break;
 492                                 }
 493                 }
 494         }
 495
 496         PG_RETURN_POINTER(result);
 497 }
 498
 499 static int4
 500 sizebitvec(BITVECP sign)
 501 {
 502         int4            size = 0,
 503                                 i;
 504
 505         LOOPBYTE
 506                 size += number_of_ones[(unsigned char) sign[i]];
 507         return size;
 508 }
 509
 510 static int
 511 hemdistsign(BITVECP a, BITVECP b)
 512 {
 513         int                     i,
 514                                 diff,
 515                                 dist = 0;
 516
 517         LOOPBYTE
 518         {
 519                 diff = (unsigned char) (a[i] ^ b[i]);
 520                 dist += number_of_ones[diff];
 521         }
 522         return dist;
 523 }
 524
 525 static int
 526 hemdist(SignTSVector *a, SignTSVector *b)
 527 {
 528         if (ISALLTRUE(a))
 529         {
 530                 if (ISALLTRUE(b))
 531                         return 0;
 532                 else
 533                         return SIGLENBIT - sizebitvec(GETSIGN(b));
 534         }
 535         else if (ISALLTRUE(b))
 536                 return SIGLENBIT - sizebitvec(GETSIGN(a));
 537
 538         return hemdistsign(GETSIGN(a), GETSIGN(b));
 539 }
 540
 541 Datum
 542 gtsvector_penalty(PG_FUNCTION_ARGS)
 543 {
 544         GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
 545         GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
 546         float      *penalty = (float *) PG_GETARG_POINTER(2);
 547         SignTSVector *origval = (SignTSVector *) DatumGetPointer(origentry->key);
 548         SignTSVector *newval = (SignTSVector *) DatumGetPointer(newentry->key);
 549         BITVECP         orig = GETSIGN(origval);
 550
 551         *penalty = 0.0;
 552
 553         if (ISARRKEY(newval))
 554         {
 555                 BITVEC          sign;
 556
 557                 makesign(sign, newval);
 558
 559                 if (ISALLTRUE(origval))
 560                         *penalty = ((float) (SIGLENBIT - sizebitvec(sign))) / (float) (SIGLENBIT + 1);
 561                 else
 562                         *penalty = hemdistsign(sign, orig);
 563         }
 564         else
 565                 *penalty = hemdist(origval, newval);
 566         PG_RETURN_POINTER(penalty);
 567 }
 568
 569 typedef struct
 570 {
 571         bool            allistrue;
 572         BITVEC          sign;
 573 } CACHESIGN;
 574
 575 static void
 576 fillcache(CACHESIGN *item, SignTSVector *key)
 577 {
 578         item->allistrue = false;
 579         if (ISARRKEY(key))
 580                 makesign(item->sign, key);
 581         else if (ISALLTRUE(key))
 582                 item->allistrue = true;
 583         else
 584                 memcpy((void *) item->sign, (void *) GETSIGN(key), sizeof(BITVEC));
 585 }
 586
 587 #define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
 588 typedef struct
 589 {
 590         OffsetNumber pos;
 591         int4            cost;
 592 } SPLITCOST;
 593
 594 static int
 595 comparecost(const void *va, const void *vb)
 596 {
 597         SPLITCOST  *a = (SPLITCOST *) va;
 598         SPLITCOST  *b = (SPLITCOST *) vb;
 599
 600         if (a->cost == b->cost)
 601                 return 0;
 602         else
 603                 return (a->cost > b->cost) ? 1 : -1;
 604 }
 605
 606
 607 static int
 608 hemdistcache(CACHESIGN *a, CACHESIGN *b)
 609 {
 610         if (a->allistrue)
 611         {
 612                 if (b->allistrue)
 613                         return 0;
 614                 else
 615                         return SIGLENBIT - sizebitvec(b->sign);
 616         }
 617         else if (b->allistrue)
 618                 return SIGLENBIT - sizebitvec(a->sign);
 619
 620         return hemdistsign(a->sign, b->sign);
 621 }
 622
 623 Datum
 624 gtsvector_picksplit(PG_FUNCTION_ARGS)
 625 {
 626         GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 627         GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
 628         OffsetNumber k,
 629                                 j;
 630         SignTSVector *datum_l,
 631                            *datum_r;
 632         BITVECP         union_l,
 633                                 union_r;
 634         int4            size_alpha,
 635                                 size_beta;
 636         int4            size_waste,
 637                                 waste = -1;
 638         int4            nbytes;
 639         OffsetNumber seed_1 = 0,
 640                                 seed_2 = 0;
 641         OffsetNumber *left,
 642                            *right;
 643         OffsetNumber maxoff;
 644         BITVECP         ptr;
 645         int                     i;
 646         CACHESIGN  *cache;
 647         SPLITCOST  *costvector;
 648
 649         maxoff = entryvec->n - 2;
 650         nbytes = (maxoff + 2) * sizeof(OffsetNumber);
 651         v->spl_left = (OffsetNumber *) palloc(nbytes);
 652         v->spl_right = (OffsetNumber *) palloc(nbytes);
 653
 654         cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (maxoff + 2));
 655         fillcache(&cache[FirstOffsetNumber], GETENTRY(entryvec, FirstOffsetNumber));
 656
 657         for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
 658         {
 659                 for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
 660                 {
 661                         if (k == FirstOffsetNumber)
 662                                 fillcache(&cache[j], GETENTRY(entryvec, j));
 663
 664                         size_waste = hemdistcache(&(cache[j]), &(cache[k]));
 665                         if (size_waste > waste)
 666                         {
 667                                 waste = size_waste;
 668                                 seed_1 = k;
 669                                 seed_2 = j;
 670                         }
 671                 }
 672         }
 673
 674         left = v->spl_left;
 675         v->spl_nleft = 0;
 676         right = v->spl_right;
 677         v->spl_nright = 0;
 678
 679         if (seed_1 == 0 || seed_2 == 0)
 680         {
 681                 seed_1 = 1;
 682                 seed_2 = 2;
 683         }
 684
 685         /* form initial .. */
 686         if (cache[seed_1].allistrue)
 687         {
 688                 datum_l = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
 689                 SET_VARSIZE(datum_l, CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
 690                 datum_l->flag = SIGNKEY | ALLISTRUE;
 691         }
 692         else
 693         {
 694                 datum_l = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY, 0));
 695                 SET_VARSIZE(datum_l, CALCGTSIZE(SIGNKEY, 0));
 696                 datum_l->flag = SIGNKEY;
 697                 memcpy((void *) GETSIGN(datum_l), (void *) cache[seed_1].sign, sizeof(BITVEC));
 698         }
 699         if (cache[seed_2].allistrue)
 700         {
 701                 datum_r = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
 702                 SET_VARSIZE(datum_r, CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
 703                 datum_r->flag = SIGNKEY | ALLISTRUE;
 704         }
 705         else
 706         {
 707                 datum_r = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY, 0));
 708                 SET_VARSIZE(datum_r, CALCGTSIZE(SIGNKEY, 0));
 709                 datum_r->flag = SIGNKEY;
 710                 memcpy((void *) GETSIGN(datum_r), (void *) cache[seed_2].sign, sizeof(BITVEC));
 711         }
 712
 713         union_l = GETSIGN(datum_l);
 714         union_r = GETSIGN(datum_r);
 715         maxoff = OffsetNumberNext(maxoff);
 716         fillcache(&cache[maxoff], GETENTRY(entryvec, maxoff));
 717         /* sort before ... */
 718         costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
 719         for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
 720         {
 721                 costvector[j - 1].pos = j;
 722                 size_alpha = hemdistcache(&(cache[seed_1]), &(cache[j]));
 723                 size_beta = hemdistcache(&(cache[seed_2]), &(cache[j]));
 724                 costvector[j - 1].cost = Abs(size_alpha - size_beta);
 725         }
 726         qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
 727
 728         for (k = 0; k < maxoff; k++)
 729         {
 730                 j = costvector[k].pos;
 731                 if (j == seed_1)
 732                 {
 733                         *left++ = j;
 734                         v->spl_nleft++;
 735                         continue;
 736                 }
 737                 else if (j == seed_2)
 738                 {
 739                         *right++ = j;
 740                         v->spl_nright++;
 741                         continue;
 742                 }
 743
 744                 if (ISALLTRUE(datum_l) || cache[j].allistrue)
 745                 {
 746                         if (ISALLTRUE(datum_l) && cache[j].allistrue)
 747                                 size_alpha = 0;
 748                         else
 749                                 size_alpha = SIGLENBIT - sizebitvec(
 750                                                                                                         (cache[j].allistrue) ? GETSIGN(datum_l) : GETSIGN(cache[j].sign)
 751                                         );
 752                 }
 753                 else
 754                         size_alpha = hemdistsign(cache[j].sign, GETSIGN(datum_l));
 755
 756                 if (ISALLTRUE(datum_r) || cache[j].allistrue)
 757                 {
 758                         if (ISALLTRUE(datum_r) && cache[j].allistrue)
 759                                 size_beta = 0;
 760                         else
 761                                 size_beta = SIGLENBIT - sizebitvec(
 762                                                                                                    (cache[j].allistrue) ? GETSIGN(datum_r) : GETSIGN(cache[j].sign)
 763                                         );
 764                 }
 765                 else
 766                         size_beta = hemdistsign(cache[j].sign, GETSIGN(datum_r));
 767
 768                 if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.1))
 769                 {
 770                         if (ISALLTRUE(datum_l) || cache[j].allistrue)
 771                         {
 772                                 if (!ISALLTRUE(datum_l))
 773                                         MemSet((void *) GETSIGN(datum_l), 0xff, sizeof(BITVEC));
 774                         }
 775                         else
 776                         {
 777                                 ptr = cache[j].sign;
 778                                 LOOPBYTE
 779                                         union_l[i] |= ptr[i];
 780                         }
 781                         *left++ = j;
 782                         v->spl_nleft++;
 783                 }
 784                 else
 785                 {
 786                         if (ISALLTRUE(datum_r) || cache[j].allistrue)
 787                         {
 788                                 if (!ISALLTRUE(datum_r))
 789                                         MemSet((void *) GETSIGN(datum_r), 0xff, sizeof(BITVEC));
 790                         }
 791                         else
 792                         {
 793                                 ptr = cache[j].sign;
 794                                 LOOPBYTE
 795                                         union_r[i] |= ptr[i];
 796                         }
 797                         *right++ = j;
 798                         v->spl_nright++;
 799                 }
 800         }
 801
 802         *right = *left = FirstOffsetNumber;
 803         v->spl_ldatum = PointerGetDatum(datum_l);
 804         v->spl_rdatum = PointerGetDatum(datum_r);
 805
 806         PG_RETURN_POINTER(v);
 807 }