1/*****************************************************************************
2
3Copyright (c) 2013, 2015, Oracle and/or its affiliates. All Rights Reserved.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License as published by the Free Software
7Foundation; version 2 of the License.
8
9This program is distributed in the hope that it will be useful, but WITHOUT
10ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
13You should have received a copy of the GNU General Public License along with
14this program; if not, write to the Free Software Foundation, Inc.,
1551 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
16
17*****************************************************************************/
18
19/**************************************************//**
20@file gis/gis0geo.cc
21InnoDB R-tree related functions.
22
23Created 2013/03/27 Allen Lai and Jimmy Yang
24*******************************************************/
25
26#include "page0types.h"
27#include "gis0geo.h"
28#include "page0cur.h"
29#include "ut0rnd.h"
30#include "mach0data.h"
31
32#include <spatial.h>
33
34/* These definitions are for comparing 2 mbrs. */
35
36/* Check if a intersects b.
37Return false if a intersects b, otherwise true. */
38#define INTERSECT_CMP(amin, amax, bmin, bmax) \
39(((amin) > (bmax)) || ((bmin) > (amax)))
40
41/* Check if b contains a.
42Return false if b contains a, otherwise true. */
43#define CONTAIN_CMP(amin, amax, bmin, bmax) \
44(((bmin) > (amin)) || ((bmax) < (amax)))
45
46/* Check if b is within a.
47Return false if b is within a, otherwise true. */
48#define WITHIN_CMP(amin, amax, bmin, bmax) \
49(((amin) > (bmin)) || ((amax) < (bmax)))
50
51/* Check if a disjoints b.
52Return false if a disjoints b, otherwise true. */
53#define DISJOINT_CMP(amin, amax, bmin, bmax) \
54(((amin) <= (bmax)) && ((bmin) <= (amax)))
55
56/* Check if a equals b.
57Return false if equal, otherwise true. */
58#define EQUAL_CMP(amin, amax, bmin, bmax) \
59(((amin) != (bmin)) || ((amax) != (bmax)))
60
61/****************************************************************
62Functions for generating mbr
63****************************************************************/
64/*************************************************************//**
65Add one point stored in wkb to a given mbr.
66@return 0 if the point in wkb is valid, otherwise -1. */
67static
68int
69rtree_add_point_to_mbr(
70/*===================*/
71 uchar** wkb, /*!< in: pointer to wkb,
72 where point is stored */
73 uchar* end, /*!< in: end of wkb. */
74 uint n_dims, /*!< in: dimensions. */
75 double* mbr) /*!< in/out: mbr, which
76 must be of length n_dims * 2. */
77{
78 double ord;
79 double* mbr_end = mbr + n_dims * 2;
80
81 while (mbr < mbr_end) {
82 if ((*wkb) + sizeof(double) > end) {
83 return(-1);
84 }
85
86 ord = mach_double_read(*wkb);
87 (*wkb) += sizeof(double);
88
89 if (ord < *mbr) {
90 *mbr = ord;
91 }
92 mbr++;
93
94 if (ord > *mbr) {
95 *mbr = ord;
96 }
97 mbr++;
98 }
99
100 return(0);
101}
102
103/*************************************************************//**
104Get mbr of point stored in wkb.
105@return 0 if ok, otherwise -1. */
106static
107int
108rtree_get_point_mbr(
109/*================*/
110 uchar** wkb, /*!< in: pointer to wkb,
111 where point is stored. */
112 uchar* end, /*!< in: end of wkb. */
113 uint n_dims, /*!< in: dimensions. */
114 double* mbr) /*!< in/out: mbr,
115 must be of length n_dims * 2. */
116{
117 return rtree_add_point_to_mbr(wkb, end, n_dims, mbr);
118}
119
120
121/*************************************************************//**
122Get mbr of linestring stored in wkb.
123@return 0 if the linestring is valid, otherwise -1. */
124static
125int
126rtree_get_linestring_mbr(
127/*=====================*/
128 uchar** wkb, /*!< in: pointer to wkb,
129 where point is stored. */
130 uchar* end, /*!< in: end of wkb. */
131 uint n_dims, /*!< in: dimensions. */
132 double* mbr) /*!< in/out: mbr,
133 must be of length n_dims * 2. */
134{
135 uint n_points;
136
137 n_points = uint4korr(*wkb);
138 (*wkb) += 4;
139
140 for (; n_points > 0; --n_points) {
141 /* Add next point to mbr */
142 if (rtree_add_point_to_mbr(wkb, end, n_dims, mbr)) {
143 return(-1);
144 }
145 }
146
147 return(0);
148}
149
150/*************************************************************//**
151Get mbr of polygon stored in wkb.
152@return 0 if the polygon is valid, otherwise -1. */
153static
154int
155rtree_get_polygon_mbr(
156/*==================*/
157 uchar** wkb, /*!< in: pointer to wkb,
158 where point is stored. */
159 uchar* end, /*!< in: end of wkb. */
160 uint n_dims, /*!< in: dimensions. */
161 double* mbr) /*!< in/out: mbr,
162 must be of length n_dims * 2. */
163{
164 uint n_linear_rings;
165 uint n_points;
166
167 n_linear_rings = uint4korr((*wkb));
168 (*wkb) += 4;
169
170 for (; n_linear_rings > 0; --n_linear_rings) {
171 n_points = uint4korr((*wkb));
172 (*wkb) += 4;
173
174 for (; n_points > 0; --n_points) {
175 /* Add next point to mbr */
176 if (rtree_add_point_to_mbr(wkb, end, n_dims, mbr)) {
177 return(-1);
178 }
179 }
180 }
181
182 return(0);
183}
184
185/*************************************************************//**
186Get mbr of geometry stored in wkb.
187@return 0 if the geometry is valid, otherwise -1. */
188static
189int
190rtree_get_geometry_mbr(
191/*===================*/
192 uchar** wkb, /*!< in: pointer to wkb,
193 where point is stored. */
194 uchar* end, /*!< in: end of wkb. */
195 uint n_dims, /*!< in: dimensions. */
196 double* mbr, /*!< in/out: mbr. */
197 int top) /*!< in: if it is the top,
198 which means it's not called
199 by itself. */
200{
201 int res;
202 uint wkb_type = 0;
203 uint n_items;
204
205 /* byte_order = *(*wkb); */
206 ++(*wkb);
207
208 wkb_type = uint4korr((*wkb));
209 (*wkb) += 4;
210
211 switch ((enum wkbType) wkb_type) {
212 case wkbPoint:
213 res = rtree_get_point_mbr(wkb, end, n_dims, mbr);
214 break;
215 case wkbLineString:
216 res = rtree_get_linestring_mbr(wkb, end, n_dims, mbr);
217 break;
218 case wkbPolygon:
219 res = rtree_get_polygon_mbr(wkb, end, n_dims, mbr);
220 break;
221 case wkbMultiPoint:
222 n_items = uint4korr((*wkb));
223 (*wkb) += 4;
224 for (; n_items > 0; --n_items) {
225 /* byte_order = *(*wkb); */
226 ++(*wkb);
227 (*wkb) += 4;
228 if (rtree_get_point_mbr(wkb, end, n_dims, mbr)) {
229 return(-1);
230 }
231 }
232 res = 0;
233 break;
234 case wkbMultiLineString:
235 n_items = uint4korr((*wkb));
236 (*wkb) += 4;
237 for (; n_items > 0; --n_items) {
238 /* byte_order = *(*wkb); */
239 ++(*wkb);
240 (*wkb) += 4;
241 if (rtree_get_linestring_mbr(wkb, end, n_dims, mbr)) {
242 return(-1);
243 }
244 }
245 res = 0;
246 break;
247 case wkbMultiPolygon:
248 n_items = uint4korr((*wkb));
249 (*wkb) += 4;
250 for (; n_items > 0; --n_items) {
251 /* byte_order = *(*wkb); */
252 ++(*wkb);
253 (*wkb) += 4;
254 if (rtree_get_polygon_mbr(wkb, end, n_dims, mbr)) {
255 return(-1);
256 }
257 }
258 res = 0;
259 break;
260 case wkbGeometryCollection:
261 if (!top) {
262 return(-1);
263 }
264
265 n_items = uint4korr((*wkb));
266 (*wkb) += 4;
267 for (; n_items > 0; --n_items) {
268 if (rtree_get_geometry_mbr(wkb, end, n_dims,
269 mbr, 0)) {
270 return(-1);
271 }
272 }
273 res = 0;
274 break;
275 default:
276 res = -1;
277 }
278
279 return(res);
280}
281
282/*************************************************************//**
283Calculate Minimal Bounding Rectangle (MBR) of the spatial object
284stored in "well-known binary representation" (wkb) format.
285@return 0 if ok. */
286int
287rtree_mbr_from_wkb(
288/*===============*/
289 uchar* wkb, /*!< in: wkb */
290 uint size, /*!< in: size of wkb. */
291 uint n_dims, /*!< in: dimensions. */
292 double* mbr) /*!< in/out: mbr, which must
293 be of length n_dim2 * 2. */
294{
295 for (uint i = 0; i < n_dims; ++i) {
296 mbr[i * 2] = DBL_MAX;
297 mbr[i * 2 + 1] = -DBL_MAX;
298 }
299
300 return rtree_get_geometry_mbr(&wkb, wkb + size, n_dims, mbr, 1);
301}
302
303
304/****************************************************************
305Functions for Rtree split
306****************************************************************/
307/*************************************************************//**
308Join 2 mbrs of dimensions n_dim. */
309static
310void
311mbr_join(
312/*=====*/
313 double* a, /*!< in/out: the first mbr,
314 where the joined result will be. */
315 const double* b, /*!< in: the second mbr. */
316 int n_dim) /*!< in: dimensions. */
317{
318 double* end = a + n_dim * 2;
319
320 do {
321 if (a[0] > b[0]) {
322 a[0] = b[0];
323 }
324
325 if (a[1] < b[1]) {
326 a[1] = b[1];
327 }
328
329 a += 2;
330 b += 2;
331
332 } while (a != end);
333}
334
335/*************************************************************//**
336Counts the square of mbr which is the join of a and b. Both a and b
337are of dimensions n_dim. */
338static
339double
340mbr_join_square(
341/*============*/
342 const double* a, /*!< in: the first mbr. */
343 const double* b, /*!< in: the second mbr. */
344 int n_dim) /*!< in: dimensions. */
345{
346 const double* end = a + n_dim * 2;
347 double square = 1.0;
348
349 do {
350 square *= std::max(a[1], b[1]) - std::min(a[0], b[0]);
351
352 a += 2;
353 b += 2;
354 } while (a != end);
355
356 /* Check if finite (not infinity or NaN),
357 so we don't get NaN in calculations */
358 if (!std::isfinite(square)) {
359 return DBL_MAX;
360 }
361
362 return square;
363}
364
365/*************************************************************//**
366Counts the square of mbr of dimension n_dim. */
367static
368double
369count_square(
370/*=========*/
371 const double* a, /*!< in: the mbr. */
372 int n_dim) /*!< in: dimensions. */
373{
374 const double* end = a + n_dim * 2;
375 double square = 1.0;
376
377 do {
378 square *= a[1] - a[0];
379 a += 2;
380 } while (a != end);
381
382 return square;
383}
384
385/*************************************************************//**
386Copy mbr of dimension n_dim from src to dst. */
387inline
388static
389void
390copy_coords(
391/*========*/
392 double* dst, /*!< in/out: destination. */
393 const double* src, /*!< in: source. */
394 int)
395{
396 memcpy(dst, src, DATA_MBR_LEN);
397}
398
399/*************************************************************//**
400Select two nodes to collect group upon */
401static
402void
403pick_seeds(
404/*=======*/
405 rtr_split_node_t* node, /*!< in: split nodes. */
406 int n_entries, /*!< in: entries number. */
407 rtr_split_node_t** seed_a, /*!< out: seed 1. */
408 rtr_split_node_t** seed_b, /*!< out: seed 2. */
409 int n_dim) /*!< in: dimensions. */
410{
411 rtr_split_node_t* cur1;
412 rtr_split_node_t* lim1 = node + (n_entries - 1);
413 rtr_split_node_t* cur2;
414 rtr_split_node_t* lim2 = node + n_entries;
415
416 double max_d = -DBL_MAX;
417 double d;
418
419 *seed_a = node;
420 *seed_b = node + 1;
421
422 for (cur1 = node; cur1 < lim1; ++cur1) {
423 for (cur2 = cur1 + 1; cur2 < lim2; ++cur2) {
424 d = mbr_join_square(cur1->coords, cur2->coords, n_dim) -
425 cur1->square - cur2->square;
426 if (d > max_d) {
427 max_d = d;
428 *seed_a = cur1;
429 *seed_b = cur2;
430 }
431 }
432 }
433}
434
435/*********************************************************//**
436Generates a random iboolean value.
437@return the random value */
438static
439ibool
440ut_rnd_gen_ibool(void)
441/*=================*/
442{
443 ulint x;
444
445 x = ut_rnd_gen_ulint();
446
447 if (((x >> 20) + (x >> 15)) & 1) {
448
449 return(TRUE);
450 }
451
452 return(FALSE);
453}
454
455/*************************************************************//**
456Select next node and group where to add. */
457static
458void
459pick_next(
460/*======*/
461 rtr_split_node_t* node, /*!< in: split nodes. */
462 int n_entries, /*!< in: entries number. */
463 double* g1, /*!< in: mbr of group 1. */
464 double* g2, /*!< in: mbr of group 2. */
465 rtr_split_node_t** choice, /*!< out: the next node.*/
466 int* n_group, /*!< out: group number.*/
467 int n_dim) /*!< in: dimensions. */
468{
469 rtr_split_node_t* cur = node;
470 rtr_split_node_t* end = node + n_entries;
471 double max_diff = -DBL_MAX;
472
473 for (; cur < end; ++cur) {
474 double diff;
475 double abs_diff;
476
477 if (cur->n_node != 0) {
478 continue;
479 }
480
481 diff = mbr_join_square(g1, cur->coords, n_dim) -
482 mbr_join_square(g2, cur->coords, n_dim);
483
484 abs_diff = fabs(diff);
485 if (abs_diff > max_diff) {
486 max_diff = abs_diff;
487
488 /* Introduce some randomness if the record
489 is identical */
490 if (diff == 0) {
491 diff = static_cast<double>(
492 ut_rnd_gen_ibool());
493 }
494
495 *n_group = 1 + (diff > 0);
496 *choice = cur;
497 }
498 }
499}
500
501/*************************************************************//**
502Mark not-in-group entries as n_group. */
503static
504void
505mark_all_entries(
506/*=============*/
507 rtr_split_node_t* node, /*!< in/out: split nodes. */
508 int n_entries, /*!< in: entries number. */
509 int n_group) /*!< in: group number. */
510{
511 rtr_split_node_t* cur = node;
512 rtr_split_node_t* end = node + n_entries;
513 for (; cur < end; ++cur) {
514 if (cur->n_node != 0) {
515 continue;
516 }
517 cur->n_node = n_group;
518 }
519}
520
521/*************************************************************//**
522Split rtree node.
523Return which group the first rec is in. */
524int
525split_rtree_node(
526/*=============*/
527 rtr_split_node_t* node, /*!< in: split nodes. */
528 int n_entries, /*!< in: entries number. */
529 int all_size, /*!< in: total key's size. */
530 int key_size, /*!< in: key's size. */
531 int min_size, /*!< in: minimal group size. */
532 int size1, /*!< in: size of group. */
533 int size2, /*!< in: initial group sizes */
534 double** d_buffer, /*!< in/out: buffer. */
535 int n_dim, /*!< in: dimensions. */
536 uchar* first_rec) /*!< in: the first rec. */
537{
538 rtr_split_node_t* cur;
539 rtr_split_node_t* a = NULL;
540 rtr_split_node_t* b = NULL;
541 double* g1 = reserve_coords(d_buffer, n_dim);
542 double* g2 = reserve_coords(d_buffer, n_dim);
543 rtr_split_node_t* next = NULL;
544 int next_node = 0;
545 int i;
546 int first_rec_group = 1;
547 rtr_split_node_t* end = node + n_entries;
548
549 if (all_size < min_size * 2) {
550 return 1;
551 }
552
553 cur = node;
554 for (; cur < end; ++cur) {
555 cur->square = count_square(cur->coords, n_dim);
556 cur->n_node = 0;
557 }
558
559 pick_seeds(node, n_entries, &a, &b, n_dim);
560 a->n_node = 1;
561 b->n_node = 2;
562
563 copy_coords(g1, a->coords, n_dim);
564 size1 += key_size;
565 copy_coords(g2, b->coords, n_dim);
566 size2 += key_size;
567
568 for (i = n_entries - 2; i > 0; --i) {
569 /* Can't write into group 2 */
570 if (all_size - (size2 + key_size) < min_size) {
571 mark_all_entries(node, n_entries, 1);
572 break;
573 }
574
575 /* Can't write into group 1 */
576 if (all_size - (size1 + key_size) < min_size) {
577 mark_all_entries(node, n_entries, 2);
578 break;
579 }
580
581 pick_next(node, n_entries, g1, g2, &next, &next_node, n_dim);
582 if (next_node == 1) {
583 size1 += key_size;
584 mbr_join(g1, next->coords, n_dim);
585 } else {
586 size2 += key_size;
587 mbr_join(g2, next->coords, n_dim);
588 }
589
590 next->n_node = next_node;
591
592 /* Find out where the first rec (of the page) will be at,
593 and inform the caller */
594 if (first_rec && first_rec == next->key) {
595 first_rec_group = next_node;
596 }
597 }
598
599 return(first_rec_group);
600}
601
602/*************************************************************//**
603Compares two keys a and b depending on nextflag
604nextflag can contain these flags:
605 MBR_INTERSECT(a,b) a overlaps b
606 MBR_CONTAIN(a,b) a contains b
607 MBR_DISJOINT(a,b) a disjoint b
608 MBR_WITHIN(a,b) a within b
609 MBR_EQUAL(a,b) All coordinates of MBRs are equal
610Return 0 on success, otherwise 1. */
611int
612rtree_key_cmp(
613/*==========*/
614 page_cur_mode_t mode, /*!< in: compare method. */
615 const uchar* b, /*!< in: first key. */
616 int,
617 const uchar* a, /*!< in: second key. */
618 int a_len) /*!< in: second key len. */
619{
620 double amin, amax, bmin, bmax;
621 int key_len;
622 int keyseg_len;
623
624 keyseg_len = 2 * sizeof(double);
625 for (key_len = a_len; key_len > 0; key_len -= keyseg_len) {
626 amin = mach_double_read(a);
627 bmin = mach_double_read(b);
628 amax = mach_double_read(a + sizeof(double));
629 bmax = mach_double_read(b + sizeof(double));
630
631 switch (mode) {
632 case PAGE_CUR_INTERSECT:
633 if (INTERSECT_CMP(amin, amax, bmin, bmax)) {
634 return(1);
635 }
636 break;
637 case PAGE_CUR_CONTAIN:
638 if (CONTAIN_CMP(amin, amax, bmin, bmax)) {
639 return(1);
640 }
641 break;
642 case PAGE_CUR_WITHIN:
643 if (WITHIN_CMP(amin, amax, bmin, bmax)) {
644 return(1);
645 }
646 break;
647 case PAGE_CUR_MBR_EQUAL:
648 if (EQUAL_CMP(amin, amax, bmin, bmax)) {
649 return(1);
650 }
651 break;
652 case PAGE_CUR_DISJOINT:
653 int result;
654
655 result = DISJOINT_CMP(amin, amax, bmin, bmax);
656 if (result == 0) {
657 return(0);
658 }
659
660 if (key_len - keyseg_len <= 0) {
661 return(1);
662 }
663
664 break;
665 default:
666 /* if unknown comparison operator */
667 ut_ad(0);
668 }
669
670 a += keyseg_len;
671 b += keyseg_len;
672 }
673
674 return(0);
675}
676
677/*************************************************************//**
678Calculates MBR_AREA(a+b) - MBR_AREA(a)
679Note: when 'a' and 'b' objects are far from each other,
680the area increase can be really big, so this function
681can return 'inf' as a result.
682Return the area increaed. */
683double
684rtree_area_increase(
685 const uchar* a, /*!< in: original mbr. */
686 const uchar* b, /*!< in: new mbr. */
687 int mbr_len, /*!< in: mbr length of a and b. */
688 double* ab_area) /*!< out: increased area. */
689{
690 double a_area = 1.0;
691 double loc_ab_area = 1.0;
692 double amin, amax, bmin, bmax;
693 int key_len;
694 int keyseg_len;
695 double data_round = 1.0;
696
697 keyseg_len = 2 * sizeof(double);
698
699 for (key_len = mbr_len; key_len > 0; key_len -= keyseg_len) {
700 double area;
701
702 amin = mach_double_read(a);
703 bmin = mach_double_read(b);
704 amax = mach_double_read(a + sizeof(double));
705 bmax = mach_double_read(b + sizeof(double));
706
707 area = amax - amin;
708 if (area == 0) {
709 a_area *= LINE_MBR_WEIGHTS;
710 } else {
711 a_area *= area;
712 }
713
714 area = (double)std::max(amax, bmax) -
715 (double)std::min(amin, bmin);
716 if (area == 0) {
717 loc_ab_area *= LINE_MBR_WEIGHTS;
718 } else {
719 loc_ab_area *= area;
720 }
721
722 /* Value of amax or bmin can be so large that small difference
723 are ignored. For example: 3.2884281489988079e+284 - 100 =
724 3.2884281489988079e+284. This results some area difference
725 are not detected */
726 if (loc_ab_area == a_area) {
727 if (bmin < amin || bmax > amax) {
728 data_round *= ((double)std::max(amax, bmax)
729 - amax
730 + (amin - (double)std::min(
731 amin, bmin)));
732 } else {
733 data_round *= area;
734 }
735 }
736
737 a += keyseg_len;
738 b += keyseg_len;
739 }
740
741 *ab_area = loc_ab_area;
742
743 if (loc_ab_area == a_area && data_round != 1.0) {
744 return(data_round);
745 }
746
747 return(loc_ab_area - a_area);
748}
749
750/** Calculates overlapping area
751@param[in] a mbr a
752@param[in] b mbr b
753@param[in] mbr_len mbr length
754@return overlapping area */
755double
756rtree_area_overlapping(
757 const uchar* a,
758 const uchar* b,
759 int mbr_len)
760{
761 double area = 1.0;
762 double amin;
763 double amax;
764 double bmin;
765 double bmax;
766 int key_len;
767 int keyseg_len;
768
769 keyseg_len = 2 * sizeof(double);
770
771 for (key_len = mbr_len; key_len > 0; key_len -= keyseg_len) {
772 amin = mach_double_read(a);
773 bmin = mach_double_read(b);
774 amax = mach_double_read(a + sizeof(double));
775 bmax = mach_double_read(b + sizeof(double));
776
777 amin = std::max(amin, bmin);
778 amax = std::min(amax, bmax);
779
780 if (amin > amax) {
781 return(0);
782 } else {
783 area *= (amax - amin);
784 }
785
786 a += keyseg_len;
787 b += keyseg_len;
788 }
789
790 return(area);
791}
792
793/** Get the wkb of default POINT value, which represents POINT(0 0)
794if it's of dimension 2, etc.
795@param[in] n_dims dimensions
796@param[out] wkb wkb buffer for default POINT
797@param[in] len length of wkb buffer
798@return non-0 indicate the length of wkb of the default POINT,
7990 if the buffer is too small */
800uint
801get_wkb_of_default_point(
802 uint n_dims,
803 uchar* wkb,
804 uint len)
805{
806 // JAN: TODO: MYSQL 5.7 GIS
807 #define GEOM_HEADER_SIZE 16
808 if (len < GEOM_HEADER_SIZE + sizeof(double) * n_dims) {
809 return(0);
810 }
811
812 /** POINT wkb comprises SRID, wkb header(byte order and type)
813 and coordinates of the POINT */
814 len = GEOM_HEADER_SIZE + sizeof(double) * n_dims;
815 /** We always use 0 as default coordinate */
816 memset(wkb, 0, len);
817 /** We don't need to write SRID, write 0x01 for Byte Order */
818 mach_write_to_n_little_endian(wkb + SRID_SIZE, 1, 0x01);
819 /** Write wkbType::wkbPoint for the POINT type */
820 mach_write_to_n_little_endian(wkb + SRID_SIZE + 1, 4, wkbPoint);
821
822 return(len);
823}
824