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