1 /***************************************************************************** 2 3 Copyright (c) 1996, 2016, Oracle and/or its affiliates. All Rights Reserved. 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 /*****************************************************************//** 46 Creates and initializes the adaptive search system at a database start. */ 47 UNIV_INTERN 48 void 49 btr_search_sys_create( 50 /*==================*/ 51 ulint hash_size); /*!< in: hash index hash table size */ 52 /*****************************************************************//** 53 Frees the adaptive search system at a database shutdown. */ 54 UNIV_INTERN 55 void 56 btr_search_sys_free(void); 57 /*=====================*/ 58 59 /********************************************************************//** 60 Disable the adaptive hash search system and empty the index. */ 61 UNIV_INTERN 62 void 63 btr_search_disable(void); 64 /*====================*/ 65 /********************************************************************//** 66 Enable the adaptive hash search system. */ 67 UNIV_INTERN 68 void 69 btr_search_enable(void); 70 /*====================*/ 71 72 /********************************************************************//** 73 Returns search info for an index. 74 @return search info; search mutex reserved */ 75 UNIV_INLINE 76 btr_search_t* 77 btr_search_get_info( 78 /*================*/ 79 dict_index_t* index) /*!< in: index */ 80 MY_ATTRIBUTE((nonnull)); 81 /*****************************************************************//** 82 Creates and initializes a search info struct. 83 @return own: search info struct */ 84 UNIV_INTERN 85 btr_search_t* 86 btr_search_info_create( 87 /*===================*/ 88 mem_heap_t* heap); /*!< in: heap where created */ 89 /*****************************************************************//** 90 Returns the value of ref_count. The value is protected by 91 the latch of the AHI partition corresponding to this index. 92 @return ref_count value. */ 93 UNIV_INTERN 94 ulint 95 btr_search_info_get_ref_count( 96 /*==========================*/ 97 btr_search_t* info, /*!< in: search info. */ 98 dict_index_t* index); /*!< in: index */ 99 /*********************************************************************//** 100 Updates the search info. */ 101 UNIV_INLINE 102 void 103 btr_search_info_update( 104 /*===================*/ 105 dict_index_t* index, /*!< in: index of the cursor */ 106 btr_cur_t* cursor);/*!< in: cursor which was just positioned */ 107 /******************************************************************//** 108 Tries to guess the right search position based on the hash search info 109 of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts, 110 and the function returns TRUE, then cursor->up_match and cursor->low_match 111 both have sensible values. 112 @return TRUE if succeeded */ 113 UNIV_INTERN 114 ibool 115 btr_search_guess_on_hash( 116 /*=====================*/ 117 dict_index_t* index, /*!< in: index */ 118 btr_search_t* info, /*!< in: index search info */ 119 const dtuple_t* tuple, /*!< in: logical record */ 120 ulint mode, /*!< in: PAGE_CUR_L, ... */ 121 ulint latch_mode, /*!< in: BTR_SEARCH_LEAF, ... */ 122 btr_cur_t* cursor, /*!< out: tree cursor */ 123 ulint has_search_latch,/*!< in: latch mode the caller 124 currently has on btr_search_latch: 125 RW_S_LATCH, RW_X_LATCH, or 0 */ 126 mtr_t* mtr); /*!< in: mtr */ 127 /********************************************************************//** 128 Moves or deletes hash entries for moved records. If new_page is already hashed, 129 then the hash index for page, if any, is dropped. If new_page is not hashed, 130 and page is hashed, then a new hash index is built to new_page with the same 131 parameters as page (this often happens when a page is split). */ 132 UNIV_INTERN 133 void 134 btr_search_move_or_delete_hash_entries( 135 /*===================================*/ 136 buf_block_t* new_block, /*!< in: records are copied 137 to this page */ 138 buf_block_t* block, /*!< in: index page from which 139 records were copied, and the 140 copied records will be deleted 141 from this page */ 142 dict_index_t* index); /*!< in: record descriptor */ 143 /********************************************************************//** 144 Drops a page hash index. */ 145 UNIV_INTERN 146 void 147 btr_search_drop_page_hash_index( 148 /*============================*/ 149 buf_block_t* block); /*!< in: block containing index page, 150 s- or x-latched, or an index page 151 for which we know that 152 block->buf_fix_count == 0 */ 153 /********************************************************************//** 154 Drops a possible page hash index when a page is evicted from the buffer pool 155 or freed in a file segment. */ 156 UNIV_INTERN 157 void 158 btr_search_drop_page_hash_when_freed( 159 /*=================================*/ 160 ulint space, /*!< in: space id */ 161 ulint zip_size, /*!< in: compressed page size in bytes 162 or 0 for uncompressed pages */ 163 ulint page_no); /*!< in: page number */ 164 /********************************************************************//** 165 Updates the page hash index when a single record is inserted on a page. */ 166 UNIV_INTERN 167 void 168 btr_search_update_hash_node_on_insert( 169 /*==================================*/ 170 btr_cur_t* cursor);/*!< in: cursor which was positioned to the 171 place to insert using btr_cur_search_..., 172 and the new record has been inserted next 173 to the cursor */ 174 /********************************************************************//** 175 Updates the page hash index when a single record is inserted on a page. */ 176 UNIV_INTERN 177 void 178 btr_search_update_hash_on_insert( 179 /*=============================*/ 180 btr_cur_t* cursor);/*!< in: cursor which was positioned to the 181 place to insert using btr_cur_search_..., 182 and the new record has been inserted next 183 to the cursor */ 184 /********************************************************************//** 185 Updates the page hash index when a single record is deleted from a page. */ 186 UNIV_INTERN 187 void 188 btr_search_update_hash_on_delete( 189 /*=============================*/ 190 btr_cur_t* cursor);/*!< in: cursor which was positioned on the 191 record to delete using btr_cur_search_..., 192 the record is not yet deleted */ 193 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG 194 /********************************************************************//** 195 Validates the search system. 196 @return TRUE if ok */ 197 UNIV_INTERN 198 ibool 199 btr_search_validate(void); 200 /*======================*/ 201 #endif /* defined UNIV_AHI_DEBUG || defined UNIV_DEBUG */ 202 203 /********************************************************************//** 204 Returns the adaptive hash index table for a given index key. 205 @return the adaptive hash index table for a given index key */ 206 UNIV_INLINE 207 hash_table_t* 208 btr_search_get_hash_table( 209 /*======================*/ 210 const dict_index_t* index) /*!< in: index */ 211 MY_ATTRIBUTE((warn_unused_result)); 212 213 /********************************************************************//** 214 Returns the adaptive hash index latch for a given index key. 215 @return the adaptive hash index latch for a given index key */ 216 UNIV_INLINE 217 prio_rw_lock_t* 218 btr_search_get_latch( 219 /*=================*/ 220 const dict_index_t* index) /*!< in: index */ 221 MY_ATTRIBUTE((warn_unused_result)); 222 223 /*********************************************************************//** 224 Returns the AHI partition number corresponding to a given index ID. */ 225 UNIV_INLINE 226 ulint 227 btr_search_get_key( 228 /*===============*/ 229 index_id_t index_id) /*!< in: index ID */ 230 MY_ATTRIBUTE((pure,warn_unused_result)); 231 232 /*********************************************************************//** 233 Initializes AHI-related fields in a newly created index. */ 234 UNIV_INLINE 235 void 236 btr_search_index_init( 237 /*===============*/ 238 dict_index_t* index); /*!< in: index */ 239 240 /********************************************************************//** 241 Latches all adaptive hash index latches in exclusive mode. */ 242 UNIV_INLINE 243 void 244 btr_search_x_lock_all(void); 245 /*========================*/ 246 247 /********************************************************************//** 248 Unlatches all adaptive hash index latches in exclusive mode. */ 249 UNIV_INLINE 250 void 251 btr_search_x_unlock_all(void); 252 /*==========================*/ 253 254 #ifdef UNIV_SYNC_DEBUG 255 /******************************************************************//** 256 Checks if the thread has locked all the adaptive hash index latches in the 257 specified mode. 258 259 @return true if all latches are locked by the current thread, false 260 otherwise. */ 261 UNIV_INLINE 262 bool 263 btr_search_own_all( 264 /*===============*/ 265 ulint lock_type) 266 MY_ATTRIBUTE((warn_unused_result)); 267 /********************************************************************//** 268 Checks if the thread owns any adaptive hash latches in either S or X mode. 269 @return true if the thread owns at least one latch in any mode. */ 270 UNIV_INLINE 271 bool 272 btr_search_own_any(void) 273 /*=====================*/ 274 MY_ATTRIBUTE((warn_unused_result)); 275 #endif 276 277 /** The search info struct in an index */ 278 struct btr_search_t{ 279 ulint ref_count; /*!< Number of blocks in this index tree 280 that have search index built 281 i.e. block->index points to this index. 282 Protected by btr_search_latch except 283 when during initialization in 284 btr_search_info_create(). */ 285 286 /* @{ The following fields are not protected by any latch. 287 Unfortunately, this means that they must be aligned to 288 the machine word, i.e., they cannot be turned into bit-fields. */ 289 buf_block_t* root_guess;/*!< the root page frame when it was last time 290 fetched, or NULL */ 291 ulint hash_analysis; /*!< when this exceeds 292 BTR_SEARCH_HASH_ANALYSIS, the hash 293 analysis starts; this is reset if no 294 success noticed */ 295 ibool last_hash_succ; /*!< TRUE if the last search would have 296 succeeded, or did succeed, using the hash 297 index; NOTE that the value here is not exact: 298 it is not calculated for every search, and the 299 calculation itself is not always accurate! */ 300 ulint n_hash_potential; 301 /*!< number of consecutive searches 302 which would have succeeded, or did succeed, 303 using the hash index; 304 the range is 0 .. BTR_SEARCH_BUILD_LIMIT + 5 */ 305 /* @} */ 306 /*---------------------- @{ */ 307 ulint n_fields; /*!< recommended prefix length for hash search: 308 number of full fields */ 309 ulint n_bytes; /*!< recommended prefix: number of bytes in 310 an incomplete field 311 @see BTR_PAGE_MAX_REC_SIZE */ 312 ibool left_side; /*!< TRUE or FALSE, depending on whether 313 the leftmost record of several records with 314 the same prefix should be indexed in the 315 hash index */ 316 /*---------------------- @} */ 317 #ifdef UNIV_SEARCH_PERF_STAT 318 ulint n_hash_succ; /*!< number of successful hash searches thus 319 far */ 320 ulint n_hash_fail; /*!< number of failed hash searches */ 321 ulint n_patt_succ; /*!< number of successful pattern searches thus 322 far */ 323 ulint n_searches; /*!< number of searches */ 324 #endif /* UNIV_SEARCH_PERF_STAT */ 325 #ifdef UNIV_DEBUG 326 ulint magic_n; /*!< magic number @see BTR_SEARCH_MAGIC_N */ 327 /** value of btr_search_t::magic_n, used in assertions */ 328 # define BTR_SEARCH_MAGIC_N 1112765 329 #endif /* UNIV_DEBUG */ 330 }; 331 332 /** The hash index system */ 333 struct btr_search_sys_t{ 334 hash_table_t** hash_tables; /*!< the array of adaptive hash index 335 tables, mapping dtuple_fold values to 336 rec_t pointers on index pages */ 337 }; 338 339 /** The adaptive hash index */ 340 extern btr_search_sys_t* btr_search_sys; 341 342 #ifdef UNIV_SEARCH_PERF_STAT 343 /** Number of successful adaptive hash index lookups */ 344 extern ulint btr_search_n_succ; 345 /** Number of failed adaptive hash index lookups */ 346 extern ulint btr_search_n_hash_fail; 347 #endif /* UNIV_SEARCH_PERF_STAT */ 348 349 /** After change in n_fields or n_bytes in info, this many rounds are waited 350 before starting the hash analysis again: this is to save CPU time when there 351 is no hope in building a hash index. */ 352 #define BTR_SEARCH_HASH_ANALYSIS 17 353 354 /** Limit of consecutive searches for trying a search shortcut on the search 355 pattern */ 356 #define BTR_SEARCH_ON_PATTERN_LIMIT 3 357 358 /** Limit of consecutive searches for trying a search shortcut using 359 the hash index */ 360 #define BTR_SEARCH_ON_HASH_LIMIT 3 361 362 /** We do this many searches before trying to keep the search latch 363 over calls from MySQL. If we notice someone waiting for the latch, we 364 again set this much timeout. This is to reduce contention. */ 365 #define BTR_SEA_TIMEOUT 10000 366 367 #ifndef UNIV_NONINL 368 #include "btr0sea.ic" 369 #endif 370 371 #endif 372