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