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 11688 : _ltree_compress(PG_FUNCTION_ARGS)
49 : {
50 11688 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
51 11688 : GISTENTRY *retval = entry;
52 11688 : int siglen = LTREE_GET_ASIGLEN();
53 :
54 11688 : 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 7688 : else if (!LTG_ISALLTRUE(entry->key))
85 : {
86 : int32 i;
87 : ltree_gist *key;
88 7688 : BITVECP sign = LTG_SIGN(DatumGetPointer(entry->key));
89 :
90 7688 : ALOOPBYTE(siglen)
91 : {
92 7688 : if ((sign[i] & 0xff) != 0xff)
93 7688 : 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 16352 : _ltree_same(PG_FUNCTION_ARGS)
107 : {
108 16352 : ltree_gist *a = (ltree_gist *) PG_GETARG_POINTER(0);
109 16352 : ltree_gist *b = (ltree_gist *) PG_GETARG_POINTER(1);
110 16352 : bool *result = (bool *) PG_GETARG_POINTER(2);
111 16352 : int siglen = LTREE_GET_ASIGLEN();
112 :
113 16352 : if (LTG_ISALLTRUE(a) && LTG_ISALLTRUE(b))
114 0 : *result = true;
115 16352 : else if (LTG_ISALLTRUE(a))
116 0 : *result = false;
117 16352 : else if (LTG_ISALLTRUE(b))
118 0 : *result = false;
119 : else
120 : {
121 : int32 i;
122 16352 : BITVECP sa = LTG_SIGN(a),
123 16352 : sb = LTG_SIGN(b);
124 :
125 16352 : *result = true;
126 23892286 : ALOOPBYTE(siglen)
127 : {
128 23880062 : if (sa[i] != sb[i])
129 : {
130 4128 : *result = false;
131 4128 : break;
132 : }
133 : }
134 : }
135 16352 : PG_RETURN_POINTER(result);
136 : }
137 :
138 : static int32
139 32704 : unionkey(BITVECP sbase, ltree_gist *add, int siglen)
140 : {
141 : int32 i;
142 32704 : BITVECP sadd = LTG_SIGN(add);
143 :
144 32704 : if (LTG_ISALLTRUE(add))
145 0 : return 1;
146 :
147 59367344 : ALOOPBYTE(siglen)
148 59334640 : sbase[i] |= sadd[i];
149 32704 : return 0;
150 : }
151 :
152 : Datum
153 16352 : _ltree_union(PG_FUNCTION_ARGS)
154 : {
155 16352 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
156 16352 : int *size = (int *) PG_GETARG_POINTER(1);
157 16352 : int siglen = LTREE_GET_ASIGLEN();
158 : int32 i;
159 16352 : ltree_gist *result = ltree_gist_alloc(false, NULL, siglen, NULL, NULL);
160 16352 : BITVECP base = LTG_SIGN(result);
161 :
162 49056 : for (i = 0; i < entryvec->n; i++)
163 : {
164 32704 : 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 16352 : *size = VARSIZE(result);
173 :
174 16352 : 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 250758 : hemdistsign(BITVECP a, BITVECP b, int siglen)
185 : {
186 : int i,
187 : diff,
188 250758 : dist = 0;
189 :
190 118381318 : ALOOPBYTE(siglen)
191 : {
192 118130560 : diff = (unsigned char) (a[i] ^ b[i]);
193 : /* Using the popcount functions here isn't likely to win */
194 118130560 : dist += pg_number_of_ones[diff];
195 : }
196 250758 : return dist;
197 : }
198 :
199 : static int
200 250758 : hemdist(ltree_gist *a, ltree_gist *b, int siglen)
201 : {
202 250758 : 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 250758 : else if (LTG_ISALLTRUE(b))
210 0 : return ASIGLENBIT(siglen) - sizebitvec(LTG_SIGN(a), siglen);
211 :
212 250758 : return hemdistsign(LTG_SIGN(a), LTG_SIGN(b), siglen);
213 : }
214 :
215 :
216 : Datum
217 39108 : _ltree_penalty(PG_FUNCTION_ARGS)
218 : {
219 39108 : ltree_gist *origval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(0))->key);
220 39108 : ltree_gist *newval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(1))->key);
221 39108 : float *penalty = (float *) PG_GETARG_POINTER(2);
222 39108 : int siglen = LTREE_GET_ASIGLEN();
223 :
224 39108 : *penalty = hemdist(origval, newval, siglen);
225 39108 : PG_RETURN_POINTER(penalty);
226 : }
227 :
228 : typedef struct
229 : {
230 : OffsetNumber pos;
231 : int32 cost;
232 : } SPLITCOST;
233 :
234 : static int
235 15976 : comparecost(const void *a, const void *b)
236 : {
237 15976 : return ((const SPLITCOST *) a)->cost - ((const SPLITCOST *) b)->cost;
238 : }
239 :
240 : Datum
241 1780 : _ltree_picksplit(PG_FUNCTION_ARGS)
242 : {
243 1780 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
244 1780 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
245 1780 : 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 1780 : waste = -1;
256 : int32 nbytes;
257 1780 : OffsetNumber seed_1 = 0,
258 1780 : 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 1780 : maxoff = entryvec->n - 2;
269 1780 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
270 1780 : v->spl_left = (OffsetNumber *) palloc(nbytes);
271 1780 : v->spl_right = (OffsetNumber *) palloc(nbytes);
272 :
273 7806 : for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
274 : {
275 6026 : _k = GETENTRY(entryvec, k);
276 186452 : for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
277 : {
278 180426 : size_waste = hemdist(_k, GETENTRY(entryvec, j), siglen);
279 180426 : if (size_waste > waste)
280 : {
281 3266 : waste = size_waste;
282 3266 : seed_1 = k;
283 3266 : seed_2 = j;
284 : }
285 : }
286 : }
287 :
288 1780 : left = v->spl_left;
289 1780 : v->spl_nleft = 0;
290 1780 : right = v->spl_right;
291 1780 : v->spl_nright = 0;
292 :
293 1780 : if (seed_1 == 0 || seed_2 == 0)
294 : {
295 0 : seed_1 = 1;
296 0 : seed_2 = 2;
297 : }
298 :
299 : /* form initial .. */
300 1780 : datum_l = ltree_gist_alloc(LTG_ISALLTRUE(GETENTRY(entryvec, seed_1)),
301 1780 : LTG_SIGN(GETENTRY(entryvec, seed_1)),
302 : siglen, NULL, NULL);
303 :
304 1780 : datum_r = ltree_gist_alloc(LTG_ISALLTRUE(GETENTRY(entryvec, seed_2)),
305 1780 : LTG_SIGN(GETENTRY(entryvec, seed_2)),
306 : siglen, NULL, NULL);
307 :
308 1780 : maxoff = OffsetNumberNext(maxoff);
309 : /* sort before ... */
310 1780 : costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
311 11366 : for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
312 : {
313 9586 : costvector[j - 1].pos = j;
314 9586 : _j = GETENTRY(entryvec, j);
315 9586 : size_alpha = hemdist(datum_l, _j, siglen);
316 9586 : size_beta = hemdist(datum_r, _j, siglen);
317 9586 : costvector[j - 1].cost = Abs(size_alpha - size_beta);
318 : }
319 1780 : qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
320 :
321 1780 : union_l = LTG_SIGN(datum_l);
322 1780 : union_r = LTG_SIGN(datum_r);
323 :
324 11366 : for (k = 0; k < maxoff; k++)
325 : {
326 9586 : j = costvector[k].pos;
327 9586 : if (j == seed_1)
328 : {
329 1780 : *left++ = j;
330 1780 : v->spl_nleft++;
331 1780 : continue;
332 : }
333 7806 : else if (j == seed_2)
334 : {
335 1780 : *right++ = j;
336 1780 : v->spl_nright++;
337 1780 : continue;
338 : }
339 6026 : _j = GETENTRY(entryvec, j);
340 6026 : size_alpha = hemdist(datum_l, _j, siglen);
341 6026 : size_beta = hemdist(datum_r, _j, siglen);
342 :
343 6026 : if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.00001))
344 : {
345 2958 : 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 2958 : ptr = LTG_SIGN(_j);
353 3327286 : ALOOPBYTE(siglen)
354 3324328 : union_l[i] |= ptr[i];
355 : }
356 2958 : *left++ = j;
357 2958 : v->spl_nleft++;
358 : }
359 : else
360 : {
361 3068 : 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 3068 : ptr = LTG_SIGN(_j);
369 3881372 : ALOOPBYTE(siglen)
370 3878304 : union_r[i] |= ptr[i];
371 : }
372 3068 : *right++ = j;
373 3068 : v->spl_nright++;
374 : }
375 : }
376 :
377 1780 : *right = *left = FirstOffsetNumber;
378 :
379 1780 : v->spl_ldatum = PointerGetDatum(datum_l);
380 1780 : v->spl_rdatum = PointerGetDatum(datum_r);
381 :
382 1780 : PG_RETURN_POINTER(v);
383 : }
384 :
385 : static bool
386 5102 : gist_te(ltree_gist *key, ltree *query, int siglen)
387 : {
388 5102 : ltree_level *curq = LTREE_FIRST(query);
389 5102 : BITVECP sign = LTG_SIGN(key);
390 5102 : int qlen = query->numlevel;
391 : unsigned int hv;
392 :
393 5102 : if (LTG_ISALLTRUE(key))
394 0 : return true;
395 :
396 17168 : while (qlen > 0)
397 : {
398 13146 : hv = ltree_crc32_sz(curq->name, curq->len);
399 13146 : if (!GETBIT(sign, AHASHVAL(hv, siglen)))
400 1080 : return false;
401 12066 : curq = LEVEL_NEXT(curq);
402 12066 : qlen--;
403 : }
404 :
405 4022 : return true;
406 : }
407 :
408 : typedef struct LtreeSignature
409 : {
410 : BITVECP sign;
411 : int siglen;
412 : } LtreeSignature;
413 :
414 : static bool
415 7462 : checkcondition_bit(void *cxt, ITEM *val)
416 : {
417 7462 : LtreeSignature *sig = cxt;
418 :
419 7462 : return (FLG_CANLOOKSIGN(val->flag)) ? GETBIT(sig->sign, AHASHVAL(val->val, sig->siglen)) : true;
420 : }
421 :
422 : static bool
423 4454 : gist_qtxt(ltree_gist *key, ltxtquery *query, int siglen)
424 : {
425 : LtreeSignature sig;
426 :
427 4454 : if (LTG_ISALLTRUE(key))
428 0 : return true;
429 :
430 4454 : sig.sign = LTG_SIGN(key);
431 4454 : sig.siglen = siglen;
432 :
433 4454 : return ltree_execute(GETQUERY(query),
434 : &sig, false,
435 : checkcondition_bit);
436 : }
437 :
438 : static bool
439 30388 : gist_qe(ltree_gist *key, lquery *query, int siglen)
440 : {
441 30388 : lquery_level *curq = LQUERY_FIRST(query);
442 30388 : BITVECP sign = LTG_SIGN(key);
443 30388 : int qlen = query->numlevel;
444 :
445 30388 : if (LTG_ISALLTRUE(key))
446 0 : return true;
447 :
448 91488 : while (qlen > 0)
449 : {
450 73360 : if (curq->numvar && LQL_CANLOOKSIGN(curq))
451 : {
452 51334 : bool isexist = false;
453 51334 : int vlen = curq->numvar;
454 51334 : lquery_variant *curv = LQL_FIRST(curq);
455 :
456 63594 : while (vlen > 0)
457 : {
458 51334 : if (GETBIT(sign, AHASHVAL(curv->val, siglen)))
459 : {
460 39074 : isexist = true;
461 39074 : break;
462 : }
463 12260 : curv = LVAR_NEXT(curv);
464 12260 : vlen--;
465 : }
466 51334 : if (!isexist)
467 12260 : return false;
468 : }
469 :
470 61100 : curq = LQL_NEXT(curq);
471 61100 : qlen--;
472 : }
473 :
474 18128 : return true;
475 : }
476 :
477 : static bool
478 4804 : _arrq_cons(ltree_gist *key, ArrayType *_query, int siglen)
479 : {
480 4804 : lquery *query = (lquery *) ARR_DATA_PTR(_query);
481 4804 : int num = ArrayGetNItems(ARR_NDIM(_query), ARR_DIMS(_query));
482 :
483 4804 : if (ARR_NDIM(_query) > 1)
484 0 : ereport(ERROR,
485 : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
486 : errmsg("array must be one-dimensional")));
487 4804 : 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 8910 : while (num > 0)
493 : {
494 7102 : if (gist_qe(key, query, siglen))
495 2996 : return true;
496 4106 : num--;
497 4106 : query = (lquery *) NEXTVAL(query);
498 : }
499 1808 : return false;
500 : }
501 :
502 : Datum
503 37646 : _ltree_consistent(PG_FUNCTION_ARGS)
504 : {
505 37646 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
506 37646 : void *query = (void *) PG_DETOAST_DATUM(PG_GETARG_DATUM(1));
507 37646 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
508 :
509 : /* Oid subtype = PG_GETARG_OID(3); */
510 37646 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
511 37646 : int siglen = LTREE_GET_ASIGLEN();
512 37646 : ltree_gist *key = (ltree_gist *) DatumGetPointer(entry->key);
513 37646 : bool res = false;
514 :
515 : /* All cases served by this function are inexact */
516 37646 : *recheck = true;
517 :
518 37646 : switch (strategy)
519 : {
520 5102 : case 10:
521 : case 11:
522 5102 : res = gist_te(key, (ltree *) query, siglen);
523 5102 : break;
524 23286 : case 12:
525 : case 13:
526 23286 : res = gist_qe(key, (lquery *) query, siglen);
527 23286 : break;
528 4454 : case 14:
529 : case 15:
530 4454 : res = gist_qtxt(key, (ltxtquery *) query, siglen);
531 4454 : break;
532 4804 : case 16:
533 : case 17:
534 4804 : res = _arrq_cons(key, (ArrayType *) query, siglen);
535 4804 : break;
536 0 : default:
537 : /* internal error */
538 0 : elog(ERROR, "unrecognized StrategyNumber: %d", strategy);
539 : }
540 37646 : PG_FREE_IF_COPY(query, 1);
541 37646 : 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 : }
|
