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