1 /***************************************************************************** 2 3 Copyright (c) 1996, 2011, Oracle and/or its affiliates. All Rights Reserved. 4 5 This program is free software; you can redistribute it and/or modify it under 6 the terms of the GNU General Public License as published by the Free Software 7 Foundation; version 2 of the License. 8 9 This program is distributed in the hope that it will be useful, but WITHOUT 10 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 11 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. 12 13 You should have received a copy of the GNU General Public License along with 14 this program; if not, write to the Free Software Foundation, Inc., 15 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 16 17 *****************************************************************************/ 18 19 /********************************************************************//** 20 @file include/btr0sea.h 21 The index tree adaptive search 22 23 Created 2/17/1996 Heikki Tuuri 24 *************************************************************************/ 25 26 #ifndef btr0sea_h 27 #define btr0sea_h 28 29 #include "univ.i" 30 31 #include "rem0rec.h" 32 #include "dict0dict.h" 33 #include "btr0types.h" 34 #include "mtr0mtr.h" 35 #include "ha0ha.h" 36 37 /*****************************************************************//** 38 Creates and initializes the adaptive search system at a database start. */ 39 UNIV_INTERN 40 void 41 btr_search_sys_create( 42 /*==================*/ 43 ulint hash_size); /*!< in: hash index hash table size */ 44 /*****************************************************************//** 45 Frees the adaptive search system at a database shutdown. */ 46 UNIV_INTERN 47 void 48 btr_search_sys_free(void); 49 /*=====================*/ 50 51 /********************************************************************//** 52 Disable the adaptive hash search system and empty the index. */ 53 UNIV_INTERN 54 void 55 btr_search_disable(void); 56 /*====================*/ 57 /********************************************************************//** 58 Enable the adaptive hash search system. */ 59 UNIV_INTERN 60 void 61 btr_search_enable(void); 62 /*====================*/ 63 64 /********************************************************************//** 65 Returns search info for an index. 66 @return search info; search mutex reserved */ 67 UNIV_INLINE 68 btr_search_t* 69 btr_search_get_info( 70 /*================*/ 71 dict_index_t* index); /*!< in: index */ 72 /*****************************************************************//** 73 Creates and initializes a search info struct. 74 @return own: search info struct */ 75 UNIV_INTERN 76 btr_search_t* 77 btr_search_info_create( 78 /*===================*/ 79 mem_heap_t* heap); /*!< in: heap where created */ 80 /*****************************************************************//** 81 Returns the value of ref_count. The value is protected by 82 btr_search_latch. 83 @return ref_count value. */ 84 UNIV_INTERN 85 ulint 86 btr_search_info_get_ref_count( 87 /*==========================*/ 88 btr_search_t* info); /*!< in: search info. */ 89 /*********************************************************************//** 90 Updates the search info. */ 91 UNIV_INLINE 92 void 93 btr_search_info_update( 94 /*===================*/ 95 dict_index_t* index, /*!< in: index of the cursor */ 96 btr_cur_t* cursor);/*!< in: cursor which was just positioned */ 97 /******************************************************************//** 98 Tries to guess the right search position based on the hash search info 99 of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts, 100 and the function returns TRUE, then cursor->up_match and cursor->low_match 101 both have sensible values. 102 @return TRUE if succeeded */ 103 UNIV_INTERN 104 ibool 105 btr_search_guess_on_hash( 106 /*=====================*/ 107 dict_index_t* index, /*!< in: index */ 108 btr_search_t* info, /*!< in: index search info */ 109 const dtuple_t* tuple, /*!< in: logical record */ 110 ulint mode, /*!< in: PAGE_CUR_L, ... */ 111 ulint latch_mode, /*!< in: BTR_SEARCH_LEAF, ... */ 112 btr_cur_t* cursor, /*!< out: tree cursor */ 113 ulint has_search_latch,/*!< in: latch mode the caller 114 currently has on btr_search_latch: 115 RW_S_LATCH, RW_X_LATCH, or 0 */ 116 mtr_t* mtr); /*!< in: mtr */ 117 /********************************************************************//** 118 Moves or deletes hash entries for moved records. If new_page is already hashed, 119 then the hash index for page, if any, is dropped. If new_page is not hashed, 120 and page is hashed, then a new hash index is built to new_page with the same 121 parameters as page (this often happens when a page is split). */ 122 UNIV_INTERN 123 void 124 btr_search_move_or_delete_hash_entries( 125 /*===================================*/ 126 buf_block_t* new_block, /*!< in: records are copied 127 to this page */ 128 buf_block_t* block, /*!< in: index page from which 129 records were copied, and the 130 copied records will be deleted 131 from this page */ 132 dict_index_t* index); /*!< in: record descriptor */ 133 /********************************************************************//** 134 Drops a page hash index. */ 135 UNIV_INTERN 136 void 137 btr_search_drop_page_hash_index( 138 /*============================*/ 139 buf_block_t* block); /*!< in: block containing index page, 140 s- or x-latched, or an index page 141 for which we know that 142 block->buf_fix_count == 0 */ 143 /********************************************************************//** 144 Drops a possible page hash index when a page is evicted from the buffer pool 145 or freed in a file segment. */ 146 UNIV_INTERN 147 void 148 btr_search_drop_page_hash_when_freed( 149 /*=================================*/ 150 ulint space, /*!< in: space id */ 151 ulint zip_size, /*!< in: compressed page size in bytes 152 or 0 for uncompressed pages */ 153 ulint page_no); /*!< in: page number */ 154 /********************************************************************//** 155 Updates the page hash index when a single record is inserted on a page. */ 156 UNIV_INTERN 157 void 158 btr_search_update_hash_node_on_insert( 159 /*==================================*/ 160 btr_cur_t* cursor);/*!< in: cursor which was positioned to the 161 place to insert using btr_cur_search_..., 162 and the new record has been inserted next 163 to the cursor */ 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_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 deleted from a page. */ 176 UNIV_INTERN 177 void 178 btr_search_update_hash_on_delete( 179 /*=============================*/ 180 btr_cur_t* cursor);/*!< in: cursor which was positioned on the 181 record to delete using btr_cur_search_..., 182 the record is not yet deleted */ 183 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG 184 /********************************************************************//** 185 Validates the search system. 186 @return TRUE if ok */ 187 UNIV_INTERN 188 ibool 189 btr_search_validate(void); 190 /*======================*/ 191 #endif /* defined UNIV_AHI_DEBUG || defined UNIV_DEBUG */ 192 193 /** The search info struct in an index */ 194 struct btr_search_struct{ 195 ulint ref_count; /*!< Number of blocks in this index tree 196 that have search index built 197 i.e. block->index points to this index. 198 Protected by btr_search_latch except 199 when during initialization in 200 btr_search_info_create(). */ 201 202 /* @{ The following fields are not protected by any latch. 203 Unfortunately, this means that they must be aligned to 204 the machine word, i.e., they cannot be turned into bit-fields. */ 205 buf_block_t* root_guess;/*!< the root page frame when it was last time 206 fetched, or NULL */ 207 ulint hash_analysis; /*!< when this exceeds 208 BTR_SEARCH_HASH_ANALYSIS, the hash 209 analysis starts; this is reset if no 210 success noticed */ 211 ibool last_hash_succ; /*!< TRUE if the last search would have 212 succeeded, or did succeed, using the hash 213 index; NOTE that the value here is not exact: 214 it is not calculated for every search, and the 215 calculation itself is not always accurate! */ 216 ulint n_hash_potential; 217 /*!< number of consecutive searches 218 which would have succeeded, or did succeed, 219 using the hash index; 220 the range is 0 .. BTR_SEARCH_BUILD_LIMIT + 5 */ 221 /* @} */ 222 /*---------------------- @{ */ 223 ulint n_fields; /*!< recommended prefix length for hash search: 224 number of full fields */ 225 ulint n_bytes; /*!< recommended prefix: number of bytes in 226 an incomplete field 227 @see BTR_PAGE_MAX_REC_SIZE */ 228 ibool left_side; /*!< TRUE or FALSE, depending on whether 229 the leftmost record of several records with 230 the same prefix should be indexed in the 231 hash index */ 232 /*---------------------- @} */ 233 #ifdef UNIV_SEARCH_PERF_STAT 234 ulint n_hash_succ; /*!< number of successful hash searches thus 235 far */ 236 ulint n_hash_fail; /*!< number of failed hash searches */ 237 ulint n_patt_succ; /*!< number of successful pattern searches thus 238 far */ 239 ulint n_searches; /*!< number of searches */ 240 #endif /* UNIV_SEARCH_PERF_STAT */ 241 #ifdef UNIV_DEBUG 242 ulint magic_n; /*!< magic number @see BTR_SEARCH_MAGIC_N */ 243 /** value of btr_search_struct::magic_n, used in assertions */ 244 # define BTR_SEARCH_MAGIC_N 1112765 245 #endif /* UNIV_DEBUG */ 246 }; 247 248 /** The hash index system */ 249 typedef struct btr_search_sys_struct btr_search_sys_t; 250 251 /** The hash index system */ 252 struct btr_search_sys_struct{ 253 hash_table_t* hash_index; /*!< the adaptive hash index, 254 mapping dtuple_fold values 255 to rec_t pointers on index pages */ 256 }; 257 258 /** The adaptive hash index */ 259 extern btr_search_sys_t* btr_search_sys; 260 261 #ifdef UNIV_SEARCH_PERF_STAT 262 /** Number of successful adaptive hash index lookups */ 263 extern ulint btr_search_n_succ; 264 /** Number of failed adaptive hash index lookups */ 265 extern ulint btr_search_n_hash_fail; 266 #endif /* UNIV_SEARCH_PERF_STAT */ 267 268 /** After change in n_fields or n_bytes in info, this many rounds are waited 269 before starting the hash analysis again: this is to save CPU time when there 270 is no hope in building a hash index. */ 271 #define BTR_SEARCH_HASH_ANALYSIS 17 272 273 /** Limit of consecutive searches for trying a search shortcut on the search 274 pattern */ 275 #define BTR_SEARCH_ON_PATTERN_LIMIT 3 276 277 /** Limit of consecutive searches for trying a search shortcut using 278 the hash index */ 279 #define BTR_SEARCH_ON_HASH_LIMIT 3 280 281 /** We do this many searches before trying to keep the search latch 282 over calls from MySQL. If we notice someone waiting for the latch, we 283 again set this much timeout. This is to reduce contention. */ 284 #define BTR_SEA_TIMEOUT 10000 285 286 #ifndef UNIV_NONINL 287 #include "btr0sea.ic" 288 #endif 289 290 #endif 291