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