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