1
/*****************************************************************************
3
Copyright (c) 1996, 2009, Innobase Oy. All Rights Reserved.
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.
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.
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
17
*****************************************************************************/
19
/************************************************************************
20
The index tree adaptive search
22
Created 2/17/1996 Heikki Tuuri
23
*************************************************************************/
31
#include "dict0dict.h"
32
#include "btr0types.h"
36
/*********************************************************************
37
Creates and initializes the adaptive search system at a database start. */
40
btr_search_sys_create(
41
/*==================*/
42
ulint hash_size); /* in: hash index hash table size */
44
/************************************************************************
45
Disable the adaptive hash search system and empty the index. */
48
btr_search_disable(void);
49
/*====================*/
50
/************************************************************************
51
Enable the adaptive hash search system. */
54
btr_search_enable(void);
55
/*====================*/
57
/************************************************************************
58
Returns search info for an index. */
63
/* out: search info; search mutex reserved */
64
dict_index_t* index); /* in: index */
65
/*********************************************************************
66
Creates and initializes a search info struct. */
69
btr_search_info_create(
70
/*===================*/
71
/* out, own: search info struct */
72
mem_heap_t* heap); /* in: heap where created */
73
/*********************************************************************
74
Returns the value of ref_count. The value is protected by
78
btr_search_info_get_ref_count(
79
/*==========================*/
80
/* out: ref_count value. */
81
btr_search_t* info); /* in: search info. */
82
/*************************************************************************
83
Updates the search info. */
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. */
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). */
117
btr_search_move_or_delete_hash_entries(
118
/*===================================*/
119
buf_block_t* new_block, /* in: records are copied
121
buf_block_t* block, /* in: index page from which
122
records were copied, and the
123
copied records will be deleted
125
dict_index_t* index); /* in: record descriptor */
126
/************************************************************************
127
Drops a page hash index. */
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. */
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. */
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
157
/************************************************************************
158
Updates the page hash index when a single record is inserted on a page. */
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
167
/************************************************************************
168
Updates the page hash index when a single record is deleted from a page. */
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. */
180
btr_search_validate(void);
181
/*======================*/
182
/* out: TRUE if ok */
183
/*********************************************************************
184
Reset global configuration variables. */
187
btr_search_var_init(void);
188
/*=====================*/
189
/*********************************************************************
190
Closes the adaptive search system at a database shutdown. */
193
btr_search_sys_close(void);
194
/*======================*/
196
/* Flag: has the search system been enabled?
197
Protected by btr_search_latch and btr_search_enabled_mutex. */
198
extern char btr_search_enabled;
200
/* The search info struct in an index */
202
struct btr_search_struct{
203
ulint ref_count; /* Number of blocks in this index tree
204
that have search index built
205
i.e. block->index points to this index.
206
Protected by btr_search_latch except
207
when during initialization in
208
btr_search_info_create(). */
210
/* The following fields are not protected by any latch.
211
Unfortunately, this means that they must be aligned to
212
the machine word, i.e., they cannot be turned into bit-fields. */
213
buf_block_t* root_guess;/* the root page frame when it was last time
215
ulint hash_analysis; /* when this exceeds BTR_SEARCH_HASH_ANALYSIS,
216
the hash analysis starts; this is reset if no
218
ibool last_hash_succ; /* TRUE if the last search would have
219
succeeded, or did succeed, using the hash
220
index; NOTE that the value here is not exact:
221
it is not calculated for every search, and the
222
calculation itself is not always accurate! */
223
ulint n_hash_potential;
224
/* number of consecutive searches
225
which would have succeeded, or did succeed,
226
using the hash index;
227
the range is 0 .. BTR_SEARCH_BUILD_LIMIT + 5 */
228
/*----------------------*/
229
ulint n_fields; /* recommended prefix length for hash search:
230
number of full fields */
231
ulint n_bytes; /* recommended prefix: number of bytes in
233
see also BTR_PAGE_MAX_REC_SIZE */
234
ibool left_side; /* TRUE or FALSE, depending on whether
235
the leftmost record of several records with
236
the same prefix should be indexed in the
238
/*----------------------*/
239
#ifdef UNIV_SEARCH_PERF_STAT
240
ulint n_hash_succ; /* number of successful hash searches thus
242
ulint n_hash_fail; /* number of failed hash searches */
243
ulint n_patt_succ; /* number of successful pattern searches thus
245
ulint n_searches; /* number of searches */
246
#endif /* UNIV_SEARCH_PERF_STAT */
248
ulint magic_n; /* magic number */
249
# define BTR_SEARCH_MAGIC_N 1112765
250
#endif /* UNIV_DEBUG */
253
/* The hash index system */
255
typedef struct btr_search_sys_struct btr_search_sys_t;
257
struct btr_search_sys_struct{
258
hash_table_t* hash_index;
261
extern btr_search_sys_t* btr_search_sys;
263
/* The latch protecting the adaptive search system: this latch protects the
265
(2) columns of a record to which we have a pointer in the hash index;
267
but does NOT protect:
269
(3) next record offset field in a record;
270
(4) next or previous records on the same page.
272
Bear in mind (3) and (4) when using the hash index.
275
extern rw_lock_t* btr_search_latch_temp;
277
#define btr_search_latch (*btr_search_latch_temp)
279
#ifdef UNIV_SEARCH_PERF_STAT
280
extern ulint btr_search_n_succ;
281
extern ulint btr_search_n_hash_fail;
282
#endif /* UNIV_SEARCH_PERF_STAT */
284
/* After change in n_fields or n_bytes in info, this many rounds are waited
285
before starting the hash analysis again: this is to save CPU time when there
286
is no hope in building a hash index. */
288
#define BTR_SEARCH_HASH_ANALYSIS 17
290
/* Limit of consecutive searches for trying a search shortcut on the search
293
#define BTR_SEARCH_ON_PATTERN_LIMIT 3
295
/* Limit of consecutive searches for trying a search shortcut using the hash
298
#define BTR_SEARCH_ON_HASH_LIMIT 3
300
/* We do this many searches before trying to keep the search latch over calls
301
from the user. If we notice someone waiting for the latch, we again set this
302
much timeout. This is to reduce contention. */
304
#define BTR_SEA_TIMEOUT 10000
307
#include "btr0sea.ic"
added
removed
include/btr0sea.h
