Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * tsgistidx.c
4 : * GiST support functions for tsvector_ops
5 : *
6 : * Portions Copyright (c) 1996-2017, 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/tuptoaster.h"
19 : #include "tsearch/ts_utils.h"
20 : #include "utils/builtins.h"
21 : #include "utils/pg_crc.h"
22 :
23 :
24 : #define SIGLENINT 31 /* >121 => key will toast, so it will not work
25 : * !!! */
26 :
27 : #define SIGLEN ( sizeof(int32) * SIGLENINT )
28 : #define SIGLENBIT (SIGLEN * BITS_PER_BYTE)
29 :
30 : typedef char BITVEC[SIGLEN];
31 : typedef char *BITVECP;
32 :
33 : #define LOOPBYTE \
34 : for(i=0;i<SIGLEN;i++)
35 :
36 : #define GETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITS_PER_BYTE ) ) )
37 : #define GETBITBYTE(x,i) ( ((char)(x)) >> (i) & 0x01 )
38 : #define CLRBIT(x,i) GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITS_PER_BYTE ) )
39 : #define SETBIT(x,i) GETBYTE(x,i) |= ( 0x01 << ( (i) % BITS_PER_BYTE ) )
40 : #define GETBIT(x,i) ( (GETBYTE(x,i) >> ( (i) % BITS_PER_BYTE )) & 0x01 )
41 :
42 : #define HASHVAL(val) (((unsigned int)(val)) % SIGLENBIT)
43 : #define HASH(sign, val) SETBIT((sign), HASHVAL(val))
44 :
45 : #define GETENTRY(vec,pos) ((SignTSVector *) DatumGetPointer((vec)->vector[(pos)].key))
46 :
47 : /*
48 : * type of GiST index key
49 : */
50 :
51 : typedef struct
52 : {
53 : int32 vl_len_; /* varlena header (do not touch directly!) */
54 : int32 flag;
55 : char data[FLEXIBLE_ARRAY_MEMBER];
56 : } SignTSVector;
57 :
58 : #define ARRKEY 0x01
59 : #define SIGNKEY 0x02
60 : #define ALLISTRUE 0x04
61 :
62 : #define ISARRKEY(x) ( ((SignTSVector*)(x))->flag & ARRKEY )
63 : #define ISSIGNKEY(x) ( ((SignTSVector*)(x))->flag & SIGNKEY )
64 : #define ISALLTRUE(x) ( ((SignTSVector*)(x))->flag & ALLISTRUE )
65 :
66 : #define GTHDRSIZE ( VARHDRSZ + sizeof(int32) )
67 : #define CALCGTSIZE(flag, len) ( GTHDRSIZE + ( ( (flag) & ARRKEY ) ? ((len)*sizeof(int32)) : (((flag) & ALLISTRUE) ? 0 : SIGLEN) ) )
68 :
69 : #define GETSIGN(x) ( (BITVECP)( (char*)(x)+GTHDRSIZE ) )
70 : #define GETARR(x) ( (int32*)( (char*)(x)+GTHDRSIZE ) )
71 : #define ARRNELEM(x) ( ( VARSIZE(x) - GTHDRSIZE )/sizeof(int32) )
72 :
73 : /* Number of one-bits in an unsigned byte */
74 : static const uint8 number_of_ones[256] = {
75 : 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
76 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
77 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
78 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
79 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
80 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
81 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
82 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
83 : 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
84 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
85 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
86 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
87 : 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
88 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
89 : 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
90 : 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
91 : };
92 :
93 : static int32 sizebitvec(BITVECP sign);
94 :
95 : Datum
96 0 : gtsvectorin(PG_FUNCTION_ARGS)
97 : {
98 0 : ereport(ERROR,
99 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
100 : errmsg("gtsvector_in not implemented")));
101 : PG_RETURN_DATUM(0);
102 : }
103 :
104 : #define SINGOUTSTR "%d true bits, %d false bits"
105 : #define ARROUTSTR "%d unique words"
106 : #define EXTRALEN ( 2*13 )
107 :
108 : static int outbuf_maxlen = 0;
109 :
110 : Datum
111 0 : gtsvectorout(PG_FUNCTION_ARGS)
112 : {
113 0 : SignTSVector *key = (SignTSVector *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_POINTER(0)));
114 : char *outbuf;
115 :
116 0 : if (outbuf_maxlen == 0)
117 0 : outbuf_maxlen = 2 * EXTRALEN + Max(strlen(SINGOUTSTR), strlen(ARROUTSTR)) + 1;
118 0 : outbuf = palloc(outbuf_maxlen);
119 :
120 0 : if (ISARRKEY(key))
121 0 : sprintf(outbuf, ARROUTSTR, (int) ARRNELEM(key));
122 : else
123 : {
124 0 : int cnttrue = (ISALLTRUE(key)) ? SIGLENBIT : sizebitvec(GETSIGN(key));
125 :
126 0 : sprintf(outbuf, SINGOUTSTR, cnttrue, (int) SIGLENBIT - cnttrue);
127 : }
128 :
129 0 : PG_FREE_IF_COPY(key, 0);
130 0 : PG_RETURN_POINTER(outbuf);
131 : }
132 :
133 : static int
134 173382 : compareint(const void *va, const void *vb)
135 : {
136 173382 : int32 a = *((const int32 *) va);
137 173382 : int32 b = *((const int32 *) vb);
138 :
139 173382 : if (a == b)
140 0 : return 0;
141 173382 : return (a > b) ? 1 : -1;
142 : }
143 :
144 : /*
145 : * Removes duplicates from an array of int32. 'l' is
146 : * size of the input array. Returns the new size of the array.
147 : */
148 : static int
149 508 : uniqueint(int32 *a, int32 l)
150 : {
151 : int32 *ptr,
152 : *res;
153 :
154 508 : if (l <= 1)
155 8 : return l;
156 :
157 500 : ptr = res = a;
158 :
159 500 : qsort((void *) a, l, sizeof(int32), compareint);
160 :
161 29817 : while (ptr - a < l)
162 28817 : if (*ptr != *res)
163 28317 : *(++res) = *ptr++;
164 : else
165 500 : ptr++;
166 500 : return res + 1 - a;
167 : }
168 :
169 : static void
170 5297 : makesign(BITVECP sign, SignTSVector *a)
171 : {
172 : int32 k,
173 5297 : len = ARRNELEM(a);
174 5297 : int32 *ptr = GETARR(a);
175 :
176 5297 : MemSet((void *) sign, 0, sizeof(BITVEC));
177 312500 : for (k = 0; k < len; k++)
178 307203 : HASH(sign, ptr[k]);
179 5297 : }
180 :
181 : Datum
182 998 : gtsvector_compress(PG_FUNCTION_ARGS)
183 : {
184 998 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
185 998 : GISTENTRY *retval = entry;
186 :
187 998 : if (entry->leafkey)
188 : { /* tsvector */
189 : SignTSVector *res;
190 508 : TSVector val = DatumGetTSVector(entry->key);
191 : int32 len;
192 : int32 *arr;
193 508 : WordEntry *ptr = ARRPTR(val);
194 508 : char *words = STRPTR(val);
195 :
196 508 : len = CALCGTSIZE(ARRKEY, val->size);
197 508 : res = (SignTSVector *) palloc(len);
198 508 : SET_VARSIZE(res, len);
199 508 : res->flag = ARRKEY;
200 508 : arr = GETARR(res);
201 508 : len = val->size;
202 29833 : while (len--)
203 : {
204 : pg_crc32 c;
205 :
206 28817 : INIT_LEGACY_CRC32(c);
207 28817 : COMP_LEGACY_CRC32(c, words + ptr->pos, ptr->len);
208 28817 : FIN_LEGACY_CRC32(c);
209 :
210 28817 : *arr = *(int32 *) &c;
211 28817 : arr++;
212 28817 : ptr++;
213 : }
214 :
215 508 : len = uniqueint(GETARR(res), val->size);
216 508 : if (len != val->size)
217 : {
218 : /*
219 : * there is a collision of hash-function; len is always less than
220 : * val->size
221 : */
222 0 : len = CALCGTSIZE(ARRKEY, len);
223 0 : res = (SignTSVector *) repalloc((void *) res, len);
224 0 : SET_VARSIZE(res, len);
225 : }
226 :
227 : /* make signature, if array is too long */
228 508 : if (VARSIZE(res) > TOAST_INDEX_TARGET)
229 : {
230 : SignTSVector *ressign;
231 :
232 0 : len = CALCGTSIZE(SIGNKEY, 0);
233 0 : ressign = (SignTSVector *) palloc(len);
234 0 : SET_VARSIZE(ressign, len);
235 0 : ressign->flag = SIGNKEY;
236 0 : makesign(GETSIGN(ressign), res);
237 0 : res = ressign;
238 : }
239 :
240 508 : retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
241 508 : gistentryinit(*retval, PointerGetDatum(res),
242 : entry->rel, entry->page,
243 : entry->offset, FALSE);
244 : }
245 980 : else if (ISSIGNKEY(DatumGetPointer(entry->key)) &&
246 490 : !ISALLTRUE(DatumGetPointer(entry->key)))
247 : {
248 : int32 i,
249 : len;
250 : SignTSVector *res;
251 490 : BITVECP sign = GETSIGN(DatumGetPointer(entry->key));
252 :
253 490 : LOOPBYTE
254 : {
255 490 : if ((sign[i] & 0xff) != 0xff)
256 490 : PG_RETURN_POINTER(retval);
257 : }
258 :
259 0 : len = CALCGTSIZE(SIGNKEY | ALLISTRUE, 0);
260 0 : res = (SignTSVector *) palloc(len);
261 0 : SET_VARSIZE(res, len);
262 0 : res->flag = SIGNKEY | ALLISTRUE;
263 :
264 0 : retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
265 0 : gistentryinit(*retval, PointerGetDatum(res),
266 : entry->rel, entry->page,
267 : entry->offset, FALSE);
268 : }
269 508 : PG_RETURN_POINTER(retval);
270 : }
271 :
272 : Datum
273 16860 : gtsvector_decompress(PG_FUNCTION_ARGS)
274 : {
275 16860 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
276 16860 : SignTSVector *key = (SignTSVector *) DatumGetPointer(PG_DETOAST_DATUM(entry->key));
277 :
278 16860 : if (key != (SignTSVector *) DatumGetPointer(entry->key))
279 : {
280 0 : GISTENTRY *retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
281 :
282 0 : gistentryinit(*retval, PointerGetDatum(key),
283 : entry->rel, entry->page,
284 : entry->offset, FALSE);
285 :
286 0 : PG_RETURN_POINTER(retval);
287 : }
288 :
289 16860 : PG_RETURN_POINTER(entry);
290 : }
291 :
292 : typedef struct
293 : {
294 : int32 *arrb;
295 : int32 *arre;
296 : } CHKVAL;
297 :
298 : /*
299 : * is there value 'val' in array or not ?
300 : */
301 : static bool
302 14330 : checkcondition_arr(void *checkval, QueryOperand *val, ExecPhraseData *data)
303 : {
304 14330 : int32 *StopLow = ((CHKVAL *) checkval)->arrb;
305 14330 : int32 *StopHigh = ((CHKVAL *) checkval)->arre;
306 : int32 *StopMiddle;
307 :
308 : /* Loop invariant: StopLow <= val < StopHigh */
309 :
310 : /*
311 : * we are not able to find a prefix by hash value
312 : */
313 14330 : if (val->prefix)
314 1016 : return true;
315 :
316 99217 : while (StopLow < StopHigh)
317 : {
318 74178 : StopMiddle = StopLow + (StopHigh - StopLow) / 2;
319 74178 : if (*StopMiddle == val->valcrc)
320 1589 : return (true);
321 72589 : else if (*StopMiddle < val->valcrc)
322 27006 : StopLow = StopMiddle + 1;
323 : else
324 45583 : StopHigh = StopMiddle;
325 : }
326 :
327 11725 : return (false);
328 : }
329 :
330 : static bool
331 498 : checkcondition_bit(void *checkval, QueryOperand *val, ExecPhraseData *data)
332 : {
333 : /*
334 : * we are not able to find a prefix in signature tree
335 : */
336 498 : if (val->prefix)
337 38 : return true;
338 460 : return GETBIT(checkval, HASHVAL(val->valcrc));
339 : }
340 :
341 : Datum
342 10156 : gtsvector_consistent(PG_FUNCTION_ARGS)
343 : {
344 10156 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
345 10156 : TSQuery query = PG_GETARG_TSQUERY(1);
346 :
347 : /* StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); */
348 : /* Oid subtype = PG_GETARG_OID(3); */
349 10156 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
350 10156 : SignTSVector *key = (SignTSVector *) DatumGetPointer(entry->key);
351 :
352 : /* All cases served by this function are inexact */
353 10156 : *recheck = true;
354 :
355 10156 : if (!query->size)
356 0 : PG_RETURN_BOOL(false);
357 :
358 10156 : if (ISSIGNKEY(key))
359 : {
360 380 : if (ISALLTRUE(key))
361 0 : PG_RETURN_BOOL(true);
362 :
363 : /* since signature is lossy, cannot specify CALC_NOT here */
364 380 : PG_RETURN_BOOL(TS_execute(GETQUERY(query),
365 : (void *) GETSIGN(key),
366 : TS_EXEC_PHRASE_NO_POS,
367 : checkcondition_bit));
368 : }
369 : else
370 : { /* only leaf pages */
371 : CHKVAL chkval;
372 :
373 9776 : chkval.arrb = GETARR(key);
374 9776 : chkval.arre = chkval.arrb + ARRNELEM(key);
375 9776 : PG_RETURN_BOOL(TS_execute(GETQUERY(query),
376 : (void *) &chkval,
377 : TS_EXEC_PHRASE_NO_POS | TS_EXEC_CALC_NOT,
378 : checkcondition_arr));
379 : }
380 : }
381 :
382 : static int32
383 938 : unionkey(BITVECP sbase, SignTSVector *add)
384 : {
385 : int32 i;
386 :
387 938 : if (ISSIGNKEY(add))
388 : {
389 469 : BITVECP sadd = GETSIGN(add);
390 :
391 469 : if (ISALLTRUE(add))
392 0 : return 1;
393 :
394 58625 : LOOPBYTE
395 58156 : sbase[i] |= sadd[i];
396 : }
397 : else
398 : {
399 469 : int32 *ptr = GETARR(add);
400 :
401 27590 : for (i = 0; i < ARRNELEM(add); i++)
402 27121 : HASH(sbase, ptr[i]);
403 : }
404 938 : return 0;
405 : }
406 :
407 :
408 : Datum
409 469 : gtsvector_union(PG_FUNCTION_ARGS)
410 : {
411 469 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
412 469 : int *size = (int *) PG_GETARG_POINTER(1);
413 : BITVEC base;
414 : int32 i,
415 : len;
416 469 : int32 flag = 0;
417 : SignTSVector *result;
418 :
419 469 : MemSet((void *) base, 0, sizeof(BITVEC));
420 1407 : for (i = 0; i < entryvec->n; i++)
421 : {
422 938 : if (unionkey(base, GETENTRY(entryvec, i)))
423 : {
424 0 : flag = ALLISTRUE;
425 0 : break;
426 : }
427 : }
428 :
429 469 : flag |= SIGNKEY;
430 469 : len = CALCGTSIZE(flag, 0);
431 469 : result = (SignTSVector *) palloc(len);
432 469 : *size = len;
433 469 : SET_VARSIZE(result, len);
434 469 : result->flag = flag;
435 469 : if (!ISALLTRUE(result))
436 469 : memcpy((void *) GETSIGN(result), (void *) base, sizeof(BITVEC));
437 :
438 469 : PG_RETURN_POINTER(result);
439 : }
440 :
441 : Datum
442 469 : gtsvector_same(PG_FUNCTION_ARGS)
443 : {
444 469 : SignTSVector *a = (SignTSVector *) PG_GETARG_POINTER(0);
445 469 : SignTSVector *b = (SignTSVector *) PG_GETARG_POINTER(1);
446 469 : bool *result = (bool *) PG_GETARG_POINTER(2);
447 :
448 469 : if (ISSIGNKEY(a))
449 : { /* then b also ISSIGNKEY */
450 469 : if (ISALLTRUE(a) && ISALLTRUE(b))
451 0 : *result = true;
452 469 : else if (ISALLTRUE(a))
453 0 : *result = false;
454 469 : else if (ISALLTRUE(b))
455 0 : *result = false;
456 : else
457 : {
458 : int32 i;
459 469 : BITVECP sa = GETSIGN(a),
460 469 : sb = GETSIGN(b);
461 :
462 469 : *result = true;
463 10372 : LOOPBYTE
464 : {
465 10357 : if (sa[i] != sb[i])
466 : {
467 454 : *result = false;
468 454 : break;
469 : }
470 : }
471 : }
472 : }
473 : else
474 : { /* a and b ISARRKEY */
475 0 : int32 lena = ARRNELEM(a),
476 0 : lenb = ARRNELEM(b);
477 :
478 0 : if (lena != lenb)
479 0 : *result = false;
480 : else
481 : {
482 0 : int32 *ptra = GETARR(a),
483 0 : *ptrb = GETARR(b);
484 : int32 i;
485 :
486 0 : *result = true;
487 0 : for (i = 0; i < lena; i++)
488 0 : if (ptra[i] != ptrb[i])
489 : {
490 0 : *result = false;
491 0 : break;
492 : }
493 : }
494 : }
495 :
496 469 : PG_RETURN_POINTER(result);
497 : }
498 :
499 : static int32
500 0 : sizebitvec(BITVECP sign)
501 : {
502 0 : int32 size = 0,
503 : i;
504 :
505 0 : LOOPBYTE
506 0 : size += number_of_ones[(unsigned char) sign[i]];
507 0 : return size;
508 : }
509 :
510 : static int
511 14779 : hemdistsign(BITVECP a, BITVECP b)
512 : {
513 : int i,
514 : diff,
515 14779 : dist = 0;
516 :
517 1847375 : LOOPBYTE
518 : {
519 1832596 : diff = (unsigned char) (a[i] ^ b[i]);
520 1832596 : dist += number_of_ones[diff];
521 : }
522 14779 : return dist;
523 : }
524 :
525 : static int
526 0 : hemdist(SignTSVector *a, SignTSVector *b)
527 : {
528 0 : if (ISALLTRUE(a))
529 : {
530 0 : if (ISALLTRUE(b))
531 0 : return 0;
532 : else
533 0 : return SIGLENBIT - sizebitvec(GETSIGN(b));
534 : }
535 0 : else if (ISALLTRUE(b))
536 0 : return SIGLENBIT - sizebitvec(GETSIGN(a));
537 :
538 0 : return hemdistsign(GETSIGN(a), GETSIGN(b));
539 : }
540 :
541 : Datum
542 4740 : gtsvector_penalty(PG_FUNCTION_ARGS)
543 : {
544 4740 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
545 4740 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
546 4740 : float *penalty = (float *) PG_GETARG_POINTER(2);
547 4740 : SignTSVector *origval = (SignTSVector *) DatumGetPointer(origentry->key);
548 4740 : SignTSVector *newval = (SignTSVector *) DatumGetPointer(newentry->key);
549 4740 : BITVECP orig = GETSIGN(origval);
550 :
551 4740 : *penalty = 0.0;
552 :
553 4740 : if (ISARRKEY(newval))
554 : {
555 : BITVEC sign;
556 :
557 4740 : makesign(sign, newval);
558 :
559 4740 : if (ISALLTRUE(origval))
560 0 : *penalty = ((float) (SIGLENBIT - sizebitvec(sign))) / (float) (SIGLENBIT + 1);
561 : else
562 4740 : *penalty = hemdistsign(sign, orig);
563 : }
564 : else
565 0 : *penalty = hemdist(origval, newval);
566 4740 : PG_RETURN_POINTER(penalty);
567 : }
568 :
569 : typedef struct
570 : {
571 : bool allistrue;
572 : BITVEC sign;
573 : } CACHESIGN;
574 :
575 : static void
576 557 : fillcache(CACHESIGN *item, SignTSVector *key)
577 : {
578 557 : item->allistrue = false;
579 557 : if (ISARRKEY(key))
580 557 : makesign(item->sign, key);
581 0 : else if (ISALLTRUE(key))
582 0 : item->allistrue = true;
583 : else
584 0 : memcpy((void *) item->sign, (void *) GETSIGN(key), sizeof(BITVEC));
585 557 : }
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
595 1757 : comparecost(const void *va, const void *vb)
596 : {
597 1757 : const SPLITCOST *a = (const SPLITCOST *) va;
598 1757 : const SPLITCOST *b = (const SPLITCOST *) vb;
599 :
600 1757 : if (a->cost == b->cost)
601 457 : return 0;
602 : else
603 1300 : return (a->cost > b->cost) ? 1 : -1;
604 : }
605 :
606 :
607 : static int
608 8997 : hemdistcache(CACHESIGN *a, CACHESIGN *b)
609 : {
610 8997 : if (a->allistrue)
611 : {
612 0 : if (b->allistrue)
613 0 : return 0;
614 : else
615 0 : return SIGLENBIT - sizebitvec(b->sign);
616 : }
617 8997 : else if (b->allistrue)
618 0 : return SIGLENBIT - sizebitvec(a->sign);
619 :
620 8997 : return hemdistsign(a->sign, b->sign);
621 : }
622 :
623 : Datum
624 18 : gtsvector_picksplit(PG_FUNCTION_ARGS)
625 : {
626 18 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
627 18 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
628 : OffsetNumber k,
629 : j;
630 : SignTSVector *datum_l,
631 : *datum_r;
632 : BITVECP union_l,
633 : union_r;
634 : int32 size_alpha,
635 : size_beta;
636 : int32 size_waste,
637 18 : waste = -1;
638 : int32 nbytes;
639 18 : OffsetNumber seed_1 = 0,
640 18 : seed_2 = 0;
641 : OffsetNumber *left,
642 : *right;
643 : OffsetNumber maxoff;
644 : BITVECP ptr;
645 : int i;
646 : CACHESIGN *cache;
647 : SPLITCOST *costvector;
648 :
649 18 : maxoff = entryvec->n - 2;
650 18 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
651 18 : v->spl_left = (OffsetNumber *) palloc(nbytes);
652 18 : v->spl_right = (OffsetNumber *) palloc(nbytes);
653 :
654 18 : cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (maxoff + 2));
655 18 : fillcache(&cache[FirstOffsetNumber], GETENTRY(entryvec, FirstOffsetNumber));
656 :
657 539 : for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
658 : {
659 8404 : for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
660 : {
661 7883 : if (k == FirstOffsetNumber)
662 521 : fillcache(&cache[j], GETENTRY(entryvec, j));
663 :
664 7883 : size_waste = hemdistcache(&(cache[j]), &(cache[k]));
665 7883 : if (size_waste > waste)
666 : {
667 165 : waste = size_waste;
668 165 : seed_1 = k;
669 165 : seed_2 = j;
670 : }
671 : }
672 : }
673 :
674 18 : left = v->spl_left;
675 18 : v->spl_nleft = 0;
676 18 : right = v->spl_right;
677 18 : v->spl_nright = 0;
678 :
679 18 : if (seed_1 == 0 || seed_2 == 0)
680 : {
681 0 : seed_1 = 1;
682 0 : seed_2 = 2;
683 : }
684 :
685 : /* form initial .. */
686 18 : if (cache[seed_1].allistrue)
687 : {
688 0 : datum_l = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
689 0 : SET_VARSIZE(datum_l, CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
690 0 : datum_l->flag = SIGNKEY | ALLISTRUE;
691 : }
692 : else
693 : {
694 18 : datum_l = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY, 0));
695 18 : SET_VARSIZE(datum_l, CALCGTSIZE(SIGNKEY, 0));
696 18 : datum_l->flag = SIGNKEY;
697 18 : memcpy((void *) GETSIGN(datum_l), (void *) cache[seed_1].sign, sizeof(BITVEC));
698 : }
699 18 : if (cache[seed_2].allistrue)
700 : {
701 0 : datum_r = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
702 0 : SET_VARSIZE(datum_r, CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
703 0 : datum_r->flag = SIGNKEY | ALLISTRUE;
704 : }
705 : else
706 : {
707 18 : datum_r = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY, 0));
708 18 : SET_VARSIZE(datum_r, CALCGTSIZE(SIGNKEY, 0));
709 18 : datum_r->flag = SIGNKEY;
710 18 : memcpy((void *) GETSIGN(datum_r), (void *) cache[seed_2].sign, sizeof(BITVEC));
711 : }
712 :
713 18 : union_l = GETSIGN(datum_l);
714 18 : union_r = GETSIGN(datum_r);
715 18 : maxoff = OffsetNumberNext(maxoff);
716 18 : fillcache(&cache[maxoff], GETENTRY(entryvec, maxoff));
717 : /* sort before ... */
718 18 : costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
719 575 : for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
720 : {
721 557 : costvector[j - 1].pos = j;
722 557 : size_alpha = hemdistcache(&(cache[seed_1]), &(cache[j]));
723 557 : size_beta = hemdistcache(&(cache[seed_2]), &(cache[j]));
724 557 : costvector[j - 1].cost = Abs(size_alpha - size_beta);
725 : }
726 18 : qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
727 :
728 575 : for (k = 0; k < maxoff; k++)
729 : {
730 557 : j = costvector[k].pos;
731 557 : if (j == seed_1)
732 : {
733 18 : *left++ = j;
734 18 : v->spl_nleft++;
735 18 : continue;
736 : }
737 539 : else if (j == seed_2)
738 : {
739 18 : *right++ = j;
740 18 : v->spl_nright++;
741 18 : continue;
742 : }
743 :
744 521 : if (ISALLTRUE(datum_l) || cache[j].allistrue)
745 : {
746 0 : if (ISALLTRUE(datum_l) && cache[j].allistrue)
747 0 : size_alpha = 0;
748 : else
749 0 : size_alpha = SIGLENBIT - sizebitvec(
750 0 : (cache[j].allistrue) ? GETSIGN(datum_l) : GETSIGN(cache[j].sign)
751 : );
752 : }
753 : else
754 521 : size_alpha = hemdistsign(cache[j].sign, GETSIGN(datum_l));
755 :
756 521 : if (ISALLTRUE(datum_r) || cache[j].allistrue)
757 : {
758 0 : if (ISALLTRUE(datum_r) && cache[j].allistrue)
759 0 : size_beta = 0;
760 : else
761 0 : size_beta = SIGLENBIT - sizebitvec(
762 0 : (cache[j].allistrue) ? GETSIGN(datum_r) : GETSIGN(cache[j].sign)
763 : );
764 : }
765 : else
766 521 : size_beta = hemdistsign(cache[j].sign, GETSIGN(datum_r));
767 :
768 521 : if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.1))
769 : {
770 257 : if (ISALLTRUE(datum_l) || cache[j].allistrue)
771 : {
772 0 : if (!ISALLTRUE(datum_l))
773 0 : MemSet((void *) GETSIGN(datum_l), 0xff, sizeof(BITVEC));
774 : }
775 : else
776 : {
777 257 : ptr = cache[j].sign;
778 32125 : LOOPBYTE
779 31868 : union_l[i] |= ptr[i];
780 : }
781 257 : *left++ = j;
782 257 : v->spl_nleft++;
783 : }
784 : else
785 : {
786 264 : if (ISALLTRUE(datum_r) || cache[j].allistrue)
787 : {
788 0 : if (!ISALLTRUE(datum_r))
789 0 : MemSet((void *) GETSIGN(datum_r), 0xff, sizeof(BITVEC));
790 : }
791 : else
792 : {
793 264 : ptr = cache[j].sign;
794 33000 : LOOPBYTE
795 32736 : union_r[i] |= ptr[i];
796 : }
797 264 : *right++ = j;
798 264 : v->spl_nright++;
799 : }
800 : }
801 :
802 18 : *right = *left = FirstOffsetNumber;
803 18 : v->spl_ldatum = PointerGetDatum(datum_l);
804 18 : v->spl_rdatum = PointerGetDatum(datum_r);
805 :
806 18 : PG_RETURN_POINTER(v);
807 : }
808 :
809 : /*
810 : * Formerly, gtsvector_consistent was declared in pg_proc.h with arguments
811 : * that did not match the documented conventions for GiST support functions.
812 : * We fixed that, but we still need a pg_proc entry with the old signature
813 : * to support reloading pre-9.6 contrib/tsearch2 opclass declarations.
814 : * This compatibility function should go away eventually.
815 : */
816 : Datum
817 0 : gtsvector_consistent_oldsig(PG_FUNCTION_ARGS)
818 : {
819 0 : return gtsvector_consistent(fcinfo);
820 : }
|
