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