1 #include "gist.h"
2
3 /*
4 * Functions needed to build a GIST index
5 */
6
7 PG_FUNCTION_INFO_V1(pointkey_in);
8 PG_FUNCTION_INFO_V1(pointkey_out);
9 PG_FUNCTION_INFO_V1(pointkey_volume);
10 PG_FUNCTION_INFO_V1(pointkey_area);
11 PG_FUNCTION_INFO_V1(pointkey_perimeter);
12 PG_FUNCTION_INFO_V1(spherekey_in);
13 PG_FUNCTION_INFO_V1(spherekey_out);
14 PG_FUNCTION_INFO_V1(g_spherekey_decompress);
15 PG_FUNCTION_INFO_V1(g_scircle_compress);
16 PG_FUNCTION_INFO_V1(g_spoint_compress);
17 PG_FUNCTION_INFO_V1(g_sline_compress);
18 PG_FUNCTION_INFO_V1(g_spath_compress);
19 PG_FUNCTION_INFO_V1(g_spoly_compress);
20 PG_FUNCTION_INFO_V1(g_sellipse_compress);
21 PG_FUNCTION_INFO_V1(g_sbox_compress);
22 PG_FUNCTION_INFO_V1(g_spherekey_union);
23 PG_FUNCTION_INFO_V1(g_spherekey_same);
24 PG_FUNCTION_INFO_V1(g_spoint_consistent);
25 PG_FUNCTION_INFO_V1(g_scircle_consistent);
26 PG_FUNCTION_INFO_V1(g_sline_consistent);
27 PG_FUNCTION_INFO_V1(g_spath_consistent);
28 PG_FUNCTION_INFO_V1(g_spoly_consistent);
29 PG_FUNCTION_INFO_V1(g_sellipse_consistent);
30 PG_FUNCTION_INFO_V1(g_sbox_consistent);
31 PG_FUNCTION_INFO_V1(g_spherekey_penalty);
32 PG_FUNCTION_INFO_V1(g_spherekey_picksplit);
33
34 /*
35 * Returns the relationship between two keys as PGS_KEY_REL.
36 */
37 uchar
spherekey_interleave(const int32 * k1,const int32 * k2)38 spherekey_interleave(const int32 *k1, const int32 *k2)
39 {
40 uchar i;
41 char tb;
42
43 /* i represents x,y,z */
44 tb = 0;
45 for (i = 0; i < 3; i++)
46 {
47 tb |= ((k2[i] > k1[i + 3]) || (k1[i] > k2[i + 3]));
48 if (tb)
49 break;
50 }
51 if (tb)
52 {
53 return SCKEY_DISJ;
54 }
55 tb = 1;
56 for (i = 0; i < 3; i++)
57 {
58 tb &= ((k1[i] == k2[i]) && (k1[i + 3] == k2[i + 3]));
59 if (!tb)
60 break;
61 }
62 if (tb)
63 {
64 return SCKEY_SAME;
65 }
66 tb = 1;
67 for (i = 0; i < 3; i++)
68 {
69 tb &= (k1[i] <= k2[i] && k1[i + 3] >= k2[i + 3]);
70 if (!tb)
71 break;
72 }
73 if (tb)
74 {
75 /* v2 in v1 */
76 return SCKEY_IN;
77 }
78 return SCKEY_OVERLAP;
79 }
80
81 Datum
spherekey_in(PG_FUNCTION_ARGS)82 spherekey_in(PG_FUNCTION_ARGS)
83 {
84 elog(ERROR, "Not implemented!");
85 PG_RETURN_POINTER(NULL);
86 }
87
88 Datum
spherekey_out(PG_FUNCTION_ARGS)89 spherekey_out(PG_FUNCTION_ARGS)
90 {
91 const float8 ks = (float8) MAXCVALUE;
92 int32 *k = (int32 *) PG_GETARG_POINTER(0);
93 char *buffer = (char *) palloc(1024);
94
95 sprintf(buffer, "(%.9f,%.9f,%.9f),(%.9f,%.9f,%.9f)",
96 k[0] / ks, k[1] / ks, k[2] / ks,
97 k[3] / ks, k[4] / ks, k[5] / ks);
98
99 PG_RETURN_CSTRING(buffer);
100
101 }
102
103 static bool
get_sizes(GiSTSPointKey * k,float8 sizes[3])104 get_sizes(GiSTSPointKey *k, float8 sizes[3])
105 {
106 int i;
107 const float8 ks = (float8) MAXCVALUE;
108
109 if (IS_LEAF(k))
110 return false;
111
112 for (i = 0; i < 3; i++)
113 {
114 sizes[i] = (((uint64) k->k[i + 3] - (uint64) k->k[i]) + 1) / ks;
115 }
116 return true;
117 }
118
119 Datum
pointkey_volume(PG_FUNCTION_ARGS)120 pointkey_volume(PG_FUNCTION_ARGS)
121 {
122 GiSTSPointKey *k = (GiSTSPointKey *) PG_GETARG_POINTER(0);
123 float8 sizes[3];
124
125 if (!get_sizes(k, sizes))
126 PG_RETURN_FLOAT8(0.0);
127
128 PG_RETURN_FLOAT8(sizes[0] * sizes[1] * sizes[2]);
129 }
130
131 Datum
pointkey_area(PG_FUNCTION_ARGS)132 pointkey_area(PG_FUNCTION_ARGS)
133 {
134 GiSTSPointKey *k = (GiSTSPointKey *) PG_GETARG_POINTER(0);
135 float8 sizes[3];
136
137 if (!get_sizes(k, sizes))
138 PG_RETURN_FLOAT8(0.0);
139
140 PG_RETURN_FLOAT8(sizes[0] * sizes[1] +
141 sizes[0] * sizes[2] +
142 sizes[1] * sizes[2]);
143 }
144
145 Datum
pointkey_perimeter(PG_FUNCTION_ARGS)146 pointkey_perimeter(PG_FUNCTION_ARGS)
147 {
148 GiSTSPointKey *k = (GiSTSPointKey *) PG_GETARG_POINTER(0);
149 float8 sizes[3];
150
151 if (!get_sizes(k, sizes))
152 PG_RETURN_FLOAT8(0.0);
153
154 PG_RETURN_FLOAT8(sizes[0] + sizes[1] + sizes[2]);
155 }
156
157 Datum
pointkey_in(PG_FUNCTION_ARGS)158 pointkey_in(PG_FUNCTION_ARGS)
159 {
160 elog(ERROR, "Not implemented!");
161 PG_RETURN_POINTER(NULL);
162 }
163
164 Datum
pointkey_out(PG_FUNCTION_ARGS)165 pointkey_out(PG_FUNCTION_ARGS)
166 {
167 const float8 ks = (float8) MAXCVALUE;
168 GiSTSPointKey *k = (GiSTSPointKey *) PG_GETARG_POINTER(0);
169 char *buffer = (char *) palloc(1024);
170
171 if (IS_LEAF(k))
172 {
173 sprintf(buffer, "(%.9f,%.9f)", k->lng, k->lat);
174 }
175 else
176 {
177 sprintf(buffer, "(%.9f,%.9f,%.9f),(%.9f,%.9f,%.9f)",
178 k->k[0] / ks, k->k[1] / ks, k->k[2] / ks,
179 k->k[3] / ks, k->k[4] / ks, k->k[5] / ks);
180 }
181
182 PG_RETURN_CSTRING(buffer);
183 }
184
185 Datum
g_spherekey_decompress(PG_FUNCTION_ARGS)186 g_spherekey_decompress(PG_FUNCTION_ARGS)
187 {
188 PG_RETURN_DATUM(PG_GETARG_DATUM(0));
189 }
190
191 /*
192 * General compress method for all data types. Uses genkey to generate key
193 * value (see key.c).
194 */
195 #define PGS_COMPRESS(type, genkey, detoast) \
196 do \
197 { \
198 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); \
199 GISTENTRY *retval; \
200 if (entry->leafkey) \
201 { \
202 retval = (GISTENTRY *) palloc(sizeof(GISTENTRY)); \
203 if (DatumGetPointer(entry->key) != NULL) \
204 { \
205 int32 *k = (int32 *) palloc(KEYSIZE); \
206 if (detoast) \
207 genkey(k, (type *) DatumGetPointer(PG_DETOAST_DATUM(entry->key))); \
208 else \
209 genkey(k, (type *) DatumGetPointer(entry->key)); \
210 gistentryinit(*retval, PointerGetDatum(k), \
211 entry->rel, entry->page, \
212 entry->offset, false); \
213 } \
214 else \
215 { \
216 gistentryinit(*retval, (Datum) 0, \
217 entry->rel, entry->page, \
218 entry->offset, false); \
219 } \
220 } \
221 else \
222 { \
223 retval = entry; \
224 } \
225 PG_RETURN_POINTER(retval); \
226 } \
227 while (0)
228
229 Datum
g_scircle_compress(PG_FUNCTION_ARGS)230 g_scircle_compress(PG_FUNCTION_ARGS)
231 {
232 PGS_COMPRESS(SCIRCLE, spherecircle_gen_key, 0);
233 }
234
235 Datum
g_spoint_compress(PG_FUNCTION_ARGS)236 g_spoint_compress(PG_FUNCTION_ARGS)
237 {
238 PGS_COMPRESS(SPoint, spherepoint_gen_key, 0);
239 }
240
241 Datum
g_sline_compress(PG_FUNCTION_ARGS)242 g_sline_compress(PG_FUNCTION_ARGS)
243 {
244 PGS_COMPRESS(SLine, sphereline_gen_key, 0);
245 }
246
247 Datum
g_spath_compress(PG_FUNCTION_ARGS)248 g_spath_compress(PG_FUNCTION_ARGS)
249 {
250 PGS_COMPRESS(SPATH, spherepath_gen_key, 1);
251 }
252
253 Datum
g_spoly_compress(PG_FUNCTION_ARGS)254 g_spoly_compress(PG_FUNCTION_ARGS)
255 {
256 PGS_COMPRESS(SPOLY, spherepoly_gen_key, 1);
257 }
258
259 Datum
g_sellipse_compress(PG_FUNCTION_ARGS)260 g_sellipse_compress(PG_FUNCTION_ARGS)
261 {
262 PGS_COMPRESS(SELLIPSE, sphereellipse_gen_key, 0);
263 }
264
265 Datum
g_sbox_compress(PG_FUNCTION_ARGS)266 g_sbox_compress(PG_FUNCTION_ARGS)
267 {
268 PGS_COMPRESS(SBOX, spherebox_gen_key, 0);
269 }
270
271 Datum
g_spherekey_union(PG_FUNCTION_ARGS)272 g_spherekey_union(PG_FUNCTION_ARGS)
273 {
274 GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
275 int *sizep = (int *) PG_GETARG_POINTER(1);
276 int numranges, i;
277 int32 *ret = (int32 *) palloc(KEYSIZE);
278
279 numranges = entryvec->n;
280 memcpy((void *) ret,
281 (void *) DatumGetPointer(entryvec->vector[0].key),
282 KEYSIZE);
283
284 for (i = 1; i < numranges; i++)
285 {
286 spherekey_union_two(ret,
287 (int32 *) DatumGetPointer(entryvec->vector[i].key));
288 }
289 *sizep = KEYSIZE;
290 PG_RETURN_POINTER(ret);
291 }
292
293 Datum
g_spherekey_same(PG_FUNCTION_ARGS)294 g_spherekey_same(PG_FUNCTION_ARGS)
295 {
296 int32 *c1 = (int32 *) PG_GETARG_POINTER(0);
297 int32 *c2 = (int32 *) PG_GETARG_POINTER(1);
298 bool *result = (bool *) PG_GETARG_POINTER(2);
299 int i;
300
301 *result = true;
302
303 if (c1 && c2)
304 {
305 for (i = 0; i < 6; i++)
306 {
307 *result &= (c1[i] == c2[i]);
308 }
309 }
310 else
311 {
312 *result = (c1 == NULL && c2 == NULL) ? true : false;
313 }
314
315 PG_RETURN_POINTER(result);
316 }
317
318 /*
319 * General interleave method with query cache. genkey function is used to
320 * generate the key value. "dir" defines which value is the first for
321 * spherekey_interleave: 0 - query key, 1 - entry key.
322 */
323 #define SCK_INTERLEAVE(type, genkey, dir) \
324 do \
325 { \
326 int32 * q = NULL; \
327 if (!gq_cache_get_value (PGS_TYPE_##type, query, &q)) \
328 { \
329 q = (int32 *) malloc(KEYSIZE); \
330 genkey(q, (type * )query); \
331 gq_cache_set_value(PGS_TYPE_##type, query, q); \
332 free(q); \
333 gq_cache_get_value(PGS_TYPE_##type, query, &q); \
334 } \
335 if (dir) \
336 i = spherekey_interleave(ent, q); \
337 else \
338 i = spherekey_interleave(q , ent); \
339 } \
340 while (0)
341
342
343 Datum
g_spoint_consistent(PG_FUNCTION_ARGS)344 g_spoint_consistent(PG_FUNCTION_ARGS)
345 {
346 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
347 void *query = (void *) PG_GETARG_POINTER(1);
348 StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
349 bool result = false;
350
351 if (DatumGetPointer(entry->key) == NULL || !query)
352 {
353 PG_RETURN_BOOL(false);
354 }
355 else
356 {
357 bool *recheck = (bool *) PG_GETARG_POINTER(4);
358 int32 *ent = (int32 *) DatumGetPointer(entry->key);
359 int i = SCKEY_DISJ;
360
361 *recheck = true;
362
363 switch (strategy)
364 {
365 case 1:
366 SCK_INTERLEAVE(SPoint, spherepoint_gen_key, 1);
367 break;
368 case 11:
369 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
370 break;
371 case 12:
372 SCK_INTERLEAVE(SLine, sphereline_gen_key, 0);
373 break;
374 case 13:
375 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 0);
376 break;
377 case 14:
378 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
379 break;
380 case 15:
381 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
382 break;
383 case 16:
384 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
385 break;
386 case 37:
387 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
388 break;
389 case 38:
390 SCK_INTERLEAVE(SLine, sphereline_gen_key, 0);
391 break;
392 case 39:
393 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 0);
394 break;
395 case 40:
396 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
397 break;
398 case 41:
399 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
400 break;
401 case 42:
402 SCK_INTERLEAVE(SBOX, spherebox_gen_key , 0);
403 break;
404 }
405
406 if (GIST_LEAF(entry))
407 {
408 switch (strategy)
409 {
410 case 1:
411 if (i == SCKEY_SAME)
412 result = true;
413 break;
414 default:
415 if (i > SCKEY_OVERLAP)
416 result = true;
417 break;
418 }
419 }
420 else
421 {
422 switch (strategy)
423 {
424 case 1:
425 if (i > SCKEY_OVERLAP)
426 result = true;
427 break;
428 default:
429 if (i > SCKEY_DISJ)
430 result = true;
431 break;
432 }
433
434 }
435 PG_RETURN_BOOL(result);
436 }
437 PG_RETURN_BOOL(false);
438 }
439
440 Datum
g_scircle_consistent(PG_FUNCTION_ARGS)441 g_scircle_consistent(PG_FUNCTION_ARGS)
442 {
443 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
444 void *query = (void *) PG_GETARG_POINTER(1);
445 StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
446 bool result = false;
447
448 if (DatumGetPointer(entry->key) == NULL || !query)
449 {
450 PG_RETURN_BOOL(false);
451 }
452 else
453 {
454 bool *recheck = (bool *) PG_GETARG_POINTER(4);
455 int32 *ent = (int32 *) DatumGetPointer(entry->key);
456 int i = SCKEY_DISJ;
457
458 *recheck = true;
459
460 switch (strategy)
461 {
462 case 1:
463 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 1);
464 break;
465 case 11:
466 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
467 break;
468 case 12:
469 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
470 break;
471 case 13:
472 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
473 break;
474 case 14:
475 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
476 break;
477 case 21:
478 SCK_INTERLEAVE(SPoint, spherepoint_gen_key, 1);
479 break;
480 case 22:
481 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 1);
482 break;
483 case 23:
484 SCK_INTERLEAVE(SLine, sphereline_gen_key, 1);
485 break;
486 case 24:
487 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 1);
488 break;
489 case 25:
490 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 1);
491 break;
492 case 26:
493 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 1);
494 break;
495 case 27:
496 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 1);
497 break;
498 case 31:
499 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
500 break;
501 case 32:
502 SCK_INTERLEAVE(SLine, sphereline_gen_key, 0);
503 break;
504 case 33:
505 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 0);
506 break;
507 case 34:
508 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
509 break;
510 case 35:
511 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
512 break;
513 case 36:
514 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
515 break;
516 case 37:
517 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
518 break;
519 case 38:
520 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
521 break;
522 case 39:
523 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
524 break;
525 case 40:
526 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
527 break;
528 case 43:
529 SCK_INTERLEAVE(SPoint, spherepoint_gen_key, 1);
530 break;
531 case 44:
532 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 1);
533 break;
534 case 45:
535 SCK_INTERLEAVE(SLine, sphereline_gen_key, 1);
536 break;
537 case 46:
538 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 1);
539 break;
540 case 47:
541 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 1);
542 break;
543 case 48:
544 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 1);
545 break;
546 case 49:
547 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 1);
548 break;
549 }
550
551 if (GIST_LEAF(entry))
552 {
553 switch (strategy)
554 {
555 case 1:
556 if (i == SCKEY_SAME)
557 result = true;
558 break;
559 default:
560 if (i > SCKEY_DISJ)
561 result = true;
562 break;
563 }
564 }
565 else
566 {
567 switch (strategy)
568 {
569 case 1:
570 if (i > SCKEY_OVERLAP)
571 result = true;
572 break;
573 default:
574 if (i > SCKEY_DISJ)
575 result = true;
576 break;
577 }
578 }
579 PG_RETURN_BOOL(result);
580 }
581 PG_RETURN_BOOL(false);
582 }
583
584 Datum
g_sline_consistent(PG_FUNCTION_ARGS)585 g_sline_consistent(PG_FUNCTION_ARGS)
586 {
587 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
588 void *query = (void *) PG_GETARG_POINTER(1);
589 StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
590 bool result = false;
591
592 if (DatumGetPointer(entry->key) == NULL || !query)
593 {
594 PG_RETURN_BOOL(false);
595 }
596 else
597 {
598 bool *recheck = (bool *) PG_GETARG_POINTER(4);
599 int32 *ent = (int32 *) DatumGetPointer(entry->key);
600 int i = SCKEY_DISJ;
601
602 *recheck = true;
603
604 switch (strategy)
605 {
606 case 1:
607 case 2:
608 SCK_INTERLEAVE(SLine, sphereline_gen_key, 1);
609 break;
610 case 11:
611 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
612 break;
613 case 12:
614 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
615 break;
616 case 13:
617 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
618 break;
619 case 14:
620 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
621 break;
622 case 21:
623 SCK_INTERLEAVE(SPoint, spherepoint_gen_key, 1);
624 break;
625 case 31:
626 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 1);
627 break;
628 case 32:
629 SCK_INTERLEAVE(SLine, sphereline_gen_key, 1);
630 break;
631 case 33:
632 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 1);
633 break;
634 case 34:
635 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 1);
636 break;
637 case 35:
638 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 1);
639 break;
640 case 36:
641 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 1);
642 break;
643 case 37:
644 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
645 break;
646 case 38:
647 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
648 break;
649 case 39:
650 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
651 break;
652 case 40:
653 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
654 break;
655 case 43:
656 SCK_INTERLEAVE(SPoint, spherepoint_gen_key, 1);
657 break;
658 }
659
660 if (GIST_LEAF(entry))
661 {
662 switch (strategy)
663 {
664 case 1:
665 if (i == SCKEY_SAME)
666 result = true;
667 break;
668 default:
669 if (i > SCKEY_DISJ)
670 result = true;
671 break;
672 }
673 }
674 else
675 {
676 switch (strategy)
677 {
678 case 1:
679 if (i > SCKEY_OVERLAP)
680 result = true;
681 break;
682 default:
683 if (i > SCKEY_DISJ)
684 result = true;
685 break;
686 }
687 }
688 PG_RETURN_BOOL(result);
689 }
690 PG_RETURN_BOOL(false);
691 }
692
693 Datum
g_spath_consistent(PG_FUNCTION_ARGS)694 g_spath_consistent(PG_FUNCTION_ARGS)
695 {
696 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
697 void *query = (void *) PG_GETARG_POINTER(1);
698 StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
699 bool result = false;
700
701 if (DatumGetPointer(entry->key) == NULL || !query)
702 {
703 PG_RETURN_BOOL(false);
704 }
705 else
706 {
707 bool *recheck = (bool *) PG_GETARG_POINTER(4);
708 int32 *ent = (int32 *) DatumGetPointer(entry->key);
709 int i = SCKEY_DISJ;
710
711 *recheck = true;
712
713 switch (strategy)
714 {
715 case 1:
716 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 1);
717 break;
718 case 11:
719 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
720 break;
721 case 12:
722 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
723 break;
724 case 13:
725 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
726 break;
727 case 14:
728 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
729 break;
730 case 21:
731 SCK_INTERLEAVE(SPoint, spherepoint_gen_key, 1);
732 break;
733 case 31:
734 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 1);
735 break;
736 case 32:
737 SCK_INTERLEAVE(SLine, sphereline_gen_key, 1);
738 break;
739 case 33:
740 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 1);
741 break;
742 case 34:
743 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 1);
744 break;
745 case 35:
746 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 1);
747 break;
748 case 36:
749 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 1);
750 break;
751 case 37:
752 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
753 break;
754 case 38:
755 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
756 break;
757 case 39:
758 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
759 break;
760 case 40:
761 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
762 break;
763 case 43:
764 SCK_INTERLEAVE(SPoint, spherepoint_gen_key, 1);
765 break;
766 }
767
768 if (GIST_LEAF(entry))
769 {
770 switch (strategy)
771 {
772 case 1:
773 if (i == SCKEY_SAME)
774 result = true;
775 break;
776 default:
777 if (i > SCKEY_DISJ)
778 result = true;
779 break;
780 }
781 }
782 else
783 {
784 switch (strategy)
785 {
786 case 1:
787 if (i > SCKEY_OVERLAP)
788 result = true;
789 break;
790 default:
791 if (i > SCKEY_DISJ)
792 result = true;
793 break;
794 }
795 }
796 PG_RETURN_BOOL(result);
797 }
798 PG_RETURN_BOOL(false);
799 }
800
801
802 Datum
g_spoly_consistent(PG_FUNCTION_ARGS)803 g_spoly_consistent(PG_FUNCTION_ARGS)
804 {
805 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
806 void *query = (void *) PG_GETARG_POINTER(1);
807 StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
808 bool result = false;
809
810 if (DatumGetPointer(entry->key) == NULL || !query)
811 {
812 PG_RETURN_BOOL(false);
813 }
814 else
815 {
816 bool *recheck = (bool *) PG_GETARG_POINTER(4);
817 int32 *ent = (int32 *) DatumGetPointer(entry->key);
818 int i = SCKEY_DISJ;
819
820 *recheck = true;
821
822 switch (strategy)
823 {
824 case 1:
825 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 1);
826 break;
827 case 11:
828 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
829 break;
830 case 12:
831 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
832 break;
833 case 13:
834 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
835 break;
836 case 14:
837 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
838 break;
839 case 21:
840 SCK_INTERLEAVE(SPoint, spherepoint_gen_key, 1);
841 break;
842 case 22:
843 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 1);
844 break;
845 case 23:
846 SCK_INTERLEAVE(SLine, sphereline_gen_key, 1);
847 break;
848 case 24:
849 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 1);
850 break;
851 case 25:
852 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 1);
853 break;
854 case 26:
855 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 1);
856 break;
857 case 27:
858 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 1);
859 break;
860 case 31:
861 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
862 break;
863 case 32:
864 SCK_INTERLEAVE(SLine, sphereline_gen_key, 0);
865 break;
866 case 33:
867 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 0);
868 break;
869 case 34:
870 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
871 break;
872 case 35:
873 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
874 break;
875 case 36:
876 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
877 break;
878 case 37:
879 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
880 break;
881 case 38:
882 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
883 break;
884 case 39:
885 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
886 break;
887 case 40:
888 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
889 break;
890 case 43:
891 SCK_INTERLEAVE(SPoint, spherepoint_gen_key, 1);
892 break;
893 case 44:
894 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 1);
895 break;
896 case 45:
897 SCK_INTERLEAVE(SLine, sphereline_gen_key, 1);
898 break;
899 case 46:
900 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 1);
901 break;
902 case 47:
903 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 1);
904 break;
905 case 48:
906 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 1);
907 break;
908 case 49:
909 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 1);
910 break;
911 }
912
913 if (GIST_LEAF(entry))
914 {
915 switch (strategy)
916 {
917 case 1:
918 if (i == SCKEY_SAME)
919 result = true;
920 break;
921 default:
922 if (i > SCKEY_DISJ)
923 result = true;
924 break;
925 }
926 }
927 else
928 {
929 switch (strategy)
930 {
931 case 1:
932 if (i > SCKEY_OVERLAP)
933 result = true;
934 break;
935 default:
936 if (i > SCKEY_DISJ)
937 result = true;
938 break;
939 }
940 }
941 PG_RETURN_BOOL(result);
942 }
943 PG_RETURN_BOOL(false);
944 }
945
946 Datum
g_sellipse_consistent(PG_FUNCTION_ARGS)947 g_sellipse_consistent(PG_FUNCTION_ARGS)
948 {
949 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
950 void *query = (void *) PG_GETARG_POINTER(1);
951 StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
952 bool result = false;
953
954 if (DatumGetPointer(entry->key) == NULL || !query)
955 {
956 PG_RETURN_BOOL(false);
957 }
958 else
959 {
960 bool *recheck = (bool *) PG_GETARG_POINTER(4);
961 int32 *ent = (int32 *) DatumGetPointer(entry->key);
962 int i = SCKEY_DISJ;
963
964 *recheck = true;
965
966 switch (strategy)
967 {
968 case 1:
969 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 1);
970 break;
971 case 11:
972 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
973 break;
974 case 12:
975 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
976 break;
977 case 13:
978 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
979 break;
980 case 14:
981 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
982 break;
983 case 21:
984 SCK_INTERLEAVE(SPoint, spherepoint_gen_key, 1);
985 break;
986 case 22:
987 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 1);
988 break;
989 case 23:
990 SCK_INTERLEAVE(SLine, sphereline_gen_key, 1);
991 break;
992 case 24:
993 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 1);
994 break;
995 case 25:
996 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 1);
997 break;
998 case 26:
999 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 1);
1000 break;
1001 case 27:
1002 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 1);
1003 break;
1004 case 31:
1005 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
1006 break;
1007 case 32:
1008 SCK_INTERLEAVE(SLine, sphereline_gen_key, 0);
1009 break;
1010 case 33:
1011 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 0);
1012 break;
1013 case 34:
1014 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
1015 break;
1016 case 35:
1017 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
1018 break;
1019 case 36:
1020 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
1021 break;
1022 case 37:
1023 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
1024 break;
1025 case 38:
1026 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
1027 break;
1028 case 39:
1029 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
1030 break;
1031 case 40:
1032 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
1033 break;
1034 case 43:
1035 SCK_INTERLEAVE(SPoint, spherepoint_gen_key, 1);
1036 break;
1037 case 44:
1038 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 1);
1039 break;
1040 case 45:
1041 SCK_INTERLEAVE(SLine, sphereline_gen_key, 1);
1042 break;
1043 case 46:
1044 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 1);
1045 break;
1046 case 47:
1047 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 1);
1048 break;
1049 case 48:
1050 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 1);
1051 break;
1052 case 49:
1053 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 1);
1054 break;
1055 }
1056
1057 if (GIST_LEAF(entry))
1058 {
1059 switch (strategy)
1060 {
1061 case 1:
1062 if (i == SCKEY_SAME)
1063 result = true;
1064 break;
1065 default:
1066 if (i > SCKEY_DISJ)
1067 result = true;
1068 break;
1069 }
1070 }
1071 else
1072 {
1073 switch (strategy)
1074 {
1075 case 1:
1076 if (i > SCKEY_OVERLAP)
1077 result = true;
1078 break;
1079 default:
1080 if (i > SCKEY_DISJ)
1081 result = true;
1082 break;
1083 }
1084 }
1085 PG_RETURN_BOOL(result);
1086 }
1087 PG_RETURN_BOOL(false);
1088 }
1089
1090 Datum
g_sbox_consistent(PG_FUNCTION_ARGS)1091 g_sbox_consistent(PG_FUNCTION_ARGS)
1092 {
1093 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1094 void *query = (void *) PG_GETARG_POINTER(1);
1095 StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1096 bool result = false;
1097
1098 if (DatumGetPointer(entry->key) == NULL || !query)
1099 {
1100 PG_RETURN_BOOL(false);
1101 }
1102 else
1103 {
1104 bool *recheck = (bool *) PG_GETARG_POINTER(4);
1105 int32 *ent = (int32 *) DatumGetPointer(entry->key);
1106 int i = SCKEY_DISJ;
1107
1108 *recheck = true;
1109
1110 switch (strategy)
1111 {
1112 case 1:
1113 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 1);
1114 break;
1115 case 11:
1116 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
1117 break;
1118 case 12:
1119 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
1120 break;
1121 case 13:
1122 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
1123 break;
1124 case 14:
1125 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
1126 break;
1127 case 21:
1128 SCK_INTERLEAVE(SPoint, spherepoint_gen_key, 1);
1129 break;
1130 case 22:
1131 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 1);
1132 break;
1133 case 23:
1134 SCK_INTERLEAVE(SLine, sphereline_gen_key, 1);
1135 break;
1136 case 24:
1137 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 1);
1138 break;
1139 case 25:
1140 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 1);
1141 break;
1142 case 26:
1143 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 1);
1144 break;
1145 case 27:
1146 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 1);
1147 break;
1148 case 31:
1149 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
1150 break;
1151 case 32:
1152 SCK_INTERLEAVE(SLine, sphereline_gen_key, 0);
1153 break;
1154 case 33:
1155 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 0);
1156 break;
1157 case 34:
1158 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
1159 break;
1160 case 35:
1161 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
1162 break;
1163 case 36:
1164 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
1165 break;
1166 case 37:
1167 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 0);
1168 break;
1169 case 38:
1170 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 0);
1171 break;
1172 case 39:
1173 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 0);
1174 break;
1175 case 40:
1176 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 0);
1177 break;
1178 case 43:
1179 SCK_INTERLEAVE(SPoint, spherepoint_gen_key, 1);
1180 break;
1181 case 44:
1182 SCK_INTERLEAVE(SCIRCLE, spherecircle_gen_key, 1);
1183 break;
1184 case 45:
1185 SCK_INTERLEAVE(SLine, sphereline_gen_key, 1);
1186 break;
1187 case 46:
1188 SCK_INTERLEAVE(SPATH, spherepath_gen_key, 1);
1189 break;
1190 case 47:
1191 SCK_INTERLEAVE(SPOLY, spherepoly_gen_key, 1);
1192 break;
1193 case 48:
1194 SCK_INTERLEAVE(SELLIPSE, sphereellipse_gen_key, 1);
1195 break;
1196 case 49:
1197 SCK_INTERLEAVE(SBOX, spherebox_gen_key, 1);
1198 break;
1199 }
1200
1201 if (GIST_LEAF(entry))
1202 {
1203 switch (strategy)
1204 {
1205 case 1:
1206 if (i == SCKEY_SAME)
1207 result = true;
1208 break;
1209 default:
1210 if (i > SCKEY_DISJ)
1211 result = true;
1212 break;
1213 }
1214 }
1215 else
1216 {
1217 switch (strategy)
1218 {
1219 case 1:
1220 if (i > SCKEY_OVERLAP)
1221 result = true;
1222 break;
1223 default:
1224 if (i > SCKEY_DISJ)
1225 result = true;
1226 break;
1227 }
1228 }
1229 PG_RETURN_BOOL(result);
1230 }
1231 PG_RETURN_BOOL(false);
1232 }
1233
1234 typedef int32 coord_t;
1235
1236 typedef struct
1237 {
1238 coord_t coord[3];
1239 } Point3D;
1240
1241 typedef struct
1242 {
1243 Point3D low;
1244 Point3D high;
1245 } Box3D;
1246
1247 #ifdef NOT_USED
1248 static void
checkBox3D(Box3D * box)1249 checkBox3D(Box3D *box)
1250 {
1251 int i;
1252 for (i = 0; i < 3; i++)
1253 {
1254 if (box->low.coord[i] < -MAXCVALUE || box->low.coord[i] > MAXCVALUE)
1255 {
1256 elog(ERROR, "Invalid key!");
1257 }
1258 if (box->high.coord[i] < -MAXCVALUE || box->high.coord[i] > MAXCVALUE)
1259 {
1260 elog(ERROR, "Invalid key!");
1261 }
1262 }
1263 }
1264 #endif
1265
1266 static void
adjustBox3D(Box3D * b,Box3D * addon)1267 adjustBox3D(Box3D *b, Box3D *addon)
1268 {
1269 int i;
1270
1271 for (i = 0; i < 3; i++)
1272 {
1273 if (b->high.coord[i] < addon->high.coord[i])
1274 b->high.coord[i] = addon->high.coord[i];
1275 if (b->low.coord[i] > addon->low.coord[i])
1276 b->low.coord[i] = addon->low.coord[i];
1277 }
1278 }
1279
1280 static inline double
sizeBox3D(Box3D * b)1281 sizeBox3D(Box3D *b)
1282 {
1283 return (double) ((int64) b->high.coord[0] - (int64) b->low.coord[0]) / MAXCVALUE
1284 * (double) ((int64) b->high.coord[1] - (int64) b->low.coord[1]) / MAXCVALUE
1285 * (double) ((int64) b->high.coord[2] - (int64) b->low.coord[2]) / MAXCVALUE;
1286 }
1287
1288 static inline double
unionSizeBox3D(Box3D * a,Box3D * b)1289 unionSizeBox3D(Box3D *a, Box3D *b)
1290 {
1291 return (double) ((int64) Max(a->high.coord[0], b->high.coord[0]) -
1292 (int64) Min(a->low.coord[0], b->low.coord[0])) / MAXCVALUE
1293
1294 * (double) ((int64) Max(a->high.coord[1], b->high.coord[1]) -
1295 (int64) Min(a->low.coord[1], b->low.coord[1])) / MAXCVALUE
1296
1297 * (double) ((int64) Max(a->high.coord[2], b->high.coord[2]) -
1298 (int64) Min(a->low.coord[2], b->low.coord[2])) / MAXCVALUE;
1299 }
1300
1301 /*
1302 * Trivial split: half of entries will be placed on one page
1303 * and another half - to another.
1304 */
1305 static void
fallbackSplit(Box3D * boxes,OffsetNumber maxoff,GIST_SPLITVEC * v)1306 fallbackSplit(Box3D *boxes, OffsetNumber maxoff, GIST_SPLITVEC *v)
1307 {
1308 OffsetNumber i;
1309 Box3D *unionL = NULL,
1310 *unionR = NULL;
1311 int nbytes;
1312
1313 nbytes = (maxoff + 2) * sizeof(OffsetNumber);
1314 v->spl_left = (OffsetNumber *) palloc(nbytes);
1315 v->spl_right = (OffsetNumber *) palloc(nbytes);
1316 v->spl_nleft = v->spl_nright = 0;
1317
1318 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1319 {
1320 Box3D *cur = &boxes[i];
1321
1322 if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
1323 {
1324 v->spl_left[v->spl_nleft] = i;
1325 if (unionL == NULL)
1326 {
1327 unionL = (Box3D *) palloc(sizeof(Box3D));
1328 *unionL = *cur;
1329 }
1330 else
1331 adjustBox3D(unionL, cur);
1332
1333 v->spl_nleft++;
1334 }
1335 else
1336 {
1337 v->spl_right[v->spl_nright] = i;
1338 if (unionR == NULL)
1339 {
1340 unionR = (Box3D *) palloc(sizeof(Box3D));
1341 *unionR = *cur;
1342 }
1343 else
1344 adjustBox3D(unionR, cur);
1345
1346 v->spl_nright++;
1347 }
1348 }
1349
1350 if (v->spl_ldatum_exists)
1351 adjustBox3D(unionL, (Box3D *) DatumGetPointer(v->spl_ldatum));
1352 v->spl_ldatum = PointerGetDatum(unionL);
1353
1354 if (v->spl_rdatum_exists)
1355 adjustBox3D(unionR, (Box3D *) DatumGetPointer(v->spl_rdatum));
1356 v->spl_rdatum = PointerGetDatum(unionR);
1357
1358 v->spl_ldatum_exists = v->spl_rdatum_exists = false;
1359 }
1360
1361 /*
1362 * Represents information about an entry that can be placed to either group
1363 * without affecting overlap over selected axis ("common entry").
1364 */
1365 typedef struct
1366 {
1367 /* Index of entry in the initial array */
1368 int index;
1369 /* Delta between penalties of entry insertion into different groups */
1370 double delta;
1371 } CommonEntry;
1372
1373 /*
1374 * Context for g_box_consider_split. Contains information about currently
1375 * selected split and some general information.
1376 */
1377 typedef struct
1378 {
1379 int entriesCount; /* total number of entries being split */
1380 Box3D boundingBox; /* minimum bounding box across all entries */
1381
1382 /* Information about currently selected split follows */
1383
1384 bool first; /* true if no split was selected yet */
1385
1386 coord_t leftUpper; /* upper bound of left interval */
1387 coord_t rightLower; /* lower bound of right interval */
1388
1389 float4 ratio;
1390 float4 overlap;
1391 int dim; /* axis of this split */
1392 double range; /* width of general MBR projection to the
1393 * selected axis */
1394 } ConsiderSplitContext;
1395
1396 /*
1397 * Interval represents projection of box to axis.
1398 */
1399 typedef struct
1400 {
1401 coord_t lower,
1402 upper;
1403 } SplitInterval;
1404
1405 /*
1406 * Interval comparison function by lower bound of the interval;
1407 */
1408 static inline int
interval_cmp_lower(const void * i1,const void * i2)1409 interval_cmp_lower(const void *i1, const void *i2)
1410 {
1411 coord_t lower1 = ((const SplitInterval *) i1)->lower,
1412 lower2 = ((const SplitInterval *) i2)->lower;
1413
1414 if (lower1 < lower2)
1415 return -1;
1416 else if (lower1 > lower2)
1417 return 1;
1418 else
1419 return 0;
1420 }
1421
1422 /*
1423 * Interval comparison function by upper bound of the interval;
1424 */
1425 static inline int
interval_cmp_upper(const void * i1,const void * i2)1426 interval_cmp_upper(const void *i1, const void *i2)
1427 {
1428 coord_t upper1 = ((const SplitInterval *) i1)->upper,
1429 upper2 = ((const SplitInterval *) i2)->upper;
1430
1431 if (upper1 < upper2)
1432 return -1;
1433 else if (upper1 > upper2)
1434 return 1;
1435 else
1436 return 0;
1437 }
1438
1439 /*
1440 * Replace negative value with zero.
1441 */
1442 static inline float
non_negative(float val)1443 non_negative(float val)
1444 {
1445 if (val >= 0.0f)
1446 return val;
1447 else
1448 return 0.0f;
1449 }
1450
1451 /* Minimum accepted ratio of split */
1452 #define LIMIT_RATIO 0.3
1453
1454 /*
1455 * Consider replacement of currently selected split with the better one.
1456 */
1457 static inline void
g_box_consider_split(ConsiderSplitContext * context,int dimNum,coord_t rightLower,int minLeftCount,coord_t leftUpper,int maxLeftCount)1458 g_box_consider_split(ConsiderSplitContext *context, int dimNum,
1459 coord_t rightLower, int minLeftCount,
1460 coord_t leftUpper, int maxLeftCount)
1461 {
1462 int leftCount,
1463 rightCount;
1464 float4 ratio,
1465 overlap;
1466 double range;
1467
1468 /*
1469 * Calculate entries distribution ratio assuming most uniform distribution
1470 * of common entries.
1471 */
1472 if (minLeftCount >= (context->entriesCount + 1) / 2)
1473 {
1474 leftCount = minLeftCount;
1475 }
1476 else
1477 {
1478 if (maxLeftCount <= context->entriesCount / 2)
1479 leftCount = maxLeftCount;
1480 else
1481 leftCount = context->entriesCount / 2;
1482 }
1483 rightCount = context->entriesCount - leftCount;
1484
1485 /*
1486 * Ratio of split - quotient between size of lesser group and total
1487 * entries count.
1488 */
1489 ratio = ((float4) Min(leftCount, rightCount)) /
1490 ((float4) context->entriesCount);
1491
1492 if (ratio > LIMIT_RATIO)
1493 {
1494 bool selectthis = false;
1495
1496 /*
1497 * The ratio is acceptable, so compare current split with previously
1498 * selected one. Between splits of one dimension we search for minimal
1499 * overlap (allowing negative values) and minimal ration (between same
1500 * overlaps. We switch dimension if find less overlap (non-negative)
1501 * or less range with same overlap.
1502 */
1503 range = (float8) context->boundingBox.high.coord[dimNum] -
1504 (float8) context->boundingBox.low.coord[dimNum];
1505 overlap = ((float8) leftUpper - (float8) rightLower) / range;
1506
1507 /* If there is no previous selection, select this */
1508 if (context->first)
1509 selectthis = true;
1510 else if (context->dim == dimNum)
1511 {
1512 /*
1513 * Within the same dimension, choose the new split if it has a
1514 * smaller overlap, or same overlap but better ratio.
1515 */
1516 if (overlap < context->overlap ||
1517 (overlap == context->overlap && ratio > context->ratio))
1518 selectthis = true;
1519 }
1520 else
1521 {
1522 /*
1523 * Across dimensions, choose the new split if it has a smaller
1524 * *non-negative* overlap, or same *non-negative* overlap but
1525 * bigger range. This condition differs from the one described in
1526 * the article. On the datasets where leaf MBRs don't overlap
1527 * themselves, non-overlapping splits (i.e. splits which have zero
1528 * *non-negative* overlap) are frequently possible. In this case
1529 * splits tends to be along one dimension, because most distant
1530 * non-overlapping splits (i.e. having lowest negative overlap)
1531 * appears to be in the same dimension as in the previous split.
1532 * Therefore MBRs appear to be very prolonged along another
1533 * dimension, which leads to bad search performance. Using range
1534 * as the second split criteria makes MBRs more quadratic. Using
1535 * *non-negative* overlap instead of overlap as the first split
1536 * criteria gives to range criteria a chance to matter, because
1537 * non-overlapping splits are equivalent in this criteria.
1538 */
1539 if (non_negative(overlap) < non_negative(context->overlap) ||
1540 (range > context->range &&
1541 non_negative(overlap) <= non_negative(context->overlap)))
1542 selectthis = true;
1543 }
1544
1545 if (selectthis)
1546 {
1547 /* save information about selected split */
1548 context->first = false;
1549 context->ratio = ratio;
1550 context->range = range;
1551 context->overlap = overlap;
1552 context->rightLower = rightLower;
1553 context->leftUpper = leftUpper;
1554 context->dim = dimNum;
1555 }
1556 }
1557 }
1558
1559 /*
1560 * Compare common entries by their deltas.
1561 */
1562 static int
common_entry_cmp(const void * i1,const void * i2)1563 common_entry_cmp(const void *i1, const void *i2)
1564 {
1565 double delta1 = ((const CommonEntry *) i1)->delta,
1566 delta2 = ((const CommonEntry *) i2)->delta;
1567
1568 if (delta1 < delta2)
1569 return -1;
1570 else if (delta1 > delta2)
1571 return 1;
1572 else
1573 return 0;
1574 }
1575
1576 /*
1577 * --------------------------------------------------------------------------
1578 * Double sorting split algorithm. This is used for both boxes and points.
1579 *
1580 * The algorithm finds split of boxes by considering splits along each axis.
1581 * Each entry is first projected as an interval on the X-axis, and different
1582 * ways to split the intervals into two groups are considered, trying to
1583 * minimize the overlap of the groups. Then the same is repeated for the
1584 * Y-axis, and the overall best split is chosen. The quality of a split is
1585 * determined by overlap along that axis and some other criteria (see
1586 * g_box_consider_split).
1587 *
1588 * After that, all the entries are divided into three groups:
1589 *
1590 * 1) Entries which should be placed to the left group
1591 * 2) Entries which should be placed to the right group
1592 * 3) "Common entries" which can be placed to any of groups without affecting
1593 * of overlap along selected axis.
1594 *
1595 * The common entries are distributed by minimizing penalty.
1596 *
1597 * For details see:
1598 * "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov
1599 * http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
1600 * --------------------------------------------------------------------------
1601 */
1602 static void
do_picksplit(Box3D * boxes,OffsetNumber maxoff,GIST_SPLITVEC * v)1603 do_picksplit(Box3D *boxes, OffsetNumber maxoff, GIST_SPLITVEC *v)
1604 {
1605 OffsetNumber i;
1606 ConsiderSplitContext context;
1607 Box3D *box,
1608 *leftBox,
1609 *rightBox;
1610 int dim,
1611 commonEntriesCount;
1612 SplitInterval *intervalsLower,
1613 *intervalsUpper;
1614 CommonEntry *commonEntries;
1615 int nentries;
1616 double leftBoxSize,
1617 rightBoxSize;
1618
1619 memset(&context, 0, sizeof(ConsiderSplitContext));
1620
1621 nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
1622
1623 /* Allocate arrays for intervals along axes */
1624 intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
1625 intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
1626
1627 /*
1628 * Calculate the overall minimum bounding box over all the entries.
1629 */
1630 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1631 {
1632 box = &boxes[i];
1633 if (i == FirstOffsetNumber)
1634 context.boundingBox = *box;
1635 else
1636 adjustBox3D(&context.boundingBox, box);
1637 }
1638
1639 /*
1640 * Iterate over axes for optimal split searching.
1641 */
1642 context.first = true; /* nothing selected yet */
1643 for (dim = 0; dim < 3; dim++)
1644 {
1645 coord_t leftUpper,
1646 rightLower;
1647 int i1,
1648 i2;
1649
1650 /* Project each entry as an interval on the selected axis. */
1651 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1652 {
1653 box = &boxes[i];
1654 intervalsLower[i - FirstOffsetNumber].lower = box->low.coord[dim];
1655 intervalsLower[i - FirstOffsetNumber].upper = box->high.coord[dim];
1656 }
1657
1658 /*
1659 * Make two arrays of intervals: one sorted by lower bound and another
1660 * sorted by upper bound.
1661 */
1662 memcpy(intervalsUpper, intervalsLower,
1663 sizeof(SplitInterval) * nentries);
1664 qsort(intervalsLower, nentries, sizeof(SplitInterval),
1665 interval_cmp_lower);
1666 qsort(intervalsUpper, nentries, sizeof(SplitInterval),
1667 interval_cmp_upper);
1668
1669 /*----
1670 * The goal is to form a left and right interval, so that every entry
1671 * interval is contained by either left or right interval (or both).
1672 *
1673 * For example, with the intervals (0,1), (1,3), (2,3), (2,4):
1674 *
1675 * 0 1 2 3 4
1676 * +-+
1677 * +---+
1678 * +-+
1679 * +---+
1680 *
1681 * The left and right intervals are of the form (0,a) and (b,4).
1682 * We first consider splits where b is the lower bound of an entry.
1683 * We iterate through all entries, and for each b, calculate the
1684 * smallest possible a. Then we consider splits where a is the
1685 * uppper bound of an entry, and for each a, calculate the greatest
1686 * possible b.
1687 *
1688 * In the above example, the first loop would consider splits:
1689 * b=0: (0,1)-(0,4)
1690 * b=1: (0,1)-(1,4)
1691 * b=2: (0,3)-(2,4)
1692 *
1693 * And the second loop:
1694 * a=1: (0,1)-(1,4)
1695 * a=3: (0,3)-(2,4)
1696 * a=4: (0,4)-(2,4)
1697 */
1698
1699 /*
1700 * Iterate over lower bound of right group, finding smallest possible
1701 * upper bound of left group.
1702 */
1703 i1 = 0;
1704 i2 = 0;
1705 rightLower = intervalsLower[i1].lower;
1706 leftUpper = intervalsUpper[i2].lower;
1707 while (true)
1708 {
1709 /*
1710 * Find next lower bound of right group.
1711 */
1712 while (i1 < nentries && rightLower == intervalsLower[i1].lower)
1713 {
1714 leftUpper = Max(leftUpper, intervalsLower[i1].upper);
1715 i1++;
1716 }
1717 if (i1 >= nentries)
1718 break;
1719 rightLower = intervalsLower[i1].lower;
1720
1721 /*
1722 * Find count of intervals which anyway should be placed to the
1723 * left group.
1724 */
1725 while (i2 < nentries && intervalsUpper[i2].upper <= leftUpper)
1726 i2++;
1727
1728 /*
1729 * Consider found split.
1730 */
1731 g_box_consider_split(&context, dim, rightLower, i1, leftUpper, i2);
1732 }
1733
1734 /*
1735 * Iterate over upper bound of left group finding greates possible
1736 * lower bound of right group.
1737 */
1738 i1 = nentries - 1;
1739 i2 = nentries - 1;
1740 rightLower = intervalsLower[i1].upper;
1741 leftUpper = intervalsUpper[i2].upper;
1742 while (true)
1743 {
1744 /*
1745 * Find next upper bound of left group.
1746 */
1747 while (i2 >= 0 && leftUpper == intervalsUpper[i2].upper)
1748 {
1749 rightLower = Min(rightLower, intervalsUpper[i2].lower);
1750 i2--;
1751 }
1752 if (i2 < 0)
1753 break;
1754 leftUpper = intervalsUpper[i2].upper;
1755
1756 /*
1757 * Find count of intervals which anyway should be placed to the
1758 * right group.
1759 */
1760 while (i1 >= 0 && intervalsLower[i1].lower >= rightLower)
1761 i1--;
1762
1763 /*
1764 * Consider found split.
1765 */
1766 g_box_consider_split(&context, dim,
1767 rightLower, i1 + 1, leftUpper, i2 + 1);
1768 }
1769 }
1770
1771 /*
1772 * If we failed to find any acceptable splits, use trivial split.
1773 */
1774 if (context.first)
1775 {
1776 fallbackSplit(boxes, maxoff, v);
1777 return;
1778 }
1779
1780 /*
1781 * Ok, we have now selected the split across one axis.
1782 *
1783 * While considering the splits, we already determined that there will be
1784 * enough entries in both groups to reach the desired ratio, but we did
1785 * not memorize which entries go to which group. So determine that now.
1786 */
1787
1788 /* Allocate vectors for results */
1789 v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
1790 v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
1791 v->spl_nleft = 0;
1792 v->spl_nright = 0;
1793
1794 /* Allocate bounding boxes of left and right groups */
1795 leftBox = palloc0(sizeof(Box3D));
1796 rightBox = palloc0(sizeof(Box3D));
1797
1798 leftBoxSize = sizeBox3D(leftBox);
1799 rightBoxSize = sizeBox3D(rightBox);
1800
1801 /*
1802 * Allocate an array for "common entries" - entries which can be placed to
1803 * either group without affecting overlap along selected axis.
1804 */
1805 commonEntriesCount = 0;
1806 commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
1807
1808 /* Helper macros to place an entry in the left or right group */
1809 #define PLACE_LEFT(box, off) \
1810 do { \
1811 if (v->spl_nleft > 0) \
1812 adjustBox3D(leftBox, box); \
1813 else \
1814 *leftBox = *(box); \
1815 v->spl_left[v->spl_nleft++] = off; \
1816 } while(0)
1817
1818 #define PLACE_RIGHT(box, off) \
1819 do { \
1820 if (v->spl_nright > 0) \
1821 adjustBox3D(rightBox, box); \
1822 else \
1823 *rightBox = *(box); \
1824 v->spl_right[v->spl_nright++] = off; \
1825 } while(0)
1826
1827 /*
1828 * Distribute entries which can be distributed unambiguously, and collect
1829 * common entries.
1830 */
1831 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1832 {
1833 coord_t lower,
1834 upper;
1835
1836 /*
1837 * Get upper and lower bounds along selected axis.
1838 */
1839 box = &boxes[i];
1840 lower = box->low.coord[context.dim];
1841 upper = box->high.coord[context.dim];
1842
1843 if (upper <= context.leftUpper)
1844 {
1845 /* Fits to the left group */
1846 if (lower >= context.rightLower)
1847 {
1848 /* Fits also to the right group, so "common entry" */
1849 commonEntries[commonEntriesCount++].index = i;
1850 }
1851 else
1852 {
1853 /* Doesn't fit to the right group, so join to the left group */
1854 PLACE_LEFT(box, i);
1855 /* checkBox3D(leftBox); */
1856 }
1857 }
1858 else
1859 {
1860 /*
1861 * Each entry should fit on either left or right group. Since this
1862 * entry didn't fit on the left group, it better fit in the right
1863 * group.
1864 */
1865 Assert(lower >= context.rightLower);
1866
1867 /* Doesn't fit to the left group, so join to the right group */
1868 PLACE_RIGHT(box, i);
1869 /* checkBox3D(rightBox); */
1870 }
1871 }
1872
1873 /*
1874 * Distribute "common entries", if any.
1875 */
1876 if (commonEntriesCount > 0)
1877 {
1878 /*
1879 * Calculate minimum number of entries that must be placed in both
1880 * groups, to reach LIMIT_RATIO.
1881 */
1882 int m = ceil(LIMIT_RATIO * (double) nentries);
1883
1884 /*
1885 * Calculate delta between penalties of join "common entries" to
1886 * different groups.
1887 */
1888 for (i = 0; i < commonEntriesCount; i++)
1889 {
1890 box = &boxes[i];
1891 commonEntries[i].delta = Abs((unionSizeBox3D(leftBox, box) - leftBoxSize) -
1892 (unionSizeBox3D(rightBox, box) - rightBoxSize));
1893 }
1894
1895 /*
1896 * Sort "common entries" by calculated deltas in order to distribute
1897 * the most ambiguous entries first.
1898 */
1899 qsort(commonEntries,
1900 commonEntriesCount,
1901 sizeof(CommonEntry),
1902 common_entry_cmp);
1903
1904 /*
1905 * Distribute "common entries" between groups.
1906 */
1907 for (i = 0; i < commonEntriesCount; i++)
1908 {
1909 box = &boxes[commonEntries[i].index];
1910
1911 /*
1912 * Check if we have to place this entry in either group to achieve
1913 * LIMIT_RATIO.
1914 */
1915 if (v->spl_nleft + (commonEntriesCount - i) <= m)
1916 {
1917 PLACE_LEFT(box, commonEntries[i].index);
1918 /* checkBox3D(leftBox); */
1919 }
1920 else if (v->spl_nright + (commonEntriesCount - i) <= m)
1921 {
1922 PLACE_RIGHT(box, commonEntries[i].index);
1923 /* checkBox3D(rightBox); */
1924 }
1925 else
1926 {
1927 /* Otherwise select the group by minimal penalty */
1928 if (unionSizeBox3D(leftBox, box) - leftBoxSize <
1929 unionSizeBox3D(rightBox, box) - rightBoxSize)
1930 {
1931 PLACE_LEFT(box, commonEntries[i].index);
1932 /* checkBox3D(leftBox); */
1933 }
1934 else
1935 {
1936 PLACE_RIGHT(box, commonEntries[i].index);
1937 /* checkBox3D(rightBox); */
1938 }
1939 }
1940 }
1941 }
1942
1943 /*
1944 * checkBox3D(leftBox); checkBox3D(rightBox);
1945 */
1946
1947 v->spl_ldatum = PointerGetDatum(leftBox);
1948 v->spl_rdatum = PointerGetDatum(rightBox);
1949 }
1950
1951 Datum
g_spherekey_picksplit(PG_FUNCTION_ARGS)1952 g_spherekey_picksplit(PG_FUNCTION_ARGS)
1953 {
1954 GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
1955 GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
1956 OffsetNumber i,
1957 maxoff;
1958 Box3D *boxes;
1959
1960 maxoff = entryvec->n - 1;
1961 boxes = (Box3D *) palloc(sizeof(Box3D) * entryvec->n);
1962 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1963 boxes[i] = *((Box3D *) DatumGetPointer(entryvec->vector[i].key));
1964
1965 do_picksplit(boxes, maxoff, v);
1966
1967 PG_RETURN_POINTER(v);
1968 }
1969
1970 /*
1971 * The GiST Penalty method for boxes. We have to make panalty as fast as
1972 * possible ( offen called ! )
1973 */
1974 Datum
g_spherekey_penalty(PG_FUNCTION_ARGS)1975 g_spherekey_penalty(PG_FUNCTION_ARGS)
1976 {
1977 GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
1978 GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
1979 float *result = (float *) PG_GETARG_POINTER(2);
1980 Box3D *o = (Box3D *) DatumGetPointer(origentry->key);
1981
1982 if (newentry != NULL)
1983 {
1984 Box3D *n = (Box3D *) DatumGetPointer(newentry->key);
1985
1986 *result = (float) (((uint64) (Max(o->high.coord[0], n->high.coord[0]) -
1987 Min(o->low.coord[0], n->low.coord[0])) >> 10)
1988
1989 * ((uint64) (Max(o->high.coord[1], n->high.coord[1]) -
1990 Min(o->low.coord[1], n->low.coord[1])) >> 10)
1991
1992 * ((uint64) (Max(o->high.coord[2], n->high.coord[2]) -
1993 Min(o->low.coord[2], n->low.coord[2])) >> 10)
1994
1995 - ((uint64) (o->high.coord[0] - o->low.coord[0]) >> 10)
1996 * ((uint64) (o->high.coord[1] - o->low.coord[1]) >> 10)
1997 * ((uint64) (o->high.coord[2] - o->low.coord[2]) >> 10));
1998 PG_RETURN_POINTER(result);
1999 }
2000 else
2001 {
2002 PG_RETURN_POINTER(NULL);
2003 }
2004 }
2005