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