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