MySQL 8.3.0
Source Code Documentation
gis0sea.cc File Reference

InnoDB R-tree search interfaces. More...

#include <new>
#include "fsp0fsp.h"
#include "gis0rtree.h"
#include "my_dbug.h"
#include "page0cur.h"
#include "page0page.h"
#include "page0zip.h"
#include "btr0cur.h"
#include "btr0pcur.h"
#include "btr0sea.h"
#include "ibuf0ibuf.h"
#include "lock0lock.h"
#include "rem0cmp.h"
#include "srv0mon.h"
#include "sync0sync.h"
#include "trx0trx.h"
#include "univ.i"

Functions

static bool rtr_cur_restore_position (ulint latch_mode, btr_cur_t *cursor, ulint level, mtr_t *mtr)
 Restore the stored position of a persistent cursor bufferfixing the page. More...
 
static void rtr_adjust_parent_path (rtr_info_t *rtr_info, page_no_t page_no)
 Pop out used parent path entry, until we find the parent with matching page number. More...
 
static bool rtr_pcur_getnext_from_path (const dtuple_t *tuple, page_cur_mode_t mode, btr_cur_t *btr_cur, ulint target_level, ulint latch_mode, bool index_locked, mtr_t *mtr)
 Find the next matching record. More...
 
bool rtr_pcur_move_to_next (const dtuple_t *tuple, page_cur_mode_t mode, select_mode sel_mode, btr_pcur_t *cursor, ulint cur_level, mtr_t *mtr)
 Find the next matching record. More...
 
static bool rtr_compare_cursor_rec (dict_index_t *index, btr_cur_t *cursor, page_no_t page_no, mem_heap_t **heap)
 Check if the cursor holds record pointing to the specified child page. More...
 
void rtr_pcur_open_low (dict_index_t *index, ulint level, const dtuple_t *tuple, page_cur_mode_t mode, ulint latch_mode, btr_pcur_t *cursor, ut::Location location, mtr_t *mtr)
 Initializes and opens a persistent cursor to an index tree. More...
 
static ulintrtr_page_get_father_node_ptr (ulint *offsets, mem_heap_t *heap, btr_cur_t *sea_cur, btr_cur_t *cursor, mtr_t *mtr)
 Returns the upper level node pointer to a R-Tree page. More...
 
void rtr_page_get_father (dict_index_t *index, buf_block_t *block, mtr_t *mtr, btr_cur_t *sea_cur, btr_cur_t *cursor)
 
ulintrtr_page_get_father_block (ulint *offsets, mem_heap_t *heap, dict_index_t *index, buf_block_t *block, mtr_t *mtr, btr_cur_t *sea_cur, btr_cur_t *cursor)
 Returns the father block to a page. More...
 
void rtr_get_father_node (dict_index_t *index, ulint level, const dtuple_t *tuple, btr_cur_t *sea_cur, btr_cur_t *btr_cur, page_no_t page_no, mtr_t *mtr)
 Returns the upper level node pointer to a R-Tree page. More...
 
rtr_info_trtr_create_rtr_info (bool need_prdt, bool init_matches, btr_cur_t *cursor, dict_index_t *index)
 Create a RTree search info structure. More...
 
void rtr_info_update_btr (btr_cur_t *cursor, rtr_info_t *rtr_info)
 Update a btr_cur_t with rtr_info. More...
 
void rtr_init_rtr_info (rtr_info_t *rtr_info, bool need_prdt, btr_cur_t *cursor, dict_index_t *index, bool reinit)
 Initialize a R-Tree Search structure. More...
 
void rtr_clean_rtr_info (rtr_info_t *rtr_info, bool free_all)
 Clean up R-Tree search structure. More...
 
static void rtr_rebuild_path (rtr_info_t *rtr_info, page_no_t page_no)
 Rebuilt the "path" to exclude the removing page no. More...
 
void rtr_check_discard_page (dict_index_t *index, btr_cur_t *cursor, buf_block_t *block)
 Check whether a discarding page is in anyone's search path. More...
 
static void rtr_leaf_push_match_rec (const rec_t *rec, rtr_info_t *rtr_info, ulint *offsets, bool is_comp)
 Copy the leaf level R-tree record, and push it to matched_rec in rtr_info. More...
 
ulint rtr_store_parent_path (const buf_block_t *block, btr_cur_t *btr_cur, ulint latch_mode, ulint level, mtr_t *mtr)
 Store the parent path cursor. More...
 
static void rtr_non_leaf_insert_stack_push (dict_index_t *index, rtr_node_path_t *path, ulint level, page_no_t child_no, const buf_block_t *block, const rec_t *rec, double mbr_inc)
 push a nonleaf index node to the search path for insertion More...
 
static void rtr_copy_buf (matched_rec_t *matches, const buf_block_t *block)
 Copy a buf_block_t structure, except "block->lock", "block->mutex","block->debug_latch", "block->ahi.n_pointers and block->frame.". More...
 
static void rtr_init_match (matched_rec_t *matches, const buf_block_t *block, const page_t *page)
 Generate a shadow copy of the page block header to save the matched records. More...
 
void rtr_get_mbr_from_rec (const rec_t *rec, const ulint *offsets, rtr_mbr_t *mbr)
 Get the bounding box content from an index record. More...
 
void rtr_get_mbr_from_tuple (const dtuple_t *dtuple, rtr_mbr *mbr)
 Get the bounding box content from a MBR data record. More...
 
bool rtr_cur_search_with_match (const buf_block_t *block, dict_index_t *index, const dtuple_t *tuple, page_cur_mode_t mode, page_cur_t *cursor, rtr_info_t *rtr_info)
 Searches the right position in rtree for a page cursor. More...
 

Detailed Description

InnoDB R-tree search interfaces.

Created 2014/01/16 Jimmy Yang

Function Documentation

◆ rtr_adjust_parent_path()

static void rtr_adjust_parent_path ( rtr_info_t rtr_info,
page_no_t  page_no 
)
static

Pop out used parent path entry, until we find the parent with matching page number.

◆ rtr_check_discard_page()

void rtr_check_discard_page ( dict_index_t index,
btr_cur_t cursor,
buf_block_t block 
)

Check whether a discarding page is in anyone's search path.

Parameters
[in]indexIndex
[in,out]cursorCursor on the page to discard: not on the root page
[in]blockBlock of page to be discarded

◆ rtr_clean_rtr_info()

void rtr_clean_rtr_info ( rtr_info_t rtr_info,
bool  free_all 
)

Clean up R-Tree search structure.

Clean up Rtree cursor.

Parameters
rtr_infoin: RTree search info
free_allin: need to free rtr_info itself

◆ rtr_compare_cursor_rec()

static bool rtr_compare_cursor_rec ( dict_index_t index,
btr_cur_t cursor,
page_no_t  page_no,
mem_heap_t **  heap 
)
static

Check if the cursor holds record pointing to the specified child page.

Returns
true if it is (pointing to the child page) false otherwise
Parameters
indexin: index
cursorin: Cursor to check
page_noin: desired child page number
heapin: memory heap

◆ rtr_copy_buf()

static void rtr_copy_buf ( matched_rec_t matches,
const buf_block_t block 
)
static

Copy a buf_block_t structure, except "block->lock", "block->mutex","block->debug_latch", "block->ahi.n_pointers and block->frame.".

Parameters
[in,out]matchescopy to match->block
[in]blockblock to copy

◆ rtr_create_rtr_info()

rtr_info_t * rtr_create_rtr_info ( bool  need_prdt,
bool  init_matches,
btr_cur_t cursor,
dict_index_t index 
)

Create a RTree search info structure.

Parameters
[in]need_prdtWhether predicate lock is needed
[in]init_matchesWhether to initiate the "matches" structure for collecting matched leaf records
[in]cursorTree search cursor
[in]indexIndex struct

◆ rtr_cur_restore_position()

static bool rtr_cur_restore_position ( ulint  latch_mode,
btr_cur_t cursor,
ulint  level,
mtr_t mtr 
)
static

Restore the stored position of a persistent cursor bufferfixing the page.

in: mtr

Parameters
latch_modein: BTR_SEARCH_LEAF, ...
cursorin: detached persistent cursor
levelin: index level
mtrin: mtr

◆ rtr_cur_search_with_match()

bool rtr_cur_search_with_match ( const buf_block_t block,
dict_index_t index,
const dtuple_t tuple,
page_cur_mode_t  mode,
page_cur_t cursor,
rtr_info_t rtr_info 
)

Searches the right position in rtree for a page cursor.

Parameters
[in]blockBuffer block
[in]indexIndex descriptor
[in]tupleData tuple
[in]modePage_cur_l, page_cur_le, page_cur_g, or page_cur_ge
[in,out]cursorPage cursor
[in,out]rtr_infoSearch stack

◆ rtr_get_father_node()

void rtr_get_father_node ( dict_index_t index,
ulint  level,
const dtuple_t tuple,
btr_cur_t sea_cur,
btr_cur_t btr_cur,
page_no_t  page_no,
mtr_t mtr 
)

Returns the upper level node pointer to a R-Tree page.

in: mtr

It is assumed that mtr holds an x-latch on the tree.

Parameters
indexin: index
levelin: the tree level of search
tuplein: data tuple; NOTE: n_fields_cmp in tuple must be set so that it cannot get compared to the node ptr page number field!
sea_curin: search cursor
btr_curin/out: tree cursor; the cursor page is s- or x-latched, but see also above!
page_noCurrent page no
mtrin: mtr

◆ rtr_get_mbr_from_rec()

void rtr_get_mbr_from_rec ( const rec_t rec,
const ulint offsets,
rtr_mbr_t mbr 
)

Get the bounding box content from an index record.

Parameters
[in]recData tuple
[in]offsetsOffsets array
[out]mbrMbr

◆ rtr_get_mbr_from_tuple()

void rtr_get_mbr_from_tuple ( const dtuple_t dtuple,
rtr_mbr mbr 
)

Get the bounding box content from a MBR data record.

Parameters
[in]dtupleData tuple
[out]mbrMbr to fill
Parameters
dtuplein: data tuple
mbrout: mbr to fill

◆ rtr_info_update_btr()

void rtr_info_update_btr ( btr_cur_t cursor,
rtr_info_t rtr_info 
)

Update a btr_cur_t with rtr_info.

Parameters
[in,out]cursorTree cursor
[in]rtr_infoRtr_info to set to the cursor

◆ rtr_init_match()

static void rtr_init_match ( matched_rec_t matches,
const buf_block_t block,
const page_t page 
)
static

Generate a shadow copy of the page block header to save the matched records.

Parameters
matchesin/out: match to initialize
blockin: buffer block
pagein: buffer page

◆ rtr_init_rtr_info()

void rtr_init_rtr_info ( rtr_info_t rtr_info,
bool  need_prdt,
btr_cur_t cursor,
dict_index_t index,
bool  reinit 
)

Initialize a R-Tree Search structure.

Update a btr_cur_t with rtr_info.

Parameters
rtr_info************* in: rtr_info to set to the cursor
need_prdtin: Whether predicate lock is needed
cursorin: tree search cursor
indexin: index structure
reinitin: Whether this is a reinit

◆ rtr_leaf_push_match_rec()

static void rtr_leaf_push_match_rec ( const rec_t rec,
rtr_info_t rtr_info,
ulint offsets,
bool  is_comp 
)
static

Copy the leaf level R-tree record, and push it to matched_rec in rtr_info.

Parameters
recin: record to copy
rtr_infoin/out: search stack
offsetsin: offsets
is_compin: is compact format

◆ rtr_non_leaf_insert_stack_push()

static void rtr_non_leaf_insert_stack_push ( dict_index_t index,
rtr_node_path_t path,
ulint  level,
page_no_t  child_no,
const buf_block_t block,
const rec_t rec,
double  mbr_inc 
)
static

push a nonleaf index node to the search path for insertion

Parameters
indexin: index descriptor
pathin/out: search path
levelin: index page level
child_noin: child page no
blockin: block of the page
recin: positioned record
mbr_incin: MBR needs to be enlarged

◆ rtr_page_get_father()

void rtr_page_get_father ( dict_index_t index,
buf_block_t block,
mtr_t mtr,
btr_cur_t sea_cur,
btr_cur_t cursor 
)

◆ rtr_page_get_father_block()

ulint * rtr_page_get_father_block ( ulint offsets,
mem_heap_t heap,
dict_index_t index,
buf_block_t block,
mtr_t mtr,
btr_cur_t sea_cur,
btr_cur_t cursor 
)

Returns the father block to a page.

It is assumed that mtr holds an X or SX latch on the tree.

Returns
rec_get_offsets() of the node pointer record
Parameters
offsetsin: work area for the return value
heapin: memory heap to use
indexin: b-tree index
blockin: child page in the index
mtrin: mtr
sea_curin: search cursor, contains information about parent nodes in search
cursorout: cursor on node pointer record, its page x-latched

◆ rtr_page_get_father_node_ptr()

static ulint * rtr_page_get_father_node_ptr ( ulint offsets,
mem_heap_t heap,
btr_cur_t sea_cur,
btr_cur_t cursor,
mtr_t mtr 
)
static

Returns the upper level node pointer to a R-Tree page.

It is assumed that mtr holds an SX-latch or X-latch on the tree.

Returns
rec_get_offsets() of the node pointer record
Parameters
offsetsin: work area for the return value
heapin: memory heap to use
sea_curin: search cursor
cursorin: cursor pointing to user record, out: cursor on node pointer record, its page x-latched
mtrin: mtr

◆ rtr_pcur_getnext_from_path()

static bool rtr_pcur_getnext_from_path ( const dtuple_t tuple,
page_cur_mode_t  mode,
btr_cur_t btr_cur,
ulint  target_level,
ulint  latch_mode,
bool  index_locked,
mtr_t mtr 
)
static

Find the next matching record.

This function is used by search or record locating during index delete/update.

Returns
true if there is suitable record found, otherwise false
Parameters
tuplein: data tuple
modein: cursor search mode
btr_curin: persistent cursor; NOTE that the function may release the page latch
target_levelin: target level
latch_modein: latch_mode
index_lockedin: index tree locked
mtrin: mtr

◆ rtr_pcur_move_to_next()

bool rtr_pcur_move_to_next ( const dtuple_t tuple,
page_cur_mode_t  mode,
select_mode  sel_mode,
btr_pcur_t cursor,
ulint  cur_level,
mtr_t mtr 
)

Find the next matching record.

This function will first exhaust the copied record listed in the rtr_info->matches vector before moving to next page

Parameters
[in]tupleData tuple; NOTE: n_fields_cmp in tuple must be set so that it cannot get compared to the node ptr page number field!
[in]modeCursor search mode
[in]sel_modeSelect mode: SELECT_ORDINARY, SELECT_SKIP_LOKCED, or SELECT_NO_WAIT
[in]cursorPersistent cursor; NOTE that the function may release the page latch
[in]cur_levelCurrent level
[in]mtrMini-transaction
Returns
true if there is next qualified record found, otherwise(if exhausted) false

◆ rtr_pcur_open_low()

void rtr_pcur_open_low ( dict_index_t index,
ulint  level,
const dtuple_t tuple,
page_cur_mode_t  mode,
ulint  latch_mode,
btr_pcur_t cursor,
ut::Location  location,
mtr_t mtr 
)

Initializes and opens a persistent cursor to an index tree.

It should be closed with btr_pcur::close. Mainly called by row_search_index_entry()

Parameters
[in]indexindex
[in]levellevel in the btree
[in]tupletuple on which search done
[in]modePAGE_CUR_L, ...; NOTE that if the search is made using a unique prefix of a record, mode should be PAGE_CUR_LE, not PAGE_CUR_GE, as the latter may end up on the previous page from the record!
[in]latch_modeBTR_SEARCH_LEAF, ...
[in]cursormemore buffer for persistent cursor
[in]locationlocation where called
[in]mtrmtr

◆ rtr_rebuild_path()

static void rtr_rebuild_path ( rtr_info_t rtr_info,
page_no_t  page_no 
)
static

Rebuilt the "path" to exclude the removing page no.

Parameters
rtr_infoin: RTree search info
page_noin: need to free rtr_info itself

◆ rtr_store_parent_path()

ulint rtr_store_parent_path ( const buf_block_t block,
btr_cur_t btr_cur,
ulint  latch_mode,
ulint  level,
mtr_t mtr 
)

Store the parent path cursor.

Returns
number of cursor stored
Parameters
blockin: block of the page
btr_curin/out: persistent cursor
latch_modein: latch_mode
levelin: index level
mtrin: mtr