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