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