PostgreSQL Source Code  git master
geo_spgist.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * geo_spgist.c
4  * SP-GiST implementation of 4-dimensional quad tree over boxes
5  *
6  * This module provides SP-GiST implementation for boxes using quad tree
7  * analogy in 4-dimensional space. SP-GiST doesn't allow indexing of
8  * overlapping objects. We are making 2D objects never-overlapping in
9  * 4D space. This technique has some benefits compared to traditional
10  * R-Tree which is implemented as GiST. The performance tests reveal
11  * that this technique especially beneficial with too much overlapping
12  * objects, so called "spaghetti data".
13  *
14  * Unlike the original quad tree, we are splitting the tree into 16
15  * quadrants in 4D space. It is easier to imagine it as splitting space
16  * two times into 4:
17  *
18  * | |
19  * | |
20  * | -----+-----
21  * | |
22  * | |
23  * -------------+-------------
24  * |
25  * |
26  * |
27  * |
28  * |
29  *
30  * We are using box datatype as the prefix, but we are treating them
31  * as points in 4-dimensional space, because 2D boxes are not enough
32  * to represent the quadrant boundaries in 4D space. They however are
33  * sufficient to point out the additional boundaries of the next
34  * quadrant.
35  *
36  * We are using traversal values provided by SP-GiST to calculate and
37  * to store the bounds of the quadrants, while traversing into the tree.
38  * Traversal value has all the boundaries in the 4D space, and is is
39  * capable of transferring the required boundaries to the following
40  * traversal values. In conclusion, three things are necessary
41  * to calculate the next traversal value:
42  *
43  * (1) the traversal value of the parent
44  * (2) the quadrant of the current node
45  * (3) the prefix of the current node
46  *
47  * If we visualize them on our simplified drawing (see the drawing above);
48  * transferred boundaries of (1) would be the outer axis, relevant part
49  * of (2) would be the up right part of the other axis, and (3) would be
50  * the inner axis.
51  *
52  * For example, consider the case of overlapping. When recursion
53  * descends deeper and deeper down the tree, all quadrants in
54  * the current node will be checked for overlapping. The boundaries
55  * will be re-calculated for all quadrants. Overlap check answers
56  * the question: can any box from this quadrant overlap with the given
57  * box? If yes, then this quadrant will be walked. If no, then this
58  * quadrant will be skipped.
59  *
60  * This method provides restrictions for minimum and maximum values of
61  * every dimension of every corner of the box on every level of the tree
62  * except the root. For the root node, we are setting the boundaries
63  * that we don't yet have as infinity.
64  *
65  * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
66  * Portions Copyright (c) 1994, Regents of the University of California
67  *
68  * IDENTIFICATION
69  * src/backend/utils/adt/geo_spgist.c
70  *
71  *-------------------------------------------------------------------------
72  */
73 
74 #include "postgres.h"
75 
76 #include "access/spgist.h"
77 #include "access/stratnum.h"
78 #include "catalog/pg_type.h"
79 #include "utils/builtins.h"
80 #include "utils/geo_decls.h"
81 
82 /*
83  * Comparator for qsort
84  *
85  * We don't need to use the floating point macros in here, because this
86  * is going only going to be used in a place to effect the performance
87  * of the index, not the correctness.
88  */
89 static int
90 compareDoubles(const void *a, const void *b)
91 {
92  double x = *(double *) a;
93  double y = *(double *) b;
94 
95  if (x == y)
96  return 0;
97  return (x > y) ? 1 : -1;
98 }
99 
100 typedef struct
101 {
102  double low;
103  double high;
104 } Range;
105 
106 typedef struct
107 {
110 } RangeBox;
111 
112 typedef struct
113 {
116 } RectBox;
117 
118 /*
119  * Calculate the quadrant
120  *
121  * The quadrant is 8 bit unsigned integer with 4 least bits in use.
122  * This function accepts BOXes as input. They are not casted to
123  * RangeBoxes, yet. All 4 bits are set by comparing a corner of the box.
124  * This makes 16 quadrants in total.
125  */
126 static uint8
127 getQuadrant(BOX *centroid, BOX *inBox)
128 {
129  uint8 quadrant = 0;
130 
131  if (inBox->low.x > centroid->low.x)
132  quadrant |= 0x8;
133 
134  if (inBox->high.x > centroid->high.x)
135  quadrant |= 0x4;
136 
137  if (inBox->low.y > centroid->low.y)
138  quadrant |= 0x2;
139 
140  if (inBox->high.y > centroid->high.y)
141  quadrant |= 0x1;
142 
143  return quadrant;
144 }
145 
146 /*
147  * Get RangeBox using BOX
148  *
149  * We are turning the BOX to our structures to emphasize their function
150  * of representing points in 4D space. It also is more convenient to
151  * access the values with this structure.
152  */
153 static RangeBox *
155 {
156  RangeBox *range_box = (RangeBox *) palloc(sizeof(RangeBox));
157 
158  range_box->left.low = box->low.x;
159  range_box->left.high = box->high.x;
160 
161  range_box->right.low = box->low.y;
162  range_box->right.high = box->high.y;
163 
164  return range_box;
165 }
166 
167 /*
168  * Initialize the traversal value
169  *
170  * In the beginning, we don't have any restrictions. We have to
171  * initialize the struct to cover the whole 4D space.
172  */
173 static RectBox *
175 {
176  RectBox *rect_box = (RectBox *) palloc(sizeof(RectBox));
177  double infinity = get_float8_infinity();
178 
179  rect_box->range_box_x.left.low = -infinity;
180  rect_box->range_box_x.left.high = infinity;
181 
182  rect_box->range_box_x.right.low = -infinity;
183  rect_box->range_box_x.right.high = infinity;
184 
185  rect_box->range_box_y.left.low = -infinity;
186  rect_box->range_box_y.left.high = infinity;
187 
188  rect_box->range_box_y.right.low = -infinity;
189  rect_box->range_box_y.right.high = infinity;
190 
191  return rect_box;
192 }
193 
194 /*
195  * Calculate the next traversal value
196  *
197  * All centroids are bounded by RectBox, but SP-GiST only keeps
198  * boxes. When we are traversing the tree, we must calculate RectBox,
199  * using centroid and quadrant.
200  */
201 static RectBox *
202 nextRectBox(RectBox *rect_box, RangeBox *centroid, uint8 quadrant)
203 {
204  RectBox *next_rect_box = (RectBox *) palloc(sizeof(RectBox));
205 
206  memcpy(next_rect_box, rect_box, sizeof(RectBox));
207 
208  if (quadrant & 0x8)
209  next_rect_box->range_box_x.left.low = centroid->left.low;
210  else
211  next_rect_box->range_box_x.left.high = centroid->left.low;
212 
213  if (quadrant & 0x4)
214  next_rect_box->range_box_x.right.low = centroid->left.high;
215  else
216  next_rect_box->range_box_x.right.high = centroid->left.high;
217 
218  if (quadrant & 0x2)
219  next_rect_box->range_box_y.left.low = centroid->right.low;
220  else
221  next_rect_box->range_box_y.left.high = centroid->right.low;
222 
223  if (quadrant & 0x1)
224  next_rect_box->range_box_y.right.low = centroid->right.high;
225  else
226  next_rect_box->range_box_y.right.high = centroid->right.high;
227 
228  return next_rect_box;
229 }
230 
231 /* Can any range from range_box overlap with this argument? */
232 static bool
233 overlap2D(RangeBox *range_box, Range *query)
234 {
235  return FPge(range_box->right.high, query->low) &&
236  FPle(range_box->left.low, query->high);
237 }
238 
239 /* Can any rectangle from rect_box overlap with this argument? */
240 static bool
241 overlap4D(RectBox *rect_box, RangeBox *query)
242 {
243  return overlap2D(&rect_box->range_box_x, &query->left) &&
244  overlap2D(&rect_box->range_box_y, &query->right);
245 }
246 
247 /* Can any range from range_box contain this argument? */
248 static bool
249 contain2D(RangeBox *range_box, Range *query)
250 {
251  return FPge(range_box->right.high, query->high) &&
252  FPle(range_box->left.low, query->low);
253 }
254 
255 /* Can any rectangle from rect_box contain this argument? */
256 static bool
257 contain4D(RectBox *rect_box, RangeBox *query)
258 {
259  return contain2D(&rect_box->range_box_x, &query->left) &&
260  contain2D(&rect_box->range_box_y, &query->right);
261 }
262 
263 /* Can any range from range_box be contained by this argument? */
264 static bool
265 contained2D(RangeBox *range_box, Range *query)
266 {
267  return FPle(range_box->left.low, query->high) &&
268  FPge(range_box->left.high, query->low) &&
269  FPle(range_box->right.low, query->high) &&
270  FPge(range_box->right.high, query->low);
271 }
272 
273 /* Can any rectangle from rect_box be contained by this argument? */
274 static bool
275 contained4D(RectBox *rect_box, RangeBox *query)
276 {
277  return contained2D(&rect_box->range_box_x, &query->left) &&
278  contained2D(&rect_box->range_box_y, &query->right);
279 }
280 
281 /* Can any range from range_box to be lower than this argument? */
282 static bool
283 lower2D(RangeBox *range_box, Range *query)
284 {
285  return FPlt(range_box->left.low, query->low) &&
286  FPlt(range_box->right.low, query->low);
287 }
288 
289 /* Can any range from range_box not extend to the right side of the query? */
290 static bool
291 overLower2D(RangeBox *range_box, Range *query)
292 {
293  return FPle(range_box->left.low, query->high) &&
294  FPle(range_box->right.low, query->high);
295 }
296 
297 /* Can any range from range_box to be higher than this argument? */
298 static bool
299 higher2D(RangeBox *range_box, Range *query)
300 {
301  return FPgt(range_box->left.high, query->high) &&
302  FPgt(range_box->right.high, query->high);
303 }
304 
305 /* Can any range from range_box not extend to the left side of the query? */
306 static bool
307 overHigher2D(RangeBox *range_box, Range *query)
308 {
309  return FPge(range_box->left.high, query->low) &&
310  FPge(range_box->right.high, query->low);
311 }
312 
313 /* Can any rectangle from rect_box be left of this argument? */
314 static bool
315 left4D(RectBox *rect_box, RangeBox *query)
316 {
317  return lower2D(&rect_box->range_box_x, &query->left);
318 }
319 
320 /* Can any rectangle from rect_box does not extend the right of this argument? */
321 static bool
322 overLeft4D(RectBox *rect_box, RangeBox *query)
323 {
324  return overLower2D(&rect_box->range_box_x, &query->left);
325 }
326 
327 /* Can any rectangle from rect_box be right of this argument? */
328 static bool
329 right4D(RectBox *rect_box, RangeBox *query)
330 {
331  return higher2D(&rect_box->range_box_x, &query->left);
332 }
333 
334 /* Can any rectangle from rect_box does not extend the left of this argument? */
335 static bool
336 overRight4D(RectBox *rect_box, RangeBox *query)
337 {
338  return overHigher2D(&rect_box->range_box_x, &query->left);
339 }
340 
341 /* Can any rectangle from rect_box be below of this argument? */
342 static bool
343 below4D(RectBox *rect_box, RangeBox *query)
344 {
345  return lower2D(&rect_box->range_box_y, &query->right);
346 }
347 
348 /* Can any rectangle from rect_box does not extend above this argument? */
349 static bool
350 overBelow4D(RectBox *rect_box, RangeBox *query)
351 {
352  return overLower2D(&rect_box->range_box_y, &query->right);
353 }
354 
355 /* Can any rectangle from rect_box be above of this argument? */
356 static bool
357 above4D(RectBox *rect_box, RangeBox *query)
358 {
359  return higher2D(&rect_box->range_box_y, &query->right);
360 }
361 
362 /* Can any rectangle from rect_box does not extend below of this argument? */
363 static bool
364 overAbove4D(RectBox *rect_box, RangeBox *query)
365 {
366  return overHigher2D(&rect_box->range_box_y, &query->right);
367 }
368 
369 /*
370  * SP-GiST config function
371  */
372 Datum
374 {
376 
377  cfg->prefixType = BOXOID;
378  cfg->labelType = VOIDOID; /* We don't need node labels. */
379  cfg->canReturnData = true;
380  cfg->longValuesOK = false;
381 
382  PG_RETURN_VOID();
383 }
384 
385 /*
386  * SP-GiST choose function
387  */
388 Datum
390 {
393  BOX *centroid = DatumGetBoxP(in->prefixDatum),
394  *box = DatumGetBoxP(in->leafDatum);
395 
396  out->resultType = spgMatchNode;
397  out->result.matchNode.restDatum = BoxPGetDatum(box);
398 
399  /* nodeN will be set by core, when allTheSame. */
400  if (!in->allTheSame)
401  out->result.matchNode.nodeN = getQuadrant(centroid, box);
402 
403  PG_RETURN_VOID();
404 }
405 
406 /*
407  * SP-GiST pick-split function
408  *
409  * It splits a list of boxes into quadrants by choosing a central 4D
410  * point as the median of the coordinates of the boxes.
411  */
412 Datum
414 {
417  BOX *centroid;
418  int median,
419  i;
420  double *lowXs = palloc(sizeof(double) * in->nTuples);
421  double *highXs = palloc(sizeof(double) * in->nTuples);
422  double *lowYs = palloc(sizeof(double) * in->nTuples);
423  double *highYs = palloc(sizeof(double) * in->nTuples);
424 
425  /* Calculate median of all 4D coordinates */
426  for (i = 0; i < in->nTuples; i++)
427  {
428  BOX *box = DatumGetBoxP(in->datums[i]);
429 
430  lowXs[i] = box->low.x;
431  highXs[i] = box->high.x;
432  lowYs[i] = box->low.y;
433  highYs[i] = box->high.y;
434  }
435 
436  qsort(lowXs, in->nTuples, sizeof(double), compareDoubles);
437  qsort(highXs, in->nTuples, sizeof(double), compareDoubles);
438  qsort(lowYs, in->nTuples, sizeof(double), compareDoubles);
439  qsort(highYs, in->nTuples, sizeof(double), compareDoubles);
440 
441  median = in->nTuples / 2;
442 
443  centroid = palloc(sizeof(BOX));
444 
445  centroid->low.x = lowXs[median];
446  centroid->high.x = highXs[median];
447  centroid->low.y = lowYs[median];
448  centroid->high.y = highYs[median];
449 
450  /* Fill the output */
451  out->hasPrefix = true;
452  out->prefixDatum = BoxPGetDatum(centroid);
453 
454  out->nNodes = 16;
455  out->nodeLabels = NULL; /* We don't need node labels. */
456 
457  out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
458  out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
459 
460  /*
461  * Assign ranges to corresponding nodes according to quadrants relative to
462  * the "centroid" range
463  */
464  for (i = 0; i < in->nTuples; i++)
465  {
466  BOX *box = DatumGetBoxP(in->datums[i]);
467  uint8 quadrant = getQuadrant(centroid, box);
468 
469  out->leafTupleDatums[i] = BoxPGetDatum(box);
470  out->mapTuplesToNodes[i] = quadrant;
471  }
472 
473  PG_RETURN_VOID();
474 }
475 
476 /*
477  * Check if result of consistent method based on bounding box is exact.
478  */
479 static bool
481 {
482  switch (strategy)
483  {
492  return true;
493 
494  default:
495  return false;
496  }
497 }
498 
499 /*
500  * Get bounding box for ScanKey.
501  */
502 static BOX *
504 {
505  switch (sk->sk_subtype)
506  {
507  case BOXOID:
508  return DatumGetBoxP(sk->sk_argument);
509 
510  case POLYGONOID:
511  if (recheck && !is_bounding_box_test_exact(sk->sk_strategy))
512  *recheck = true;
513  return &DatumGetPolygonP(sk->sk_argument)->boundbox;
514 
515  default:
516  elog(ERROR, "unrecognized scankey subtype: %d", sk->sk_subtype);
517  return NULL;
518  }
519 }
520 
521 /*
522  * SP-GiST inner consistent function
523  */
524 Datum
526 {
529  int i;
530  MemoryContext old_ctx;
531  RectBox *rect_box;
532  uint8 quadrant;
533  RangeBox *centroid,
534  **queries;
535 
536  if (in->allTheSame)
537  {
538  /* Report that all nodes should be visited */
539  out->nNodes = in->nNodes;
540  out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
541  for (i = 0; i < in->nNodes; i++)
542  out->nodeNumbers[i] = i;
543 
544  PG_RETURN_VOID();
545  }
546 
547  /*
548  * We are saving the traversal value or initialize it an unbounded one, if
549  * we have just begun to walk the tree.
550  */
551  if (in->traversalValue)
552  rect_box = in->traversalValue;
553  else
554  rect_box = initRectBox();
555 
556  /*
557  * We are casting the prefix and queries to RangeBoxes for ease of the
558  * following operations.
559  */
560  centroid = getRangeBox(DatumGetBoxP(in->prefixDatum));
561  queries = (RangeBox **) palloc(in->nkeys * sizeof(RangeBox *));
562  for (i = 0; i < in->nkeys; i++)
563  {
564  BOX *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i], NULL);
565 
566  queries[i] = getRangeBox(box);
567  }
568 
569  /* Allocate enough memory for nodes */
570  out->nNodes = 0;
571  out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
572  out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
573 
574  /*
575  * We switch memory context, because we want to allocate memory for new
576  * traversal values (next_rect_box) and pass these pieces of memory to
577  * further call of this function.
578  */
580 
581  for (quadrant = 0; quadrant < in->nNodes; quadrant++)
582  {
583  RectBox *next_rect_box = nextRectBox(rect_box, centroid, quadrant);
584  bool flag = true;
585 
586  for (i = 0; i < in->nkeys; i++)
587  {
588  StrategyNumber strategy = in->scankeys[i].sk_strategy;
589 
590  switch (strategy)
591  {
593  flag = overlap4D(next_rect_box, queries[i]);
594  break;
595 
597  flag = contain4D(next_rect_box, queries[i]);
598  break;
599 
602  flag = contained4D(next_rect_box, queries[i]);
603  break;
604 
606  flag = left4D(next_rect_box, queries[i]);
607  break;
608 
610  flag = overLeft4D(next_rect_box, queries[i]);
611  break;
612 
614  flag = right4D(next_rect_box, queries[i]);
615  break;
616 
618  flag = overRight4D(next_rect_box, queries[i]);
619  break;
620 
622  flag = above4D(next_rect_box, queries[i]);
623  break;
624 
626  flag = overAbove4D(next_rect_box, queries[i]);
627  break;
628 
630  flag = below4D(next_rect_box, queries[i]);
631  break;
632 
634  flag = overBelow4D(next_rect_box, queries[i]);
635  break;
636 
637  default:
638  elog(ERROR, "unrecognized strategy: %d", strategy);
639  }
640 
641  /* If any check is failed, we have found our answer. */
642  if (!flag)
643  break;
644  }
645 
646  if (flag)
647  {
648  out->traversalValues[out->nNodes] = next_rect_box;
649  out->nodeNumbers[out->nNodes] = quadrant;
650  out->nNodes++;
651  }
652  else
653  {
654  /*
655  * If this node is not selected, we don't need to keep the next
656  * traversal value in the memory context.
657  */
658  pfree(next_rect_box);
659  }
660  }
661 
662  /* Switch back */
663  MemoryContextSwitchTo(old_ctx);
664 
665  PG_RETURN_VOID();
666 }
667 
668 /*
669  * SP-GiST inner consistent function
670  */
671 Datum
673 {
676  Datum leaf = in->leafDatum;
677  bool flag = true;
678  int i;
679 
680  /* All tests are exact. */
681  out->recheck = false;
682 
683  /* leafDatum is what it is... */
684  out->leafValue = in->leafDatum;
685 
686  /* Perform the required comparison(s) */
687  for (i = 0; i < in->nkeys; i++)
688  {
689  StrategyNumber strategy = in->scankeys[i].sk_strategy;
691  &out->recheck);
692  Datum query = BoxPGetDatum(box);
693 
694  switch (strategy)
695  {
698  query));
699  break;
700 
703  query));
704  break;
705 
708  query));
709  break;
710 
713  query));
714  break;
715 
718  query));
719  break;
720 
723  query));
724  break;
725 
728  query));
729  break;
730 
733  query));
734  break;
735 
738  query));
739  break;
740 
743  query));
744  break;
745 
748  query));
749  break;
750 
753  query));
754  break;
755 
756  default:
757  elog(ERROR, "unrecognized strategy: %d", strategy);
758  }
759 
760  /* If any check is failed, we have found our answer. */
761  if (!flag)
762  break;
763  }
764 
765  PG_RETURN_BOOL(flag);
766 }
767 
768 
769 /*
770  * SP-GiST config function for 2-D types that are lossy represented by their
771  * bounding boxes
772  */
773 Datum
775 {
777 
778  cfg->prefixType = BOXOID; /* A type represented by its bounding box */
779  cfg->labelType = VOIDOID; /* We don't need node labels. */
780  cfg->leafType = BOXOID;
781  cfg->canReturnData = false;
782  cfg->longValuesOK = false;
783 
784  PG_RETURN_VOID();
785 }
786 
787 /*
788  * SP-GiST compress function for polygons
789  */
790 Datum
792 {
793  POLYGON *polygon = PG_GETARG_POLYGON_P(0);
794  BOX *box;
795 
796  box = box_copy(&polygon->boundbox);
797 
798  PG_RETURN_BOX_P(box);
799 }
static bool overHigher2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:307
Datum box_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:563
Datum box_contained(PG_FUNCTION_ARGS)
Definition: geo_ops.c:635
Oid sk_subtype
Definition: skey.h:69
static bool contained2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:265
static bool overAbove4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:364
Datum box_same(PG_FUNCTION_ARGS)
Definition: geo_ops.c:503
Definition: geo_decls.h:102
Datum box_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:537
static bool overBelow4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:350
bool canReturnData
Definition: spgist.h:50
static bool contain4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:257
Datum * leafTupleDatums
Definition: spgist.h:130
#define RTLeftStrategyNumber
Definition: stratnum.h:44
Datum * datums
Definition: spgist.h:117
struct spgChooseOut::@48::@49 matchNode
Datum box_overright(PG_FUNCTION_ARGS)
Definition: geo_ops.c:578
Datum spg_box_quad_picksplit(PG_FUNCTION_ARGS)
Definition: geo_spgist.c:413
Datum spg_box_quad_config(PG_FUNCTION_ARGS)
Definition: geo_spgist.c:373
Datum spg_bbox_quad_config(PG_FUNCTION_ARGS)
Definition: geo_spgist.c:774
double y
Definition: geo_decls.h:60
Datum box_overlap(PG_FUNCTION_ARGS)
Definition: geo_ops.c:517
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
unsigned char uint8
Definition: c.h:323
void * traversalValue
Definition: spgist.h:142
#define RTOverBelowStrategyNumber
Definition: stratnum.h:52
static bool overRight4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:336
Datum prefixDatum
Definition: spgist.h:66
static bool lower2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:283
uint16 StrategyNumber
Definition: stratnum.h:22
#define RTContainedByStrategyNumber
Definition: stratnum.h:51
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:246
static bool left4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:315
#define RTBelowStrategyNumber
Definition: stratnum.h:53
RangeBox range_box_y
Definition: geo_spgist.c:115
#define PG_GETARG_POLYGON_P(n)
Definition: geo_decls.h:167
Range right
Definition: geo_spgist.c:109
static bool overLower2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:291
double x
Definition: geo_decls.h:60
RangeBox range_box_x
Definition: geo_spgist.c:114
static bool is_bounding_box_test_exact(StrategyNumber strategy)
Definition: geo_spgist.c:480
#define RTOverAboveStrategyNumber
Definition: stratnum.h:55
#define FPgt(A, B)
Definition: geo_decls.h:41
static bool below4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:343
void pfree(void *pointer)
Definition: mcxt.c:1031
static bool overlap4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:241
MemoryContext traversalMemoryContext
Definition: spgist.h:143
#define ERROR
Definition: elog.h:43
Datum spg_box_quad_inner_consistent(PG_FUNCTION_ARGS)
Definition: geo_spgist.c:525
BOX * box_copy(BOX *box)
Definition: geo_ops.c:485
Datum * nodeLabels
Definition: spgist.h:127
StrategyNumber sk_strategy
Definition: skey.h:68
ScanKey scankeys
Definition: spgist.h:169
Datum box_contain(PG_FUNCTION_ARGS)
Definition: geo_ops.c:649
Datum box_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:612
char * flag(int b)
Definition: test-ctype.c:33
static bool contain2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:249
#define DatumGetBool(X)
Definition: postgres.h:376
#define RTSameStrategyNumber
Definition: stratnum.h:49
#define RTOverRightStrategyNumber
Definition: stratnum.h:47
void ** traversalValues
Definition: spgist.h:161
double low
Definition: geo_spgist.c:102
double get_float8_infinity(void)
Definition: float.c:118
static bool above4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:357
Point low
Definition: geo_decls.h:104
#define RTOverLeftStrategyNumber
Definition: stratnum.h:45
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:324
bool longValuesOK
Definition: spgist.h:51
uintptr_t Datum
Definition: postgres.h:365
Datum spg_box_quad_leaf_consistent(PG_FUNCTION_ARGS)
Definition: geo_spgist.c:672
static RectBox * initRectBox(void)
Definition: geo_spgist.c:174
Datum spg_box_quad_choose(PG_FUNCTION_ARGS)
Definition: geo_spgist.c:389
Oid prefixType
Definition: spgist.h:47
Datum box_overbelow(PG_FUNCTION_ARGS)
Definition: geo_ops.c:601
spgChooseResultType resultType
Definition: spgist.h:80
#define PG_RETURN_BOX_P(x)
Definition: geo_decls.h:162
#define BoxPGetDatum(X)
Definition: geo_decls.h:160
BOX boundbox
Definition: geo_decls.h:117
#define PG_RETURN_VOID()
Definition: fmgr.h:314
Datum box_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:589
#define RTAboveStrategyNumber
Definition: stratnum.h:54
#define FPlt(A, B)
Definition: geo_decls.h:39
double high
Definition: geo_spgist.c:103
Datum leafDatum
Definition: spgist.h:60
#define RTRightStrategyNumber
Definition: stratnum.h:48
bool hasPrefix
Definition: spgist.h:123
Datum box_overleft(PG_FUNCTION_ARGS)
Definition: geo_ops.c:552
static bool contained4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:275
#define RTContainsStrategyNumber
Definition: stratnum.h:50
union spgChooseOut::@48 result
ScanKey scankeys
Definition: spgist.h:138
#define DatumGetBoxP(X)
Definition: geo_decls.h:159
Point high
Definition: geo_decls.h:104
#define DatumGetPolygonP(X)
Definition: geo_decls.h:164
static uint8 getQuadrant(BOX *centroid, BOX *inBox)
Definition: geo_spgist.c:127
static bool overlap2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:233
void * palloc(Size size)
Definition: mcxt.c:924
#define FPge(A, B)
Definition: geo_decls.h:42
static BOX * spg_box_quad_get_scankey_bbox(ScanKey sk, bool *recheck)
Definition: geo_spgist.c:503
static bool overLeft4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:322
Oid labelType
Definition: spgist.h:48
int i
int * mapTuplesToNodes
Definition: spgist.h:129
static int compareDoubles(const void *a, const void *b)
Definition: geo_spgist.c:90
Oid leafType
Definition: spgist.h:49
bool allTheSame
Definition: spgist.h:64
Datum prefixDatum
Definition: spgist.h:124
#define RTOverlapStrategyNumber
Definition: stratnum.h:46
#define PG_FUNCTION_ARGS
Definition: fmgr.h:163
Datum box_overabove(PG_FUNCTION_ARGS)
Definition: geo_ops.c:624
#define elog
Definition: elog.h:219
#define FPle(A, B)
Definition: geo_decls.h:40
#define qsort(a, b, c, d)
Definition: port.h:421
static bool right4D(RectBox *rect_box, RangeBox *query)
Definition: geo_spgist.c:329
static RangeBox * getRangeBox(BOX *box)
Definition: geo_spgist.c:154
Datum spg_poly_quad_compress(PG_FUNCTION_ARGS)
Definition: geo_spgist.c:791
Datum sk_argument
Definition: skey.h:72
Range left
Definition: geo_spgist.c:108
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:592
static bool higher2D(RangeBox *range_box, Range *query)
Definition: geo_spgist.c:299
static RectBox * nextRectBox(RectBox *rect_box, RangeBox *centroid, uint8 quadrant)
Definition: geo_spgist.c:202