Line data Source code
1 : /*
2 : * contrib/ltree/_ltree_gist.c
3 : *
4 : *
5 : * GiST support for ltree[]
6 : * Teodor Sigaev <teodor@stack.net>
7 : */
8 : #include "postgres.h"
9 :
10 : #include "access/gist.h"
11 : #include "access/reloptions.h"
12 : #include "access/stratnum.h"
13 : #include "crc32.h"
14 : #include "ltree.h"
15 : #include "port/pg_bitutils.h"
16 :
17 6 : PG_FUNCTION_INFO_V1(_ltree_compress);
18 6 : PG_FUNCTION_INFO_V1(_ltree_same);
19 6 : PG_FUNCTION_INFO_V1(_ltree_union);
20 6 : PG_FUNCTION_INFO_V1(_ltree_penalty);
21 6 : PG_FUNCTION_INFO_V1(_ltree_picksplit);
22 6 : PG_FUNCTION_INFO_V1(_ltree_consistent);
23 6 : PG_FUNCTION_INFO_V1(_ltree_gist_options);
24 :
25 : #define GETENTRY(vec,pos) ((ltree_gist *) DatumGetPointer((vec)->vector[(pos)].key))
26 : #define NEXTVAL(x) ( (ltree*)( (char*)(x) + INTALIGN( VARSIZE(x) ) ) )
27 :
28 : #define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
29 :
30 :
31 : static void
32 14116 : hashing(BITVECP sign, ltree *t, int siglen)
33 : {
34 14116 : int tlen = t->numlevel;
35 14116 : ltree_level *cur = LTREE_FIRST(t);
36 : int hash;
37 :
38 106932 : while (tlen > 0)
39 : {
40 92816 : hash = ltree_crc32_sz(cur->name, cur->len);
41 92816 : AHASH(sign, hash, siglen);
42 92816 : cur = LEVEL_NEXT(cur);
43 92816 : tlen--;
44 : }
45 14116 : }
46 :
47 : Datum
48 11842 : _ltree_compress(PG_FUNCTION_ARGS)
49 : {
50 11842 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
51 11842 : GISTENTRY *retval = entry;
52 11842 : int siglen = LTREE_GET_ASIGLEN();
53 :
54 11842 : if (entry->leafkey)
55 : { /* ltree */
56 : ltree_gist *key;
57 4000 : ArrayType *val = DatumGetArrayTypeP(entry->key);
58 4000 : int num = ArrayGetNItems(ARR_NDIM(val), ARR_DIMS(val));
59 4000 : ltree *item = (ltree *) ARR_DATA_PTR(val);
60 :
61 4000 : if (ARR_NDIM(val) > 1)
62 0 : ereport(ERROR,
63 : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
64 : errmsg("array must be one-dimensional")));
65 4000 : if (array_contains_nulls(val))
66 0 : ereport(ERROR,
67 : (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
68 : errmsg("array must not contain nulls")));
69 :
70 4000 : key = ltree_gist_alloc(false, NULL, siglen, NULL, NULL);
71 :
72 18116 : while (num > 0)
73 : {
74 14116 : hashing(LTG_SIGN(key), item, siglen);
75 14116 : num--;
76 14116 : item = NEXTVAL(item);
77 : }
78 :
79 4000 : retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
80 4000 : gistentryinit(*retval, PointerGetDatum(key),
81 : entry->rel, entry->page,
82 : entry->offset, false);
83 : }
84 7842 : else if (!LTG_ISALLTRUE(entry->key))
85 : {
86 : int32 i;
87 : ltree_gist *key;
88 7842 : BITVECP sign = LTG_SIGN(DatumGetPointer(entry->key));
89 :
90 7842 : ALOOPBYTE(siglen)
91 : {
92 7842 : if ((sign[i] & 0xff) != 0xff)
93 7842 : PG_RETURN_POINTER(retval);
94 : }
95 :
96 0 : key = ltree_gist_alloc(true, sign, siglen, NULL, NULL);
97 0 : retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
98 0 : gistentryinit(*retval, PointerGetDatum(key),
99 : entry->rel, entry->page,
100 : entry->offset, false);
101 : }
102 4000 : PG_RETURN_POINTER(retval);
103 : }
104 :
105 : Datum
106 15950 : _ltree_same(PG_FUNCTION_ARGS)
107 : {
108 15950 : ltree_gist *a = (ltree_gist *) PG_GETARG_POINTER(0);
109 15950 : ltree_gist *b = (ltree_gist *) PG_GETARG_POINTER(1);
110 15950 : bool *result = (bool *) PG_GETARG_POINTER(2);
111 15950 : int siglen = LTREE_GET_ASIGLEN();
112 :
113 15950 : if (LTG_ISALLTRUE(a) && LTG_ISALLTRUE(b))
114 0 : *result = true;
115 15950 : else if (LTG_ISALLTRUE(a))
116 0 : *result = false;
117 15950 : else if (LTG_ISALLTRUE(b))
118 0 : *result = false;
119 : else
120 : {
121 : int32 i;
122 15950 : BITVECP sa = LTG_SIGN(a),
123 15950 : sb = LTG_SIGN(b);
124 :
125 15950 : *result = true;
126 22701348 : ALOOPBYTE(siglen)
127 : {
128 22689668 : if (sa[i] != sb[i])
129 : {
130 4270 : *result = false;
131 4270 : break;
132 : }
133 : }
134 : }
135 15950 : PG_RETURN_POINTER(result);
136 : }
137 :
138 : static int32
139 31900 : unionkey(BITVECP sbase, ltree_gist *add, int siglen)
140 : {
141 : int32 i;
142 31900 : BITVECP sadd = LTG_SIGN(add);
143 :
144 31900 : if (LTG_ISALLTRUE(add))
145 0 : return 1;
146 :
147 57739244 : ALOOPBYTE(siglen)
148 57707344 : sbase[i] |= sadd[i];
149 31900 : return 0;
150 : }
151 :
152 : Datum
153 15950 : _ltree_union(PG_FUNCTION_ARGS)
154 : {
155 15950 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
156 15950 : int *size = (int *) PG_GETARG_POINTER(1);
157 15950 : int siglen = LTREE_GET_ASIGLEN();
158 : int32 i;
159 15950 : ltree_gist *result = ltree_gist_alloc(false, NULL, siglen, NULL, NULL);
160 15950 : BITVECP base = LTG_SIGN(result);
161 :
162 47850 : for (i = 0; i < entryvec->n; i++)
163 : {
164 31900 : if (unionkey(base, GETENTRY(entryvec, i), siglen))
165 : {
166 0 : result->flag |= LTG_ALLTRUE;
167 0 : SET_VARSIZE(result, LTG_HDRSIZE);
168 0 : break;
169 : }
170 : }
171 :
172 15950 : *size = VARSIZE(result);
173 :
174 15950 : PG_RETURN_POINTER(result);
175 : }
176 :
177 : static int32
178 0 : sizebitvec(BITVECP sign, int siglen)
179 : {
180 0 : return pg_popcount((const char *) sign, siglen);
181 : }
182 :
183 : static int
184 229904 : hemdistsign(BITVECP a, BITVECP b, int siglen)
185 : {
186 : int i,
187 : diff,
188 229904 : dist = 0;
189 :
190 117636832 : ALOOPBYTE(siglen)
191 : {
192 117406928 : diff = (unsigned char) (a[i] ^ b[i]);
193 : /* Using the popcount functions here isn't likely to win */
194 117406928 : dist += pg_number_of_ones[diff];
195 : }
196 229904 : return dist;
197 : }
198 :
199 : static int
200 229904 : hemdist(ltree_gist *a, ltree_gist *b, int siglen)
201 : {
202 229904 : if (LTG_ISALLTRUE(a))
203 : {
204 0 : if (LTG_ISALLTRUE(b))
205 0 : return 0;
206 : else
207 0 : return ASIGLENBIT(siglen) - sizebitvec(LTG_SIGN(b), siglen);
208 : }
209 229904 : else if (LTG_ISALLTRUE(b))
210 0 : return ASIGLENBIT(siglen) - sizebitvec(LTG_SIGN(a), siglen);
211 :
212 229904 : return hemdistsign(LTG_SIGN(a), LTG_SIGN(b), siglen);
213 : }
214 :
215 :
216 : Datum
217 38714 : _ltree_penalty(PG_FUNCTION_ARGS)
218 : {
219 38714 : ltree_gist *origval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(0))->key);
220 38714 : ltree_gist *newval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(1))->key);
221 38714 : float *penalty = (float *) PG_GETARG_POINTER(2);
222 38714 : int siglen = LTREE_GET_ASIGLEN();
223 :
224 38714 : *penalty = hemdist(origval, newval, siglen);
225 38714 : PG_RETURN_POINTER(penalty);
226 : }
227 :
228 : typedef struct
229 : {
230 : OffsetNumber pos;
231 : int32 cost;
232 : } SPLITCOST;
233 :
234 : static int
235 15100 : comparecost(const void *a, const void *b)
236 : {
237 15100 : return ((const SPLITCOST *) a)->cost - ((const SPLITCOST *) b)->cost;
238 : }
239 :
240 : Datum
241 1786 : _ltree_picksplit(PG_FUNCTION_ARGS)
242 : {
243 1786 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
244 1786 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
245 1786 : int siglen = LTREE_GET_ASIGLEN();
246 : OffsetNumber k,
247 : j;
248 : ltree_gist *datum_l,
249 : *datum_r;
250 : BITVECP union_l,
251 : union_r;
252 : int32 size_alpha,
253 : size_beta;
254 : int32 size_waste,
255 1786 : waste = -1;
256 : int32 nbytes;
257 1786 : OffsetNumber seed_1 = 0,
258 1786 : seed_2 = 0;
259 : OffsetNumber *left,
260 : *right;
261 : OffsetNumber maxoff;
262 : BITVECP ptr;
263 : int i;
264 : SPLITCOST *costvector;
265 : ltree_gist *_k,
266 : *_j;
267 :
268 1786 : maxoff = entryvec->n - 2;
269 1786 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
270 1786 : v->spl_left = (OffsetNumber *) palloc(nbytes);
271 1786 : v->spl_right = (OffsetNumber *) palloc(nbytes);
272 :
273 7550 : for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
274 : {
275 5764 : _k = GETENTRY(entryvec, k);
276 166754 : for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
277 : {
278 160990 : size_waste = hemdist(_k, GETENTRY(entryvec, j), siglen);
279 160990 : if (size_waste > waste)
280 : {
281 3244 : waste = size_waste;
282 3244 : seed_1 = k;
283 3244 : seed_2 = j;
284 : }
285 : }
286 : }
287 :
288 1786 : left = v->spl_left;
289 1786 : v->spl_nleft = 0;
290 1786 : right = v->spl_right;
291 1786 : v->spl_nright = 0;
292 :
293 1786 : if (seed_1 == 0 || seed_2 == 0)
294 : {
295 0 : seed_1 = 1;
296 0 : seed_2 = 2;
297 : }
298 :
299 : /* form initial .. */
300 1786 : datum_l = ltree_gist_alloc(LTG_ISALLTRUE(GETENTRY(entryvec, seed_1)),
301 1786 : LTG_SIGN(GETENTRY(entryvec, seed_1)),
302 : siglen, NULL, NULL);
303 :
304 1786 : datum_r = ltree_gist_alloc(LTG_ISALLTRUE(GETENTRY(entryvec, seed_2)),
305 1786 : LTG_SIGN(GETENTRY(entryvec, seed_2)),
306 : siglen, NULL, NULL);
307 :
308 1786 : maxoff = OffsetNumberNext(maxoff);
309 : /* sort before ... */
310 1786 : costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
311 11122 : for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
312 : {
313 9336 : costvector[j - 1].pos = j;
314 9336 : _j = GETENTRY(entryvec, j);
315 9336 : size_alpha = hemdist(datum_l, _j, siglen);
316 9336 : size_beta = hemdist(datum_r, _j, siglen);
317 9336 : costvector[j - 1].cost = Abs(size_alpha - size_beta);
318 : }
319 1786 : qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
320 :
321 1786 : union_l = LTG_SIGN(datum_l);
322 1786 : union_r = LTG_SIGN(datum_r);
323 :
324 11122 : for (k = 0; k < maxoff; k++)
325 : {
326 9336 : j = costvector[k].pos;
327 9336 : if (j == seed_1)
328 : {
329 1786 : *left++ = j;
330 1786 : v->spl_nleft++;
331 1786 : continue;
332 : }
333 7550 : else if (j == seed_2)
334 : {
335 1786 : *right++ = j;
336 1786 : v->spl_nright++;
337 1786 : continue;
338 : }
339 5764 : _j = GETENTRY(entryvec, j);
340 5764 : size_alpha = hemdist(datum_l, _j, siglen);
341 5764 : size_beta = hemdist(datum_r, _j, siglen);
342 :
343 5764 : if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.00001))
344 : {
345 2802 : if (LTG_ISALLTRUE(datum_l) || LTG_ISALLTRUE(_j))
346 : {
347 0 : if (!LTG_ISALLTRUE(datum_l))
348 0 : MemSet((void *) union_l, 0xff, siglen);
349 : }
350 : else
351 : {
352 2802 : ptr = LTG_SIGN(_j);
353 3382642 : ALOOPBYTE(siglen)
354 3379840 : union_l[i] |= ptr[i];
355 : }
356 2802 : *left++ = j;
357 2802 : v->spl_nleft++;
358 : }
359 : else
360 : {
361 2962 : if (LTG_ISALLTRUE(datum_r) || LTG_ISALLTRUE(_j))
362 : {
363 0 : if (!LTG_ISALLTRUE(datum_r))
364 0 : MemSet((void *) union_r, 0xff, siglen);
365 : }
366 : else
367 : {
368 2962 : ptr = LTG_SIGN(_j);
369 3850354 : ALOOPBYTE(siglen)
370 3847392 : union_r[i] |= ptr[i];
371 : }
372 2962 : *right++ = j;
373 2962 : v->spl_nright++;
374 : }
375 : }
376 :
377 1786 : *right = *left = FirstOffsetNumber;
378 :
379 1786 : v->spl_ldatum = PointerGetDatum(datum_l);
380 1786 : v->spl_rdatum = PointerGetDatum(datum_r);
381 :
382 1786 : PG_RETURN_POINTER(v);
383 : }
384 :
385 : static bool
386 5064 : gist_te(ltree_gist *key, ltree *query, int siglen)
387 : {
388 5064 : ltree_level *curq = LTREE_FIRST(query);
389 5064 : BITVECP sign = LTG_SIGN(key);
390 5064 : int qlen = query->numlevel;
391 : unsigned int hv;
392 :
393 5064 : if (LTG_ISALLTRUE(key))
394 0 : return true;
395 :
396 17118 : while (qlen > 0)
397 : {
398 13100 : hv = ltree_crc32_sz(curq->name, curq->len);
399 13100 : if (!GETBIT(sign, AHASHVAL(hv, siglen)))
400 1046 : return false;
401 12054 : curq = LEVEL_NEXT(curq);
402 12054 : qlen--;
403 : }
404 :
405 4018 : return true;
406 : }
407 :
408 : typedef struct LtreeSignature
409 : {
410 : BITVECP sign;
411 : int siglen;
412 : } LtreeSignature;
413 :
414 : static bool
415 7202 : checkcondition_bit(void *cxt, ITEM *val)
416 : {
417 7202 : LtreeSignature *sig = cxt;
418 :
419 7202 : return (FLG_CANLOOKSIGN(val->flag)) ? GETBIT(sig->sign, AHASHVAL(val->val, sig->siglen)) : true;
420 : }
421 :
422 : static bool
423 4190 : gist_qtxt(ltree_gist *key, ltxtquery *query, int siglen)
424 : {
425 : LtreeSignature sig;
426 :
427 4190 : if (LTG_ISALLTRUE(key))
428 0 : return true;
429 :
430 4190 : sig.sign = LTG_SIGN(key);
431 4190 : sig.siglen = siglen;
432 :
433 4190 : return ltree_execute(GETQUERY(query),
434 : &sig, false,
435 : checkcondition_bit);
436 : }
437 :
438 : static bool
439 29146 : gist_qe(ltree_gist *key, lquery *query, int siglen)
440 : {
441 29146 : lquery_level *curq = LQUERY_FIRST(query);
442 29146 : BITVECP sign = LTG_SIGN(key);
443 29146 : int qlen = query->numlevel;
444 :
445 29146 : if (LTG_ISALLTRUE(key))
446 0 : return true;
447 :
448 90338 : while (qlen > 0)
449 : {
450 72168 : if (curq->numvar && LQL_CANLOOKSIGN(curq))
451 : {
452 50134 : bool isexist = false;
453 50134 : int vlen = curq->numvar;
454 50134 : lquery_variant *curv = LQL_FIRST(curq);
455 :
456 61110 : while (vlen > 0)
457 : {
458 50134 : if (GETBIT(sign, AHASHVAL(curv->val, siglen)))
459 : {
460 39158 : isexist = true;
461 39158 : break;
462 : }
463 10976 : curv = LVAR_NEXT(curv);
464 10976 : vlen--;
465 : }
466 50134 : if (!isexist)
467 10976 : return false;
468 : }
469 :
470 61192 : curq = LQL_NEXT(curq);
471 61192 : qlen--;
472 : }
473 :
474 18170 : return true;
475 : }
476 :
477 : static bool
478 4546 : _arrq_cons(ltree_gist *key, ArrayType *_query, int siglen)
479 : {
480 4546 : lquery *query = (lquery *) ARR_DATA_PTR(_query);
481 4546 : int num = ArrayGetNItems(ARR_NDIM(_query), ARR_DIMS(_query));
482 :
483 4546 : if (ARR_NDIM(_query) > 1)
484 0 : ereport(ERROR,
485 : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
486 : errmsg("array must be one-dimensional")));
487 4546 : if (array_contains_nulls(_query))
488 0 : ereport(ERROR,
489 : (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
490 : errmsg("array must not contain nulls")));
491 :
492 8108 : while (num > 0)
493 : {
494 6568 : if (gist_qe(key, query, siglen))
495 3006 : return true;
496 3562 : num--;
497 3562 : query = (lquery *) NEXTVAL(query);
498 : }
499 1540 : return false;
500 : }
501 :
502 : Datum
503 36378 : _ltree_consistent(PG_FUNCTION_ARGS)
504 : {
505 36378 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
506 36378 : void *query = (void *) PG_DETOAST_DATUM(PG_GETARG_DATUM(1));
507 36378 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
508 :
509 : /* Oid subtype = PG_GETARG_OID(3); */
510 36378 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
511 36378 : int siglen = LTREE_GET_ASIGLEN();
512 36378 : ltree_gist *key = (ltree_gist *) DatumGetPointer(entry->key);
513 36378 : bool res = false;
514 :
515 : /* All cases served by this function are inexact */
516 36378 : *recheck = true;
517 :
518 36378 : switch (strategy)
519 : {
520 5064 : case 10:
521 : case 11:
522 5064 : res = gist_te(key, (ltree *) query, siglen);
523 5064 : break;
524 22578 : case 12:
525 : case 13:
526 22578 : res = gist_qe(key, (lquery *) query, siglen);
527 22578 : break;
528 4190 : case 14:
529 : case 15:
530 4190 : res = gist_qtxt(key, (ltxtquery *) query, siglen);
531 4190 : break;
532 4546 : case 16:
533 : case 17:
534 4546 : res = _arrq_cons(key, (ArrayType *) query, siglen);
535 4546 : break;
536 0 : default:
537 : /* internal error */
538 0 : elog(ERROR, "unrecognized StrategyNumber: %d", strategy);
539 : }
540 36378 : PG_FREE_IF_COPY(query, 1);
541 36378 : PG_RETURN_BOOL(res);
542 : }
543 :
544 : Datum
545 18 : _ltree_gist_options(PG_FUNCTION_ARGS)
546 : {
547 18 : local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
548 :
549 18 : init_local_reloptions(relopts, sizeof(LtreeGistOptions));
550 18 : add_local_int_reloption(relopts, "siglen", "signature length",
551 : LTREE_ASIGLEN_DEFAULT, 1, LTREE_ASIGLEN_MAX,
552 : offsetof(LtreeGistOptions, siglen));
553 :
554 18 : PG_RETURN_VOID();
555 : }
|
