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