Line data Source code
1 : /*
2 : * contrib/pg_trgm/trgm_gist.c
3 : */
4 : #include "postgres.h"
5 :
6 : #include "access/reloptions.h"
7 : #include "access/stratnum.h"
8 : #include "fmgr.h"
9 : #include "port/pg_bitutils.h"
10 : #include "trgm.h"
11 : #include "varatt.h"
12 :
13 : /* gist_trgm_ops opclass options */
14 : typedef struct
15 : {
16 : int32 vl_len_; /* varlena header (do not touch directly!) */
17 : int siglen; /* signature length in bytes */
18 : } TrgmGistOptions;
19 :
20 : #define GET_SIGLEN() (PG_HAS_OPCLASS_OPTIONS() ? \
21 : ((TrgmGistOptions *) PG_GET_OPCLASS_OPTIONS())->siglen : \
22 : SIGLEN_DEFAULT)
23 :
24 : typedef struct
25 : {
26 : /* most recent inputs to gtrgm_consistent */
27 : StrategyNumber strategy;
28 : text *query;
29 : /* extracted trigrams for query */
30 : TRGM *trigrams;
31 : /* if a regex operator, the extracted graph */
32 : TrgmPackedGraph *graph;
33 :
34 : /*
35 : * The "query" and "trigrams" are stored in the same palloc block as this
36 : * cache struct, at MAXALIGN'ed offsets. The graph however isn't.
37 : */
38 : } gtrgm_consistent_cache;
39 :
40 : #define GETENTRY(vec,pos) ((TRGM *) DatumGetPointer((vec)->vector[(pos)].key))
41 :
42 :
43 2 : PG_FUNCTION_INFO_V1(gtrgm_in);
44 2 : PG_FUNCTION_INFO_V1(gtrgm_out);
45 10 : PG_FUNCTION_INFO_V1(gtrgm_compress);
46 10 : PG_FUNCTION_INFO_V1(gtrgm_decompress);
47 10 : PG_FUNCTION_INFO_V1(gtrgm_consistent);
48 10 : PG_FUNCTION_INFO_V1(gtrgm_distance);
49 10 : PG_FUNCTION_INFO_V1(gtrgm_union);
50 10 : PG_FUNCTION_INFO_V1(gtrgm_same);
51 10 : PG_FUNCTION_INFO_V1(gtrgm_penalty);
52 10 : PG_FUNCTION_INFO_V1(gtrgm_picksplit);
53 10 : PG_FUNCTION_INFO_V1(gtrgm_options);
54 :
55 :
56 : Datum
57 0 : gtrgm_in(PG_FUNCTION_ARGS)
58 : {
59 0 : ereport(ERROR,
60 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
61 : errmsg("cannot accept a value of type %s", "gtrgm")));
62 :
63 : PG_RETURN_VOID(); /* keep compiler quiet */
64 : }
65 :
66 : Datum
67 0 : gtrgm_out(PG_FUNCTION_ARGS)
68 : {
69 0 : ereport(ERROR,
70 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
71 : errmsg("cannot display a value of type %s", "gtrgm")));
72 :
73 : PG_RETURN_VOID(); /* keep compiler quiet */
74 : }
75 :
76 : static TRGM *
77 56260 : gtrgm_alloc(bool isalltrue, int siglen, BITVECP sign)
78 : {
79 56260 : int flag = SIGNKEY | (isalltrue ? ALLISTRUE : 0);
80 56260 : int size = CALCGTSIZE(flag, siglen);
81 56260 : TRGM *res = palloc(size);
82 :
83 56260 : SET_VARSIZE(res, size);
84 56260 : res->flag = flag;
85 :
86 56260 : if (!isalltrue)
87 : {
88 56260 : if (sign)
89 1108 : memcpy(GETSIGN(res), sign, siglen);
90 : else
91 55152 : memset(GETSIGN(res), 0, siglen);
92 : }
93 :
94 56260 : return res;
95 : }
96 :
97 : static void
98 94970 : makesign(BITVECP sign, TRGM *a, int siglen)
99 : {
100 : int32 k,
101 94970 : len = ARRNELEM(a);
102 94970 : trgm *ptr = GETARR(a);
103 94970 : int32 tmp = 0;
104 :
105 94970 : MemSet(sign, 0, siglen);
106 94970 : SETBIT(sign, SIGLENBIT(siglen)); /* set last unused bit */
107 932876 : for (k = 0; k < len; k++)
108 : {
109 837906 : CPTRGM(&tmp, ptr + k);
110 837906 : HASH(sign, tmp, siglen);
111 : }
112 94970 : }
113 :
114 : Datum
115 55668 : gtrgm_compress(PG_FUNCTION_ARGS)
116 : {
117 55668 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
118 55668 : int siglen = GET_SIGLEN();
119 55668 : GISTENTRY *retval = entry;
120 :
121 55668 : if (entry->leafkey)
122 : { /* trgm */
123 : TRGM *res;
124 48904 : text *val = DatumGetTextPP(entry->key);
125 :
126 48904 : res = generate_trgm(VARDATA_ANY(val), VARSIZE_ANY_EXHDR(val));
127 48904 : retval = palloc_object(GISTENTRY);
128 48904 : gistentryinit(*retval, PointerGetDatum(res),
129 : entry->rel, entry->page,
130 : entry->offset, false);
131 : }
132 6764 : else if (ISSIGNKEY(DatumGetPointer(entry->key)) &&
133 6764 : !ISALLTRUE(DatumGetPointer(entry->key)))
134 : {
135 : int32 i;
136 : TRGM *res;
137 6764 : BITVECP sign = GETSIGN(DatumGetPointer(entry->key));
138 :
139 7088 : LOOPBYTE(siglen)
140 : {
141 7088 : if ((sign[i] & 0xff) != 0xff)
142 6764 : PG_RETURN_POINTER(retval);
143 : }
144 :
145 0 : res = gtrgm_alloc(true, siglen, sign);
146 0 : retval = palloc_object(GISTENTRY);
147 0 : gistentryinit(*retval, PointerGetDatum(res),
148 : entry->rel, entry->page,
149 : entry->offset, false);
150 : }
151 48904 : PG_RETURN_POINTER(retval);
152 : }
153 :
154 : Datum
155 2728876 : gtrgm_decompress(PG_FUNCTION_ARGS)
156 : {
157 2728876 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
158 : GISTENTRY *retval;
159 : text *key;
160 :
161 2728876 : key = DatumGetTextPP(entry->key);
162 :
163 2728876 : if (key != (text *) DatumGetPointer(entry->key))
164 : {
165 : /* need to pass back the decompressed item */
166 0 : retval = palloc_object(GISTENTRY);
167 0 : gistentryinit(*retval, PointerGetDatum(key),
168 : entry->rel, entry->page, entry->offset, entry->leafkey);
169 0 : PG_RETURN_POINTER(retval);
170 : }
171 : else
172 : {
173 : /* we can return the entry as-is */
174 2728876 : PG_RETURN_POINTER(entry);
175 : }
176 : }
177 :
178 : static int32
179 1280 : cnt_sml_sign_common(TRGM *qtrg, BITVECP sign, int siglen)
180 : {
181 1280 : int32 count = 0;
182 : int32 k,
183 1280 : len = ARRNELEM(qtrg);
184 1280 : trgm *ptr = GETARR(qtrg);
185 1280 : int32 tmp = 0;
186 :
187 11700 : for (k = 0; k < len; k++)
188 : {
189 10420 : CPTRGM(&tmp, ptr + k);
190 10420 : count += GETBIT(sign, HASHVAL(tmp, siglen));
191 : }
192 :
193 1280 : return count;
194 : }
195 :
196 : Datum
197 75320 : gtrgm_consistent(PG_FUNCTION_ARGS)
198 : {
199 75320 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
200 75320 : text *query = PG_GETARG_TEXT_P(1);
201 75320 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
202 : #ifdef NOT_USED
203 : Oid subtype = PG_GETARG_OID(3);
204 : #endif
205 75320 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
206 75320 : int siglen = GET_SIGLEN();
207 75320 : TRGM *key = (TRGM *) DatumGetPointer(entry->key);
208 : TRGM *qtrg;
209 : bool res;
210 75320 : Size querysize = VARSIZE(query);
211 : gtrgm_consistent_cache *cache;
212 : double nlimit;
213 :
214 : /*
215 : * We keep the extracted trigrams in cache, because trigram extraction is
216 : * relatively CPU-expensive. When trying to reuse a cached value, check
217 : * strategy number not just query itself, because trigram extraction
218 : * depends on strategy.
219 : *
220 : * The cached structure is a single palloc chunk containing the
221 : * gtrgm_consistent_cache header, then the input query (4-byte length
222 : * word, uncompressed, starting at a MAXALIGN boundary), then the TRGM
223 : * value (also starting at a MAXALIGN boundary). However we don't try to
224 : * include the regex graph (if any) in that struct. (XXX currently, this
225 : * approach can leak regex graphs across index rescans. Not clear if
226 : * that's worth fixing.)
227 : */
228 75320 : cache = (gtrgm_consistent_cache *) fcinfo->flinfo->fn_extra;
229 75320 : if (cache == NULL ||
230 150416 : cache->strategy != strategy ||
231 75208 : VARSIZE(cache->query) != querysize ||
232 75208 : memcmp(cache->query, query, querysize) != 0)
233 : {
234 : gtrgm_consistent_cache *newcache;
235 112 : TrgmPackedGraph *graph = NULL;
236 : Size qtrgsize;
237 :
238 112 : switch (strategy)
239 : {
240 56 : case SimilarityStrategyNumber:
241 : case WordSimilarityStrategyNumber:
242 : case StrictWordSimilarityStrategyNumber:
243 : case EqualStrategyNumber:
244 56 : qtrg = generate_trgm(VARDATA(query),
245 56 : querysize - VARHDRSZ);
246 56 : break;
247 14 : case ILikeStrategyNumber:
248 : #ifndef IGNORECASE
249 : elog(ERROR, "cannot handle ~~* with case-sensitive trigrams");
250 : #endif
251 : /* FALL THRU */
252 : case LikeStrategyNumber:
253 14 : qtrg = generate_wildcard_trgm(VARDATA(query),
254 14 : querysize - VARHDRSZ);
255 14 : break;
256 42 : case RegExpICaseStrategyNumber:
257 : #ifndef IGNORECASE
258 : elog(ERROR, "cannot handle ~* with case-sensitive trigrams");
259 : #endif
260 : /* FALL THRU */
261 : case RegExpStrategyNumber:
262 42 : qtrg = createTrgmNFA(query, PG_GET_COLLATION(),
263 42 : &graph, fcinfo->flinfo->fn_mcxt);
264 : /* just in case an empty array is returned ... */
265 42 : if (qtrg && ARRNELEM(qtrg) <= 0)
266 : {
267 0 : pfree(qtrg);
268 0 : qtrg = NULL;
269 : }
270 42 : break;
271 0 : default:
272 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
273 : qtrg = NULL; /* keep compiler quiet */
274 : break;
275 : }
276 :
277 112 : qtrgsize = qtrg ? VARSIZE(qtrg) : 0;
278 :
279 : newcache = (gtrgm_consistent_cache *)
280 112 : MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
281 : MAXALIGN(sizeof(gtrgm_consistent_cache)) +
282 112 : MAXALIGN(querysize) +
283 : qtrgsize);
284 :
285 112 : newcache->strategy = strategy;
286 112 : newcache->query = (text *)
287 : ((char *) newcache + MAXALIGN(sizeof(gtrgm_consistent_cache)));
288 112 : memcpy(newcache->query, query, querysize);
289 112 : if (qtrg)
290 : {
291 104 : newcache->trigrams = (TRGM *)
292 104 : ((char *) newcache->query + MAXALIGN(querysize));
293 104 : memcpy((char *) newcache->trigrams, qtrg, qtrgsize);
294 : /* release qtrg in case it was made in fn_mcxt */
295 104 : pfree(qtrg);
296 : }
297 : else
298 8 : newcache->trigrams = NULL;
299 112 : newcache->graph = graph;
300 :
301 112 : if (cache)
302 0 : pfree(cache);
303 112 : fcinfo->flinfo->fn_extra = newcache;
304 112 : cache = newcache;
305 : }
306 :
307 75320 : qtrg = cache->trigrams;
308 :
309 75320 : switch (strategy)
310 : {
311 70516 : case SimilarityStrategyNumber:
312 : case WordSimilarityStrategyNumber:
313 : case StrictWordSimilarityStrategyNumber:
314 :
315 : /*
316 : * Similarity search is exact. (Strict) word similarity search is
317 : * inexact
318 : */
319 70516 : *recheck = (strategy != SimilarityStrategyNumber);
320 :
321 70516 : nlimit = index_strategy_get_limit(strategy);
322 :
323 70516 : if (GIST_LEAF(entry))
324 : { /* all leafs contains orig trgm */
325 69312 : double tmpsml = cnt_sml(qtrg, key, *recheck);
326 :
327 69312 : res = (tmpsml >= nlimit);
328 : }
329 1204 : else if (ISALLTRUE(key))
330 : { /* non-leaf contains signature */
331 0 : res = true;
332 : }
333 : else
334 : { /* non-leaf contains signature */
335 1204 : int32 count = cnt_sml_sign_common(qtrg, GETSIGN(key), siglen);
336 1204 : int32 len = ARRNELEM(qtrg);
337 :
338 1204 : if (len == 0)
339 0 : res = false;
340 : else
341 1204 : res = (((((float8) count) / ((float8) len))) >= nlimit);
342 : }
343 70516 : break;
344 380 : case ILikeStrategyNumber:
345 : #ifndef IGNORECASE
346 : elog(ERROR, "cannot handle ~~* with case-sensitive trigrams");
347 : #endif
348 : /* FALL THRU */
349 : case LikeStrategyNumber:
350 : case EqualStrategyNumber:
351 : /* Wildcard and equal search are inexact */
352 380 : *recheck = true;
353 :
354 : /*
355 : * Check if all the extracted trigrams can be present in child
356 : * nodes.
357 : */
358 380 : if (GIST_LEAF(entry))
359 : { /* all leafs contains orig trgm */
360 380 : res = trgm_contained_by(qtrg, key);
361 : }
362 0 : else if (ISALLTRUE(key))
363 : { /* non-leaf contains signature */
364 0 : res = true;
365 : }
366 : else
367 : { /* non-leaf contains signature */
368 : int32 k,
369 0 : tmp = 0,
370 0 : len = ARRNELEM(qtrg);
371 0 : trgm *ptr = GETARR(qtrg);
372 0 : BITVECP sign = GETSIGN(key);
373 :
374 0 : res = true;
375 0 : for (k = 0; k < len; k++)
376 : {
377 0 : CPTRGM(&tmp, ptr + k);
378 0 : if (!GETBIT(sign, HASHVAL(tmp, siglen)))
379 : {
380 0 : res = false;
381 0 : break;
382 : }
383 : }
384 : }
385 380 : break;
386 4424 : case RegExpICaseStrategyNumber:
387 : #ifndef IGNORECASE
388 : elog(ERROR, "cannot handle ~* with case-sensitive trigrams");
389 : #endif
390 : /* FALL THRU */
391 : case RegExpStrategyNumber:
392 : /* Regexp search is inexact */
393 4424 : *recheck = true;
394 :
395 : /* Check regex match as much as we can with available info */
396 4424 : if (qtrg)
397 : {
398 4344 : if (GIST_LEAF(entry))
399 : { /* all leafs contains orig trgm */
400 : bool *check;
401 :
402 4300 : check = trgm_presence_map(qtrg, key);
403 4300 : res = trigramsMatchGraph(cache->graph, check);
404 4300 : pfree(check);
405 : }
406 44 : else if (ISALLTRUE(key))
407 : { /* non-leaf contains signature */
408 0 : res = true;
409 : }
410 : else
411 : { /* non-leaf contains signature */
412 : int32 k,
413 44 : tmp = 0,
414 44 : len = ARRNELEM(qtrg);
415 44 : trgm *ptr = GETARR(qtrg);
416 44 : BITVECP sign = GETSIGN(key);
417 : bool *check;
418 :
419 : /*
420 : * GETBIT() tests may give false positives, due to limited
421 : * size of the sign array. But since trigramsMatchGraph()
422 : * implements a monotone boolean function, false positives
423 : * in the check array can't lead to false negative answer.
424 : * So we can apply trigramsMatchGraph despite uncertainty,
425 : * and that usefully improves the quality of the search.
426 : */
427 44 : check = (bool *) palloc(len * sizeof(bool));
428 11132 : for (k = 0; k < len; k++)
429 : {
430 11088 : CPTRGM(&tmp, ptr + k);
431 11088 : check[k] = GETBIT(sign, HASHVAL(tmp, siglen));
432 : }
433 44 : res = trigramsMatchGraph(cache->graph, check);
434 44 : pfree(check);
435 : }
436 : }
437 : else
438 : {
439 : /* trigram-free query must be rechecked everywhere */
440 80 : res = true;
441 : }
442 4424 : break;
443 0 : default:
444 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
445 : res = false; /* keep compiler quiet */
446 : break;
447 : }
448 :
449 75320 : PG_RETURN_BOOL(res);
450 : }
451 :
452 : Datum
453 5946 : gtrgm_distance(PG_FUNCTION_ARGS)
454 : {
455 5946 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
456 5946 : text *query = PG_GETARG_TEXT_P(1);
457 5946 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
458 : #ifdef NOT_USED
459 : Oid subtype = PG_GETARG_OID(3);
460 : #endif
461 5946 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
462 5946 : int siglen = GET_SIGLEN();
463 5946 : TRGM *key = (TRGM *) DatumGetPointer(entry->key);
464 : TRGM *qtrg;
465 : float8 res;
466 5946 : Size querysize = VARSIZE(query);
467 5946 : char *cache = (char *) fcinfo->flinfo->fn_extra;
468 :
469 : /*
470 : * Cache the generated trigrams across multiple calls with the same query.
471 : */
472 11884 : if (cache == NULL ||
473 5938 : VARSIZE(cache) != querysize ||
474 5938 : memcmp(cache, query, querysize) != 0)
475 : {
476 : char *newcache;
477 :
478 8 : qtrg = generate_trgm(VARDATA(query), querysize - VARHDRSZ);
479 :
480 8 : newcache = MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
481 8 : MAXALIGN(querysize) +
482 8 : VARSIZE(qtrg));
483 :
484 8 : memcpy(newcache, query, querysize);
485 8 : memcpy(newcache + MAXALIGN(querysize), qtrg, VARSIZE(qtrg));
486 :
487 8 : if (cache)
488 0 : pfree(cache);
489 8 : fcinfo->flinfo->fn_extra = newcache;
490 8 : cache = newcache;
491 : }
492 :
493 5946 : qtrg = (TRGM *) (cache + MAXALIGN(querysize));
494 :
495 5946 : switch (strategy)
496 : {
497 5946 : case DistanceStrategyNumber:
498 : case WordDistanceStrategyNumber:
499 : case StrictWordDistanceStrategyNumber:
500 : /* Only plain trigram distance is exact */
501 5946 : *recheck = (strategy != DistanceStrategyNumber);
502 5946 : if (GIST_LEAF(entry))
503 : { /* all leafs contains orig trgm */
504 :
505 : /*
506 : * Prevent gcc optimizing the sml variable using volatile
507 : * keyword. Otherwise res can differ from the
508 : * word_similarity_dist_op() function.
509 : */
510 5870 : float4 volatile sml = cnt_sml(qtrg, key, *recheck);
511 :
512 5870 : res = 1.0 - sml;
513 : }
514 76 : else if (ISALLTRUE(key))
515 : { /* all leafs contains orig trgm */
516 0 : res = 0.0;
517 : }
518 : else
519 : { /* non-leaf contains signature */
520 76 : int32 count = cnt_sml_sign_common(qtrg, GETSIGN(key), siglen);
521 76 : int32 len = ARRNELEM(qtrg);
522 :
523 76 : res = (len == 0) ? -1.0 : 1.0 - ((float8) count) / ((float8) len);
524 : }
525 5946 : break;
526 0 : default:
527 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
528 : res = 0; /* keep compiler quiet */
529 : break;
530 : }
531 :
532 5946 : PG_RETURN_FLOAT8(res);
533 : }
534 :
535 : static int32
536 110304 : unionkey(BITVECP sbase, TRGM *add, int siglen)
537 : {
538 : int32 i;
539 :
540 110304 : if (ISSIGNKEY(add))
541 : {
542 55152 : BITVECP sadd = GETSIGN(add);
543 :
544 55152 : if (ISALLTRUE(add))
545 0 : return 1;
546 :
547 13006272 : LOOPBYTE(siglen)
548 12951120 : sbase[i] |= sadd[i];
549 : }
550 : else
551 : {
552 55152 : trgm *ptr = GETARR(add);
553 55152 : int32 tmp = 0;
554 :
555 551538 : for (i = 0; i < ARRNELEM(add); i++)
556 : {
557 496386 : CPTRGM(&tmp, ptr + i);
558 496386 : HASH(sbase, tmp, siglen);
559 : }
560 : }
561 110304 : return 0;
562 : }
563 :
564 :
565 : Datum
566 55152 : gtrgm_union(PG_FUNCTION_ARGS)
567 : {
568 55152 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
569 55152 : int32 len = entryvec->n;
570 55152 : int *size = (int *) PG_GETARG_POINTER(1);
571 55152 : int siglen = GET_SIGLEN();
572 : int32 i;
573 55152 : TRGM *result = gtrgm_alloc(false, siglen, NULL);
574 55152 : BITVECP base = GETSIGN(result);
575 :
576 165456 : for (i = 0; i < len; i++)
577 : {
578 110304 : if (unionkey(base, GETENTRY(entryvec, i), siglen))
579 : {
580 0 : result->flag = ALLISTRUE;
581 0 : SET_VARSIZE(result, CALCGTSIZE(ALLISTRUE, siglen));
582 0 : break;
583 : }
584 : }
585 :
586 55152 : *size = VARSIZE(result);
587 :
588 55152 : PG_RETURN_POINTER(result);
589 : }
590 :
591 : Datum
592 55152 : gtrgm_same(PG_FUNCTION_ARGS)
593 : {
594 55152 : TRGM *a = (TRGM *) PG_GETARG_POINTER(0);
595 55152 : TRGM *b = (TRGM *) PG_GETARG_POINTER(1);
596 55152 : bool *result = (bool *) PG_GETARG_POINTER(2);
597 55152 : int siglen = GET_SIGLEN();
598 :
599 55152 : if (ISSIGNKEY(a))
600 : { /* then b also ISSIGNKEY */
601 55152 : if (ISALLTRUE(a) && ISALLTRUE(b))
602 0 : *result = true;
603 55152 : else if (ISALLTRUE(a))
604 0 : *result = false;
605 55152 : else if (ISALLTRUE(b))
606 0 : *result = false;
607 : else
608 : {
609 : int32 i;
610 55152 : BITVECP sa = GETSIGN(a),
611 55152 : sb = GETSIGN(b);
612 :
613 55152 : *result = true;
614 6269434 : LOOPBYTE(siglen)
615 : {
616 6219938 : if (sa[i] != sb[i])
617 : {
618 5656 : *result = false;
619 5656 : break;
620 : }
621 : }
622 : }
623 : }
624 : else
625 : { /* a and b ISARRKEY */
626 0 : int32 lena = ARRNELEM(a),
627 0 : lenb = ARRNELEM(b);
628 :
629 0 : if (lena != lenb)
630 0 : *result = false;
631 : else
632 : {
633 0 : trgm *ptra = GETARR(a),
634 0 : *ptrb = GETARR(b);
635 : int32 i;
636 :
637 0 : *result = true;
638 0 : for (i = 0; i < lena; i++)
639 0 : if (CMPTRGM(ptra + i, ptrb + i))
640 : {
641 0 : *result = false;
642 0 : break;
643 : }
644 : }
645 : }
646 :
647 55152 : PG_RETURN_POINTER(result);
648 : }
649 :
650 : static int32
651 0 : sizebitvec(BITVECP sign, int siglen)
652 : {
653 0 : return pg_popcount(sign, siglen);
654 : }
655 :
656 : static int
657 9834218 : hemdistsign(BITVECP a, BITVECP b, int siglen)
658 : {
659 : int i,
660 : diff,
661 9834218 : dist = 0;
662 :
663 673833226 : LOOPBYTE(siglen)
664 : {
665 663999008 : diff = (unsigned char) (a[i] ^ b[i]);
666 : /* Using the popcount functions here isn't likely to win */
667 663999008 : dist += pg_number_of_ones[diff];
668 : }
669 9834218 : return dist;
670 : }
671 :
672 : static int
673 0 : hemdist(TRGM *a, TRGM *b, int siglen)
674 : {
675 0 : if (ISALLTRUE(a))
676 : {
677 0 : if (ISALLTRUE(b))
678 0 : return 0;
679 : else
680 0 : return SIGLENBIT(siglen) - sizebitvec(GETSIGN(b), siglen);
681 : }
682 0 : else if (ISALLTRUE(b))
683 0 : return SIGLENBIT(siglen) - sizebitvec(GETSIGN(a), siglen);
684 :
685 0 : return hemdistsign(GETSIGN(a), GETSIGN(b), siglen);
686 : }
687 :
688 : Datum
689 2394270 : gtrgm_penalty(PG_FUNCTION_ARGS)
690 : {
691 2394270 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
692 2394270 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
693 2394270 : float *penalty = (float *) PG_GETARG_POINTER(2);
694 2394270 : int siglen = GET_SIGLEN();
695 2394270 : TRGM *origval = (TRGM *) DatumGetPointer(origentry->key);
696 2394270 : TRGM *newval = (TRGM *) DatumGetPointer(newentry->key);
697 2394270 : BITVECP orig = GETSIGN(origval);
698 :
699 2394270 : *penalty = 0.0;
700 :
701 2394270 : if (ISARRKEY(newval))
702 : {
703 2394270 : char *cache = (char *) fcinfo->flinfo->fn_extra;
704 2394270 : TRGM *cachedVal = NULL;
705 2394270 : Size newvalsize = VARSIZE(newval);
706 : BITVECP sign;
707 :
708 2394270 : if (cache != NULL)
709 2394258 : cachedVal = (TRGM *) (cache + MAXALIGN(siglen));
710 :
711 : /*
712 : * Cache the sign data across multiple calls with the same newval.
713 : */
714 4788528 : if (cache == NULL ||
715 2394258 : VARSIZE(cachedVal) != newvalsize ||
716 2392204 : memcmp(cachedVal, newval, newvalsize) != 0)
717 : {
718 : char *newcache;
719 :
720 7526 : newcache = MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
721 7526 : MAXALIGN(siglen) +
722 : newvalsize);
723 :
724 7526 : makesign((BITVECP) newcache, newval, siglen);
725 :
726 7526 : cachedVal = (TRGM *) (newcache + MAXALIGN(siglen));
727 7526 : memcpy(cachedVal, newval, newvalsize);
728 :
729 7526 : if (cache)
730 7514 : pfree(cache);
731 7526 : fcinfo->flinfo->fn_extra = newcache;
732 7526 : cache = newcache;
733 : }
734 :
735 2394270 : sign = (BITVECP) cache;
736 :
737 2394270 : if (ISALLTRUE(origval))
738 0 : *penalty = ((float) (SIGLENBIT(siglen) - sizebitvec(sign, siglen))) / (float) (SIGLENBIT(siglen) + 1);
739 : else
740 2394270 : *penalty = hemdistsign(sign, orig, siglen);
741 : }
742 : else
743 0 : *penalty = hemdist(origval, newval, siglen);
744 2394270 : PG_RETURN_POINTER(penalty);
745 : }
746 :
747 : typedef struct
748 : {
749 : bool allistrue;
750 : BITVECP sign;
751 : } CACHESIGN;
752 :
753 : static void
754 87884 : fillcache(CACHESIGN *item, TRGM *key, BITVECP sign, int siglen)
755 : {
756 87884 : item->allistrue = false;
757 87884 : item->sign = sign;
758 87884 : if (ISARRKEY(key))
759 87444 : makesign(item->sign, key, siglen);
760 440 : else if (ISALLTRUE(key))
761 0 : item->allistrue = true;
762 : else
763 440 : memcpy(item->sign, GETSIGN(key), siglen);
764 87884 : }
765 :
766 : #define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
767 : typedef struct
768 : {
769 : OffsetNumber pos;
770 : int32 cost;
771 : } SPLITCOST;
772 :
773 : static int
774 98434 : comparecost(const void *a, const void *b)
775 : {
776 98434 : if (((const SPLITCOST *) a)->cost == ((const SPLITCOST *) b)->cost)
777 88176 : return 0;
778 : else
779 10258 : return (((const SPLITCOST *) a)->cost > ((const SPLITCOST *) b)->cost) ? 1 : -1;
780 : }
781 :
782 :
783 : static int
784 7266396 : hemdistcache(CACHESIGN *a, CACHESIGN *b, int siglen)
785 : {
786 7266396 : if (a->allistrue)
787 : {
788 0 : if (b->allistrue)
789 0 : return 0;
790 : else
791 0 : return SIGLENBIT(siglen) - sizebitvec(b->sign, siglen);
792 : }
793 7266396 : else if (b->allistrue)
794 0 : return SIGLENBIT(siglen) - sizebitvec(a->sign, siglen);
795 :
796 7266396 : return hemdistsign(a->sign, b->sign, siglen);
797 : }
798 :
799 : Datum
800 554 : gtrgm_picksplit(PG_FUNCTION_ARGS)
801 : {
802 554 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
803 554 : OffsetNumber maxoff = entryvec->n - 1;
804 554 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
805 554 : int siglen = GET_SIGLEN();
806 : OffsetNumber k,
807 : j;
808 : TRGM *datum_l,
809 : *datum_r;
810 : BITVECP union_l,
811 : union_r;
812 : int32 size_alpha,
813 : size_beta;
814 : int32 size_waste,
815 554 : waste = -1;
816 : int32 nbytes;
817 554 : OffsetNumber seed_1 = 0,
818 554 : seed_2 = 0;
819 : OffsetNumber *left,
820 : *right;
821 : BITVECP ptr;
822 : int i;
823 : CACHESIGN *cache;
824 : char *cache_sign;
825 : SPLITCOST *costvector;
826 :
827 : /* cache the sign data for each existing item */
828 554 : cache = palloc_array(CACHESIGN, maxoff + 1);
829 554 : cache_sign = palloc(siglen * (maxoff + 1));
830 :
831 88438 : for (k = FirstOffsetNumber; k <= maxoff; k = OffsetNumberNext(k))
832 87884 : fillcache(&cache[k], GETENTRY(entryvec, k), &cache_sign[siglen * k],
833 : siglen);
834 :
835 : /* now find the two furthest-apart items */
836 87884 : for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
837 : {
838 7177958 : for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
839 : {
840 7090628 : size_waste = hemdistcache(&(cache[j]), &(cache[k]), siglen);
841 7090628 : if (size_waste > waste)
842 : {
843 914 : waste = size_waste;
844 914 : seed_1 = k;
845 914 : seed_2 = j;
846 : }
847 : }
848 : }
849 :
850 : /* just in case we didn't make a selection ... */
851 554 : if (seed_1 == 0 || seed_2 == 0)
852 : {
853 0 : seed_1 = 1;
854 0 : seed_2 = 2;
855 : }
856 :
857 : /* initialize the result vectors */
858 554 : nbytes = maxoff * sizeof(OffsetNumber);
859 554 : v->spl_left = left = (OffsetNumber *) palloc(nbytes);
860 554 : v->spl_right = right = (OffsetNumber *) palloc(nbytes);
861 554 : v->spl_nleft = 0;
862 554 : v->spl_nright = 0;
863 :
864 : /* form initial .. */
865 554 : datum_l = gtrgm_alloc(cache[seed_1].allistrue, siglen, cache[seed_1].sign);
866 554 : datum_r = gtrgm_alloc(cache[seed_2].allistrue, siglen, cache[seed_2].sign);
867 :
868 554 : union_l = GETSIGN(datum_l);
869 554 : union_r = GETSIGN(datum_r);
870 :
871 : /* sort before ... */
872 554 : costvector = palloc_array(SPLITCOST, maxoff);
873 88438 : for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
874 : {
875 87884 : costvector[j - 1].pos = j;
876 87884 : size_alpha = hemdistcache(&(cache[seed_1]), &(cache[j]), siglen);
877 87884 : size_beta = hemdistcache(&(cache[seed_2]), &(cache[j]), siglen);
878 87884 : costvector[j - 1].cost = abs(size_alpha - size_beta);
879 : }
880 554 : qsort(costvector, maxoff, sizeof(SPLITCOST), comparecost);
881 :
882 88438 : for (k = 0; k < maxoff; k++)
883 : {
884 87884 : j = costvector[k].pos;
885 87884 : if (j == seed_1)
886 : {
887 554 : *left++ = j;
888 554 : v->spl_nleft++;
889 554 : continue;
890 : }
891 87330 : else if (j == seed_2)
892 : {
893 554 : *right++ = j;
894 554 : v->spl_nright++;
895 554 : continue;
896 : }
897 :
898 86776 : if (ISALLTRUE(datum_l) || cache[j].allistrue)
899 : {
900 0 : if (ISALLTRUE(datum_l) && cache[j].allistrue)
901 0 : size_alpha = 0;
902 : else
903 0 : size_alpha = SIGLENBIT(siglen) -
904 0 : sizebitvec((cache[j].allistrue) ? GETSIGN(datum_l) :
905 0 : GETSIGN(cache[j].sign),
906 : siglen);
907 : }
908 : else
909 86776 : size_alpha = hemdistsign(cache[j].sign, GETSIGN(datum_l), siglen);
910 :
911 86776 : if (ISALLTRUE(datum_r) || cache[j].allistrue)
912 : {
913 0 : if (ISALLTRUE(datum_r) && cache[j].allistrue)
914 0 : size_beta = 0;
915 : else
916 0 : size_beta = SIGLENBIT(siglen) -
917 0 : sizebitvec((cache[j].allistrue) ? GETSIGN(datum_r) :
918 0 : GETSIGN(cache[j].sign),
919 : siglen);
920 : }
921 : else
922 86776 : size_beta = hemdistsign(cache[j].sign, GETSIGN(datum_r), siglen);
923 :
924 86776 : if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.1))
925 : {
926 43146 : if (ISALLTRUE(datum_l) || cache[j].allistrue)
927 : {
928 0 : if (!ISALLTRUE(datum_l))
929 0 : memset(GETSIGN(datum_l), 0xff, siglen);
930 : }
931 : else
932 : {
933 43146 : ptr = cache[j].sign;
934 4480274 : LOOPBYTE(siglen)
935 4437128 : union_l[i] |= ptr[i];
936 : }
937 43146 : *left++ = j;
938 43146 : v->spl_nleft++;
939 : }
940 : else
941 : {
942 43630 : if (ISALLTRUE(datum_r) || cache[j].allistrue)
943 : {
944 0 : if (!ISALLTRUE(datum_r))
945 0 : memset(GETSIGN(datum_r), 0xff, siglen);
946 : }
947 : else
948 : {
949 43630 : ptr = cache[j].sign;
950 4470470 : LOOPBYTE(siglen)
951 4426840 : union_r[i] |= ptr[i];
952 : }
953 43630 : *right++ = j;
954 43630 : v->spl_nright++;
955 : }
956 : }
957 :
958 554 : v->spl_ldatum = PointerGetDatum(datum_l);
959 554 : v->spl_rdatum = PointerGetDatum(datum_r);
960 :
961 554 : PG_RETURN_POINTER(v);
962 : }
963 :
964 : Datum
965 62 : gtrgm_options(PG_FUNCTION_ARGS)
966 : {
967 62 : local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
968 :
969 62 : init_local_reloptions(relopts, sizeof(TrgmGistOptions));
970 62 : add_local_int_reloption(relopts, "siglen",
971 : "signature length in bytes",
972 : SIGLEN_DEFAULT, 1, SIGLEN_MAX,
973 : offsetof(TrgmGistOptions, siglen));
974 :
975 62 : PG_RETURN_VOID();
976 : }
|
