1 /*****************************************************************************
2
3 Copyright (c) 1996, 2016, Oracle and/or its affiliates. All Rights Reserved.
4 Copyright (c) 2017, 2020, MariaDB Corporation.
5
6 This program is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free Software
8 Foundation; version 2 of the License.
9
10 This program is distributed in the hope that it will be useful, but WITHOUT
11 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along with
15 this program; if not, write to the Free Software Foundation, Inc.,
16 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA
17
18 *****************************************************************************/
19
20 /********************************************************************//**
21 @file include/btr0sea.h
22 The index tree adaptive search
23
24 Created 2/17/1996 Heikki Tuuri
25 *************************************************************************/
26
27 #ifndef btr0sea_h
28 #define btr0sea_h
29
30 #include "dict0dict.h"
31 #ifdef BTR_CUR_HASH_ADAPT
32 #include "ha0ha.h"
33 #include "sync0sync.h"
34
35 #define btr_search_sys_create() btr_search_sys.create()
36 #define btr_search_sys_free() btr_search_sys.free()
37
38 /** Disable the adaptive hash search system and empty the index. */
39 void btr_search_disable();
40
41 /** Enable the adaptive hash search system.
42 @param resize whether buf_pool_t::resize() is the caller */
43 void btr_search_enable(bool resize= false);
44
45 /*********************************************************************//**
46 Updates the search info. */
47 UNIV_INLINE
48 void
49 btr_search_info_update(
50 /*===================*/
51 dict_index_t* index, /*!< in: index of the cursor */
52 btr_cur_t* cursor);/*!< in: cursor which was just positioned */
53
54 /** Tries to guess the right search position based on the hash search info
55 of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts,
56 and the function returns TRUE, then cursor->up_match and cursor->low_match
57 both have sensible values.
58 @param[in,out] index index
59 @param[in,out] info index search info
60 @param[in] tuple logical record
61 @param[in] mode PAGE_CUR_L, ....
62 @param[in] latch_mode BTR_SEARCH_LEAF, ...;
63 NOTE that only if has_search_latch is 0, we will
64 have a latch set on the cursor page, otherwise
65 we assume the caller uses his search latch
66 to protect the record!
67 @param[out] cursor tree cursor
68 @param[in] ahi_latch the adaptive hash index latch being held,
69 or NULL
70 @param[in] mtr mini transaction
71 @return whether the search succeeded */
72 bool
73 btr_search_guess_on_hash(
74 dict_index_t* index,
75 btr_search_t* info,
76 const dtuple_t* tuple,
77 ulint mode,
78 ulint latch_mode,
79 btr_cur_t* cursor,
80 rw_lock_t* ahi_latch,
81 mtr_t* mtr);
82
83 /** Move or delete hash entries for moved records, usually in a page split.
84 If new_block is already hashed, then any hash index for block is dropped.
85 If new_block is not hashed, and block is hashed, then a new hash index is
86 built to new_block with the same parameters as block.
87 @param[in,out] new_block destination page
88 @param[in,out] block source page (subject to deletion later) */
89 void
90 btr_search_move_or_delete_hash_entries(
91 buf_block_t* new_block,
92 buf_block_t* block);
93
94 /** Drop any adaptive hash index entries that point to an index page.
95 @param[in,out] block block containing index page, s- or x-latched, or an
96 index page for which we know that
97 block->buf_fix_count == 0 or it is an index page which
98 has already been removed from the buf_pool.page_hash
99 i.e.: it is in state BUF_BLOCK_REMOVE_HASH */
100 void btr_search_drop_page_hash_index(buf_block_t* block);
101
102 /** Drop possible adaptive hash index entries when a page is evicted
103 from the buffer pool or freed in a file, or the index is being dropped.
104 @param[in] page_id page id */
105 void btr_search_drop_page_hash_when_freed(const page_id_t page_id);
106
107 /** Updates the page hash index when a single record is inserted on a page.
108 @param[in] cursor cursor which was positioned to the place to insert
109 using btr_cur_search_, and the new record has been
110 inserted next to the cursor.
111 @param[in] ahi_latch the adaptive hash index latch */
112 void
113 btr_search_update_hash_node_on_insert(btr_cur_t* cursor, rw_lock_t* ahi_latch);
114
115 /** Updates the page hash index when a single record is inserted on a page.
116 @param[in,out] cursor cursor which was positioned to the
117 place to insert using btr_cur_search_...,
118 and the new record has been inserted next
119 to the cursor
120 @param[in] ahi_latch the adaptive hash index latch */
121 void
122 btr_search_update_hash_on_insert(btr_cur_t* cursor, rw_lock_t* ahi_latch);
123
124 /** Updates the page hash index when a single record is deleted from a page.
125 @param[in] cursor cursor which was positioned on the record to delete
126 using btr_cur_search_, the record is not yet deleted.*/
127 void btr_search_update_hash_on_delete(btr_cur_t* cursor);
128
129 /** Validates the search system.
130 @return true if ok */
131 bool btr_search_validate();
132
133 /** Lock all search latches in exclusive mode. */
134 static inline void btr_search_x_lock_all();
135
136 /** Unlock all search latches from exclusive mode. */
137 static inline void btr_search_x_unlock_all();
138
139 /** Lock all search latches in shared mode. */
140 static inline void btr_search_s_lock_all();
141
142 #ifdef UNIV_DEBUG
143 /** Check if thread owns all the search latches.
144 @param[in] mode lock mode check
145 @retval true if owns all of them
146 @retval false if does not own some of them */
147 static inline bool btr_search_own_all(ulint mode);
148
149 /** Check if thread owns any of the search latches.
150 @param[in] mode lock mode check
151 @retval true if owns any of them
152 @retval false if owns no search latch */
153 static inline bool btr_search_own_any(ulint mode);
154
155 /** @return whether this thread holds any of the search latches */
156 static inline bool btr_search_own_any();
157 #endif /* UNIV_DEBUG */
158
159 /** Unlock all search latches from shared mode. */
160 static inline void btr_search_s_unlock_all();
161
162 #else /* BTR_CUR_HASH_ADAPT */
163 # define btr_search_sys_create()
164 # define btr_search_sys_free()
165 # define btr_search_drop_page_hash_index(block)
166 # define btr_search_s_lock_all(index)
167 # define btr_search_s_unlock_all(index)
168 # define btr_search_info_update(index, cursor)
169 # define btr_search_move_or_delete_hash_entries(new_block, block)
170 # define btr_search_update_hash_on_insert(cursor, ahi_latch)
171 # define btr_search_update_hash_on_delete(cursor)
172 #endif /* BTR_CUR_HASH_ADAPT */
173
174 #ifdef BTR_CUR_ADAPT
175 /** Create and initialize search info.
176 @param[in,out] heap heap where created
177 @return own: search info struct */
178 static inline btr_search_t* btr_search_info_create(mem_heap_t* heap)
179 MY_ATTRIBUTE((nonnull, warn_unused_result));
180
181 /** @return the search info of an index */
btr_search_get_info(dict_index_t * index)182 static inline btr_search_t* btr_search_get_info(dict_index_t* index)
183 {
184 return(index->search_info);
185 }
186 #endif /* BTR_CUR_ADAPT */
187
188 /** The search info struct in an index */
189 struct btr_search_t{
190 /* @{ The following fields are not protected by any latch.
191 Unfortunately, this means that they must be aligned to
192 the machine word, i.e., they cannot be turned into bit-fields. */
193 buf_block_t* root_guess;/*!< the root page frame when it was last time
194 fetched, or NULL */
195 #ifdef BTR_CUR_HASH_ADAPT
196 ulint hash_analysis; /*!< when this exceeds
197 BTR_SEARCH_HASH_ANALYSIS, the hash
198 analysis starts; this is reset if no
199 success noticed */
200 ibool last_hash_succ; /*!< TRUE if the last search would have
201 succeeded, or did succeed, using the hash
202 index; NOTE that the value here is not exact:
203 it is not calculated for every search, and the
204 calculation itself is not always accurate! */
205 ulint n_hash_potential;
206 /*!< number of consecutive searches
207 which would have succeeded, or did succeed,
208 using the hash index;
209 the range is 0 .. BTR_SEARCH_BUILD_LIMIT + 5 */
210 /* @} */
211 ulint ref_count; /*!< Number of blocks in this index tree
212 that have search index built
213 i.e. block->index points to this index.
214 Protected by search latch except
215 when during initialization in
216 btr_search_info_create(). */
217
218 /*---------------------- @{ */
219 uint16_t n_fields; /*!< recommended prefix length for hash search:
220 number of full fields */
221 uint16_t n_bytes; /*!< recommended prefix: number of bytes in
222 an incomplete field
223 @see BTR_PAGE_MAX_REC_SIZE */
224 bool left_side; /*!< true or false, depending on whether
225 the leftmost record of several records with
226 the same prefix should be indexed in the
227 hash index */
228 /*---------------------- @} */
229 #ifdef UNIV_SEARCH_PERF_STAT
230 ulint n_hash_succ; /*!< number of successful hash searches thus
231 far */
232 ulint n_hash_fail; /*!< number of failed hash searches */
233 ulint n_patt_succ; /*!< number of successful pattern searches thus
234 far */
235 ulint n_searches; /*!< number of searches */
236 #endif /* UNIV_SEARCH_PERF_STAT */
237 #endif /* BTR_CUR_HASH_ADAPT */
238 #ifdef UNIV_DEBUG
239 ulint magic_n; /*!< magic number @see BTR_SEARCH_MAGIC_N */
240 /** value of btr_search_t::magic_n, used in assertions */
241 # define BTR_SEARCH_MAGIC_N 1112765
242 #endif /* UNIV_DEBUG */
243 };
244
245 #ifdef BTR_CUR_HASH_ADAPT
246 /** The hash index system */
247 struct btr_search_sys_t
248 {
249 /** Partition of the hash table */
250 struct partition
251 {
252 /** latches protecting hash_table */
253 rw_lock_t latch;
254 /** mapping of dtuple_fold() to rec_t* in buf_block_t::frame */
255 hash_table_t table;
256 /** memory heap for table */
257 mem_heap_t *heap;
258
259 char pad[(CPU_LEVEL1_DCACHE_LINESIZE - sizeof(rw_lock_t) -
260 sizeof(hash_table_t) - sizeof(mem_heap_t)) &
261 (CPU_LEVEL1_DCACHE_LINESIZE - 1)];
262
initbtr_search_sys_t::partition263 void init()
264 {
265 memset((void*) this, 0, sizeof *this);
266 rw_lock_create(btr_search_latch_key, &latch, SYNC_SEARCH_SYS);
267 }
268
allocbtr_search_sys_t::partition269 void alloc(ulint hash_size)
270 {
271 table.create(hash_size);
272 heap= mem_heap_create_typed(std::min<ulong>(4096,
273 MEM_MAX_ALLOC_IN_BUF / 2
274 - MEM_BLOCK_HEADER_SIZE
275 - MEM_SPACE_NEEDED(0)),
276 MEM_HEAP_FOR_BTR_SEARCH);
277 }
278
clearbtr_search_sys_t::partition279 void clear()
280 {
281 mem_heap_free(heap);
282 heap= nullptr;
283 ut_free(table.array);
284 }
285
freebtr_search_sys_t::partition286 void free()
287 {
288 rw_lock_free(&latch);
289 if (heap)
290 clear();
291 }
292 };
293
294 /** Partitions of the adaptive hash index */
295 partition *parts;
296
297 /** Get an adaptive hash index partition */
get_partbtr_search_sys_t298 partition *get_part(index_id_t id, ulint space_id) const
299 {
300 return parts + ut_fold_ulint_pair(ulint(id), space_id) % btr_ahi_parts;
301 }
302
303 /** Get an adaptive hash index partition */
get_partbtr_search_sys_t304 partition *get_part(const dict_index_t &index) const
305 {
306 ut_ad(!index.table->space ||
307 index.table->space->id == index.table->space_id);
308 return get_part(ulint(index.id), index.table->space_id);
309 }
310
311 /** Get the search latch for the adaptive hash index partition */
get_latchbtr_search_sys_t312 rw_lock_t *get_latch(const dict_index_t &index) const
313 { return &get_part(index)->latch; }
314
315 /** Create and initialize at startup */
createbtr_search_sys_t316 void create()
317 {
318 parts= static_cast<partition*>(ut_malloc(btr_ahi_parts * sizeof *parts,
319 mem_key_ahi));
320 for (ulong i= 0; i < btr_ahi_parts; ++i)
321 parts[i].init();
322 if (btr_search_enabled)
323 btr_search_enable();
324 }
325
allocbtr_search_sys_t326 void alloc(ulint hash_size)
327 {
328 hash_size/= btr_ahi_parts;
329 for (ulong i= 0; i < btr_ahi_parts; ++i)
330 parts[i].alloc(hash_size);
331 }
332
333 /** Clear when disabling the adaptive hash index */
clearbtr_search_sys_t334 void clear() { for (ulong i= 0; i < btr_ahi_parts; ++i) parts[i].clear(); }
335
336 /** Free at shutdown */
freebtr_search_sys_t337 void free()
338 {
339 if (parts)
340 {
341 for (ulong i= 0; i < btr_ahi_parts; ++i)
342 parts[i].free();
343 ut_free(parts);
344 parts= nullptr;
345 }
346 }
347 };
348
349 /** The adaptive hash index */
350 extern btr_search_sys_t btr_search_sys;
351
352 /** @return number of leaf pages pointed to by the adaptive hash index */
n_ahi_pages()353 inline ulint dict_index_t::n_ahi_pages() const
354 {
355 if (!btr_search_enabled)
356 return 0;
357 rw_lock_t *latch = &btr_search_sys.get_part(*this)->latch;
358 rw_lock_s_lock(latch);
359 ulint ref_count= search_info->ref_count;
360 rw_lock_s_unlock(latch);
361 return ref_count;
362 }
363
364 #ifdef UNIV_SEARCH_PERF_STAT
365 /** Number of successful adaptive hash index lookups */
366 extern ulint btr_search_n_succ;
367 /** Number of failed adaptive hash index lookups */
368 extern ulint btr_search_n_hash_fail;
369 #endif /* UNIV_SEARCH_PERF_STAT */
370
371 /** After change in n_fields or n_bytes in info, this many rounds are waited
372 before starting the hash analysis again: this is to save CPU time when there
373 is no hope in building a hash index. */
374 #define BTR_SEARCH_HASH_ANALYSIS 17
375
376 /** Limit of consecutive searches for trying a search shortcut on the search
377 pattern */
378 #define BTR_SEARCH_ON_PATTERN_LIMIT 3
379
380 /** Limit of consecutive searches for trying a search shortcut using
381 the hash index */
382 #define BTR_SEARCH_ON_HASH_LIMIT 3
383
384 /** We do this many searches before trying to keep the search latch
385 over calls from MySQL. If we notice someone waiting for the latch, we
386 again set this much timeout. This is to reduce contention. */
387 #define BTR_SEA_TIMEOUT 10000
388 #endif /* BTR_CUR_HASH_ADAPT */
389
390 #include "btr0sea.inl"
391
392 #endif
393