MySQL 8.0.31
Source Code Documentation
btr0sea.h File Reference

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"

Go to the source code of this file.

Classes

struct  btr_search_t
 The search info struct in an index. More...
 
struct  btr_search_sys_t
 The hash index system. More...
 

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...
 
void btr_search_disable (bool need_mutex)
 Disable the adaptive hash search system and empty the index. More...
 
void btr_search_enable ()
 Enable the adaptive hash search system. More...
 
static btr_search_tbtr_search_get_info (dict_index_t *index)
 Returns search info for an index. More...
 
btr_search_tbtr_search_info_create (mem_heap_t *heap)
 Creates and initializes a search info struct. More...
 
size_t btr_search_info_get_ref_count (const btr_search_t *info)
 Returns the value of ref_count. More...
 
static void btr_search_info_update (dict_index_t *index, 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 (dict_index_t *index, btr_search_t *info, 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_move_or_delete_hash_entries (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)
 Drop any adaptive hash index entries that point to an index page. 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_get_search_slot (const space_index_t index_id, const space_id_t space_id)
 Get the adaptive hash search index slot ID for a b-tree specified by its IDs of index and space. More...
 
static rw_lock_tbtr_get_search_latch (const dict_index_t *index)
 Get the latch based on index attributes. More...
 
static hash_table_tbtr_get_search_table (const dict_index_t *index)
 Get the hash-table 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...
 
rw_lock_t ** btr_search_latches
 Latches protecting access to adaptive hash index. More...
 
btr_search_sys_tbtr_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]indexto 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]tableto 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]indexindex handler
Returns
latch

◆ btr_get_search_slot()

static size_t btr_get_search_slot ( const space_index_t  index_id,
const space_id_t  space_id 
)
inlinestatic

Get the adaptive hash search index slot ID for a b-tree specified by its IDs of index and space.

Parameters
[in]index_idIndex of the b-tree index
[in]space_idIndex of the tablespace the index is in.
Returns
Index of the slot for btr_search_sys->hash_tables and btr_search_latches arrays.

◆ 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]indexindex handler
Returns
hash table

◆ btr_search_disable()

void btr_search_disable ( bool  need_mutex)

Disable the adaptive hash search system and empty the index.

Parameters
[in]need_mutexNeed to acquire dict_sys->mutex

◆ btr_search_drop_page_hash_index()

void btr_search_drop_page_hash_index ( buf_block_t block)

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

Parameters
[in,out]blockblock 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

◆ 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_idpage id
[in]page_sizepage size

◆ btr_search_enable()

void btr_search_enable ( )

Enable the adaptive hash search system.

◆ btr_search_get_info()

static btr_search_t * btr_search_get_info ( dict_index_t index)
inlinestatic

Returns search info for an index.

Returns
search info; search mutex reserved in: index

◆ btr_search_guess_on_hash()

bool btr_search_guess_on_hash ( dict_index_t index,
btr_search_t info,
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,out]indexIndex
[in,out]infoIndex search info
[in]tupleLogical record
[in]modePAGE_CUR_L, ....
[in]latch_modeBTR_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]cursorTree cursor
[in]has_search_latchLatch mode the caller currently has on search system: RW_S/X_LATCH or 0
[in]mtrMini-transaction
Returns
true if succeeded

◆ btr_search_info_create()

btr_search_t * btr_search_info_create ( mem_heap_t heap)

Creates and initializes a search info struct.

Parameters
[in]heapheap where created.
Returns
own: search info struct

◆ btr_search_info_get_ref_count()

size_t btr_search_info_get_ref_count ( const btr_search_t info)

Returns the value of ref_count.

Parameters
[in]infosearch info
Returns
ref_count value.

◆ btr_search_info_update()

static void btr_search_info_update ( dict_index_t index,
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]indexindex of the cursor
[in]cursorcursor which was just positioned

◆ btr_search_move_or_delete_hash_entries()

void btr_search_move_or_delete_hash_entries ( 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, then the hash index for page, if any, is dropped. If new_page is not hashed, and page is hashed, then a new hash index is built to new_page with the same parameters as page (this often happens when a page is split).

Parameters
[in,out]new_blockrecords are copied to this page.
[in,out]blockindex page from which record are copied, and the copied records will be deleted from this page.
[in,out]indexrecord descriptor

◆ btr_search_own_all()

static bool btr_search_own_all ( ulint  mode)
inlinestatic

Check if thread owns all the search latches.

Parameters
[in]modelock mode check
Return values
trueif owns all of them
falseif 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]modelock mode check
Return values
trueif owns any of them
falseif 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]indexindex handler
[in]locationsource 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]locationsource 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]indexindex handler
[in]locationsource 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]indexindex handler

◆ btr_search_s_unlock_all()

static void btr_search_s_unlock_all ( )
inlinestatic

Unlock all search latches from shared mode.

◆ 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_sizehash 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_sizehash 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]cursorcursor 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]cursorcursor 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]cursorcursor 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_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]indexindex handler
[in]locationsource 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]locationsource 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]indexindex handler
[in]locationsource 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]indexindex 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_latches

rw_lock_t** btr_search_latches
extern

Latches protecting access to adaptive hash index.

Latches protecting access to adaptive hash index.

NOTE: It does not protect values of non-ordering fields within a record from being updated in-place! We can use fact (1) to perform unique searches to indexes. We will allocate the latches from dynamic memory to get it to the same DRAM page as other hotspot semaphores

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