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 */
27
/************************************************************************
28
Returns search info for an index. */
33
/* out: search info; search mutex reserved */
34
dict_index_t* index); /* in: index */
35
/*********************************************************************
36
Creates and initializes a search info struct. */
39
btr_search_info_create(
40
/*===================*/
41
/* out, own: search info struct */
42
mem_heap_t* heap); /* in: heap where created */
43
/*************************************************************************
44
Updates the search info. */
47
btr_search_info_update(
48
/*===================*/
49
dict_index_t* index, /* in: index of the cursor */
50
btr_cur_t* cursor);/* in: cursor which was just positioned */
51
/**********************************************************************
52
Tries to guess the right search position based on the hash search info
53
of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts,
54
and the function returns TRUE, then cursor->up_match and cursor->low_match
55
both have sensible values. */
58
btr_search_guess_on_hash(
59
/*=====================*/
60
/* out: TRUE if succeeded */
61
dict_index_t* index, /* in: index */
62
btr_search_t* info, /* in: index search info */
63
dtuple_t* tuple, /* in: logical record */
64
ulint mode, /* in: PAGE_CUR_L, ... */
65
ulint latch_mode, /* in: BTR_SEARCH_LEAF, ... */
66
btr_cur_t* cursor, /* out: tree cursor */
67
ulint has_search_latch,/* in: latch mode the caller
68
currently has on btr_search_latch:
69
RW_S_LATCH, RW_X_LATCH, or 0 */
70
mtr_t* mtr); /* in: mtr */
71
/************************************************************************
72
Moves or deletes hash entries for moved records. If new_page is already hashed,
73
then the hash index for page, if any, is dropped. If new_page is not hashed,
74
and page is hashed, then a new hash index is built to new_page with the same
75
parameters as page (this often happens when a page is split). */
78
btr_search_move_or_delete_hash_entries(
79
/*===================================*/
80
page_t* new_page, /* in: records are copied
82
page_t* page, /* in: index page */
83
dict_index_t* index); /* in: record descriptor */
84
/************************************************************************
85
Drops a page hash index. */
88
btr_search_drop_page_hash_index(
89
/*============================*/
90
page_t* page); /* in: index page, s- or x-latched */
91
/************************************************************************
92
Drops a page hash index when a page is freed from a fseg to the file system.
93
Drops possible hash index if the page happens to be in the buffer pool. */
96
btr_search_drop_page_hash_when_freed(
97
/*=================================*/
98
ulint space, /* in: space id */
99
ulint page_no); /* in: page number */
100
/************************************************************************
101
Updates the page hash index when a single record is inserted on a page. */
104
btr_search_update_hash_node_on_insert(
105
/*==================================*/
106
btr_cur_t* cursor);/* in: cursor which was positioned to the
107
place to insert using btr_cur_search_...,
108
and the new record has been inserted next
110
/************************************************************************
111
Updates the page hash index when a single record is inserted on a page. */
114
btr_search_update_hash_on_insert(
115
/*=============================*/
116
btr_cur_t* cursor);/* in: cursor which was positioned to the
117
place to insert using btr_cur_search_...,
118
and the new record has been inserted next
120
/************************************************************************
121
Updates the page hash index when a single record is deleted from a page. */
124
btr_search_update_hash_on_delete(
125
/*=============================*/
126
btr_cur_t* cursor);/* in: cursor which was positioned on the
127
record to delete using btr_cur_search_...,
128
the record is not yet deleted */
129
/************************************************************************
130
Validates the search system. */
133
btr_search_validate(void);
134
/*======================*/
135
/* out: TRUE if ok */
137
/* The search info struct in an index */
139
struct btr_search_struct{
140
/* The following fields are not protected by any latch.
141
Unfortunately, this means that they must be aligned to
142
the machine word, i.e., they cannot be turned into bit-fields. */
143
page_t* root_guess; /* the root page frame when it was last time
145
ulint hash_analysis; /* when this exceeds BTR_SEARCH_HASH_ANALYSIS,
146
the hash analysis starts; this is reset if no
148
ibool last_hash_succ; /* TRUE if the last search would have
149
succeeded, or did succeed, using the hash
150
index; NOTE that the value here is not exact:
151
it is not calculated for every search, and the
152
calculation itself is not always accurate! */
153
ulint n_hash_potential;
154
/* number of consecutive searches
155
which would have succeeded, or did succeed,
156
using the hash index;
157
the range is 0 .. BTR_SEARCH_BUILD_LIMIT + 5 */
158
/*----------------------*/
159
ulint n_fields; /* recommended prefix length for hash search:
160
number of full fields */
161
ulint n_bytes; /* recommended prefix: number of bytes in
163
see also BTR_PAGE_MAX_REC_SIZE */
164
ibool left_side; /* TRUE or FALSE, depending on whether
165
the leftmost record of several records with
166
the same prefix should be indexed in the
168
/*----------------------*/
169
#ifdef UNIV_SEARCH_PERF_STAT
170
ulint n_hash_succ; /* number of successful hash searches thus
172
ulint n_hash_fail; /* number of failed hash searches */
173
ulint n_patt_succ; /* number of successful pattern searches thus
175
ulint n_searches; /* number of searches */
176
#endif /* UNIV_SEARCH_PERF_STAT */
178
ulint magic_n; /* magic number */
179
# define BTR_SEARCH_MAGIC_N 1112765
180
#endif /* UNIV_DEBUG */
183
/* The hash index system */
185
typedef struct btr_search_sys_struct btr_search_sys_t;
187
struct btr_search_sys_struct{
188
hash_table_t* hash_index;
191
extern btr_search_sys_t* btr_search_sys;
193
/* The latch protecting the adaptive search system: this latch protects the
195
(2) columns of a record to which we have a pointer in the hash index;
197
but does NOT protect:
199
(3) next record offset field in a record;
200
(4) next or previous records on the same page.
202
Bear in mind (3) and (4) when using the hash index.
205
extern rw_lock_t* btr_search_latch_temp;
207
#define btr_search_latch (*btr_search_latch_temp)
209
#ifdef UNIV_SEARCH_PERF_STAT
210
extern ulint btr_search_n_succ;
211
extern ulint btr_search_n_hash_fail;
212
#endif /* UNIV_SEARCH_PERF_STAT */
214
/* After change in n_fields or n_bytes in info, this many rounds are waited
215
before starting the hash analysis again: this is to save CPU time when there
216
is no hope in building a hash index. */
218
#define BTR_SEARCH_HASH_ANALYSIS 17
220
/* Limit of consecutive searches for trying a search shortcut on the search
223
#define BTR_SEARCH_ON_PATTERN_LIMIT 3
225
/* Limit of consecutive searches for trying a search shortcut using the hash
228
#define BTR_SEARCH_ON_HASH_LIMIT 3
230
/* We do this many searches before trying to keep the search latch over calls
231
from MySQL. If we notice someone waiting for the latch, we again set this
232
much timeout. This is to reduce contention. */
234
#define BTR_SEA_TIMEOUT 10000
237
#include "btr0sea.ic"
added
removed
storage/innobase/include/btr0sea.h
