The index tree adaptive search. More...

#include "univ.i"
#include "btr0types.h"
#include "dict0dict.h"
#include "ha0ha.h"
#include "mtr0mtr.h"
#include "rem0rec.h"
#include "btr0sea.ic"

Classes
struct	btr_search_t
	The search info struct in an index. More...

class	btr_search_sys_t
	The hash index system. More...

class	btr_search_sys_t::search_part_t

Functions
void	btr_search_sys_create (ulint hash_size)
	Creates and initializes the adaptive search system at a database start. More...

void	btr_search_sys_resize (ulint hash_size)
	Resize hash index hash table. More...

void	btr_search_sys_free ()
	Frees the adaptive search system at a database shutdown. More...

bool	btr_search_disable ()
	Disable the adaptive hash search system and empty the index. More...

void	btr_search_enable ()
	Enable the adaptive hash search system. More...

btr_search_t *	btr_search_info_create (mem_heap_t *heap)
	Creates and initializes a search info struct. More...

void	btr_search_await_no_reference (dict_table_t table, dict_index_t index, bool force)
	Wait for the specified index to have all references from AHI dropped. More...

static void	btr_search_info_update (btr_cur_t *cursor)
	Updates the search info statistics following a search in B-tree that was performed not using or not finding row with the AHI index. More...

bool	btr_search_guess_on_hash (const dtuple_t tuple, ulint mode, ulint latch_mode, btr_cur_t cursor, ulint has_search_latch, mtr_t *mtr)
	Tries to guess the right search position based on the hash search info of the index. More...

void	btr_search_update_hash_on_move (buf_block_t new_block, buf_block_t block, dict_index_t *index)
	Moves or deletes hash entries for moved records. More...

void	btr_search_drop_page_hash_index (buf_block_t *block, bool force=false)
	Drop any adaptive hash index entries that point to an index page. More...

void	btr_search_set_block_not_cached (buf_block_t *block)
	Resets block's AHI index field to nullptr, removes the reference from index's reference counter. More...

void	btr_search_drop_page_hash_when_freed (const page_id_t &page_id, const page_size_t &page_size)
	Drop any adaptive hash index entries that may point to an index page that may be in the buffer pool, when a page is evicted from the buffer pool or freed in a file segment. More...

void	btr_drop_ahi_for_table (dict_table_t *table)
	Drop any adaptive hash index entries for a table. More...

void	btr_drop_ahi_for_index (const dict_index_t *index)
	Drop any adaptive hash index entries for a index. More...

void	btr_search_update_hash_node_on_insert (btr_cur_t *cursor)
	Updates the page hash index when a single record is inserted on a page. More...

void	btr_search_update_hash_on_insert (btr_cur_t *cursor)
	Updates the page hash index when a single record is inserted on a page. More...

void	btr_search_update_hash_on_delete (btr_cur_t *cursor)
	Updates the page hash index when a single record is deleted from a page. More...

bool	btr_search_validate ()
	Validates the search system. More...

static void	btr_search_x_lock (const dict_index_t *index, ut::Location location)
	X-Lock the search latch (corresponding to given index) More...

static bool	btr_search_x_lock_nowait (const dict_index_t *index, ut::Location location)
	X-Lock the search latch (corresponding to given index), does not block. More...

static void	btr_search_x_unlock (const dict_index_t *index)
	X-Unlock the search latch (corresponding to given index) More...

static void	btr_search_x_lock_all (ut::Location location)
	Lock all search latches in exclusive mode. More...

static void	btr_search_x_unlock_all ()
	Unlock all search latches from exclusive mode. More...

static void	btr_search_s_lock (const dict_index_t *index, ut::Location location)
	S-Lock the search latch (corresponding to given index) More...

static bool	btr_search_s_lock_nowait (const dict_index_t *index, ut::Location location)
	S-Lock the search latch (corresponding to given index), does not block. More...

static void	btr_search_s_unlock (const dict_index_t *index)
	S-Unlock the search latch (corresponding to given index) More...

static void	btr_search_s_lock_all (ut::Location location)
	Lock all search latches in shared mode. More...

static bool	btr_search_own_all (ulint mode)
	Check if thread owns all the search latches. More...

static bool	btr_search_own_any (ulint mode)
	Check if thread owns any of the search latches. More...

static void	btr_search_s_unlock_all ()
	Unlock all search latches from shared mode. More...

static size_t	btr_search_hash_index_id (const dict_index_t *index)
	Compute a hash value for a specified index. More...

static class btr_search_sys_t::search_part_t &	btr_get_search_part (const dict_index_t *index)
	Gets a pointer to a adaptive search part structure for a specified index. More...

static rw_lock_t *	btr_get_search_latch (const dict_index_t *index)
	Get the latch based on index attributes. More...

Variables
constexpr uint32_t	BTR_SEARCH_MAGIC_N = 1112765
	value of btr_search_t::magic_n, used in assertions More...

btr_search_sys_t *	btr_search_sys
	The adaptive hash index. More...

constexpr uint32_t	BTR_SEARCH_HASH_ANALYSIS = 17
	After change in n_fields or n_bytes in info, this many rounds are waited before starting the hash analysis again: this is to save CPU time when there is no hope in building a hash index. More...

constexpr uint32_t	BTR_SEARCH_ON_PATTERN_LIMIT = 3
	Limit of consecutive searches for trying a search shortcut on the search pattern. More...

constexpr uint32_t	BTR_SEARCH_ON_HASH_LIMIT = 3
	Limit of consecutive searches for trying a search shortcut using the hash index. More...

Detailed Description

The index tree adaptive search.

Created 2/17/1996 Heikki Tuuri

Function Documentation

◆ btr_drop_ahi_for_index()

void btr_drop_ahi_for_index ( const dict_index_t * index )

Drop any adaptive hash index entries for a index.

Parameters

[in,out] index to drop hash indexes for this index

◆ btr_drop_ahi_for_table()

void btr_drop_ahi_for_table ( dict_table_t * table )

Drop any adaptive hash index entries for a table.

Parameters

[in,out] table to drop indexes of this table

◆ btr_get_search_latch()

static rw_lock_t * btr_get_search_latch ( const dict_index_t * index )

inlinestatic

Get the latch based on index attributes.

A latch is selected from an array of latches using pair of index-id, space-id.

Parameters

[in] index index handler

Returns: latch

◆ btr_get_search_part()

static class btr_search_sys_t::search_part_t & btr_get_search_part ( const dict_index_t * index )

inlinestatic

Gets a pointer to a adaptive search part structure for a specified index.

Parameters

[in] index Index structure

Returns: hash value of the index

◆ btr_search_await_no_reference()

void btr_search_await_no_reference	(	dict_table_t *	table,
		dict_index_t *	index,
		bool	force
	)

Wait for the specified index to have all references from AHI dropped.

We assume the caller prevents the new references from AHI from being created. This means the reference count will monotonically drop to zero.

Parameters

[in,out]	table	table handler
[in,out]	index	index data dictionary structure
[in]	force	should the wait be forced even if SRV_SHUTDOWN_CLEANUP state was reached?

◆ btr_search_disable()

bool btr_search_disable ( )

Disable the adaptive hash search system and empty the index.

Returns: true if the AHI system was enabled and became disabled.

◆ btr_search_drop_page_hash_index()

void btr_search_drop_page_hash_index	(	buf_block_t *	block,
		bool	force = `false`
	)

Drop any adaptive hash index entries that point to an index page.

Parameters

[in,out]	block	block containing index page, s- or x-latched, or an index page for which we know that block->buf_fix_count == 0 or it is an index page which has already been removed from the buf_pool->page_hash i.e.: it is in state BUF_BLOCK_REMOVE_HASH
[in]	force	Should the block's index be reset even if AHI is disabled?

◆ btr_search_drop_page_hash_when_freed()

void btr_search_drop_page_hash_when_freed	(	const page_id_t &	page_id,
		const page_size_t &	page_size
	)

Drop any adaptive hash index entries that may point to an index page that may be in the buffer pool, when a page is evicted from the buffer pool or freed in a file segment.

Parameters

[in]	page_id	page id
[in]	page_size	page size

◆ btr_search_enable()

void btr_search_enable ( )

Enable the adaptive hash search system.

◆ btr_search_guess_on_hash()

bool btr_search_guess_on_hash	(	const dtuple_t *	tuple,
		ulint	mode,
		ulint	latch_mode,
		btr_cur_t *	cursor,
		ulint	has_search_latch,
		mtr_t *	mtr
	)

Tries to guess the right search position based on the hash search info of the index.

Note that if mode is PAGE_CUR_LE, which is used in inserts, and the function returns true, then cursor->up_match and cursor->low_match both have sensible values.

Parameters

[in]	tuple	Logical record
[in]	mode	PAGE_CUR_L, ....
[in]	latch_mode	BTR_SEARCH_LEAF, ...; NOTE that only if has_search_latch is 0, we will have a latch set on the cursor page, otherwise we assume the caller uses his search latch to protect the record!
[out]	cursor	Tree cursor
[in]	has_search_latch	Latch mode the caller currently has on search system: RW_S/X_LATCH or 0
[in]	mtr	Mini-transaction

Returns: true if succeeded

◆ btr_search_hash_index_id()

static size_t btr_search_hash_index_id ( const dict_index_t * index )

inlinestatic

Compute a hash value for a specified index.

Parameters

[in] index Index structure

Returns: hash value of the index

◆ btr_search_info_create()

btr_search_t * btr_search_info_create ( mem_heap_t * heap )

Creates and initializes a search info struct.

Parameters

[in] heap heap where created.

Returns: own: search info struct

◆ btr_search_info_update()

static void btr_search_info_update ( btr_cur_t * cursor )

inlinestatic

Updates the search info statistics following a search in B-tree that was performed not using or not finding row with the AHI index.

It may do nothing or decide to try to update the searched record on which the supplied cursor in positioned at, or add the whole page to AHI.

Parameters

[in] cursor cursor which was just positioned

◆ btr_search_own_all()

static bool btr_search_own_all ( ulint mode )

inlinestatic

Check if thread owns all the search latches.

Parameters

[in] mode lock mode check

Return values

true	if owns all of them
false	if does not own some of them

◆ btr_search_own_any()

static bool btr_search_own_any ( ulint mode )

inlinestatic

Check if thread owns any of the search latches.

Parameters

[in] mode lock mode check

Return values

true	if owns any of them
false	if owns no search latch

◆ btr_search_s_lock()

static void btr_search_s_lock	(	const dict_index_t *	index,
		ut::Location	location
	)

inlinestatic

S-Lock the search latch (corresponding to given index)

Parameters

[in]	index	index handler
[in]	location	source location

◆ btr_search_s_lock_all()

static void btr_search_s_lock_all ( ut::Location location )

inlinestatic

Lock all search latches in shared mode.

Parameters

[in] location source location

◆ btr_search_s_lock_nowait()

static bool btr_search_s_lock_nowait	(	const dict_index_t *	index,
		ut::Location	location
	)

inlinestatic

S-Lock the search latch (corresponding to given index), does not block.

Parameters

[in]	index	index handler
[in]	location	source location

Returns: true if the latch could was acquired.

◆ btr_search_s_unlock()

static void btr_search_s_unlock ( const dict_index_t * index )

inlinestatic

S-Unlock the search latch (corresponding to given index)

Parameters

[in] index index handler

◆ btr_search_s_unlock_all()

static void btr_search_s_unlock_all ( )

inlinestatic

Unlock all search latches from shared mode.

◆ btr_search_set_block_not_cached()

void btr_search_set_block_not_cached ( buf_block_t * block )

Resets block's AHI index field to nullptr, removes the reference from index's reference counter.

This is done after all blocks' records were removed from AHI hash tables and caller assures the block still has reference to index.

Parameters

[in,out] block index page from which records were removed from AHI hash tables.

◆ btr_search_sys_create()

void btr_search_sys_create ( ulint hash_size )

Creates and initializes the adaptive search system at a database start.

Parameters

[in] hash_size hash table size.

◆ btr_search_sys_free()

void btr_search_sys_free ( )

Frees the adaptive search system at a database shutdown.

◆ btr_search_sys_resize()

void btr_search_sys_resize ( ulint hash_size )

Resize hash index hash table.

Parameters

[in] hash_size hash index hash table size

◆ btr_search_update_hash_node_on_insert()

void btr_search_update_hash_node_on_insert ( btr_cur_t * cursor )

Updates the page hash index when a single record is inserted on a page.

Parameters

[in] cursor cursor which was positioned to the place to insert using btr_cur_search_, and the new record has been inserted next to the cursor.

◆ btr_search_update_hash_on_delete()

void btr_search_update_hash_on_delete ( btr_cur_t * cursor )

Updates the page hash index when a single record is deleted from a page.

Parameters

[in] cursor cursor which was positioned on the record to delete using btr_cur_search_, the record is not yet deleted.

◆ btr_search_update_hash_on_insert()

void btr_search_update_hash_on_insert ( btr_cur_t * cursor )

Updates the page hash index when a single record is inserted on a page.

Parameters

[in,out] cursor cursor which was positioned to the place to insert using btr_cur_search_..., and the new record has been inserted next to the cursor.

◆ btr_search_update_hash_on_move()

void btr_search_update_hash_on_move	(	buf_block_t *	new_block,
		buf_block_t *	block,
		dict_index_t *	index
	)

Moves or deletes hash entries for moved records.

If new_page is already hashed in compatible way or not cached at all, then the hash index for the new page is (re-)built. Otherwise the old page hash records are dropped.

Parameters

[in,out]	new_block	records are copied to this page.
[in,out]	block	index page from which record are copied, and the copied records will be deleted from this page.
[in,out]	index	record descriptor

◆ btr_search_validate()

bool btr_search_validate ( )

Validates the search system.

Returns: true if ok

◆ btr_search_x_lock()

static void btr_search_x_lock	(	const dict_index_t *	index,
		ut::Location	location
	)

inlinestatic

X-Lock the search latch (corresponding to given index)

Parameters

[in]	index	index handler
[in]	location	source location

◆ btr_search_x_lock_all()

static void btr_search_x_lock_all ( ut::Location location )

inlinestatic

Lock all search latches in exclusive mode.

Parameters

[in] location source location

◆ btr_search_x_lock_nowait()

static bool btr_search_x_lock_nowait	(	const dict_index_t *	index,
		ut::Location	location
	)

inlinestatic

X-Lock the search latch (corresponding to given index), does not block.

Parameters

[in]	index	index handler
[in]	location	source location

Returns: true if the latch could was acquired.

◆ btr_search_x_unlock()

static void btr_search_x_unlock ( const dict_index_t * index )

inlinestatic

X-Unlock the search latch (corresponding to given index)

Parameters

[in] index index handler

◆ btr_search_x_unlock_all()

static void btr_search_x_unlock_all ( )

inlinestatic

Unlock all search latches from exclusive mode.

Variable Documentation

◆ BTR_SEARCH_HASH_ANALYSIS

constexpr uint32_t BTR_SEARCH_HASH_ANALYSIS = 17

constexpr

After change in n_fields or n_bytes in info, this many rounds are waited before starting the hash analysis again: this is to save CPU time when there is no hope in building a hash index.

◆ BTR_SEARCH_MAGIC_N

constexpr uint32_t BTR_SEARCH_MAGIC_N = 1112765

constexpr

value of btr_search_t::magic_n, used in assertions

◆ BTR_SEARCH_ON_HASH_LIMIT

constexpr uint32_t BTR_SEARCH_ON_HASH_LIMIT = 3

constexpr

Limit of consecutive searches for trying a search shortcut using the hash index.

◆ BTR_SEARCH_ON_PATTERN_LIMIT

constexpr uint32_t BTR_SEARCH_ON_PATTERN_LIMIT = 3

constexpr

Limit of consecutive searches for trying a search shortcut on the search pattern.

◆ btr_search_sys

btr_search_sys_t* btr_search_sys

extern

The adaptive hash index.

Classes

Functions

Variables

Detailed Description

Function Documentation

◆ btr_drop_ahi_for_index()

◆ btr_drop_ahi_for_table()

◆ btr_get_search_latch()

◆ btr_get_search_part()

◆ btr_search_await_no_reference()

◆ btr_search_disable()

◆ btr_search_drop_page_hash_index()

◆ btr_search_drop_page_hash_when_freed()

◆ btr_search_enable()

◆ btr_search_guess_on_hash()

◆ btr_search_hash_index_id()

◆ btr_search_info_create()

◆ btr_search_info_update()

◆ btr_search_own_all()

◆ btr_search_own_any()

◆ btr_search_s_lock()

◆ btr_search_s_lock_all()

◆ btr_search_s_lock_nowait()

◆ btr_search_s_unlock()

◆ btr_search_s_unlock_all()

◆ btr_search_set_block_not_cached()

◆ btr_search_sys_create()

◆ btr_search_sys_free()

◆ btr_search_sys_resize()

◆ btr_search_update_hash_node_on_insert()

◆ btr_search_update_hash_on_delete()

◆ btr_search_update_hash_on_insert()

◆ btr_search_update_hash_on_move()

◆ btr_search_validate()

◆ btr_search_x_lock()

◆ btr_search_x_lock_all()

◆ btr_search_x_lock_nowait()

◆ btr_search_x_unlock()

◆ btr_search_x_unlock_all()

Variable Documentation

◆ BTR_SEARCH_HASH_ANALYSIS

◆ BTR_SEARCH_MAGIC_N

◆ BTR_SEARCH_ON_HASH_LIMIT

◆ BTR_SEARCH_ON_PATTERN_LIMIT

◆ btr_search_sys