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