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