1 /* Copyright (c) 2002, 2021, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22
23 #include "myisamdef.h"
24 #include "rt_index.h"
25 #include "rt_key.h"
26 #include "rt_mbr.h"
27
28 typedef struct
29 {
30 double square;
31 int n_node;
32 uchar *key;
33 double *coords;
34 } SplitStruct;
35
reserve_coords(double ** d_buffer,int n_dim)36 inline static double *reserve_coords(double **d_buffer, int n_dim)
37 {
38 double *coords = *d_buffer;
39 (*d_buffer) += n_dim * 2;
40 return coords;
41 }
42
mbr_join(double * a,const double * b,int n_dim)43 static void mbr_join(double *a, const double *b, int n_dim)
44 {
45 double *end = a + n_dim * 2;
46 do
47 {
48 if (a[0] > b[0])
49 a[0] = b[0];
50
51 if (a[1] < b[1])
52 a[1] = b[1];
53
54 a += 2;
55 b += 2;
56 }while (a != end);
57 }
58
59 /*
60 Counts the square of mbr which is a join of a and b
61 */
mbr_join_square(const double * a,const double * b,int n_dim)62 static double mbr_join_square(const double *a, const double *b, int n_dim)
63 {
64 const double *end = a + n_dim * 2;
65 double square = 1.0;
66 do
67 {
68 square *=
69 ((a[1] < b[1]) ? b[1] : a[1]) - ((a[0] > b[0]) ? b[0] : a[0]);
70
71 a += 2;
72 b += 2;
73 }while (a != end);
74
75 /* Check for infinity or NaN */
76 if (my_isinf(square) || my_isnan(square))
77 square = DBL_MAX;
78
79 return square;
80 }
81
count_square(const double * a,int n_dim)82 static double count_square(const double *a, int n_dim)
83 {
84 const double *end = a + n_dim * 2;
85 double square = 1.0;
86 do
87 {
88 square *= a[1] - a[0];
89 a += 2;
90 }while (a != end);
91 return square;
92 }
93
copy_coords(double * dst,const double * src,int n_dim)94 inline static void copy_coords(double *dst, const double *src, int n_dim)
95 {
96 memcpy(dst, src, sizeof(double) * (n_dim * 2));
97 }
98
99 /*
100 Select two nodes to collect group upon
101 */
pick_seeds(SplitStruct * node,int n_entries,SplitStruct ** seed_a,SplitStruct ** seed_b,int n_dim)102 static void pick_seeds(SplitStruct *node, int n_entries,
103 SplitStruct **seed_a, SplitStruct **seed_b, int n_dim)
104 {
105 SplitStruct *cur1;
106 SplitStruct *lim1 = node + (n_entries - 1);
107 SplitStruct *cur2;
108 SplitStruct *lim2 = node + n_entries;
109
110 double max_d = -DBL_MAX;
111 double d;
112
113 *seed_a = node;
114 *seed_b = node + 1;
115
116 for (cur1 = node; cur1 < lim1; ++cur1)
117 {
118 for (cur2=cur1 + 1; cur2 < lim2; ++cur2)
119 {
120
121 d = mbr_join_square(cur1->coords, cur2->coords, n_dim) - cur1->square -
122 cur2->square;
123 if (d > max_d)
124 {
125 max_d = d;
126 *seed_a = cur1;
127 *seed_b = cur2;
128 }
129 }
130 }
131 }
132
133 /*
134 Select next node and group where to add
135 */
pick_next(SplitStruct * node,int n_entries,double * g1,double * g2,SplitStruct ** choice,int * n_group,int n_dim)136 static void pick_next(SplitStruct *node, int n_entries, double *g1, double *g2,
137 SplitStruct **choice, int *n_group, int n_dim)
138 {
139 SplitStruct *cur = node;
140 SplitStruct *end = node + n_entries;
141
142 double max_diff = -DBL_MAX;
143
144 for (; cur<end; ++cur)
145 {
146 double diff;
147 double abs_diff;
148
149 if (cur->n_node)
150 {
151 continue;
152 }
153
154 diff = mbr_join_square(g1, cur->coords, n_dim) -
155 mbr_join_square(g2, cur->coords, n_dim);
156
157 abs_diff = fabs(diff);
158 if (abs_diff > max_diff)
159 {
160 max_diff = abs_diff;
161 *n_group = 1 + (diff > 0);
162 *choice = cur;
163 }
164 }
165 }
166
167 /*
168 Mark not-in-group entries as n_group
169 */
mark_all_entries(SplitStruct * node,int n_entries,int n_group)170 static void mark_all_entries(SplitStruct *node, int n_entries, int n_group)
171 {
172 SplitStruct *cur = node;
173 SplitStruct *end = node + n_entries;
174 for (; cur<end; ++cur)
175 {
176 if (cur->n_node)
177 {
178 continue;
179 }
180 cur->n_node = n_group;
181 }
182 }
183
split_rtree_node(SplitStruct * node,int n_entries,int all_size,int key_size,int min_size,int size1,int size2,double ** d_buffer,int n_dim)184 static int split_rtree_node(SplitStruct *node, int n_entries,
185 int all_size, /* Total key's size */
186 int key_size,
187 int min_size, /* Minimal group size */
188 int size1, int size2 /* initial group sizes */,
189 double **d_buffer, int n_dim)
190 {
191 SplitStruct *cur;
192 SplitStruct *a= NULL, *b= NULL;
193 double *g1 = reserve_coords(d_buffer, n_dim);
194 double *g2 = reserve_coords(d_buffer, n_dim);
195 SplitStruct *next= NULL;
196 int next_node= 0;
197 int i;
198 SplitStruct *end = node + n_entries;
199
200 if (all_size < min_size * 2)
201 {
202 return 1;
203 }
204
205 cur = node;
206 for (; cur<end; ++cur)
207 {
208 cur->square = count_square(cur->coords, n_dim);
209 cur->n_node = 0;
210 }
211
212 pick_seeds(node, n_entries, &a, &b, n_dim);
213 a->n_node = 1;
214 b->n_node = 2;
215
216
217 copy_coords(g1, a->coords, n_dim);
218 size1 += key_size;
219 copy_coords(g2, b->coords, n_dim);
220 size2 += key_size;
221
222
223 for (i=n_entries - 2; i>0; --i)
224 {
225 if (all_size - (size2 + key_size) < min_size) /* Can't write into group 2 */
226 {
227 mark_all_entries(node, n_entries, 1);
228 break;
229 }
230
231 if (all_size - (size1 + key_size) < min_size) /* Can't write into group 1 */
232 {
233 mark_all_entries(node, n_entries, 2);
234 break;
235 }
236
237 pick_next(node, n_entries, g1, g2, &next, &next_node, n_dim);
238 if (next_node == 1)
239 {
240 size1 += key_size;
241 mbr_join(g1, next->coords, n_dim);
242 }
243 else
244 {
245 size2 += key_size;
246 mbr_join(g2, next->coords, n_dim);
247 }
248 next->n_node = next_node;
249 }
250
251 return 0;
252 }
253
rtree_split_page(MI_INFO * info,MI_KEYDEF * keyinfo,uchar * page,uchar * key,uint key_length,my_off_t * new_page_offs)254 int rtree_split_page(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page, uchar *key,
255 uint key_length, my_off_t *new_page_offs)
256 {
257 int n1, n2; /* Number of items in groups */
258
259 SplitStruct *task;
260 SplitStruct *cur;
261 SplitStruct *stop;
262 double *coord_buf;
263 double *next_coord;
264 int n_dim;
265 uchar *source_cur, *cur1, *cur2;
266 uchar *new_page= info->buff;
267 int err_code= 0;
268 uint nod_flag= mi_test_if_nod(page);
269 uint full_length= key_length + (nod_flag ? nod_flag :
270 info->s->base.rec_reflength);
271 int max_keys= (mi_getint(page)-2) / (full_length);
272 DBUG_ENTER("rtree_split_page");
273 DBUG_PRINT("rtree", ("splitting block"));
274
275 n_dim = keyinfo->keysegs / 2;
276
277 if (!(coord_buf= (double*) my_alloca(n_dim * 2 * sizeof(double) *
278 (max_keys + 1 + 4) +
279 sizeof(SplitStruct) * (max_keys + 1))))
280 DBUG_RETURN(-1); /* purecov: inspected */
281
282 task= (SplitStruct *)(coord_buf + n_dim * 2 * (max_keys + 1 + 4));
283
284 next_coord = coord_buf;
285
286 stop = task + max_keys;
287 source_cur = rt_PAGE_FIRST_KEY(page, nod_flag);
288
289 for (cur = task; cur < stop; ++cur, source_cur = rt_PAGE_NEXT_KEY(source_cur,
290 key_length, nod_flag))
291 {
292 cur->coords = reserve_coords(&next_coord, n_dim);
293 cur->key = source_cur;
294 rtree_d_mbr(keyinfo->seg, source_cur, key_length, cur->coords);
295 }
296
297 cur->coords = reserve_coords(&next_coord, n_dim);
298 rtree_d_mbr(keyinfo->seg, key, key_length, cur->coords);
299 cur->key = key;
300
301 if (split_rtree_node(task, max_keys + 1,
302 mi_getint(page) + full_length + 2, full_length,
303 rt_PAGE_MIN_SIZE(keyinfo->block_length),
304 2, 2, &next_coord, n_dim))
305 {
306 err_code = 1;
307 goto split_err;
308 }
309
310 info->buff_used= 1;
311 stop = task + (max_keys + 1);
312 cur1 = rt_PAGE_FIRST_KEY(page, nod_flag);
313 cur2 = rt_PAGE_FIRST_KEY(new_page, nod_flag);
314
315 n1= n2 = 0;
316 for (cur = task; cur < stop; ++cur)
317 {
318 uchar *to;
319 if (cur->n_node == 1)
320 {
321 to = cur1;
322 cur1 = rt_PAGE_NEXT_KEY(cur1, key_length, nod_flag);
323 ++n1;
324 }
325 else
326 {
327 to = cur2;
328 cur2 = rt_PAGE_NEXT_KEY(cur2, key_length, nod_flag);
329 ++n2;
330 }
331 if (to != cur->key)
332 memcpy(to - nod_flag, cur->key - nod_flag, full_length);
333 }
334
335 mi_putint(page, 2 + n1 * full_length, nod_flag);
336 mi_putint(new_page, 2 + n2 * full_length, nod_flag);
337
338 if ((*new_page_offs= _mi_new(info, keyinfo, DFLT_INIT_HITS)) ==
339 HA_OFFSET_ERROR)
340 err_code= -1;
341 else
342 err_code= _mi_write_keypage(info, keyinfo, *new_page_offs,
343 DFLT_INIT_HITS, new_page);
344 DBUG_PRINT("rtree", ("split new block: %lu", (ulong) *new_page_offs));
345
346 split_err:
347 DBUG_RETURN(err_code);
348 }
349