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