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