TLA 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 UBC 0 : gtsvectorin(PG_FUNCTION_ARGS)
89 : {
90 : /* There's no need to support input of gtsvectors */
91 UIC 0 : ereport(ERROR,
92 EUB : (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 UIC 0 : gtsvectorout(PG_FUNCTION_ARGS)
106 : {
107 UNC 0 : SignTSVector *key = (SignTSVector *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
108 : char *outbuf;
109 EUB :
110 UIC 0 : if (outbuf_maxlen == 0)
111 0 : outbuf_maxlen = 2 * EXTRALEN + Max(strlen(SINGOUTSTR), strlen(ARROUTSTR)) + 1;
112 UBC 0 : outbuf = palloc(outbuf_maxlen);
113 EUB :
114 UBC 0 : if (ISARRKEY(key))
115 UIC 0 : sprintf(outbuf, ARROUTSTR, (int) ARRNELEM(key));
116 EUB : else
117 : {
118 UIC 0 : int siglen = GETSIGLEN(key);
119 0 : int cnttrue = (ISALLTRUE(key)) ? SIGLENBIT(siglen) : sizebitvec(GETSIGN(key), siglen);
120 EUB :
121 UBC 0 : sprintf(outbuf, SINGOUTSTR, cnttrue, (int) SIGLENBIT(siglen) - cnttrue);
122 : }
123 EUB :
124 UIC 0 : PG_FREE_IF_COPY(key, 0);
125 0 : PG_RETURN_POINTER(outbuf);
126 EUB : }
127 :
128 : static int
129 GIC 1813068 : compareint(const void *va, const void *vb)
130 : {
131 CBC 1813068 : int32 a = *((const int32 *) va);
132 GIC 1813068 : int32 b = *((const int32 *) vb);
133 ECB :
134 CBC 1813068 : if (a == b)
135 UIC 0 : return 0;
136 CBC 1813068 : return (a > b) ? 1 : -1;
137 EUB : }
138 ECB :
139 : static void
140 GIC 37682 : makesign(BITVECP sign, SignTSVector *a, int siglen)
141 : {
142 ECB : int32 k,
143 GIC 37682 : len = ARRNELEM(a);
144 37682 : int32 *ptr = GETARR(a);
145 ECB :
146 GNC 37682 : MemSet(sign, 0, siglen);
147 GIC 2102583 : for (k = 0; k < len; k++)
148 CBC 2064901 : HASH(sign, ptr[k], siglen);
149 37682 : }
150 ECB :
151 : static SignTSVector *
152 GIC 9737 : gtsvector_alloc(int flag, int len, BITVECP sign)
153 : {
154 CBC 9737 : int size = CALCGTSIZE(flag, len);
155 GIC 9737 : SignTSVector *res = palloc(size);
156 ECB :
157 CBC 9737 : SET_VARSIZE(res, size);
158 GIC 9737 : res->flag = flag;
159 ECB :
160 CBC 9737 : if ((flag & (SIGNKEY | ALLISTRUE)) == SIGNKEY && sign)
161 GIC 410 : memcpy(GETSIGN(res), sign, len);
162 ECB :
163 CBC 9737 : return res;
164 : }
165 ECB :
166 :
167 : Datum
168 GIC 7839 : gtsvector_compress(PG_FUNCTION_ARGS)
169 : {
170 CBC 7839 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
171 GIC 7839 : int siglen = GET_SIGLEN();
172 CBC 7839 : GISTENTRY *retval = entry;
173 ECB :
174 CBC 7839 : if (entry->leafkey)
175 : { /* tsvector */
176 4572 : TSVector val = DatumGetTSVector(entry->key);
177 GIC 4572 : SignTSVector *res = gtsvector_alloc(ARRKEY, val->size, NULL);
178 ECB : int32 len;
179 : int32 *arr;
180 GIC 4572 : WordEntry *ptr = ARRPTR(val);
181 4572 : char *words = STRPTR(val);
182 ECB :
183 CBC 4572 : arr = GETARR(res);
184 GIC 4572 : len = val->size;
185 CBC 263772 : while (len--)
186 ECB : {
187 : pg_crc32 c;
188 :
189 GIC 259200 : INIT_LEGACY_CRC32(c);
190 777600 : COMP_LEGACY_CRC32(c, words + ptr->pos, ptr->len);
191 CBC 259200 : FIN_LEGACY_CRC32(c);
192 ECB :
193 CBC 259200 : *arr = *(int32 *) &c;
194 GIC 259200 : arr++;
195 CBC 259200 : ptr++;
196 ECB : }
197 :
198 GIC 4572 : qsort(GETARR(res), val->size, sizeof(int), compareint);
199 4572 : len = qunique(GETARR(res), val->size, sizeof(int), compareint);
200 CBC 4572 : if (len != val->size)
201 ECB : {
202 : /*
203 : * there is a collision of hash-function; len is always less than
204 : * val->size
205 : */
206 UIC 0 : len = CALCGTSIZE(ARRKEY, len);
207 UNC 0 : res = (SignTSVector *) repalloc(res, len);
208 UBC 0 : SET_VARSIZE(res, len);
209 EUB : }
210 :
211 : /* make signature, if array is too long */
212 GIC 4572 : if (VARSIZE(res) > TOAST_INDEX_TARGET)
213 : {
214 LBC 0 : SignTSVector *ressign = gtsvector_alloc(SIGNKEY, siglen, NULL);
215 :
216 UBC 0 : makesign(GETSIGN(ressign), res, siglen);
217 UIC 0 : res = ressign;
218 EUB : }
219 :
220 GIC 4572 : retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
221 4572 : gistentryinit(*retval, PointerGetDatum(res),
222 ECB : entry->rel, entry->page,
223 : entry->offset, false);
224 : }
225 GIC 3267 : else if (ISSIGNKEY(DatumGetPointer(entry->key)) &&
226 3267 : !ISALLTRUE(DatumGetPointer(entry->key)))
227 ECB : {
228 : int32 i;
229 : SignTSVector *res;
230 GIC 3267 : BITVECP sign = GETSIGN(DatumGetPointer(entry->key));
231 :
232 CBC 3455 : LOOPBYTE(siglen)
233 : {
234 3267 : if ((sign[i] & 0xff) != 0xff)
235 GIC 3079 : PG_RETURN_POINTER(retval);
236 ECB : }
237 :
238 GIC 188 : res = gtsvector_alloc(SIGNKEY | ALLISTRUE, siglen, sign);
239 188 : retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
240 CBC 188 : gistentryinit(*retval, PointerGetDatum(res),
241 ECB : entry->rel, entry->page,
242 : entry->offset, false);
243 : }
244 GIC 4760 : PG_RETURN_POINTER(retval);
245 : }
246 ECB :
247 : Datum
248 GIC 203283 : gtsvector_decompress(PG_FUNCTION_ARGS)
249 : {
250 ECB : /*
251 : * We need to detoast the stored value, because the other gtsvector
252 : * support functions don't cope with toasted values.
253 : */
254 GIC 203283 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
255 203283 : SignTSVector *key = (SignTSVector *) PG_DETOAST_DATUM(entry->key);
256 ECB :
257 CBC 203283 : if (key != (SignTSVector *) DatumGetPointer(entry->key))
258 : {
259 LBC 0 : GISTENTRY *retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
260 :
261 UBC 0 : gistentryinit(*retval, PointerGetDatum(key),
262 : entry->rel, entry->page,
263 EUB : entry->offset, false);
264 :
265 UIC 0 : PG_RETURN_POINTER(retval);
266 : }
267 EUB :
268 GIC 203283 : PG_RETURN_POINTER(entry);
269 : }
270 ECB :
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 GIC 209435 : checkcondition_arr(void *checkval, QueryOperand *val, ExecPhraseData *data)
282 : {
283 CBC 209435 : int32 *StopLow = ((CHKVAL *) checkval)->arrb;
284 GIC 209435 : int32 *StopHigh = ((CHKVAL *) checkval)->arre;
285 ECB : 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 GIC 209435 : if (val->prefix)
293 12192 : return TS_MAYBE;
294 ECB :
295 CBC 1268542 : while (StopLow < StopHigh)
296 : {
297 1095576 : StopMiddle = StopLow + (StopHigh - StopLow) / 2;
298 GIC 1095576 : if (*StopMiddle == val->valcrc)
299 CBC 24277 : return TS_MAYBE;
300 1071299 : else if (*StopMiddle < val->valcrc)
301 455483 : StopLow = StopMiddle + 1;
302 ECB : else
303 CBC 615816 : StopHigh = StopMiddle;
304 : }
305 ECB :
306 GIC 172966 : return TS_NO;
307 : }
308 ECB :
309 : /*
310 : * TS_execute callback for matching a tsquery operand to GIST non-leaf data
311 : */
312 : static TSTernaryValue
313 GIC 7978 : checkcondition_bit(void *checkval, QueryOperand *val, ExecPhraseData *data)
314 : {
315 CBC 7978 : void *key = (SignTSVector *) checkval;
316 :
317 ECB : /*
318 : * we are not able to find a prefix in signature tree
319 : */
320 GIC 7978 : if (val->prefix)
321 354 : return TS_MAYBE;
322 ECB :
323 CBC 7624 : if (GETBIT(GETSIGN(key), HASHVAL(val->valcrc, GETSIGLEN(key))))
324 GIC 7266 : return TS_MAYBE;
325 ECB : else
326 CBC 358 : return TS_NO;
327 : }
328 ECB :
329 : Datum
330 GIC 151855 : gtsvector_consistent(PG_FUNCTION_ARGS)
331 : {
332 CBC 151855 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
333 GIC 151855 : TSQuery query = PG_GETARG_TSQUERY(1);
334 ECB :
335 : /* StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); */
336 : /* Oid subtype = PG_GETARG_OID(3); */
337 GIC 151855 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
338 151855 : SignTSVector *key = (SignTSVector *) DatumGetPointer(entry->key);
339 ECB :
340 : /* All cases served by this function are inexact */
341 GIC 151855 : *recheck = true;
342 :
343 CBC 151855 : if (!query->size)
344 UIC 0 : PG_RETURN_BOOL(false);
345 ECB :
346 GBC 151855 : if (ISSIGNKEY(key))
347 : {
348 CBC 6736 : if (ISALLTRUE(key))
349 GIC 2425 : PG_RETURN_BOOL(true);
350 ECB :
351 CBC 4311 : PG_RETURN_BOOL(TS_execute(GETQUERY(query),
352 : key,
353 ECB : TS_EXEC_PHRASE_NO_POS,
354 : checkcondition_bit));
355 : }
356 : else
357 : { /* only leaf pages */
358 : CHKVAL chkval;
359 :
360 GIC 145119 : chkval.arrb = GETARR(key);
361 145119 : chkval.arre = chkval.arrb + ARRNELEM(key);
362 CBC 145119 : PG_RETURN_BOOL(TS_execute(GETQUERY(query),
363 ECB : (void *) &chkval,
364 : TS_EXEC_PHRASE_NO_POS,
365 : checkcondition_arr));
366 : }
367 : }
368 :
369 : static int32
370 GIC 7724 : unionkey(BITVECP sbase, SignTSVector *add, int siglen)
371 : {
372 ECB : int32 i;
373 :
374 GIC 7724 : if (ISSIGNKEY(add))
375 : {
376 CBC 4567 : BITVECP sadd = GETSIGN(add);
377 :
378 4567 : if (ISALLTRUE(add))
379 GIC 1410 : return 1;
380 ECB :
381 CBC 3157 : Assert(GETSIGLEN(add) == siglen);
382 :
383 1023545 : LOOPBYTE(siglen)
384 GIC 1020388 : sbase[i] |= sadd[i];
385 ECB : }
386 : else
387 : {
388 GIC 3157 : int32 *ptr = GETARR(add);
389 :
390 CBC 185391 : for (i = 0; i < ARRNELEM(add); i++)
391 GIC 182234 : HASH(sbase, ptr[i], siglen);
392 ECB : }
393 CBC 6314 : return 0;
394 : }
395 ECB :
396 :
397 : Datum
398 GIC 4567 : gtsvector_union(PG_FUNCTION_ARGS)
399 : {
400 CBC 4567 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
401 GIC 4567 : int *size = (int *) PG_GETARG_POINTER(1);
402 CBC 4567 : int siglen = GET_SIGLEN();
403 4567 : SignTSVector *result = gtsvector_alloc(SIGNKEY, siglen, NULL);
404 4567 : BITVECP base = GETSIGN(result);
405 ECB : int32 i;
406 :
407 GIC 4567 : memset(base, 0, siglen);
408 :
409 CBC 10881 : for (i = 0; i < entryvec->n; i++)
410 : {
411 7724 : if (unionkey(base, GETENTRY(entryvec, i), siglen))
412 : {
413 1410 : result->flag |= ALLISTRUE;
414 GIC 1410 : SET_VARSIZE(result, CALCGTSIZE(result->flag, siglen));
415 CBC 1410 : break;
416 ECB : }
417 : }
418 :
419 GIC 4567 : *size = VARSIZE(result);
420 :
421 CBC 4567 : PG_RETURN_POINTER(result);
422 : }
423 ECB :
424 : Datum
425 GIC 4567 : gtsvector_same(PG_FUNCTION_ARGS)
426 : {
427 CBC 4567 : SignTSVector *a = (SignTSVector *) PG_GETARG_POINTER(0);
428 GIC 4567 : SignTSVector *b = (SignTSVector *) PG_GETARG_POINTER(1);
429 CBC 4567 : bool *result = (bool *) PG_GETARG_POINTER(2);
430 4567 : int siglen = GET_SIGLEN();
431 ECB :
432 CBC 4567 : if (ISSIGNKEY(a))
433 : { /* then b also ISSIGNKEY */
434 4567 : if (ISALLTRUE(a) && ISALLTRUE(b))
435 GIC 1410 : *result = true;
436 CBC 3157 : else if (ISALLTRUE(a))
437 LBC 0 : *result = false;
438 CBC 3157 : else if (ISALLTRUE(b))
439 UBC 0 : *result = false;
440 ECB : else
441 EUB : {
442 : int32 i;
443 GIC 3157 : BITVECP sa = GETSIGN(a),
444 3157 : sb = GETSIGN(b);
445 ECB :
446 CBC 3157 : Assert(GETSIGLEN(a) == siglen && GETSIGLEN(b) == siglen);
447 :
448 3157 : *result = true;
449 GIC 258519 : LOOPBYTE(siglen)
450 ECB : {
451 CBC 258219 : if (sa[i] != sb[i])
452 : {
453 2857 : *result = false;
454 GIC 2857 : break;
455 ECB : }
456 : }
457 : }
458 : }
459 : else
460 : { /* a and b ISARRKEY */
461 UIC 0 : int32 lena = ARRNELEM(a),
462 0 : lenb = ARRNELEM(b);
463 EUB :
464 UBC 0 : if (lena != lenb)
465 UIC 0 : *result = false;
466 EUB : else
467 : {
468 UIC 0 : int32 *ptra = GETARR(a),
469 0 : *ptrb = GETARR(b);
470 EUB : int32 i;
471 :
472 UIC 0 : *result = true;
473 0 : for (i = 0; i < lena; i++)
474 UBC 0 : if (ptra[i] != ptrb[i])
475 EUB : {
476 UBC 0 : *result = false;
477 UIC 0 : break;
478 EUB : }
479 : }
480 : }
481 :
482 GIC 4567 : PG_RETURN_POINTER(result);
483 : }
484 ECB :
485 : static int32
486 GIC 5308 : sizebitvec(BITVECP sign, int siglen)
487 : {
488 CBC 5308 : return pg_popcount(sign, siglen);
489 : }
490 ECB :
491 : static int
492 GIC 141373 : hemdistsign(BITVECP a, BITVECP b, int siglen)
493 : {
494 ECB : int i,
495 : diff,
496 GIC 141373 : dist = 0;
497 :
498 CBC 26506511 : LOOPBYTE(siglen)
499 : {
500 26365138 : diff = (unsigned char) (a[i] ^ b[i]);
501 : /* Using the popcount functions here isn't likely to win */
502 26365138 : dist += pg_number_of_ones[diff];
503 : }
504 141373 : return dist;
505 : }
506 ECB :
507 : static int
508 UIC 0 : hemdist(SignTSVector *a, SignTSVector *b)
509 : {
510 UBC 0 : int siglena = GETSIGLEN(a);
511 UIC 0 : int siglenb = GETSIGLEN(b);
512 EUB :
513 UBC 0 : if (ISALLTRUE(a))
514 : {
515 0 : if (ISALLTRUE(b))
516 UIC 0 : return 0;
517 EUB : else
518 UBC 0 : return SIGLENBIT(siglenb) - sizebitvec(GETSIGN(b), siglenb);
519 : }
520 0 : else if (ISALLTRUE(b))
521 UIC 0 : return SIGLENBIT(siglena) - sizebitvec(GETSIGN(a), siglena);
522 EUB :
523 UBC 0 : Assert(siglena == siglenb);
524 :
525 0 : return hemdistsign(GETSIGN(a), GETSIGN(b), siglena);
526 : }
527 EUB :
528 : Datum
529 GIC 31366 : gtsvector_penalty(PG_FUNCTION_ARGS)
530 : {
531 CBC 31366 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
532 GIC 31366 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
533 CBC 31366 : float *penalty = (float *) PG_GETARG_POINTER(2);
534 31366 : int siglen = GET_SIGLEN();
535 31366 : SignTSVector *origval = (SignTSVector *) DatumGetPointer(origentry->key);
536 31366 : SignTSVector *newval = (SignTSVector *) DatumGetPointer(newentry->key);
537 31366 : BITVECP orig = GETSIGN(origval);
538 ECB :
539 CBC 31366 : *penalty = 0.0;
540 :
541 31366 : if (ISARRKEY(newval))
542 : {
543 31366 : BITVECP sign = palloc(siglen);
544 :
545 31366 : makesign(sign, newval, siglen);
546 :
547 31366 : if (ISALLTRUE(origval))
548 : {
549 5308 : int siglenbit = SIGLENBIT(siglen);
550 :
551 5308 : *penalty =
552 GIC 5308 : (float) (siglenbit - sizebitvec(sign, siglen)) /
553 CBC 5308 : (float) (siglenbit + 1);
554 ECB : }
555 : else
556 GIC 26058 : *penalty = hemdistsign(sign, orig, siglen);
557 :
558 CBC 31366 : pfree(sign);
559 : }
560 ECB : else
561 UIC 0 : *penalty = hemdist(origval, newval);
562 GIC 31366 : PG_RETURN_POINTER(penalty);
563 EUB : }
564 ECB :
565 : typedef struct
566 : {
567 : bool allistrue;
568 : BITVECP sign;
569 : } CACHESIGN;
570 :
571 : static void
572 GIC 6361 : fillcache(CACHESIGN *item, SignTSVector *key, int siglen)
573 : {
574 CBC 6361 : item->allistrue = false;
575 GIC 6361 : if (ISARRKEY(key))
576 CBC 6316 : makesign(item->sign, key, siglen);
577 45 : else if (ISALLTRUE(key))
578 LBC 0 : item->allistrue = true;
579 ECB : else
580 GNC 45 : memcpy(item->sign, GETSIGN(key), siglen);
581 GIC 6361 : }
582 ECB :
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 GIC 15733 : comparecost(const void *va, const void *vb)
592 : {
593 CBC 15733 : const SPLITCOST *a = (const SPLITCOST *) va;
594 GIC 15733 : const SPLITCOST *b = (const SPLITCOST *) vb;
595 ECB :
596 CBC 15733 : if (a->cost == b->cost)
597 GIC 6653 : return 0;
598 ECB : else
599 CBC 9080 : return (a->cost > b->cost) ? 1 : -1;
600 : }
601 ECB :
602 :
603 : static int
604 GIC 103413 : hemdistcache(CACHESIGN *a, CACHESIGN *b, int siglen)
605 : {
606 CBC 103413 : if (a->allistrue)
607 : {
608 LBC 0 : if (b->allistrue)
609 UIC 0 : return 0;
610 EUB : else
611 UBC 0 : return SIGLENBIT(siglen) - sizebitvec(b->sign, siglen);
612 : }
613 GBC 103413 : else if (b->allistrue)
614 UIC 0 : return SIGLENBIT(siglen) - sizebitvec(a->sign, siglen);
615 ECB :
616 GBC 103413 : return hemdistsign(a->sign, b->sign, siglen);
617 : }
618 ECB :
619 : Datum
620 GIC 205 : gtsvector_picksplit(PG_FUNCTION_ARGS)
621 : {
622 CBC 205 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
623 GIC 205 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
624 CBC 205 : int siglen = GET_SIGLEN();
625 ECB : 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 GIC 205 : waste = -1;
635 : int32 nbytes;
636 CBC 205 : OffsetNumber seed_1 = 0,
637 GIC 205 : seed_2 = 0;
638 ECB : 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 GIC 205 : maxoff = entryvec->n - 2;
648 205 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
649 CBC 205 : v->spl_left = (OffsetNumber *) palloc(nbytes);
650 205 : v->spl_right = (OffsetNumber *) palloc(nbytes);
651 ECB :
652 CBC 205 : cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (maxoff + 2));
653 GIC 205 : cache_sign = palloc(siglen * (maxoff + 2));
654 ECB :
655 CBC 6771 : for (j = 0; j < maxoff + 2; j++)
656 GIC 6566 : cache[j].sign = &cache_sign[siglen * j];
657 ECB :
658 CBC 205 : fillcache(&cache[FirstOffsetNumber], GETENTRY(entryvec, FirstOffsetNumber),
659 : siglen);
660 ECB :
661 GIC 6156 : for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
662 : {
663 CBC 96642 : for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
664 : {
665 90691 : if (k == FirstOffsetNumber)
666 GIC 5951 : fillcache(&cache[j], GETENTRY(entryvec, j), siglen);
667 ECB :
668 CBC 90691 : size_waste = hemdistcache(&(cache[j]), &(cache[k]), siglen);
669 GIC 90691 : if (size_waste > waste)
670 ECB : {
671 CBC 1275 : waste = size_waste;
672 GIC 1275 : seed_1 = k;
673 CBC 1275 : seed_2 = j;
674 ECB : }
675 : }
676 : }
677 :
678 GIC 205 : left = v->spl_left;
679 205 : v->spl_nleft = 0;
680 CBC 205 : right = v->spl_right;
681 205 : v->spl_nright = 0;
682 ECB :
683 CBC 205 : if (seed_1 == 0 || seed_2 == 0)
684 : {
685 LBC 0 : seed_1 = 1;
686 UIC 0 : seed_2 = 2;
687 EUB : }
688 :
689 : /* form initial .. */
690 GIC 205 : datum_l = gtsvector_alloc(SIGNKEY | (cache[seed_1].allistrue ? ALLISTRUE : 0),
691 205 : siglen, cache[seed_1].sign);
692 CBC 205 : datum_r = gtsvector_alloc(SIGNKEY | (cache[seed_2].allistrue ? ALLISTRUE : 0),
693 205 : siglen, cache[seed_2].sign);
694 205 : union_l = GETSIGN(datum_l);
695 205 : union_r = GETSIGN(datum_r);
696 205 : maxoff = OffsetNumberNext(maxoff);
697 205 : fillcache(&cache[maxoff], GETENTRY(entryvec, maxoff), siglen);
698 ECB : /* sort before ... */
699 CBC 205 : costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
700 GIC 6566 : for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
701 ECB : {
702 CBC 6361 : costvector[j - 1].pos = j;
703 GIC 6361 : size_alpha = hemdistcache(&(cache[seed_1]), &(cache[j]), siglen);
704 CBC 6361 : size_beta = hemdistcache(&(cache[seed_2]), &(cache[j]), siglen);
705 GNC 6361 : costvector[j - 1].cost = abs(size_alpha - size_beta);
706 ECB : }
707 GNC 205 : qsort(costvector, maxoff, sizeof(SPLITCOST), comparecost);
708 :
709 CBC 6566 : for (k = 0; k < maxoff; k++)
710 : {
711 6361 : j = costvector[k].pos;
712 GIC 6361 : if (j == seed_1)
713 ECB : {
714 CBC 205 : *left++ = j;
715 GIC 205 : v->spl_nleft++;
716 CBC 205 : continue;
717 ECB : }
718 CBC 6156 : else if (j == seed_2)
719 : {
720 205 : *right++ = j;
721 GIC 205 : v->spl_nright++;
722 CBC 205 : continue;
723 ECB : }
724 :
725 GIC 5951 : if (ISALLTRUE(datum_l) || cache[j].allistrue)
726 : {
727 LBC 0 : if (ISALLTRUE(datum_l) && cache[j].allistrue)
728 UIC 0 : size_alpha = 0;
729 EUB : else
730 UBC 0 : size_alpha = SIGLENBIT(siglen) -
731 UIC 0 : sizebitvec((cache[j].allistrue) ?
732 EUB : GETSIGN(datum_l) :
733 UBC 0 : GETSIGN(cache[j].sign),
734 : siglen);
735 EUB : }
736 : else
737 GIC 5951 : size_alpha = hemdistsign(cache[j].sign, GETSIGN(datum_l), siglen);
738 :
739 CBC 5951 : if (ISALLTRUE(datum_r) || cache[j].allistrue)
740 : {
741 LBC 0 : if (ISALLTRUE(datum_r) && cache[j].allistrue)
742 UIC 0 : size_beta = 0;
743 EUB : else
744 UBC 0 : size_beta = SIGLENBIT(siglen) -
745 UIC 0 : sizebitvec((cache[j].allistrue) ?
746 EUB : GETSIGN(datum_r) :
747 UBC 0 : GETSIGN(cache[j].sign),
748 : siglen);
749 EUB : }
750 : else
751 GIC 5951 : size_beta = hemdistsign(cache[j].sign, GETSIGN(datum_r), siglen);
752 :
753 CBC 5951 : if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.1))
754 : {
755 2930 : if (ISALLTRUE(datum_l) || cache[j].allistrue)
756 : {
757 LBC 0 : if (!ISALLTRUE(datum_l))
758 UNC 0 : memset(GETSIGN(datum_l), 0xff, siglen);
759 EUB : }
760 : else
761 : {
762 GIC 2930 : ptr = cache[j].sign;
763 485452 : LOOPBYTE(siglen)
764 CBC 482522 : union_l[i] |= ptr[i];
765 ECB : }
766 CBC 2930 : *left++ = j;
767 GIC 2930 : v->spl_nleft++;
768 ECB : }
769 : else
770 : {
771 GIC 3021 : if (ISALLTRUE(datum_r) || cache[j].allistrue)
772 : {
773 LBC 0 : if (!ISALLTRUE(datum_r))
774 UNC 0 : memset(GETSIGN(datum_r), 0xff, siglen);
775 EUB : }
776 : else
777 : {
778 GIC 3021 : ptr = cache[j].sign;
779 499335 : LOOPBYTE(siglen)
780 CBC 496314 : union_r[i] |= ptr[i];
781 ECB : }
782 CBC 3021 : *right++ = j;
783 GIC 3021 : v->spl_nright++;
784 ECB : }
785 : }
786 :
787 GIC 205 : *right = *left = FirstOffsetNumber;
788 205 : v->spl_ldatum = PointerGetDatum(datum_l);
789 CBC 205 : v->spl_rdatum = PointerGetDatum(datum_r);
790 ECB :
791 CBC 205 : PG_RETURN_POINTER(v);
792 : }
793 ECB :
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 UIC 0 : gtsvector_consistent_oldsig(PG_FUNCTION_ARGS)
803 : {
804 UBC 0 : return gtsvector_consistent(fcinfo);
805 : }
806 EUB :
807 : Datum
808 GIC 179 : gtsvector_options(PG_FUNCTION_ARGS)
809 : {
810 CBC 179 : local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
811 :
812 179 : init_local_reloptions(relopts, sizeof(GistTsVectorOptions));
813 GIC 179 : add_local_int_reloption(relopts, "siglen", "signature length",
814 ECB : SIGLEN_DEFAULT, 1, SIGLEN_MAX,
815 : offsetof(GistTsVectorOptions, siglen));
816 :
817 GIC 179 : PG_RETURN_VOID();
818 : }
|
