MySQL 8.4.3
Source Code Documentation
btr0sea.h
Go to the documentation of this file.
1/*****************************************************************************
2
3Copyright (c) 1996, 2024, 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 designed to work with certain software (including
10but not limited to OpenSSL) that is licensed under separate terms,
11as designated in a particular file or component or in included license
12documentation. The authors of MySQL hereby grant you an additional
13permission to link the program and your derivative works with the
14separately licensed software that they have either included with
15the program or referenced in the documentation.
16
17This program is distributed in the hope that it will be useful, but WITHOUT
18ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
19FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
20for more details.
21
22You should have received a copy of the GNU General Public License along with
23this program; if not, write to the Free Software Foundation, Inc.,
2451 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
25
26*****************************************************************************/
27
28/** @file include/btr0sea.h
29 The index tree adaptive search
30
31 Created 2/17/1996 Heikki Tuuri
32 *************************************************************************/
33
34#ifndef btr0sea_h
35#define btr0sea_h
36
37#include "univ.i"
38
39#include "btr0types.h"
40#include "dict0dict.h"
41#include "ha0ha.h"
42#include "mtr0mtr.h"
43#include "rem0rec.h"
44
45/** The search info struct in an index */
47 /** Number of blocks in this index tree that have search index built i.e.
48 block->ahi.index points to this index. */
49 std::atomic<size_t> ref_count;
50
51 /** @{ The following fields are not protected by any latch.
52 Unfortunately, this means that they must be aligned to the machine word, i.e.,
53 they cannot be turned into bit-fields. */
54
55 /** the root page frame when it was last time fetched, or NULL. */
57 /** when this exceeds BTR_SEARCH_HASH_ANALYSIS, the hash analysis starts; this
58 is reset if no success noticed. */
59 std::atomic<uint64_t> hash_analysis;
60 /** true if the last search would have succeeded, or did succeed, using the
61 hash index; NOTE that the value here is not exact: it is not calculated for
62 every search, and the calculation itself is not always accurate! */
64 /** number of consecutive searches which would have succeeded, or did succeed,
65 using the hash index; the range is 0 .. BTR_SEARCH_BUILD_LIMIT + 5. */
66 std::atomic<uint64_t> n_hash_potential;
67 /** @} */
68
69 std::atomic<btr_search_prefix_info_t> prefix_info;
70 static_assert(decltype(prefix_info)::is_always_lock_free);
71#ifdef UNIV_SEARCH_PERF_STAT
72 /** number of successful hash searches so far. */
73 std::atomic<ulint> n_hash_succ;
74 /** number of failed hash searches */
75 std::atomic<ulint> n_hash_fail;
76 /** number of successful pattern searches thus far */
77 std::atomic<ulint> n_patt_succ;
78 /** number of searches */
79 std::atomic<ulint> n_searches;
80#endif /* UNIV_SEARCH_PERF_STAT */
81#ifdef UNIV_DEBUG
82 /** magic number @see BTR_SEARCH_MAGIC_N */
84#endif /* UNIV_DEBUG */
85};
86
87#ifdef UNIV_DEBUG
88/** value of btr_search_t::magic_n, used in assertions */
89constexpr uint32_t BTR_SEARCH_MAGIC_N = 1112765;
90#endif /* UNIV_DEBUG */
91
92/** The hash index system */
94 public:
95 btr_search_sys_t(size_t hash_size);
96
98 public:
99 void initialize(size_t hash_size);
100 /** The latch protecting the adaptive search part: this latch protects the
101 (1) positions of records on those pages where a hash index has been built.
102 NOTE: It does not protect values of non-ordering fields within a record from
103 being updated in-place! We can use fact (1) to perform unique searches to
104 indexes. */
106 /** The adaptive hash table, mapping dtuple_hash values to rec_t pointers
107 on index pages. For any hash value at most one pointer is hold. Is protected
108 by the part's latch. It is in a separate cache line to not collide with the
109 possible multiple readers that are registering for the latching. */
111 /** A pointer to a free block that the heap in the hash table may use for
112 adding new hash nodes. Changes to nullptr are done under appropriate
113 X-latched rwlock. Changes from nullptr to non-nullptr are done without any
114 protection. Changes from non-null to a different non-null are prohibited. */
115 std::atomic<buf_block_t *> free_block_for_heap;
116 };
117
118 /** Partitions of the AHI system. */
120};
121
122/** The adaptive hash index */
124
125/** Creates and initializes the adaptive search system at a database start.
126@param[in] hash_size hash table size. */
127void btr_search_sys_create(ulint hash_size);
128
129/** Resize hash index hash table.
130@param[in] hash_size hash index hash table size */
131void btr_search_sys_resize(ulint hash_size);
132
133/** Frees the adaptive search system at a database shutdown. */
135
136/** Disable the adaptive hash search system and empty the index.
137@returns true if the AHI system was enabled and became disabled. */
138bool btr_search_disable();
139/** Enable the adaptive hash search system. */
140void btr_search_enable();
141
142/** Creates and initializes a search info struct.
143@param[in] heap heap where created.
144@return own: search info struct */
146
147/** Wait for the specified index to have all references from AHI dropped. We
148assume the caller prevents the new references from AHI from being created. This
149means the reference count will monotonically drop to zero.
150@param[in,out] table table handler
151@param[in,out] index index data dictionary structure
152@param[in] force should the wait be forced even if SRV_SHUTDOWN_CLEANUP
153 state was reached? */
155 bool force);
156
157/** Updates the search info statistics following a search in B-tree that was
158performed not using or not finding row with the AHI index. It may do nothing or
159decide to try to update the searched record on which the supplied cursor in
160positioned at, or add the whole page to AHI.
161@param[in] cursor cursor which was just positioned */
162static inline void btr_search_info_update(btr_cur_t *cursor);
163
164/** Tries to guess the right search position based on the hash search info
165of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts,
166and the function returns true, then cursor->up_match and cursor->low_match
167both have sensible values.
168@param[in] tuple Logical record
169@param[in] mode PAGE_CUR_L, ....
170@param[in] latch_mode BTR_SEARCH_LEAF, ...;
171 NOTE that only if has_search_latch is 0, we will
172 have a latch set on the cursor page, otherwise
173 we assume the caller uses his search latch
174 to protect the record!
175@param[out] cursor Tree cursor
176@param[in] has_search_latch
177 Latch mode the caller currently has on
178 search system: RW_S/X_LATCH or 0
179@param[in] mtr Mini-transaction
180@return true if succeeded */
182 ulint latch_mode, btr_cur_t *cursor,
183 ulint has_search_latch, mtr_t *mtr);
184
185/** Moves or deletes hash entries for moved records. If new_page is already
186hashed in compatible way or not cached at all, then the hash index for the new
187page is (re-)built. Otherwise the old page hash records are dropped.
188@param[in,out] new_block records are copied to this page.
189@param[in,out] block index page from which record are copied, and the
190 copied records will be deleted from this page.
191@param[in,out] index record descriptor */
193 dict_index_t *index);
194
195/** Drop any adaptive hash index entries that point to an index page.
196@param[in,out] block block containing index page, s- or x-latched, or an
197 index page for which we know that
198 block->buf_fix_count == 0 or it is an index page which
199 has already been removed from the buf_pool->page_hash
200 i.e.: it is in state BUF_BLOCK_REMOVE_HASH
201@param[in] force Should the block's index be reset even if AHI is
202 disabled? */
203void btr_search_drop_page_hash_index(buf_block_t *block, bool force = false);
204
205/** Resets block's AHI index field to nullptr, removes the reference from
206index's reference counter. This is done after all blocks' records were removed
207from AHI hash tables and caller assures the block still has reference to index.
208@param[in,out] block index page from which records were removed from
209 AHI hash tables. */
211
212/** Drop any adaptive hash index entries that may point to an index
213page that may be in the buffer pool, when a page is evicted from the
214buffer pool or freed in a file segment.
215@param[in] page_id page id
216@param[in] page_size page size */
218 const page_size_t &page_size);
219
220/** Drop any adaptive hash index entries for a table.
221@param[in,out] table to drop indexes of this table */
223
224/** Drop any adaptive hash index entries for a index.
225@param[in,out] index to drop hash indexes for this index */
226void btr_drop_ahi_for_index(const dict_index_t *index);
227
228/** Updates the page hash index when a single record is inserted on a page.
229@param[in] cursor cursor which was positioned to the place to insert using
230 btr_cur_search_, and the new record has been inserted
231 next to the cursor. */
233
234/** Updates the page hash index when a single record is inserted on a page.
235@param[in,out] cursor cursor which was positioned to the place to insert using
236 btr_cur_search_..., and the new record has been inserted
237 next to the cursor. */
239
240/** Updates the page hash index when a single record is deleted from a page.
241@param[in] cursor cursor which was positioned on the record to delete
242 using btr_cur_search_, the record is not yet deleted. */
244
245/** Validates the search system.
246@return true if ok */
248
249/** X-Lock the search latch (corresponding to given index)
250@param[in] index index handler
251@param[in] location source location */
252static inline void btr_search_x_lock(const dict_index_t *index,
253 ut::Location location);
254
255/** X-Lock the search latch (corresponding to given index), does not block.
256@param[in] index index handler
257@param[in] location source location
258@return true if the latch could was acquired.*/
259[[nodiscard]] static inline bool btr_search_x_lock_nowait(
260 const dict_index_t *index, ut::Location location);
261
262/** X-Unlock the search latch (corresponding to given index)
263@param[in] index index handler */
264static inline void btr_search_x_unlock(const dict_index_t *index);
265
266/** Lock all search latches in exclusive mode.
267@param[in] location source location */
268static inline void btr_search_x_lock_all(ut::Location location);
269
270/** Unlock all search latches from exclusive mode. */
271static inline void btr_search_x_unlock_all();
272
273/** S-Lock the search latch (corresponding to given index)
274@param[in] index index handler
275@param[in] location source location */
276static inline void btr_search_s_lock(const dict_index_t *index,
277 ut::Location location);
278
279/** S-Lock the search latch (corresponding to given index), does not block.
280@param[in] index index handler
281@param[in] location source location
282@return true if the latch could was acquired.*/
283[[nodiscard]] static inline bool btr_search_s_lock_nowait(
284 const dict_index_t *index, ut::Location location);
285
286/** S-Unlock the search latch (corresponding to given index)
287@param[in] index index handler */
288static inline void btr_search_s_unlock(const dict_index_t *index);
289
290/** Lock all search latches in shared mode.
291@param[in] location source location */
292static inline void btr_search_s_lock_all(ut::Location location);
293
294#ifdef UNIV_DEBUG
295/** Check if thread owns all the search latches.
296@param[in] mode lock mode check
297@retval true if owns all of them
298@retval false if does not own some of them */
299[[nodiscard]] static inline bool btr_search_own_all(ulint mode);
300
301/** Check if thread owns any of the search latches.
302@param[in] mode lock mode check
303@retval true if owns any of them
304@retval false if owns no search latch */
305[[nodiscard]] static inline bool btr_search_own_any(ulint mode);
306#endif /* UNIV_DEBUG */
307
308/** Unlock all search latches from shared mode. */
309static inline void btr_search_s_unlock_all();
310
311/** Compute a hash value for a specified index.
312@param[in] index Index structure
313@return hash value of the index */
314static inline size_t btr_search_hash_index_id(const dict_index_t *index);
315
316/** Gets a pointer to a adaptive search part structure for a specified index.
317@param[in] index Index structure
318@return hash value of the index */
320 const dict_index_t *index);
321
322/** Get the latch based on index attributes.
323A latch is selected from an array of latches using pair of index-id, space-id.
324@param[in] index index handler
325@return latch */
326static inline rw_lock_t *btr_get_search_latch(const dict_index_t *index);
327
328#ifdef UNIV_SEARCH_PERF_STAT
329/** Number of successful adaptive hash index lookups */
330extern ulint btr_search_n_succ;
331/** Number of failed adaptive hash index lookups */
332extern ulint btr_search_n_hash_fail;
333#endif /* UNIV_SEARCH_PERF_STAT */
334
335/** After change in n_fields or n_bytes in info, this many rounds are waited
336before starting the hash analysis again: this is to save CPU time when there
337is no hope in building a hash index. */
338constexpr uint32_t BTR_SEARCH_HASH_ANALYSIS = 17;
339
340/** Limit of consecutive searches for trying a search shortcut on the search
341pattern */
342constexpr uint32_t BTR_SEARCH_ON_PATTERN_LIMIT = 3;
343
344/** Limit of consecutive searches for trying a search shortcut using
345the hash index */
346constexpr uint32_t BTR_SEARCH_ON_HASH_LIMIT = 3;
347
348#include "btr0sea.ic"
349
350#endif
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.
Definition: btr0sea.cc:1006
constexpr uint32_t BTR_SEARCH_ON_HASH_LIMIT
Limit of consecutive searches for trying a search shortcut using the hash index.
Definition: btr0sea.h:346
bool btr_search_disable()
Disable the adaptive hash search system and empty the index.
Definition: btr0sea.cc:314
static rw_lock_t * btr_get_search_latch(const dict_index_t *index)
Get the latch based on index attributes.
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.
Definition: btr0sea.cc:1581
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:2048
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:1737
static size_t btr_search_hash_index_id(const dict_index_t *index)
Compute a hash value for a specified index.
constexpr uint32_t BTR_SEARCH_MAGIC_N
value of btr_search_t::magic_n, used in assertions
Definition: btr0sea.h:89
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:256
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:1632
static void btr_search_x_lock(const dict_index_t *index, ut::Location location)
X-Lock the search latch (corresponding to given index)
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.
static void btr_search_s_unlock_all()
Unlock all search latches from shared mode.
btr_search_t * btr_search_info_create(mem_heap_t *heap)
Creates and initializes a search info struct.
Definition: btr0sea.cc:374
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_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.
Definition: btr0sea.cc:273
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.
Definition: btr0sea.cc:1226
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:342
void btr_search_sys_resize(ulint hash_size)
Resize hash index hash table.
Definition: btr0sea.cc:223
void btr_search_sys_create(ulint hash_size)
Creates and initializes the adaptive search system at a database start.
Definition: btr0sea.cc:186
static bool btr_search_own_all(ulint mode)
Check if thread owns all the search latches.
void btr_drop_ahi_for_index(const dict_index_t *index)
Drop any adaptive hash index entries for a index.
Definition: btr0sea.cc:1384
void btr_drop_ahi_for_table(dict_table_t *table)
Drop any adaptive hash index entries for a table.
Definition: btr0sea.cc:1347
btr_search_sys_t * btr_search_sys
The adaptive hash index.
Definition: btr0sea.cc:85
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.
Definition: btr0sea.cc:805
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:338
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:1259
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 f...
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:359
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:1687
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: btr0sea.h:97
std::atomic< buf_block_t * > free_block_for_heap
A pointer to a free block that the heap in the hash table may use for adding new hash nodes.
Definition: btr0sea.h:115
hash_table_t * hash_table
The adaptive hash table, mapping dtuple_hash values to rec_t pointers on index pages.
Definition: btr0sea.h:110
rw_lock_t latch
The latch protecting the adaptive search part: this latch protects the (1) positions of records on th...
Definition: btr0sea.h:105
void initialize(size_t hash_size)
Definition: btr0sea.cc:209
The hash index system.
Definition: btr0sea.h:93
btr_search_sys_t(size_t hash_size)
Definition: btr0sea.cc:195
ut::unique_ptr_aligned< search_part_t[]> parts
Partitions of the AHI system.
Definition: btr0sea.h:119
Definition: hash0hash.h:375
Page identifier.
Definition: buf0types.h:207
Page size descriptor.
Definition: page0size.h:50
Data dictionary system.
The hash table with external chains.
Mini-transaction buffer.
static PFS_engine_table_share_proxy table
Definition: pfs.cc:61
mode
Definition: file_handle.h:61
constexpr size_t INNODB_CACHE_LINE_SIZE
CPU cache line size.
Definition: ut0cpu_cache.h:41
std::conditional_t< !std::is_array< T >::value, std::unique_ptr< T, detail::Aligned_deleter< T > >, std::conditional_t< detail::is_unbounded_array_v< T >, std::unique_ptr< T, detail::Aligned_array_deleter< std::remove_extent_t< T > > >, void > > unique_ptr_aligned
The following is a common type that is returned by all the ut::make_unique_aligned (non-aligned) spec...
Definition: ut0new.h:2573
Record manager.
The tree cursor: the definition appears here only for the compiler to know struct size!
Definition: btr0cur.h:668
The search info struct in an index.
Definition: btr0sea.h:46
std::atomic< btr_search_prefix_info_t > prefix_info
Definition: btr0sea.h:69
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:63
ulint magic_n
magic number
Definition: btr0sea.h:70
std::atomic< uint64_t > hash_analysis
when this exceeds BTR_SEARCH_HASH_ANALYSIS, the hash analysis starts; this is reset if no success not...
Definition: btr0sea.h:59
buf_block_t * root_guess
the root page frame when it was last time fetched, or NULL.
Definition: btr0sea.h:56
std::atomic< uint64_t > n_hash_potential
number of consecutive searches which would have succeeded, or did succeed, using the hash index; the ...
Definition: btr0sea.h:66
std::atomic< size_t > ref_count
Number of blocks in this index tree that have search index built i.e.
Definition: btr0sea.h:49
The buffer control block structure.
Definition: buf0buf.h:1747
Data structure for an index.
Definition: dict0mem.h:1046
Data structure for a database table.
Definition: dict0mem.h:1909
Structure for an SQL data tuple of fields (logical record)
Definition: data0data.h:694
The info structure stored at the beginning of a heap block.
Definition: mem0mem.h:302
Mini-transaction handle and buffer.
Definition: mtr0mtr.h:177
The structure used in the spin lock implementation of a read-write lock.
Definition: sync0rw.h:363
Definition: ut0core.h:36
Version control for database, common definitions, and include files.
unsigned long int ulint
Definition: univ.i:406