| 1 |
/*------------------------------------------------------------------------- |
| 2 |
* |
| 3 |
* gistproc.c |
| 4 |
* Support procedures for GiSTs over 2-D objects (boxes, polygons, circles, |
| 5 |
* points). |
| 6 |
* |
| 7 |
* This gives R-tree behavior, with Guttman's poly-time split algorithm. |
| 8 |
* |
| 9 |
* |
| 10 |
* Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group |
| 11 |
* Portions Copyright (c) 1994, Regents of the University of California |
| 12 |
* |
| 13 |
* IDENTIFICATION |
| 14 |
* src/backend/access/gist/gistproc.c |
| 15 |
* |
| 16 |
*------------------------------------------------------------------------- |
| 17 |
*/ |
| 18 |
#include "postgres.h" |
| 19 |
|
| 20 |
#include <math.h> |
| 21 |
|
| 22 |
#include "access/gist.h" |
| 23 |
#include "access/stratnum.h" |
| 24 |
#include "utils/float.h" |
| 25 |
#include "utils/fmgrprotos.h" |
| 26 |
#include "utils/geo_decls.h" |
| 27 |
#include "utils/sortsupport.h" |
| 28 |
|
| 29 |
|
| 30 |
static bool gist_box_leaf_consistent(BOX *key, BOX *query, |
| 31 |
StrategyNumber strategy); |
| 32 |
static bool rtree_internal_consistent(BOX *key, BOX *query, |
| 33 |
StrategyNumber strategy); |
| 34 |
|
| 35 |
static uint64 point_zorder_internal(float4 x, float4 y); |
| 36 |
static uint64 part_bits32_by2(uint32 x); |
| 37 |
static uint32 ieee_float32_to_uint32(float f); |
| 38 |
static int gist_bbox_zorder_cmp(Datum a, Datum b, SortSupport ssup); |
| 39 |
static Datum gist_bbox_zorder_abbrev_convert(Datum original, SortSupport ssup); |
| 40 |
static bool gist_bbox_zorder_abbrev_abort(int memtupcount, SortSupport ssup); |
| 41 |
|
| 42 |
|
| 43 |
/* Minimum accepted ratio of split */ |
| 44 |
#define LIMIT_RATIO 0.3 |
| 45 |
|
| 46 |
|
| 47 |
/************************************************** |
| 48 |
* Box ops |
| 49 |
**************************************************/ |
| 50 |
|
| 51 |
/* |
| 52 |
* Calculates union of two boxes, a and b. The result is stored in *n. |
| 53 |
*/ |
| 54 |
static void |
| 55 |
rt_box_union(BOX *n, const BOX *a, const BOX *b) |
| 56 |
{ |
| 57 |
n->high.x = float8_max(a->high.x, b->high.x); |
| 58 |
n->high.y = float8_max(a->high.y, b->high.y); |
| 59 |
n->low.x = float8_min(a->low.x, b->low.x); |
| 60 |
n->low.y = float8_min(a->low.y, b->low.y); |
| 61 |
} |
| 62 |
|
| 63 |
/* |
| 64 |
* Size of a BOX for penalty-calculation purposes. |
| 65 |
* The result can be +Infinity, but not NaN. |
| 66 |
*/ |
| 67 |
static float8 |
| 68 |
size_box(const BOX *box) |
| 69 |
{ |
| 70 |
/* |
| 71 |
* Check for zero-width cases. Note that we define the size of a zero- |
| 72 |
* by-infinity box as zero. It's important to special-case this somehow, |
| 73 |
* as naively multiplying infinity by zero will produce NaN. |
| 74 |
* |
| 75 |
* The less-than cases should not happen, but if they do, say "zero". |
| 76 |
*/ |
| 77 |
if (float8_le(box->high.x, box->low.x) || |
| 78 |
float8_le(box->high.y, box->low.y)) |
| 79 |
return 0.0; |
| 80 |
|
| 81 |
/* |
| 82 |
* We treat NaN as larger than +Infinity, so any distance involving a NaN |
| 83 |
* and a non-NaN is infinite. Note the previous check eliminated the |
| 84 |
* possibility that the low fields are NaNs. |
| 85 |
*/ |
| 86 |
if (isnan(box->high.x) || isnan(box->high.y)) |
| 87 |
return get_float8_infinity(); |
| 88 |
return float8_mul(float8_mi(box->high.x, box->low.x), |
| 89 |
float8_mi(box->high.y, box->low.y)); |
| 90 |
} |
| 91 |
|
| 92 |
/* |
| 93 |
* Return amount by which the union of the two boxes is larger than |
| 94 |
* the original BOX's area. The result can be +Infinity, but not NaN. |
| 95 |
*/ |
| 96 |
static float8 |
| 97 |
box_penalty(const BOX *original, const BOX *new) |
| 98 |
{ |
| 99 |
BOX unionbox; |
| 100 |
|
| 101 |
rt_box_union(&unionbox, original, new); |
| 102 |
return float8_mi(size_box(&unionbox), size_box(original)); |
| 103 |
} |
| 104 |
|
| 105 |
/* |
| 106 |
* The GiST Consistent method for boxes |
| 107 |
* |
| 108 |
* Should return false if for all data items x below entry, |
| 109 |
* the predicate x op query must be false, where op is the oper |
| 110 |
* corresponding to strategy in the pg_amop table. |
| 111 |
*/ |
| 112 |
Datum |
| 113 |
gist_box_consistent(PG_FUNCTION_ARGS) |
| 114 |
{ |
| 115 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 116 |
BOX *query = PG_GETARG_BOX_P(1); |
| 117 |
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); |
| 118 |
|
| 119 |
/* Oid subtype = PG_GETARG_OID(3); */ |
| 120 |
bool *recheck = (bool *) PG_GETARG_POINTER(4); |
| 121 |
|
| 122 |
/* All cases served by this function are exact */ |
| 123 |
*recheck = false; |
| 124 |
|
| 125 |
if (DatumGetBoxP(entry->key) == NULL || query == NULL) |
| 126 |
PG_RETURN_BOOL(false); |
| 127 |
|
| 128 |
/* |
| 129 |
* if entry is not leaf, use rtree_internal_consistent, else use |
| 130 |
* gist_box_leaf_consistent |
| 131 |
*/ |
| 132 |
if (GIST_LEAF(entry)) |
| 133 |
PG_RETURN_BOOL(gist_box_leaf_consistent(DatumGetBoxP(entry->key), |
| 134 |
query, |
| 135 |
strategy)); |
| 136 |
else |
| 137 |
PG_RETURN_BOOL(rtree_internal_consistent(DatumGetBoxP(entry->key), |
| 138 |
query, |
| 139 |
strategy)); |
| 140 |
} |
| 141 |
|
| 142 |
/* |
| 143 |
* Increase BOX b to include addon. |
| 144 |
*/ |
| 145 |
static void |
| 146 |
adjustBox(BOX *b, const BOX *addon) |
| 147 |
{ |
| 148 |
if (float8_lt(b->high.x, addon->high.x)) |
| 149 |
b->high.x = addon->high.x; |
| 150 |
if (float8_gt(b->low.x, addon->low.x)) |
| 151 |
b->low.x = addon->low.x; |
| 152 |
if (float8_lt(b->high.y, addon->high.y)) |
| 153 |
b->high.y = addon->high.y; |
| 154 |
if (float8_gt(b->low.y, addon->low.y)) |
| 155 |
b->low.y = addon->low.y; |
| 156 |
} |
| 157 |
|
| 158 |
/* |
| 159 |
* The GiST Union method for boxes |
| 160 |
* |
| 161 |
* returns the minimal bounding box that encloses all the entries in entryvec |
| 162 |
*/ |
| 163 |
Datum |
| 164 |
gist_box_union(PG_FUNCTION_ARGS) |
| 165 |
{ |
| 166 |
GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); |
| 167 |
int *sizep = (int *) PG_GETARG_POINTER(1); |
| 168 |
int numranges, |
| 169 |
i; |
| 170 |
BOX *cur, |
| 171 |
*pageunion; |
| 172 |
|
| 173 |
numranges = entryvec->n; |
| 174 |
pageunion = (BOX *) palloc(sizeof(BOX)); |
| 175 |
cur = DatumGetBoxP(entryvec->vector[0].key); |
| 176 |
memcpy(pageunion, cur, sizeof(BOX)); |
| 177 |
|
| 178 |
for (i = 1; i < numranges; i++) |
| 179 |
{ |
| 180 |
cur = DatumGetBoxP(entryvec->vector[i].key); |
| 181 |
adjustBox(pageunion, cur); |
| 182 |
} |
| 183 |
*sizep = sizeof(BOX); |
| 184 |
|
| 185 |
PG_RETURN_POINTER(pageunion); |
| 186 |
} |
| 187 |
|
| 188 |
/* |
| 189 |
* We store boxes as boxes in GiST indexes, so we do not need |
| 190 |
* compress, decompress, or fetch functions. |
| 191 |
*/ |
| 192 |
|
| 193 |
/* |
| 194 |
* The GiST Penalty method for boxes (also used for points) |
| 195 |
* |
| 196 |
* As in the R-tree paper, we use change in area as our penalty metric |
| 197 |
*/ |
| 198 |
Datum |
| 199 |
gist_box_penalty(PG_FUNCTION_ARGS) |
| 200 |
{ |
| 201 |
GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 202 |
GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1); |
| 203 |
float *result = (float *) PG_GETARG_POINTER(2); |
| 204 |
BOX *origbox = DatumGetBoxP(origentry->key); |
| 205 |
BOX *newbox = DatumGetBoxP(newentry->key); |
| 206 |
|
| 207 |
*result = (float) box_penalty(origbox, newbox); |
| 208 |
PG_RETURN_POINTER(result); |
| 209 |
} |
| 210 |
|
| 211 |
/* |
| 212 |
* Trivial split: half of entries will be placed on one page |
| 213 |
* and another half - to another |
| 214 |
*/ |
| 215 |
static void |
| 216 |
fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v) |
| 217 |
{ |
| 218 |
OffsetNumber i, |
| 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); |
| 227 |
v->spl_left = (OffsetNumber *) palloc(nbytes); |
| 228 |
v->spl_right = (OffsetNumber *) palloc(nbytes); |
| 229 |
v->spl_nleft = v->spl_nright = 0; |
| 230 |
|
| 231 |
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) |
| 232 |
{ |
| 233 |
BOX *cur = DatumGetBoxP(entryvec->vector[i].key); |
| 234 |
|
| 235 |
if (i <= (maxoff - FirstOffsetNumber + 1) / 2) |
| 236 |
{ |
| 237 |
v->spl_left[v->spl_nleft] = i; |
| 238 |
if (unionL == NULL) |
| 239 |
{ |
| 240 |
unionL = (BOX *) palloc(sizeof(BOX)); |
| 241 |
*unionL = *cur; |
| 242 |
} |
| 243 |
else |
| 244 |
adjustBox(unionL, cur); |
| 245 |
|
| 246 |
v->spl_nleft++; |
| 247 |
} |
| 248 |
else |
| 249 |
{ |
| 250 |
v->spl_right[v->spl_nright] = i; |
| 251 |
if (unionR == NULL) |
| 252 |
{ |
| 253 |
unionR = (BOX *) palloc(sizeof(BOX)); |
| 254 |
*unionR = *cur; |
| 255 |
} |
| 256 |
else |
| 257 |
adjustBox(unionR, cur); |
| 258 |
|
| 259 |
v->spl_nright++; |
| 260 |
} |
| 261 |
} |
| 262 |
|
| 263 |
v->spl_ldatum = BoxPGetDatum(unionL); |
| 264 |
v->spl_rdatum = BoxPGetDatum(unionR); |
| 265 |
} |
| 266 |
|
| 267 |
/* |
| 268 |
* Represents information about an entry that can be placed to either group |
| 269 |
* without affecting overlap over selected axis ("common entry"). |
| 270 |
*/ |
| 271 |
typedef struct |
| 272 |
{ |
| 273 |
/* Index of entry in the initial array */ |
| 274 |
int index; |
| 275 |
/* Delta between penalties of entry insertion into different groups */ |
| 276 |
float8 delta; |
| 277 |
} CommonEntry; |
| 278 |
|
| 279 |
/* |
| 280 |
* Context for g_box_consider_split. Contains information about currently |
| 281 |
* selected split and some general information. |
| 282 |
*/ |
| 283 |
typedef struct |
| 284 |
{ |
| 285 |
int entriesCount; /* total number of entries being split */ |
| 286 |
BOX boundingBox; /* minimum bounding box across all entries */ |
| 287 |
|
| 288 |
/* Information about currently selected split follows */ |
| 289 |
|
| 290 |
bool first; /* true if no split was selected yet */ |
| 291 |
|
| 292 |
float8 leftUpper; /* upper bound of left interval */ |
| 293 |
float8 rightLower; /* lower bound of right interval */ |
| 294 |
|
| 295 |
float4 ratio; |
| 296 |
float4 overlap; |
| 297 |
int dim; /* axis of this split */ |
| 298 |
float8 range; /* width of general MBR projection to the |
| 299 |
* selected axis */ |
| 300 |
} ConsiderSplitContext; |
| 301 |
|
| 302 |
/* |
| 303 |
* Interval represents projection of box to axis. |
| 304 |
*/ |
| 305 |
typedef struct |
| 306 |
{ |
| 307 |
float8 lower, |
| 308 |
upper; |
| 309 |
} SplitInterval; |
| 310 |
|
| 311 |
/* |
| 312 |
* Interval comparison function by lower bound of the interval; |
| 313 |
*/ |
| 314 |
static int |
| 315 |
interval_cmp_lower(const void *i1, const void *i2) |
| 316 |
{ |
| 317 |
float8 lower1 = ((const SplitInterval *) i1)->lower, |
| 318 |
lower2 = ((const SplitInterval *) i2)->lower; |
| 319 |
|
| 320 |
return float8_cmp_internal(lower1, lower2); |
| 321 |
} |
| 322 |
|
| 323 |
/* |
| 324 |
* Interval comparison function by upper bound of the interval; |
| 325 |
*/ |
| 326 |
static int |
| 327 |
interval_cmp_upper(const void *i1, const void *i2) |
| 328 |
{ |
| 329 |
float8 upper1 = ((const SplitInterval *) i1)->upper, |
| 330 |
upper2 = ((const SplitInterval *) i2)->upper; |
| 331 |
|
| 332 |
return float8_cmp_internal(upper1, upper2); |
| 333 |
} |
| 334 |
|
| 335 |
/* |
| 336 |
* Replace negative (or NaN) value with zero. |
| 337 |
*/ |
| 338 |
static inline float |
| 339 |
non_negative(float val) |
| 340 |
{ |
| 341 |
if (val >= 0.0f) |
| 342 |
return val; |
| 343 |
else |
| 344 |
return 0.0f; |
| 345 |
} |
| 346 |
|
| 347 |
/* |
| 348 |
* Consider replacement of currently selected split with the better one. |
| 349 |
*/ |
| 350 |
static inline void |
| 351 |
g_box_consider_split(ConsiderSplitContext *context, int dimNum, |
| 352 |
float8 rightLower, int minLeftCount, |
| 353 |
float8 leftUpper, int maxLeftCount) |
| 354 |
{ |
| 355 |
int leftCount, |
| 356 |
rightCount; |
| 357 |
float4 ratio, |
| 358 |
overlap; |
| 359 |
float8 range; |
| 360 |
|
| 361 |
/* |
| 362 |
* Calculate entries distribution ratio assuming most uniform distribution |
| 363 |
* of common entries. |
| 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 |
| 374 |
leftCount = context->entriesCount / 2; |
| 375 |
} |
| 376 |
rightCount = context->entriesCount - leftCount; |
| 377 |
|
| 378 |
/* |
| 379 |
* Ratio of split - quotient between size of lesser group and total |
| 380 |
* entries count. |
| 381 |
*/ |
| 382 |
ratio = float4_div(Min(leftCount, rightCount), context->entriesCount); |
| 383 |
|
| 384 |
if (ratio > LIMIT_RATIO) |
| 385 |
{ |
| 386 |
bool selectthis = false; |
| 387 |
|
| 388 |
/* |
| 389 |
* The ratio is acceptable, so compare current split with previously |
| 390 |
* selected one. Between splits of one dimension we search for minimal |
| 391 |
* overlap (allowing negative values) and minimal ration (between same |
| 392 |
* overlaps. We switch dimension if find less overlap (non-negative) |
| 393 |
* or less range with same overlap. |
| 394 |
*/ |
| 395 |
if (dimNum == 0) |
| 396 |
range = float8_mi(context->boundingBox.high.x, |
| 397 |
context->boundingBox.low.x); |
| 398 |
else |
| 399 |
range = float8_mi(context->boundingBox.high.y, |
| 400 |
context->boundingBox.low.y); |
| 401 |
|
| 402 |
overlap = float8_div(float8_mi(leftUpper, rightLower), range); |
| 403 |
|
| 404 |
/* If there is no previous selection, select this */ |
| 405 |
if (context->first) |
| 406 |
selectthis = true; |
| 407 |
else if (context->dim == dimNum) |
| 408 |
{ |
| 409 |
/* |
| 410 |
* Within the same dimension, choose the new split if it has a |
| 411 |
* smaller overlap, or same overlap but better ratio. |
| 412 |
*/ |
| 413 |
if (overlap < context->overlap || |
| 414 |
(overlap == context->overlap && ratio > context->ratio)) |
| 415 |
selectthis = true; |
| 416 |
} |
| 417 |
else |
| 418 |
{ |
| 419 |
/* |
| 420 |
* Across dimensions, choose the new split if it has a smaller |
| 421 |
* *non-negative* overlap, or same *non-negative* overlap but |
| 422 |
* bigger range. This condition differs from the one described in |
| 423 |
* the article. On the datasets where leaf MBRs don't overlap |
| 424 |
* themselves, non-overlapping splits (i.e. splits which have zero |
| 425 |
* *non-negative* overlap) are frequently possible. In this case |
| 426 |
* splits tends to be along one dimension, because most distant |
| 427 |
* non-overlapping splits (i.e. having lowest negative overlap) |
| 428 |
* appears to be in the same dimension as in the previous split. |
| 429 |
* Therefore MBRs appear to be very prolonged along another |
| 430 |
* dimension, which leads to bad search performance. Using range |
| 431 |
* as the second split criteria makes MBRs more quadratic. Using |
| 432 |
* *non-negative* overlap instead of overlap as the first split |
| 433 |
* criteria gives to range criteria a chance to matter, because |
| 434 |
* non-overlapping splits are equivalent in this criteria. |
| 435 |
*/ |
| 436 |
if (non_negative(overlap) < non_negative(context->overlap) || |
| 437 |
(range > context->range && |
| 438 |
non_negative(overlap) <= non_negative(context->overlap))) |
| 439 |
selectthis = true; |
| 440 |
} |
| 441 |
|
| 442 |
if (selectthis) |
| 443 |
{ |
| 444 |
/* save information about selected split */ |
| 445 |
context->first = false; |
| 446 |
context->ratio = ratio; |
| 447 |
context->range = range; |
| 448 |
context->overlap = overlap; |
| 449 |
context->rightLower = rightLower; |
| 450 |
context->leftUpper = leftUpper; |
| 451 |
context->dim = dimNum; |
| 452 |
} |
| 453 |
} |
| 454 |
} |
| 455 |
|
| 456 |
/* |
| 457 |
* Compare common entries by their deltas. |
| 458 |
*/ |
| 459 |
static int |
| 460 |
common_entry_cmp(const void *i1, const void *i2) |
| 461 |
{ |
| 462 |
float8 delta1 = ((const CommonEntry *) i1)->delta, |
| 463 |
delta2 = ((const CommonEntry *) i2)->delta; |
| 464 |
|
| 465 |
return float8_cmp_internal(delta1, delta2); |
| 466 |
} |
| 467 |
|
| 468 |
/* |
| 469 |
* -------------------------------------------------------------------------- |
| 470 |
* Double sorting split algorithm. This is used for both boxes and points. |
| 471 |
* |
| 472 |
* The algorithm finds split of boxes by considering splits along each axis. |
| 473 |
* Each entry is first projected as an interval on the X-axis, and different |
| 474 |
* ways to split the intervals into two groups are considered, trying to |
| 475 |
* minimize the overlap of the groups. Then the same is repeated for the |
| 476 |
* Y-axis, and the overall best split is chosen. The quality of a split is |
| 477 |
* determined by overlap along that axis and some other criteria (see |
| 478 |
* g_box_consider_split). |
| 479 |
* |
| 480 |
* After that, all the entries are divided into three groups: |
| 481 |
* |
| 482 |
* 1) Entries which should be placed to the left group |
| 483 |
* 2) Entries which should be placed to the right group |
| 484 |
* 3) "Common entries" which can be placed to any of groups without affecting |
| 485 |
* of overlap along selected axis. |
| 486 |
* |
| 487 |
* The common entries are distributed by minimizing penalty. |
| 488 |
* |
| 489 |
* For details see: |
| 490 |
* "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov |
| 491 |
* http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36 |
| 492 |
* -------------------------------------------------------------------------- |
| 493 |
*/ |
| 494 |
Datum |
| 495 |
gist_box_picksplit(PG_FUNCTION_ARGS) |
| 496 |
{ |
| 497 |
GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); |
| 498 |
GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1); |
| 499 |
OffsetNumber i, |
| 500 |
maxoff; |
| 501 |
ConsiderSplitContext context; |
| 502 |
BOX *box, |
| 503 |
*leftBox, |
| 504 |
*rightBox; |
| 505 |
int dim, |
| 506 |
commonEntriesCount; |
| 507 |
SplitInterval *intervalsLower, |
| 508 |
*intervalsUpper; |
| 509 |
CommonEntry *commonEntries; |
| 510 |
int nentries; |
| 511 |
|
| 512 |
memset(&context, 0, sizeof(ConsiderSplitContext)); |
| 513 |
|
| 514 |
maxoff = entryvec->n - 1; |
| 515 |
nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1; |
| 516 |
|
| 517 |
/* Allocate arrays for intervals along axes */ |
| 518 |
intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval)); |
| 519 |
intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval)); |
| 520 |
|
| 521 |
/* |
| 522 |
* Calculate the overall minimum bounding box over all the entries. |
| 523 |
*/ |
| 524 |
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) |
| 525 |
{ |
| 526 |
box = DatumGetBoxP(entryvec->vector[i].key); |
| 527 |
if (i == FirstOffsetNumber) |
| 528 |
context.boundingBox = *box; |
| 529 |
else |
| 530 |
adjustBox(&context.boundingBox, box); |
| 531 |
} |
| 532 |
|
| 533 |
/* |
| 534 |
* Iterate over axes for optimal split searching. |
| 535 |
*/ |
| 536 |
context.first = true; /* nothing selected yet */ |
| 537 |
for (dim = 0; dim < 2; dim++) |
| 538 |
{ |
| 539 |
float8 leftUpper, |
| 540 |
rightLower; |
| 541 |
int i1, |
| 542 |
i2; |
| 543 |
|
| 544 |
/* Project each entry as an interval on the selected axis. */ |
| 545 |
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) |
| 546 |
{ |
| 547 |
box = DatumGetBoxP(entryvec->vector[i].key); |
| 548 |
if (dim == 0) |
| 549 |
{ |
| 550 |
intervalsLower[i - FirstOffsetNumber].lower = box->low.x; |
| 551 |
intervalsLower[i - FirstOffsetNumber].upper = box->high.x; |
| 552 |
} |
| 553 |
else |
| 554 |
{ |
| 555 |
intervalsLower[i - FirstOffsetNumber].lower = box->low.y; |
| 556 |
intervalsLower[i - FirstOffsetNumber].upper = box->high.y; |
| 557 |
} |
| 558 |
} |
| 559 |
|
| 560 |
/* |
| 561 |
* Make two arrays of intervals: one sorted by lower bound and another |
| 562 |
* sorted by upper bound. |
| 563 |
*/ |
| 564 |
memcpy(intervalsUpper, intervalsLower, |
| 565 |
sizeof(SplitInterval) * nentries); |
| 566 |
qsort(intervalsLower, nentries, sizeof(SplitInterval), |
| 567 |
interval_cmp_lower); |
| 568 |
qsort(intervalsUpper, nentries, sizeof(SplitInterval), |
| 569 |
interval_cmp_upper); |
| 570 |
|
| 571 |
/*---- |
| 572 |
* The goal is to form a left and right interval, so that every entry |
| 573 |
* interval is contained by either left or right interval (or both). |
| 574 |
* |
| 575 |
* For example, with the intervals (0,1), (1,3), (2,3), (2,4): |
| 576 |
* |
| 577 |
* 0 1 2 3 4 |
| 578 |
* +-+ |
| 579 |
* +---+ |
| 580 |
* +-+ |
| 581 |
* +---+ |
| 582 |
* |
| 583 |
* The left and right intervals are of the form (0,a) and (b,4). |
| 584 |
* We first consider splits where b is the lower bound of an entry. |
| 585 |
* We iterate through all entries, and for each b, calculate the |
| 586 |
* smallest possible a. Then we consider splits where a is the |
| 587 |
* upper bound of an entry, and for each a, calculate the greatest |
| 588 |
* possible b. |
| 589 |
* |
| 590 |
* In the above example, the first loop would consider splits: |
| 591 |
* b=0: (0,1)-(0,4) |
| 592 |
* b=1: (0,1)-(1,4) |
| 593 |
* b=2: (0,3)-(2,4) |
| 594 |
* |
| 595 |
* And the second loop: |
| 596 |
* a=1: (0,1)-(1,4) |
| 597 |
* a=3: (0,3)-(2,4) |
| 598 |
* a=4: (0,4)-(2,4) |
| 599 |
*/ |
| 600 |
|
| 601 |
/* |
| 602 |
* Iterate over lower bound of right group, finding smallest possible |
| 603 |
* upper bound of left group. |
| 604 |
*/ |
| 605 |
i1 = 0; |
| 606 |
i2 = 0; |
| 607 |
rightLower = intervalsLower[i1].lower; |
| 608 |
leftUpper = intervalsUpper[i2].lower; |
| 609 |
while (true) |
| 610 |
{ |
| 611 |
/* |
| 612 |
* Find next lower bound of right group. |
| 613 |
*/ |
| 614 |
while (i1 < nentries && |
| 615 |
float8_eq(rightLower, intervalsLower[i1].lower)) |
| 616 |
{ |
| 617 |
if (float8_lt(leftUpper, intervalsLower[i1].upper)) |
| 618 |
leftUpper = intervalsLower[i1].upper; |
| 619 |
i1++; |
| 620 |
} |
| 621 |
if (i1 >= nentries) |
| 622 |
break; |
| 623 |
rightLower = intervalsLower[i1].lower; |
| 624 |
|
| 625 |
/* |
| 626 |
* Find count of intervals which anyway should be placed to the |
| 627 |
* left group. |
| 628 |
*/ |
| 629 |
while (i2 < nentries && |
| 630 |
float8_le(intervalsUpper[i2].upper, leftUpper)) |
| 631 |
i2++; |
| 632 |
|
| 633 |
/* |
| 634 |
* Consider found split. |
| 635 |
*/ |
| 636 |
g_box_consider_split(&context, dim, rightLower, i1, leftUpper, i2); |
| 637 |
} |
| 638 |
|
| 639 |
/* |
| 640 |
* Iterate over upper bound of left group finding greatest possible |
| 641 |
* lower bound of right group. |
| 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 |
* Find next upper bound of left group. |
| 651 |
*/ |
| 652 |
while (i2 >= 0 && float8_eq(leftUpper, intervalsUpper[i2].upper)) |
| 653 |
{ |
| 654 |
if (float8_gt(rightLower, intervalsUpper[i2].lower)) |
| 655 |
rightLower = intervalsUpper[i2].lower; |
| 656 |
i2--; |
| 657 |
} |
| 658 |
if (i2 < 0) |
| 659 |
break; |
| 660 |
leftUpper = intervalsUpper[i2].upper; |
| 661 |
|
| 662 |
/* |
| 663 |
* Find count of intervals which anyway should be placed to the |
| 664 |
* right group. |
| 665 |
*/ |
| 666 |
while (i1 >= 0 && float8_ge(intervalsLower[i1].lower, rightLower)) |
| 667 |
i1--; |
| 668 |
|
| 669 |
/* |
| 670 |
* Consider found split. |
| 671 |
*/ |
| 672 |
g_box_consider_split(&context, dim, |
| 673 |
rightLower, i1 + 1, leftUpper, i2 + 1); |
| 674 |
} |
| 675 |
} |
| 676 |
|
| 677 |
/* |
| 678 |
* If we failed to find any acceptable splits, use trivial split. |
| 679 |
*/ |
| 680 |
if (context.first) |
| 681 |
{ |
| 682 |
fallbackSplit(entryvec, v); |
| 683 |
PG_RETURN_POINTER(v); |
| 684 |
} |
| 685 |
|
| 686 |
/* |
| 687 |
* Ok, we have now selected the split across one axis. |
| 688 |
* |
| 689 |
* While considering the splits, we already determined that there will be |
| 690 |
* enough entries in both groups to reach the desired ratio, but we did |
| 691 |
* not memorize which entries go to which group. So determine that now. |
| 692 |
*/ |
| 693 |
|
| 694 |
/* Allocate vectors for results */ |
| 695 |
v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber)); |
| 696 |
v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber)); |
| 697 |
v->spl_nleft = 0; |
| 698 |
v->spl_nright = 0; |
| 699 |
|
| 700 |
/* Allocate bounding boxes of left and right groups */ |
| 701 |
leftBox = palloc0(sizeof(BOX)); |
| 702 |
rightBox = palloc0(sizeof(BOX)); |
| 703 |
|
| 704 |
/* |
| 705 |
* Allocate an array for "common entries" - entries which can be placed to |
| 706 |
* either group without affecting overlap along selected axis. |
| 707 |
*/ |
| 708 |
commonEntriesCount = 0; |
| 709 |
commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry)); |
| 710 |
|
| 711 |
/* Helper macros to place an entry in the left or right group */ |
| 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 |
* Distribute entries which can be distributed unambiguously, and collect |
| 732 |
* common entries. |
| 733 |
*/ |
| 734 |
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) |
| 735 |
{ |
| 736 |
float8 lower, |
| 737 |
upper; |
| 738 |
|
| 739 |
/* |
| 740 |
* Get upper and lower bounds along selected axis. |
| 741 |
*/ |
| 742 |
box = DatumGetBoxP(entryvec->vector[i].key); |
| 743 |
if (context.dim == 0) |
| 744 |
{ |
| 745 |
lower = box->low.x; |
| 746 |
upper = box->high.x; |
| 747 |
} |
| 748 |
else |
| 749 |
{ |
| 750 |
lower = box->low.y; |
| 751 |
upper = box->high.y; |
| 752 |
} |
| 753 |
|
| 754 |
if (float8_le(upper, context.leftUpper)) |
| 755 |
{ |
| 756 |
/* Fits to the left group */ |
| 757 |
if (float8_ge(lower, context.rightLower)) |
| 758 |
{ |
| 759 |
/* Fits also to the right group, so "common entry" */ |
| 760 |
commonEntries[commonEntriesCount++].index = i; |
| 761 |
} |
| 762 |
else |
| 763 |
{ |
| 764 |
/* Doesn't fit to the right group, so join to the left group */ |
| 765 |
PLACE_LEFT(box, i); |
| 766 |
} |
| 767 |
} |
| 768 |
else |
| 769 |
{ |
| 770 |
/* |
| 771 |
* Each entry should fit on either left or right group. Since this |
| 772 |
* entry didn't fit on the left group, it better fit in the right |
| 773 |
* group. |
| 774 |
*/ |
| 775 |
Assert(float8_ge(lower, context.rightLower)); |
| 776 |
|
| 777 |
/* Doesn't fit to the left group, so join to the right group */ |
| 778 |
PLACE_RIGHT(box, i); |
| 779 |
} |
| 780 |
} |
| 781 |
|
| 782 |
/* |
| 783 |
* Distribute "common entries", if any. |
| 784 |
*/ |
| 785 |
if (commonEntriesCount > 0) |
| 786 |
{ |
| 787 |
/* |
| 788 |
* Calculate minimum number of entries that must be placed in both |
| 789 |
* groups, to reach LIMIT_RATIO. |
| 790 |
*/ |
| 791 |
int m = ceil(LIMIT_RATIO * nentries); |
| 792 |
|
| 793 |
/* |
| 794 |
* Calculate delta between penalties of join "common entries" to |
| 795 |
* different groups. |
| 796 |
*/ |
| 797 |
for (i = 0; i < commonEntriesCount; i++) |
| 798 |
{ |
| 799 |
box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key); |
| 800 |
commonEntries[i].delta = fabs(float8_mi(box_penalty(leftBox, box), |
| 801 |
box_penalty(rightBox, box))); |
| 802 |
} |
| 803 |
|
| 804 |
/* |
| 805 |
* Sort "common entries" by calculated deltas in order to distribute |
| 806 |
* the most ambiguous entries first. |
| 807 |
*/ |
| 808 |
qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp); |
| 809 |
|
| 810 |
/* |
| 811 |
* Distribute "common entries" between groups. |
| 812 |
*/ |
| 813 |
for (i = 0; i < commonEntriesCount; i++) |
| 814 |
{ |
| 815 |
box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key); |
| 816 |
|
| 817 |
/* |
| 818 |
* Check if we have to place this entry in either group to achieve |
| 819 |
* LIMIT_RATIO. |
| 820 |
*/ |
| 821 |
if (v->spl_nleft + (commonEntriesCount - i) <= m) |
| 822 |
PLACE_LEFT(box, commonEntries[i].index); |
| 823 |
else if (v->spl_nright + (commonEntriesCount - i) <= m) |
| 824 |
PLACE_RIGHT(box, commonEntries[i].index); |
| 825 |
else |
| 826 |
{ |
| 827 |
/* Otherwise select the group by minimal penalty */ |
| 828 |
if (box_penalty(leftBox, box) < box_penalty(rightBox, box)) |
| 829 |
PLACE_LEFT(box, commonEntries[i].index); |
| 830 |
else |
| 831 |
PLACE_RIGHT(box, commonEntries[i].index); |
| 832 |
} |
| 833 |
} |
| 834 |
} |
| 835 |
|
| 836 |
v->spl_ldatum = PointerGetDatum(leftBox); |
| 837 |
v->spl_rdatum = PointerGetDatum(rightBox); |
| 838 |
PG_RETURN_POINTER(v); |
| 839 |
} |
| 840 |
|
| 841 |
/* |
| 842 |
* Equality method |
| 843 |
* |
| 844 |
* This is used for boxes, points, circles, and polygons, all of which store |
| 845 |
* boxes as GiST index entries. |
| 846 |
* |
| 847 |
* Returns true only when boxes are exactly the same. We can't use fuzzy |
| 848 |
* comparisons here without breaking index consistency; therefore, this isn't |
| 849 |
* equivalent to box_same(). |
| 850 |
*/ |
| 851 |
Datum |
| 852 |
gist_box_same(PG_FUNCTION_ARGS) |
| 853 |
{ |
| 854 |
BOX *b1 = PG_GETARG_BOX_P(0); |
| 855 |
BOX *b2 = PG_GETARG_BOX_P(1); |
| 856 |
bool *result = (bool *) PG_GETARG_POINTER(2); |
| 857 |
|
| 858 |
if (b1 && b2) |
| 859 |
*result = (float8_eq(b1->low.x, b2->low.x) && |
| 860 |
float8_eq(b1->low.y, b2->low.y) && |
| 861 |
float8_eq(b1->high.x, b2->high.x) && |
| 862 |
float8_eq(b1->high.y, b2->high.y)); |
| 863 |
else |
| 864 |
*result = (b1 == NULL && b2 == NULL); |
| 865 |
PG_RETURN_POINTER(result); |
| 866 |
} |
| 867 |
|
| 868 |
/* |
| 869 |
* Leaf-level consistency for boxes: just apply the query operator |
| 870 |
*/ |
| 871 |
static bool |
| 872 |
gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy) |
| 873 |
{ |
| 874 |
bool retval; |
| 875 |
|
| 876 |
switch (strategy) |
| 877 |
{ |
| 878 |
case RTLeftStrategyNumber: |
| 879 |
retval = DatumGetBool(DirectFunctionCall2(box_left, |
| 880 |
PointerGetDatum(key), |
| 881 |
PointerGetDatum(query))); |
| 882 |
break; |
| 883 |
case RTOverLeftStrategyNumber: |
| 884 |
retval = DatumGetBool(DirectFunctionCall2(box_overleft, |
| 885 |
PointerGetDatum(key), |
| 886 |
PointerGetDatum(query))); |
| 887 |
break; |
| 888 |
case RTOverlapStrategyNumber: |
| 889 |
retval = DatumGetBool(DirectFunctionCall2(box_overlap, |
| 890 |
PointerGetDatum(key), |
| 891 |
PointerGetDatum(query))); |
| 892 |
break; |
| 893 |
case RTOverRightStrategyNumber: |
| 894 |
retval = DatumGetBool(DirectFunctionCall2(box_overright, |
| 895 |
PointerGetDatum(key), |
| 896 |
PointerGetDatum(query))); |
| 897 |
break; |
| 898 |
case RTRightStrategyNumber: |
| 899 |
retval = DatumGetBool(DirectFunctionCall2(box_right, |
| 900 |
PointerGetDatum(key), |
| 901 |
PointerGetDatum(query))); |
| 902 |
break; |
| 903 |
case RTSameStrategyNumber: |
| 904 |
retval = DatumGetBool(DirectFunctionCall2(box_same, |
| 905 |
PointerGetDatum(key), |
| 906 |
PointerGetDatum(query))); |
| 907 |
break; |
| 908 |
case RTContainsStrategyNumber: |
| 909 |
retval = DatumGetBool(DirectFunctionCall2(box_contain, |
| 910 |
PointerGetDatum(key), |
| 911 |
PointerGetDatum(query))); |
| 912 |
break; |
| 913 |
case RTContainedByStrategyNumber: |
| 914 |
retval = DatumGetBool(DirectFunctionCall2(box_contained, |
| 915 |
PointerGetDatum(key), |
| 916 |
PointerGetDatum(query))); |
| 917 |
break; |
| 918 |
case RTOverBelowStrategyNumber: |
| 919 |
retval = DatumGetBool(DirectFunctionCall2(box_overbelow, |
| 920 |
PointerGetDatum(key), |
| 921 |
PointerGetDatum(query))); |
| 922 |
break; |
| 923 |
case RTBelowStrategyNumber: |
| 924 |
retval = DatumGetBool(DirectFunctionCall2(box_below, |
| 925 |
PointerGetDatum(key), |
| 926 |
PointerGetDatum(query))); |
| 927 |
break; |
| 928 |
case RTAboveStrategyNumber: |
| 929 |
retval = DatumGetBool(DirectFunctionCall2(box_above, |
| 930 |
PointerGetDatum(key), |
| 931 |
PointerGetDatum(query))); |
| 932 |
break; |
| 933 |
case RTOverAboveStrategyNumber: |
| 934 |
retval = DatumGetBool(DirectFunctionCall2(box_overabove, |
| 935 |
PointerGetDatum(key), |
| 936 |
PointerGetDatum(query))); |
| 937 |
break; |
| 938 |
default: |
| 939 |
elog(ERROR, "unrecognized strategy number: %d", strategy); |
| 940 |
retval = false; /* keep compiler quiet */ |
| 941 |
break; |
| 942 |
} |
| 943 |
return retval; |
| 944 |
} |
| 945 |
|
| 946 |
/***************************************** |
| 947 |
* Common rtree functions (for boxes, polygons, and circles) |
| 948 |
*****************************************/ |
| 949 |
|
| 950 |
/* |
| 951 |
* Internal-page consistency for all these types |
| 952 |
* |
| 953 |
* We can use the same function since all types use bounding boxes as the |
| 954 |
* internal-page representation. |
| 955 |
*/ |
| 956 |
static bool |
| 957 |
rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy) |
| 958 |
{ |
| 959 |
bool retval; |
| 960 |
|
| 961 |
switch (strategy) |
| 962 |
{ |
| 963 |
case RTLeftStrategyNumber: |
| 964 |
retval = !DatumGetBool(DirectFunctionCall2(box_overright, |
| 965 |
PointerGetDatum(key), |
| 966 |
PointerGetDatum(query))); |
| 967 |
break; |
| 968 |
case RTOverLeftStrategyNumber: |
| 969 |
retval = !DatumGetBool(DirectFunctionCall2(box_right, |
| 970 |
PointerGetDatum(key), |
| 971 |
PointerGetDatum(query))); |
| 972 |
break; |
| 973 |
case RTOverlapStrategyNumber: |
| 974 |
retval = DatumGetBool(DirectFunctionCall2(box_overlap, |
| 975 |
PointerGetDatum(key), |
| 976 |
PointerGetDatum(query))); |
| 977 |
break; |
| 978 |
case RTOverRightStrategyNumber: |
| 979 |
retval = !DatumGetBool(DirectFunctionCall2(box_left, |
| 980 |
PointerGetDatum(key), |
| 981 |
PointerGetDatum(query))); |
| 982 |
break; |
| 983 |
case RTRightStrategyNumber: |
| 984 |
retval = !DatumGetBool(DirectFunctionCall2(box_overleft, |
| 985 |
PointerGetDatum(key), |
| 986 |
PointerGetDatum(query))); |
| 987 |
break; |
| 988 |
case RTSameStrategyNumber: |
| 989 |
case RTContainsStrategyNumber: |
| 990 |
retval = DatumGetBool(DirectFunctionCall2(box_contain, |
| 991 |
PointerGetDatum(key), |
| 992 |
PointerGetDatum(query))); |
| 993 |
break; |
| 994 |
case RTContainedByStrategyNumber: |
| 995 |
retval = DatumGetBool(DirectFunctionCall2(box_overlap, |
| 996 |
PointerGetDatum(key), |
| 997 |
PointerGetDatum(query))); |
| 998 |
break; |
| 999 |
case RTOverBelowStrategyNumber: |
| 1000 |
retval = !DatumGetBool(DirectFunctionCall2(box_above, |
| 1001 |
PointerGetDatum(key), |
| 1002 |
PointerGetDatum(query))); |
| 1003 |
break; |
| 1004 |
case RTBelowStrategyNumber: |
| 1005 |
retval = !DatumGetBool(DirectFunctionCall2(box_overabove, |
| 1006 |
PointerGetDatum(key), |
| 1007 |
PointerGetDatum(query))); |
| 1008 |
break; |
| 1009 |
case RTAboveStrategyNumber: |
| 1010 |
retval = !DatumGetBool(DirectFunctionCall2(box_overbelow, |
| 1011 |
PointerGetDatum(key), |
| 1012 |
PointerGetDatum(query))); |
| 1013 |
break; |
| 1014 |
case RTOverAboveStrategyNumber: |
| 1015 |
retval = !DatumGetBool(DirectFunctionCall2(box_below, |
| 1016 |
PointerGetDatum(key), |
| 1017 |
PointerGetDatum(query))); |
| 1018 |
break; |
| 1019 |
default: |
| 1020 |
elog(ERROR, "unrecognized strategy number: %d", strategy); |
| 1021 |
retval = false; /* keep compiler quiet */ |
| 1022 |
break; |
| 1023 |
} |
| 1024 |
return retval; |
| 1025 |
} |
| 1026 |
|
| 1027 |
/************************************************** |
| 1028 |
* Polygon ops |
| 1029 |
**************************************************/ |
| 1030 |
|
| 1031 |
/* |
| 1032 |
* GiST compress for polygons: represent a polygon by its bounding box |
| 1033 |
*/ |
| 1034 |
Datum |
| 1035 |
gist_poly_compress(PG_FUNCTION_ARGS) |
| 1036 |
{ |
| 1037 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 1038 |
GISTENTRY *retval; |
| 1039 |
|
| 1040 |
if (entry->leafkey) |
| 1041 |
{ |
| 1042 |
POLYGON *in = DatumGetPolygonP(entry->key); |
| 1043 |
BOX *r; |
| 1044 |
|
| 1045 |
r = (BOX *) palloc(sizeof(BOX)); |
| 1046 |
memcpy(r, &(in->boundbox), sizeof(BOX)); |
| 1047 |
|
| 1048 |
retval = (GISTENTRY *) palloc(sizeof(GISTENTRY)); |
| 1049 |
gistentryinit(*retval, PointerGetDatum(r), |
| 1050 |
entry->rel, entry->page, |
| 1051 |
entry->offset, false); |
| 1052 |
} |
| 1053 |
else |
| 1054 |
retval = entry; |
| 1055 |
PG_RETURN_POINTER(retval); |
| 1056 |
} |
| 1057 |
|
| 1058 |
/* |
| 1059 |
* The GiST Consistent method for polygons |
| 1060 |
*/ |
| 1061 |
Datum |
| 1062 |
gist_poly_consistent(PG_FUNCTION_ARGS) |
| 1063 |
{ |
| 1064 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 1065 |
POLYGON *query = PG_GETARG_POLYGON_P(1); |
| 1066 |
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); |
| 1067 |
|
| 1068 |
/* Oid subtype = PG_GETARG_OID(3); */ |
| 1069 |
bool *recheck = (bool *) PG_GETARG_POINTER(4); |
| 1070 |
bool result; |
| 1071 |
|
| 1072 |
/* All cases served by this function are inexact */ |
| 1073 |
*recheck = true; |
| 1074 |
|
| 1075 |
if (DatumGetBoxP(entry->key) == NULL || query == NULL) |
| 1076 |
PG_RETURN_BOOL(false); |
| 1077 |
|
| 1078 |
/* |
| 1079 |
* Since the operators require recheck anyway, we can just use |
| 1080 |
* rtree_internal_consistent even at leaf nodes. (This works in part |
| 1081 |
* because the index entries are bounding boxes not polygons.) |
| 1082 |
*/ |
| 1083 |
result = rtree_internal_consistent(DatumGetBoxP(entry->key), |
| 1084 |
&(query->boundbox), strategy); |
| 1085 |
|
| 1086 |
/* Avoid memory leak if supplied poly is toasted */ |
| 1087 |
PG_FREE_IF_COPY(query, 1); |
| 1088 |
|
| 1089 |
PG_RETURN_BOOL(result); |
| 1090 |
} |
| 1091 |
|
| 1092 |
/************************************************** |
| 1093 |
* Circle ops |
| 1094 |
**************************************************/ |
| 1095 |
|
| 1096 |
/* |
| 1097 |
* GiST compress for circles: represent a circle by its bounding box |
| 1098 |
*/ |
| 1099 |
Datum |
| 1100 |
gist_circle_compress(PG_FUNCTION_ARGS) |
| 1101 |
{ |
| 1102 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 1103 |
GISTENTRY *retval; |
| 1104 |
|
| 1105 |
if (entry->leafkey) |
| 1106 |
{ |
| 1107 |
CIRCLE *in = DatumGetCircleP(entry->key); |
| 1108 |
BOX *r; |
| 1109 |
|
| 1110 |
r = (BOX *) palloc(sizeof(BOX)); |
| 1111 |
r->high.x = float8_pl(in->center.x, in->radius); |
| 1112 |
r->low.x = float8_mi(in->center.x, in->radius); |
| 1113 |
r->high.y = float8_pl(in->center.y, in->radius); |
| 1114 |
r->low.y = float8_mi(in->center.y, in->radius); |
| 1115 |
|
| 1116 |
retval = (GISTENTRY *) palloc(sizeof(GISTENTRY)); |
| 1117 |
gistentryinit(*retval, PointerGetDatum(r), |
| 1118 |
entry->rel, entry->page, |
| 1119 |
entry->offset, false); |
| 1120 |
} |
| 1121 |
else |
| 1122 |
retval = entry; |
| 1123 |
PG_RETURN_POINTER(retval); |
| 1124 |
} |
| 1125 |
|
| 1126 |
/* |
| 1127 |
* The GiST Consistent method for circles |
| 1128 |
*/ |
| 1129 |
Datum |
| 1130 |
gist_circle_consistent(PG_FUNCTION_ARGS) |
| 1131 |
{ |
| 1132 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 1133 |
CIRCLE *query = PG_GETARG_CIRCLE_P(1); |
| 1134 |
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); |
| 1135 |
|
| 1136 |
/* Oid subtype = PG_GETARG_OID(3); */ |
| 1137 |
bool *recheck = (bool *) PG_GETARG_POINTER(4); |
| 1138 |
BOX bbox; |
| 1139 |
bool result; |
| 1140 |
|
| 1141 |
/* All cases served by this function are inexact */ |
| 1142 |
*recheck = true; |
| 1143 |
|
| 1144 |
if (DatumGetBoxP(entry->key) == NULL || query == NULL) |
| 1145 |
PG_RETURN_BOOL(false); |
| 1146 |
|
| 1147 |
/* |
| 1148 |
* Since the operators require recheck anyway, we can just use |
| 1149 |
* rtree_internal_consistent even at leaf nodes. (This works in part |
| 1150 |
* because the index entries are bounding boxes not circles.) |
| 1151 |
*/ |
| 1152 |
bbox.high.x = float8_pl(query->center.x, query->radius); |
| 1153 |
bbox.low.x = float8_mi(query->center.x, query->radius); |
| 1154 |
bbox.high.y = float8_pl(query->center.y, query->radius); |
| 1155 |
bbox.low.y = float8_mi(query->center.y, query->radius); |
| 1156 |
|
| 1157 |
result = rtree_internal_consistent(DatumGetBoxP(entry->key), |
| 1158 |
&bbox, strategy); |
| 1159 |
|
| 1160 |
PG_RETURN_BOOL(result); |
| 1161 |
} |
| 1162 |
|
| 1163 |
/************************************************** |
| 1164 |
* Point ops |
| 1165 |
**************************************************/ |
| 1166 |
|
| 1167 |
Datum |
| 1168 |
gist_point_compress(PG_FUNCTION_ARGS) |
| 1169 |
{ |
| 1170 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 1171 |
|
| 1172 |
if (entry->leafkey) /* Point, actually */ |
| 1173 |
{ |
| 1174 |
BOX *box = palloc(sizeof(BOX)); |
| 1175 |
Point *point = DatumGetPointP(entry->key); |
| 1176 |
GISTENTRY *retval = palloc(sizeof(GISTENTRY)); |
| 1177 |
|
| 1178 |
box->high = box->low = *point; |
| 1179 |
|
| 1180 |
gistentryinit(*retval, BoxPGetDatum(box), |
| 1181 |
entry->rel, entry->page, entry->offset, false); |
| 1182 |
|
| 1183 |
PG_RETURN_POINTER(retval); |
| 1184 |
} |
| 1185 |
|
| 1186 |
PG_RETURN_POINTER(entry); |
| 1187 |
} |
| 1188 |
|
| 1189 |
/* |
| 1190 |
* GiST Fetch method for point |
| 1191 |
* |
| 1192 |
* Get point coordinates from its bounding box coordinates and form new |
| 1193 |
* gistentry. |
| 1194 |
*/ |
| 1195 |
Datum |
| 1196 |
gist_point_fetch(PG_FUNCTION_ARGS) |
| 1197 |
{ |
| 1198 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 1199 |
BOX *in = DatumGetBoxP(entry->key); |
| 1200 |
Point *r; |
| 1201 |
GISTENTRY *retval; |
| 1202 |
|
| 1203 |
retval = palloc(sizeof(GISTENTRY)); |
| 1204 |
|
| 1205 |
r = (Point *) palloc(sizeof(Point)); |
| 1206 |
r->x = in->high.x; |
| 1207 |
r->y = in->high.y; |
| 1208 |
gistentryinit(*retval, PointerGetDatum(r), |
| 1209 |
entry->rel, entry->page, |
| 1210 |
entry->offset, false); |
| 1211 |
|
| 1212 |
PG_RETURN_POINTER(retval); |
| 1213 |
} |
| 1214 |
|
| 1215 |
|
| 1216 |
#define point_point_distance(p1,p2) \ |
| 1217 |
DatumGetFloat8(DirectFunctionCall2(point_distance, \ |
| 1218 |
PointPGetDatum(p1), PointPGetDatum(p2))) |
| 1219 |
|
| 1220 |
static float8 |
| 1221 |
computeDistance(bool isLeaf, BOX *box, Point *point) |
| 1222 |
{ |
| 1223 |
float8 result = 0.0; |
| 1224 |
|
| 1225 |
if (isLeaf) |
| 1226 |
{ |
| 1227 |
/* simple point to point distance */ |
| 1228 |
result = point_point_distance(point, &box->low); |
| 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 |
/* point inside the box */ |
| 1234 |
result = 0.0; |
| 1235 |
} |
| 1236 |
else if (point->x <= box->high.x && point->x >= box->low.x) |
| 1237 |
{ |
| 1238 |
/* point is over or below box */ |
| 1239 |
Assert(box->low.y <= box->high.y); |
| 1240 |
if (point->y > box->high.y) |
| 1241 |
result = float8_mi(point->y, box->high.y); |
| 1242 |
else if (point->y < box->low.y) |
| 1243 |
result = float8_mi(box->low.y, point->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 |
/* point is to left or right of box */ |
| 1250 |
Assert(box->low.x <= box->high.x); |
| 1251 |
if (point->x > box->high.x) |
| 1252 |
result = float8_mi(point->x, box->high.x); |
| 1253 |
else if (point->x < box->low.x) |
| 1254 |
result = float8_mi(box->low.x, point->x); |
| 1255 |
else |
| 1256 |
elog(ERROR, "inconsistent point values"); |
| 1257 |
} |
| 1258 |
else |
| 1259 |
{ |
| 1260 |
/* closest point will be a vertex */ |
| 1261 |
Point p; |
| 1262 |
float8 subresult; |
| 1263 |
|
| 1264 |
result = point_point_distance(point, &box->low); |
| 1265 |
|
| 1266 |
subresult = point_point_distance(point, &box->high); |
| 1267 |
if (result > subresult) |
| 1268 |
result = subresult; |
| 1269 |
|
| 1270 |
p.x = box->low.x; |
| 1271 |
p.y = box->high.y; |
| 1272 |
subresult = point_point_distance(point, &p); |
| 1273 |
if (result > subresult) |
| 1274 |
result = subresult; |
| 1275 |
|
| 1276 |
p.x = box->high.x; |
| 1277 |
p.y = box->low.y; |
| 1278 |
subresult = point_point_distance(point, &p); |
| 1279 |
if (result > subresult) |
| 1280 |
result = subresult; |
| 1281 |
} |
| 1282 |
|
| 1283 |
return result; |
| 1284 |
} |
| 1285 |
|
| 1286 |
static bool |
| 1287 |
gist_point_consistent_internal(StrategyNumber strategy, |
| 1288 |
bool isLeaf, BOX *key, Point *query) |
| 1289 |
{ |
| 1290 |
bool result = false; |
| 1291 |
|
| 1292 |
switch (strategy) |
| 1293 |
{ |
| 1294 |
case RTLeftStrategyNumber: |
| 1295 |
result = FPlt(key->low.x, query->x); |
| 1296 |
break; |
| 1297 |
case RTRightStrategyNumber: |
| 1298 |
result = FPgt(key->high.x, query->x); |
| 1299 |
break; |
| 1300 |
case RTAboveStrategyNumber: |
| 1301 |
result = FPgt(key->high.y, query->y); |
| 1302 |
break; |
| 1303 |
case RTBelowStrategyNumber: |
| 1304 |
result = FPlt(key->low.y, query->y); |
| 1305 |
break; |
| 1306 |
case RTSameStrategyNumber: |
| 1307 |
if (isLeaf) |
| 1308 |
{ |
| 1309 |
/* key.high must equal key.low, so we can disregard it */ |
| 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; /* keep compiler quiet */ |
| 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 |
|
| 1336 |
Datum |
| 1337 |
gist_point_consistent(PG_FUNCTION_ARGS) |
| 1338 |
{ |
| 1339 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 1340 |
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); |
| 1341 |
bool *recheck = (bool *) PG_GETARG_POINTER(4); |
| 1342 |
bool result; |
| 1343 |
StrategyNumber strategyGroup; |
| 1344 |
|
| 1345 |
/* |
| 1346 |
* We have to remap these strategy numbers to get this klugy |
| 1347 |
* classification logic to work. |
| 1348 |
*/ |
| 1349 |
if (strategy == RTOldBelowStrategyNumber) |
| 1350 |
strategy = RTBelowStrategyNumber; |
| 1351 |
else if (strategy == RTOldAboveStrategyNumber) |
| 1352 |
strategy = RTAboveStrategyNumber; |
| 1353 |
|
| 1354 |
strategyGroup = strategy / GeoStrategyNumberOffset; |
| 1355 |
switch (strategyGroup) |
| 1356 |
{ |
| 1357 |
case PointStrategyNumberGroup: |
| 1358 |
result = gist_point_consistent_internal(strategy % GeoStrategyNumberOffset, |
| 1359 |
GIST_LEAF(entry), |
| 1360 |
DatumGetBoxP(entry->key), |
| 1361 |
PG_GETARG_POINT_P(1)); |
| 1362 |
*recheck = false; |
| 1363 |
break; |
| 1364 |
case BoxStrategyNumberGroup: |
| 1365 |
{ |
| 1366 |
/* |
| 1367 |
* The only operator in this group is point <@ box (on_pb), so |
| 1368 |
* we needn't examine strategy again. |
| 1369 |
* |
| 1370 |
* For historical reasons, on_pb uses exact rather than fuzzy |
| 1371 |
* comparisons. We could use box_overlap when at an internal |
| 1372 |
* page, but that would lead to possibly visiting child pages |
| 1373 |
* uselessly, because box_overlap uses fuzzy comparisons. |
| 1374 |
* Instead we write a non-fuzzy overlap test. The same code |
| 1375 |
* will also serve for leaf-page tests, since leaf keys have |
| 1376 |
* high == low. |
| 1377 |
*/ |
| 1378 |
BOX *query, |
| 1379 |
*key; |
| 1380 |
|
| 1381 |
query = PG_GETARG_BOX_P(1); |
| 1382 |
key = DatumGetBoxP(entry->key); |
| 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; |
| 1391 |
case PolygonStrategyNumberGroup: |
| 1392 |
{ |
| 1393 |
POLYGON *query = PG_GETARG_POLYGON_P(1); |
| 1394 |
|
| 1395 |
result = DatumGetBool(DirectFunctionCall5(gist_poly_consistent, |
| 1396 |
PointerGetDatum(entry), |
| 1397 |
PolygonPGetDatum(query), |
| 1398 |
Int16GetDatum(RTOverlapStrategyNumber), |
| 1399 |
0, PointerGetDatum(recheck))); |
| 1400 |
|
| 1401 |
if (GIST_LEAF(entry) && result) |
| 1402 |
{ |
| 1403 |
/* |
| 1404 |
* We are on leaf page and quick check shows overlapping |
| 1405 |
* of polygon's bounding box and point |
| 1406 |
*/ |
| 1407 |
BOX *box = DatumGetBoxP(entry->key); |
| 1408 |
|
| 1409 |
Assert(box->high.x == box->low.x |
| 1410 |
&& box->high.y == box->low.y); |
| 1411 |
result = DatumGetBool(DirectFunctionCall2(poly_contain_pt, |
| 1412 |
PolygonPGetDatum(query), |
| 1413 |
PointPGetDatum(&box->high))); |
| 1414 |
*recheck = false; |
| 1415 |
} |
| 1416 |
} |
| 1417 |
break; |
| 1418 |
case CircleStrategyNumberGroup: |
| 1419 |
{ |
| 1420 |
CIRCLE *query = PG_GETARG_CIRCLE_P(1); |
| 1421 |
|
| 1422 |
result = DatumGetBool(DirectFunctionCall5(gist_circle_consistent, |
| 1423 |
PointerGetDatum(entry), |
| 1424 |
CirclePGetDatum(query), |
| 1425 |
Int16GetDatum(RTOverlapStrategyNumber), |
| 1426 |
0, PointerGetDatum(recheck))); |
| 1427 |
|
| 1428 |
if (GIST_LEAF(entry) && result) |
| 1429 |
{ |
| 1430 |
/* |
| 1431 |
* We are on leaf page and quick check shows overlapping |
| 1432 |
* of polygon's bounding box and point |
| 1433 |
*/ |
| 1434 |
BOX *box = DatumGetBoxP(entry->key); |
| 1435 |
|
| 1436 |
Assert(box->high.x == box->low.x |
| 1437 |
&& box->high.y == box->low.y); |
| 1438 |
result = DatumGetBool(DirectFunctionCall2(circle_contain_pt, |
| 1439 |
CirclePGetDatum(query), |
| 1440 |
PointPGetDatum(&box->high))); |
| 1441 |
*recheck = false; |
| 1442 |
} |
| 1443 |
} |
| 1444 |
break; |
| 1445 |
default: |
| 1446 |
elog(ERROR, "unrecognized strategy number: %d", strategy); |
| 1447 |
result = false; /* keep compiler quiet */ |
| 1448 |
break; |
| 1449 |
} |
| 1450 |
|
| 1451 |
PG_RETURN_BOOL(result); |
| 1452 |
} |
| 1453 |
|
| 1454 |
Datum |
| 1455 |
gist_point_distance(PG_FUNCTION_ARGS) |
| 1456 |
{ |
| 1457 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 1458 |
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); |
| 1459 |
float8 distance; |
| 1460 |
StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset; |
| 1461 |
|
| 1462 |
switch (strategyGroup) |
| 1463 |
{ |
| 1464 |
case PointStrategyNumberGroup: |
| 1465 |
distance = computeDistance(GIST_LEAF(entry), |
| 1466 |
DatumGetBoxP(entry->key), |
| 1467 |
PG_GETARG_POINT_P(1)); |
| 1468 |
break; |
| 1469 |
default: |
| 1470 |
elog(ERROR, "unrecognized strategy number: %d", strategy); |
| 1471 |
distance = 0.0; /* keep compiler quiet */ |
| 1472 |
break; |
| 1473 |
} |
| 1474 |
|
| 1475 |
PG_RETURN_FLOAT8(distance); |
| 1476 |
} |
| 1477 |
|
| 1478 |
static float8 |
| 1479 |
gist_bbox_distance(GISTENTRY *entry, Datum query, StrategyNumber strategy) |
| 1480 |
{ |
| 1481 |
float8 distance; |
| 1482 |
StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset; |
| 1483 |
|
| 1484 |
switch (strategyGroup) |
| 1485 |
{ |
| 1486 |
case PointStrategyNumberGroup: |
| 1487 |
distance = computeDistance(false, |
| 1488 |
DatumGetBoxP(entry->key), |
| 1489 |
DatumGetPointP(query)); |
| 1490 |
break; |
| 1491 |
default: |
| 1492 |
elog(ERROR, "unrecognized strategy number: %d", strategy); |
| 1493 |
distance = 0.0; /* keep compiler quiet */ |
| 1494 |
} |
| 1495 |
|
| 1496 |
return distance; |
| 1497 |
} |
| 1498 |
|
| 1499 |
Datum |
| 1500 |
gist_box_distance(PG_FUNCTION_ARGS) |
| 1501 |
{ |
| 1502 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 1503 |
Datum query = PG_GETARG_DATUM(1); |
| 1504 |
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); |
| 1505 |
|
| 1506 |
/* Oid subtype = PG_GETARG_OID(3); */ |
| 1507 |
/* bool *recheck = (bool *) PG_GETARG_POINTER(4); */ |
| 1508 |
float8 distance; |
| 1509 |
|
| 1510 |
distance = gist_bbox_distance(entry, query, strategy); |
| 1511 |
|
| 1512 |
PG_RETURN_FLOAT8(distance); |
| 1513 |
} |
| 1514 |
|
| 1515 |
/* |
| 1516 |
* The inexact GiST distance methods for geometric types that store bounding |
| 1517 |
* boxes. |
| 1518 |
* |
| 1519 |
* Compute lossy distance from point to index entries. The result is inexact |
| 1520 |
* because index entries are bounding boxes, not the exact shapes of the |
| 1521 |
* indexed geometric types. We use distance from point to MBR of index entry. |
| 1522 |
* This is a lower bound estimate of distance from point to indexed geometric |
| 1523 |
* type. |
| 1524 |
*/ |
| 1525 |
Datum |
| 1526 |
gist_circle_distance(PG_FUNCTION_ARGS) |
| 1527 |
{ |
| 1528 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 1529 |
Datum query = PG_GETARG_DATUM(1); |
| 1530 |
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); |
| 1531 |
|
| 1532 |
/* Oid subtype = PG_GETARG_OID(3); */ |
| 1533 |
bool *recheck = (bool *) PG_GETARG_POINTER(4); |
| 1534 |
float8 distance; |
| 1535 |
|
| 1536 |
distance = gist_bbox_distance(entry, query, strategy); |
| 1537 |
*recheck = true; |
| 1538 |
|
| 1539 |
PG_RETURN_FLOAT8(distance); |
| 1540 |
} |
| 1541 |
|
| 1542 |
Datum |
| 1543 |
gist_poly_distance(PG_FUNCTION_ARGS) |
| 1544 |
{ |
| 1545 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 1546 |
Datum query = PG_GETARG_DATUM(1); |
| 1547 |
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); |
| 1548 |
|
| 1549 |
/* Oid subtype = PG_GETARG_OID(3); */ |
| 1550 |
bool *recheck = (bool *) PG_GETARG_POINTER(4); |
| 1551 |
float8 distance; |
| 1552 |
|
| 1553 |
distance = gist_bbox_distance(entry, query, strategy); |
| 1554 |
*recheck = true; |
| 1555 |
|
| 1556 |
PG_RETURN_FLOAT8(distance); |
| 1557 |
} |
| 1558 |
|
| 1559 |
/* |
| 1560 |
* Z-order routines for fast index build |
| 1561 |
*/ |
| 1562 |
|
| 1563 |
/* |
| 1564 |
* Compute Z-value of a point |
| 1565 |
* |
| 1566 |
* Z-order (also known as Morton Code) maps a two-dimensional point to a |
| 1567 |
* single integer, in a way that preserves locality. Points that are close in |
| 1568 |
* the two-dimensional space are mapped to integer that are not far from each |
| 1569 |
* other. We do that by interleaving the bits in the X and Y components. |
| 1570 |
* |
| 1571 |
* Morton Code is normally defined only for integers, but the X and Y values |
| 1572 |
* of a point are floating point. We expect floats to be in IEEE format. |
| 1573 |
*/ |
| 1574 |
static uint64 |
| 1575 |
point_zorder_internal(float4 x, float4 y) |
| 1576 |
{ |
| 1577 |
uint32 ix = ieee_float32_to_uint32(x); |
| 1578 |
uint32 iy = ieee_float32_to_uint32(y); |
| 1579 |
|
| 1580 |
/* Interleave the bits */ |
| 1581 |
return part_bits32_by2(ix) | (part_bits32_by2(iy) << 1); |
| 1582 |
} |
| 1583 |
|
| 1584 |
/* Interleave 32 bits with zeroes */ |
| 1585 |
static uint64 |
| 1586 |
part_bits32_by2(uint32 x) |
| 1587 |
{ |
| 1588 |
uint64 n = x; |
| 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 |
* Convert a 32-bit IEEE float to uint32 in a way that preserves the ordering |
| 1601 |
*/ |
| 1602 |
static uint32 |
| 1603 |
ieee_float32_to_uint32(float f) |
| 1604 |
{ |
| 1605 |
/*---- |
| 1606 |
* |
| 1607 |
* IEEE 754 floating point format |
| 1608 |
* ------------------------------ |
| 1609 |
* |
| 1610 |
* IEEE 754 floating point numbers have this format: |
| 1611 |
* |
| 1612 |
* exponent (8 bits) |
| 1613 |
* | |
| 1614 |
* s eeeeeeee mmmmmmmmmmmmmmmmmmmmmmm |
| 1615 |
* | | |
| 1616 |
* sign mantissa (23 bits) |
| 1617 |
* |
| 1618 |
* Infinity has all bits in the exponent set and the mantissa is all |
| 1619 |
* zeros. Negative infinity is the same but with the sign bit set. |
| 1620 |
* |
| 1621 |
* NaNs are represented with all bits in the exponent set, and the least |
| 1622 |
* significant bit in the mantissa also set. The rest of the mantissa bits |
| 1623 |
* can be used to distinguish different kinds of NaNs. |
| 1624 |
* |
| 1625 |
* The IEEE format has the nice property that when you take the bit |
| 1626 |
* representation and interpret it as an integer, the order is preserved, |
| 1627 |
* except for the sign. That holds for the +-Infinity values too. |
| 1628 |
* |
| 1629 |
* Mapping to uint32 |
| 1630 |
* ----------------- |
| 1631 |
* |
| 1632 |
* In order to have a smooth transition from negative to positive numbers, |
| 1633 |
* we map floats to unsigned integers like this: |
| 1634 |
* |
| 1635 |
* x < 0 to range 0-7FFFFFFF |
| 1636 |
* x = 0 to value 8000000 (both positive and negative zero) |
| 1637 |
* x > 0 to range 8000001-FFFFFFFF |
| 1638 |
* |
| 1639 |
* We don't care to distinguish different kind of NaNs, so they are all |
| 1640 |
* mapped to the same arbitrary value, FFFFFFFF. Because of the IEEE bit |
| 1641 |
* representation of NaNs, there aren't any non-NaN values that would be |
| 1642 |
* mapped to FFFFFFFF. In fact, there is a range of unused values on both |
| 1643 |
* ends of the uint32 space. |
| 1644 |
*/ |
| 1645 |
if (isnan(f)) |
| 1646 |
return 0xFFFFFFFF; |
| 1647 |
else |
| 1648 |
{ |
| 1649 |
union |
| 1650 |
{ |
| 1651 |
float f; |
| 1652 |
uint32 i; |
| 1653 |
} u; |
| 1654 |
|
| 1655 |
u.f = f; |
| 1656 |
|
| 1657 |
/* Check the sign bit */ |
| 1658 |
if ((u.i & 0x80000000) != 0) |
| 1659 |
{ |
| 1660 |
/* |
| 1661 |
* Map the negative value to range 0-7FFFFFFF. This flips the sign |
| 1662 |
* bit to 0 in the same instruction. |
| 1663 |
*/ |
| 1664 |
Assert(f <= 0); /* can be -0 */ |
| 1665 |
u.i ^= 0xFFFFFFFF; |
| 1666 |
} |
| 1667 |
else |
| 1668 |
{ |
| 1669 |
/* Map the positive value (or 0) to range 80000000-FFFFFFFF */ |
| 1670 |
u.i |= 0x80000000; |
| 1671 |
} |
| 1672 |
|
| 1673 |
return u.i; |
| 1674 |
} |
| 1675 |
} |
| 1676 |
|
| 1677 |
/* |
| 1678 |
* Compare the Z-order of points |
| 1679 |
*/ |
| 1680 |
static int |
| 1681 |
gist_bbox_zorder_cmp(Datum a, Datum b, SortSupport ssup) |
| 1682 |
{ |
| 1683 |
Point *p1 = &(DatumGetBoxP(a)->low); |
| 1684 |
Point *p2 = &(DatumGetBoxP(b)->low); |
| 1685 |
uint64 z1; |
| 1686 |
uint64 z2; |
| 1687 |
|
| 1688 |
/* |
| 1689 |
* Do a quick check for equality first. It's not clear if this is worth it |
| 1690 |
* in general, but certainly is when used as tie-breaker with abbreviated |
| 1691 |
* keys, |
| 1692 |
*/ |
| 1693 |
if (p1->x == p2->x && p1->y == p2->y) |
| 1694 |
return 0; |
| 1695 |
|
| 1696 |
z1 = point_zorder_internal(p1->x, p1->y); |
| 1697 |
z2 = point_zorder_internal(p2->x, p2->y); |
| 1698 |
if (z1 > z2) |
| 1699 |
return 1; |
| 1700 |
else if (z1 < z2) |
| 1701 |
return -1; |
| 1702 |
else |
| 1703 |
return 0; |
| 1704 |
} |
| 1705 |
|
| 1706 |
/* |
| 1707 |
* Abbreviated version of Z-order comparison |
| 1708 |
* |
| 1709 |
* The abbreviated format is a Z-order value computed from the two 32-bit |
| 1710 |
* floats. If SIZEOF_DATUM == 8, the 64-bit Z-order value fits fully in the |
| 1711 |
* abbreviated Datum, otherwise use its most significant bits. |
| 1712 |
*/ |
| 1713 |
static Datum |
| 1714 |
gist_bbox_zorder_abbrev_convert(Datum original, SortSupport ssup) |
| 1715 |
{ |
| 1716 |
Point *p = &(DatumGetBoxP(original)->low); |
| 1717 |
uint64 z; |
| 1718 |
|
| 1719 |
z = point_zorder_internal(p->x, p->y); |
| 1720 |
|
| 1721 |
#if SIZEOF_DATUM == 8 |
| 1722 |
return (Datum) z; |
| 1723 |
#else |
| 1724 |
return (Datum) (z >> 32); |
| 1725 |
#endif |
| 1726 |
} |
| 1727 |
|
| 1728 |
/* |
| 1729 |
* We never consider aborting the abbreviation. |
| 1730 |
* |
| 1731 |
* On 64-bit systems, the abbreviation is not lossy so it is always |
| 1732 |
* worthwhile. (Perhaps it's not on 32-bit systems, but we don't bother |
| 1733 |
* with logic to decide.) |
| 1734 |
*/ |
| 1735 |
static bool |
| 1736 |
gist_bbox_zorder_abbrev_abort(int memtupcount, SortSupport ssup) |
| 1737 |
{ |
| 1738 |
return false; |
| 1739 |
} |
| 1740 |
|
| 1741 |
/* |
| 1742 |
* Sort support routine for fast GiST index build by sorting. |
| 1743 |
*/ |
| 1744 |
Datum |
| 1745 |
gist_point_sortsupport(PG_FUNCTION_ARGS) |
| 1746 |
{ |
| 1747 |
SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0); |
| 1748 |
|
| 1749 |
if (ssup->abbreviate) |
| 1750 |
{ |
| 1751 |
ssup->comparator = ssup_datum_unsigned_cmp; |
| 1752 |
ssup->abbrev_converter = gist_bbox_zorder_abbrev_convert; |
| 1753 |
ssup->abbrev_abort = gist_bbox_zorder_abbrev_abort; |
| 1754 |
ssup->abbrev_full_comparator = gist_bbox_zorder_cmp; |
| 1755 |
} |
| 1756 |
else |
| 1757 |
{ |
| 1758 |
ssup->comparator = gist_bbox_zorder_cmp; |
| 1759 |
} |
| 1760 |
PG_RETURN_VOID(); |
| 1761 |
} |