1/*****************************************************************************
2
3Copyright (c) 2014, 2016, Oracle and/or its affiliates. All Rights Reserved.
4Copyright (c) 2017, 2018, MariaDB Corporation.
5
6This program is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free Software
8Foundation; version 2 of the License.
9
10This program is distributed in the hope that it will be useful, but WITHOUT
11ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13
14You should have received a copy of the GNU General Public License along with
15this program; if not, write to the Free Software Foundation, Inc.,
1651 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
17
18*****************************************************************************/
19
20/******************************************************************//**
21@file include gis0rtree.h
22R-tree header file
23
24Created 2013/03/27 Jimmy Yang and Allen Lai
25***********************************************************************/
26
27#ifndef gis0rtree_h
28#define gis0rtree_h
29
30#include "univ.i"
31#include "my_base.h"
32
33#include "data0type.h"
34#include "data0types.h"
35#include "dict0types.h"
36#include "hash0hash.h"
37#include "mem0mem.h"
38#include "page0page.h"
39#include "rem0types.h"
40#include "row0types.h"
41#include "trx0types.h"
42#include "ut0vec.h"
43#include "ut0wqueue.h"
44#include "que0types.h"
45#include "gis0geo.h"
46#include "gis0type.h"
47#include "btr0types.h"
48#include "btr0cur.h"
49
50/* Whether MBR 'a' contains 'b' */
51#define MBR_CONTAIN_CMP(a, b) \
52 ((((b)->xmin >= (a)->xmin) && ((b)->xmax <= (a)->xmax) \
53 && ((b)->ymin >= (a)->ymin) && ((b)->ymax <= (a)->ymax)))
54
55/* Whether MBR 'a' equals to 'b' */
56#define MBR_EQUAL_CMP(a, b) \
57 ((((b)->xmin == (a)->xmin) && ((b)->xmax == (a)->xmax)) \
58 && (((b)->ymin == (a)->ymin) && ((b)->ymax == (a)->ymax)))
59
60/* Whether MBR 'a' intersects 'b' */
61#define MBR_INTERSECT_CMP(a, b) \
62 ((((b)->xmin <= (a)->xmax) || ((b)->xmax >= (a)->xmin)) \
63 && (((b)->ymin <= (a)->ymax) || ((b)->ymax >= (a)->ymin)))
64
65/* Whether MBR 'a' and 'b' disjoint */
66#define MBR_DISJOINT_CMP(a, b) (!MBR_INTERSECT_CMP(a, b))
67
68/* Whether MBR 'a' within 'b' */
69#define MBR_WITHIN_CMP(a, b) \
70 ((((b)->xmin <= (a)->xmin) && ((b)->xmax >= (a)->xmax)) \
71 && (((b)->ymin <= (a)->ymin) && ((b)->ymax >= (a)->ymax)))
72
73/* Define it for rtree search mode checking. */
74#define RTREE_SEARCH_MODE(mode) \
75 (((mode) >= PAGE_CUR_CONTAIN) && ((mode <= PAGE_CUR_RTREE_GET_FATHER)))
76
77/* Geometry data header */
78#define GEO_DATA_HEADER_SIZE 4
79/**********************************************************************//**
80Builds a Rtree node pointer out of a physical record and a page number.
81@return own: node pointer */
82dtuple_t*
83rtr_index_build_node_ptr(
84/*=====================*/
85 const dict_index_t* index, /*!< in: index */
86 const rtr_mbr_t* mbr, /*!< in: mbr of lower page */
87 const rec_t* rec, /*!< in: record for which to build node
88 pointer */
89 ulint page_no,/*!< in: page number to put in node
90 pointer */
91 mem_heap_t* heap); /*!< in: memory heap where pointer
92 created */
93
94/*************************************************************//**
95Splits an R-tree index page to halves and inserts the tuple. It is assumed
96that mtr holds an x-latch to the index tree. NOTE: the tree x-latch is
97released within this function! NOTE that the operation of this
98function must always succeed, we cannot reverse it: therefore enough
99free disk space (2 pages) must be guaranteed to be available before
100this function is called.
101@return inserted record */
102rec_t*
103rtr_page_split_and_insert(
104/*======================*/
105 ulint flags, /*!< in: undo logging and locking flags */
106 btr_cur_t* cursor, /*!< in/out: cursor at which to insert; when the
107 function returns, the cursor is positioned
108 on the predecessor of the inserted record */
109 ulint** offsets,/*!< out: offsets on inserted record */
110 mem_heap_t** heap, /*!< in/out: pointer to memory heap, or NULL */
111 const dtuple_t* tuple, /*!< in: tuple to insert */
112 ulint n_ext, /*!< in: number of externally stored columns */
113 mtr_t* mtr); /*!< in: mtr */
114
115/**************************************************************//**
116Sets the child node mbr in a node pointer. */
117UNIV_INLINE
118void
119rtr_page_cal_mbr(
120/*=============*/
121 const dict_index_t* index, /*!< in: index */
122 const buf_block_t* block, /*!< in: buffer block */
123 rtr_mbr_t* mbr, /*!< out: MBR encapsulates the page */
124 mem_heap_t* heap); /*!< in: heap for the memory
125 allocation */
126/*************************************************************//**
127Find the next matching record. This function will first exhaust
128the copied record listed in the rtr_info->matches vector before
129moving to next page
130@return true if there is next qualified record found, otherwise(if
131exhausted) false */
132bool
133rtr_pcur_move_to_next(
134/*==================*/
135 const dtuple_t* tuple, /*!< in: data tuple; NOTE: n_fields_cmp in
136 tuple must be set so that it cannot get
137 compared to the node ptr page number field! */
138 page_cur_mode_t mode, /*!< in: cursor search mode */
139 btr_pcur_t* cursor, /*!< in: persistent cursor; NOTE that the
140 function may release the page latch */
141 ulint cur_level,
142 /*!< in: current level */
143 mtr_t* mtr); /*!< in: mtr */
144
145/****************************************************************//**
146Searches the right position in rtree for a page cursor. */
147bool
148rtr_cur_search_with_match(
149/*======================*/
150 const buf_block_t* block, /*!< in: buffer block */
151 dict_index_t* index, /*!< in: index descriptor */
152 const dtuple_t* tuple, /*!< in: data tuple */
153 page_cur_mode_t mode, /*!< in: PAGE_CUR_L,
154 PAGE_CUR_LE, PAGE_CUR_G, or
155 PAGE_CUR_GE */
156 page_cur_t* cursor, /*!< in/out: page cursor */
157 rtr_info_t* rtr_info);/*!< in/out: search stack */
158
159/****************************************************************//**
160Calculate the area increased for a new record
161@return area increased */
162double
163rtr_rec_cal_increase(
164/*=================*/
165 const dtuple_t* dtuple, /*!< in: data tuple to insert, which
166 cause area increase */
167 const rec_t* rec, /*!< in: physical record which differs from
168 dtuple in some of the common fields, or which
169 has an equal number or more fields than
170 dtuple */
171 const ulint* offsets,/*!< in: array returned by rec_get_offsets() */
172 double* area); /*!< out: increased area */
173
174/****************************************************************//**
175Following the right link to find the proper block for insert.
176@return the proper block.*/
177dberr_t
178rtr_ins_enlarge_mbr(
179/*=================*/
180 btr_cur_t* cursor, /*!< in: btr cursor */
181 mtr_t* mtr); /*!< in: mtr */
182
183/********************************************************************//**
184*/
185void
186rtr_get_father_node(
187/*================*/
188 dict_index_t* index, /*!< in: index */
189 ulint level, /*!< in: the tree level of search */
190 const dtuple_t* tuple, /*!< in: data tuple; NOTE: n_fields_cmp in
191 tuple must be set so that it cannot get
192 compared to the node ptr page number field! */
193 btr_cur_t* sea_cur,/*!< in: search cursor */
194 btr_cur_t* cursor, /*!< in/out: tree cursor; the cursor page is
195 s- or x-latched */
196 ulint page_no,/*!< in: current page no */
197 mtr_t* mtr); /*!< in: mtr */
198
199/**************************************************************//**
200push a nonleaf index node to the search path */
201UNIV_INLINE
202void
203rtr_non_leaf_stack_push(
204/*====================*/
205 rtr_node_path_t* path, /*!< in/out: search path */
206 ulint pageno, /*!< in: pageno to insert */
207 node_seq_t seq_no, /*!< in: Node sequence num */
208 ulint level, /*!< in: index level */
209 ulint child_no, /*!< in: child page no */
210 btr_pcur_t* cursor, /*!< in: position cursor */
211 double mbr_inc); /*!< in: MBR needs to be
212 enlarged */
213
214/**************************************************************//**
215push a nonleaf index node to the search path for insertion */
216void
217rtr_non_leaf_insert_stack_push(
218/*===========================*/
219 dict_index_t* index, /*!< in: index descriptor */
220 rtr_node_path_t* path, /*!< in/out: search path */
221 ulint level, /*!< in: index level */
222 const buf_block_t* block, /*!< in: block of the page */
223 const rec_t* rec, /*!< in: positioned record */
224 double mbr_inc); /*!< in: MBR needs to be
225 enlarged */
226
227/*****************************************************************//**
228Allocates a new Split Sequence Number.
229@return new SSN id */
230UNIV_INLINE
231node_seq_t
232rtr_get_new_ssn_id(
233/*===============*/
234 dict_index_t* index); /*!< in: the index struct */
235
236/*****************************************************************//**
237Get the current Split Sequence Number.
238@return current SSN id */
239UNIV_INLINE
240node_seq_t
241rtr_get_current_ssn_id(
242/*===================*/
243 dict_index_t* index); /*!< in/out: the index struct */
244
245/********************************************************************//**
246Create a RTree search info structure */
247rtr_info_t*
248rtr_create_rtr_info(
249/******************/
250 bool need_prdt, /*!< in: Whether predicate lock is
251 needed */
252 bool init_matches, /*!< in: Whether to initiate the
253 "matches" structure for collecting
254 matched leaf records */
255 btr_cur_t* cursor, /*!< in: tree search cursor */
256 dict_index_t* index); /*!< in: index struct */
257
258/********************************************************************//**
259Update a btr_cur_t with rtr_info */
260void
261rtr_info_update_btr(
262/******************/
263 btr_cur_t* cursor, /*!< in/out: tree cursor */
264 rtr_info_t* rtr_info); /*!< in: rtr_info to set to the
265 cursor */
266
267/********************************************************************//**
268Update a btr_cur_t with rtr_info */
269void
270rtr_init_rtr_info(
271/****************/
272 rtr_info_t* rtr_info, /*!< in: rtr_info to set to the
273 cursor */
274 bool need_prdt, /*!< in: Whether predicate lock is
275 needed */
276 btr_cur_t* cursor, /*!< in: tree search cursor */
277 dict_index_t* index, /*!< in: index structure */
278 bool reinit); /*!< in: Whether this is a reinit */
279
280/**************************************************************//**
281Clean up Rtree cursor */
282void
283rtr_clean_rtr_info(
284/*===============*/
285 rtr_info_t* rtr_info, /*!< in: RTree search info */
286 bool free_all); /*!< in: need to free rtr_info itself */
287
288/****************************************************************//**
289Get the bounding box content from an index record*/
290void
291rtr_get_mbr_from_rec(
292/*=================*/
293 const rec_t* rec, /*!< in: data tuple */
294 const ulint* offsets,/*!< in: offsets array */
295 rtr_mbr_t* mbr); /*!< out MBR */
296
297/****************************************************************//**
298Get the bounding box content from a MBR data record */
299void
300rtr_get_mbr_from_tuple(
301/*===================*/
302 const dtuple_t* dtuple, /*!< in: data tuple */
303 rtr_mbr* mbr); /*!< out: mbr to fill */
304
305/* Get the rtree page father.
306@param[in] offsets work area for the return value
307@param[in] index rtree index
308@param[in] block child page in the index
309@param[in] mtr mtr
310@param[in] sea_cur search cursor, contains information
311 about parent nodes in search
312@param[in] cursor cursor on node pointer record,
313 its page x-latched */
314void
315rtr_page_get_father(
316 dict_index_t* index,
317 buf_block_t* block,
318 mtr_t* mtr,
319 btr_cur_t* sea_cur,
320 btr_cur_t* cursor);
321
322/************************************************************//**
323Returns the father block to a page. It is assumed that mtr holds
324an X or SX latch on the tree.
325@return rec_get_offsets() of the node pointer record */
326ulint*
327rtr_page_get_father_block(
328/*======================*/
329 ulint* offsets,/*!< in: work area for the return value */
330 mem_heap_t* heap, /*!< in: memory heap to use */
331 dict_index_t* index, /*!< in: b-tree index */
332 buf_block_t* block, /*!< in: child page in the index */
333 mtr_t* mtr, /*!< in: mtr */
334 btr_cur_t* sea_cur,/*!< in: search cursor, contains information
335 about parent nodes in search */
336 btr_cur_t* cursor);/*!< out: cursor on node pointer record,
337 its page x-latched */
338/**************************************************************//**
339Store the parent path cursor
340@return number of cursor stored */
341ulint
342rtr_store_parent_path(
343/*==================*/
344 const buf_block_t* block, /*!< in: block of the page */
345 btr_cur_t* btr_cur,/*!< in/out: persistent cursor */
346 ulint latch_mode,
347 /*!< in: latch_mode */
348 ulint level, /*!< in: index level */
349 mtr_t* mtr); /*!< in: mtr */
350
351/**************************************************************//**
352Initializes and opens a persistent cursor to an index tree. It should be
353closed with btr_pcur_close. */
354void
355rtr_pcur_open_low(
356/*==============*/
357 dict_index_t* index, /*!< in: index */
358 ulint level, /*!< in: level in the btree */
359 const dtuple_t* tuple, /*!< in: tuple on which search done */
360 page_cur_mode_t mode, /*!< in: PAGE_CUR_L, ...;
361 NOTE that if the search is made using a unique
362 prefix of a record, mode should be
363 PAGE_CUR_LE, not PAGE_CUR_GE, as the latter
364 may end up on the previous page from the
365 record! */
366 ulint latch_mode,/*!< in: BTR_SEARCH_LEAF, ... */
367 btr_pcur_t* cursor, /*!< in: memory buffer for persistent cursor */
368 const char* file, /*!< in: file name */
369 unsigned line, /*!< in: line where called */
370 mtr_t* mtr); /*!< in: mtr */
371
372#define rtr_pcur_open(i,t,md,l,c,m) \
373 rtr_pcur_open_low(i,0,t,md,l,c,__FILE__,__LINE__,m)
374
375struct btr_cur_t;
376
377/*********************************************************//**
378Returns the R-Tree node stored in the parent search path
379@return pointer to R-Tree cursor component */
380UNIV_INLINE
381node_visit_t*
382rtr_get_parent_node(
383/*================*/
384 btr_cur_t* btr_cur, /*!< in: persistent cursor */
385 ulint level, /*!< in: index level of buffer page */
386 ulint is_insert); /*!< in: whether it is insert */
387
388/*********************************************************//**
389Returns the R-Tree cursor stored in the parent search path
390@return pointer to R-Tree cursor component */
391UNIV_INLINE
392btr_pcur_t*
393rtr_get_parent_cursor(
394/*==================*/
395 btr_cur_t* btr_cur, /*!< in: persistent cursor */
396 ulint level, /*!< in: index level of buffer page */
397 ulint is_insert); /*!< in: whether insert operation */
398
399/*************************************************************//**
400Copy recs from a page to new_block of rtree. */
401void
402rtr_page_copy_rec_list_end_no_locks(
403/*================================*/
404 buf_block_t* new_block, /*!< in: index page to copy to */
405 buf_block_t* block, /*!< in: index page of rec */
406 rec_t* rec, /*!< in: record on page */
407 dict_index_t* index, /*!< in: record descriptor */
408 mem_heap_t* heap, /*!< in/out: heap memory */
409 rtr_rec_move_t* rec_move, /*!< in: recording records moved */
410 ulint max_move, /*!< in: num of rec to move */
411 ulint* num_moved, /*!< out: num of rec to move */
412 mtr_t* mtr); /*!< in: mtr */
413
414/*************************************************************//**
415Copy recs till a specified rec from a page to new_block of rtree. */
416void
417rtr_page_copy_rec_list_start_no_locks(
418/*==================================*/
419 buf_block_t* new_block, /*!< in: index page to copy to */
420 buf_block_t* block, /*!< in: index page of rec */
421 rec_t* rec, /*!< in: record on page */
422 dict_index_t* index, /*!< in: record descriptor */
423 mem_heap_t* heap, /*!< in/out: heap memory */
424 rtr_rec_move_t* rec_move, /*!< in: recording records moved */
425 ulint max_move, /*!< in: num of rec to move */
426 ulint* num_moved, /*!< out: num of rec to move */
427 mtr_t* mtr); /*!< in: mtr */
428
429/****************************************************************//**
430Merge 2 mbrs and update the the mbr that cursor is on. */
431dberr_t
432rtr_merge_and_update_mbr(
433/*=====================*/
434 btr_cur_t* cursor, /*!< in/out: cursor */
435 btr_cur_t* cursor2, /*!< in: the other cursor */
436 ulint* offsets, /*!< in: rec offsets */
437 ulint* offsets2, /*!< in: rec offsets */
438 page_t* child_page, /*!< in: the child page. */
439 mtr_t* mtr); /*!< in: mtr */
440
441/*************************************************************//**
442Deletes on the upper level the node pointer to a page. */
443void
444rtr_node_ptr_delete(
445/*================*/
446 btr_cur_t* cursor, /*!< in: search cursor, contains information
447 about parent nodes in search */
448 mtr_t* mtr); /*!< in: mtr */
449
450/****************************************************************//**
451Check two MBRs are identical or need to be merged */
452bool
453rtr_merge_mbr_changed(
454/*==================*/
455 btr_cur_t* cursor, /*!< in: cursor */
456 btr_cur_t* cursor2, /*!< in: the other cursor */
457 ulint* offsets, /*!< in: rec offsets */
458 ulint* offsets2, /*!< in: rec offsets */
459 rtr_mbr_t* new_mbr); /*!< out: MBR to update */
460
461
462/**************************************************************//**
463Update the mbr field of a spatial index row.
464@return true if successful */
465bool
466rtr_update_mbr_field(
467/*=================*/
468 btr_cur_t* cursor, /*!< in: cursor pointed to rec.*/
469 ulint* offsets, /*!< in: offsets on rec. */
470 btr_cur_t* cursor2, /*!< in/out: cursor pointed to rec
471 that should be deleted.
472 this cursor is for btr_compress to
473 delete the merged page's father rec.*/
474 page_t* child_page, /*!< in: child page. */
475 rtr_mbr_t* new_mbr, /*!< in: the new mbr. */
476 rec_t* new_rec, /*!< in: rec to use */
477 mtr_t* mtr); /*!< in: mtr */
478
479/**************************************************************//**
480Check whether a Rtree page is child of a parent page
481@return true if there is child/parent relationship */
482bool
483rtr_check_same_block(
484/*=================*/
485 dict_index_t* index, /*!< in: index tree */
486 btr_cur_t* cur, /*!< in/out: position at the parent entry
487 pointing to the child if successful */
488 buf_block_t* parentb,/*!< in: parent page to check */
489 buf_block_t* childb, /*!< in: child Page */
490 mem_heap_t* heap); /*!< in: memory heap */
491
492/*********************************************************************//**
493Sets pointer to the data and length in a field. */
494UNIV_INLINE
495void
496rtr_write_mbr(
497/*==========*/
498 byte* data, /*!< out: data */
499 const rtr_mbr_t* mbr); /*!< in: data */
500
501/*********************************************************************//**
502Sets pointer to the data and length in a field. */
503UNIV_INLINE
504void
505rtr_read_mbr(
506/*==========*/
507 const byte* data, /*!< in: data */
508 rtr_mbr_t* mbr); /*!< out: data */
509
510/**************************************************************//**
511Check whether a discarding page is in anyone's search path */
512void
513rtr_check_discard_page(
514/*===================*/
515 dict_index_t* index, /*!< in: index */
516 btr_cur_t* cursor, /*!< in: cursor on the page to discard: not on
517 the root page */
518 buf_block_t* block); /*!< in: block of page to be discarded */
519
520/********************************************************************//**
521Reinitialize a RTree search info */
522UNIV_INLINE
523void
524rtr_info_reinit_in_cursor(
525/************************/
526 btr_cur_t* cursor, /*!< in/out: tree cursor */
527 dict_index_t* index, /*!< in: index struct */
528 bool need_prdt); /*!< in: Whether predicate lock is
529 needed */
530
531/** Estimates the number of rows in a given area.
532@param[in] index index
533@param[in] tuple range tuple containing mbr, may also be empty tuple
534@param[in] mode search mode
535@return estimated number of rows */
536ha_rows
537rtr_estimate_n_rows_in_range(
538 dict_index_t* index,
539 const dtuple_t* tuple,
540 page_cur_mode_t mode);
541
542#include "gis0rtree.ic"
543#endif /*!< gis0rtree.h */
544