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
34 /** Creates and initializes the adaptive search system at a database start.
35 @param[in] hash_size hash table size. */
36 void btr_search_sys_create(ulint hash_size);
37
38 /** Frees the adaptive search system at a database shutdown. */
39 void btr_search_sys_free();
40
41 /** Disable the adaptive hash search system and empty the index. */
42 void btr_search_disable();
43
44 /** Enable the adaptive hash search system.
45 @param resize whether buf_pool_resize() is the caller */
46 void btr_search_enable(bool resize= false);
47
48 /*********************************************************************//**
49 Updates the search info. */
50 UNIV_INLINE
51 void
52 btr_search_info_update(
53 /*===================*/
54 dict_index_t* index, /*!< in: index of the cursor */
55 btr_cur_t* cursor);/*!< in: cursor which was just positioned */
56
57 /** Tries to guess the right search position based on the hash search info
58 of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts,
59 and the function returns TRUE, then cursor->up_match and cursor->low_match
60 both have sensible values.
61 @param[in,out] index index
62 @param[in,out] info index search info
63 @param[in] tuple logical record
64 @param[in] mode PAGE_CUR_L, ....
65 @param[in] latch_mode BTR_SEARCH_LEAF, ...;
66 NOTE that only if has_search_latch is 0, we will
67 have a latch set on the cursor page, otherwise
68 we assume the caller uses his search latch
69 to protect the record!
70 @param[out] cursor tree cursor
71 @param[in] ahi_latch the adaptive hash index latch being held,
72 or NULL
73 @param[in] mtr mini transaction
74 @return whether the search succeeded */
75 bool
76 btr_search_guess_on_hash(
77 dict_index_t* index,
78 btr_search_t* info,
79 const dtuple_t* tuple,
80 ulint mode,
81 ulint latch_mode,
82 btr_cur_t* cursor,
83 rw_lock_t* ahi_latch,
84 mtr_t* mtr);
85
86 /** Move or delete hash entries for moved records, usually in a page split.
87 If new_block is already hashed, then any hash index for block is dropped.
88 If new_block is not hashed, and block is hashed, then a new hash index is
89 built to new_block with the same parameters as block.
90 @param[in,out] new_block destination page
91 @param[in,out] block source page (subject to deletion later) */
92 void
93 btr_search_move_or_delete_hash_entries(
94 buf_block_t* new_block,
95 buf_block_t* block);
96
97 /** Drop any adaptive hash index entries that point to an index page.
98 @param[in,out] block block containing index page, s- or x-latched, or an
99 index page for which we know that
100 block->buf_fix_count == 0 or it is an index page which
101 has already been removed from the buf_pool->page_hash
102 i.e.: it is in state BUF_BLOCK_REMOVE_HASH */
103 void btr_search_drop_page_hash_index(buf_block_t* block);
104
105 /** Drop possible adaptive hash index entries when a page is evicted
106 from the buffer pool or freed in a file, or the index is being dropped.
107 @param[in] page_id page id */
108 void btr_search_drop_page_hash_when_freed(const page_id_t page_id);
109
110 /** Updates the page hash index when a single record is inserted on a page.
111 @param[in] cursor cursor which was positioned to the place to insert
112 using btr_cur_search_, and the new record has been
113 inserted next to the cursor.
114 @param[in] ahi_latch the adaptive hash index latch */
115 void
116 btr_search_update_hash_node_on_insert(btr_cur_t* cursor, rw_lock_t* ahi_latch);
117
118 /** Updates the page hash index when a single record is inserted on a page.
119 @param[in,out] cursor cursor which was positioned to the
120 place to insert using btr_cur_search_...,
121 and the new record has been inserted next
122 to the cursor
123 @param[in] ahi_latch the adaptive hash index latch */
124 void
125 btr_search_update_hash_on_insert(btr_cur_t* cursor, rw_lock_t* ahi_latch);
126
127 /** Updates the page hash index when a single record is deleted from a page.
128 @param[in] cursor cursor which was positioned on the record to delete
129 using btr_cur_search_, the record is not yet deleted.*/
130 void btr_search_update_hash_on_delete(btr_cur_t* cursor);
131
132 /** Validates the search system.
133 @return true if ok */
134 bool btr_search_validate();
135
136 /** Lock all search latches in exclusive mode. */
137 static inline void btr_search_x_lock_all();
138
139 /** Unlock all search latches from exclusive mode. */
140 static inline void btr_search_x_unlock_all();
141
142 /** Lock all search latches in shared mode. */
143 static inline void btr_search_s_lock_all();
144
145 #ifdef UNIV_DEBUG
146 /** Check if thread owns all the search latches.
147 @param[in] mode lock mode check
148 @retval true if owns all of them
149 @retval false if does not own some of them */
150 static inline bool btr_search_own_all(ulint mode);
151
152 /** Check if thread owns any of the search latches.
153 @param[in] mode lock mode check
154 @retval true if owns any of them
155 @retval false if owns no search latch */
156 static inline bool btr_search_own_any(ulint mode);
157
158 /** @return whether this thread holds any of the search latches */
159 static inline bool btr_search_own_any();
160 #endif /* UNIV_DEBUG */
161
162 /** Unlock all search latches from shared mode. */
163 static inline void btr_search_s_unlock_all();
164
165 /** Get the latch based on index attributes.
166 A latch is selected from an array of latches using pair of index-id, space-id.
167 @param[in] index index handler
168 @return latch */
169 static inline rw_lock_t* btr_get_search_latch(const dict_index_t* index);
170
171 /** Get the hash-table based on index attributes.
172 A table is selected from an array of tables using pair of index-id, space-id.
173 @param[in] index index handler
174 @return hash table */
175 static inline hash_table_t* btr_get_search_table(const dict_index_t* index);
176 #else /* BTR_CUR_HASH_ADAPT */
177 # define btr_search_sys_create(size)
178 # define btr_search_sys_free()
179 # define btr_search_drop_page_hash_index(block)
180 # define btr_search_s_lock_all(index)
181 # define btr_search_s_unlock_all(index)
182 # define btr_search_info_update(index, cursor)
183 # define btr_search_move_or_delete_hash_entries(new_block, block)
184 # define btr_search_update_hash_on_insert(cursor, ahi_latch)
185 # define btr_search_update_hash_on_delete(cursor)
186 #endif /* BTR_CUR_HASH_ADAPT */
187
188 #ifdef BTR_CUR_ADAPT
189 /** Create and initialize search info.
190 @param[in,out] heap heap where created
191 @return own: search info struct */
192 static inline btr_search_t* btr_search_info_create(mem_heap_t* heap)
193 MY_ATTRIBUTE((nonnull, warn_unused_result));
194
195 /** @return the search info of an index */
btr_search_get_info(dict_index_t * index)196 static inline btr_search_t* btr_search_get_info(dict_index_t* index)
197 {
198 return(index->search_info);
199 }
200 #endif /* BTR_CUR_ADAPT */
201
202 /** The search info struct in an index */
203 struct btr_search_t{
204 /* @{ The following fields are not protected by any latch.
205 Unfortunately, this means that they must be aligned to
206 the machine word, i.e., they cannot be turned into bit-fields. */
207 buf_block_t* root_guess;/*!< the root page frame when it was last time
208 fetched, or NULL */
209 #ifdef BTR_CUR_HASH_ADAPT
210 ulint hash_analysis; /*!< when this exceeds
211 BTR_SEARCH_HASH_ANALYSIS, the hash
212 analysis starts; this is reset if no
213 success noticed */
214 ibool last_hash_succ; /*!< TRUE if the last search would have
215 succeeded, or did succeed, using the hash
216 index; NOTE that the value here is not exact:
217 it is not calculated for every search, and the
218 calculation itself is not always accurate! */
219 ulint n_hash_potential;
220 /*!< number of consecutive searches
221 which would have succeeded, or did succeed,
222 using the hash index;
223 the range is 0 .. BTR_SEARCH_BUILD_LIMIT + 5 */
224 /* @} */
225 ulint ref_count; /*!< Number of blocks in this index tree
226 that have search index built
227 i.e. block->index points to this index.
228 Protected by search latch except
229 when during initialization in
230 btr_search_info_create(). */
231
232 /*---------------------- @{ */
233 ulint n_fields; /*!< recommended prefix length for hash search:
234 number of full fields */
235 ulint n_bytes; /*!< recommended prefix: number of bytes in
236 an incomplete field
237 @see BTR_PAGE_MAX_REC_SIZE */
238 bool left_side; /*!< true or false, depending on whether
239 the leftmost record of several records with
240 the same prefix should be indexed in the
241 hash index */
242 /*---------------------- @} */
243 #ifdef UNIV_SEARCH_PERF_STAT
244 ulint n_hash_succ; /*!< number of successful hash searches thus
245 far */
246 ulint n_hash_fail; /*!< number of failed hash searches */
247 ulint n_patt_succ; /*!< number of successful pattern searches thus
248 far */
249 ulint n_searches; /*!< number of searches */
250 #endif /* UNIV_SEARCH_PERF_STAT */
251 #endif /* BTR_CUR_HASH_ADAPT */
252 #ifdef UNIV_DEBUG
253 ulint magic_n; /*!< magic number @see BTR_SEARCH_MAGIC_N */
254 /** value of btr_search_t::magic_n, used in assertions */
255 # define BTR_SEARCH_MAGIC_N 1112765
256 #endif /* UNIV_DEBUG */
257 };
258
259 #ifdef BTR_CUR_HASH_ADAPT
260 /** @return number of leaf pages pointed to by the adaptive hash index */
n_ahi_pages()261 inline ulint dict_index_t::n_ahi_pages() const
262 {
263 if (!btr_search_enabled)
264 return 0;
265 rw_lock_t *latch = btr_get_search_latch(this);
266 rw_lock_s_lock(latch);
267 ulint ref_count= search_info->ref_count;
268 rw_lock_s_unlock(latch);
269 return ref_count;
270 }
271
272 /** The hash index system */
273 struct btr_search_sys_t{
274 hash_table_t** hash_tables; /*!< the adaptive hash tables,
275 mapping dtuple_fold values
276 to rec_t pointers on index pages */
277 };
278
279 /** Latches protecting access to adaptive hash index. */
280 extern rw_lock_t** btr_search_latches;
281
282 /** The adaptive hash index */
283 extern btr_search_sys_t* btr_search_sys;
284
285 #ifdef UNIV_SEARCH_PERF_STAT
286 /** Number of successful adaptive hash index lookups */
287 extern ulint btr_search_n_succ;
288 /** Number of failed adaptive hash index lookups */
289 extern ulint btr_search_n_hash_fail;
290 #endif /* UNIV_SEARCH_PERF_STAT */
291
292 /** After change in n_fields or n_bytes in info, this many rounds are waited
293 before starting the hash analysis again: this is to save CPU time when there
294 is no hope in building a hash index. */
295 #define BTR_SEARCH_HASH_ANALYSIS 17
296
297 /** Limit of consecutive searches for trying a search shortcut on the search
298 pattern */
299 #define BTR_SEARCH_ON_PATTERN_LIMIT 3
300
301 /** Limit of consecutive searches for trying a search shortcut using
302 the hash index */
303 #define BTR_SEARCH_ON_HASH_LIMIT 3
304
305 /** We do this many searches before trying to keep the search latch
306 over calls from MySQL. If we notice someone waiting for the latch, we
307 again set this much timeout. This is to reduce contention. */
308 #define BTR_SEA_TIMEOUT 10000
309 #endif /* BTR_CUR_HASH_ADAPT */
310
311 #include "btr0sea.inl"
312
313 #endif
314