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