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 btr_search_latch. 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 /*********************************************************************//** 99 Updates the search info. */ 100 UNIV_INLINE 101 void 102 btr_search_info_update( 103 /*===================*/ 104 dict_index_t* index, /*!< in: index of the cursor */ 105 btr_cur_t* cursor);/*!< in: cursor which was just positioned */ 106 /******************************************************************//** 107 Tries to guess the right search position based on the hash search info 108 of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts, 109 and the function returns TRUE, then cursor->up_match and cursor->low_match 110 both have sensible values. 111 @return TRUE if succeeded */ 112 UNIV_INTERN 113 ibool 114 btr_search_guess_on_hash( 115 /*=====================*/ 116 dict_index_t* index, /*!< in: index */ 117 btr_search_t* info, /*!< in: index search info */ 118 const dtuple_t* tuple, /*!< in: logical record */ 119 ulint mode, /*!< in: PAGE_CUR_L, ... */ 120 ulint latch_mode, /*!< in: BTR_SEARCH_LEAF, ... */ 121 btr_cur_t* cursor, /*!< out: tree cursor */ 122 ulint has_search_latch,/*!< in: latch mode the caller 123 currently has on btr_search_latch: 124 RW_S_LATCH, RW_X_LATCH, or 0 */ 125 mtr_t* mtr); /*!< in: mtr */ 126 /********************************************************************//** 127 Moves or deletes hash entries for moved records. If new_page is already hashed, 128 then the hash index for page, if any, is dropped. If new_page is not hashed, 129 and page is hashed, then a new hash index is built to new_page with the same 130 parameters as page (this often happens when a page is split). */ 131 UNIV_INTERN 132 void 133 btr_search_move_or_delete_hash_entries( 134 /*===================================*/ 135 buf_block_t* new_block, /*!< in: records are copied 136 to this page */ 137 buf_block_t* block, /*!< in: index page from which 138 records were copied, and the 139 copied records will be deleted 140 from this page */ 141 dict_index_t* index); /*!< in: record descriptor */ 142 /********************************************************************//** 143 Drops a page hash index. */ 144 UNIV_INTERN 145 void 146 btr_search_drop_page_hash_index( 147 /*============================*/ 148 buf_block_t* block); /*!< in: block containing index page, 149 s- or x-latched, or an index page 150 for which we know that 151 block->buf_fix_count == 0 */ 152 /********************************************************************//** 153 Drops a possible page hash index when a page is evicted from the buffer pool 154 or freed in a file segment. */ 155 UNIV_INTERN 156 void 157 btr_search_drop_page_hash_when_freed( 158 /*=================================*/ 159 ulint space, /*!< in: space id */ 160 ulint zip_size, /*!< in: compressed page size in bytes 161 or 0 for uncompressed pages */ 162 ulint page_no); /*!< in: page number */ 163 /********************************************************************//** 164 Updates the page hash index when a single record is inserted on a page. */ 165 UNIV_INTERN 166 void 167 btr_search_update_hash_node_on_insert( 168 /*==================================*/ 169 btr_cur_t* cursor);/*!< in: cursor which was positioned to the 170 place to insert using btr_cur_search_..., 171 and the new record has been inserted next 172 to the cursor */ 173 /********************************************************************//** 174 Updates the page hash index when a single record is inserted on a page. */ 175 UNIV_INTERN 176 void 177 btr_search_update_hash_on_insert( 178 /*=============================*/ 179 btr_cur_t* cursor);/*!< in: cursor which was positioned to the 180 place to insert using btr_cur_search_..., 181 and the new record has been inserted next 182 to the cursor */ 183 /********************************************************************//** 184 Updates the page hash index when a single record is deleted from a page. */ 185 UNIV_INTERN 186 void 187 btr_search_update_hash_on_delete( 188 /*=============================*/ 189 btr_cur_t* cursor);/*!< in: cursor which was positioned on the 190 record to delete using btr_cur_search_..., 191 the record is not yet deleted */ 192 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG 193 /********************************************************************//** 194 Validates the search system. 195 @return TRUE if ok */ 196 UNIV_INTERN 197 ibool 198 btr_search_validate(void); 199 /*======================*/ 200 #endif /* defined UNIV_AHI_DEBUG || defined UNIV_DEBUG */ 201 202 /** The search info struct in an index */ 203 struct btr_search_t{ 204 ulint ref_count; /*!< Number of blocks in this index tree 205 that have search index built 206 i.e. block->index points to this index. 207 Protected by btr_search_latch except 208 when during initialization in 209 btr_search_info_create(). */ 210 211 /* @{ The following fields are not protected by any latch. 212 Unfortunately, this means that they must be aligned to 213 the machine word, i.e., they cannot be turned into bit-fields. */ 214 buf_block_t* root_guess;/*!< the root page frame when it was last time 215 fetched, or NULL */ 216 ulint hash_analysis; /*!< when this exceeds 217 BTR_SEARCH_HASH_ANALYSIS, the hash 218 analysis starts; this is reset if no 219 success noticed */ 220 ibool last_hash_succ; /*!< TRUE if the last search would have 221 succeeded, or did succeed, using the hash 222 index; NOTE that the value here is not exact: 223 it is not calculated for every search, and the 224 calculation itself is not always accurate! */ 225 ulint n_hash_potential; 226 /*!< number of consecutive searches 227 which would have succeeded, or did succeed, 228 using the hash index; 229 the range is 0 .. BTR_SEARCH_BUILD_LIMIT + 5 */ 230 /* @} */ 231 /*---------------------- @{ */ 232 ulint n_fields; /*!< recommended prefix length for hash search: 233 number of full fields */ 234 ulint n_bytes; /*!< recommended prefix: number of bytes in 235 an incomplete field 236 @see BTR_PAGE_MAX_REC_SIZE */ 237 ibool left_side; /*!< TRUE or FALSE, depending on whether 238 the leftmost record of several records with 239 the same prefix should be indexed in the 240 hash index */ 241 /*---------------------- @} */ 242 #ifdef UNIV_SEARCH_PERF_STAT 243 ulint n_hash_succ; /*!< number of successful hash searches thus 244 far */ 245 ulint n_hash_fail; /*!< number of failed hash searches */ 246 ulint n_patt_succ; /*!< number of successful pattern searches thus 247 far */ 248 ulint n_searches; /*!< number of searches */ 249 #endif /* UNIV_SEARCH_PERF_STAT */ 250 #ifdef UNIV_DEBUG 251 ulint magic_n; /*!< magic number @see BTR_SEARCH_MAGIC_N */ 252 /** value of btr_search_t::magic_n, used in assertions */ 253 # define BTR_SEARCH_MAGIC_N 1112765 254 #endif /* UNIV_DEBUG */ 255 }; 256 257 /** The hash index system */ 258 struct btr_search_sys_t{ 259 hash_table_t* hash_index; /*!< the adaptive hash index, 260 mapping dtuple_fold values 261 to rec_t pointers on index pages */ 262 }; 263 264 /** The adaptive hash index */ 265 extern btr_search_sys_t* btr_search_sys; 266 267 #ifdef UNIV_SEARCH_PERF_STAT 268 /** Number of successful adaptive hash index lookups */ 269 extern ulint btr_search_n_succ; 270 /** Number of failed adaptive hash index lookups */ 271 extern ulint btr_search_n_hash_fail; 272 #endif /* UNIV_SEARCH_PERF_STAT */ 273 274 /** After change in n_fields or n_bytes in info, this many rounds are waited 275 before starting the hash analysis again: this is to save CPU time when there 276 is no hope in building a hash index. */ 277 #define BTR_SEARCH_HASH_ANALYSIS 17 278 279 /** Limit of consecutive searches for trying a search shortcut on the search 280 pattern */ 281 #define BTR_SEARCH_ON_PATTERN_LIMIT 3 282 283 /** Limit of consecutive searches for trying a search shortcut using 284 the hash index */ 285 #define BTR_SEARCH_ON_HASH_LIMIT 3 286 287 /** We do this many searches before trying to keep the search latch 288 over calls from MySQL. If we notice someone waiting for the latch, we 289 again set this much timeout. This is to reduce contention. */ 290 #define BTR_SEA_TIMEOUT 10000 291 292 #ifndef UNIV_NONINL 293 #include "btr0sea.ic" 294 #endif 295 296 #endif 297