InnoDB R-tree interfaces. More...

#include <sys/types.h>
#include <cmath>
#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 "gis0geo.h"
#include "ibuf0ibuf.h"
#include "lock0lock.h"
#include "rem0cmp.h"
#include "srv0mon.h"
#include "trx0trx.h"

Functions
static rtr_split_node_t *	rtr_page_split_initialize_nodes (mem_heap_t heap, btr_cur_t cursor, ulint *offsets, const dtuple_t tuple, double **buf_pos)
	Initial split nodes info for R-tree split. More...

dtuple_t *	rtr_index_build_node_ptr (const dict_index_t index, const rtr_mbr_t mbr, const rec_t rec, page_no_t page_no, mem_heap_t heap)
	Builds a Rtree node pointer out of a physical record and a page number. More...

static void	rtr_update_mbr_field_in_place (dict_index_t index, rec_t rec, ulint offsets, rtr_mbr_t mbr, mtr_t *mtr)
	In-place update the mbr field of a spatial index row. More...

bool	rtr_update_mbr_field (btr_cur_t cursor, ulint offsets, btr_cur_t cursor2, page_t child_page, rtr_mbr_t mbr, rec_t new_rec, mtr_t *mtr)
	Update the mbr field of a spatial index row. More...

static void	rtr_adjust_upper_level (btr_cur_t sea_cur, uint32_t flags, buf_block_t block, buf_block_t new_block, rtr_mbr_t mbr, rtr_mbr_t new_mbr, mtr_t mtr)
	Update parent page's MBR and Predicate lock information during a split. More...

static bool	rtr_split_page_move_rec_list (rtr_split_node_t node_array, int first_rec_group, buf_block_t new_block, buf_block_t block, rec_t first_rec, dict_index_t index, mem_heap_t heap, mtr_t *mtr)
	Moves record list to another page for rtree splitting. More...

rec_t *	rtr_page_split_and_insert (uint32_t flags, btr_cur_t cursor, ulint offsets, mem_heap_t heap, const dtuple_t tuple, mtr_t *mtr)
	Splits an R-tree index page to halves and inserts the tuple. More...

dberr_t	rtr_ins_enlarge_mbr (btr_cur_t btr_cur, mtr_t mtr)
	Following the right link to find the proper block for insert. More...

void	rtr_page_copy_rec_list_end_no_locks (buf_block_t new_block, buf_block_t block, rec_t rec, dict_index_t index, mem_heap_t heap, rtr_rec_move_t rec_move, ulint max_move, ulint num_moved, mtr_t mtr)
	Copy recs from a page to new_block of rtree. More...

void	rtr_page_copy_rec_list_start_no_locks (buf_block_t new_block, buf_block_t block, rec_t rec, dict_index_t index, mem_heap_t heap, rtr_rec_move_t rec_move, ulint max_move, ulint num_moved, mtr_t mtr)
	Copy recs till a specified rec from a page to new_block of rtree. More...

bool	rtr_merge_mbr_changed (btr_cur_t cursor, btr_cur_t cursor2, ulint offsets, ulint offsets2, rtr_mbr_t *new_mbr)
	Check two MBRs are identical or need to be merged. More...

dberr_t	rtr_merge_and_update_mbr (btr_cur_t cursor, btr_cur_t cursor2, ulint offsets, ulint offsets2, page_t child_page, mtr_t mtr)
	Merge 2 mbrs and update the the mbr that cursor is on. More...

void	rtr_node_ptr_delete (btr_cur_t sea_cur, mtr_t mtr)
	Deletes on the upper level the node pointer to a page. More...

bool	rtr_check_same_block (dict_index_t index, btr_cur_t cursor, buf_block_t parentb, buf_block_t childb, mem_heap_t *heap)
	Check whether a Rtree page is child of a parent page. More...

double	rtr_rec_cal_increase (const dtuple_t dtuple, const rec_t rec, const ulint offsets, double area, const dd::Spatial_reference_system *srs)
	Calculate the area increased for a new record. More...

int64_t	rtr_estimate_n_rows_in_range (dict_index_t index, const dtuple_t tuple, page_cur_mode_t mode)
	Estimates the number of rows in a given area. More...

Detailed Description

InnoDB R-tree interfaces.

Created 2013/03/27 Allen Lai and Jimmy Yang

Function Documentation

◆ rtr_adjust_upper_level()

static void rtr_adjust_upper_level	(	btr_cur_t *	sea_cur,
		uint32_t	flags,
		buf_block_t *	block,
		buf_block_t *	new_block,
		rtr_mbr_t *	mbr,
		rtr_mbr_t *	new_mbr,
		mtr_t *	mtr
	)

static

Update parent page's MBR and Predicate lock information during a split.

Parameters

sea_cur	in: search cursor
flags	in: undo logging and locking flags
block	in/out: page to be split
new_block	in/out: the new half page
mbr	in: MBR on the old page
new_mbr	in: MBR on the new page
mtr	in: mtr

◆ rtr_check_same_block()

bool rtr_check_same_block	(	dict_index_t *	index,
		btr_cur_t *	cursor,
		buf_block_t *	parentb,
		buf_block_t *	childb,
		mem_heap_t *	heap
	)

Check whether a Rtree page is child of a parent page.

Returns: true if there is child/parent relationship

Parameters

index	in: index tree
cursor	in/out: position at the parent entry pointing to the child if successful
parentb	in: parent page to check
childb	in: child Page
heap	in: memory heap

◆ rtr_estimate_n_rows_in_range()

int64_t rtr_estimate_n_rows_in_range	(	dict_index_t *	index,
		const dtuple_t *	tuple,
		page_cur_mode_t	mode
	)

Estimates the number of rows in a given area.

Parameters

[in]	index	index
[in]	tuple	range tuple containing mbr, may also be empty tuple
[in]	mode	search mode

Returns: estimated number of rows

◆ rtr_index_build_node_ptr()

dtuple_t * rtr_index_build_node_ptr	(	const dict_index_t *	index,
		const rtr_mbr_t *	mbr,
		const rec_t *	rec,
		page_no_t	page_no,
		mem_heap_t *	heap
	)

Builds a Rtree node pointer out of a physical record and a page number.

Returns: own: node pointer

Parameters

[in]	index	index
[in]	mbr	mbr of lower page
[in]	rec	record for which to build node pointer
[in]	page_no	page number to put in node pointer
[in]	heap	memory heap where pointer created

◆ rtr_ins_enlarge_mbr()

dberr_t rtr_ins_enlarge_mbr	(	btr_cur_t *	btr_cur,
		mtr_t *	mtr
	)

Following the right link to find the proper block for insert.

Returns: the proper block.

Parameters

[in]	btr_cur	btr cursor
[in]	mtr	mtr

◆ rtr_merge_and_update_mbr()

dberr_t rtr_merge_and_update_mbr	(	btr_cur_t *	cursor,
		btr_cur_t *	cursor2,
		ulint *	offsets,
		ulint *	offsets2,
		page_t *	child_page,
		mtr_t *	mtr
	)

Merge 2 mbrs and update the the mbr that cursor is on.

Parameters

[in,out]	cursor	Cursor
[in]	cursor2	The other cursor
[in]	offsets	Rec offsets
[in]	offsets2	Rec offsets
[in]	child_page	The child page.
[in]	mtr	Mini-transaction

◆ rtr_merge_mbr_changed()

bool rtr_merge_mbr_changed	(	btr_cur_t *	cursor,
		btr_cur_t *	cursor2,
		ulint *	offsets,
		ulint *	offsets2,
		rtr_mbr_t *	new_mbr
	)

Check two MBRs are identical or need to be merged.

Parameters

[in]	cursor	Cursor
[in]	cursor2	The other cursor
[in]	offsets	Rec offsets
[in]	offsets2	Rec offsets
[out]	new_mbr	Mbr to update

◆ rtr_node_ptr_delete()

void rtr_node_ptr_delete	(	btr_cur_t *	sea_cur,
		mtr_t *	mtr
	)

Deletes on the upper level the node pointer to a page.

Parameters

[in]	sea_cur	Search cursor, contains information about parent nodes in search
[in]	mtr	Mini-transaction

◆ rtr_page_copy_rec_list_end_no_locks()

void rtr_page_copy_rec_list_end_no_locks	(	buf_block_t *	new_block,
		buf_block_t *	block,
		rec_t *	rec,
		dict_index_t *	index,
		mem_heap_t *	heap,
		rtr_rec_move_t *	rec_move,
		ulint	max_move,
		ulint *	num_moved,
		mtr_t *	mtr
	)

Copy recs from a page to new_block of rtree.

Differs from page_copy_rec_list_end, because this function does not touch the lock table and max trx id on page or compress the page.

IMPORTANT: The caller will have to update IBUF_BITMAP_FREE if new_block is a compressed leaf page in a secondary index. This has to be done either within the same mini-transaction, or by invoking ibuf_reset_free_bits() before mtr_commit().

Parameters

[in]	new_block	Index page to copy to
[in]	block	Index page of rec
[in]	rec	Record on page
[in]	index	Record descriptor
[in,out]	heap	Heap memory
[in]	rec_move	Recording records moved
[in]	max_move	Num of rec to move
[out]	num_moved	Num of rec to move
[in]	mtr	Mini-transaction

◆ rtr_page_copy_rec_list_start_no_locks()

void rtr_page_copy_rec_list_start_no_locks	(	buf_block_t *	new_block,
		buf_block_t *	block,
		rec_t *	rec,
		dict_index_t *	index,
		mem_heap_t *	heap,
		rtr_rec_move_t *	rec_move,
		ulint	max_move,
		ulint *	num_moved,
		mtr_t *	mtr
	)

Copy recs till a specified rec from a page to new_block of rtree.

Parameters

[in]	new_block	Index page to copy to
[in]	block	Index page of rec
[in]	rec	Record on page
[in]	index	Record descriptor
[in,out]	heap	Heap memory
[in]	rec_move	Recording records moved
[in]	max_move	Num of rec to move
[out]	num_moved	Num of rec to move
[in]	mtr	Mini-transaction

◆ rtr_page_split_and_insert()

rec_t * rtr_page_split_and_insert	(	uint32_t	flags,
		btr_cur_t *	cursor,
		ulint **	offsets,
		mem_heap_t **	heap,
		const dtuple_t *	tuple,
		mtr_t *	mtr
	)

Splits an R-tree index page to halves and inserts the tuple.

It is assumed that mtr holds an x-latch to the index tree. NOTE: the tree x-latch is released within this function! NOTE that the operation of this function must always succeed, we cannot reverse it: therefore enough free disk space (2 pages) must be guaranteed to be available before this function is called.

Returns: inserted record

Parameters

flags	in: undo logging and locking flags
cursor	in/out: cursor at which to insert; when the function returns, the cursor is positioned on the predecessor of the inserted record
offsets	out: offsets on inserted record
heap	in/out: pointer to memory heap, or NULL
tuple	in: tuple to insert
mtr	in: mtr

◆ rtr_page_split_initialize_nodes()

static rtr_split_node_t * rtr_page_split_initialize_nodes	(	mem_heap_t *	heap,
		btr_cur_t *	cursor,
		ulint **	offsets,
		const dtuple_t *	tuple,
		double **	buf_pos
	)

static

Initial split nodes info for R-tree split.

Returns: initialized split nodes array

Parameters

heap	in: pointer to memory heap, or NULL
cursor	in: cursor at which to insert; when the function returns, the cursor is positioned on the predecessor of the inserted record
offsets	in: offsets on inserted record
tuple	in: tuple to insert
buf_pos	in/out: current buffer position

◆ rtr_rec_cal_increase()

double rtr_rec_cal_increase	(	const dtuple_t *	dtuple,
		const rec_t *	rec,
		const ulint *	offsets,
		double *	area,
		const dd::Spatial_reference_system *	srs
	)

Calculate the area increased for a new record.

Returns: area increased

Parameters

dtuple	in: data tuple to insert, which cause area increase
rec	in: physical record which differs from dtuple in some of the common fields, or which has an equal number or more fields than dtuple
offsets	in: array returned by rec_get_offsets()
area	out: increased area
srs	in: SRS of R-tree

◆ rtr_split_page_move_rec_list()

static bool rtr_split_page_move_rec_list	(	rtr_split_node_t *	node_array,
		int	first_rec_group,
		buf_block_t *	new_block,
		buf_block_t *	block,
		rec_t *	first_rec,
		dict_index_t *	index,
		mem_heap_t *	heap,
		mtr_t *	mtr
	)

static

Moves record list to another page for rtree splitting.

IMPORTANT: The caller will have to update IBUF_BITMAP_FREE if new_block is a compressed leaf page in a secondary index. This has to be done either within the same mini-transaction, or by invoking ibuf_reset_free_bits() before mtr_commit().

Returns: true on success; false on compression failure

Parameters

node_array	in: split node array.
first_rec_group	in: group number of the first rec.
new_block	in/out: index page where to move
block	in/out: page containing split_rec
first_rec	in: first record not to move
index	in: record descriptor
heap	in: pointer to memory heap, or NULL
mtr	in: mtr

◆ rtr_update_mbr_field()

bool rtr_update_mbr_field	(	btr_cur_t *	cursor,
		ulint *	offsets,
		btr_cur_t *	cursor2,
		page_t *	child_page,
		rtr_mbr_t *	mbr,
		rec_t *	new_rec,
		mtr_t *	mtr
	)

Update the mbr field of a spatial index row.

Returns: true if update is successful

Parameters

cursor	in/out: cursor pointed to rec.
offsets	in/out: offsets on rec.
cursor2	in/out: cursor pointed to rec that should be deleted. this cursor is for btr_compress to delete the merged page's father rec.
child_page	in: child page.
mbr	in: the new mbr.
new_rec	in: rec to use
mtr	in: mtr

◆ rtr_update_mbr_field_in_place()

static void rtr_update_mbr_field_in_place	(	dict_index_t *	index,
		rec_t *	rec,
		ulint *	offsets,
		rtr_mbr_t *	mbr,
		mtr_t *	mtr
	)

static

In-place update the mbr field of a spatial index row.

Parameters

index	in: spatial index.
rec	in/out: rec to be modified.
offsets	in/out: offsets on rec.
mbr	in: the new mbr.
mtr	in: mtr

Functions

Detailed Description

Function Documentation

◆ rtr_adjust_upper_level()

◆ rtr_check_same_block()

◆ rtr_estimate_n_rows_in_range()

◆ rtr_index_build_node_ptr()

◆ rtr_ins_enlarge_mbr()

◆ rtr_merge_and_update_mbr()

◆ rtr_merge_mbr_changed()

◆ rtr_node_ptr_delete()

◆ rtr_page_copy_rec_list_end_no_locks()

◆ rtr_page_copy_rec_list_start_no_locks()

◆ rtr_page_split_and_insert()

◆ rtr_page_split_initialize_nodes()

◆ rtr_rec_cal_increase()

◆ rtr_split_page_move_rec_list()

◆ rtr_update_mbr_field()

◆ rtr_update_mbr_field_in_place()