MySQL  8.0.20
Source Code Documentation
btr0sea.h
Go to the documentation of this file.
1 /*****************************************************************************
2 
3 Copyright (c) 1996, 2018, Oracle and/or its affiliates. All Rights Reserved.
4 
5 This program is free software; you can redistribute it and/or modify it under
6 the terms of the GNU General Public License, version 2.0, as published by the
7 Free Software Foundation.
8 
9 This program is also distributed with certain software (including but not
10 limited to OpenSSL) that is licensed under separate terms, as designated in a
11 particular file or component or in included license documentation. The authors
12 of MySQL hereby grant you an additional permission to link the program and
13 your derivative works with the separately licensed software that they have
14 included with MySQL.
15 
16 This program is distributed in the hope that it will be useful, but WITHOUT
17 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18 FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
19 for more details.
20 
21 You should have received a copy of the GNU General Public License along with
22 this program; if not, write to the Free Software Foundation, Inc.,
23 51 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. */
46 void btr_search_sys_create(ulint hash_size);
47 
48 /** Resize hash index hash table.
49 @param[in] hash_size hash index hash table size */
50 void btr_search_sys_resize(ulint hash_size);
51 
52 /** Frees the adaptive search system at a database shutdown. */
53 void btr_search_sys_free();
54 
55 /** Disable the adaptive hash search system and empty the index.
56 @param need_mutex need to acquire dict_sys->mutex */
57 void btr_search_disable(bool need_mutex);
58 /** Enable the adaptive hash search system. */
59 void btr_search_enable();
60 
61 /** Returns search info for an index.
62  @return search info; search mutex reserved */
63 UNIV_INLINE
64 btr_search_t *btr_search_get_info(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. The value is protected by latch.
72 @param[in] info search info
73 @param[in] index index identifier
74 @return ref_count value. */
76  const dict_index_t *index);
77 
78 /** Updates the search info.
79 @param[in] index index of the cursor
80 @param[in] cursor cursor which was just positioned */
81 UNIV_INLINE
82 void btr_search_info_update(dict_index_t *index, btr_cur_t *cursor);
83 
84 /** Tries to guess the right search position based on the hash search info
85 of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts,
86 and the function returns TRUE, then cursor->up_match and cursor->low_match
87 both have sensible values.
88 @param[in,out] index index
89 @param[in,out] info index search info
90 @param[in] tuple logical record
91 @param[in] mode PAGE_CUR_L, ....
92 @param[in] latch_mode BTR_SEARCH_LEAF, ...;
93  NOTE that only if has_search_latch is 0, we will
94  have a latch set on the cursor page, otherwise
95  we assume the caller uses his search latch
96  to protect the record!
97 @param[out] cursor tree cursor
98 @param[in] has_search_latch
99  latch mode the caller currently has on
100  search system: RW_S/X_LATCH or 0
101 @param[in] mtr mini transaction
102 @return true if succeeded */
104  const dtuple_t *tuple, ulint mode,
105  ulint latch_mode, btr_cur_t *cursor,
106  ulint has_search_latch, mtr_t *mtr);
107 
108 /** Moves or deletes hash entries for moved records. If new_page is already
109 hashed, then the hash index for page, if any, is dropped. If new_page is not
110 hashed, and page is hashed, then a new hash index is built to new_page with the
111 same parameters as page (this often happens when a page is split).
112 @param[in,out] new_block records are copied to this page.
113 @param[in,out] block index page from which record are copied, and the
114  copied records will be deleted from this page.
115 @param[in,out] index record descriptor */
117  buf_block_t *block,
118  dict_index_t *index);
119 
120 /** Drop any adaptive hash index entries that point to an index page.
121 @param[in,out] block block containing index page, s- or x-latched, or an
122  index page for which we know that
123  block->buf_fix_count == 0 or it is an index page which
124  has already been removed from the buf_pool->page_hash
125  i.e.: it is in state BUF_BLOCK_REMOVE_HASH */
127 
128 /** Drop any adaptive hash index entries that may point to an index
129 page that may be in the buffer pool, when a page is evicted from the
130 buffer pool or freed in a file segment.
131 @param[in] page_id page id
132 @param[in] page_size page size */
134  const page_size_t &page_size);
135 
136 /** Drop any adaptive hash index entries for a table.
137 @param[in,out] table to drop indexes of this table */
139 
140 /** Drop any adaptive hash index entries for a index.
141 @param[in,out] index to drop hash indexes for this index */
143 
144 /** Updates the page hash index when a single record is inserted on a page.
145 @param[in] cursor cursor which was positioned to the place to insert
146  using btr_cur_search_, and the new record has been
147  inserted next to the cursor. */
149 
150 /** Updates the page hash index when a single record is inserted on a page.
151 @param[in] cursor cursor which was positioned to the
152  place to insert using btr_cur_search_...,
153  and the new record has been inserted next
154  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
159  using btr_cur_search_, the record is not yet deleted.*/
161 
162 /** Validates the search system.
163 @return true if ok */
164 bool btr_search_validate();
165 
166 /** X-Lock the search latch (corresponding to given index)
167 @param[in] index index handler */
168 UNIV_INLINE
169 void btr_search_x_lock(const dict_index_t *index);
170 
171 /** X-Unlock the search latch (corresponding to given index)
172 @param[in] index index handler */
173 UNIV_INLINE
174 void btr_search_x_unlock(const dict_index_t *index);
175 
176 /** Lock all search latches in exclusive mode. */
177 UNIV_INLINE
178 void btr_search_x_lock_all();
179 
180 /** Unlock all search latches from exclusive mode. */
181 UNIV_INLINE
183 
184 /** S-Lock the search latch (corresponding to given index)
185 @param[in] index index handler */
186 UNIV_INLINE
187 void btr_search_s_lock(const dict_index_t *index);
188 
189 /** S-Unlock the search latch (corresponding to given index)
190 @param[in] index index handler */
191 UNIV_INLINE
192 void btr_search_s_unlock(const dict_index_t *index);
193 
194 /** Lock all search latches in shared mode. */
195 UNIV_INLINE
196 void btr_search_s_lock_all();
197 
198 #ifdef UNIV_DEBUG
199 /** Check if thread owns all the search latches.
200 @param[in] mode lock mode check
201 @retval true if owns all of them
202 @retval false if does not own some of them */
203 UNIV_INLINE
204 bool btr_search_own_all(ulint mode);
205 
206 /** Check if thread owns any of the search latches.
207 @param[in] mode lock mode check
208 @retval true if owns any of them
209 @retval false if owns no search latch */
210 UNIV_INLINE
211 bool btr_search_own_any(ulint mode);
212 #endif /* UNIV_DEBUG */
213 
214 /** Unlock all search latches from shared mode. */
215 UNIV_INLINE
217 
218 /** Get the latch based on index attributes.
219 A latch is selected from an array of latches using pair of index-id, space-id.
220 @param[in] index index handler
221 @return latch */
222 UNIV_INLINE
224 
225 /** Get the hash-table based on index attributes.
226 A table is selected from an array of tables using pair of index-id, space-id.
227 @param[in] index index handler
228 @return hash table */
229 UNIV_INLINE
231 
232 /** The search info struct in an index */
233 struct btr_search_t {
234  ulint ref_count; /*!< Number of blocks in this index tree
235  that have search index built
236  i.e. block->index points to this index.
237  Protected by search latch except
238  when during initialization in
239  btr_search_info_create(). */
240 
241  /* @{ The following fields are not protected by any latch.
242  Unfortunately, this means that they must be aligned to
243  the machine word, i.e., they cannot be turned into bit-fields. */
244  buf_block_t *root_guess; /*!< the root page frame when it was last time
245  fetched, or NULL */
246  ulint withdraw_clock; /*!< the withdraw clock value of the buffer
247  pool when root_guess was stored */
248  ulint hash_analysis; /*!< when this exceeds
249  BTR_SEARCH_HASH_ANALYSIS, the hash
250  analysis starts; this is reset if no
251  success noticed */
252  ibool last_hash_succ; /*!< TRUE if the last search would have
253  succeeded, or did succeed, using the hash
254  index; NOTE that the value here is not exact:
255  it is not calculated for every search, and the
256  calculation itself is not always accurate! */
258  /*!< number of consecutive searches
259  which would have succeeded, or did succeed,
260  using the hash index;
261  the range is 0 .. BTR_SEARCH_BUILD_LIMIT + 5 */
262  /* @} */
263  /*---------------------- @{ */
264  ulint n_fields; /*!< recommended prefix length for hash search:
265  number of full fields */
266  ulint n_bytes; /*!< recommended prefix: number of bytes in
267  an incomplete field
268  @see BTR_PAGE_MAX_REC_SIZE */
269  ibool left_side; /*!< TRUE or FALSE, depending on whether
270  the leftmost record of several records with
271  the same prefix should be indexed in the
272  hash index */
273  /*---------------------- @} */
274 #ifdef UNIV_SEARCH_PERF_STAT
275  ulint n_hash_succ; /*!< number of successful hash searches thus
276  far */
277  ulint n_hash_fail; /*!< number of failed hash searches */
278  ulint n_patt_succ; /*!< number of successful pattern searches thus
279  far */
280  ulint n_searches; /*!< number of searches */
281 #endif /* UNIV_SEARCH_PERF_STAT */
282 #ifdef UNIV_DEBUG
283  ulint magic_n; /*!< magic number @see BTR_SEARCH_MAGIC_N */
284 /** value of btr_search_t::magic_n, used in assertions */
285 #define BTR_SEARCH_MAGIC_N 1112765
286 #endif /* UNIV_DEBUG */
287 };
288 
289 /** The hash index system */
291  hash_table_t **hash_tables; /*!< the adaptive hash tables,
292  mapping dtuple_fold values
293  to rec_t pointers on index pages */
294 };
295 
296 /** Latches protecting access to adaptive hash index. */
298 
299 /** The adaptive hash index */
301 
302 #ifdef UNIV_SEARCH_PERF_STAT
303 /** Number of successful adaptive hash index lookups */
304 extern ulint btr_search_n_succ;
305 /** Number of failed adaptive hash index lookups */
306 extern ulint btr_search_n_hash_fail;
307 #endif /* UNIV_SEARCH_PERF_STAT */
308 
309 /** After change in n_fields or n_bytes in info, this many rounds are waited
310 before starting the hash analysis again: this is to save CPU time when there
311 is no hope in building a hash index. */
312 #define BTR_SEARCH_HASH_ANALYSIS 17
313 
314 /** Limit of consecutive searches for trying a search shortcut on the search
315 pattern */
316 #define BTR_SEARCH_ON_PATTERN_LIMIT 3
317 
318 /** Limit of consecutive searches for trying a search shortcut using
319 the hash index */
320 #define BTR_SEARCH_ON_HASH_LIMIT 3
321 
322 #include "btr0sea.ic"
323 
324 #endif
void btr_drop_ahi_for_index(dict_index_t *index)
Drop any adaptive hash index entries for a index.
Definition: btr0sea.cc:1364
ulint hash_analysis
when this exceeds BTR_SEARCH_HASH_ANALYSIS, the hash analysis starts; this is reset if no success not...
Definition: btr0sea.h:248
ibool left_side
TRUE or FALSE, depending on whether the leftmost record of several records with the same prefix shoul...
Definition: btr0sea.h:269
The structure used in the spin lock implementation of a read-write lock.
Definition: sync0rw.h:556
UNIV_INLINE void btr_search_x_lock(const dict_index_t *index)
X-Lock the search latch (corresponding to given index)
UNIV_INLINE hash_table_t * btr_get_search_table(const dict_index_t *index)
Get the hash-table based on index attributes.
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:1053
void btr_search_sys_resize(ulint hash_size)
Resize hash index hash table.
Definition: btr0sea.cc:225
The buffer control block structure.
Definition: buf0buf.h:1321
Page identifier.
Definition: buf0types.h:153
bool btr_search_validate()
Validates the search system.
Definition: btr0sea.cc:2120
buf_block_t * root_guess
the root page frame when it was last time fetched, or NULL
Definition: btr0sea.h:244
btr_search_sys_t * btr_search_sys
The adaptive hash index.
Definition: btr0sea.cc:87
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:1243
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:1739
Data structure for a database table.
Definition: dict0mem.h:1520
The tree cursor: the definition appears here only for the compiler to know struct size! ...
Definition: btr0cur.h:690
UNIV_INLINE rw_lock_t * btr_get_search_latch(const dict_index_t *index)
Get the latch based on index attributes.
The hash table with external chains.
The search info struct in an index.
Definition: btr0sea.h:233
UNIV_INLINE btr_search_t * btr_search_get_info(dict_index_t *index)
Returns search info for an index.
The info structure stored at the beginning of a heap block.
Definition: mem0mem.h:343
void btr_search_disable(bool need_mutex)
Disable the adaptive hash search system and empty the index.
Definition: btr0sea.cc:301
ulint ref_count
Number of blocks in this index tree that have search index built i.e.
Definition: btr0sea.h:234
ulint n_fields
recommended prefix length for hash search: number of full fields
Definition: btr0sea.h:264
Definition: hash0hash.h:401
The index tree general types.
UNIV_INLINE void btr_search_x_unlock(const dict_index_t *index)
X-Unlock the search latch (corresponding to given index)
UNIV_INLINE bool btr_search_own_all(ulint mode)
Check if thread owns all the search latches.
rw_lock_t ** btr_search_latches
Latches protecting access to adaptive hash index.
Definition: btr0sea.cc:80
Data dictionary system.
UNIV_INLINE void btr_search_s_lock(const dict_index_t *index)
S-Lock the search latch (corresponding to given index)
Structure for an SQL data tuple of fields (logical record)
Definition: data0data.h:711
ulint n_hash_potential
number of consecutive searches which would have succeeded, or did succeed, using the hash index; the ...
Definition: btr0sea.h:257
void btr_drop_ahi_for_table(dict_table_t *table)
Drop any adaptive hash index entries for a table.
Definition: btr0sea.cc:1284
ulint btr_search_info_get_ref_count(const btr_search_t *info, const dict_index_t *index)
Returns the value of ref_count.
Definition: btr0sea.cc:401
UNIV_INLINE void btr_search_x_unlock_all()
Unlock all search latches from exclusive mode.
UNIV_INLINE bool btr_search_own_any(ulint mode)
Check if thread owns any of the search latches.
hash_table_t ** hash_tables
the adaptive hash tables, mapping dtuple_fold values to rec_t pointers on index pages ...
Definition: btr0sea.h:291
UNIV_INLINE void btr_search_s_lock_all()
Lock all search latches in shared mode.
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:1797
ulint magic_n
magic number
Definition: btr0sea.h:283
ulint n_bytes
recommended prefix: number of bytes in an incomplete field
Definition: btr0sea.h:266
UNIV_INLINE void btr_search_info_update(dict_index_t *index, btr_cur_t *cursor)
Updates the search info.
UNIV_INLINE void btr_search_s_unlock(const dict_index_t *index)
S-Unlock the search latch (corresponding to given index)
Page size descriptor.
Definition: page0size.h:49
UNIV_INLINE void btr_search_x_lock_all()
Lock all search latches in exclusive mode.
ibool 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:252
The hash index system.
Definition: btr0sea.h:290
UNIV_INLINE void btr_search_s_unlock_all()
Unlock all search latches from shared mode.
Mini-transaction buffer.
void btr_search_sys_free()
Frees the adaptive search system at a database shutdown.
Definition: btr0sea.cc:257
ibool 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:864
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:1675
Log info(cout, "NOTE")
btr_search_t * btr_search_info_create(mem_heap_t *heap)
Creates and initializes a search info struct.
Definition: btr0sea.cc:365
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:1617
Mini-transaction handle and buffer.
Definition: mtr0mtr.h:169
void btr_search_sys_create(ulint hash_size)
Creates and initializes the adaptive search system at a database start.
Definition: btr0sea.cc:188
void btr_search_enable()
Enable the adaptive hash search system.
Definition: btr0sea.cc:351
ulint withdraw_clock
the withdraw clock value of the buffer pool when root_guess was stored
Definition: btr0sea.h:246
Record manager.
Data structure for an index.
Definition: dict0mem.h:879