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 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)
	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)

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. 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_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. 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]	index	Index
[in,out]	cursor	Cursor on the page to discard: not on the root page
[in]	block	Block 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_info	in: RTree search info
free_all	in: 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

index	in: index
cursor	in: Cursor to check
page_no	in: desired child page number
heap	in: 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]	matches	copy to match->block
[in]	block	block 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_prdt	Whether predicate lock is needed
[in]	init_matches	Whether to initiate the "matches" structure for collecting matched leaf records
[in]	cursor	Tree search cursor
[in]	index	Index 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_mode	in: BTR_SEARCH_LEAF, ...
cursor	in: detached persistent cursor
level	in: index level
mtr	in: 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]	block	Buffer block
[in]	index	Index descriptor
[in]	tuple	Data tuple
[in]	mode	Page_cur_l, page_cur_le, page_cur_g, or page_cur_ge
[in,out]	cursor	Page cursor
[in,out]	rtr_info	Search 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

index	in: index
level	in: the tree level of search
tuple	in: 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_cur	in: search cursor
btr_cur	in/out: tree cursor; the cursor page is s- or x-latched, but see also above!
page_no	Current page no
mtr	in: 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]	rec	Data tuple
[in]	offsets	Offsets array
[out]	mbr	Mbr

◆ 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]	dtuple	Data tuple
[out]	mbr	Mbr to fill

Parameters

dtuple	in: data tuple
mbr	out: 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]	cursor	Tree cursor
[in]	rtr_info	Rtr_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

matches	in/out: match to initialize
block	in: buffer block
page	in: 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_prdt	in: Whether predicate lock is needed
cursor	in: tree search cursor
index	in: index structure
reinit	in: 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

rec	in: record to copy
rtr_info	in/out: search stack
offsets	in: offsets
is_comp	in: 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

index	in: index descriptor
path	in/out: search path
level	in: index page level
child_no	in: child page no
block	in: block of the page
rec	in: positioned record
mbr_inc	in: 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

offsets	in: work area for the return value
heap	in: memory heap to use
index	in: b-tree index
block	in: child page in the index
mtr	in: mtr
sea_cur	in: search cursor, contains information about parent nodes in search
cursor	out: 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

offsets	in: work area for the return value
heap	in: memory heap to use
sea_cur	in: search cursor
cursor	in: cursor pointing to user record, out: cursor on node pointer record, its page x-latched
mtr	in: 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

tuple	in: data tuple
mode	in: cursor search mode
btr_cur	in: persistent cursor; NOTE that the function may release the page latch
target_level	in: target level
latch_mode	in: latch_mode
index_locked	in: index tree locked
mtr	in: 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]	tuple	Data tuple; NOTE: n_fields_cmp in tuple must be set so that it cannot get compared to the node ptr page number field!
[in]	mode	Cursor search mode
[in]	sel_mode	Select mode: SELECT_ORDINARY, SELECT_SKIP_LOKCED, or SELECT_NO_WAIT
[in]	cursor	Persistent cursor; NOTE that the function may release the page latch
[in]	cur_level	Current level
[in]	mtr	Mini-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]	index	index
[in]	level	level in the btree
[in]	tuple	tuple on which search done
[in]	mode	PAGE_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_mode	BTR_SEARCH_LEAF, ...
[in]	cursor	memore buffer for persistent cursor
[in]	location	location where called
[in]	mtr	mtr

◆ 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_info	in: RTree search info
page_no	in: 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

block	in: block of the page
btr_cur	in/out: persistent cursor
latch_mode	in: latch_mode
level	in: index level
mtr	in: mtr

Functions

Detailed Description

Function Documentation

◆ rtr_adjust_parent_path()

◆ rtr_check_discard_page()

◆ rtr_clean_rtr_info()

◆ rtr_compare_cursor_rec()

◆ rtr_copy_buf()

◆ rtr_create_rtr_info()

◆ rtr_cur_restore_position()

◆ rtr_cur_search_with_match()

◆ rtr_get_father_node()

◆ rtr_get_mbr_from_rec()

◆ rtr_get_mbr_from_tuple()

◆ rtr_info_update_btr()

◆ rtr_init_match()

◆ rtr_init_rtr_info()

◆ rtr_leaf_push_match_rec()

◆ rtr_non_leaf_insert_stack_push()

◆ rtr_page_get_father()

◆ rtr_page_get_father_block()

◆ rtr_page_get_father_node_ptr()

◆ rtr_pcur_getnext_from_path()

◆ rtr_pcur_move_to_next()

◆ rtr_pcur_open_low()

◆ rtr_rebuild_path()

◆ rtr_store_parent_path()