1 /***************************************************************************** 2 3 Copyright (c) 1996, 2021, Oracle and/or its affiliates. 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License, version 2.0, 7 as published by the Free Software Foundation. 8 9 This program is also distributed with certain software (including 10 but not limited to OpenSSL) that is licensed under separate terms, 11 as designated in a particular file or component or in included license 12 documentation. The authors of MySQL hereby grant you an additional 13 permission to link the program and your derivative works with the 14 separately licensed software that they have included with MySQL. 15 16 This program is distributed in the hope that it will be useful, 17 but WITHOUT ANY WARRANTY; without even the implied warranty of 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19 GNU General Public License, version 2.0, 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 Street, Suite 500, Boston, MA 02110-1335 USA 24 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 "rem0rec.h" 40 #include "dict0dict.h" 41 #include "btr0types.h" 42 #include "mtr0mtr.h" 43 #include "ha0ha.h" 44 45 /** Creates and initializes the adaptive search system at a database start. 46 @param[in] hash_size hash table size. */ 47 void 48 btr_search_sys_create(ulint hash_size); 49 50 /** Resize hash index hash table. 51 @param[in] hash_size hash index hash table size */ 52 void 53 btr_search_sys_resize(ulint hash_size); 54 55 /** Frees the adaptive search system at a database shutdown. */ 56 void 57 btr_search_sys_free(); 58 59 /** Disable the adaptive hash search system and empty the index. 60 @param need_mutex need to acquire dict_sys->mutex */ 61 void 62 btr_search_disable( 63 bool need_mutex); 64 /** Enable the adaptive hash search system. */ 65 void 66 btr_search_enable(); 67 68 /********************************************************************//** 69 Returns search info for an index. 70 @return search info; search mutex reserved */ 71 UNIV_INLINE 72 btr_search_t* 73 btr_search_get_info( 74 /*================*/ 75 dict_index_t* index) /*!< in: index */ 76 MY_ATTRIBUTE((nonnull)); 77 78 /** Creates and initializes a search info struct. 79 @param[in] heap heap where created. 80 @return own: search info struct */ 81 btr_search_t* 82 btr_search_info_create(mem_heap_t* heap); 83 84 /** Returns the value of ref_count. The value is protected by latch. 85 @param[in] info search info 86 @param[in] index index identifier 87 @return ref_count value. */ 88 ulint 89 btr_search_info_get_ref_count( 90 btr_search_t* info, 91 dict_index_t* index); 92 93 /*********************************************************************//** 94 Updates the search info. */ 95 UNIV_INLINE 96 void 97 btr_search_info_update( 98 /*===================*/ 99 dict_index_t* index, /*!< in: index of the cursor */ 100 btr_cur_t* cursor);/*!< in: cursor which was just positioned */ 101 102 /** Tries to guess the right search position based on the hash search info 103 of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts, 104 and the function returns TRUE, then cursor->up_match and cursor->low_match 105 both have sensible values. 106 @param[in,out] index index 107 @param[in,out] info index search info 108 @param[in] tuple logical record 109 @param[in] mode PAGE_CUR_L, .... 110 @param[in] latch_mode BTR_SEARCH_LEAF, ...; 111 NOTE that only if has_search_latch is 0, we will 112 have a latch set on the cursor page, otherwise 113 we assume the caller uses his search latch 114 to protect the record! 115 @param[out] cursor tree cursor 116 @param[in] has_search_latch 117 latch mode the caller currently has on 118 search system: RW_S/X_LATCH or 0 119 @param[in] mtr mini transaction 120 @return TRUE if succeeded */ 121 ibool 122 btr_search_guess_on_hash( 123 dict_index_t* index, 124 btr_search_t* info, 125 const dtuple_t* tuple, 126 ulint mode, 127 ulint latch_mode, 128 btr_cur_t* cursor, 129 ulint has_search_latch, 130 mtr_t* mtr); 131 132 /** Moves or deletes hash entries for moved records. If new_page is already 133 hashed, then the hash index for page, if any, is dropped. If new_page is not 134 hashed, and page is hashed, then a new hash index is built to new_page with the 135 same parameters as page (this often happens when a page is split). 136 @param[in,out] new_block records are copied to this page. 137 @param[in,out] block index page from which record are copied, and the 138 copied records will be deleted from this page. 139 @param[in,out] index record descriptor */ 140 void 141 btr_search_move_or_delete_hash_entries( 142 buf_block_t* new_block, 143 buf_block_t* block, 144 dict_index_t* index); 145 146 /** Drop any adaptive hash index entries that point to an index page. 147 @param[in,out] block block containing index page, s- or x-latched, or an 148 index page for which we know that 149 block->buf_fix_count == 0 or it is an index page which 150 has already been removed from the buf_pool->page_hash 151 i.e.: it is in state BUF_BLOCK_REMOVE_HASH */ 152 void 153 btr_search_drop_page_hash_index(buf_block_t* block); 154 155 /** Drop any adaptive hash index entries that may point to an index 156 page that may be in the buffer pool, when a page is evicted from the 157 buffer pool or freed in a file segment. 158 @param[in] page_id page id 159 @param[in] page_size page size */ 160 void 161 btr_search_drop_page_hash_when_freed( 162 const page_id_t& page_id, 163 const page_size_t& page_size); 164 165 /** Updates the page hash index when a single record is inserted on a page. 166 @param[in] cursor cursor which was positioned to the place to insert 167 using btr_cur_search_, and the new record has been 168 inserted next to the cursor. */ 169 void 170 btr_search_update_hash_node_on_insert(btr_cur_t* cursor); 171 172 /** Updates the page hash index when a single record is inserted on a page. 173 @param[in] cursor cursor which was positioned to the 174 place to insert using btr_cur_search_..., 175 and the new record has been inserted next 176 to the cursor */ 177 void 178 btr_search_update_hash_on_insert(btr_cur_t* cursor); 179 180 /** Updates the page hash index when a single record is deleted from a page. 181 @param[in] cursor cursor which was positioned on the record to delete 182 using btr_cur_search_, the record is not yet deleted.*/ 183 void 184 btr_search_update_hash_on_delete(btr_cur_t* cursor); 185 186 /** Validates the search system. 187 @return true if ok */ 188 bool 189 btr_search_validate(); 190 191 /** X-Lock the search latch (corresponding to given index) 192 @param[in] index index handler */ 193 UNIV_INLINE 194 void 195 btr_search_x_lock(const dict_index_t* index); 196 197 /** X-Unlock the search latch (corresponding to given index) 198 @param[in] index index handler */ 199 UNIV_INLINE 200 void 201 btr_search_x_unlock(const dict_index_t* index); 202 203 /** Lock all search latches in exclusive mode. */ 204 UNIV_INLINE 205 void 206 btr_search_x_lock_all(); 207 208 /** Unlock all search latches from exclusive mode. */ 209 UNIV_INLINE 210 void 211 btr_search_x_unlock_all(); 212 213 /** S-Lock the search latch (corresponding to given index) 214 @param[in] index index handler */ 215 UNIV_INLINE 216 void 217 btr_search_s_lock(const dict_index_t* index); 218 219 /** S-Unlock the search latch (corresponding to given index) 220 @param[in] index index handler */ 221 UNIV_INLINE 222 void 223 btr_search_s_unlock(const dict_index_t* index); 224 225 /** Lock all search latches in shared mode. */ 226 UNIV_INLINE 227 void 228 btr_search_s_lock_all(); 229 230 #ifdef UNIV_DEBUG 231 /** Check if thread owns all the search latches. 232 @param[in] mode lock mode check 233 @retval true if owns all of them 234 @retval false if does not own some of them */ 235 UNIV_INLINE 236 bool 237 btr_search_own_all(ulint mode); 238 239 /** Check if thread owns any of the search latches. 240 @param[in] mode lock mode check 241 @retval true if owns any of them 242 @retval false if owns no search latch */ 243 UNIV_INLINE 244 bool 245 btr_search_own_any(ulint mode); 246 #endif /* UNIV_DEBUG */ 247 248 /** Unlock all search latches from shared mode. */ 249 UNIV_INLINE 250 void 251 btr_search_s_unlock_all(); 252 253 /** Get the latch based on index attributes. 254 A latch is selected from an array of latches using pair of index-id, space-id. 255 @param[in] index index handler 256 @return latch */ 257 UNIV_INLINE 258 rw_lock_t* 259 btr_get_search_latch(const dict_index_t* index); 260 261 /** Get the hash-table based on index attributes. 262 A table is selected from an array of tables using pair of index-id, space-id. 263 @param[in] index index handler 264 @return hash table */ 265 UNIV_INLINE 266 hash_table_t* 267 btr_get_search_table(const dict_index_t* index); 268 269 /** The search info struct in an index */ 270 struct btr_search_t{ 271 ulint ref_count; /*!< Number of blocks in this index tree 272 that have search index built 273 i.e. block->index points to this index. 274 Protected by search latch except 275 when during initialization in 276 btr_search_info_create(). */ 277 278 /* @{ The following fields are not protected by any latch. 279 Unfortunately, this means that they must be aligned to 280 the machine word, i.e., they cannot be turned into bit-fields. */ 281 buf_block_t* root_guess;/*!< the root page frame when it was last time 282 fetched, or NULL */ 283 ulint hash_analysis; /*!< when this exceeds 284 BTR_SEARCH_HASH_ANALYSIS, the hash 285 analysis starts; this is reset if no 286 success noticed */ 287 ibool last_hash_succ; /*!< TRUE if the last search would have 288 succeeded, or did succeed, using the hash 289 index; NOTE that the value here is not exact: 290 it is not calculated for every search, and the 291 calculation itself is not always accurate! */ 292 ulint n_hash_potential; 293 /*!< number of consecutive searches 294 which would have succeeded, or did succeed, 295 using the hash index; 296 the range is 0 .. BTR_SEARCH_BUILD_LIMIT + 5 */ 297 /* @} */ 298 /*---------------------- @{ */ 299 ulint n_fields; /*!< recommended prefix length for hash search: 300 number of full fields */ 301 ulint n_bytes; /*!< recommended prefix: number of bytes in 302 an incomplete field 303 @see BTR_PAGE_MAX_REC_SIZE */ 304 ibool left_side; /*!< TRUE or FALSE, depending on whether 305 the leftmost record of several records with 306 the same prefix should be indexed in the 307 hash index */ 308 /*---------------------- @} */ 309 #ifdef UNIV_SEARCH_PERF_STAT 310 ulint n_hash_succ; /*!< number of successful hash searches thus 311 far */ 312 ulint n_hash_fail; /*!< number of failed hash searches */ 313 ulint n_patt_succ; /*!< number of successful pattern searches thus 314 far */ 315 ulint n_searches; /*!< number of searches */ 316 #endif /* UNIV_SEARCH_PERF_STAT */ 317 #ifdef UNIV_DEBUG 318 ulint magic_n; /*!< magic number @see BTR_SEARCH_MAGIC_N */ 319 /** value of btr_search_t::magic_n, used in assertions */ 320 # define BTR_SEARCH_MAGIC_N 1112765 321 #endif /* UNIV_DEBUG */ 322 }; 323 324 /** The hash index system */ 325 struct btr_search_sys_t{ 326 hash_table_t** hash_tables; /*!< the adaptive hash tables, 327 mapping dtuple_fold values 328 to rec_t pointers on index pages */ 329 }; 330 331 /** Latches protecting access to adaptive hash index. */ 332 extern rw_lock_t** btr_search_latches; 333 334 /** The adaptive hash index */ 335 extern btr_search_sys_t* btr_search_sys; 336 337 #ifdef UNIV_SEARCH_PERF_STAT 338 /** Number of successful adaptive hash index lookups */ 339 extern ulint btr_search_n_succ; 340 /** Number of failed adaptive hash index lookups */ 341 extern ulint btr_search_n_hash_fail; 342 #endif /* UNIV_SEARCH_PERF_STAT */ 343 344 /** After change in n_fields or n_bytes in info, this many rounds are waited 345 before starting the hash analysis again: this is to save CPU time when there 346 is no hope in building a hash index. */ 347 #define BTR_SEARCH_HASH_ANALYSIS 17 348 349 /** Limit of consecutive searches for trying a search shortcut on the search 350 pattern */ 351 #define BTR_SEARCH_ON_PATTERN_LIMIT 3 352 353 /** Limit of consecutive searches for trying a search shortcut using 354 the hash index */ 355 #define BTR_SEARCH_ON_HASH_LIMIT 3 356 357 /** We do this many searches before trying to keep the search latch 358 over calls from MySQL. If we notice someone waiting for the latch, we 359 again set this much timeout. This is to reduce contention. */ 360 #define BTR_SEA_TIMEOUT 10000 361 362 #ifndef UNIV_NONINL 363 #include "btr0sea.ic" 364 #endif 365 366 #endif 367