The world's most popular open source database
mysql/src/5.1-dbg/storage/innobase/include/btr0sea.h
Go to the documentation of this file.00001 /************************************************************************ 00002 The index tree adaptive search 00003 00004 (c) 1996 Innobase Oy 00005 00006 Created 2/17/1996 Heikki Tuuri 00007 *************************************************************************/ 00008 00009 #ifndef btr0sea_h 00010 #define btr0sea_h 00011 00012 #include "univ.i" 00013 00014 #include "rem0rec.h" 00015 #include "dict0dict.h" 00016 #include "btr0types.h" 00017 #include "mtr0mtr.h" 00018 #include "ha0ha.h" 00019 00020 /********************************************************************* 00021 Creates and initializes the adaptive search system at a database start. */ 00022 00023 void 00024 btr_search_sys_create( 00025 /*==================*/ 00026 ulint hash_size); /* in: hash index hash table size */ 00027 /************************************************************************ 00028 Returns search info for an index. */ 00029 UNIV_INLINE 00030 btr_search_t* 00031 btr_search_get_info( 00032 /*================*/ 00033 /* out: search info; search mutex reserved */ 00034 dict_index_t* index); /* in: index */ 00035 /********************************************************************* 00036 Creates and initializes a search info struct. */ 00037 00038 btr_search_t* 00039 btr_search_info_create( 00040 /*===================*/ 00041 /* out, own: search info struct */ 00042 mem_heap_t* heap); /* in: heap where created */ 00043 /************************************************************************* 00044 Updates the search info. */ 00045 UNIV_INLINE 00046 void 00047 btr_search_info_update( 00048 /*===================*/ 00049 dict_index_t* index, /* in: index of the cursor */ 00050 btr_cur_t* cursor);/* in: cursor which was just positioned */ 00051 /********************************************************************** 00052 Tries to guess the right search position based on the hash search info 00053 of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts, 00054 and the function returns TRUE, then cursor->up_match and cursor->low_match 00055 both have sensible values. */ 00056 00057 ibool 00058 btr_search_guess_on_hash( 00059 /*=====================*/ 00060 /* out: TRUE if succeeded */ 00061 dict_index_t* index, /* in: index */ 00062 btr_search_t* info, /* in: index search info */ 00063 dtuple_t* tuple, /* in: logical record */ 00064 ulint mode, /* in: PAGE_CUR_L, ... */ 00065 ulint latch_mode, /* in: BTR_SEARCH_LEAF, ... */ 00066 btr_cur_t* cursor, /* out: tree cursor */ 00067 ulint has_search_latch,/* in: latch mode the caller 00068 currently has on btr_search_latch: 00069 RW_S_LATCH, RW_X_LATCH, or 0 */ 00070 mtr_t* mtr); /* in: mtr */ 00071 /************************************************************************ 00072 Moves or deletes hash entries for moved records. If new_page is already hashed, 00073 then the hash index for page, if any, is dropped. If new_page is not hashed, 00074 and page is hashed, then a new hash index is built to new_page with the same 00075 parameters as page (this often happens when a page is split). */ 00076 00077 void 00078 btr_search_move_or_delete_hash_entries( 00079 /*===================================*/ 00080 page_t* new_page, /* in: records are copied 00081 to this page */ 00082 page_t* page, /* in: index page */ 00083 dict_index_t* index); /* in: record descriptor */ 00084 /************************************************************************ 00085 Drops a page hash index. */ 00086 00087 void 00088 btr_search_drop_page_hash_index( 00089 /*============================*/ 00090 page_t* page); /* in: index page, s- or x-latched */ 00091 /************************************************************************ 00092 Drops a page hash index when a page is freed from a fseg to the file system. 00093 Drops possible hash index if the page happens to be in the buffer pool. */ 00094 00095 void 00096 btr_search_drop_page_hash_when_freed( 00097 /*=================================*/ 00098 ulint space, /* in: space id */ 00099 ulint page_no); /* in: page number */ 00100 /************************************************************************ 00101 Updates the page hash index when a single record is inserted on a page. */ 00102 00103 void 00104 btr_search_update_hash_node_on_insert( 00105 /*==================================*/ 00106 btr_cur_t* cursor);/* in: cursor which was positioned to the 00107 place to insert using btr_cur_search_..., 00108 and the new record has been inserted next 00109 to the cursor */ 00110 /************************************************************************ 00111 Updates the page hash index when a single record is inserted on a page. */ 00112 00113 void 00114 btr_search_update_hash_on_insert( 00115 /*=============================*/ 00116 btr_cur_t* cursor);/* in: cursor which was positioned to the 00117 place to insert using btr_cur_search_..., 00118 and the new record has been inserted next 00119 to the cursor */ 00120 /************************************************************************ 00121 Updates the page hash index when a single record is deleted from a page. */ 00122 00123 void 00124 btr_search_update_hash_on_delete( 00125 /*=============================*/ 00126 btr_cur_t* cursor);/* in: cursor which was positioned on the 00127 record to delete using btr_cur_search_..., 00128 the record is not yet deleted */ 00129 /************************************************************************ 00130 Validates the search system. */ 00131 00132 ibool 00133 btr_search_validate(void); 00134 /*======================*/ 00135 /* out: TRUE if ok */ 00136 00137 /* Search info directions */ 00138 #define BTR_SEA_NO_DIRECTION 1 00139 #define BTR_SEA_LEFT 2 00140 #define BTR_SEA_RIGHT 3 00141 #define BTR_SEA_SAME_REC 4 00142 00143 /* The search info struct in an index */ 00144 00145 struct btr_search_struct{ 00146 ulint magic_n; /* magic number */ 00147 /* The following 4 fields are currently not used: */ 00148 rec_t* last_search; /* pointer to the lower limit record of the 00149 previous search; NULL if not known */ 00150 ulint n_direction; /* number of consecutive searches in the 00151 same direction */ 00152 ulint direction; /* BTR_SEA_NO_DIRECTION, BTR_SEA_LEFT, 00153 BTR_SEA_RIGHT, BTR_SEA_SAME_REC, 00154 or BTR_SEA_SAME_PAGE */ 00155 dulint modify_clock; /* value of modify clock at the time 00156 last_search was stored */ 00157 /*----------------------*/ 00158 /* The following 4 fields are not protected by any latch: */ 00159 page_t* root_guess; /* the root page frame when it was last time 00160 fetched, or NULL */ 00161 ulint hash_analysis; /* when this exceeds a certain value, the 00162 hash analysis starts; this is reset if no 00163 success noticed */ 00164 ibool last_hash_succ; /* TRUE if the last search would have 00165 succeeded, or did succeed, using the hash 00166 index; NOTE that the value here is not exact: 00167 it is not calculated for every search, and the 00168 calculation itself is not always accurate! */ 00169 ulint n_hash_potential;/* number of consecutive searches which would 00170 have succeeded, or did succeed, using the hash 00171 index */ 00172 /*----------------------*/ 00173 ulint n_fields; /* recommended prefix length for hash search: 00174 number of full fields */ 00175 ulint n_bytes; /* recommended prefix: number of bytes in 00176 an incomplete field */ 00177 ulint side; /* BTR_SEARCH_LEFT_SIDE or 00178 BTR_SEARCH_RIGHT_SIDE, depending on whether 00179 the leftmost record of several records with 00180 the same prefix should be indexed in the 00181 hash index */ 00182 /*----------------------*/ 00183 #ifdef UNIV_SEARCH_PERF_STAT 00184 ulint n_hash_succ; /* number of successful hash searches thus 00185 far */ 00186 ulint n_hash_fail; /* number of failed hash searches */ 00187 ulint n_patt_succ; /* number of successful pattern searches thus 00188 far */ 00189 ulint n_searches; /* number of searches */ 00190 #endif /* UNIV_SEARCH_PERF_STAT */ 00191 }; 00192 00193 #define BTR_SEARCH_MAGIC_N 1112765 00194 00195 /* The hash index system */ 00196 00197 typedef struct btr_search_sys_struct btr_search_sys_t; 00198 00199 struct btr_search_sys_struct{ 00200 hash_table_t* hash_index; 00201 }; 00202 00203 extern btr_search_sys_t* btr_search_sys; 00204 00205 /* The latch protecting the adaptive search system: this latch protects the 00206 (1) hash index; 00207 (2) columns of a record to which we have a pointer in the hash index; 00208 00209 but does NOT protect: 00210 00211 (3) next record offset field in a record; 00212 (4) next or previous records on the same page. 00213 00214 Bear in mind (3) and (4) when using the hash index. 00215 */ 00216 00217 extern rw_lock_t* btr_search_latch_temp; 00218 00219 #define btr_search_latch (*btr_search_latch_temp) 00220 00221 #ifdef UNIV_SEARCH_PERF_STAT 00222 extern ulint btr_search_n_succ; 00223 extern ulint btr_search_n_hash_fail; 00224 #endif /* UNIV_SEARCH_PERF_STAT */ 00225 00226 /* After change in n_fields or n_bytes in info, this many rounds are waited 00227 before starting the hash analysis again: this is to save CPU time when there 00228 is no hope in building a hash index. */ 00229 00230 #define BTR_SEARCH_HASH_ANALYSIS 17 00231 00232 #define BTR_SEARCH_LEFT_SIDE 1 00233 #define BTR_SEARCH_RIGHT_SIDE 2 00234 00235 /* Limit of consecutive searches for trying a search shortcut on the search 00236 pattern */ 00237 00238 #define BTR_SEARCH_ON_PATTERN_LIMIT 3 00239 00240 /* Limit of consecutive searches for trying a search shortcut using the hash 00241 index */ 00242 00243 #define BTR_SEARCH_ON_HASH_LIMIT 3 00244 00245 /* We do this many searches before trying to keep the search latch over calls 00246 from MySQL. If we notice someone waiting for the latch, we again set this 00247 much timeout. This is to reduce contention. */ 00248 00249 #define BTR_SEA_TIMEOUT 10000 00250 00251 #ifndef UNIV_NONINL 00252 #include "btr0sea.ic" 00253 #endif 00254 00255 #endif
Generated on Sat Sep 9 00:50:26 2006 for MySQL 5.1 by
1.4.7
© 1995-2008 MySQL AB, 2008- Sun Microsystems, Inc.