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