~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/innobase/include/btr0sea.h

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
/************************************************************************
 
2
The index tree adaptive search
 
3
 
 
4
(c) 1996 Innobase Oy
 
5
 
 
6
Created 2/17/1996 Heikki Tuuri
 
7
*************************************************************************/
 
8
 
 
9
#ifndef btr0sea_h
 
10
#define btr0sea_h
 
11
 
 
12
#include "univ.i"
 
13
 
 
14
#include "rem0rec.h"
 
15
#include "dict0dict.h"
 
16
#include "btr0types.h"
 
17
#include "mtr0mtr.h"
 
18
#include "ha0ha.h"
 
19
 
 
20
/*********************************************************************
 
21
Creates and initializes the adaptive search system at a database start. */
 
22
 
 
23
void
 
24
btr_search_sys_create(
 
25
/*==================*/
 
26
        ulint   hash_size);     /* in: hash index hash table size */
 
27
/************************************************************************
 
28
Returns search info for an index. */
 
29
UNIV_INLINE
 
30
btr_search_t*
 
31
btr_search_get_info(
 
32
/*================*/
 
33
                                /* out: search info; search mutex reserved */
 
34
        dict_index_t*   index); /* in: index */
 
35
/*********************************************************************
 
36
Creates and initializes a search info struct. */
 
37
 
 
38
btr_search_t*
 
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. */
 
45
UNIV_INLINE
 
46
void
 
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. */
 
56
 
 
57
ibool
 
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). */
 
76
 
 
77
void
 
78
btr_search_move_or_delete_hash_entries(
 
79
/*===================================*/
 
80
        page_t*         new_page,       /* in: records are copied
 
81
                                        to this page */
 
82
        page_t*         page,           /* in: index page */
 
83
        dict_index_t*   index);         /* in: record descriptor */
 
84
/************************************************************************
 
85
Drops a page hash index. */
 
86
 
 
87
void
 
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. */
 
94
 
 
95
void
 
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. */
 
102
 
 
103
void
 
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
 
109
                                to the cursor */
 
110
/************************************************************************
 
111
Updates the page hash index when a single record is inserted on a page. */
 
112
 
 
113
void
 
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
 
119
                                to the cursor */
 
120
/************************************************************************
 
121
Updates the page hash index when a single record is deleted from a page. */
 
122
 
 
123
void
 
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. */
 
131
 
 
132
ibool
 
133
btr_search_validate(void);
 
134
/*======================*/
 
135
                                /* out: TRUE if ok */
 
136
 
 
137
/* The search info struct in an index */
 
138
 
 
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
 
144
                                fetched, or NULL */
 
145
        ulint   hash_analysis;  /* when this exceeds BTR_SEARCH_HASH_ANALYSIS,
 
146
                                the hash analysis starts; this is reset if no
 
147
                                success noticed */
 
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
 
162
                                an incomplete field;
 
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
 
167
                                hash index */
 
168
        /*----------------------*/
 
169
#ifdef UNIV_SEARCH_PERF_STAT
 
170
        ulint   n_hash_succ;    /* number of successful hash searches thus
 
171
                                far */
 
172
        ulint   n_hash_fail;    /* number of failed hash searches */
 
173
        ulint   n_patt_succ;    /* number of successful pattern searches thus
 
174
                                far */
 
175
        ulint   n_searches;     /* number of searches */
 
176
#endif /* UNIV_SEARCH_PERF_STAT */
 
177
#ifdef UNIV_DEBUG
 
178
        ulint   magic_n;        /* magic number */
 
179
# define BTR_SEARCH_MAGIC_N     1112765
 
180
#endif /* UNIV_DEBUG */
 
181
};
 
182
 
 
183
/* The hash index system */
 
184
 
 
185
typedef struct btr_search_sys_struct    btr_search_sys_t;
 
186
 
 
187
struct btr_search_sys_struct{
 
188
        hash_table_t*   hash_index;
 
189
};
 
190
 
 
191
extern btr_search_sys_t*        btr_search_sys;
 
192
 
 
193
/* The latch protecting the adaptive search system: this latch protects the
 
194
(1) hash index;
 
195
(2) columns of a record to which we have a pointer in the hash index;
 
196
 
 
197
but does NOT protect:
 
198
 
 
199
(3) next record offset field in a record;
 
200
(4) next or previous records on the same page.
 
201
 
 
202
Bear in mind (3) and (4) when using the hash index.
 
203
*/
 
204
 
 
205
extern rw_lock_t*       btr_search_latch_temp;
 
206
 
 
207
#define btr_search_latch        (*btr_search_latch_temp)
 
208
 
 
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 */
 
213
 
 
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. */
 
217
 
 
218
#define BTR_SEARCH_HASH_ANALYSIS        17
 
219
 
 
220
/* Limit of consecutive searches for trying a search shortcut on the search
 
221
pattern */
 
222
 
 
223
#define BTR_SEARCH_ON_PATTERN_LIMIT     3
 
224
 
 
225
/* Limit of consecutive searches for trying a search shortcut using the hash
 
226
index */
 
227
 
 
228
#define BTR_SEARCH_ON_HASH_LIMIT        3
 
229
 
 
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. */
 
233
 
 
234
#define BTR_SEA_TIMEOUT                 10000
 
235
 
 
236
#ifndef UNIV_NONINL
 
237
#include "btr0sea.ic"
 
238
#endif
 
239
 
 
240
#endif