1
/************************************************************************
2
The index tree adaptive search
6
Created 2/17/1996 Heikki Tuuri
7
*************************************************************************/
15
#include "dict0dict.h"
16
#include "btr0types.h"
20
/*********************************************************************
21
Creates and initializes the adaptive search system at a database start. */
24
btr_search_sys_create(
25
/*==================*/
26
ulint hash_size); /* in: hash index hash table size */
28
/************************************************************************
29
Disable the adaptive hash search system and empty the index. */
32
btr_search_disable(void);
33
/*====================*/
34
/************************************************************************
35
Enable the adaptive hash search system. */
38
btr_search_enable(void);
39
/*====================*/
41
/************************************************************************
42
Returns search info for an index. */
47
/* out: search info; search mutex reserved */
48
dict_index_t* index); /* in: index */
49
/*********************************************************************
50
Creates and initializes a search info struct. */
53
btr_search_info_create(
54
/*===================*/
55
/* out, own: search info struct */
56
mem_heap_t* heap); /* in: heap where created */
57
/*************************************************************************
58
Updates the search info. */
61
btr_search_info_update(
62
/*===================*/
63
dict_index_t* index, /* in: index of the cursor */
64
btr_cur_t* cursor);/* in: cursor which was just positioned */
65
/**********************************************************************
66
Tries to guess the right search position based on the hash search info
67
of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts,
68
and the function returns TRUE, then cursor->up_match and cursor->low_match
69
both have sensible values. */
72
btr_search_guess_on_hash(
73
/*=====================*/
74
/* out: TRUE if succeeded */
75
dict_index_t* index, /* in: index */
76
btr_search_t* info, /* in: index search info */
77
const dtuple_t* tuple, /* in: logical record */
78
ulint mode, /* in: PAGE_CUR_L, ... */
79
ulint latch_mode, /* in: BTR_SEARCH_LEAF, ... */
80
btr_cur_t* cursor, /* out: tree cursor */
81
ulint has_search_latch,/* in: latch mode the caller
82
currently has on btr_search_latch:
83
RW_S_LATCH, RW_X_LATCH, or 0 */
84
mtr_t* mtr); /* in: mtr */
85
/************************************************************************
86
Moves or deletes hash entries for moved records. If new_page is already hashed,
87
then the hash index for page, if any, is dropped. If new_page is not hashed,
88
and page is hashed, then a new hash index is built to new_page with the same
89
parameters as page (this often happens when a page is split). */
92
btr_search_move_or_delete_hash_entries(
93
/*===================================*/
94
buf_block_t* new_block, /* in: records are copied
96
buf_block_t* block, /* in: index page from which
97
records were copied, and the
98
copied records will be deleted
100
dict_index_t* index); /* in: record descriptor */
101
/************************************************************************
102
Drops a page hash index. */
105
btr_search_drop_page_hash_index(
106
/*============================*/
107
buf_block_t* block); /* in: block containing index page,
108
s- or x-latched, or an index page
109
for which we know that
110
block->buf_fix_count == 0 */
111
/************************************************************************
112
Drops a page hash index when a page is freed from a fseg to the file system.
113
Drops possible hash index if the page happens to be in the buffer pool. */
116
btr_search_drop_page_hash_when_freed(
117
/*=================================*/
118
ulint space, /* in: space id */
119
ulint zip_size, /* in: compressed page size in bytes
120
or 0 for uncompressed pages */
121
ulint page_no); /* in: page number */
122
/************************************************************************
123
Updates the page hash index when a single record is inserted on a page. */
126
btr_search_update_hash_node_on_insert(
127
/*==================================*/
128
btr_cur_t* cursor);/* in: cursor which was positioned to the
129
place to insert using btr_cur_search_...,
130
and the new record has been inserted next
132
/************************************************************************
133
Updates the page hash index when a single record is inserted on a page. */
136
btr_search_update_hash_on_insert(
137
/*=============================*/
138
btr_cur_t* cursor);/* in: cursor which was positioned to the
139
place to insert using btr_cur_search_...,
140
and the new record has been inserted next
142
/************************************************************************
143
Updates the page hash index when a single record is deleted from a page. */
146
btr_search_update_hash_on_delete(
147
/*=============================*/
148
btr_cur_t* cursor);/* in: cursor which was positioned on the
149
record to delete using btr_cur_search_...,
150
the record is not yet deleted */
151
/************************************************************************
152
Validates the search system. */
155
btr_search_validate(void);
156
/*======================*/
157
/* out: TRUE if ok */
159
/* Flag: has the search system been disabled? */
160
extern ibool btr_search_disabled;
162
/* The search info struct in an index */
164
struct btr_search_struct{
165
/* The following fields are not protected by any latch.
166
Unfortunately, this means that they must be aligned to
167
the machine word, i.e., they cannot be turned into bit-fields. */
168
buf_block_t* root_guess;/* the root page frame when it was last time
170
ulint hash_analysis; /* when this exceeds BTR_SEARCH_HASH_ANALYSIS,
171
the hash analysis starts; this is reset if no
173
ibool last_hash_succ; /* TRUE if the last search would have
174
succeeded, or did succeed, using the hash
175
index; NOTE that the value here is not exact:
176
it is not calculated for every search, and the
177
calculation itself is not always accurate! */
178
ulint n_hash_potential;
179
/* number of consecutive searches
180
which would have succeeded, or did succeed,
181
using the hash index;
182
the range is 0 .. BTR_SEARCH_BUILD_LIMIT + 5 */
183
/*----------------------*/
184
ulint n_fields; /* recommended prefix length for hash search:
185
number of full fields */
186
ulint n_bytes; /* recommended prefix: number of bytes in
188
see also BTR_PAGE_MAX_REC_SIZE */
189
ibool left_side; /* TRUE or FALSE, depending on whether
190
the leftmost record of several records with
191
the same prefix should be indexed in the
193
/*----------------------*/
194
#ifdef UNIV_SEARCH_PERF_STAT
195
ulint n_hash_succ; /* number of successful hash searches thus
197
ulint n_hash_fail; /* number of failed hash searches */
198
ulint n_patt_succ; /* number of successful pattern searches thus
200
ulint n_searches; /* number of searches */
201
#endif /* UNIV_SEARCH_PERF_STAT */
203
ulint magic_n; /* magic number */
204
# define BTR_SEARCH_MAGIC_N 1112765
205
#endif /* UNIV_DEBUG */
208
/* The hash index system */
210
typedef struct btr_search_sys_struct btr_search_sys_t;
212
struct btr_search_sys_struct{
213
hash_table_t* hash_index;
216
extern btr_search_sys_t* btr_search_sys;
218
/* The latch protecting the adaptive search system: this latch protects the
220
(2) columns of a record to which we have a pointer in the hash index;
222
but does NOT protect:
224
(3) next record offset field in a record;
225
(4) next or previous records on the same page.
227
Bear in mind (3) and (4) when using the hash index.
230
extern rw_lock_t* btr_search_latch_temp;
232
#define btr_search_latch (*btr_search_latch_temp)
234
#ifdef UNIV_SEARCH_PERF_STAT
235
extern ulint btr_search_n_succ;
236
extern ulint btr_search_n_hash_fail;
237
#endif /* UNIV_SEARCH_PERF_STAT */
239
/* After change in n_fields or n_bytes in info, this many rounds are waited
240
before starting the hash analysis again: this is to save CPU time when there
241
is no hope in building a hash index. */
243
#define BTR_SEARCH_HASH_ANALYSIS 17
245
/* Limit of consecutive searches for trying a search shortcut on the search
248
#define BTR_SEARCH_ON_PATTERN_LIMIT 3
250
/* Limit of consecutive searches for trying a search shortcut using the hash
253
#define BTR_SEARCH_ON_HASH_LIMIT 3
255
/* We do this many searches before trying to keep the search latch over calls
256
from MySQL. If we notice someone waiting for the latch, we again set this
257
much timeout. This is to reduce contention. */
259
#define BTR_SEA_TIMEOUT 10000
262
#include "btr0sea.ic"
added
removed
include/btr0sea.h
