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