The index tree adaptive search. More...

#include "btr0sea.h"
#include <sys/types.h>
#include "btr0btr.h"
#include "btr0cur.h"
#include "btr0pcur.h"
#include "buf0buf.h"
#include "ha0ha.h"
#include "page0cur.h"
#include "page0page.h"
#include "srv0mon.h"
#include "sync0sync.h"
#include <scope_guard.h>

Functions
static ulint	btr_hash_seed_for_record (const dict_index_t *index)
	Compute a value to seed the hash value of a record. More...

static hash_table_t *	btr_get_search_table (const dict_index_t *index)
	Get the hash-table based on index attributes. More...

uint16_t	btr_search_get_n_fields (btr_search_prefix_info_t prefix_info)
	Determine the number of accessed key fields. More...

uint16_t	btr_search_get_n_fields (const btr_cur_t *cursor)
	Determine the number of accessed key fields. More...

static void	btr_search_build_page_hash_index (dict_index_t index, buf_block_t block, bool update)
	Builds a hash index on a page with the block's recommended parameters. More...

static void	btr_search_check_free_space_in_heap (dict_index_t *index)
	Checks that there is a free buffer frame allocated for hash table heap in the btr search system. More...

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

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_await_no_reference (dict_table_t *table)
	Wait for every index in the specified table to have all references from AHI dropped. 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...

static void	btr_search_info_update_hash (btr_cur_t *cursor)
	Updates the search info of an index about hash successes. More...

static bool	btr_search_update_block_hash_info (buf_block_t block, const btr_cur_t cursor)
	Update the block search info on hash successes. More...

static void	btr_search_update_hash_ref (buf_block_t block, const btr_cur_t cursor)
	Updates a hash node reference when it has been unsuccessfully used in a search which could have succeeded with the used hash parameters. More...

void	btr_search_info_update_slow (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...

static bool	btr_search_check_guess (btr_cur_t cursor, bool can_only_compare_to_cursor_rec, const dtuple_t tuple, ulint mode, mtr_t *mtr)
	Checks if a guessed position for a tree cursor is right. 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_drop_page_hash_index (buf_block_t *block, bool force)
	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...

static void	btr_drop_next_batch (const page_size_t &page_size, const dict_index_t first, const dict_index_t last)

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_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_update_hash_on_delete (btr_cur_t *cursor)
	Updates the page hash index when a single record is deleted from a page. 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...

static bool	btr_search_hash_table_validate (ulint part_id)
	Validates the search system for given hash table. More...

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

Variables
std::atomic_bool	btr_search_enabled = true
	Flag storing if the search system is in enabled state. More...

bool	srv_btr_search_enabled = true
	A value that basically stores the same as btr_search_enabled, but is not atomic and thus can be used as SYSVAR. More...

static ib_mutex_t	btr_search_enabled_mutex
	Protects changes of btr_search_enabled flag. More...

ulong	btr_ahi_parts = 8
	Number of adaptive hash index partition. More...

ut::fast_modulo_t	btr_ahi_parts_fast_modulo (8)

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

constexpr uint32_t	BTR_SEARCH_PAGE_BUILD_LIMIT = 16
	If the number of records on the page divided by this parameter would have been successfully accessed using a hash index, the index is then built on the page, assuming the global limit has been reached. More...

constexpr uint32_t	BTR_SEARCH_BUILD_LIMIT = 100
	The global limit for consecutive potentially successful hash searches, before hash index building is started. 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_drop_next_batch()

static void btr_drop_next_batch	(	const page_size_t &	page_size,
		const dict_index_t **	first,
		const dict_index_t **	last
	)

static

◆ btr_get_search_table()

static hash_table_t * btr_get_search_table ( const dict_index_t * index )

inlinestatic

Get the hash-table based on index attributes.

A table is selected from an array of tables using pair of index-id, space-id.

Parameters

[in] index index handler

Returns: hash table

◆ btr_hash_seed_for_record()

static ulint btr_hash_seed_for_record ( const dict_index_t * index )

static

Compute a value to seed the hash value of a record.

Parameters

[in] index Index structure

Returns: hash value for seed

◆ btr_search_await_no_reference() [1/2]

static void btr_search_await_no_reference ( dict_table_t * table )

static

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

This can only be called while the AHI is being disabled. The last fact causes that no new references to indexes can be added from AHI, so the reference count will monotonically drop to zero.

Parameters

[in,out] table table handler

◆ btr_search_await_no_reference() [2/2]

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

static void btr_search_build_page_hash_index	(	dict_index_t *	index,
		buf_block_t *	block,
		bool	update
	)

static

Builds a hash index on a page with the block's recommended parameters.

If the page already has a hash index with different parameters, the old hash index is removed. This function checks if n_fields and n_bytes are sensible, and does not build a hash index if not.

Parameters

[in,out]	index	index for which to build
[in,out]	block	index page, s-/x- latched.
[in]	update	specifies if the page should be only added to index (false) or possibly updated if any hash entries are already added for the records this page has (true)

◆ btr_search_check_free_space_in_heap()

static void btr_search_check_free_space_in_heap ( dict_index_t * index )

inlinestatic

Checks that there is a free buffer frame allocated for hash table heap in the btr search system.

If not, allocates a free frame for the heap. This function should be called before reserving any btr search mutex, if the intended operation might add nodes to the search system hash table. The heap frame will allow to do some insertions to the AHI hash table, but does not guarantee anything, i.e. there may be a space in frame only for a part of the nodes to insert or some other concurrent operation on AHI could consume the frame's memory before we latch the AHI.

Parameters

[in] index index handler

◆ btr_search_check_guess()

static bool btr_search_check_guess	(	btr_cur_t *	cursor,
		bool	can_only_compare_to_cursor_rec,
		const dtuple_t *	tuple,
		ulint	mode,
		mtr_t *	mtr
	)

static

Checks if a guessed position for a tree cursor is right.

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,out]	cursor	Guess cursor position
[in]	can_only_compare_to_cursor_rec	If we do not have a latch on the page of cursor, but a latch corresponding search system, then ONLY the columns of the record UNDER the cursor are protected, not the next or previous record in the chain: we cannot look at the next or previous record to check our guess!
[in]	tuple	Data tuple
[in]	mode	PAGE_CUR_L, PAGE_CUR_LE, PAGE_CUR_G, PAGE_CUR_GE
[in]	mtr	Mini-transaction

Returns: true if success

◆ 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_get_n_fields() [1/2]

uint16_t btr_search_get_n_fields ( btr_search_prefix_info_t prefix_info )

inline

Determine the number of accessed key fields.

Parameters

[in] prefix_info prefix information to get number of fields from

Returns: number of complete or incomplete fields

◆ btr_search_get_n_fields() [2/2]

uint16_t btr_search_get_n_fields ( const btr_cur_t * cursor )

inline

Determine the number of accessed key fields.

Parameters

[in] cursor b-tree cursor

Returns: number of complete or incomplete fields

◆ 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_table_validate()

static bool btr_search_hash_table_validate ( ulint part_id )

static

Validates the search system for given hash table.

Parameters

[in] part_id Part ID of AHI, for which hash table is to be validated.

Returns: true if OK

◆ 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_hash()

static void btr_search_info_update_hash ( btr_cur_t * cursor )

static

Updates the search info of an index about hash successes.

NOTE that info is NOT protected by any semaphore, to save CPU time! Do not assume its fields are consistent.

Parameters

[in] cursor cursor which was just positioned

◆ btr_search_info_update_slow()

void btr_search_info_update_slow ( 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.

It may 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_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_block_hash_info()

static bool btr_search_update_block_hash_info	(	buf_block_t *	block,
		const btr_cur_t *	cursor
	)

static

Update the block search info on hash successes.

NOTE that info and block->n_hash_helps, ahi.prefix_info are NOT protected by any semaphore, to save CPU time! Do not assume the fields are consistent.

Returns: true if building a (new) hash index on the block is recommended

Parameters

[in,out]	block	buffer block
[in]	cursor	cursor

◆ 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_update_hash_ref()

static void btr_search_update_hash_ref	(	buf_block_t *	block,
		const btr_cur_t *	cursor
	)

static

Updates a hash node reference when it has been unsuccessfully used in a search which could have succeeded with the used hash parameters.

This can happen because when building a hash index for a page, we do not check what happens at page boundaries, and therefore there can be misleading hash nodes. Also, collisions in the hash value can lead to misleading references. This function lazily fixes these imperfections in the hash index.

Parameters

[in]	block	buffer block where cursor positioned
[in]	cursor	cursor

◆ btr_search_validate()

bool btr_search_validate ( )

Validates the search system.

Returns: true if ok

Variable Documentation

◆ btr_ahi_parts

ulong btr_ahi_parts = 8

Number of adaptive hash index partition.

◆ btr_ahi_parts_fast_modulo

ut::fast_modulo_t btr_ahi_parts_fast_modulo(8) ( 8 )

◆ BTR_SEARCH_BUILD_LIMIT

constexpr uint32_t BTR_SEARCH_BUILD_LIMIT = 100

constexpr

The global limit for consecutive potentially successful hash searches, before hash index building is started.

◆ btr_search_enabled

std::atomic_bool btr_search_enabled = true

Flag storing if the search system is in enabled state.

Is search system enabled.

While it is false, the AHI data structures can't have new entries added, they can only be removed. It is changed to false while having all AHI latches X-latched, so any section that adds entries to AHI data structures must have at least one S-latch. All changes to this flag are protected by the btr_search_enable_mutex.

◆ btr_search_enabled_mutex

ib_mutex_t btr_search_enabled_mutex

static

Protects changes of btr_search_enabled flag.

◆ BTR_SEARCH_PAGE_BUILD_LIMIT

constexpr uint32_t BTR_SEARCH_PAGE_BUILD_LIMIT = 16

constexpr

If the number of records on the page divided by this parameter would have been successfully accessed using a hash index, the index is then built on the page, assuming the global limit has been reached.

◆ btr_search_sys

btr_search_sys_t* btr_search_sys

The adaptive hash index.

◆ srv_btr_search_enabled

bool srv_btr_search_enabled = true

A value that basically stores the same as btr_search_enabled, but is not atomic and thus can be used as SYSVAR.

Functions

Variables

Detailed Description

Function Documentation

◆ btr_drop_ahi_for_index()

◆ btr_drop_ahi_for_table()

◆ btr_drop_next_batch()

◆ btr_get_search_table()

◆ btr_hash_seed_for_record()

◆ btr_search_await_no_reference() [1/2]

◆ btr_search_await_no_reference() [2/2]

◆ btr_search_build_page_hash_index()

◆ btr_search_check_free_space_in_heap()

◆ btr_search_check_guess()

◆ btr_search_disable()

◆ btr_search_drop_page_hash_index()

◆ btr_search_drop_page_hash_when_freed()

◆ btr_search_enable()

◆ btr_search_get_n_fields() [1/2]

◆ btr_search_get_n_fields() [2/2]

◆ btr_search_guess_on_hash()

◆ btr_search_hash_table_validate()

◆ btr_search_info_create()

◆ btr_search_info_update_hash()

◆ btr_search_info_update_slow()

◆ btr_search_set_block_not_cached()

◆ btr_search_sys_create()

◆ btr_search_sys_free()

◆ btr_search_sys_resize()

◆ btr_search_update_block_hash_info()

◆ 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_update_hash_ref()

◆ btr_search_validate()

Variable Documentation

◆ btr_ahi_parts

◆ btr_ahi_parts_fast_modulo

◆ BTR_SEARCH_BUILD_LIMIT

◆ btr_search_enabled

◆ btr_search_enabled_mutex

◆ BTR_SEARCH_PAGE_BUILD_LIMIT

◆ btr_search_sys

◆ srv_btr_search_enabled