97
100
#ifdef UNIV_BTR_DEBUG
98
/******************************************************************
99
Checks a file segment header within a B-tree root page. */
101
/**************************************************************//**
102
Checks a file segment header within a B-tree root page.
103
@return TRUE if valid */
102
106
btr_root_fseg_validate(
103
107
/*===================*/
104
/* out: TRUE if valid */
105
const fseg_header_t* seg_header, /* in: segment header */
106
ulint space) /* in: tablespace identifier */
108
const fseg_header_t* seg_header, /*!< in: segment header */
109
ulint space) /*!< in: tablespace identifier */
108
111
ulint offset = mach_read_from_2(seg_header + FSEG_HDR_OFFSET);
115
118
#endif /* UNIV_BTR_DEBUG */
117
/******************************************************************
118
Gets the root node of a tree and x-latches it. */
120
/**************************************************************//**
121
Gets the root node of a tree and x-latches it.
122
@return root page, x-latched */
121
125
btr_root_block_get(
122
126
/*===============*/
123
/* out: root page, x-latched */
124
dict_index_t* index, /* in: index tree */
125
mtr_t* mtr) /* in: mtr */
127
dict_index_t* index, /*!< in: index tree */
128
mtr_t* mtr) /*!< in: mtr */
153
/******************************************************************
154
Gets the root node of a tree and x-latches it. */
156
/**************************************************************//**
157
Gets the root node of a tree and x-latches it.
158
@return root page, x-latched */
159
/* out: root page, x-latched */
160
dict_index_t* index, /* in: index tree */
161
mtr_t* mtr) /* in: mtr */
163
dict_index_t* index, /*!< in: index tree */
164
mtr_t* mtr) /*!< in: mtr */
163
166
return(buf_block_get_frame(btr_root_block_get(index, mtr)));
166
/*****************************************************************
169
/*************************************************************//**
167
170
Gets pointer to the previous user record in the tree. It is assumed that
168
the caller has appropriate latches on the page and its neighbor. */
171
the caller has appropriate latches on the page and its neighbor.
172
@return previous user record, NULL if there is none */
171
175
btr_get_prev_user_rec(
172
176
/*==================*/
173
/* out: previous user record, NULL if there is none */
174
rec_t* rec, /* in: record on leaf level */
175
mtr_t* mtr) /* in: mtr holding a latch on the page, and if
177
rec_t* rec, /*!< in: record on leaf level */
178
mtr_t* mtr) /*!< in: mtr holding a latch on the page, and if
176
179
needed, also to the previous page */
224
/*****************************************************************
227
/*************************************************************//**
225
228
Gets pointer to the next user record in the tree. It is assumed that the
226
caller has appropriate latches on the page and its neighbor. */
229
caller has appropriate latches on the page and its neighbor.
230
@return next user record, NULL if there is none */
229
233
btr_get_next_user_rec(
230
234
/*==================*/
231
/* out: next user record, NULL if there is none */
232
rec_t* rec, /* in: record on leaf level */
233
mtr_t* mtr) /* in: mtr holding a latch on the page, and if
235
rec_t* rec, /*!< in: record on leaf level */
236
mtr_t* mtr) /*!< in: mtr holding a latch on the page, and if
234
237
needed, also to the next page */
280
/******************************************************************
283
/**************************************************************//**
281
284
Creates a new index page (not the root, and also not
282
285
used in page reorganization). @see btr_page_empty(). */
287
buf_block_t* block, /* in/out: page to be created */
288
page_zip_des_t* page_zip,/* in/out: compressed page, or NULL */
289
dict_index_t* index, /* in: index */
290
ulint level, /* in: the B-tree level of the page */
291
mtr_t* mtr) /* in: mtr */
290
buf_block_t* block, /*!< in/out: page to be created */
291
page_zip_des_t* page_zip,/*!< in/out: compressed page, or NULL */
292
dict_index_t* index, /*!< in: index */
293
ulint level, /*!< in: the B-tree level of the page */
294
mtr_t* mtr) /*!< in: mtr */
293
296
page_t* page = buf_block_get_frame(block);
307
310
btr_page_set_index_id(page, page_zip, index->id, mtr);
310
/******************************************************************
313
/**************************************************************//**
311
314
Allocates a new file page to be used in an ibuf tree. Takes the page from
312
the free list of the tree, which must contain pages! */
315
the free list of the tree, which must contain pages!
316
@return new allocated block, x-latched */
315
319
btr_page_alloc_for_ibuf(
316
320
/*====================*/
317
/* out: new allocated block, x-latched */
318
dict_index_t* index, /* in: index tree */
319
mtr_t* mtr) /* in: mtr */
321
dict_index_t* index, /*!< in: index tree */
322
mtr_t* mtr) /*!< in: mtr */
321
324
fil_addr_t node_addr;
344
347
return(new_block);
347
/******************************************************************
350
/**************************************************************//**
348
351
Allocates a new file page to be used in an index tree. NOTE: we assume
349
that the caller has made the reservation for free extents! */
352
that the caller has made the reservation for free extents!
353
@return new allocated block, x-latched; NULL if out of space */
354
/* out: new allocated block, x-latched;
355
NULL if out of space */
356
dict_index_t* index, /* in: index */
357
ulint hint_page_no, /* in: hint of a good page */
358
byte file_direction, /* in: direction where a possible
358
dict_index_t* index, /*!< in: index */
359
ulint hint_page_no, /*!< in: hint of a good page */
360
byte file_direction, /*!< in: direction where a possible
359
361
page split is made */
360
ulint level, /* in: level where the page is placed
362
ulint level, /*!< in: level where the page is placed
362
mtr_t* mtr) /* in: mtr */
364
mtr_t* mtr) /*!< in: mtr */
364
366
fseg_header_t* seg_header;
398
400
return(new_block);
401
/******************************************************************
402
Gets the number of pages in a B-tree. */
403
/**************************************************************//**
404
Gets the number of pages in a B-tree.
405
@return number of pages */
407
/* out: number of pages */
408
dict_index_t* index, /* in: index */
409
ulint flag) /* in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */
410
dict_index_t* index, /*!< in: index */
411
ulint flag) /*!< in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */
411
413
fseg_header_t* seg_header;
445
/******************************************************************
447
/**************************************************************//**
446
448
Frees a page used in an ibuf tree. Puts the page to the free list of the
450
452
btr_page_free_for_ibuf(
451
453
/*===================*/
452
dict_index_t* index, /* in: index tree */
453
buf_block_t* block, /* in: block to be freed, x-latched */
454
mtr_t* mtr) /* in: mtr */
454
dict_index_t* index, /*!< in: index tree */
455
buf_block_t* block, /*!< in: block to be freed, x-latched */
456
mtr_t* mtr) /*!< in: mtr */
475
477
btr_page_free_low(
476
478
/*==============*/
477
dict_index_t* index, /* in: index tree */
478
buf_block_t* block, /* in: block to be freed, x-latched */
479
ulint level, /* in: page level */
480
mtr_t* mtr) /* in: mtr */
479
dict_index_t* index, /*!< in: index tree */
480
buf_block_t* block, /*!< in: block to be freed, x-latched */
481
ulint level, /*!< in: page level */
482
mtr_t* mtr) /*!< in: mtr */
482
484
fseg_header_t* seg_header;
508
510
buf_block_get_page_no(block), mtr);
511
/******************************************************************
513
/**************************************************************//**
512
514
Frees a file page used in an index tree. NOTE: cannot free field external
513
515
storage pages because the page must contain info on its level. */
518
dict_index_t* index, /* in: index tree */
519
buf_block_t* block, /* in: block to be freed, x-latched */
520
mtr_t* mtr) /* in: mtr */
520
dict_index_t* index, /*!< in: index tree */
521
buf_block_t* block, /*!< in: block to be freed, x-latched */
522
mtr_t* mtr) /*!< in: mtr */
526
528
btr_page_free_low(index, block, level, mtr);
529
/******************************************************************
531
/**************************************************************//**
530
532
Sets the child node file address in a node pointer. */
533
535
btr_node_ptr_set_child_page_no(
534
536
/*===========================*/
535
rec_t* rec, /* in: node pointer record */
536
page_zip_des_t* page_zip,/* in/out: compressed page whose uncompressed
537
rec_t* rec, /*!< in: node pointer record */
538
page_zip_des_t* page_zip,/*!< in/out: compressed page whose uncompressed
537
539
part will be updated, or NULL */
538
const ulint* offsets,/* in: array returned by rec_get_offsets() */
539
ulint page_no,/* in: child node address */
540
mtr_t* mtr) /* in: mtr */
540
const ulint* offsets,/*!< in: array returned by rec_get_offsets() */
541
ulint page_no,/*!< in: child node address */
542
mtr_t* mtr) /*!< in: mtr */
564
/****************************************************************
565
Returns the child page of a node pointer and x-latches it. */
566
/************************************************************//**
567
Returns the child page of a node pointer and x-latches it.
568
@return child page, x-latched */
568
571
btr_node_ptr_get_child(
569
572
/*===================*/
570
/* out: child page, x-latched */
571
const rec_t* node_ptr,/* in: node pointer */
572
dict_index_t* index, /* in: index */
573
const ulint* offsets,/* in: array returned by rec_get_offsets() */
574
mtr_t* mtr) /* in: mtr */
573
const rec_t* node_ptr,/*!< in: node pointer */
574
dict_index_t* index, /*!< in: index */
575
const ulint* offsets,/*!< in: array returned by rec_get_offsets() */
576
mtr_t* mtr) /*!< in: mtr */
584
586
page_no, RW_X_LATCH, mtr));
587
/****************************************************************
589
/************************************************************//**
588
590
Returns the upper level node pointer to a page. It is assumed that mtr holds
589
an x-latch on the tree. */
591
an x-latch on the tree.
592
@return rec_get_offsets() of the node pointer record */
592
595
btr_page_get_father_node_ptr(
593
596
/*=========================*/
594
/* out: rec_get_offsets() of the
595
node pointer record */
596
ulint* offsets,/* in: work area for the return value */
597
mem_heap_t* heap, /* in: memory heap to use */
598
btr_cur_t* cursor, /* in: cursor pointing to user record,
597
ulint* offsets,/*!< in: work area for the return value */
598
mem_heap_t* heap, /*!< in: memory heap to use */
599
btr_cur_t* cursor, /*!< in: cursor pointing to user record,
599
600
out: cursor on node pointer record,
600
601
its page x-latched */
601
mtr_t* mtr) /* in: mtr */
602
mtr_t* mtr) /*!< in: mtr */
660
661
"InnoDB: corruption. If the crash happens at "
661
662
"the database startup, see\n"
662
"InnoDB: http://dev.mysql.com/doc/refman/5.1/en/"
663
"forcing-recovery.html about\n"
663
"InnoDB: " REFMAN "forcing-recovery.html about\n"
664
664
"InnoDB: forcing recovery. "
665
665
"Then dump + drop + reimport.\n", stderr);
673
/****************************************************************
673
/************************************************************//**
674
674
Returns the upper level node pointer to a page. It is assumed that mtr holds
675
an x-latch on the tree. */
675
an x-latch on the tree.
676
@return rec_get_offsets() of the node pointer record */
678
679
btr_page_get_father_block(
679
680
/*======================*/
680
/* out: rec_get_offsets() of the
681
node pointer record */
682
ulint* offsets,/* in: work area for the return value */
683
mem_heap_t* heap, /* in: memory heap to use */
684
dict_index_t* index, /* in: b-tree index */
685
buf_block_t* block, /* in: child page in the index */
686
mtr_t* mtr, /* in: mtr */
687
btr_cur_t* cursor) /* out: cursor on node pointer record,
681
ulint* offsets,/*!< in: work area for the return value */
682
mem_heap_t* heap, /*!< in: memory heap to use */
683
dict_index_t* index, /*!< in: b-tree index */
684
buf_block_t* block, /*!< in: child page in the index */
685
mtr_t* mtr, /*!< in: mtr */
686
btr_cur_t* cursor) /*!< out: cursor on node pointer record,
688
687
its page x-latched */
694
693
return(btr_page_get_father_node_ptr(offsets, heap, cursor, mtr));
697
/****************************************************************
696
/************************************************************//**
698
697
Seeks to the upper level node pointer to a page.
699
698
It is assumed that mtr holds an x-latch on the tree. */
702
701
btr_page_get_father(
703
702
/*================*/
704
dict_index_t* index, /* in: b-tree index */
705
buf_block_t* block, /* in: child page in the index */
706
mtr_t* mtr, /* in: mtr */
707
btr_cur_t* cursor) /* out: cursor on node pointer record,
703
dict_index_t* index, /*!< in: b-tree index */
704
buf_block_t* block, /*!< in: child page in the index */
705
mtr_t* mtr, /*!< in: mtr */
706
btr_cur_t* cursor) /*!< out: cursor on node pointer record,
708
707
its page x-latched */
710
709
mem_heap_t* heap;
718
717
mem_heap_free(heap);
721
/****************************************************************
722
Creates the root node for a new index tree. */
720
/************************************************************//**
721
Creates the root node for a new index tree.
722
@return page number of the created root, FIL_NULL if did not succeed */
727
/* out: page number of the created root,
728
FIL_NULL if did not succeed */
729
ulint type, /* in: type of the index */
730
ulint space, /* in: space where created */
731
ulint zip_size,/* in: compressed page size in bytes
727
ulint type, /*!< in: type of the index */
728
ulint space, /*!< in: space where created */
729
ulint zip_size,/*!< in: compressed page size in bytes
732
730
or 0 for uncompressed pages */
733
dulint index_id,/* in: index id */
734
dict_index_t* index, /* in: index */
735
mtr_t* mtr) /* in: mini-transaction handle */
731
dulint index_id,/*!< in: index id */
732
dict_index_t* index, /*!< in: index */
733
mtr_t* mtr) /*!< in: mini-transaction handle */
738
736
buf_block_t* block;
840
/****************************************************************
838
/************************************************************//**
841
839
Frees a B-tree except the root page, which MUST be freed after this
842
840
by calling btr_free_root. */
845
843
btr_free_but_not_root(
846
844
/*==================*/
847
ulint space, /* in: space where created */
848
ulint zip_size, /* in: compressed page size in bytes
845
ulint space, /*!< in: space where created */
846
ulint zip_size, /*!< in: compressed page size in bytes
849
847
or 0 for uncompressed pages */
850
ulint root_page_no) /* in: root page number */
848
ulint root_page_no) /*!< in: root page number */
897
/****************************************************************
895
/************************************************************//**
898
896
Frees the B-tree root page. Other tree MUST already have been freed. */
903
ulint space, /* in: space where created */
904
ulint zip_size, /* in: compressed page size in bytes
901
ulint space, /*!< in: space where created */
902
ulint zip_size, /*!< in: compressed page size in bytes
905
903
or 0 for uncompressed pages */
906
ulint root_page_no, /* in: root page number */
907
mtr_t* mtr) /* in: a mini-transaction which has already
904
ulint root_page_no, /*!< in: root page number */
905
mtr_t* mtr) /*!< in: a mini-transaction which has already
910
908
buf_block_t* block;
922
920
while (!fseg_free_step(header, mtr));
922
#endif /* !UNIV_HOTBACKUP */
925
/*****************************************************************
924
/*************************************************************//**
926
925
Reorganizes an index page. */
929
928
btr_page_reorganize_low(
930
929
/*====================*/
931
ibool recovery,/* in: TRUE if called in recovery:
930
ibool recovery,/*!< in: TRUE if called in recovery:
932
931
locks should not be updated, i.e.,
933
932
there cannot exist locks on the
934
933
page, and a hash index should not be
935
934
dropped: it cannot exist */
936
buf_block_t* block, /* in: page to be reorganized */
937
dict_index_t* index, /* in: record descriptor */
938
mtr_t* mtr) /* in: mtr */
935
buf_block_t* block, /*!< in: page to be reorganized */
936
dict_index_t* index, /*!< in: record descriptor */
937
mtr_t* mtr) /*!< in: mtr */
940
939
page_t* page = buf_block_get_frame(block);
941
940
page_zip_des_t* page_zip = buf_block_get_page_zip(block);
956
955
data_size1 = page_get_data_size(page);
957
956
max_ins_size1 = page_get_max_insert_size_after_reorganize(page, 1);
958
#ifndef UNIV_HOTBACKUP
959
959
/* Write the log record */
960
960
mlog_open_and_write_index(mtr, page, index, page_is_comp(page)
961
961
? MLOG_COMP_PAGE_REORGANIZE
962
962
: MLOG_PAGE_REORGANIZE, 0);
963
#endif /* !UNIV_HOTBACKUP */
964
965
/* Turn logging off */
965
966
log_mode = mtr_set_log_mode(mtr, MTR_LOG_NONE);
968
#ifndef UNIV_HOTBACKUP
967
969
temp_block = buf_block_alloc(0);
970
#else /* !UNIV_HOTBACKUP */
971
ut_ad(block == back_block1);
972
temp_block = back_block2;
973
#endif /* !UNIV_HOTBACKUP */
968
974
temp_page = temp_block->frame;
970
976
/* Copy the old page to temporary space */
971
977
buf_frame_copy(temp_page, page);
979
#ifndef UNIV_HOTBACKUP
973
980
if (UNIV_LIKELY(!recovery)) {
974
981
btr_search_drop_page_hash_index(block);
984
block->check_index_page_at_flush = TRUE;
985
#endif /* !UNIV_HOTBACKUP */
977
987
/* Recreate the page: note that global data on page (possible
978
988
segment headers, next page-field, etc.) is preserved intact */
980
990
page_create(block, mtr, dict_table_is_comp(index->table));
981
block->check_index_page_at_flush = TRUE;
983
992
/* Copy the records from the temporary space to the recreated page;
984
993
do not copy the lock bits yet */
986
995
page_copy_rec_list_end_no_locks(block, temp_block,
987
996
page_get_infimum_rec(temp_page),
989
/* Copy max trx id to recreated page */
990
page_set_max_trx_id(block, NULL, page_get_max_trx_id(temp_page));
999
if (dict_index_is_sec_or_ibuf(index) && page_is_leaf(page)) {
1000
/* Copy max trx id to recreated page */
1001
trx_id_t max_trx_id = page_get_max_trx_id(temp_page);
1002
page_set_max_trx_id(block, NULL, max_trx_id, mtr);
1003
/* In crash recovery, dict_index_is_sec_or_ibuf() always
1004
returns TRUE, even for clustered indexes. max_trx_id is
1005
unused in clustered index pages. */
1006
ut_ad(!ut_dulint_is_zero(max_trx_id) || recovery);
992
1009
if (UNIV_LIKELY_NULL(page_zip)
993
1010
&& UNIV_UNLIKELY
1019
#ifndef UNIV_HOTBACKUP
1002
1020
if (UNIV_LIKELY(!recovery)) {
1003
1021
/* Update the record lock bitmaps */
1004
1022
lock_move_reorganize_page(block, temp_block);
1024
#endif /* !UNIV_HOTBACKUP */
1007
1026
data_size2 = page_get_data_size(page);
1008
1027
max_ins_size2 = page_get_max_insert_size_after_reorganize(page, 1);
1029
1048
#ifdef UNIV_ZIP_DEBUG
1030
1049
ut_a(!page_zip || page_zip_validate(page_zip, page));
1031
1050
#endif /* UNIV_ZIP_DEBUG */
1051
#ifndef UNIV_HOTBACKUP
1032
1052
buf_block_free(temp_block);
1053
#endif /* !UNIV_HOTBACKUP */
1034
1055
/* Restore logging mode */
1035
1056
mtr_set_log_mode(mtr, log_mode);
1037
1058
return(success);
1040
/*****************************************************************
1061
#ifndef UNIV_HOTBACKUP
1062
/*************************************************************//**
1041
1063
Reorganizes an index page.
1042
1064
IMPORTANT: if btr_page_reorganize() is invoked on a compressed leaf
1043
1065
page of a non-clustered index, the caller must update the insert
1044
1066
buffer free bits in the same mini-transaction in such a way that the
1045
modification will be redo-logged. */
1067
modification will be redo-logged.
1068
@return TRUE on success, FALSE on failure */
1048
1071
btr_page_reorganize(
1049
1072
/*================*/
1050
/* out: TRUE on success, FALSE on failure */
1051
buf_block_t* block, /* in: page to be reorganized */
1052
dict_index_t* index, /* in: record descriptor */
1053
mtr_t* mtr) /* in: mtr */
1073
buf_block_t* block, /*!< in: page to be reorganized */
1074
dict_index_t* index, /*!< in: record descriptor */
1075
mtr_t* mtr) /*!< in: mtr */
1055
1077
return(btr_page_reorganize_low(FALSE, block, index, mtr));
1079
#endif /* !UNIV_HOTBACKUP */
1058
/***************************************************************
1059
Parses a redo log record of reorganizing a page. */
1081
/***********************************************************//**
1082
Parses a redo log record of reorganizing a page.
1083
@return end of log record or NULL */
1062
1086
btr_parse_page_reorganize(
1063
1087
/*======================*/
1064
/* out: end of log record or NULL */
1065
byte* ptr, /* in: buffer */
1088
byte* ptr, /*!< in: buffer */
1066
1089
byte* end_ptr __attribute__((unused)),
1067
/* in: buffer end */
1068
dict_index_t* index, /* in: record descriptor */
1069
buf_block_t* block, /* in: page to be reorganized, or NULL */
1070
mtr_t* mtr) /* in: mtr or NULL */
1090
/*!< in: buffer end */
1091
dict_index_t* index, /*!< in: record descriptor */
1092
buf_block_t* block, /*!< in: page to be reorganized, or NULL */
1093
mtr_t* mtr) /*!< in: mtr or NULL */
1072
1095
ut_ad(ptr && end_ptr);
1083
/*****************************************************************
1084
Empties an index page. @see btr_page_create().*/
1106
#ifndef UNIV_HOTBACKUP
1107
/*************************************************************//**
1108
Empties an index page. @see btr_page_create(). */
1087
1111
btr_page_empty(
1088
1112
/*===========*/
1089
buf_block_t* block, /* in: page to be emptied */
1090
page_zip_des_t* page_zip,/* out: compressed page, or NULL */
1091
dict_index_t* index, /* in: index of the page */
1092
ulint level, /* in: the B-tree level of the page */
1093
mtr_t* mtr) /* in: mtr */
1113
buf_block_t* block, /*!< in: page to be emptied */
1114
page_zip_des_t* page_zip,/*!< out: compressed page, or NULL */
1115
dict_index_t* index, /*!< in: index of the page */
1116
ulint level, /*!< in: the B-tree level of the page */
1117
mtr_t* mtr) /*!< in: mtr */
1095
1119
page_t* page = buf_block_get_frame(block);
1115
1139
block->check_index_page_at_flush = TRUE;
1118
/*****************************************************************
1142
/*************************************************************//**
1119
1143
Makes tree one level higher by splitting the root, and inserts
1120
1144
the tuple. It is assumed that mtr contains an x-latch on the tree.
1121
1145
NOTE that the operation of this function must always succeed,
1122
1146
we cannot reverse it: therefore enough free disk space must be
1123
guaranteed to be available before this function is called. */
1147
guaranteed to be available before this function is called.
1148
@return inserted record */
1126
1151
btr_root_raise_and_insert(
1127
1152
/*======================*/
1128
/* out: inserted record */
1129
btr_cur_t* cursor, /* in: cursor at which to insert: must be
1153
btr_cur_t* cursor, /*!< in: cursor at which to insert: must be
1130
1154
on the root page; when the function returns,
1131
1155
the cursor is positioned on the predecessor
1132
1156
of the inserted record */
1133
const dtuple_t* tuple, /* in: tuple to insert */
1134
ulint n_ext, /* in: number of externally stored columns */
1135
mtr_t* mtr) /* in: mtr */
1157
const dtuple_t* tuple, /*!< in: tuple to insert */
1158
ulint n_ext, /*!< in: number of externally stored columns */
1159
mtr_t* mtr) /*!< in: mtr */
1137
1161
dict_index_t* index;
1287
1311
return(btr_page_split_and_insert(cursor, tuple, n_ext, mtr));
1290
/*****************************************************************
1314
/*************************************************************//**
1291
1315
Decides if the page should be split at the convergence point of inserts
1292
converging to the left. */
1316
converging to the left.
1317
@return TRUE if split recommended */
1295
1320
btr_page_get_split_rec_to_left(
1296
1321
/*===========================*/
1297
/* out: TRUE if split recommended */
1298
btr_cur_t* cursor, /* in: cursor at which to insert */
1299
rec_t** split_rec) /* out: if split recommended,
1322
btr_cur_t* cursor, /*!< in: cursor at which to insert */
1323
rec_t** split_rec) /*!< out: if split recommended,
1300
1324
the first record on upper half page,
1301
1325
or NULL if tuple to be inserted should
1335
/*****************************************************************
1359
/*************************************************************//**
1336
1360
Decides if the page should be split at the convergence point of inserts
1337
converging to the right. */
1361
converging to the right.
1362
@return TRUE if split recommended */
1340
1365
btr_page_get_split_rec_to_right(
1341
1366
/*============================*/
1342
/* out: TRUE if split recommended */
1343
btr_cur_t* cursor, /* in: cursor at which to insert */
1344
rec_t** split_rec) /* out: if split recommended,
1367
btr_cur_t* cursor, /*!< in: cursor at which to insert */
1368
rec_t** split_rec) /*!< out: if split recommended,
1345
1369
the first record on upper half page,
1346
1370
or NULL if tuple to be inserted should
1393
/*****************************************************************
1417
/*************************************************************//**
1394
1418
Calculates a split record such that the tuple will certainly fit on
1395
1419
its half-page when the split is performed. We assume in this function
1396
only that the cursor page has at least one user record. */
1420
only that the cursor page has at least one user record.
1421
@return split record, or NULL if tuple will be the first record on
1399
1425
btr_page_get_sure_split_rec(
1400
1426
/*========================*/
1401
/* out: split record, or NULL if tuple
1402
will be the first record on upper half-page */
1403
btr_cur_t* cursor, /* in: cursor at which insert should be made */
1404
const dtuple_t* tuple, /* in: tuple to insert */
1405
ulint n_ext) /* in: number of externally stored columns */
1427
btr_cur_t* cursor, /*!< in: cursor at which insert should be made */
1428
const dtuple_t* tuple, /*!< in: tuple to insert */
1429
ulint n_ext) /*!< in: number of externally stored columns */
1408
1432
page_zip_des_t* page_zip;
1513
/*****************************************************************
1537
/*************************************************************//**
1514
1538
Returns TRUE if the insert fits on the appropriate half-page with the
1515
chosen split_rec. */
1540
@return TRUE if fits */
1518
1543
btr_page_insert_fits(
1519
1544
/*=================*/
1520
/* out: TRUE if fits */
1521
btr_cur_t* cursor, /* in: cursor at which insert
1545
btr_cur_t* cursor, /*!< in: cursor at which insert
1522
1546
should be made */
1523
const rec_t* split_rec,/* in: suggestion for first record
1547
const rec_t* split_rec,/*!< in: suggestion for first record
1524
1548
on upper half-page, or NULL if
1525
1549
tuple to be inserted should be first */
1526
const ulint* offsets,/* in: rec_get_offsets(
1550
const ulint* offsets,/*!< in: rec_get_offsets(
1527
1551
split_rec, cursor->index) */
1528
const dtuple_t* tuple, /* in: tuple to insert */
1529
ulint n_ext, /* in: number of externally stored columns */
1530
mem_heap_t* heap) /* in: temporary memory heap */
1552
const dtuple_t* tuple, /*!< in: tuple to insert */
1553
ulint n_ext, /*!< in: number of externally stored columns */
1554
mem_heap_t* heap) /*!< in: temporary memory heap */
1533
1557
ulint insert_size;
1610
/***********************************************************
1634
/*******************************************************//**
1611
1635
Inserts a data tuple to a tree on a non-leaf level. It is assumed
1612
1636
that mtr holds an x-latch on the tree. */
1615
1639
btr_insert_on_non_leaf_level(
1616
1640
/*=========================*/
1617
dict_index_t* index, /* in: index */
1618
ulint level, /* in: level, must be > 0 */
1619
dtuple_t* tuple, /* in: the record to be inserted */
1620
mtr_t* mtr) /* in: mtr */
1641
dict_index_t* index, /*!< in: index */
1642
ulint level, /*!< in: level, must be > 0 */
1643
dtuple_t* tuple, /*!< in: the record to be inserted */
1644
mtr_t* mtr) /*!< in: mtr */
1622
1646
big_rec_t* dummy_big_rec;
1623
1647
btr_cur_t cursor;
1638
1662
ut_a(err == DB_SUCCESS);
1641
/******************************************************************
1665
/**************************************************************//**
1642
1666
Attaches the halves of an index page on the appropriate level in an
1646
1670
btr_attach_half_pages(
1647
1671
/*==================*/
1648
dict_index_t* index, /* in: the index tree */
1649
buf_block_t* block, /* in/out: page to be split */
1650
rec_t* split_rec, /* in: first record on upper
1672
dict_index_t* index, /*!< in: the index tree */
1673
buf_block_t* block, /*!< in/out: page to be split */
1674
rec_t* split_rec, /*!< in: first record on upper
1652
buf_block_t* new_block, /* in/out: the new half page */
1653
ulint direction, /* in: FSP_UP or FSP_DOWN */
1654
mtr_t* mtr) /* in: mtr */
1676
buf_block_t* new_block, /*!< in/out: the new half page */
1677
ulint direction, /*!< in: FSP_UP or FSP_DOWN */
1678
mtr_t* mtr) /*!< in: mtr */
1657
1681
ulint zip_size;
1773
1797
btr_page_set_next(upper_page, upper_page_zip, next_page_no, mtr);
1776
/*****************************************************************
1800
/*************************************************************//**
1777
1801
Splits an index page to halves and inserts the tuple. It is assumed
1778
that mtr holds an x-latch to the index tree. NOTE: the tree x-latch
1779
is released within this function! NOTE that the operation of this
1780
function must always succeed, we cannot reverse it: therefore
1781
enough free disk space must be guaranteed to be available before
1782
this function is called. */
1802
that mtr holds an x-latch to the index tree. NOTE: the tree x-latch is
1803
released within this function! NOTE that the operation of this
1804
function must always succeed, we cannot reverse it: therefore enough
1805
free disk space (2 pages) must be guaranteed to be available before
1806
this function is called.
1808
@return inserted record */
1785
1811
btr_page_split_and_insert(
1786
1812
/*======================*/
1787
/* out: inserted record; NOTE: the tree
1788
x-latch is released! NOTE: 2 free disk
1789
pages must be available! */
1790
btr_cur_t* cursor, /* in: cursor at which to insert; when the
1813
btr_cur_t* cursor, /*!< in: cursor at which to insert; when the
1791
1814
function returns, the cursor is positioned
1792
1815
on the predecessor of the inserted record */
1793
const dtuple_t* tuple, /* in: tuple to insert */
1794
ulint n_ext, /* in: number of externally stored columns */
1795
mtr_t* mtr) /* in: mtr */
1816
const dtuple_t* tuple, /*!< in: tuple to insert */
1817
ulint n_ext, /*!< in: number of externally stored columns */
1818
mtr_t* mtr) /*!< in: mtr */
1797
1820
buf_block_t* block;
2147
/*****************************************************************
2170
/*************************************************************//**
2148
2171
Removes a page from the level list of pages. */
2151
2174
btr_level_list_remove(
2152
2175
/*==================*/
2153
ulint space, /* in: space where removed */
2154
ulint zip_size,/* in: compressed page size in bytes
2176
ulint space, /*!< in: space where removed */
2177
ulint zip_size,/*!< in: compressed page size in bytes
2155
2178
or 0 for uncompressed pages */
2156
page_t* page, /* in: page to remove */
2157
mtr_t* mtr) /* in: mtr */
2179
page_t* page, /*!< in: page to remove */
2180
mtr_t* mtr) /*!< in: mtr */
2159
2182
ulint prev_page_no;
2160
2183
ulint next_page_no;
2207
/********************************************************************
2230
/****************************************************************//**
2208
2231
Writes the redo log record for setting an index record as the predefined
2209
2232
minimum record. */
2212
2235
btr_set_min_rec_mark_log(
2213
2236
/*=====================*/
2214
rec_t* rec, /* in: record */
2215
byte type, /* in: MLOG_COMP_REC_MIN_MARK or MLOG_REC_MIN_MARK */
2216
mtr_t* mtr) /* in: mtr */
2237
rec_t* rec, /*!< in: record */
2238
byte type, /*!< in: MLOG_COMP_REC_MIN_MARK or MLOG_REC_MIN_MARK */
2239
mtr_t* mtr) /*!< in: mtr */
2218
2241
mlog_write_initial_log_record(rec, type, mtr);
2220
2243
/* Write rec offset as a 2-byte ulint */
2221
2244
mlog_catenate_ulint(mtr, page_offset(rec), MLOG_2BYTES);
2246
#else /* !UNIV_HOTBACKUP */
2247
# define btr_set_min_rec_mark_log(rec,comp,mtr) ((void) 0)
2248
#endif /* !UNIV_HOTBACKUP */
2224
/********************************************************************
2250
/****************************************************************//**
2225
2251
Parses the redo log record for setting an index record as the predefined
2253
@return end of log record or NULL */
2229
2256
btr_parse_set_min_rec_mark(
2230
2257
/*=======================*/
2231
/* out: end of log record or NULL */
2232
byte* ptr, /* in: buffer */
2233
byte* end_ptr,/* in: buffer end */
2234
ulint comp, /* in: nonzero=compact page format */
2235
page_t* page, /* in: page or NULL */
2236
mtr_t* mtr) /* in: mtr or NULL */
2258
byte* ptr, /*!< in: buffer */
2259
byte* end_ptr,/*!< in: buffer end */
2260
ulint comp, /*!< in: nonzero=compact page format */
2261
page_t* page, /*!< in: page or NULL */
2262
mtr_t* mtr) /*!< in: mtr or NULL */
2253
2279
return(ptr + 2);
2256
/********************************************************************
2282
/****************************************************************//**
2257
2283
Sets a record as the predefined minimum record. */
2260
2286
btr_set_min_rec_mark(
2261
2287
/*=================*/
2262
rec_t* rec, /* in: record */
2263
mtr_t* mtr) /* in: mtr */
2288
rec_t* rec, /*!< in: record */
2289
mtr_t* mtr) /*!< in: mtr */
2265
2291
ulint info_bits;
2282
/*****************************************************************
2308
#ifndef UNIV_HOTBACKUP
2309
/*************************************************************//**
2283
2310
Deletes on the upper level the node pointer to a page. */
2286
2313
btr_node_ptr_delete(
2287
2314
/*================*/
2288
dict_index_t* index, /* in: index tree */
2289
buf_block_t* block, /* in: page whose node pointer is deleted */
2290
mtr_t* mtr) /* in: mtr */
2315
dict_index_t* index, /*!< in: index tree */
2316
buf_block_t* block, /*!< in: page whose node pointer is deleted */
2317
mtr_t* mtr) /*!< in: mtr */
2292
2319
btr_cur_t cursor;
2293
2320
ibool compressed;
2310
/*****************************************************************
2337
/*************************************************************//**
2311
2338
If page is the only on its level, this function moves its records to the
2312
2339
father page, thus reducing the tree height. */
2315
2342
btr_lift_page_up(
2316
2343
/*=============*/
2317
dict_index_t* index, /* in: index tree */
2318
buf_block_t* block, /* in: page which is the only on its level;
2344
dict_index_t* index, /*!< in: index tree */
2345
buf_block_t* block, /*!< in: page which is the only on its level;
2319
2346
must not be empty: use
2320
2347
btr_discard_only_page_on_level if the last
2321
2348
record from the page should be removed */
2322
mtr_t* mtr) /* in: mtr */
2349
mtr_t* mtr) /*!< in: mtr */
2324
2351
buf_block_t* father_block;
2325
2352
page_t* father_page;
2328
2355
page_t* page = buf_block_get_frame(block);
2329
2356
ulint root_page_no;
2330
2357
buf_block_t* blocks[BTR_MAX_LEVELS];
2331
ulint n_blocks; /* last used index in blocks[] */
2358
ulint n_blocks; /*!< last used index in blocks[] */
2334
2361
ut_ad(btr_page_get_prev(page, mtr) == FIL_NULL);
2429
2456
ut_ad(btr_check_node_ptr(index, father_block, mtr));
2432
/*****************************************************************
2459
/*************************************************************//**
2433
2460
Tries to merge the page first to the left immediate brother if such a
2434
2461
brother exists, and the node pointers to the current page and to the brother
2435
2462
reside on the same page. If the left brother does not satisfy these
2437
2464
level lifts the records of the page to the father page, thus reducing the
2438
2465
tree height. It is assumed that mtr holds an x-latch on the tree and on the
2439
2466
page. If cursor is on the leaf level, mtr must also hold x-latches to the
2440
brothers, if they exist. */
2467
brothers, if they exist.
2468
@return TRUE on success */
2445
/* out: TRUE on success */
2446
btr_cur_t* cursor, /* in: cursor on the page to merge or lift;
2473
btr_cur_t* cursor, /*!< in: cursor on the page to merge or lift;
2447
2474
the page must not be empty: in record delete
2448
2475
use btr_discard_page if the page would become
2450
mtr_t* mtr) /* in: mtr */
2477
mtr_t* mtr) /*!< in: mtr */
2452
2479
dict_index_t* index;
2724
/*****************************************************************
2751
/*************************************************************//**
2725
2752
Discards a page that is the only page on its level. This will empty
2726
2753
the whole B-tree, leaving just an empty root page. This function
2727
2754
should never be reached, because btr_compress(), which is invoked in
2731
2758
btr_discard_only_page_on_level(
2732
2759
/*===========================*/
2733
dict_index_t* index, /* in: index tree */
2734
buf_block_t* block, /* in: page which is the only on its level */
2735
mtr_t* mtr) /* in: mtr */
2760
dict_index_t* index, /*!< in: index tree */
2761
buf_block_t* block, /*!< in: page which is the only on its level */
2762
mtr_t* mtr) /*!< in: mtr */
2737
ulint page_level = 0;
2764
ulint page_level = 0;
2765
trx_id_t max_trx_id;
2767
/* Save the PAGE_MAX_TRX_ID from the leaf page. */
2768
max_trx_id = page_get_max_trx_id(buf_block_get_frame(block));
2739
2770
while (buf_block_get_page_no(block) != dict_index_get_page(index)) {
2740
2771
btr_cur_t cursor;
2778
2809
btr_page_empty(block, buf_block_get_page_zip(block), index, 0, mtr);
2780
/* We play it safe and reset the free bits for the root */
2781
2811
if (!dict_index_is_clust(index)) {
2812
/* We play it safe and reset the free bits for the root */
2782
2813
ibuf_reset_free_bits(block);
2815
if (page_is_leaf(buf_block_get_frame(block))) {
2816
ut_a(!ut_dulint_is_zero(max_trx_id));
2817
page_set_max_trx_id(block,
2818
buf_block_get_page_zip(block),
2786
/*****************************************************************
2824
/*************************************************************//**
2787
2825
Discards a page from a B-tree. This is used to remove the last record from
2788
2826
a B-tree page: the whole page must be removed at the same time. This cannot
2789
2827
be used for the root page, which is allowed to be empty. */
2931
2969
mtr_commit(&mtr);
2934
/****************************************************************
2972
/************************************************************//**
2935
2973
Prints recursively index tree pages. */
2938
2976
btr_print_recursive(
2939
2977
/*================*/
2940
dict_index_t* index, /* in: index tree */
2941
buf_block_t* block, /* in: index page */
2942
ulint width, /* in: print this many entries from start
2978
dict_index_t* index, /*!< in: index tree */
2979
buf_block_t* block, /*!< in: index page */
2980
ulint width, /*!< in: print this many entries from start
2944
mem_heap_t** heap, /* in/out: heap for rec_get_offsets() */
2945
ulint** offsets,/* in/out: buffer for rec_get_offsets() */
2946
mtr_t* mtr) /* in: mtr */
2982
mem_heap_t** heap, /*!< in/out: heap for rec_get_offsets() */
2983
ulint** offsets,/*!< in/out: buffer for rec_get_offsets() */
2984
mtr_t* mtr) /*!< in: mtr */
2948
2986
const page_t* page = buf_block_get_frame(block);
2949
2987
page_cur_t cursor;
2996
/******************************************************************
3034
/**************************************************************//**
2997
3035
Prints directories and other info of all nodes in the tree. */
3000
3038
btr_print_index(
3001
3039
/*============*/
3002
dict_index_t* index, /* in: index */
3003
ulint width) /* in: print this many entries from start
3040
dict_index_t* index, /*!< in: index */
3041
ulint width) /*!< in: print this many entries from start
3029
3067
#endif /* UNIV_BTR_PRINT */
3031
3069
#ifdef UNIV_DEBUG
3032
/****************************************************************
3033
Checks that the node pointer to a page is appropriate. */
3070
/************************************************************//**
3071
Checks that the node pointer to a page is appropriate.
3036
3075
btr_check_node_ptr(
3037
3076
/*===============*/
3039
dict_index_t* index, /* in: index tree */
3040
buf_block_t* block, /* in: index page */
3041
mtr_t* mtr) /* in: mtr */
3077
dict_index_t* index, /*!< in: index tree */
3078
buf_block_t* block, /*!< in: index page */
3079
mtr_t* mtr) /*!< in: mtr */
3043
3081
mem_heap_t* heap;
3044
3082
dtuple_t* tuple;
3074
3112
#endif /* UNIV_DEBUG */
3076
/****************************************************************
3114
/************************************************************//**
3077
3115
Display identification information for a record. */
3080
3118
btr_index_rec_validate_report(
3081
3119
/*==========================*/
3082
const page_t* page, /* in: index page */
3083
const rec_t* rec, /* in: index record */
3084
const dict_index_t* index) /* in: index */
3120
const page_t* page, /*!< in: index page */
3121
const rec_t* rec, /*!< in: index record */
3122
const dict_index_t* index) /*!< in: index */
3086
3124
fputs("InnoDB: Record in ", stderr);
3087
3125
dict_index_name_print(stderr, NULL, index);
3089
3127
page_get_page_no(page), (ulint) page_offset(rec));
3092
/****************************************************************
3130
/************************************************************//**
3093
3131
Checks the size and number of fields in a record based on the definition of
3133
@return TRUE if ok */
3097
3136
btr_index_rec_validate(
3098
3137
/*===================*/
3099
/* out: TRUE if ok */
3100
const rec_t* rec, /* in: index record */
3101
const dict_index_t* index, /* in: index */
3102
ibool dump_on_error) /* in: TRUE if the function
3138
const rec_t* rec, /*!< in: index record */
3139
const dict_index_t* index, /*!< in: index */
3140
ibool dump_on_error) /*!< in: TRUE if the function
3103
3141
should print hex dump of record
3104
3142
and page on error */
3155
3193
for (i = 0; i < n; i++) {
3156
3194
ulint fixed_size = dict_col_get_fixed_size(
3157
dict_index_get_nth_col(index, i));
3195
dict_index_get_nth_col(index, i), page_is_comp(page));
3159
3197
rec_get_nth_field_offs(offsets, i, &len);
3201
/****************************************************************
3239
/************************************************************//**
3202
3240
Checks the size and number of fields in records based on the definition of
3242
@return TRUE if ok */
3206
3245
btr_index_page_validate(
3207
3246
/*====================*/
3208
/* out: TRUE if ok */
3209
buf_block_t* block, /* in: index page */
3210
dict_index_t* index) /* in: index */
3247
buf_block_t* block, /*!< in: index page */
3248
dict_index_t* index) /*!< in: index */
3212
3250
page_cur_t cur;
3213
3251
ibool ret = TRUE;
3235
/****************************************************************
3273
/************************************************************//**
3236
3274
Report an error on one page of an index tree. */
3239
3277
btr_validate_report1(
3240
3278
/*=================*/
3241
/* out: TRUE if ok */
3242
dict_index_t* index, /* in: index */
3243
ulint level, /* in: B-tree level */
3244
const buf_block_t* block) /* in: index page */
3279
dict_index_t* index, /*!< in: index */
3280
ulint level, /*!< in: B-tree level */
3281
const buf_block_t* block) /*!< in: index page */
3246
3283
fprintf(stderr, "InnoDB: Error in page %lu of ",
3247
3284
buf_block_get_page_no(block));
3252
3289
putc('\n', stderr);
3255
/****************************************************************
3292
/************************************************************//**
3256
3293
Report an error on two pages of an index tree. */
3259
3296
btr_validate_report2(
3260
3297
/*=================*/
3261
/* out: TRUE if ok */
3262
const dict_index_t* index, /* in: index */
3263
ulint level, /* in: B-tree level */
3264
const buf_block_t* block1, /* in: first index page */
3265
const buf_block_t* block2) /* in: second index page */
3298
const dict_index_t* index, /*!< in: index */
3299
ulint level, /*!< in: B-tree level */
3300
const buf_block_t* block1, /*!< in: first index page */
3301
const buf_block_t* block2) /*!< in: second index page */
3267
3303
fprintf(stderr, "InnoDB: Error in pages %lu and %lu of ",
3268
3304
buf_block_get_page_no(block1),
3274
3310
putc('\n', stderr);
3277
/****************************************************************
3278
Validates index tree level. */
3313
/************************************************************//**
3314
Validates index tree level.
3315
@return TRUE if ok */
3281
3318
btr_validate_level(
3282
3319
/*===============*/
3283
/* out: TRUE if ok */
3284
dict_index_t* index, /* in: index tree */
3285
trx_t* trx, /* in: transaction or NULL */
3286
ulint level) /* in: level number */
3320
dict_index_t* index, /*!< in: index tree */
3321
trx_t* trx, /*!< in: transaction or NULL */
3322
ulint level) /*!< in: level number */
3289
3325
ulint zip_size;
3623
/******************************************************************
3624
Checks the consistency of an index tree. */
3659
/**************************************************************//**
3660
Checks the consistency of an index tree.
3661
@return TRUE if ok */
3627
3664
btr_validate_index(
3628
3665
/*===============*/
3629
/* out: TRUE if ok */
3630
dict_index_t* index, /* in: index */
3631
trx_t* trx) /* in: transaction or NULL */
3666
dict_index_t* index, /*!< in: index */
3667
trx_t* trx) /*!< in: transaction or NULL */
added
removed
storage/innobase/btr/btr0btr.c
