MySQL 9.0.0
Source Code Documentation
btr0btr.h
Go to the documentation of this file.
1/*****************************************************************************
2
3Copyright (c) 1994, 2024, Oracle and/or its affiliates.
4Copyright (c) 2012, Facebook Inc.
5
6This program is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License, version 2.0, as published by the
8Free Software Foundation.
9
10This program is designed to work with certain software (including
11but not limited to OpenSSL) that is licensed under separate terms,
12as designated in a particular file or component or in included license
13documentation. The authors of MySQL hereby grant you an additional
14permission to link the program and your derivative works with the
15separately licensed software that they have either included with
16the program or referenced in the documentation.
17
18This program is distributed in the hope that it will be useful, but WITHOUT
19ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
20FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
21for more details.
22
23You should have received a copy of the GNU General Public License along with
24this program; if not, write to the Free Software Foundation, Inc.,
2551 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
26
27*****************************************************************************/
28
29/** @file include/btr0btr.h
30 The B-tree
31
32 Created 6/2/1994 Heikki Tuuri
33 *******************************************************/
34
35#ifndef btr0btr_h
36#define btr0btr_h
37
38#include "btr0types.h"
39#include "data0data.h"
40#include "dict0dict.h"
41#include "gis0type.h"
42#include "mtr0mtr.h"
43#include "page0cur.h"
44#include "univ.i"
45
46/** Maximum record size which can be stored on a page, without using the
47special big record storage structure */
48#define BTR_PAGE_MAX_REC_SIZE (UNIV_PAGE_SIZE / 2 - 200)
49
50/** @brief Maximum depth of a B-tree in InnoDB.
51
52Note that this isn't a maximum as such; none of the tree operations
53avoid producing trees bigger than this. It is instead a "max depth
54that other code must work with", useful for e.g. fixed-size arrays
55that must store some information about each level in a tree. In other
56words: if a B-tree with bigger depth than this is encountered, it is
57not acceptable for it to lead to mysterious memory corruption, but it
58is acceptable for the program to die with a clear assert failure. */
59constexpr uint32_t BTR_MAX_LEVELS = 100;
60
61/** Latching modes for btr_cur_search_to_nth_level(). */
62enum btr_latch_mode : size_t {
63 /** Search a record on a leaf page and S-latch it. */
65 /** (Prepare to) modify a record on a leaf page and X-latch it. */
67 /** Obtain no latches. */
69 /** Start modifying the entire B-tree. */
71 /** Continue modifying the entire B-tree. */
73 /** Search the previous record. */
75 /** Modify the previous record. */
77 /** Start searching the entire B-tree. */
79 /** Continue searching the entire B-tree. */
81};
82
83/* BTR_INSERT, BTR_DELETE and BTR_DELETE_MARK are mutually exclusive. */
84
85/** If this is ORed to btr_latch_mode, it means that the search tuple
86will be inserted to the index, at the searched position.
87When the record is not in the buffer pool, try to use the insert buffer. */
88constexpr size_t BTR_INSERT = 512;
89
90/** This flag ORed to btr_latch_mode says that we do the search in query
91optimization */
92constexpr size_t BTR_ESTIMATE = 1024;
93
94/** This flag ORed to BTR_INSERT says that we can ignore possible
95UNIQUE definition on secondary indexes when we decide if we can use
96the insert buffer to speed up inserts */
97constexpr size_t BTR_IGNORE_SEC_UNIQUE = 2048;
98
99/** Try to delete mark the record at the searched position using the
100insert/delete buffer when the record is not in the buffer pool. */
101constexpr size_t BTR_DELETE_MARK = 4096;
102
103/** Try to purge the record at the searched position using the insert/delete
104buffer when the record is not in the buffer pool. */
105constexpr size_t BTR_DELETE = 8192;
106
107/** In the case of BTR_SEARCH_LEAF or BTR_MODIFY_LEAF, the caller is
108already holding an S latch on the index tree */
109constexpr size_t BTR_ALREADY_S_LATCHED = 16384;
110
111/** In the case of BTR_MODIFY_TREE, the caller specifies the intention
112to insert record only. It is used to optimize block->lock range.*/
113constexpr size_t BTR_LATCH_FOR_INSERT = 32768;
114
115/** In the case of BTR_MODIFY_TREE, the caller specifies the intention
116to delete record only. It is used to optimize block->lock range.*/
117constexpr size_t BTR_LATCH_FOR_DELETE = 65536;
118
119/** This flag is for undo insert of rtree. For rtree, we need this flag
120to find proper rec to undo insert.*/
121constexpr size_t BTR_RTREE_UNDO_INS = 131072;
122
123/** In the case of BTR_MODIFY_LEAF, the caller intends to allocate or
124free the pages of externally stored fields. */
125constexpr size_t BTR_MODIFY_EXTERNAL = 262144;
126
127/** Try to delete mark the record at the searched position when the
128record is in spatial index */
129constexpr size_t BTR_RTREE_DELETE_MARK = 524288;
130
131using Page_range_t = std::pair<page_no_t, page_no_t>;
132
134 return latch_mode &
139}
140
142 return latch_mode &
144}
145
146/** Report that an index page is corrupted. */
147void btr_corruption_report(const buf_block_t *block, /*!< in: corrupted block */
148 const dict_index_t *index) /*!< in: index tree */
149 UNIV_COLD;
150
151/** Assert that a B-tree page is not corrupted.
152@param block buffer block containing a B-tree page
153@param index the B-tree index */
154inline void btr_assert_not_corrupted(const buf_block_t *block,
155 const dict_index_t *index) {
156 if (page_is_comp(buf_block_get_frame(block)) !=
157 dict_table_is_comp((index)->table)) {
158 btr_corruption_report(block, index);
159 ut_error;
160 }
161}
162
163/** Gets the root node of a tree and sx-latches it for segment access.
164 @return root page, sx-latched */
165page_t *btr_root_get(const dict_index_t *index, /*!< in: index tree */
166 mtr_t *mtr); /*!< in: mtr */
167
168/** Checks and adjusts the root node of a tree during IMPORT TABLESPACE.
169 @return error code, or DB_SUCCESS */
171 const dict_index_t *index); /*!< in: index tree */
172
173/** Gets the height of the B-tree (the level of the root, when the leaf
174 level is assumed to be 0). The caller must hold an S or X latch on
175 the index.
176 @return tree height (level of the root) */
177[[nodiscard]] ulint btr_height_get(dict_index_t *index, /*!< in: index tree */
178 mtr_t *mtr); /*!< in/out: mini-transaction */
179
180#ifndef UNIV_HOTBACKUP
181/** Gets a buffer page and declares its latching order level.
182@param[in] page_id Page id
183@param[in] page_size Page size
184@param[in] mode Latch mode
185@param[in] location Location from where this method is called.
186@param[in] index Index tree, may be NULL if it is not an insert
187 buffer tree
188@param[in,out] mtr Mini-transaction
189@return block */
191 const page_id_t &page_id, const page_size_t &page_size, ulint mode,
192 ut::Location location, IF_DEBUG(const dict_index_t *index, ) mtr_t *mtr);
193
194/** Gets a buffer page and declares its latching order level.
195@param page_id Tablespace/page identifier
196@param page_size Page size
197@param mode Latch mode
198@param[in] location Location from where this method is called.
199@param index Index tree, may be NULL if not the insert buffer tree
200@param mtr Mini-transaction handle
201@return the block descriptor */
202static inline buf_block_t *btr_block_get(const page_id_t &page_id,
203 const page_size_t &page_size,
204 ulint mode, ut::Location location,
205 const dict_index_t *index,
206 mtr_t *mtr) {
207 return btr_block_get_func(page_id, page_size, mode, location,
208 IF_DEBUG(index, ) mtr);
209}
210
211#endif /* !UNIV_HOTBACKUP */
212
213/** Gets the index id field of a page.
214 @return index id */
215[[nodiscard]] static inline space_index_t btr_page_get_index_id(
216 const page_t *page); /*!< in: index page */
217/** Gets the node level field in an index page.
218 @param[in] page index page
219 @return level, leaf level == 0 */
220[[nodiscard]] static inline ulint btr_page_get_level(const page_t *page);
221/** Gets the next index page number.
222@param[in] page Index page.
223@param[in] mtr Mini-transaction handle.
224@return next page number */
225[[nodiscard]] static inline page_no_t btr_page_get_next(const page_t *page,
226 mtr_t *mtr);
227/** Gets the previous index page number.
228@param[in] page Index page.
229@param[in] mtr Mini-transaction handle.
230@return prev page number */
231[[nodiscard]] static inline page_no_t btr_page_get_prev(const page_t *page,
232 mtr_t *mtr);
233
234#ifndef UNIV_HOTBACKUP
235/** Releases the latch on a leaf page and bufferunfixes it.
236@param[in] block buffer block
237@param[in] latch_mode BTR_SEARCH_LEAF or BTR_MODIFY_LEAF
238@param[in] mtr mtr */
239static inline void btr_leaf_page_release(buf_block_t *block, ulint latch_mode,
240 mtr_t *mtr);
241#endif /* !UNIV_HOTBACKUP */
242
243/** Gets the child node file address in a node pointer.
244 NOTE: the offsets array must contain all offsets for the record since
245 we read the last field according to offsets and assume that it contains
246 the child page number. In other words offsets must have been retrieved
247 with rec_get_offsets(n_fields=ULINT_UNDEFINED).
248 @param[in] rec node Pointer record
249 @param[in] offsets Array returned by rec_get_offsets()
250 @return child node address */
251[[nodiscard]] static inline page_no_t btr_node_ptr_get_child_page_no(
252 const rec_t *rec, const ulint *offsets);
253
254/** Returns the child page of a node pointer and sx-latches it.
255@param[in] node_ptr node pointer
256@param[in] index index
257@param[in] offsets array returned by rec_get_offsets()
258@param[in] mtr mtr
259@param[in] type latch type
260@return child page, latched as per the type */
262 const ulint *offsets, mtr_t *mtr,
264
265/** Create the root node for a new index tree.
266@param[in] type Type of the index
267@param[in] space Space where created
268@param[in] index_id Index id
269@param[in] index Index tree
270@param[in,out] mtr Mini-transaction
271@return page number of the created root
272@retval FIL_NULL if did not succeed */
274 dict_index_t *index, mtr_t *mtr);
275
276/** Free a persistent index tree if it exists.
277@param[in] page_id Root page id
278@param[in] page_size Page size
279@param[in] index_id PAGE_INDEX_ID contents
280@param[in,out] mtr Mini-transaction */
281void btr_free_if_exists(const page_id_t &page_id, const page_size_t &page_size,
282 space_index_t index_id, mtr_t *mtr);
283
284/** Free an index tree in a temporary tablespace.
285@param[in] page_id root page id
286@param[in] page_size page size */
287void btr_free(const page_id_t &page_id, const page_size_t &page_size);
288
289/** Truncate an index tree. We just free all except the root.
290Currently, this function is only specific for clustered indexes and the only
291caller is DDTableBuffer which manages a table with only a clustered index.
292It is up to the caller to ensure atomicity and to ensure correct recovery by
293calling btr_truncate_recover().
294@param[in] index clustered index */
295void btr_truncate(const dict_index_t *index);
296
297/** Recovery function for btr_truncate. We will check if there is a
298crash during btr_truncate, if so, do recover it, if not, do nothing.
299@param[in] index clustered index */
300void btr_truncate_recover(const dict_index_t *index);
301
302/** Makes tree one level higher by splitting the root, and inserts
303 the tuple. It is assumed that mtr contains an x-latch on the tree.
304 NOTE that the operation of this function must always succeed,
305 we cannot reverse it: therefore enough free disk space must be
306 guaranteed to be available before this function is called.
307 @return inserted record */
308[[nodiscard]] rec_t *btr_root_raise_and_insert(
309 uint32_t flags, /*!< in: undo logging and locking flags */
310 btr_cur_t *cursor, /*!< in: cursor at which to insert: must be
311 on the root page; when the function returns,
312 the cursor is positioned on the predecessor
313 of the inserted record */
314 ulint **offsets, /*!< out: offsets on inserted record */
315 mem_heap_t **heap, /*!< in/out: pointer to memory heap
316 that can be emptied, or NULL */
317 const dtuple_t *tuple, /*!< in: tuple to insert */
318 mtr_t *mtr); /*!< in: mtr */
319/** Reorganizes an index page.
320
321IMPORTANT: On success, the caller will have to update IBUF_BITMAP_FREE
322if this is a compressed leaf page in a secondary index. This has to
323be done either within the same mini-transaction, or by invoking
324ibuf_reset_free_bits() before mtr_commit(). On uncompressed pages,
325IBUF_BITMAP_FREE is unaffected by reorganization.
326
327@param[in] recovery True if called in recovery: locks should not be updated,
328i.e., there cannot exist locks on the page, and a hash index should not be
329dropped: it cannot exist.
330@param[in] z_level Compression level to be used if dealing with compressed
331page.
332@param[in,out] cursor Page cursor.
333@param[in] index The index tree of the page.
334@param[in,out] mtr Mini-transaction
335@retval true if the operation was successful
336@retval false if it is a compressed page, and re-compression failed */
337[[nodiscard]] bool btr_page_reorganize_low(bool recovery, ulint z_level,
338 page_cur_t *cursor,
339 dict_index_t *index, mtr_t *mtr);
340
341/** Reorganizes an index page.
342
343IMPORTANT: On success, the caller will have to update IBUF_BITMAP_FREE
344if this is a compressed leaf page in a secondary index. This has to
345be done either within the same mini-transaction, or by invoking
346ibuf_reset_free_bits() before mtr_commit(). On uncompressed pages,
347IBUF_BITMAP_FREE is unaffected by reorganization.
348
349@param[in,out] cursor Page cursor
350@param[in] index The index tree of the page
351@param[in,out] mtr Mini-transaction
352@retval true if the operation was successful
353@retval false if it is a compressed page, and recompression failed */
354bool btr_page_reorganize(page_cur_t *cursor, dict_index_t *index, mtr_t *mtr);
355
356/** Decides if the page should be split at the convergence point of
357 inserts converging to left.
358 @return true if split recommended */
359[[nodiscard]] bool btr_page_get_split_rec_to_left(
360 btr_cur_t *cursor, /*!< in: cursor at which to insert */
361 rec_t **split_rec); /*!< out: if split recommended,
362 the first record on upper half page,
363 or NULL if tuple should be first */
364/** Decides if the page should be split at the convergence point of
365 inserts converging to right.
366 @return true if split recommended */
367[[nodiscard]] bool btr_page_get_split_rec_to_right(
368 btr_cur_t *cursor, /*!< in: cursor at which to insert */
369 rec_t **split_rec); /*!< out: if split recommended,
370 the first record on upper half page,
371 or NULL if tuple should be first */
372
373/** Splits an index page to halves and inserts the tuple. It is assumed
374 that mtr holds an x-latch to the index tree. NOTE: the tree x-latch is
375 released within this function! NOTE that the operation of this
376 function must always succeed, we cannot reverse it: therefore enough
377 free disk space (2 pages) must be guaranteed to be available before
378 this function is called.
379
380 @return inserted record */
381[[nodiscard]] rec_t *btr_page_split_and_insert(
382 uint32_t flags, /*!< in: undo logging and locking flags */
383 btr_cur_t *cursor, /*!< in: cursor at which to insert; when the
384 function returns, the cursor is positioned
385 on the predecessor of the inserted record */
386 ulint **offsets, /*!< out: offsets on inserted record */
387 mem_heap_t **heap, /*!< in/out: pointer to memory heap
388 that can be emptied, or NULL */
389 const dtuple_t *tuple, /*!< in: tuple to insert */
390 mtr_t *mtr); /*!< in: mtr */
391/** Inserts a data tuple to a tree on a non-leaf level. It is assumed
392 that mtr holds an x-latch on the tree.
393 @param[in] flags undo logging and locking flags
394 @param[in] index index
395 @param[in] level level, must be > 0
396 @param[in] tuple the record to be inserted
397 @param[in] location location where called
398 @param[in] mtr mtr */
400 ulint level, dtuple_t *tuple,
401 ut::Location location, mtr_t *mtr);
402
403/** Sets a record as the predefined minimum record.
404@param[in,out] rec Record
405@param[in] mtr Mini-transaction
406*/
407void btr_set_min_rec_mark(rec_t *rec, mtr_t *mtr);
408
409/** Removes a record as the predefined minimum record.
410@param[in] block buffer block containing the record.
411@param[in] rec the record who info bits will be modified by clearing
412 the REC_INFO_MIN_REC_FLAG bit.
413@param[in] mtr mini transaction context. */
414void btr_unset_min_rec_mark(buf_block_t *block, rec_t *rec, mtr_t *mtr);
415
416/** Deletes on the upper level the node pointer to a page.
417@param[in] index Index tree
418@param[in] block Page whose node pointer is deleted
419@param[in] mtr Mini-transaction
420*/
421void btr_node_ptr_delete(dict_index_t *index, buf_block_t *block, mtr_t *mtr);
422#ifdef UNIV_DEBUG
423/** Asserts that the node pointer to a page is appropriate.
424 @param[in] index index tree
425 @param[in] block index page
426 @param[in] mtr mtr
427 @return true */
428bool btr_check_node_ptr(dict_index_t *index, buf_block_t *block, mtr_t *mtr);
429#endif /* UNIV_DEBUG */
430/** Tries to merge the page first to the left immediate brother if such a
431 brother exists, and the node pointers to the current page and to the brother
432 reside on the same page. If the left brother does not satisfy these
433 conditions, looks at the right brother. If the page is the only one on that
434 level lifts the records of the page to the father page, thus reducing the
435 tree height. It is assumed that mtr holds an x-latch on the tree and on the
436 page. If cursor is on the leaf level, mtr must also hold x-latches to the
437 brothers, if they exist.
438 @param[in,out] cursor cursor on the page to merge or lift; the page must not be
439 empty: when deleting records, use btr_discard_page() if the page would become
440 empty
441 @param[in] adjust true if should adjust the cursor position even if compression
442 occurs.
443 @param[in,out] mtr mini-transaction
444 @return true on success */
445bool btr_compress(btr_cur_t *cursor, bool adjust, mtr_t *mtr);
446/** Discards a page from a B-tree. This is used to remove the last record from
447 a B-tree page: the whole page must be removed at the same time. This cannot
448 be used for the root page, which is allowed to be empty. */
449void btr_discard_page(btr_cur_t *cursor, /*!< in: cursor on the page to
450 discard: not on the root page */
451 mtr_t *mtr); /*!< in: mtr */
452/** Parses the redo log record for setting an index record as the predefined
453 minimum record.
454 @return end of log record or NULL */
455[[nodiscard]] const byte *btr_parse_set_min_rec_mark(
456 const byte *ptr, /*!< in: buffer */
457 const byte *end_ptr, /*!< in: buffer end */
458 ulint comp, /*!< in: nonzero=compact page format */
459 page_t *page, /*!< in: page or NULL */
460 mtr_t *mtr); /*!< in: mtr or NULL */
461/** Parses a redo log record of reorganizing a page.
462 @return end of log record or NULL */
463[[nodiscard]] const byte *btr_parse_page_reorganize(
464 const byte *ptr, /*!< in: buffer */
465 const byte *end_ptr, /*!< in: buffer end */
466 dict_index_t *index, /*!< in: record descriptor */
467 bool compressed, /*!< in: true if compressed page */
468 buf_block_t *block, /*!< in: page to be reorganized, or NULL */
469 mtr_t *mtr); /*!< in: mtr or NULL */
470/** Gets the number of pages in a B-tree.
471 @return number of pages, or ULINT_UNDEFINED if the index is unavailable */
472[[nodiscard]] ulint btr_get_size(
473 dict_index_t *index, /*!< in: index */
474 ulint flag, /*!< in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */
475 mtr_t *mtr); /*!< in/out: mini-transaction where index
476 is s-latched */
477
478#ifdef UNIV_DEBUG
479#define btr_page_alloc(index, hint_page_no, file_direction, level, mtr, \
480 init_mtr) \
481 btr_page_alloc_priv(index, hint_page_no, file_direction, level, mtr, \
482 init_mtr, UT_LOCATION_HERE)
483#else /* UNIV_DEBUG */
484#define btr_page_alloc(index, hint_page_no, file_direction, level, mtr, \
485 init_mtr) \
486 btr_page_alloc_priv(index, hint_page_no, file_direction, level, mtr, init_mtr)
487#endif /* UNIV_DEBUG */
488
489/** Allocates a new file page to be used in an index tree. NOTE: we assume
490that the caller has made the reservation for free extents!
491@param[in] index Index tree
492@param[in] hint_page_no Hint of a good page
493@param[in] file_direction Direction where a possible page split is made
494@param[in] level Level where the page is placed in the tree
495@param[in,out] mtr Mini-transaction for the allocation
496@param[in,out] init_mtr Mini-transaction for x-latching and initializing the
497page
498@param[in] loc debug only parameter providing caller source location.
499@retval NULL if no page could be allocated
500@retval block, rw_lock_x_lock_count(&block->lock) == 1 if allocation succeeded
501(init_mtr == mtr, or the page was not previously freed in mtr),
502returned block is not allocated nor initialized otherwise */
503[[nodiscard]] buf_block_t *btr_page_alloc_priv(
504 dict_index_t *index, page_no_t hint_page_no, byte file_direction,
505 ulint level, mtr_t *mtr, mtr_t *init_mtr IF_DEBUG(, const ut::Location &loc)
506
507);
508
509/** Allocates all pages of one extent to be used in an index tree.
510@param[in] index the index for which pages are allocated.
511@param[in] is_leaf true if leaf segment and false if non-leaf segment
512@param[out] page_range All pages within this pair of page numbers are
513allocated for this B-tree. The page_range.first is part of the range, while the
514page_range.second is not part of the range.
515@param[in] mtr mini transaction context for this operation.
516@return DB_SUCCESS on success, error code on failure. */
517[[nodiscard]] dberr_t btr_extent_alloc(const dict_index_t *const index,
518 bool is_leaf, Page_range_t &page_range,
519 mtr_t *mtr);
520
521/** Frees a file page used in an index tree. NOTE: cannot free field external
522 storage pages because the page must contain info on its level. */
523void btr_page_free(dict_index_t *index, /*!< in: index tree */
524 buf_block_t *block, /*!< in: block to be freed, x-latched */
525 mtr_t *mtr); /*!< in: mtr */
526/** Creates a new index page (not the root, and also not
527 used in page reorganization). @see btr_page_empty(). */
528void btr_page_create(
529 buf_block_t *block, /*!< in/out: page to be created */
530 page_zip_des_t *page_zip, /*!< in/out: compressed page, or NULL */
531 dict_index_t *index, /*!< in: index */
532 ulint level, /*!< in: the B-tree level of the page */
533 mtr_t *mtr); /*!< in: mtr */
534
535/** Frees a file page used in an index tree. Can be used also to BLOB
536 external storage pages.
537@param[in] index the index to which the page belongs
538@param[in] block block to be freed, x-latched
539@param[in] level page level (ULINT_UNDEFINED=BLOB)
540@param[in] mtr mini transaction context. */
541void btr_page_free_low(dict_index_t *index, buf_block_t *block, ulint level,
542 mtr_t *mtr);
543
544/** Gets the root node of a tree and x- or s-latches it.
545 @return root page, x- or s-latched */
547 const dict_index_t *index, /*!< in: index tree */
548 ulint mode, /*!< in: either RW_S_LATCH
549 or RW_X_LATCH */
550 mtr_t *mtr); /*!< in: mtr */
551
552/** Prints size info of a B-tree. */
553void btr_print_size(dict_index_t *index); /*!< in: index tree */
554
555/** Prints directories and other info of all nodes in the index.
556@param[in] index the index to be printed.
557@param[in] width number of entries to print from start and end. */
559
560/** Checks the size and number of fields in a record based on the definition of
561the index.
562 @return true if ok */
563[[nodiscard]] bool btr_index_rec_validate(
564 const rec_t *rec, /*!< in: index record */
565 const dict_index_t *index, /*!< in: index */
566 bool dump_on_error); /*!< in: true if the function
567 should print hex dump of
568 record and page on error */
569/** Checks the consistency of an index tree.
570 @return true if ok */
571[[nodiscard]] bool btr_validate_index(
572 dict_index_t *index, /*!< in: index */
573 const trx_t *trx, /*!< in: transaction or 0 */
574 bool lockout); /*!< in: true if X-latch index is intended */
575
576/** Creates SDI index and stores the root page numbers in page 1 & 2
577@param[in] space_id tablespace id
578@param[in] dict_locked true if dict_sys mutex is acquired
579@return DB_SUCCESS on success, else DB_ERROR on failure */
580dberr_t btr_sdi_create_index(space_id_t space_id, bool dict_locked);
581
582constexpr uint32_t BTR_N_LEAF_PAGES = 1;
583constexpr uint32_t BTR_TOTAL_SIZE = 2;
584
585/** Check if the given index is empty. An index is considered empty if it
586has only the root page with no user records, including del-marked records.
587@param[in] index index
588@return true if index is empty, false otherwise. */
589bool btr_is_index_empty(const dict_index_t *index);
590
591#ifdef UNIV_DEBUG
592/** Does a breadth first traversal (BFT) of the B-tree, and invokes the
593callback for each of the B-tree nodes. */
594struct BFT {
595 struct Callback {
598 size_t m_nrows;
599 size_t m_level;
600 std::ostream &print(std::ostream &out) const;
601 };
602 void init(size_t max_level) { m_data.resize(max_level); }
603 void operator()(buf_block_t *block);
604 std::ostream &print(std::ostream &out) const;
605
606 public:
608
609 private:
610 std::vector<std::list<Page_details>> m_data;
611 };
612 BFT(const dict_index_t *index, Callback &cb);
613 void traverse();
614
615 const dict_index_t *index() const { return m_index; }
616
617 private:
618 void children_to_visit(buf_block_t *block);
620 std::list<page_no_t> m_pages_to_visit;
623};
624
625inline std::ostream &operator<<(std::ostream &out,
626 const BFT::Callback::Page_details &obj) {
627 return obj.print(out);
628}
629
630inline std::ostream &operator<<(std::ostream &out, const BFT::Callback &obj) {
631 return obj.print(out);
632}
633
634#endif /* UNIV_DEBUG */
635
636/** NOTE - Changing this from the original number of 50 to 45 as
637insert_debug.test was failing in ASAN build because of a stack overflow issue.
638It was found that rtr_info_t was taking up a lot of stack space in the function
639btr_insert_on_non_leaf_level_func which is part of the recursive stack
640trace. */
641/** Maximum B-tree page level (not really a hard limit). Used in debug
642 assertions in btr_page_set_level and btr_page_get_level */
643constexpr uint32_t BTR_MAX_NODE_LEVEL = 45;
644#include "btr0btr.ic"
645
646#endif
uint32_t space_id_t
Tablespace identifier.
Definition: api0api.h:47
uint32_t page_no_t
Page number.
Definition: api0api.h:45
bool btr_check_node_ptr(dict_index_t *index, buf_block_t *block, mtr_t *mtr)
Asserts that the node pointer to a page is appropriate.
Definition: btr0btr.cc:3817
constexpr ulint BTR_LATCH_MODE_WITHOUT_FLAGS(ulint latch_mode)
Definition: btr0btr.h:133
bool btr_index_rec_validate(const rec_t *rec, const dict_index_t *index, bool dump_on_error)
Checks the size and number of fields in a record based on the definition of the index.
Definition: btr0btr.cc:3879
std::ostream & operator<<(std::ostream &out, const BFT::Callback::Page_details &obj)
Definition: btr0btr.h:625
ulint btr_create(ulint type, space_id_t space, space_index_t index_id, dict_index_t *index, mtr_t *mtr)
Create the root node for a new index tree.
Definition: btr0btr.cc:858
void btr_truncate(const dict_index_t *index)
Truncate an index tree.
Definition: btr0btr.cc:1073
rec_t * btr_root_raise_and_insert(uint32_t flags, btr_cur_t *cursor, ulint **offsets, mem_heap_t **heap, const dtuple_t *tuple, mtr_t *mtr)
Makes tree one level higher by splitting the root, and inserts the tuple.
Definition: btr0btr.cc:1482
static space_index_t btr_page_get_index_id(const page_t *page)
Gets the index id field of a page.
void btr_free(const page_id_t &page_id, const page_size_t &page_size)
Free an index tree in a temporary tablespace.
Definition: btr0btr.cc:1052
void btr_free_if_exists(const page_id_t &page_id, const page_size_t &page_size, space_index_t index_id, mtr_t *mtr)
Free a persistent index tree if it exists.
Definition: btr0btr.cc:1036
buf_block_t * btr_root_block_get(const dict_index_t *index, ulint mode, mtr_t *mtr)
Gets the root node of a tree and x- or s-latches it.
Definition: btr0btr.cc:165
bool btr_page_reorganize(page_cur_t *cursor, dict_index_t *index, mtr_t *mtr)
Reorganizes an index page.
Definition: btr0btr.cc:1396
static buf_block_t * btr_block_get(const page_id_t &page_id, const page_size_t &page_size, ulint mode, ut::Location location, const dict_index_t *index, mtr_t *mtr)
Gets a buffer page and declares its latching order level.
Definition: btr0btr.h:202
bool btr_validate_index(dict_index_t *index, const trx_t *trx, bool lockout)
Checks the consistency of an index tree.
Definition: btr0btr.cc:4586
btr_latch_mode
Latching modes for btr_cur_search_to_nth_level().
Definition: btr0btr.h:62
@ BTR_CONT_MODIFY_TREE
Continue modifying the entire B-tree.
Definition: btr0btr.h:72
@ BTR_MODIFY_TREE
Start modifying the entire B-tree.
Definition: btr0btr.h:70
@ BTR_MODIFY_LEAF
(Prepare to) modify a record on a leaf page and X-latch it.
Definition: btr0btr.h:66
@ BTR_SEARCH_PREV
Search the previous record.
Definition: btr0btr.h:74
@ BTR_NO_LATCHES
Obtain no latches.
Definition: btr0btr.h:68
@ BTR_SEARCH_LEAF
Search a record on a leaf page and S-latch it.
Definition: btr0btr.h:64
@ BTR_MODIFY_PREV
Modify the previous record.
Definition: btr0btr.h:76
@ BTR_CONT_SEARCH_TREE
Continue searching the entire B-tree.
Definition: btr0btr.h:80
@ BTR_SEARCH_TREE
Start searching the entire B-tree.
Definition: btr0btr.h:78
bool btr_compress(btr_cur_t *cursor, bool adjust, mtr_t *mtr)
Tries to merge the page first to the left immediate brother if such a brother exists,...
Definition: btr0btr.cc:3023
void btr_unset_min_rec_mark(buf_block_t *block, rec_t *rec, mtr_t *mtr)
Removes a record as the predefined minimum record.
Definition: btr0btr.cc:2802
constexpr size_t BTR_IGNORE_SEC_UNIQUE
This flag ORed to BTR_INSERT says that we can ignore possible UNIQUE definition on secondary indexes ...
Definition: btr0btr.h:97
static buf_block_t * btr_block_get_func(const page_id_t &page_id, const page_size_t &page_size, ulint mode, ut::Location location, const dict_index_t *index, mtr_t *mtr)
Gets a buffer page and declares its latching order level.
dberr_t btr_root_adjust_on_import(const dict_index_t *index)
Checks and adjusts the root node of a tree during IMPORT TABLESPACE.
Definition: btr0btr.cc:260
void btr_page_free_low(dict_index_t *index, buf_block_t *block, ulint level, mtr_t *mtr)
Frees a file page used in an index tree.
Definition: btr0btr.cc:554
ulint BTR_LATCH_MODE_WITHOUT_INTENTION(ulint latch_mode)
Definition: btr0btr.h:141
static page_no_t btr_page_get_prev(const page_t *page, mtr_t *mtr)
Gets the previous index page number.
void btr_truncate_recover(const dict_index_t *index)
Recovery function for btr_truncate.
Definition: btr0btr.cc:1129
bool btr_is_index_empty(const dict_index_t *index)
Check if the given index is empty.
Definition: btr0btr.cc:2819
constexpr size_t BTR_RTREE_DELETE_MARK
Try to delete mark the record at the searched position when the record is in spatial index.
Definition: btr0btr.h:129
rec_t * btr_page_split_and_insert(uint32_t flags, btr_cur_t *cursor, ulint **offsets, mem_heap_t **heap, const dtuple_t *tuple, mtr_t *mtr)
Splits an index page to halves and inserts the tuple.
Definition: btr0btr.cc:2305
constexpr size_t BTR_DELETE
Try to purge the record at the searched position using the insert/delete buffer when the record is no...
Definition: btr0btr.h:105
constexpr size_t BTR_LATCH_FOR_DELETE
In the case of BTR_MODIFY_TREE, the caller specifies the intention to delete record only.
Definition: btr0btr.h:117
ulint btr_get_size(dict_index_t *index, ulint flag, mtr_t *mtr)
Gets the number of pages in a B-tree.
Definition: btr0btr.cc:492
void btr_print_size(dict_index_t *index)
Prints size info of a B-tree.
constexpr size_t BTR_DELETE_MARK
Try to delete mark the record at the searched position using the insert/delete buffer when the record...
Definition: btr0btr.h:101
constexpr size_t BTR_INSERT
If this is ORed to btr_latch_mode, it means that the search tuple will be inserted to the index,...
Definition: btr0btr.h:88
buf_block_t * btr_node_ptr_get_child(const rec_t *node_ptr, dict_index_t *index, const ulint *offsets, mtr_t *mtr, rw_lock_type_t type=RW_SX_LATCH)
Returns the child page of a node pointer and sx-latches it.
Definition: btr0btr.cc:642
constexpr size_t BTR_ALREADY_S_LATCHED
In the case of BTR_SEARCH_LEAF or BTR_MODIFY_LEAF, the caller is already holding an S latch on the in...
Definition: btr0btr.h:109
const byte * btr_parse_set_min_rec_mark(const byte *ptr, const byte *end_ptr, ulint comp, page_t *page, mtr_t *mtr)
Parses the redo log record for setting an index record as the predefined minimum record.
Definition: btr0btr.cc:2756
constexpr size_t BTR_ESTIMATE
This flag ORed to btr_latch_mode says that we do the search in query optimization.
Definition: btr0btr.h:92
void btr_node_ptr_delete(dict_index_t *index, buf_block_t *block, mtr_t *mtr)
Deletes on the upper level the node pointer to a page.
Definition: btr0btr.cc:2834
void btr_print_index(dict_index_t *index, ulint width)
Prints directories and other info of all nodes in the index.
static page_no_t btr_page_get_next(const page_t *page, mtr_t *mtr)
Gets the next index page number.
static ulint btr_page_get_level(const page_t *page)
Gets the node level field in an index page.
bool btr_page_get_split_rec_to_left(btr_cur_t *cursor, rec_t **split_rec)
Decides if the page should be split at the convergence point of inserts converging to left.
Definition: btr0btr.cc:1665
bool btr_page_reorganize_low(bool recovery, ulint z_level, page_cur_t *cursor, dict_index_t *index, mtr_t *mtr)
Reorganizes an index page.
Definition: btr0btr.cc:1167
constexpr size_t BTR_RTREE_UNDO_INS
This flag is for undo insert of rtree.
Definition: btr0btr.h:121
buf_block_t * btr_page_alloc_priv(dict_index_t *index, page_no_t hint_page_no, byte file_direction, ulint level, mtr_t *mtr, mtr_t *init_mtr, const ut::Location &loc)
Allocates a new file page to be used in an index tree.
Definition: btr0btr.cc:470
void btr_insert_on_non_leaf_level(uint32_t flags, dict_index_t *index, ulint level, dtuple_t *tuple, ut::Location location, mtr_t *mtr)
Inserts a data tuple to a tree on a non-leaf level.
Definition: btr0btr.cc:1952
std::pair< page_no_t, page_no_t > Page_range_t
Definition: btr0btr.h:131
void btr_page_create(buf_block_t *block, page_zip_des_t *page_zip, dict_index_t *index, ulint level, mtr_t *mtr)
Creates a new index page (not the root, and also not used in page reorganization).
Definition: btr0btr.cc:332
dberr_t btr_sdi_create_index(space_id_t space_id, bool dict_locked)
Creates SDI index and stores the root page numbers in page 1 & 2.
Definition: btr0btr.cc:4767
constexpr uint32_t BTR_MAX_LEVELS
Maximum depth of a B-tree in InnoDB.
Definition: btr0btr.h:59
constexpr size_t BTR_MODIFY_EXTERNAL
In the case of BTR_MODIFY_LEAF, the caller intends to allocate or free the pages of externally stored...
Definition: btr0btr.h:125
constexpr uint32_t BTR_N_LEAF_PAGES
Definition: btr0btr.h:582
constexpr uint32_t BTR_TOTAL_SIZE
Definition: btr0btr.h:583
void btr_set_min_rec_mark(rec_t *rec, mtr_t *mtr)
Sets a record as the predefined minimum record.
Definition: btr0btr.cc:2784
page_t * btr_root_get(const dict_index_t *index, mtr_t *mtr)
Gets the root node of a tree and sx-latches it for segment access.
Definition: btr0btr.cc:195
constexpr uint32_t BTR_MAX_NODE_LEVEL
NOTE - Changing this from the original number of 50 to 45 as insert_debug.test was failing in ASAN bu...
Definition: btr0btr.h:643
void btr_discard_page(btr_cur_t *cursor, mtr_t *mtr)
Discards a page from a B-tree.
Definition: btr0btr.cc:3558
void btr_corruption_report(const buf_block_t *block, const dict_index_t *index) UNIV_COLD
Report that an index page is corrupted.
Definition: btr0btr.cc:83
constexpr size_t BTR_LATCH_FOR_INSERT
In the case of BTR_MODIFY_TREE, the caller specifies the intention to insert record only.
Definition: btr0btr.h:113
static page_no_t btr_node_ptr_get_child_page_no(const rec_t *rec, const ulint *offsets)
Gets the child node file address in a node pointer.
dberr_t btr_extent_alloc(const dict_index_t *const index, bool is_leaf, Page_range_t &page_range, mtr_t *mtr)
Allocates all pages of one extent to be used in an index tree.
Definition: btr0btr.cc:456
void btr_assert_not_corrupted(const buf_block_t *block, const dict_index_t *index)
Assert that a B-tree page is not corrupted.
Definition: btr0btr.h:154
const byte * btr_parse_page_reorganize(const byte *ptr, const byte *end_ptr, dict_index_t *index, bool compressed, buf_block_t *block, mtr_t *mtr)
Parses a redo log record of reorganizing a page.
Definition: btr0btr.cc:1402
void btr_page_free(dict_index_t *index, buf_block_t *block, mtr_t *mtr)
Frees a file page used in an index tree.
Definition: btr0btr.cc:600
bool btr_page_get_split_rec_to_right(btr_cur_t *cursor, rec_t **split_rec)
Decides if the page should be split at the convergence point of inserts converging to right.
Definition: btr0btr.cc:1703
ulint btr_height_get(dict_index_t *index, mtr_t *mtr)
Gets the height of the B-tree (the level of the root, when the leaf level is assumed to be 0).
Definition: btr0btr.cc:208
static void btr_leaf_page_release(buf_block_t *block, ulint latch_mode, mtr_t *mtr)
Releases the latch on a leaf page and bufferunfixes it.
The B-tree.
The index tree general types.
static buf_frame_t * buf_block_get_frame(const buf_block_t *block)
Gets a pointer to the memory frame of a block.
Page identifier.
Definition: buf0types.h:207
Page size descriptor.
Definition: page0size.h:50
int page
Definition: ctype-mb.cc:1224
SQL data field and tuple.
dberr_t
Definition: db0err.h:39
Data dictionary system.
static bool dict_table_is_comp(const dict_table_t *table)
Check whether the table uses the compact page format.
ib_id_t space_index_t
Index identifier (unique within a tablespace).
Definition: dict0types.h:234
R-tree header file.
static int flags[50]
Definition: hp_test1.cc:40
static int flag
Definition: hp_test1.cc:40
Mini-transaction buffer.
static PFS_engine_table_share_proxy table
Definition: pfs.cc:61
mode
Definition: file_handle.h:61
The page cursor.
static bool page_is_comp(const page_t *page)
Determine whether the page is in new-style compact format.
byte page_t
Type of the index page.
Definition: page0types.h:152
byte rec_t
Definition: rem0types.h:41
required string type
Definition: replication_group_member_actions.proto:34
Definition: btr0btr.h:596
size_t m_level
Definition: btr0btr.h:599
std::ostream & print(std::ostream &out) const
Definition: btr0btr.cc:4832
page_no_t m_page_no
Definition: btr0btr.h:597
size_t m_nrows
Definition: btr0btr.h:598
Definition: btr0btr.h:595
std::ostream & print(std::ostream &out) const
Definition: btr0btr.cc:4838
BFT * m_bft
Definition: btr0btr.h:607
std::vector< std::list< Page_details > > m_data
Definition: btr0btr.h:610
void operator()(buf_block_t *block)
Definition: btr0btr.cc:4914
void init(size_t max_level)
Definition: btr0btr.h:602
Does a breadth first traversal (BFT) of the B-tree, and invokes the callback for each of the B-tree n...
Definition: btr0btr.h:594
std::list< page_no_t > m_pages_to_visit
Definition: btr0btr.h:620
void children_to_visit(buf_block_t *block)
Definition: btr0btr.cc:4878
const dict_index_t * m_index
Definition: btr0btr.h:621
void traverse()
Definition: btr0btr.cc:4898
page_no_t visit_next()
Definition: btr0btr.cc:4869
const dict_index_t * index() const
Definition: btr0btr.h:615
BFT(const dict_index_t *index, Callback &cb)
Definition: btr0btr.cc:4862
Callback & m_callback
Definition: btr0btr.h:622
The tree cursor: the definition appears here only for the compiler to know struct size!
Definition: btr0cur.h:668
The buffer control block structure.
Definition: buf0buf.h:1747
Data structure for an index.
Definition: dict0mem.h:1046
Structure for an SQL data tuple of fields (logical record)
Definition: data0data.h:684
The info structure stored at the beginning of a heap block.
Definition: mem0mem.h:302
Mini-transaction handle and buffer.
Definition: mtr0mtr.h:177
Index page cursor.
Definition: page0cur.h:311
Compressed page descriptor.
Definition: page0types.h:201
Definition: trx0trx.h:684
Definition: ut0core.h:36
rw_lock_type_t
Definition: sync0rw.h:97
@ RW_SX_LATCH
Definition: sync0rw.h:100
@ RW_NO_LATCH
Definition: sync0rw.h:101
@ RW_X_LATCH
Definition: sync0rw.h:99
@ RW_S_LATCH
Definition: sync0rw.h:98
Version control for database, common definitions, and include files.
#define UNIV_COLD
Definition: univ.i:267
#define IF_DEBUG(...)
Definition: univ.i:674
unsigned long int ulint
Definition: univ.i:406
#define ut_error
Abort execution.
Definition: ut0dbg.h:101