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