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