MySQL 8.0.31
Source Code Documentation
btr0sea.h
Go to the documentation of this file.
1/*****************************************************************************
2
3Copyright (c) 1996, 2022, Oracle and/or its affiliates.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License, version 2.0, as published by the
7Free Software Foundation.
8
9This program is also distributed with certain software (including but not
10limited to OpenSSL) that is licensed under separate terms, as designated in a
11particular file or component or in included license documentation. The authors
12of MySQL hereby grant you an additional permission to link the program and
13your derivative works with the separately licensed software that they have
14included with MySQL.
15
16This program is distributed in the hope that it will be useful, but WITHOUT
17ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
19for more details.
20
21You should have received a copy of the GNU General Public License along with
22this program; if not, write to the Free Software Foundation, Inc.,
2351 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
24
25*****************************************************************************/
26
27/** @file include/btr0sea.h
28 The index tree adaptive search
29
30 Created 2/17/1996 Heikki Tuuri
31 *************************************************************************/
32
33#ifndef btr0sea_h
34#define btr0sea_h
35
36#include "univ.i"
37
38#include "btr0types.h"
39#include "dict0dict.h"
40#include "ha0ha.h"
41#include "mtr0mtr.h"
42#include "rem0rec.h"
43
44/** Creates and initializes the adaptive search system at a database start.
45@param[in] hash_size hash table size. */
46void btr_search_sys_create(ulint hash_size);
47
48/** Resize hash index hash table.
49@param[in] hash_size hash index hash table size */
50void btr_search_sys_resize(ulint hash_size);
51
52/** Frees the adaptive search system at a database shutdown. */
54
55/** Disable the adaptive hash search system and empty the index.
56@param[in] need_mutex Need to acquire dict_sys->mutex */
57void btr_search_disable(bool need_mutex);
58/** Enable the adaptive hash search system. */
60
61/** Returns search info for an index.
62 @return search info; search mutex reserved */
64 dict_index_t *index); /*!< in: index */
65
66/** Creates and initializes a search info struct.
67@param[in] heap heap where created.
68@return own: search info struct */
70
71/** Returns the value of ref_count.
72@param[in] info search info
73@return ref_count value. */
75
76/** Updates the search info statistics following a search in B-tree that was
77performed not using or not finding row with the AHI index. It may do nothing or
78decide to try to update the searched record on which the supplied cursor in
79positioned at, or add the whole page to AHI.
80@param[in] index index of the cursor
81@param[in] cursor cursor which was just positioned */
82static inline void btr_search_info_update(dict_index_t *index,
83 btr_cur_t *cursor);
84
85/** Tries to guess the right search position based on the hash search info
86of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts,
87and the function returns true, then cursor->up_match and cursor->low_match
88both have sensible values.
89@param[in,out] index Index
90@param[in,out] info Index search info
91@param[in] tuple Logical record
92@param[in] mode PAGE_CUR_L, ....
93@param[in] latch_mode BTR_SEARCH_LEAF, ...;
94 NOTE that only if has_search_latch is 0, we will
95 have a latch set on the cursor page, otherwise
96 we assume the caller uses his search latch
97 to protect the record!
98@param[out] cursor Tree cursor
99@param[in] has_search_latch
100 Latch mode the caller currently has on
101 search system: RW_S/X_LATCH or 0
102@param[in] mtr Mini-transaction
103@return true if succeeded */
105 const dtuple_t *tuple, ulint mode,
106 ulint latch_mode, btr_cur_t *cursor,
107 ulint has_search_latch, mtr_t *mtr);
108
109/** Moves or deletes hash entries for moved records. If new_page is already
110hashed, then the hash index for page, if any, is dropped. If new_page is not
111hashed, and page is hashed, then a new hash index is built to new_page with the
112same parameters as page (this often happens when a page is split).
113@param[in,out] new_block records are copied to this page.
114@param[in,out] block index page from which record are copied, and the
115 copied records will be deleted from this page.
116@param[in,out] index record descriptor */
118 buf_block_t *block,
119 dict_index_t *index);
120
121/** Drop any adaptive hash index entries that point to an index page.
122@param[in,out] block block containing index page, s- or x-latched, or an
123 index page for which we know that
124 block->buf_fix_count == 0 or it is an index page which
125 has already been removed from the buf_pool->page_hash
126 i.e.: it is in state BUF_BLOCK_REMOVE_HASH */
128
129/** Drop any adaptive hash index entries that may point to an index
130page that may be in the buffer pool, when a page is evicted from the
131buffer pool or freed in a file segment.
132@param[in] page_id page id
133@param[in] page_size page size */
135 const page_size_t &page_size);
136
137/** Drop any adaptive hash index entries for a table.
138@param[in,out] table to drop indexes of this table */
140
141/** Drop any adaptive hash index entries for a index.
142@param[in,out] index to drop hash indexes for this index */
143void btr_drop_ahi_for_index(const dict_index_t *index);
144
145/** Updates the page hash index when a single record is inserted on a page.
146@param[in] cursor cursor which was positioned to the place to insert using
147 btr_cur_search_, and the new record has been inserted
148 next to the cursor. */
150
151/** Updates the page hash index when a single record is inserted on a page.
152@param[in,out] cursor cursor which was positioned to the place to insert using
153 btr_cur_search_..., and the new record has been inserted
154 next to the cursor. */
156
157/** Updates the page hash index when a single record is deleted from a page.
158@param[in] cursor cursor which was positioned on the record to delete
159using btr_cur_search_, the record is not yet deleted. */
161
162/** Validates the search system.
163@return true if ok */
165
166/** X-Lock the search latch (corresponding to given index)
167@param[in] index index handler
168@param[in] location source location */
169static inline void btr_search_x_lock(const dict_index_t *index,
170 ut::Location location);
171
172/** X-Lock the search latch (corresponding to given index), does not block.
173@param[in] index index handler
174@param[in] location source location
175@return true if the latch could was acquired.*/
176[[nodiscard]] static inline bool btr_search_x_lock_nowait(
177 const dict_index_t *index, ut::Location location);
178
179/** X-Unlock the search latch (corresponding to given index)
180@param[in] index index handler */
181static inline void btr_search_x_unlock(const dict_index_t *index);
182
183/** Lock all search latches in exclusive mode.
184@param[in] location source location */
185static inline void btr_search_x_lock_all(ut::Location location);
186
187/** Unlock all search latches from exclusive mode. */
188static inline void btr_search_x_unlock_all();
189
190/** S-Lock the search latch (corresponding to given index)
191@param[in] index index handler
192@param[in] location source location */
193static inline void btr_search_s_lock(const dict_index_t *index,
194 ut::Location location);
195
196/** S-Lock the search latch (corresponding to given index), does not block.
197@param[in] index index handler
198@param[in] location source location
199@return true if the latch could was acquired.*/
200[[nodiscard]] static inline bool btr_search_s_lock_nowait(
201 const dict_index_t *index, ut::Location location);
202
203/** S-Unlock the search latch (corresponding to given index)
204@param[in] index index handler */
205static inline void btr_search_s_unlock(const dict_index_t *index);
206
207/** Lock all search latches in shared mode.
208@param[in] location source location */
209static inline void btr_search_s_lock_all(ut::Location location);
210
211#ifdef UNIV_DEBUG
212/** Check if thread owns all the search latches.
213@param[in] mode lock mode check
214@retval true if owns all of them
215@retval false if does not own some of them */
216[[nodiscard]] static inline bool btr_search_own_all(ulint mode);
217
218/** Check if thread owns any of the search latches.
219@param[in] mode lock mode check
220@retval true if owns any of them
221@retval false if owns no search latch */
222[[nodiscard]] static inline bool btr_search_own_any(ulint mode);
223#endif /* UNIV_DEBUG */
224
225/** Unlock all search latches from shared mode. */
226static inline void btr_search_s_unlock_all();
227
228/** Get the adaptive hash search index slot ID for a b-tree specified by its IDs
229of index and space.
230@param[in] index_id Index of the b-tree index
231@param[in] space_id Index of the tablespace the index is in.
232@return Index of the slot for btr_search_sys->hash_tables and btr_search_latches
233arrays. */
234static inline size_t btr_get_search_slot(const space_index_t index_id,
235 const space_id_t space_id);
236
237/** Get the latch based on index attributes.
238A latch is selected from an array of latches using pair of index-id, space-id.
239@param[in] index index handler
240@return latch */
241static inline rw_lock_t *btr_get_search_latch(const dict_index_t *index);
242
243/** Get the hash-table based on index attributes.
244A table is selected from an array of tables using pair of index-id, space-id.
245@param[in] index index handler
246@return hash table */
247static inline hash_table_t *btr_get_search_table(const dict_index_t *index);
248
249/** The search info struct in an index */
251 /** Number of blocks in this index tree that have search index built i.e.
252 block->index points to this index. */
253 std::atomic<ulint> ref_count;
254
255 /** @{ The following fields are not protected by any latch.
256 Unfortunately, this means that they must be aligned to the machine word, i.e.,
257 they cannot be turned into bit-fields. */
258
259 /** the root page frame when it was last time fetched, or NULL. */
261 /** when this exceeds BTR_SEARCH_HASH_ANALYSIS, the hash analysis starts; this
262 is reset if no success noticed. */
264 /** true if the last search would have succeeded, or did succeed, using the
265 hash index; NOTE that the value here is not exact: it is not calculated for
266 every search, and the calculation itself is not always accurate! */
268 /** number of consecutive searches which would have succeeded, or did succeed,
269 using the hash index; the range is 0 .. BTR_SEARCH_BUILD_LIMIT + 5. */
271 /** @} */
272
273 /**---------------------- @{ */
274 /** recommended prefix length for hash search: number of full fields */
276 /** recommended prefix: number of bytes in an incomplete field
277 @see BTR_PAGE_MAX_REC_SIZE */
279 /** true or false, depending on whether the leftmost record of several records
280 with the same prefix should be indexed in the hash index */
282 /*---------------------- @} */
283#ifdef UNIV_SEARCH_PERF_STAT
284 /** number of successful hash searches so far. */
285 std::atomic<ulint> n_hash_succ;
286 /** number of failed hash searches */
287 std::atomic<ulint> n_hash_fail;
288 /** number of successful pattern searches thus far */
289 std::atomic<ulint> n_patt_succ;
290 /** number of searches */
291 std::atomic<ulint> n_searches;
292#endif /* UNIV_SEARCH_PERF_STAT */
293#ifdef UNIV_DEBUG
294 /** magic number @see BTR_SEARCH_MAGIC_N */
296#endif /* UNIV_DEBUG */
297};
298
299#ifdef UNIV_DEBUG
300/** value of btr_search_t::magic_n, used in assertions */
301constexpr uint32_t BTR_SEARCH_MAGIC_N = 1112765;
302#endif /* UNIV_DEBUG */
303
304/** The hash index system */
306 /** the adaptive hash tables, mapping dtuple_hash values to rec_t pointers on
307 index pages */
309};
310
311/** Latches protecting access to adaptive hash index. */
313
314/** The adaptive hash index */
316
317#ifdef UNIV_SEARCH_PERF_STAT
318/** Number of successful adaptive hash index lookups */
319extern ulint btr_search_n_succ;
320/** Number of failed adaptive hash index lookups */
321extern ulint btr_search_n_hash_fail;
322#endif /* UNIV_SEARCH_PERF_STAT */
323
324/** After change in n_fields or n_bytes in info, this many rounds are waited
325before starting the hash analysis again: this is to save CPU time when there
326is no hope in building a hash index. */
327constexpr uint32_t BTR_SEARCH_HASH_ANALYSIS = 17;
328
329/** Limit of consecutive searches for trying a search shortcut on the search
330pattern */
331constexpr uint32_t BTR_SEARCH_ON_PATTERN_LIMIT = 3;
332
333/** Limit of consecutive searches for trying a search shortcut using
334the hash index */
335constexpr uint32_t BTR_SEARCH_ON_HASH_LIMIT = 3;
336
337#include "btr0sea.ic"
338
339#endif
uint32_t space_id_t
Tablespace identifier.
Definition: api0api.h:50
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.
Definition: btr0sea.cc:1457
constexpr uint32_t BTR_SEARCH_ON_HASH_LIMIT
Limit of consecutive searches for trying a search shortcut using the hash index.
Definition: btr0sea.h:335
static rw_lock_t * btr_get_search_latch(const dict_index_t *index)
Get the latch based on index attributes.
static void btr_search_s_unlock(const dict_index_t *index)
S-Unlock the search latch (corresponding to given index)
bool btr_search_validate()
Validates the search system.
Definition: btr0sea.cc:1931
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.
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.
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.
Definition: btr0sea.cc:1632
constexpr uint32_t BTR_SEARCH_MAGIC_N
value of btr_search_t::magic_n, used in assertions
Definition: btr0sea.h:301
static void btr_search_x_unlock_all()
Unlock all search latches from exclusive mode.
void btr_search_sys_free()
Frees the adaptive search system at a database shutdown.
Definition: btr0sea.cc:249
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.
Definition: btr0sea.cc:1514
static void btr_search_x_lock(const dict_index_t *index, ut::Location location)
X-Lock the search latch (corresponding to given index)
static void btr_search_s_unlock_all()
Unlock all search latches from shared mode.
rw_lock_t ** btr_search_latches
Latches protecting access to adaptive hash index.
Definition: btr0sea.cc:83
size_t btr_search_info_get_ref_count(const btr_search_t *info)
Returns the value of ref_count.
Definition: btr0sea.cc:378
btr_search_t * btr_search_info_create(mem_heap_t *heap)
Creates and initializes a search info struct.
Definition: btr0sea.cc:347
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.
void btr_search_disable(bool need_mutex)
Disable the adaptive hash search system and empty the index.
Definition: btr0sea.cc:291
static bool btr_search_own_any(ulint mode)
Check if thread owns any of the search latches.
static void btr_search_x_lock_all(ut::Location location)
Lock all search latches in exclusive mode.
constexpr uint32_t BTR_SEARCH_ON_PATTERN_LIMIT
Limit of consecutive searches for trying a search shortcut on the search pattern.
Definition: btr0sea.h:331
void btr_search_sys_resize(ulint hash_size)
Resize hash index hash table.
Definition: btr0sea.cc:218
static hash_table_t * btr_get_search_table(const dict_index_t *index)
Get the hash-table based on index attributes.
static btr_search_t * btr_search_get_info(dict_index_t *index)
Returns search info for an index.
void btr_search_drop_page_hash_index(buf_block_t *block)
Drop any adaptive hash index entries that point to an index page.
Definition: btr0sea.cc:965
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.
Definition: btr0sea.cc:774
void btr_search_sys_create(ulint hash_size)
Creates and initializes the adaptive search system at a database start.
Definition: btr0sea.cc:178
static bool btr_search_own_all(ulint mode)
Check if thread owns all the search latches.
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 f...
void btr_drop_ahi_for_index(const dict_index_t *index)
Drop any adaptive hash index entries for a index.
Definition: btr0sea.cc:1257
void btr_drop_ahi_for_table(dict_table_t *table)
Drop any adaptive hash index entries for a table.
Definition: btr0sea.cc:1220
btr_search_sys_t * btr_search_sys
The adaptive hash index.
Definition: btr0sea.cc:90
constexpr uint32_t BTR_SEARCH_HASH_ANALYSIS
After change in n_fields or n_bytes in info, this many rounds are waited before starting the hash ana...
Definition: btr0sea.h:327
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,...
Definition: btr0sea.cc:1132
static void btr_search_s_lock_all(ut::Location location)
Lock all search latches in shared mode.
void btr_search_enable()
Enable the adaptive hash search system.
Definition: btr0sea.cc:336
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.
Definition: btr0sea.cc:1568
static void btr_search_s_lock(const dict_index_t *index, ut::Location location)
S-Lock the search latch (corresponding to given index)
static void btr_search_x_unlock(const dict_index_t *index)
X-Unlock the search latch (corresponding to given index)
The index tree adaptive search.
The index tree general types.
Definition: hash0hash.h:373
Page identifier.
Definition: buf0types.h:206
Page size descriptor.
Definition: page0size.h:49
Data dictionary system.
ib_id_t space_index_t
Index identifier (unique within a tablespace).
Definition: dict0types.h:219
The hash table with external chains.
Mini-transaction buffer.
Log info(cout, "NOTE")
mode
Definition: file_handle.h:59
Record manager.
The tree cursor: the definition appears here only for the compiler to know struct size!
Definition: btr0cur.h:667
The hash index system.
Definition: btr0sea.h:305
hash_table_t ** hash_tables
the adaptive hash tables, mapping dtuple_hash values to rec_t pointers on index pages
Definition: btr0sea.h:308
The search info struct in an index.
Definition: btr0sea.h:250
ulint n_fields
-------------------—
Definition: btr0sea.h:275
ulint n_hash_potential
number of consecutive searches which would have succeeded, or did succeed, using the hash index; the ...
Definition: btr0sea.h:270
std::atomic< ulint > ref_count
Number of blocks in this index tree that have search index built i.e.
Definition: btr0sea.h:253
bool last_hash_succ
true if the last search would have succeeded, or did succeed, using the hash index; NOTE that the val...
Definition: btr0sea.h:267
ulint magic_n
magic number
Definition: btr0sea.h:295
ulint n_bytes
recommended prefix: number of bytes in an incomplete field
Definition: btr0sea.h:278
buf_block_t * root_guess
the root page frame when it was last time fetched, or NULL.
Definition: btr0sea.h:260
ulint hash_analysis
when this exceeds BTR_SEARCH_HASH_ANALYSIS, the hash analysis starts; this is reset if no success not...
Definition: btr0sea.h:263
bool left_side
true or false, depending on whether the leftmost record of several records with the same prefix shoul...
Definition: btr0sea.h:281
The buffer control block structure.
Definition: buf0buf.h:1664
Data structure for an index.
Definition: dict0mem.h:1021
Data structure for a database table.
Definition: dict0mem.h:1884
Structure for an SQL data tuple of fields (logical record)
Definition: data0data.h:681
The info structure stored at the beginning of a heap block.
Definition: mem0mem.h:299
Mini-transaction handle and buffer.
Definition: mtr0mtr.h:181
The structure used in the spin lock implementation of a read-write lock.
Definition: sync0rw.h:361
Definition: ut0core.h:32
Version control for database, common definitions, and include files.
unsigned long int ulint
Definition: univ.i:407