PostgreSQL Source Code: src/backend/access/gist/gistproc.c Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
19
20#include <math.h>
21
25#include "utils/fmgrprotos.h"
28
29
34
41
42
43
44#define LIMIT_RATIO 0.3
45
46
47
48
49
50
51
52
53
54static void
56{
61}
62
63
64
65
66
69{
70
71
72
73
74
75
76
79 return 0.0;
80
81
82
83
84
85
86 if (isnan(box->high.x) || isnan(box->high.y))
90}
91
92
93
94
95
98{
99 BOX unionbox;
100
103}
104
105
106
107
108
109
110
111
114{
118
119
121
122
123 *recheck = false;
124
127
128
129
130
131
134 query,
135 strategy));
136 else
138 query,
139 strategy));
140}
141
142
143
144
145static void
147{
149 b->high.x = addon->high.x;
153 b->high.y = addon->high.y;
156}
157
158
159
160
161
162
165{
168 int numranges,
169 i;
171 *pageunion;
172
173 numranges = entryvec->n;
176 memcpy(pageunion, cur, sizeof(BOX));
177
178 for (i = 1; i < numranges; i++)
179 {
182 }
183 *sizep = sizeof(BOX);
184
186}
187
188
189
190
191
192
193
194
195
196
197
200{
206
207 *result = (float) box_penalty(origbox, newbox);
209}
210
211
212
213
214
215static void
217{
219 maxoff;
220 BOX *unionL = NULL,
221 *unionR = NULL;
222 int nbytes;
223
224 maxoff = entryvec->n - 1;
225
226 nbytes = (maxoff + 2) * sizeof(OffsetNumber);
230
232 {
234
236 {
238 if (unionL == NULL)
239 {
241 *unionL = *cur;
242 }
243 else
245
247 }
248 else
249 {
251 if (unionR == NULL)
252 {
254 *unionR = *cur;
255 }
256 else
258
260 }
261 }
262
265}
266
267
268
269
270
271typedef struct
272{
273
275
278
279
280
281
282
283typedef struct
284{
285 int entriesCount;
287
288
289
291
294
299
301
302
303
304
305typedef struct
306{
310
311
312
313
314static int
316{
319
321}
322
323
324
325
326static int
328{
331
333}
334
335
336
337
338static inline float
340{
341 if (val >= 0.0f)
342 return val;
343 else
344 return 0.0f;
345}
346
347
348
349
350static inline void
352 float8 rightLower, int minLeftCount,
353 float8 leftUpper, int maxLeftCount)
354{
355 int leftCount,
356 rightCount;
358 overlap;
360
361
362
363
364
365 if (minLeftCount >= (context->entriesCount + 1) / 2)
366 {
367 leftCount = minLeftCount;
368 }
369 else
370 {
371 if (maxLeftCount <= context->entriesCount / 2)
372 leftCount = maxLeftCount;
373 else
375 }
376 rightCount = context->entriesCount - leftCount;
377
378
379
380
381
383
385 {
386 bool selectthis = false;
387
388
389
390
391
392
393
394
395 if (dimNum == 0)
398 else
401
403
404
405 if (context->first)
406 selectthis = true;
407 else if (context->dim == dimNum)
408 {
409
410
411
412
413 if (overlap < context->overlap ||
414 (overlap == context->overlap && ratio > context->ratio))
415 selectthis = true;
416 }
417 else
418 {
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
439 selectthis = true;
440 }
441
442 if (selectthis)
443 {
444
445 context->first = false;
446 context->ratio = ratio;
448 context->overlap = overlap;
451 context->dim = dimNum;
452 }
453 }
454}
455
456
457
458
459static int
461{
463 delta2 = ((const CommonEntry *) i2)->delta;
464
466}
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
496{
500 maxoff;
502 BOX *box,
503 *leftBox,
504 *rightBox;
505 int dim,
506 commonEntriesCount;
508 *intervalsUpper;
510 int nentries;
511
513
514 maxoff = entryvec->n - 1;
516
517
520
521
522
523
525 {
529 else
531 }
532
533
534
535
536 context.first = true;
537 for (dim = 0; dim < 2; dim++)
538 {
540 rightLower;
541 int i1,
542 i2;
543
544
546 {
548 if (dim == 0)
549 {
552 }
553 else
554 {
557 }
558 }
559
560
561
562
563
564 memcpy(intervalsUpper, intervalsLower,
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605 i1 = 0;
606 i2 = 0;
607 rightLower = intervalsLower[i1].lower;
608 leftUpper = intervalsUpper[i2].lower;
609 while (true)
610 {
611
612
613
614 while (i1 < nentries &&
616 {
618 leftUpper = intervalsLower[i1].upper;
619 i1++;
620 }
621 if (i1 >= nentries)
622 break;
623 rightLower = intervalsLower[i1].lower;
624
625
626
627
628
629 while (i2 < nentries &&
631 i2++;
632
633
634
635
637 }
638
639
640
641
642
643 i1 = nentries - 1;
644 i2 = nentries - 1;
645 rightLower = intervalsLower[i1].upper;
646 leftUpper = intervalsUpper[i2].upper;
647 while (true)
648 {
649
650
651
652 while (i2 >= 0 && float8_eq(leftUpper, intervalsUpper[i2].upper))
653 {
655 rightLower = intervalsUpper[i2].lower;
656 i2--;
657 }
658 if (i2 < 0)
659 break;
660 leftUpper = intervalsUpper[i2].upper;
661
662
663
664
665
666 while (i1 >= 0 && float8_ge(intervalsLower[i1].lower, rightLower))
667 i1--;
668
669
670
671
673 rightLower, i1 + 1, leftUpper, i2 + 1);
674 }
675 }
676
677
678
679
680 if (context.first)
681 {
684 }
685
686
687
688
689
690
691
692
693
694
699
700
703
704
705
706
707
708 commonEntriesCount = 0;
710
711
712#define PLACE_LEFT(box, off) \
713 do { \
714 if (v->spl_nleft > 0) \
715 adjustBox(leftBox, box); \
716 else \
717 *leftBox = *(box); \
718 v->spl_left[v->spl_nleft++] = off; \
719 } while(0)
720
721#define PLACE_RIGHT(box, off) \
722 do { \
723 if (v->spl_nright > 0) \
724 adjustBox(rightBox, box); \
725 else \
726 *rightBox = *(box); \
727 v->spl_right[v->spl_nright++] = off; \
728 } while(0)
729
730
731
732
733
735 {
738
739
740
741
743 if (context.dim == 0)
744 {
747 }
748 else
749 {
752 }
753
755 {
756
758 {
759
760 commonEntries[commonEntriesCount++].index = i;
761 }
762 else
763 {
764
766 }
767 }
768 else
769 {
770
771
772
773
774
776
777
779 }
780 }
781
782
783
784
785 if (commonEntriesCount > 0)
786 {
787
788
789
790
792
793
794
795
796
797 for (i = 0; i < commonEntriesCount; i++)
798 {
802 }
803
804
805
806
807
809
810
811
812
813 for (i = 0; i < commonEntriesCount; i++)
814 {
816
817
818
819
820
821 if (v->spl_nleft + (commonEntriesCount - i) <= m)
823 else if (v->spl_nright + (commonEntriesCount - i) <= m)
825 else
826 {
827
830 else
832 }
833 }
834 }
835
839}
840
841
842
843
844
845
846
847
848
849
850
853{
857
858 if (b1 && b2)
863 else
864 *result = (b1 == NULL && b2 == NULL);
866}
867
868
869
870
871static bool
873{
874 bool retval;
875
876 switch (strategy)
877 {
882 break;
887 break;
892 break;
897 break;
902 break;
907 break;
912 break;
917 break;
922 break;
927 break;
932 break;
937 break;
938 default:
939 elog(ERROR, "unrecognized strategy number: %d", strategy);
940 retval = false;
941 break;
942 }
943 return retval;
944}
945
946
947
948
949
950
951
952
953
954
955
956static bool
958{
959 bool retval;
960
961 switch (strategy)
962 {
967 break;
972 break;
977 break;
982 break;
987 break;
993 break;
998 break;
1003 break;
1008 break;
1013 break;
1018 break;
1019 default:
1020 elog(ERROR, "unrecognized strategy number: %d", strategy);
1021 retval = false;
1022 break;
1023 }
1024 return retval;
1025}
1026
1027
1028
1029
1030
1031
1032
1033
1036{
1039
1041 {
1044
1046 memcpy(r, &(in->boundbox), sizeof(BOX));
1047
1051 entry->offset, false);
1052 }
1053 else
1054 retval = entry;
1056}
1057
1058
1059
1060
1063{
1067
1068
1070 bool result;
1071
1072
1073 *recheck = true;
1074
1077
1078
1079
1080
1081
1082
1084 &(query->boundbox), strategy);
1085
1086
1088
1090}
1091
1092
1093
1094
1095
1096
1097
1098
1101{
1104
1106 {
1109
1115
1119 entry->offset, false);
1120 }
1121 else
1122 retval = entry;
1124}
1125
1126
1127
1128
1131{
1135
1136
1138 BOX bbox;
1139 bool result;
1140
1141
1142 *recheck = true;
1143
1146
1147
1148
1149
1150
1151
1156
1158 &bbox, strategy);
1159
1161}
1162
1163
1164
1165
1166
1169{
1171
1172 if (entry->leafkey)
1173 {
1177
1178 box->high = box->low = *point;
1179
1182
1184 }
1185
1187}
1188
1189
1190
1191
1192
1193
1194
1197{
1202
1204
1210 entry->offset, false);
1211
1213}
1214
1215
1216#define point_point_distance(p1,p2) \
1217 DatumGetFloat8(DirectFunctionCall2(point_distance, \
1218 PointPGetDatum(p1), PointPGetDatum(p2)))
1219
1222{
1223 float8 result = 0.0;
1224
1225 if (isLeaf)
1226 {
1227
1229 }
1230 else if (point->x <= box->high.x && point->x >= box->low.x &&
1231 point->y <= box->high.y && point->y >= box->low.y)
1232 {
1233
1234 result = 0.0;
1235 }
1236 else if (point->x <= box->high.x && point->x >= box->low.x)
1237 {
1238
1240 if (point->y > box->high.y)
1242 else if (point->y < box->low.y)
1244 else
1245 elog(ERROR, "inconsistent point values");
1246 }
1247 else if (point->y <= box->high.y && point->y >= box->low.y)
1248 {
1249
1251 if (point->x > box->high.x)
1253 else if (point->x < box->low.x)
1255 else
1256 elog(ERROR, "inconsistent point values");
1257 }
1258 else
1259 {
1260
1263
1265
1267 if (result > subresult)
1268 result = subresult;
1269
1273 if (result > subresult)
1274 result = subresult;
1275
1279 if (result > subresult)
1280 result = subresult;
1281 }
1282
1283 return result;
1284}
1285
1286static bool
1289{
1290 bool result = false;
1291
1292 switch (strategy)
1293 {
1295 result = FPlt(key->low.x, query->x);
1296 break;
1298 result = FPgt(key->high.x, query->x);
1299 break;
1301 result = FPgt(key->high.y, query->y);
1302 break;
1304 result = FPlt(key->low.y, query->y);
1305 break;
1307 if (isLeaf)
1308 {
1309
1310 result = (FPeq(key->low.x, query->x) &&
1311 FPeq(key->low.y, query->y));
1312 }
1313 else
1314 {
1315 result = (FPle(query->x, key->high.x) &&
1316 FPge(query->x, key->low.x) &&
1317 FPle(query->y, key->high.y) &&
1318 FPge(query->y, key->low.y));
1319 }
1320 break;
1321 default:
1322 elog(ERROR, "unrecognized strategy number: %d", strategy);
1323 result = false;
1324 break;
1325 }
1326
1327 return result;
1328}
1329
1330#define GeoStrategyNumberOffset 20
1331#define PointStrategyNumberGroup 0
1332#define BoxStrategyNumberGroup 1
1333#define PolygonStrategyNumberGroup 2
1334#define CircleStrategyNumberGroup 3
1335
1338{
1342 bool result;
1344
1345
1346
1347
1348
1353
1355 switch (strategyGroup)
1356 {
1362 *recheck = false;
1363 break;
1365 {
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378 BOX *query,
1380
1383
1384 result = (key->high.x >= query->low.x &&
1385 key->low.x <= query->high.x &&
1386 key->high.y >= query->low.y &&
1387 key->low.y <= query->high.y);
1388 *recheck = false;
1389 }
1390 break;
1392 {
1394
1400
1402 {
1403
1404
1405
1406
1408
1414 *recheck = false;
1415 }
1416 }
1417 break;
1419 {
1421
1427
1429 {
1430
1431
1432
1433
1435
1441 *recheck = false;
1442 }
1443 }
1444 break;
1445 default:
1446 elog(ERROR, "unrecognized strategy number: %d", strategy);
1447 result = false;
1448 break;
1449 }
1450
1452}
1453
1456{
1461
1462 switch (strategyGroup)
1463 {
1468 break;
1469 default:
1470 elog(ERROR, "unrecognized strategy number: %d", strategy);
1471 distance = 0.0;
1472 break;
1473 }
1474
1476}
1477
1480{
1483
1484 switch (strategyGroup)
1485 {
1490 break;
1491 default:
1492 elog(ERROR, "unrecognized strategy number: %d", strategy);
1493 distance = 0.0;
1494 }
1495
1496 return distance;
1497}
1498
1501{
1505
1506
1507
1509
1511
1513}
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1527{
1531
1532
1535
1537 *recheck = true;
1538
1540}
1541
1544{
1548
1549
1552
1554 *recheck = true;
1555
1557}
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1576{
1579
1580
1582}
1583
1584
1587{
1589
1590 n = (n | (n << 16)) & UINT64CONST(0x0000FFFF0000FFFF);
1591 n = (n | (n << 8)) & UINT64CONST(0x00FF00FF00FF00FF);
1592 n = (n | (n << 4)) & UINT64CONST(0x0F0F0F0F0F0F0F0F);
1593 n = (n | (n << 2)) & UINT64CONST(0x3333333333333333);
1594 n = (n | (n << 1)) & UINT64CONST(0x5555555555555555);
1595
1596 return n;
1597}
1598
1599
1600
1601
1604{
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645 if (isnan(f))
1646 return 0xFFFFFFFF;
1647 else
1648 {
1649 union
1650 {
1651 float f;
1653 } u;
1654
1655 u.f = f;
1656
1657
1658 if ((u.i & 0x80000000) != 0)
1659 {
1660
1661
1662
1663
1664 Assert(f <= 0);
1665 u.i ^= 0xFFFFFFFF;
1666 }
1667 else
1668 {
1669
1670 u.i |= 0x80000000;
1671 }
1672
1673 return u.i;
1674 }
1675}
1676
1677
1678
1679
1680static int
1682{
1687
1688
1689
1690
1691
1692
1693 if (p1->x == p2->x && p1->y == p2->y)
1694 return 0;
1695
1698 if (z1 > z2)
1699 return 1;
1700 else if (z1 < z2)
1701 return -1;
1702 else
1703 return 0;
1704}
1705
1706
1707
1708
1709
1710
1711
1712
1715{
1718
1720
1721#if SIZEOF_DATUM == 8
1722 return (Datum) z;
1723#else
1724 return (Datum) (z >> 32);
1725#endif
1726}
1727
1728
1729
1730
1731
1732
1733
1734
1735static bool
1737{
1738 return false;
1739}
1740
1741
1742
1743
1746{
1748
1750 {
1755 }
1756 else
1757 {
1759 }
1761}
int float8_cmp_internal(float8 a, float8 b)
static float8 float8_min(const float8 val1, const float8 val2)
static float8 float8_mul(const float8 val1, const float8 val2)
static float4 float4_div(const float4 val1, const float4 val2)
static float8 float8_pl(const float8 val1, const float8 val2)
static float8 float8_mi(const float8 val1, const float8 val2)
static float8 get_float8_infinity(void)
static bool float8_ge(const float8 val1, const float8 val2)
static float8 float8_max(const float8 val1, const float8 val2)
static bool float8_le(const float8 val1, const float8 val2)
static bool float8_eq(const float8 val1, const float8 val2)
static float8 float8_div(const float8 val1, const float8 val2)
static bool float8_lt(const float8 val1, const float8 val2)
static bool float8_gt(const float8 val1, const float8 val2)
#define PG_FREE_IF_COPY(ptr, n)
#define DirectFunctionCall2(func, arg1, arg2)
#define PG_RETURN_FLOAT8(x)
#define PG_GETARG_POINTER(n)
#define PG_GETARG_DATUM(n)
#define PG_GETARG_UINT16(n)
#define DirectFunctionCall5(func, arg1, arg2, arg3, arg4, arg5)
#define PG_RETURN_POINTER(x)
#define PG_RETURN_BOOL(x)
static bool FPlt(double A, double B)
#define PG_GETARG_POINT_P(n)
static bool FPge(double A, double B)
static Datum PolygonPGetDatum(const POLYGON *X)
static Point * DatumGetPointP(Datum X)
static Datum PointPGetDatum(const Point *X)
static POLYGON * DatumGetPolygonP(Datum X)
static BOX * DatumGetBoxP(Datum X)
#define PG_GETARG_BOX_P(n)
#define PG_GETARG_POLYGON_P(n)
static CIRCLE * DatumGetCircleP(Datum X)
static Datum CirclePGetDatum(const CIRCLE *X)
#define PG_GETARG_CIRCLE_P(n)
static bool FPgt(double A, double B)
static bool FPle(double A, double B)
static Datum BoxPGetDatum(const BOX *X)
static bool FPeq(double A, double B)
Datum box_left(PG_FUNCTION_ARGS)
Datum box_right(PG_FUNCTION_ARGS)
Datum box_same(PG_FUNCTION_ARGS)
Datum poly_contain_pt(PG_FUNCTION_ARGS)
Datum box_below(PG_FUNCTION_ARGS)
Datum box_overright(PG_FUNCTION_ARGS)
Datum box_overabove(PG_FUNCTION_ARGS)
Datum box_overlap(PG_FUNCTION_ARGS)
Datum box_contain(PG_FUNCTION_ARGS)
Datum circle_contain_pt(PG_FUNCTION_ARGS)
Datum box_overbelow(PG_FUNCTION_ARGS)
Datum box_contained(PG_FUNCTION_ARGS)
Datum box_overleft(PG_FUNCTION_ARGS)
Datum box_above(PG_FUNCTION_ARGS)
#define gistentryinit(e, k, r, pg, o, l)
static void adjustBox(BOX *b, const BOX *addon)
static void fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
Datum gist_box_penalty(PG_FUNCTION_ARGS)
#define BoxStrategyNumberGroup
Datum gist_box_picksplit(PG_FUNCTION_ARGS)
Datum gist_circle_compress(PG_FUNCTION_ARGS)
static bool rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy)
Datum gist_box_consistent(PG_FUNCTION_ARGS)
static int interval_cmp_upper(const void *i1, const void *i2)
static int gist_bbox_zorder_cmp(Datum a, Datum b, SortSupport ssup)
Datum gist_box_distance(PG_FUNCTION_ARGS)
#define point_point_distance(p1, p2)
static float8 gist_bbox_distance(GISTENTRY *entry, Datum query, StrategyNumber strategy)
Datum gist_poly_compress(PG_FUNCTION_ARGS)
static void rt_box_union(BOX *n, const BOX *a, const BOX *b)
#define GeoStrategyNumberOffset
#define PLACE_RIGHT(box, off)
Datum gist_poly_distance(PG_FUNCTION_ARGS)
static void g_box_consider_split(ConsiderSplitContext *context, int dimNum, float8 rightLower, int minLeftCount, float8 leftUpper, int maxLeftCount)
Datum gist_point_distance(PG_FUNCTION_ARGS)
static float8 box_penalty(const BOX *original, const BOX *new)
Datum gist_circle_distance(PG_FUNCTION_ARGS)
static Datum gist_bbox_zorder_abbrev_convert(Datum original, SortSupport ssup)
#define CircleStrategyNumberGroup
static uint64 part_bits32_by2(uint32 x)
Datum gist_point_sortsupport(PG_FUNCTION_ARGS)
#define PointStrategyNumberGroup
Datum gist_box_union(PG_FUNCTION_ARGS)
static int interval_cmp_lower(const void *i1, const void *i2)
static float8 size_box(const BOX *box)
static uint32 ieee_float32_to_uint32(float f)
Datum gist_circle_consistent(PG_FUNCTION_ARGS)
static bool gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy)
static int common_entry_cmp(const void *i1, const void *i2)
#define PolygonStrategyNumberGroup
Datum gist_poly_consistent(PG_FUNCTION_ARGS)
Datum gist_point_compress(PG_FUNCTION_ARGS)
static uint64 point_zorder_internal(float4 x, float4 y)
Datum gist_point_consistent(PG_FUNCTION_ARGS)
static bool gist_point_consistent_internal(StrategyNumber strategy, bool isLeaf, BOX *key, Point *query)
Datum gist_box_same(PG_FUNCTION_ARGS)
#define PLACE_LEFT(box, off)
static bool gist_bbox_zorder_abbrev_abort(int memtupcount, SortSupport ssup)
static float8 computeDistance(bool isLeaf, BOX *box, Point *point)
Datum gist_point_fetch(PG_FUNCTION_ARGS)
static float non_negative(float val)
Assert(PointerIsAligned(start, uint64))
void * palloc0(Size size)
#define OffsetNumberNext(offsetNumber)
#define FirstOffsetNumber
Datum lower(PG_FUNCTION_ARGS)
Datum upper(PG_FUNCTION_ARGS)
#define qsort(a, b, c, d)
static bool DatumGetBool(Datum X)
static Datum PointerGetDatum(const void *X)
static Datum Int16GetDatum(int16 X)
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
struct SortSupportData * SortSupport
#define RTOverlapStrategyNumber
#define RTLeftStrategyNumber
#define RTOverRightStrategyNumber
#define RTRightStrategyNumber
#define RTSameStrategyNumber
#define RTOverAboveStrategyNumber
#define RTOldBelowStrategyNumber
#define RTContainsStrategyNumber
#define RTOverBelowStrategyNumber
#define RTBelowStrategyNumber
#define RTOldAboveStrategyNumber
#define RTAboveStrategyNumber
#define RTOverLeftStrategyNumber
#define RTContainedByStrategyNumber
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
int ssup_datum_unsigned_cmp(Datum x, Datum y, SortSupport ssup)