1 /* Copyright (C) 2006 MySQL AB & Ramil Kalimullin & MySQL Finland AB
2 & TCX DataKonsult AB
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */
16
17 #include "maria_def.h"
18 #include "trnman.h"
19 #include "ma_key_recover.h"
20
21 #ifdef HAVE_RTREE_KEYS
22
23 #include "ma_rt_index.h"
24 #include "ma_rt_key.h"
25 #include "ma_rt_mbr.h"
26
27 #define REINSERT_BUFFER_INC 10
28 #define PICK_BY_AREA
29 /*#define PICK_BY_PERIMETER*/
30
31 typedef struct st_page_level
32 {
33 uint level;
34 my_off_t offs;
35 } stPageLevel;
36
37 typedef struct st_page_list
38 {
39 uint n_pages;
40 uint m_pages;
41 stPageLevel *pages;
42 } stPageList;
43
44
45 /*
46 Find next key in r-tree according to search_flag recursively
47
48 NOTES
49 Used in maria_rtree_find_first() and maria_rtree_find_next()
50
51 RETURN
52 -1 Error
53 0 Found
54 1 Not found
55 */
56
maria_rtree_find_req(MARIA_HA * info,MARIA_KEYDEF * keyinfo,uint32 search_flag,uint nod_cmp_flag,my_off_t page_pos,int level)57 static int maria_rtree_find_req(MARIA_HA *info, MARIA_KEYDEF *keyinfo,
58 uint32 search_flag,
59 uint nod_cmp_flag, my_off_t page_pos,
60 int level)
61 {
62 MARIA_SHARE *share= info->s;
63 uint nod_flag;
64 int res;
65 uchar *page_buf, *k, *last;
66 int key_data_length;
67 uint *saved_key= (uint*) (info->maria_rtree_recursion_state) + level;
68 MARIA_PAGE page;
69
70 if (!(page_buf= (uchar*) my_alloca((uint) keyinfo->block_length)))
71 {
72 my_errno= HA_ERR_OUT_OF_MEM;
73 return -1;
74 }
75 if (_ma_fetch_keypage(&page, info, keyinfo, page_pos,
76 PAGECACHE_LOCK_LEFT_UNLOCKED,
77 DFLT_INIT_HITS, page_buf, 0))
78 goto err;
79 nod_flag= page.node;
80
81 key_data_length= keyinfo->keylength - share->base.rec_reflength;
82
83 if (info->maria_rtree_recursion_depth >= level)
84 {
85 k= page_buf + *saved_key;
86 }
87 else
88 {
89 k= rt_PAGE_FIRST_KEY(share, page_buf, nod_flag);
90 }
91 last= rt_PAGE_END(&page);
92
93 for (; k < last; k= rt_PAGE_NEXT_KEY(share, k, key_data_length, nod_flag))
94 {
95 if (nod_flag)
96 {
97 /* this is an internal node in the tree */
98 if (!(res= maria_rtree_key_cmp(keyinfo->seg,
99 info->first_mbr_key, k,
100 info->last_rkey_length, nod_cmp_flag)))
101 {
102 switch ((res= maria_rtree_find_req(info, keyinfo, search_flag,
103 nod_cmp_flag,
104 _ma_kpos(nod_flag, k),
105 level + 1)))
106 {
107 case 0: /* found - exit from recursion */
108 *saved_key= (uint) (k - page_buf);
109 goto ok;
110 case 1: /* not found - continue searching */
111 info->maria_rtree_recursion_depth= level;
112 break;
113 default: /* error */
114 case -1:
115 goto err;
116 }
117 }
118 }
119 else
120 {
121 /* this is a leaf */
122 if (!maria_rtree_key_cmp(keyinfo->seg, info->first_mbr_key,
123 k, info->last_rkey_length, search_flag))
124 {
125 uchar *after_key= rt_PAGE_NEXT_KEY(share, k, key_data_length, 0);
126 MARIA_KEY tmp_key;
127
128 /*
129 We don't need to set all MARIA_KEY elements here as
130 _ma_row_pos_from_key() only uses a few of them.
131 */
132 tmp_key.keyinfo= keyinfo;
133 tmp_key.data= k;
134 tmp_key.data_length= key_data_length;
135
136 info->cur_row.lastpos= _ma_row_pos_from_key(&tmp_key);
137 info->last_key.data_length= key_data_length;
138 info->last_key.ref_length= share->base.rec_reflength;
139 info->last_key.flag= 0;
140 memcpy(info->last_key.data, k,
141 info->last_key.data_length + info->last_key.ref_length);
142 info->maria_rtree_recursion_depth= level;
143 *saved_key= (uint) (last - page_buf);
144
145 if (after_key < last)
146 {
147 uchar *keyread_buff= info->keyread_buff;
148 info->int_keypos= keyread_buff;
149 info->int_maxpos= keyread_buff + (last - after_key);
150 memcpy(keyread_buff, after_key, last - after_key);
151 info->keyread_buff_used= 0;
152 }
153 else
154 {
155 info->keyread_buff_used= 1;
156 }
157
158 res= 0;
159 goto ok;
160 }
161 }
162 }
163 info->cur_row.lastpos= HA_OFFSET_ERROR;
164 my_errno= HA_ERR_KEY_NOT_FOUND;
165 res= 1;
166
167 ok:
168 my_afree(page_buf);
169 return res;
170
171 err:
172 my_afree(page_buf);
173 info->cur_row.lastpos= HA_OFFSET_ERROR;
174 return -1;
175 }
176
177
178 /*
179 Find first key in r-tree according to search_flag condition
180
181 SYNOPSIS
182 maria_rtree_find_first()
183 info Handler to MARIA file
184 key Key to search for
185 search_flag Bitmap of flags how to do the search
186
187 RETURN
188 -1 Error
189 0 Found
190 1 Not found
191 */
192
maria_rtree_find_first(MARIA_HA * info,MARIA_KEY * key,uint32 search_flag)193 int maria_rtree_find_first(MARIA_HA *info, MARIA_KEY *key, uint32 search_flag)
194 {
195 my_off_t root;
196 uint nod_cmp_flag;
197 MARIA_KEYDEF *keyinfo= key->keyinfo;
198
199 /*
200 At the moment index can only properly handle the
201 MBR_INTERSECT, so we use it for all sorts of queries.
202 TODO: better searsh for CONTAINS/WITHIN.
203 */
204 search_flag= nod_cmp_flag= MBR_INTERSECT;
205 if ((root= info->s->state.key_root[keyinfo->key_nr]) == HA_OFFSET_ERROR)
206 {
207 my_errno= HA_ERR_END_OF_FILE;
208 return -1;
209 }
210
211 /*
212 Save searched key, include data pointer.
213 The data pointer is required if the search_flag contains MBR_DATA.
214 (minimum bounding rectangle)
215 */
216 memcpy(info->first_mbr_key, key->data, key->data_length + key->ref_length);
217 info->last_rkey_length= key->data_length;
218
219 info->maria_rtree_recursion_depth= -1;
220 info->keyread_buff_used= 1;
221
222 /*
223 TODO better search for CONTAINS/WITHIN.
224 nod_cmp_flag= ((search_flag & (MBR_EQUAL | MBR_WITHIN)) ?
225 MBR_WITHIN : MBR_INTERSECT);
226 */
227 return maria_rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag, root,
228 0);
229 }
230
231
232 /*
233 Find next key in r-tree according to search_flag condition
234
235 SYNOPSIS
236 maria_rtree_find_next()
237 info Handler to MARIA file
238 uint keynr Key number to use
239 search_flag Bitmap of flags how to do the search
240
241 RETURN
242 -1 Error
243 0 Found
244 1 Not found
245 */
246
maria_rtree_find_next(MARIA_HA * info,uint keynr,uint32 search_flag)247 int maria_rtree_find_next(MARIA_HA *info, uint keynr, uint32 search_flag)
248 {
249 my_off_t root;
250 uint32 nod_cmp_flag;
251 MARIA_KEYDEF *keyinfo= info->s->keyinfo + keynr;
252 DBUG_ASSERT(info->last_key.keyinfo == keyinfo);
253 /*
254 At the moment index can only properly handle the
255 MBR_INTERSECT, so we use it for all sorts of queries.
256 TODO: better searsh for CONTAINS/WITHIN.
257 */
258 search_flag= nod_cmp_flag= MBR_INTERSECT;
259
260 if (info->update & HA_STATE_DELETED)
261 return maria_rtree_find_first(info, &info->last_key, search_flag);
262
263 if (!info->keyread_buff_used)
264 {
265 uchar *key= info->int_keypos;
266
267 while (key < info->int_maxpos)
268 {
269 if (!maria_rtree_key_cmp(keyinfo->seg,
270 info->first_mbr_key, key,
271 info->last_rkey_length, search_flag))
272 {
273 uchar *after_key= key + keyinfo->keylength;
274 MARIA_KEY tmp_key;
275
276 /*
277 We don't need to set all MARIA_KEY elements here as
278 _ma_row_pos_from_key only uses a few of them.
279 */
280 tmp_key.keyinfo= keyinfo;
281 tmp_key.data= key;
282 tmp_key.data_length= keyinfo->keylength - info->s->base.rec_reflength;
283
284 info->cur_row.lastpos= _ma_row_pos_from_key(&tmp_key);
285 memcpy(info->last_key.data, key, info->last_key.data_length);
286
287 if (after_key < info->int_maxpos)
288 info->int_keypos= after_key;
289 else
290 info->keyread_buff_used= 1;
291 return 0;
292 }
293 key+= keyinfo->keylength;
294 }
295 }
296 if ((root= info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
297 {
298 my_errno= HA_ERR_END_OF_FILE;
299 return -1;
300 }
301
302 /*
303 TODO better search for CONTAINS/WITHIN.
304 nod_cmp_flag= (((search_flag & (MBR_EQUAL | MBR_WITHIN)) ?
305 MBR_WITHIN : MBR_INTERSECT));
306 */
307 return maria_rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag, root,
308 0);
309 }
310
311
312 /*
313 Get next key in r-tree recursively
314
315 NOTES
316 Used in maria_rtree_get_first() and maria_rtree_get_next()
317
318 RETURN
319 -1 Error
320 0 Found
321 1 Not found
322 */
323
maria_rtree_get_req(MARIA_HA * info,MARIA_KEYDEF * keyinfo,uint key_length,my_off_t page_pos,int level)324 static int maria_rtree_get_req(MARIA_HA *info, MARIA_KEYDEF *keyinfo,
325 uint key_length, my_off_t page_pos, int level)
326 {
327 MARIA_SHARE *share= info->s;
328 uchar *page_buf, *last, *k;
329 uint nod_flag, key_data_length;
330 int res;
331 uint *saved_key= (uint*) (info->maria_rtree_recursion_state) + level;
332 MARIA_PAGE page;
333
334 if (!(page_buf= (uchar*) my_alloca((uint) keyinfo->block_length)))
335 return -1;
336 if (_ma_fetch_keypage(&page, info, keyinfo, page_pos,
337 PAGECACHE_LOCK_LEFT_UNLOCKED,
338 DFLT_INIT_HITS, page_buf, 0))
339 goto err;
340 nod_flag= page.node;
341
342 key_data_length= keyinfo->keylength - share->base.rec_reflength;
343
344 if (info->maria_rtree_recursion_depth >= level)
345 {
346 k= page.buff + *saved_key;
347 if (!nod_flag)
348 {
349 /* Only leaf pages contain data references. */
350 /* Need to check next key with data reference. */
351 k= rt_PAGE_NEXT_KEY(share, k, key_data_length, nod_flag);
352 }
353 }
354 else
355 {
356 k= rt_PAGE_FIRST_KEY(share, page.buff, nod_flag);
357 }
358 last= rt_PAGE_END(&page);
359
360 for (; k < last; k= rt_PAGE_NEXT_KEY(share, k, key_data_length, nod_flag))
361 {
362 if (nod_flag)
363 {
364 /* this is an internal node in the tree */
365 switch ((res= maria_rtree_get_req(info, keyinfo, key_length,
366 _ma_kpos(nod_flag, k), level + 1)))
367 {
368 case 0: /* found - exit from recursion */
369 *saved_key= (uint) (k - page.buff);
370 goto ok;
371 case 1: /* not found - continue searching */
372 info->maria_rtree_recursion_depth= level;
373 break;
374 default:
375 case -1: /* error */
376 goto err;
377 }
378 }
379 else
380 {
381 /* this is a leaf */
382 uchar *after_key= rt_PAGE_NEXT_KEY(share, k, key_data_length, 0);
383 MARIA_KEY tmp_key;
384
385 /*
386 We don't need to set all MARIA_KEY elements here as
387 _ma_row_pos_from_key() only uses a few of them.
388 */
389 tmp_key.keyinfo= keyinfo;
390 tmp_key.data= k;
391 tmp_key.data_length= key_data_length;
392
393 info->cur_row.lastpos= _ma_row_pos_from_key(&tmp_key);
394 info->last_key.data_length= key_data_length;
395 info->last_key.ref_length= share->base.rec_reflength;
396
397 memcpy(info->last_key.data, k,
398 info->last_key.data_length + info->last_key.ref_length);
399
400 info->maria_rtree_recursion_depth= level;
401 *saved_key= (uint) (k - page.buff);
402
403 if (after_key < last)
404 {
405 uchar *keyread_buff= info->keyread_buff;
406 info->last_rtree_keypos= saved_key;
407 memcpy(keyread_buff, page.buff, page.size);
408 info->int_maxpos= keyread_buff + page.size;
409 info->keyread_buff_used= 0;
410 }
411 else
412 {
413 info->keyread_buff_used= 1;
414 }
415
416 res= 0;
417 goto ok;
418 }
419 }
420 info->cur_row.lastpos= HA_OFFSET_ERROR;
421 my_errno= HA_ERR_KEY_NOT_FOUND;
422 res= 1;
423
424 ok:
425 my_afree(page_buf);
426 return res;
427
428 err:
429 my_afree(page_buf);
430 info->cur_row.lastpos= HA_OFFSET_ERROR;
431 return -1;
432 }
433
434
435 /*
436 Get first key in r-tree
437
438 RETURN
439 -1 Error
440 0 Found
441 1 Not found
442 */
443
maria_rtree_get_first(MARIA_HA * info,uint keynr,uint key_length)444 int maria_rtree_get_first(MARIA_HA *info, uint keynr, uint key_length)
445 {
446 my_off_t root;
447 MARIA_KEYDEF *keyinfo= info->s->keyinfo + keynr;
448
449 if ((root= info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
450 {
451 my_errno= HA_ERR_END_OF_FILE;
452 return -1;
453 }
454
455 info->maria_rtree_recursion_depth= -1;
456 info->keyread_buff_used= 1;
457
458 return maria_rtree_get_req(info, keyinfo, key_length, root, 0);
459 }
460
461
462 /*
463 Get next key in r-tree
464
465 RETURN
466 -1 Error
467 0 Found
468 1 Not found
469 */
470
maria_rtree_get_next(MARIA_HA * info,uint keynr,uint key_length)471 int maria_rtree_get_next(MARIA_HA *info, uint keynr, uint key_length)
472 {
473 my_off_t root;
474 MARIA_KEYDEF *keyinfo= info->s->keyinfo + keynr;
475 uchar *keyread_buff= info->keyread_buff;
476
477 if (!info->keyread_buff_used)
478 {
479 uint key_data_length= keyinfo->keylength - info->s->base.rec_reflength;
480 /* rt_PAGE_NEXT_KEY(*info->last_rtree_keypos) */
481 uchar *key= keyread_buff + *info->last_rtree_keypos + keyinfo->keylength;
482 /* rt_PAGE_NEXT_KEY(key) */
483 uchar *after_key= key + keyinfo->keylength;
484 MARIA_KEY tmp_key;
485
486 tmp_key.keyinfo= keyinfo;
487 tmp_key.data= key;
488 tmp_key.data_length= key_data_length;
489 tmp_key.ref_length= info->s->base.rec_reflength;
490 tmp_key.flag= 0;
491
492 info->cur_row.lastpos= _ma_row_pos_from_key(&tmp_key);
493 _ma_copy_key(&info->last_key, &tmp_key);
494
495 *info->last_rtree_keypos= (uint) (key - keyread_buff);
496 if (after_key >= info->int_maxpos)
497 {
498 info->keyread_buff_used= 1;
499 }
500
501 return 0;
502 }
503 else
504 {
505 if ((root= info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
506 {
507 my_errno= HA_ERR_END_OF_FILE;
508 return -1;
509 }
510
511 return maria_rtree_get_req(info, &keyinfo[keynr], key_length, root, 0);
512 }
513 }
514
515
516 /*
517 Choose non-leaf better key for insertion
518
519 Returns a pointer inside the page_buf buffer.
520 */
521 #ifdef PICK_BY_PERIMETER
maria_rtree_pick_key(const MARIA_KEY * key,const MARIA_PAGE * page)522 static const uchar *maria_rtree_pick_key(const MARIA_KEY *key,
523 const MARIA_PAGE *page)
524 {
525 double increase;
526 double UNINIT_VAR(best_incr);
527 double perimeter;
528 double UNINIT_VAR(best_perimeter);
529 uchar *best_key= NULL;
530 const MARIA_HA *info= page->info;
531
532 uchar *k= rt_PAGE_FIRST_KEY(info->s, page->buf, page->node);
533 uchar *last= rt_PAGE_END(info, page);
534
535 for (; k < last; k= rt_PAGE_NEXT_KEY(k, key->data_length, nod_flag))
536 {
537 if ((increase= maria_rtree_perimeter_increase(keyinfo->seg, k, key,
538 &perimeter)) == -1)
539 return NULL;
540 if ((increase < best_incr)||
541 (increase == best_incr && perimeter < best_perimeter))
542 {
543 best_key= k;
544 best_perimeter= perimeter;
545 best_incr= increase;
546 }
547 }
548 return best_key;
549 }
550
551 #endif /*PICK_BY_PERIMETER*/
552
553 #ifdef PICK_BY_AREA
maria_rtree_pick_key(const MARIA_KEY * key,const MARIA_PAGE * page)554 static const uchar *maria_rtree_pick_key(const MARIA_KEY *key,
555 const MARIA_PAGE *page)
556 {
557 const MARIA_HA *info= page->info;
558 MARIA_SHARE *share= info->s;
559 double increase;
560 double best_incr= DBL_MAX;
561 double area;
562 double UNINIT_VAR(best_area);
563 const uchar *best_key= NULL;
564 const uchar *k= rt_PAGE_FIRST_KEY(share, page->buff, page->node);
565 const uchar *last= rt_PAGE_END(page);
566
567 for (; k < last;
568 k= rt_PAGE_NEXT_KEY(share, k, key->data_length, page->node))
569 {
570 /* The following is safe as -1.0 is an exact number */
571 if ((increase= maria_rtree_area_increase(key->keyinfo->seg, k, key->data,
572 key->data_length +
573 key->ref_length,
574 &area)) == -1.0)
575 return NULL;
576 /* The following should be safe, even if we compare doubles */
577 if (!best_key || increase < best_incr ||
578 ((increase == best_incr) && (area < best_area)))
579 {
580 best_key= k;
581 best_area= area;
582 best_incr= increase;
583 }
584 }
585 return best_key;
586 }
587
588 #endif /*PICK_BY_AREA*/
589
590 /*
591 Go down and insert key into tree
592
593 RETURN
594 -1 Error
595 0 Child was not split
596 1 Child was split
597 */
598
maria_rtree_insert_req(MARIA_HA * info,MARIA_KEY * key,my_off_t page_pos,my_off_t * new_page,int ins_level,int level)599 static int maria_rtree_insert_req(MARIA_HA *info, MARIA_KEY *key,
600 my_off_t page_pos, my_off_t *new_page,
601 int ins_level, int level)
602 {
603 uint nod_flag;
604 uint key_length= key->data_length;
605 int res;
606 uchar *page_buf, *k;
607 MARIA_SHARE *share= info->s;
608 MARIA_KEYDEF *keyinfo= key->keyinfo;
609 MARIA_PAGE page;
610 DBUG_ENTER("maria_rtree_insert_req");
611
612 if (!(page_buf= (uchar*) my_alloca((uint) keyinfo->block_length +
613 MARIA_MAX_KEY_BUFF)))
614 {
615 my_errno= HA_ERR_OUT_OF_MEM;
616 DBUG_RETURN(-1); /* purecov: inspected */
617 }
618 if (_ma_fetch_keypage(&page, info, keyinfo, page_pos, PAGECACHE_LOCK_WRITE,
619 DFLT_INIT_HITS, page_buf, 0))
620 goto err;
621 nod_flag= page.node;
622 DBUG_PRINT("rtree", ("page: %lu level: %d ins_level: %d nod_flag: %u",
623 (ulong) page.pos, level, ins_level, nod_flag));
624
625 if ((ins_level == -1 && nod_flag) || /* key: go down to leaf */
626 (ins_level > -1 && ins_level > level)) /* branch: go down to ins_level */
627 {
628 if (!(k= (uchar *)maria_rtree_pick_key(key, &page)))
629 goto err;
630 /* k is now a pointer inside the page_buf buffer */
631 switch ((res= maria_rtree_insert_req(info, key,
632 _ma_kpos(nod_flag, k), new_page,
633 ins_level, level + 1)))
634 {
635 case 0: /* child was not split, most common case */
636 {
637 maria_rtree_combine_rect(keyinfo->seg, k, key->data, k, key_length);
638 if (share->now_transactional &&
639 _ma_log_change(&page, k, key_length,
640 KEY_OP_DEBUG_RTREE_COMBINE))
641 goto err;
642 page_mark_changed(info, &page);
643 if (_ma_write_keypage(&page, PAGECACHE_LOCK_LEFT_WRITELOCKED,
644 DFLT_INIT_HITS))
645 goto err;
646 goto ok;
647 }
648 case 1: /* child was split */
649 {
650 /* Set new_key to point to a free buffer area */
651 uchar *new_key_buff= page_buf + keyinfo->block_length + nod_flag;
652 MARIA_KEY new_key;
653 MARIA_KEY k_key;
654
655 DBUG_ASSERT(nod_flag);
656 k_key.keyinfo= new_key.keyinfo= keyinfo;
657 new_key.data= new_key_buff;
658 k_key.data= k;
659 k_key.data_length= new_key.data_length= key->data_length;
660 k_key.ref_length= new_key.ref_length= key->ref_length;
661 k_key.flag= new_key.flag= 0; /* Safety */
662
663 /* set proper MBR for key */
664 if (maria_rtree_set_key_mbr(info, &k_key, _ma_kpos(nod_flag, k)))
665 goto err;
666 if (share->now_transactional &&
667 _ma_log_change(&page, k, key_length,
668 KEY_OP_DEBUG_RTREE_SPLIT))
669 goto err;
670 /* add new key for new page */
671 _ma_kpointer(info, new_key_buff - nod_flag, *new_page);
672 if (maria_rtree_set_key_mbr(info, &new_key, *new_page))
673 goto err;
674 res= maria_rtree_add_key(&new_key, &page, new_page);
675 page_mark_changed(info, &page);
676 if (_ma_write_keypage(&page, PAGECACHE_LOCK_LEFT_WRITELOCKED,
677 DFLT_INIT_HITS))
678 goto err;
679 goto ok;
680 }
681 default:
682 case -1: /* error */
683 {
684 goto err;
685 }
686 }
687 }
688 else
689 {
690 res= maria_rtree_add_key(key, &page, new_page);
691 page_mark_changed(info, &page);
692 if (_ma_write_keypage(&page, PAGECACHE_LOCK_LEFT_WRITELOCKED,
693 DFLT_INIT_HITS))
694 goto err;
695 }
696
697 ok:
698 my_afree(page_buf);
699 DBUG_RETURN(res);
700
701 err:
702 res= -1; /* purecov: inspected */
703 goto ok; /* purecov: inspected */
704 }
705
706
707 /**
708 Insert key into the tree
709
710 @param info table
711 @param key KEY to insert
712 @param ins_level at which level key insertion should start
713 @param root put new key_root there
714
715 @return Operation result
716 @retval -1 Error
717 @retval 0 Root was not split
718 @retval 1 Root was split
719 */
720
maria_rtree_insert_level(MARIA_HA * info,MARIA_KEY * key,int ins_level,my_off_t * root)721 int maria_rtree_insert_level(MARIA_HA *info, MARIA_KEY *key, int ins_level,
722 my_off_t *root)
723 {
724 my_off_t old_root;
725 MARIA_SHARE *share= info->s;
726 MARIA_KEYDEF *keyinfo= key->keyinfo;
727 int res;
728 my_off_t new_page;
729 enum pagecache_page_lock write_lock;
730 DBUG_ENTER("maria_rtree_insert_level");
731
732 if ((old_root= share->state.key_root[keyinfo->key_nr]) == HA_OFFSET_ERROR)
733 {
734 MARIA_PINNED_PAGE tmp_page_link, *page_link;
735 MARIA_PAGE page;
736
737 page_link= &tmp_page_link;
738 if ((old_root= _ma_new(info, DFLT_INIT_HITS, &page_link)) ==
739 HA_OFFSET_ERROR)
740 DBUG_RETURN(-1);
741 write_lock= page_link->write_lock;
742 info->keyread_buff_used= 1;
743 bzero(info->buff, share->block_size);
744 _ma_store_keynr(share, info->buff, keyinfo->key_nr);
745 _ma_store_page_used(share, info->buff, share->keypage_header);
746 _ma_page_setup(&page, info, keyinfo, old_root, info->buff);
747
748 if (share->now_transactional && _ma_log_new(&page, 1))
749 DBUG_RETURN(1);
750
751 res= maria_rtree_add_key(key, &page, NULL);
752 if (_ma_write_keypage(&page, write_lock, DFLT_INIT_HITS))
753 DBUG_RETURN(1);
754 *root= old_root;
755 DBUG_RETURN(res);
756 }
757
758 switch ((res= maria_rtree_insert_req(info, key, old_root, &new_page,
759 ins_level, 0)))
760 {
761 case 0: /* root was not split */
762 {
763 break;
764 }
765 case 1: /* root was split, grow a new root; very rare */
766 {
767 uchar *new_root_buf, *new_key_buff;
768 my_off_t new_root;
769 uint nod_flag= share->base.key_reflength;
770 MARIA_PINNED_PAGE tmp_page_link, *page_link;
771 MARIA_KEY new_key;
772 MARIA_PAGE page;
773 page_link= &tmp_page_link;
774
775 DBUG_PRINT("rtree", ("root was split, grow a new root"));
776 if (!(new_root_buf= (uchar*) my_alloca((uint) keyinfo->block_length +
777 MARIA_MAX_KEY_BUFF)))
778 {
779 my_errno= HA_ERR_OUT_OF_MEM;
780 DBUG_RETURN(-1); /* purecov: inspected */
781 }
782
783 bzero(new_root_buf, share->block_size);
784 _ma_store_keypage_flag(share, new_root_buf, KEYPAGE_FLAG_ISNOD);
785 _ma_store_keynr(share, new_root_buf, keyinfo->key_nr);
786 _ma_store_page_used(share, new_root_buf, share->keypage_header);
787 if ((new_root= _ma_new(info, DFLT_INIT_HITS, &page_link)) ==
788 HA_OFFSET_ERROR)
789 goto err;
790 write_lock= page_link->write_lock;
791
792 _ma_page_setup(&page, info, keyinfo, new_root, new_root_buf);
793
794 if (share->now_transactional && _ma_log_new(&page, 1))
795 goto err;
796
797 /* Point to some free space */
798 new_key_buff= new_root_buf + keyinfo->block_length + nod_flag;
799 new_key.keyinfo= keyinfo;
800 new_key.data= new_key_buff;
801 new_key.data_length= key->data_length;
802 new_key.ref_length= key->ref_length;
803 new_key.flag= 0;
804
805 _ma_kpointer(info, new_key_buff - nod_flag, old_root);
806 if (maria_rtree_set_key_mbr(info, &new_key, old_root))
807 goto err;
808 if (maria_rtree_add_key(&new_key, &page, NULL)
809 == -1)
810 goto err;
811 _ma_kpointer(info, new_key_buff - nod_flag, new_page);
812 if (maria_rtree_set_key_mbr(info, &new_key, new_page))
813 goto err;
814 if (maria_rtree_add_key(&new_key, &page, NULL)
815 == -1)
816 goto err;
817 if (_ma_write_keypage(&page, write_lock, DFLT_INIT_HITS))
818 goto err;
819 *root= new_root;
820 DBUG_PRINT("rtree", ("new root page: %lu level: %d nod_flag: %u",
821 (ulong) new_root, 0, page.node));
822
823 my_afree(new_root_buf);
824 break;
825 err:
826 my_afree(new_root_buf);
827 DBUG_RETURN(-1); /* purecov: inspected */
828 }
829 default:
830 case -1: /* error */
831 {
832 DBUG_ASSERT(0);
833 break;
834 }
835 }
836 DBUG_RETURN(res);
837 }
838
839
840 /*
841 Insert key into the tree - interface function
842
843 RETURN
844 1 Error
845 0 OK
846 */
847
maria_rtree_insert(MARIA_HA * info,MARIA_KEY * key)848 my_bool maria_rtree_insert(MARIA_HA *info, MARIA_KEY *key)
849 {
850 int res;
851 MARIA_SHARE *share= info->s;
852 my_off_t *root, new_root;
853 LSN lsn= LSN_IMPOSSIBLE;
854 DBUG_ENTER("maria_rtree_insert");
855
856 if (!key)
857 DBUG_RETURN(1); /* _ma_sp_make_key failed */
858
859 root= &share->state.key_root[key->keyinfo->key_nr];
860 new_root= *root;
861
862 if ((res= (maria_rtree_insert_level(info, key, -1, &new_root) == -1)))
863 goto err;
864 if (share->now_transactional)
865 res= _ma_write_undo_key_insert(info, key, root, new_root, &lsn);
866 else
867 {
868 *root= new_root;
869 _ma_fast_unlock_key_del(info);
870 }
871 _ma_unpin_all_pages_and_finalize_row(info, lsn);
872 err:
873 DBUG_RETURN(res != 0);
874 }
875
876
877 /*
878 Fill reinsert page buffer
879
880 RETURN
881 1 Error
882 0 OK
883 */
884
maria_rtree_fill_reinsert_list(stPageList * ReinsertList,my_off_t page,int level)885 static my_bool maria_rtree_fill_reinsert_list(stPageList *ReinsertList,
886 my_off_t page, int level)
887 {
888 DBUG_ENTER("maria_rtree_fill_reinsert_list");
889 DBUG_PRINT("rtree", ("page: %lu level: %d", (ulong) page, level));
890 if (ReinsertList->n_pages == ReinsertList->m_pages)
891 {
892 ReinsertList->m_pages += REINSERT_BUFFER_INC;
893 if (!(ReinsertList->pages= (stPageLevel*)my_realloc((uchar*)ReinsertList->pages,
894 ReinsertList->m_pages * sizeof(stPageLevel), MYF(MY_ALLOW_ZERO_PTR))))
895 goto err;
896 }
897 /* save page to ReinsertList */
898 ReinsertList->pages[ReinsertList->n_pages].offs= page;
899 ReinsertList->pages[ReinsertList->n_pages].level= level;
900 ReinsertList->n_pages++;
901 DBUG_RETURN(0);
902
903 err:
904 DBUG_RETURN(1); /* purecov: inspected */
905 }
906
907
908 /*
909 Go down and delete key from the tree
910
911 RETURN
912 -1 Error
913 0 Deleted
914 1 Not found
915 2 Empty leaf
916 */
917
maria_rtree_delete_req(MARIA_HA * info,const MARIA_KEY * key,my_off_t page_pos,uint * page_size,stPageList * ReinsertList,int level)918 static int maria_rtree_delete_req(MARIA_HA *info, const MARIA_KEY *key,
919 my_off_t page_pos, uint *page_size,
920 stPageList *ReinsertList, int level)
921 {
922 ulong i;
923 uint nod_flag;
924 int res;
925 uchar *page_buf, *last, *k;
926 MARIA_SHARE *share= info->s;
927 MARIA_KEYDEF *keyinfo= key->keyinfo;
928 MARIA_PAGE page;
929 DBUG_ENTER("maria_rtree_delete_req");
930
931 if (!(page_buf= (uchar*) my_alloca((uint) keyinfo->block_length)))
932 {
933 my_errno= HA_ERR_OUT_OF_MEM;
934 DBUG_RETURN(-1); /* purecov: inspected */
935 }
936 if (_ma_fetch_keypage(&page, info, keyinfo, page_pos, PAGECACHE_LOCK_WRITE,
937 DFLT_INIT_HITS, page_buf, 0))
938 goto err;
939 nod_flag= page.node;
940 DBUG_PRINT("rtree", ("page: %lu level: %d nod_flag: %u",
941 (ulong) page_pos, level, nod_flag));
942
943 k= rt_PAGE_FIRST_KEY(share, page_buf, nod_flag);
944 last= rt_PAGE_END(&page);
945
946 for (i= 0;
947 k < last;
948 k= rt_PAGE_NEXT_KEY(share, k, key->data_length, nod_flag), i++)
949 {
950 if (nod_flag)
951 {
952 /* not leaf */
953 if (!maria_rtree_key_cmp(keyinfo->seg, key->data, k, key->data_length,
954 MBR_WITHIN))
955 {
956 switch ((res= maria_rtree_delete_req(info, key,
957 _ma_kpos(nod_flag, k),
958 page_size, ReinsertList,
959 level + 1)))
960 {
961 case 0: /* deleted */
962 {
963 /* test page filling */
964 if (*page_size + key->data_length >=
965 rt_PAGE_MIN_SIZE(keyinfo->block_length))
966 {
967 /* OK */
968 /* Calculate a new key value (MBR) for the shrinked block. */
969 MARIA_KEY tmp_key;
970 tmp_key.keyinfo= keyinfo;
971 tmp_key.data= k;
972 tmp_key.data_length= key->data_length;
973 tmp_key.ref_length= key->ref_length;
974 tmp_key.flag= 0; /* Safety */
975
976 if (maria_rtree_set_key_mbr(info, &tmp_key,
977 _ma_kpos(nod_flag, k)))
978 goto err;
979 if (share->now_transactional &&
980 _ma_log_change(&page, k, key->data_length,
981 KEY_OP_DEBUG_RTREE_SET_KEY))
982 goto err;
983 page_mark_changed(info, &page)
984 if (_ma_write_keypage(&page,
985 PAGECACHE_LOCK_LEFT_WRITELOCKED,
986 DFLT_INIT_HITS))
987 goto err;
988 }
989 else
990 {
991 /*
992 Too small: delete key & add it descendant to reinsert list.
993 Store position and level of the block so that it can be
994 accessed later for inserting the remaining keys.
995 */
996 DBUG_PRINT("rtree", ("too small. move block to reinsert list"));
997 if (maria_rtree_fill_reinsert_list(ReinsertList,
998 _ma_kpos(nod_flag, k),
999 level + 1))
1000 goto err;
1001 /*
1002 Delete the key that references the block. This makes the
1003 block disappear from the index. Hence we need to insert
1004 its remaining keys later. Note: if the block is a branch
1005 block, we do not only remove this block, but the whole
1006 subtree. So we need to re-insert its keys on the same
1007 level later to reintegrate the subtrees.
1008 */
1009 if (maria_rtree_delete_key(&page, k, key->data_length))
1010 goto err;
1011 page_mark_changed(info, &page);
1012 if (_ma_write_keypage(&page, PAGECACHE_LOCK_LEFT_WRITELOCKED,
1013 DFLT_INIT_HITS))
1014 goto err;
1015 *page_size= page.size;
1016 }
1017
1018 goto ok;
1019 }
1020 case 1: /* not found - continue searching */
1021 {
1022 break;
1023 }
1024 case 2: /* vacuous case: last key in the leaf */
1025 {
1026 if (maria_rtree_delete_key(&page, k, key->data_length))
1027 goto err;
1028 page_mark_changed(info, &page);
1029 if (_ma_write_keypage(&page, PAGECACHE_LOCK_LEFT_WRITELOCKED,
1030 DFLT_INIT_HITS))
1031 goto err;
1032 *page_size= page.size;
1033 res= 0;
1034 goto ok;
1035 }
1036 default: /* error */
1037 case -1:
1038 {
1039 goto err;
1040 }
1041 }
1042 }
1043 }
1044 else
1045 {
1046 /* leaf */
1047 if (!maria_rtree_key_cmp(keyinfo->seg, key->data, k, key->data_length,
1048 MBR_EQUAL | MBR_DATA))
1049 {
1050 page_mark_changed(info, &page);
1051 if (maria_rtree_delete_key(&page, k, key->data_length))
1052 goto err;
1053 *page_size= page.size;
1054 if (*page_size == info->s->keypage_header)
1055 {
1056 /* last key in the leaf */
1057 res= 2;
1058 if (_ma_dispose(info, page.pos, 0))
1059 goto err;
1060 }
1061 else
1062 {
1063 res= 0;
1064 if (_ma_write_keypage(&page, PAGECACHE_LOCK_LEFT_WRITELOCKED,
1065 DFLT_INIT_HITS))
1066 goto err;
1067 }
1068 goto ok;
1069 }
1070 }
1071 }
1072 res= 1;
1073
1074 ok:
1075 my_afree(page_buf);
1076 DBUG_RETURN(res);
1077
1078 err:
1079 my_afree(page_buf);
1080 DBUG_RETURN(-1); /* purecov: inspected */
1081 }
1082
1083
1084 /*
1085 Delete key - interface function
1086
1087 RETURN
1088 1 Error
1089 0 Deleted
1090 */
1091
maria_rtree_delete(MARIA_HA * info,MARIA_KEY * key)1092 my_bool maria_rtree_delete(MARIA_HA *info, MARIA_KEY *key)
1093 {
1094 MARIA_SHARE *share= info->s;
1095 my_off_t new_root= share->state.key_root[key->keyinfo->key_nr];
1096 int res;
1097 LSN lsn= LSN_IMPOSSIBLE;
1098 DBUG_ENTER("maria_rtree_delete");
1099
1100 if ((res= maria_rtree_real_delete(info, key, &new_root)))
1101 goto err;
1102
1103 if (share->now_transactional)
1104 res= _ma_write_undo_key_delete(info, key, new_root, &lsn);
1105 else
1106 share->state.key_root[key->keyinfo->key_nr]= new_root;
1107
1108 err:
1109 _ma_fast_unlock_key_del(info);
1110 _ma_unpin_all_pages_and_finalize_row(info, lsn);
1111 DBUG_RETURN(res != 0);
1112 }
1113
1114
maria_rtree_real_delete(MARIA_HA * info,MARIA_KEY * key,my_off_t * root)1115 my_bool maria_rtree_real_delete(MARIA_HA *info, MARIA_KEY *key,
1116 my_off_t *root)
1117 {
1118 uint page_size;
1119 stPageList ReinsertList;
1120 my_off_t old_root;
1121 MARIA_SHARE *share= info->s;
1122 MARIA_KEYDEF *keyinfo= key->keyinfo;
1123 uint key_data_length= key->data_length;
1124 DBUG_ENTER("maria_rtree_real_delete");
1125
1126 if ((old_root= share->state.key_root[keyinfo->key_nr]) ==
1127 HA_OFFSET_ERROR)
1128 {
1129 my_errno= HA_ERR_END_OF_FILE;
1130 DBUG_RETURN(1); /* purecov: inspected */
1131 }
1132 DBUG_PRINT("rtree", ("starting deletion at root page: %lu",
1133 (ulong) old_root));
1134
1135 ReinsertList.pages= NULL;
1136 ReinsertList.n_pages= 0;
1137 ReinsertList.m_pages= 0;
1138
1139 switch (maria_rtree_delete_req(info, key, old_root, &page_size,
1140 &ReinsertList, 0)) {
1141 case 2: /* empty */
1142 {
1143 *root= HA_OFFSET_ERROR;
1144 break;
1145 }
1146 case 0: /* deleted */
1147 {
1148 uint nod_flag;
1149 ulong i;
1150 uchar *page_buf;
1151 MARIA_PAGE page;
1152 MARIA_KEY tmp_key;
1153 tmp_key.keyinfo= key->keyinfo;
1154 tmp_key.data_length= key->data_length;
1155 tmp_key.ref_length= key->ref_length;
1156 tmp_key.flag= 0; /* Safety */
1157
1158 if (ReinsertList.n_pages)
1159 {
1160 if (!(page_buf= (uchar*) my_alloca((uint) keyinfo->block_length)))
1161 {
1162 my_errno= HA_ERR_OUT_OF_MEM;
1163 goto err;
1164 }
1165
1166 for (i= 0; i < ReinsertList.n_pages; ++i)
1167 {
1168 uchar *k, *last;
1169 if (_ma_fetch_keypage(&page, info, keyinfo, ReinsertList.pages[i].offs,
1170 PAGECACHE_LOCK_WRITE,
1171 DFLT_INIT_HITS, page_buf, 0))
1172 goto err;
1173 nod_flag= page.node;
1174 DBUG_PRINT("rtree", ("reinserting keys from "
1175 "page: %lu level: %d nod_flag: %u",
1176 (ulong) ReinsertList.pages[i].offs,
1177 ReinsertList.pages[i].level, nod_flag));
1178
1179 k= rt_PAGE_FIRST_KEY(share, page.buff, nod_flag);
1180 last= rt_PAGE_END(&page);
1181 for (; k < last; k= rt_PAGE_NEXT_KEY(share, k, key_data_length,
1182 nod_flag))
1183 {
1184 int res;
1185 tmp_key.data= k;
1186 if ((res= maria_rtree_insert_level(info, &tmp_key,
1187 ReinsertList.pages[i].level,
1188 root)) == -1)
1189 {
1190 my_afree(page_buf);
1191 goto err;
1192 }
1193 if (res)
1194 {
1195 uint j;
1196 DBUG_PRINT("rtree", ("root has been split, adjust levels"));
1197 for (j= i; j < ReinsertList.n_pages; j++)
1198 {
1199 ReinsertList.pages[j].level++;
1200 DBUG_PRINT("rtree", ("keys from page: %lu now level: %d",
1201 (ulong) ReinsertList.pages[i].offs,
1202 ReinsertList.pages[i].level));
1203 }
1204 }
1205 }
1206 page_mark_changed(info, &page);
1207 if (_ma_dispose(info, page.pos, 0))
1208 {
1209 my_afree(page_buf);
1210 goto err;
1211 }
1212 }
1213 my_afree(page_buf);
1214 my_free(ReinsertList.pages);
1215 }
1216
1217 /* check for redundant root (not leaf, 1 child) and eliminate */
1218 if ((old_root= *root) == HA_OFFSET_ERROR)
1219 goto err;
1220 if (_ma_fetch_keypage(&page, info, keyinfo, old_root,
1221 PAGECACHE_LOCK_WRITE,
1222 DFLT_INIT_HITS, info->buff, 0))
1223 goto err;
1224 nod_flag= page.node;
1225 if (nod_flag && (page.size == share->keypage_header + key_data_length +
1226 nod_flag))
1227 {
1228 *root= _ma_kpos(nod_flag,
1229 rt_PAGE_FIRST_KEY(share, info->buff, nod_flag));
1230 page_mark_changed(info, &page);
1231 if (_ma_dispose(info, page.pos, 0))
1232 goto err;
1233 }
1234 info->update= HA_STATE_DELETED;
1235 break;
1236 }
1237 case 1: /* not found */
1238 {
1239 my_errno= HA_ERR_KEY_NOT_FOUND;
1240 goto err;
1241 }
1242 case -1: /* error */
1243 default:
1244 goto err; /* purecov: inspected */
1245 }
1246 DBUG_RETURN(0);
1247
1248 err:
1249 DBUG_RETURN(1);
1250 }
1251
1252
1253 /*
1254 Estimate number of suitable keys in the tree
1255
1256 RETURN
1257 estimated value
1258 */
1259
maria_rtree_estimate(MARIA_HA * info,MARIA_KEY * key,uint32 flag)1260 ha_rows maria_rtree_estimate(MARIA_HA *info, MARIA_KEY *key, uint32 flag)
1261 {
1262 my_off_t root;
1263 uint i= 0;
1264 uint nod_flag, key_data_length;
1265 uchar *page_buf, *k, *last;
1266 double area= 0;
1267 ha_rows res= 0;
1268 MARIA_SHARE *share= info->s;
1269 MARIA_KEYDEF *keyinfo= key->keyinfo;
1270 MARIA_PAGE page;
1271
1272 if (flag & MBR_DISJOINT)
1273 return HA_POS_ERROR;
1274
1275 if ((root= share->state.key_root[key->keyinfo->key_nr]) == HA_OFFSET_ERROR)
1276 return HA_POS_ERROR;
1277 if (!(page_buf= (uchar*) my_alloca((uint) keyinfo->block_length)))
1278 return HA_POS_ERROR;
1279 if (_ma_fetch_keypage(&page, info, keyinfo, root,
1280 PAGECACHE_LOCK_LEFT_UNLOCKED, DFLT_INIT_HITS, page_buf,
1281 0))
1282 goto err;
1283 nod_flag= page.node;
1284
1285 key_data_length= key->data_length;
1286
1287 k= rt_PAGE_FIRST_KEY(share, page.buff, nod_flag);
1288 last= rt_PAGE_END(&page);
1289
1290 for (; k < last;
1291 k= rt_PAGE_NEXT_KEY(share, k, key_data_length, nod_flag), i++)
1292 {
1293 if (nod_flag)
1294 {
1295 double k_area= maria_rtree_rect_volume(keyinfo->seg, k, key_data_length);
1296
1297 /* The following should be safe, even if we compare doubles */
1298 if (k_area == 0)
1299 {
1300 if (flag & (MBR_CONTAIN | MBR_INTERSECT))
1301 {
1302 area+= 1;
1303 }
1304 else if (flag & (MBR_WITHIN | MBR_EQUAL))
1305 {
1306 if (!maria_rtree_key_cmp(keyinfo->seg, key->data, k, key_data_length,
1307 MBR_WITHIN))
1308 area+= 1;
1309 }
1310 else
1311 goto err;
1312 }
1313 else
1314 {
1315 if (flag & (MBR_CONTAIN | MBR_INTERSECT))
1316 {
1317 area+= maria_rtree_overlapping_area(keyinfo->seg, key->data, k,
1318 key_data_length) / k_area;
1319 }
1320 else if (flag & (MBR_WITHIN | MBR_EQUAL))
1321 {
1322 if (!maria_rtree_key_cmp(keyinfo->seg, key->data, k, key_data_length,
1323 MBR_WITHIN))
1324 area+= (maria_rtree_rect_volume(keyinfo->seg, key->data,
1325 key_data_length) / k_area);
1326 }
1327 else
1328 goto err;
1329 }
1330 }
1331 else
1332 {
1333 if (!maria_rtree_key_cmp(keyinfo->seg, key->data, k, key_data_length,
1334 flag))
1335 ++res;
1336 }
1337 }
1338 if (nod_flag)
1339 {
1340 if (i)
1341 res= (ha_rows) (area / i * info->state->records);
1342 else
1343 res= HA_POS_ERROR;
1344 }
1345
1346 my_afree(page_buf);
1347 return res;
1348
1349 err:
1350 my_afree(page_buf);
1351 return HA_POS_ERROR;
1352 }
1353
1354 #endif /*HAVE_RTREE_KEYS*/
1355