1 /***************************************************************************** 2 3 Copyright (c) 1994, 2016, Oracle and/or its affiliates. All Rights Reserved. 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License, version 2.0, 7 as published by the Free Software Foundation. 8 9 This program is also distributed with certain software (including 10 but not limited to OpenSSL) that is licensed under separate terms, 11 as designated in a particular file or component or in included license 12 documentation. The authors of MySQL hereby grant you an additional 13 permission to link the program and your derivative works with the 14 separately licensed software that they have included with MySQL. 15 16 This program is distributed in the hope that it will be useful, 17 but WITHOUT ANY WARRANTY; without even the implied warranty of 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19 GNU General Public License, version 2.0, for more details. 20 21 You should have received a copy of the GNU General Public License along with 22 this program; if not, write to the Free Software Foundation, Inc., 23 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA 24 25 *****************************************************************************/ 26 27 /**************************************************//** 28 @file include/btr0cur.h 29 The index tree cursor 30 31 Created 10/16/1994 Heikki Tuuri 32 *******************************************************/ 33 34 #ifndef btr0cur_h 35 #define btr0cur_h 36 37 #include "univ.i" 38 #include "dict0dict.h" 39 #include "page0cur.h" 40 #include "btr0types.h" 41 42 /** Mode flags for btr_cur operations; these can be ORed */ 43 enum { 44 /** do no undo logging */ 45 BTR_NO_UNDO_LOG_FLAG = 1, 46 /** do no record lock checking */ 47 BTR_NO_LOCKING_FLAG = 2, 48 /** sys fields will be found in the update vector or inserted 49 entry */ 50 BTR_KEEP_SYS_FLAG = 4, 51 /** btr_cur_pessimistic_update() must keep cursor position 52 when moving columns to big_rec */ 53 BTR_KEEP_POS_FLAG = 8, 54 /** the caller is creating the index or wants to bypass the 55 index->info.online creation log */ 56 BTR_CREATE_FLAG = 16, 57 /** the caller of btr_cur_optimistic_update() or 58 btr_cur_update_in_place() will take care of 59 updating IBUF_BITMAP_FREE */ 60 BTR_KEEP_IBUF_BITMAP = 32 61 }; 62 63 #ifndef UNIV_HOTBACKUP 64 #include "que0types.h" 65 #include "row0types.h" 66 #include "ha0ha.h" 67 68 #define BTR_CUR_ADAPT 69 #define BTR_CUR_HASH_ADAPT 70 71 #ifdef UNIV_DEBUG 72 /*********************************************************//** 73 Returns the page cursor component of a tree cursor. 74 @return pointer to page cursor component */ 75 UNIV_INLINE 76 page_cur_t* 77 btr_cur_get_page_cur( 78 /*=================*/ 79 const btr_cur_t* cursor);/*!< in: tree cursor */ 80 /*********************************************************//** 81 Returns the buffer block on which the tree cursor is positioned. 82 @return pointer to buffer block */ 83 UNIV_INLINE 84 buf_block_t* 85 btr_cur_get_block( 86 /*==============*/ 87 const btr_cur_t* cursor);/*!< in: tree cursor */ 88 /*********************************************************//** 89 Returns the record pointer of a tree cursor. 90 @return pointer to record */ 91 UNIV_INLINE 92 rec_t* 93 btr_cur_get_rec( 94 /*============*/ 95 const btr_cur_t* cursor);/*!< in: tree cursor */ 96 #else /* UNIV_DEBUG */ 97 # define btr_cur_get_page_cur(cursor) (&(cursor)->page_cur) 98 # define btr_cur_get_block(cursor) ((cursor)->page_cur.block) 99 # define btr_cur_get_rec(cursor) ((cursor)->page_cur.rec) 100 #endif /* UNIV_DEBUG */ 101 /*********************************************************//** 102 Returns the compressed page on which the tree cursor is positioned. 103 @return pointer to compressed page, or NULL if the page is not compressed */ 104 UNIV_INLINE 105 page_zip_des_t* 106 btr_cur_get_page_zip( 107 /*=================*/ 108 btr_cur_t* cursor);/*!< in: tree cursor */ 109 /*********************************************************//** 110 Invalidates a tree cursor by setting record pointer to NULL. */ 111 UNIV_INLINE 112 void 113 btr_cur_invalidate( 114 /*===============*/ 115 btr_cur_t* cursor);/*!< in: tree cursor */ 116 /*********************************************************//** 117 Returns the page of a tree cursor. 118 @return pointer to page */ 119 UNIV_INLINE 120 page_t* 121 btr_cur_get_page( 122 /*=============*/ 123 btr_cur_t* cursor);/*!< in: tree cursor */ 124 /*********************************************************//** 125 Returns the index of a cursor. 126 @param cursor b-tree cursor 127 @return index */ 128 #define btr_cur_get_index(cursor) ((cursor)->index) 129 /*********************************************************//** 130 Positions a tree cursor at a given record. */ 131 UNIV_INLINE 132 void 133 btr_cur_position( 134 /*=============*/ 135 dict_index_t* index, /*!< in: index */ 136 rec_t* rec, /*!< in: record in tree */ 137 buf_block_t* block, /*!< in: buffer block of rec */ 138 btr_cur_t* cursor);/*!< in: cursor */ 139 /********************************************************************//** 140 Searches an index tree and positions a tree cursor on a given level. 141 NOTE: n_fields_cmp in tuple must be set so that it cannot be compared 142 to node pointer page number fields on the upper levels of the tree! 143 Note that if mode is PAGE_CUR_LE, which is used in inserts, then 144 cursor->up_match and cursor->low_match both will have sensible values. 145 If mode is PAGE_CUR_GE, then up_match will a have a sensible value. */ 146 UNIV_INTERN 147 void 148 btr_cur_search_to_nth_level( 149 /*========================*/ 150 dict_index_t* index, /*!< in: index */ 151 ulint level, /*!< in: the tree level of search */ 152 const dtuple_t* tuple, /*!< in: data tuple; NOTE: n_fields_cmp in 153 tuple must be set so that it cannot get 154 compared to the node ptr page number field! */ 155 ulint mode, /*!< in: PAGE_CUR_L, ...; 156 NOTE that if the search is made using a unique 157 prefix of a record, mode should be PAGE_CUR_LE, 158 not PAGE_CUR_GE, as the latter may end up on 159 the previous page of the record! Inserts 160 should always be made using PAGE_CUR_LE to 161 search the position! */ 162 ulint latch_mode, /*!< in: BTR_SEARCH_LEAF, ..., ORed with 163 at most one of BTR_INSERT, BTR_DELETE_MARK, 164 BTR_DELETE, or BTR_ESTIMATE; 165 cursor->left_block is used to store a pointer 166 to the left neighbor page, in the cases 167 BTR_SEARCH_PREV and BTR_MODIFY_PREV; 168 NOTE that if has_search_latch 169 is != 0, we maybe do not have a latch set 170 on the cursor page, we assume 171 the caller uses his search latch 172 to protect the record! */ 173 btr_cur_t* cursor, /*!< in/out: tree cursor; the cursor page is 174 s- or x-latched, but see also above! */ 175 ulint has_search_latch,/*!< in: latch mode the caller 176 currently has on btr_search_latch: 177 RW_S_LATCH, or 0 */ 178 const char* file, /*!< in: file name */ 179 ulint line, /*!< in: line where called */ 180 mtr_t* mtr); /*!< in: mtr */ 181 /*****************************************************************//** 182 Opens a cursor at either end of an index. */ 183 UNIV_INTERN 184 void 185 btr_cur_open_at_index_side_func( 186 /*============================*/ 187 bool from_left, /*!< in: true if open to the low end, 188 false if to the high end */ 189 dict_index_t* index, /*!< in: index */ 190 ulint latch_mode, /*!< in: latch mode */ 191 btr_cur_t* cursor, /*!< in/out: cursor */ 192 ulint level, /*!< in: level to search for 193 (0=leaf) */ 194 const char* file, /*!< in: file name */ 195 ulint line, /*!< in: line where called */ 196 mtr_t* mtr) /*!< in/out: mini-transaction */ 197 MY_ATTRIBUTE((nonnull)); 198 #define btr_cur_open_at_index_side(f,i,l,c,lv,m) \ 199 btr_cur_open_at_index_side_func(f,i,l,c,lv,__FILE__,__LINE__,m) 200 /**********************************************************************//** 201 Positions a cursor at a randomly chosen position within a B-tree. */ 202 UNIV_INTERN 203 void 204 btr_cur_open_at_rnd_pos_func( 205 /*=========================*/ 206 dict_index_t* index, /*!< in: index */ 207 ulint latch_mode, /*!< in: BTR_SEARCH_LEAF, ... */ 208 btr_cur_t* cursor, /*!< in/out: B-tree cursor */ 209 const char* file, /*!< in: file name */ 210 ulint line, /*!< in: line where called */ 211 mtr_t* mtr); /*!< in: mtr */ 212 #define btr_cur_open_at_rnd_pos(i,l,c,m) \ 213 btr_cur_open_at_rnd_pos_func(i,l,c,__FILE__,__LINE__,m) 214 /*************************************************************//** 215 Tries to perform an insert to a page in an index tree, next to cursor. 216 It is assumed that mtr holds an x-latch on the page. The operation does 217 not succeed if there is too little space on the page. If there is just 218 one record on the page, the insert will always succeed; this is to 219 prevent trying to split a page with just one record. 220 @return DB_SUCCESS, DB_WAIT_LOCK, DB_FAIL, or error number */ 221 UNIV_INTERN 222 dberr_t 223 btr_cur_optimistic_insert( 224 /*======================*/ 225 ulint flags, /*!< in: undo logging and locking flags: if not 226 zero, the parameters index and thr should be 227 specified */ 228 btr_cur_t* cursor, /*!< in: cursor on page after which to insert; 229 cursor stays valid */ 230 ulint** offsets,/*!< out: offsets on *rec */ 231 mem_heap_t** heap, /*!< in/out: pointer to memory heap, or NULL */ 232 dtuple_t* entry, /*!< in/out: entry to insert */ 233 rec_t** rec, /*!< out: pointer to inserted record if 234 succeed */ 235 big_rec_t** big_rec,/*!< out: big rec vector whose fields have to 236 be stored externally by the caller, or 237 NULL */ 238 ulint n_ext, /*!< in: number of externally stored columns */ 239 que_thr_t* thr, /*!< in: query thread or NULL */ 240 mtr_t* mtr) /*!< in/out: mini-transaction; 241 if this function returns DB_SUCCESS on 242 a leaf page of a secondary index in a 243 compressed tablespace, the caller must 244 mtr_commit(mtr) before latching 245 any further pages */ 246 MY_ATTRIBUTE((nonnull(2,3,4,5,6,7,10), warn_unused_result)); 247 /*************************************************************//** 248 Performs an insert on a page of an index tree. It is assumed that mtr 249 holds an x-latch on the tree and on the cursor page. If the insert is 250 made on the leaf level, to avoid deadlocks, mtr must also own x-latches 251 to brothers of page, if those brothers exist. 252 @return DB_SUCCESS or error number */ 253 UNIV_INTERN 254 dberr_t 255 btr_cur_pessimistic_insert( 256 /*=======================*/ 257 ulint flags, /*!< in: undo logging and locking flags: if not 258 zero, the parameter thr should be 259 specified; if no undo logging is specified, 260 then the caller must have reserved enough 261 free extents in the file space so that the 262 insertion will certainly succeed */ 263 btr_cur_t* cursor, /*!< in: cursor after which to insert; 264 cursor stays valid */ 265 ulint** offsets,/*!< out: offsets on *rec */ 266 mem_heap_t** heap, /*!< in/out: pointer to memory heap 267 that can be emptied, or NULL */ 268 dtuple_t* entry, /*!< in/out: entry to insert */ 269 rec_t** rec, /*!< out: pointer to inserted record if 270 succeed */ 271 big_rec_t** big_rec,/*!< out: big rec vector whose fields have to 272 be stored externally by the caller, or 273 NULL */ 274 ulint n_ext, /*!< in: number of externally stored columns */ 275 que_thr_t* thr, /*!< in: query thread or NULL */ 276 mtr_t* mtr) /*!< in/out: mini-transaction */ 277 MY_ATTRIBUTE((nonnull(2,3,4,5,6,7,10), warn_unused_result)); 278 /*************************************************************//** 279 See if there is enough place in the page modification log to log 280 an update-in-place. 281 282 @retval false if out of space; IBUF_BITMAP_FREE will be reset 283 outside mtr if the page was recompressed 284 @retval true if enough place; 285 286 IMPORTANT: The caller will have to update IBUF_BITMAP_FREE if this is 287 a secondary index leaf page. This has to be done either within the 288 same mini-transaction, or by invoking ibuf_reset_free_bits() before 289 mtr_commit(mtr). */ 290 UNIV_INTERN 291 bool 292 btr_cur_update_alloc_zip_func( 293 /*==========================*/ 294 page_zip_des_t* page_zip,/*!< in/out: compressed page */ 295 page_cur_t* cursor, /*!< in/out: B-tree page cursor */ 296 dict_index_t* index, /*!< in: the index corresponding to cursor */ 297 #ifdef UNIV_DEBUG 298 ulint* offsets,/*!< in/out: offsets of the cursor record */ 299 #endif /* UNIV_DEBUG */ 300 ulint length, /*!< in: size needed */ 301 bool create, /*!< in: true=delete-and-insert, 302 false=update-in-place */ 303 mtr_t* mtr) /*!< in/out: mini-transaction */ 304 MY_ATTRIBUTE((nonnull, warn_unused_result)); 305 #ifdef UNIV_DEBUG 306 # define btr_cur_update_alloc_zip(page_zip,cursor,index,offsets,len,cr,mtr) \ 307 btr_cur_update_alloc_zip_func(page_zip,cursor,index,offsets,len,cr,mtr) 308 #else /* UNIV_DEBUG */ 309 # define btr_cur_update_alloc_zip(page_zip,cursor,index,offsets,len,cr,mtr) \ 310 btr_cur_update_alloc_zip_func(page_zip,cursor,index,len,cr,mtr) 311 #endif /* UNIV_DEBUG */ 312 /*************************************************************//** 313 Updates a record when the update causes no size changes in its fields. 314 @return locking or undo log related error code, or 315 @retval DB_SUCCESS on success 316 @retval DB_ZIP_OVERFLOW if there is not enough space left 317 on the compressed page (IBUF_BITMAP_FREE was reset outside mtr) */ 318 UNIV_INTERN 319 dberr_t 320 btr_cur_update_in_place( 321 /*====================*/ 322 ulint flags, /*!< in: undo logging and locking flags */ 323 btr_cur_t* cursor, /*!< in: cursor on the record to update; 324 cursor stays valid and positioned on the 325 same record */ 326 ulint* offsets,/*!< in/out: offsets on cursor->page_cur.rec */ 327 const upd_t* update, /*!< in: update vector */ 328 ulint cmpl_info,/*!< in: compiler info on secondary index 329 updates */ 330 que_thr_t* thr, /*!< in: query thread */ 331 trx_id_t trx_id, /*!< in: transaction id */ 332 mtr_t* mtr) /*!< in/out: mini-transaction; if this 333 is a secondary index, the caller must 334 mtr_commit(mtr) before latching any 335 further pages */ 336 MY_ATTRIBUTE((warn_unused_result, nonnull)); 337 /***********************************************************//** 338 Writes a redo log record of updating a record in-place. */ 339 UNIV_INTERN 340 void 341 btr_cur_update_in_place_log( 342 /*========================*/ 343 ulint flags, /*!< in: flags */ 344 const rec_t* rec, /*!< in: record */ 345 dict_index_t* index, /*!< in: index of the record */ 346 const upd_t* update, /*!< in: update vector */ 347 trx_id_t trx_id, /*!< in: transaction id */ 348 roll_ptr_t roll_ptr, /*!< in: roll ptr */ 349 mtr_t* mtr) /*!< in: mtr */ 350 MY_ATTRIBUTE((nonnull)); 351 /*************************************************************//** 352 Tries to update a record on a page in an index tree. It is assumed that mtr 353 holds an x-latch on the page. The operation does not succeed if there is too 354 little space on the page or if the update would result in too empty a page, 355 so that tree compression is recommended. 356 @return error code, including 357 @retval DB_SUCCESS on success 358 @retval DB_OVERFLOW if the updated record does not fit 359 @retval DB_UNDERFLOW if the page would become too empty 360 @retval DB_ZIP_OVERFLOW if there is not enough space left 361 on the compressed page */ 362 UNIV_INTERN 363 dberr_t 364 btr_cur_optimistic_update( 365 /*======================*/ 366 ulint flags, /*!< in: undo logging and locking flags */ 367 btr_cur_t* cursor, /*!< in: cursor on the record to update; 368 cursor stays valid and positioned on the 369 same record */ 370 ulint** offsets,/*!< out: offsets on cursor->page_cur.rec */ 371 mem_heap_t** heap, /*!< in/out: pointer to NULL or memory heap */ 372 const upd_t* update, /*!< in: update vector; this must also 373 contain trx id and roll ptr fields */ 374 ulint cmpl_info,/*!< in: compiler info on secondary index 375 updates */ 376 que_thr_t* thr, /*!< in: query thread */ 377 trx_id_t trx_id, /*!< in: transaction id */ 378 mtr_t* mtr) /*!< in/out: mini-transaction; if this 379 is a secondary index, the caller must 380 mtr_commit(mtr) before latching any 381 further pages */ 382 MY_ATTRIBUTE((warn_unused_result, nonnull)); 383 /*************************************************************//** 384 Performs an update of a record on a page of a tree. It is assumed 385 that mtr holds an x-latch on the tree and on the cursor page. If the 386 update is made on the leaf level, to avoid deadlocks, mtr must also 387 own x-latches to brothers of page, if those brothers exist. 388 @return DB_SUCCESS or error code */ 389 UNIV_INTERN 390 dberr_t 391 btr_cur_pessimistic_update( 392 /*=======================*/ 393 ulint flags, /*!< in: undo logging, locking, and rollback 394 flags */ 395 btr_cur_t* cursor, /*!< in/out: cursor on the record to update; 396 cursor may become invalid if *big_rec == NULL 397 || !(flags & BTR_KEEP_POS_FLAG) */ 398 ulint** offsets,/*!< out: offsets on cursor->page_cur.rec */ 399 mem_heap_t** offsets_heap, 400 /*!< in/out: pointer to memory heap 401 that can be emptied, or NULL */ 402 mem_heap_t* entry_heap, 403 /*!< in/out: memory heap for allocating 404 big_rec and the index tuple */ 405 big_rec_t** big_rec,/*!< out: big rec vector whose fields have to 406 be stored externally by the caller, or NULL */ 407 const upd_t* update, /*!< in: update vector; this is allowed also 408 contain trx id and roll ptr fields, but 409 the values in update vector have no effect */ 410 ulint cmpl_info,/*!< in: compiler info on secondary index 411 updates */ 412 que_thr_t* thr, /*!< in: query thread */ 413 trx_id_t trx_id, /*!< in: transaction id */ 414 mtr_t* mtr) /*!< in/out: mini-transaction; must be committed 415 before latching any further pages */ 416 MY_ATTRIBUTE((warn_unused_result, nonnull)); 417 /***********************************************************//** 418 Marks a clustered index record deleted. Writes an undo log record to 419 undo log on this delete marking. Writes in the trx id field the id 420 of the deleting transaction, and in the roll ptr field pointer to the 421 undo log record created. 422 @return DB_SUCCESS, DB_LOCK_WAIT, or error number */ 423 UNIV_INTERN 424 dberr_t 425 btr_cur_del_mark_set_clust_rec( 426 /*===========================*/ 427 buf_block_t* block, /*!< in/out: buffer block of the record */ 428 rec_t* rec, /*!< in/out: record */ 429 dict_index_t* index, /*!< in: clustered index of the record */ 430 const ulint* offsets,/*!< in: rec_get_offsets(rec) */ 431 que_thr_t* thr, /*!< in: query thread */ 432 mtr_t* mtr) /*!< in/out: mini-transaction */ 433 MY_ATTRIBUTE((nonnull, warn_unused_result)); 434 /***********************************************************//** 435 Sets a secondary index record delete mark to TRUE or FALSE. 436 @return DB_SUCCESS, DB_LOCK_WAIT, or error number */ 437 UNIV_INTERN 438 dberr_t 439 btr_cur_del_mark_set_sec_rec( 440 /*=========================*/ 441 ulint flags, /*!< in: locking flag */ 442 btr_cur_t* cursor, /*!< in: cursor */ 443 ibool val, /*!< in: value to set */ 444 que_thr_t* thr, /*!< in: query thread */ 445 mtr_t* mtr) /*!< in/out: mini-transaction */ 446 MY_ATTRIBUTE((nonnull, warn_unused_result)); 447 /*************************************************************//** 448 Tries to compress a page of the tree if it seems useful. It is assumed 449 that mtr holds an x-latch on the tree and on the cursor page. To avoid 450 deadlocks, mtr must also own x-latches to brothers of page, if those 451 brothers exist. NOTE: it is assumed that the caller has reserved enough 452 free extents so that the compression will always succeed if done! 453 @return TRUE if compression occurred */ 454 UNIV_INTERN 455 ibool 456 btr_cur_compress_if_useful( 457 /*=======================*/ 458 btr_cur_t* cursor, /*!< in/out: cursor on the page to compress; 459 cursor does not stay valid if compression 460 occurs */ 461 ibool adjust, /*!< in: TRUE if should adjust the 462 cursor position even if compression occurs */ 463 mtr_t* mtr) /*!< in/out: mini-transaction */ 464 MY_ATTRIBUTE((nonnull)); 465 /*******************************************************//** 466 Removes the record on which the tree cursor is positioned. It is assumed 467 that the mtr has an x-latch on the page where the cursor is positioned, 468 but no latch on the whole tree. 469 @return TRUE if success, i.e., the page did not become too empty */ 470 UNIV_INTERN 471 ibool 472 btr_cur_optimistic_delete_func( 473 /*===========================*/ 474 btr_cur_t* cursor, /*!< in: cursor on the record to delete; 475 cursor stays valid: if deletion succeeds, 476 on function exit it points to the successor 477 of the deleted record */ 478 # ifdef UNIV_DEBUG 479 ulint flags, /*!< in: BTR_CREATE_FLAG or 0 */ 480 # endif /* UNIV_DEBUG */ 481 mtr_t* mtr) /*!< in: mtr; if this function returns 482 TRUE on a leaf page of a secondary 483 index, the mtr must be committed 484 before latching any further pages */ 485 MY_ATTRIBUTE((nonnull, warn_unused_result)); 486 # ifdef UNIV_DEBUG 487 # define btr_cur_optimistic_delete(cursor, flags, mtr) \ 488 btr_cur_optimistic_delete_func(cursor, flags, mtr) 489 # else /* UNIV_DEBUG */ 490 # define btr_cur_optimistic_delete(cursor, flags, mtr) \ 491 btr_cur_optimistic_delete_func(cursor, mtr) 492 # endif /* UNIV_DEBUG */ 493 /*************************************************************//** 494 Removes the record on which the tree cursor is positioned. Tries 495 to compress the page if its fillfactor drops below a threshold 496 or if it is the only page on the level. It is assumed that mtr holds 497 an x-latch on the tree and on the cursor page. To avoid deadlocks, 498 mtr must also own x-latches to brothers of page, if those brothers 499 exist. 500 @return TRUE if compression occurred */ 501 UNIV_INTERN 502 ibool 503 btr_cur_pessimistic_delete( 504 /*=======================*/ 505 dberr_t* err, /*!< out: DB_SUCCESS or DB_OUT_OF_FILE_SPACE; 506 the latter may occur because we may have 507 to update node pointers on upper levels, 508 and in the case of variable length keys 509 these may actually grow in size */ 510 ibool has_reserved_extents, /*!< in: TRUE if the 511 caller has already reserved enough free 512 extents so that he knows that the operation 513 will succeed */ 514 btr_cur_t* cursor, /*!< in: cursor on the record to delete; 515 if compression does not occur, the cursor 516 stays valid: it points to successor of 517 deleted record on function exit */ 518 ulint flags, /*!< in: BTR_CREATE_FLAG or 0 */ 519 enum trx_rb_ctx rb_ctx, /*!< in: rollback context */ 520 mtr_t* mtr) /*!< in: mtr */ 521 MY_ATTRIBUTE((nonnull)); 522 #endif /* !UNIV_HOTBACKUP */ 523 /***********************************************************//** 524 Parses a redo log record of updating a record in-place. 525 @return end of log record or NULL */ 526 UNIV_INTERN 527 byte* 528 btr_cur_parse_update_in_place( 529 /*==========================*/ 530 byte* ptr, /*!< in: buffer */ 531 byte* end_ptr,/*!< in: buffer end */ 532 page_t* page, /*!< in/out: page or NULL */ 533 page_zip_des_t* page_zip,/*!< in/out: compressed page, or NULL */ 534 dict_index_t* index); /*!< in: index corresponding to page */ 535 /****************************************************************//** 536 Parses the redo log record for delete marking or unmarking of a clustered 537 index record. 538 @return end of log record or NULL */ 539 UNIV_INTERN 540 byte* 541 btr_cur_parse_del_mark_set_clust_rec( 542 /*=================================*/ 543 byte* ptr, /*!< in: buffer */ 544 byte* end_ptr,/*!< in: buffer end */ 545 page_t* page, /*!< in/out: page or NULL */ 546 page_zip_des_t* page_zip,/*!< in/out: compressed page, or NULL */ 547 dict_index_t* index); /*!< in: index corresponding to page */ 548 /****************************************************************//** 549 Parses the redo log record for delete marking or unmarking of a secondary 550 index record. 551 @return end of log record or NULL */ 552 UNIV_INTERN 553 byte* 554 btr_cur_parse_del_mark_set_sec_rec( 555 /*===============================*/ 556 byte* ptr, /*!< in: buffer */ 557 byte* end_ptr,/*!< in: buffer end */ 558 page_t* page, /*!< in/out: page or NULL */ 559 page_zip_des_t* page_zip);/*!< in/out: compressed page, or NULL */ 560 #ifndef UNIV_HOTBACKUP 561 /*******************************************************************//** 562 Estimates the number of rows in a given index range. 563 @return estimated number of rows */ 564 UNIV_INTERN 565 ib_int64_t 566 btr_estimate_n_rows_in_range( 567 /*=========================*/ 568 dict_index_t* index, /*!< in: index */ 569 const dtuple_t* tuple1, /*!< in: range start, may also be empty tuple */ 570 ulint mode1, /*!< in: search mode for range start */ 571 const dtuple_t* tuple2, /*!< in: range end, may also be empty tuple */ 572 ulint mode2); /*!< in: search mode for range end */ 573 /*******************************************************************//** 574 Estimates the number of different key values in a given index, for 575 each n-column prefix of the index where 1 <= n <= dict_index_get_n_unique(index). 576 The estimates are stored in the array index->stat_n_diff_key_vals[] (indexed 577 0..n_uniq-1) and the number of pages that were sampled is saved in 578 index->stat_n_sample_sizes[]. 579 If innodb_stats_method is nulls_ignored, we also record the number of 580 non-null values for each prefix and stored the estimates in 581 array index->stat_n_non_null_key_vals. */ 582 UNIV_INTERN 583 void 584 btr_estimate_number_of_different_key_vals( 585 /*======================================*/ 586 dict_index_t* index); /*!< in: index */ 587 588 /** Gets the externally stored size of a record, in units of a database page. 589 @param[in] rec record 590 @param[in] offsets array returned by rec_get_offsets() 591 @return externally stored part, in units of a database page */ 592 593 ulint 594 btr_rec_get_externally_stored_len( 595 const rec_t* rec, 596 const ulint* offsets); 597 598 /*******************************************************************//** 599 Marks non-updated off-page fields as disowned by this record. The ownership 600 must be transferred to the updated record which is inserted elsewhere in the 601 index tree. In purge only the owner of externally stored field is allowed 602 to free the field. */ 603 UNIV_INTERN 604 void 605 btr_cur_disown_inherited_fields( 606 /*============================*/ 607 page_zip_des_t* page_zip,/*!< in/out: compressed page whose uncompressed 608 part will be updated, or NULL */ 609 rec_t* rec, /*!< in/out: record in a clustered index */ 610 dict_index_t* index, /*!< in: index of the page */ 611 const ulint* offsets,/*!< in: array returned by rec_get_offsets() */ 612 const upd_t* update, /*!< in: update vector */ 613 mtr_t* mtr) /*!< in/out: mini-transaction */ 614 MY_ATTRIBUTE((nonnull(2,3,4,5,6))); 615 616 /** Operation code for btr_store_big_rec_extern_fields(). */ 617 enum blob_op { 618 /** Store off-page columns for a freshly inserted record */ 619 BTR_STORE_INSERT = 0, 620 /** Store off-page columns for an insert by update */ 621 BTR_STORE_INSERT_UPDATE, 622 /** Store off-page columns for an update */ 623 BTR_STORE_UPDATE 624 }; 625 626 /*******************************************************************//** 627 Determine if an operation on off-page columns is an update. 628 @return TRUE if op != BTR_STORE_INSERT */ 629 UNIV_INLINE 630 ibool 631 btr_blob_op_is_update( 632 /*==================*/ 633 enum blob_op op) /*!< in: operation */ 634 MY_ATTRIBUTE((warn_unused_result)); 635 636 /*******************************************************************//** 637 Stores the fields in big_rec_vec to the tablespace and puts pointers to 638 them in rec. The extern flags in rec will have to be set beforehand. 639 The fields are stored on pages allocated from leaf node 640 file segment of the index tree. 641 @return DB_SUCCESS or DB_OUT_OF_FILE_SPACE */ 642 UNIV_INTERN 643 dberr_t 644 btr_store_big_rec_extern_fields( 645 /*============================*/ 646 dict_index_t* index, /*!< in: index of rec; the index tree 647 MUST be X-latched */ 648 buf_block_t* rec_block, /*!< in/out: block containing rec */ 649 rec_t* rec, /*!< in/out: record */ 650 const ulint* offsets, /*!< in: rec_get_offsets(rec, index); 651 the "external storage" flags in offsets 652 will not correspond to rec when 653 this function returns */ 654 const big_rec_t*big_rec_vec, /*!< in: vector containing fields 655 to be stored externally */ 656 mtr_t* btr_mtr, /*!< in: mtr containing the 657 latches to the clustered index */ 658 enum blob_op op) /*! in: operation code */ 659 MY_ATTRIBUTE((nonnull, warn_unused_result)); 660 661 /*******************************************************************//** 662 Frees the space in an externally stored field to the file space 663 management if the field in data is owned the externally stored field, 664 in a rollback we may have the additional condition that the field must 665 not be inherited. */ 666 UNIV_INTERN 667 void 668 btr_free_externally_stored_field( 669 /*=============================*/ 670 dict_index_t* index, /*!< in: index of the data, the index 671 tree MUST be X-latched; if the tree 672 height is 1, then also the root page 673 must be X-latched! (this is relevant 674 in the case this function is called 675 from purge where 'data' is located on 676 an undo log page, not an index 677 page) */ 678 byte* field_ref, /*!< in/out: field reference */ 679 const rec_t* rec, /*!< in: record containing field_ref, for 680 page_zip_write_blob_ptr(), or NULL */ 681 const ulint* offsets, /*!< in: rec_get_offsets(rec, index), 682 or NULL */ 683 page_zip_des_t* page_zip, /*!< in: compressed page corresponding 684 to rec, or NULL if rec == NULL */ 685 ulint i, /*!< in: field number of field_ref; 686 ignored if rec == NULL */ 687 enum trx_rb_ctx rb_ctx, /*!< in: rollback context */ 688 mtr_t* local_mtr); /*!< in: mtr containing the latch to 689 data an an X-latch to the index 690 tree */ 691 /*******************************************************************//** 692 Copies the prefix of an externally stored field of a record. The 693 clustered index record must be protected by a lock or a page latch. 694 @return the length of the copied field, or 0 if the column was being 695 or has been deleted */ 696 UNIV_INTERN 697 ulint 698 btr_copy_externally_stored_field_prefix( 699 /*====================================*/ 700 byte* buf, /*!< out: the field, or a prefix of it */ 701 ulint len, /*!< in: length of buf, in bytes */ 702 ulint zip_size,/*!< in: nonzero=compressed BLOB page size, 703 zero for uncompressed BLOBs */ 704 const byte* data, /*!< in: 'internally' stored part of the 705 field containing also the reference to 706 the external part; must be protected by 707 a lock or a page latch */ 708 ulint local_len);/*!< in: length of data, in bytes */ 709 /*******************************************************************//** 710 Copies an externally stored field of a record to mem heap. The 711 clustered index record must be protected by a lock or a page latch. 712 @return the whole field copied to heap */ 713 UNIV_INTERN 714 byte* 715 btr_copy_externally_stored_field( 716 /*=============================*/ 717 ulint* len, /*!< out: length of the whole field */ 718 const byte* data, /*!< in: 'internally' stored part of the 719 field containing also the reference to 720 the external part; must be protected by 721 a lock or a page latch */ 722 ulint zip_size,/*!< in: nonzero=compressed BLOB page size, 723 zero for uncompressed BLOBs */ 724 ulint local_len,/*!< in: length of data */ 725 mem_heap_t* heap); /*!< in: mem heap */ 726 /*******************************************************************//** 727 Copies an externally stored field of a record to mem heap. 728 @return the field copied to heap, or NULL if the field is incomplete */ 729 UNIV_INTERN 730 byte* 731 btr_rec_copy_externally_stored_field( 732 /*=================================*/ 733 const rec_t* rec, /*!< in: record in a clustered index; 734 must be protected by a lock or a page latch */ 735 const ulint* offsets,/*!< in: array returned by rec_get_offsets() */ 736 ulint zip_size,/*!< in: nonzero=compressed BLOB page size, 737 zero for uncompressed BLOBs */ 738 ulint no, /*!< in: field number */ 739 ulint* len, /*!< out: length of the field */ 740 mem_heap_t* heap); /*!< in: mem heap */ 741 /*******************************************************************//** 742 Flags the data tuple fields that are marked as extern storage in the 743 update vector. We use this function to remember which fields we must 744 mark as extern storage in a record inserted for an update. 745 @return number of flagged external columns */ 746 UNIV_INTERN 747 ulint 748 btr_push_update_extern_fields( 749 /*==========================*/ 750 dtuple_t* tuple, /*!< in/out: data tuple */ 751 const upd_t* update, /*!< in: update vector */ 752 mem_heap_t* heap) /*!< in: memory heap */ 753 MY_ATTRIBUTE((nonnull)); 754 /***********************************************************//** 755 Sets a secondary index record's delete mark to the given value. This 756 function is only used by the insert buffer merge mechanism. */ 757 UNIV_INTERN 758 void 759 btr_cur_set_deleted_flag_for_ibuf( 760 /*==============================*/ 761 rec_t* rec, /*!< in/out: record */ 762 page_zip_des_t* page_zip, /*!< in/out: compressed page 763 corresponding to rec, or NULL 764 when the tablespace is 765 uncompressed */ 766 ibool val, /*!< in: value to set */ 767 mtr_t* mtr); /*!< in/out: mini-transaction */ 768 /*######################################################################*/ 769 770 /** In the pessimistic delete, if the page data size drops below this 771 limit, merging it to a neighbor is tried */ 772 #define BTR_CUR_PAGE_COMPRESS_LIMIT (UNIV_PAGE_SIZE / 2) 773 774 /** A slot in the path array. We store here info on a search path down the 775 tree. Each slot contains data on a single level of the tree. */ 776 777 struct btr_path_t{ 778 ulint nth_rec; /*!< index of the record 779 where the page cursor stopped on 780 this level (index in alphabetical 781 order); value ULINT_UNDEFINED 782 denotes array end */ 783 ulint n_recs; /*!< number of records on the page */ 784 ulint page_no; /*!< no of the page containing the record */ 785 ulint page_level; /*!< level of the page, if later we fetch 786 the page under page_no and it is no different 787 level then we know that the tree has been 788 reorganized */ 789 }; 790 791 #define BTR_PATH_ARRAY_N_SLOTS 250 /*!< size of path array (in slots) */ 792 793 /** Values for the flag documenting the used search method */ 794 enum btr_cur_method { 795 BTR_CUR_HASH = 1, /*!< successful shortcut using 796 the hash index */ 797 BTR_CUR_HASH_FAIL, /*!< failure using hash, success using 798 binary search: the misleading hash 799 reference is stored in the field 800 hash_node, and might be necessary to 801 update */ 802 BTR_CUR_BINARY, /*!< success using the binary search */ 803 BTR_CUR_INSERT_TO_IBUF, /*!< performed the intended insert to 804 the insert buffer */ 805 BTR_CUR_DEL_MARK_IBUF, /*!< performed the intended delete 806 mark in the insert/delete buffer */ 807 BTR_CUR_DELETE_IBUF, /*!< performed the intended delete in 808 the insert/delete buffer */ 809 BTR_CUR_DELETE_REF /*!< row_purge_poss_sec() failed */ 810 }; 811 812 /** The tree cursor: the definition appears here only for the compiler 813 to know struct size! */ 814 struct btr_cur_t { 815 dict_index_t* index; /*!< index where positioned */ 816 page_cur_t page_cur; /*!< page cursor */ 817 purge_node_t* purge_node; /*!< purge node, for BTR_DELETE */ 818 buf_block_t* left_block; /*!< this field is used to store 819 a pointer to the left neighbor 820 page, in the cases 821 BTR_SEARCH_PREV and 822 BTR_MODIFY_PREV */ 823 /*------------------------------*/ 824 que_thr_t* thr; /*!< this field is only used 825 when btr_cur_search_to_nth_level 826 is called for an index entry 827 insertion: the calling query 828 thread is passed here to be 829 used in the insert buffer */ 830 /*------------------------------*/ 831 /** The following fields are used in 832 btr_cur_search_to_nth_level to pass information: */ 833 /* @{ */ 834 enum btr_cur_method flag; /*!< Search method used */ 835 ulint tree_height; /*!< Tree height if the search is done 836 for a pessimistic insert or update 837 operation */ 838 ulint up_match; /*!< If the search mode was PAGE_CUR_LE, 839 the number of matched fields to the 840 the first user record to the right of 841 the cursor record after 842 btr_cur_search_to_nth_level; 843 for the mode PAGE_CUR_GE, the matched 844 fields to the first user record AT THE 845 CURSOR or to the right of it; 846 NOTE that the up_match and low_match 847 values may exceed the correct values 848 for comparison to the adjacent user 849 record if that record is on a 850 different leaf page! (See the note in 851 row_ins_duplicate_error_in_clust.) */ 852 ulint up_bytes; /*!< number of matched bytes to the 853 right at the time cursor positioned; 854 only used internally in searches: not 855 defined after the search */ 856 ulint low_match; /*!< if search mode was PAGE_CUR_LE, 857 the number of matched fields to the 858 first user record AT THE CURSOR or 859 to the left of it after 860 btr_cur_search_to_nth_level; 861 NOT defined for PAGE_CUR_GE or any 862 other search modes; see also the NOTE 863 in up_match! */ 864 ulint low_bytes; /*!< number of matched bytes to the 865 right at the time cursor positioned; 866 only used internally in searches: not 867 defined after the search */ 868 ulint n_fields; /*!< prefix length used in a hash 869 search if hash_node != NULL */ 870 ulint n_bytes; /*!< hash prefix bytes if hash_node != 871 NULL */ 872 ulint fold; /*!< fold value used in the search if 873 flag is BTR_CUR_HASH */ 874 /* @} */ 875 btr_path_t* path_arr; /*!< in estimating the number of 876 rows in range, we store in this array 877 information of the path through 878 the tree */ 879 }; 880 881 /** If pessimistic delete fails because of lack of file space, there 882 is still a good change of success a little later. Try this many 883 times. */ 884 #define BTR_CUR_RETRY_DELETE_N_TIMES 100 885 /** If pessimistic delete fails because of lack of file space, there 886 is still a good change of success a little later. Sleep this many 887 microseconds between retries. */ 888 #define BTR_CUR_RETRY_SLEEP_TIME 50000 889 890 /** The reference in a field for which data is stored on a different page. 891 The reference is at the end of the 'locally' stored part of the field. 892 'Locally' means storage in the index record. 893 We store locally a long enough prefix of each column so that we can determine 894 the ordering parts of each index record without looking into the externally 895 stored part. */ 896 /*-------------------------------------- @{ */ 897 #define BTR_EXTERN_SPACE_ID 0 /*!< space id where stored */ 898 #define BTR_EXTERN_PAGE_NO 4 /*!< page no where stored */ 899 #define BTR_EXTERN_OFFSET 8 /*!< offset of BLOB header 900 on that page */ 901 #define BTR_EXTERN_LEN 12 /*!< 8 bytes containing the 902 length of the externally 903 stored part of the BLOB. 904 The 2 highest bits are 905 reserved to the flags below. */ 906 /*-------------------------------------- @} */ 907 /* #define BTR_EXTERN_FIELD_REF_SIZE 20 // moved to btr0types.h */ 908 909 /** The most significant bit of BTR_EXTERN_LEN (i.e., the most 910 significant bit of the byte at smallest address) is set to 1 if this 911 field does not 'own' the externally stored field; only the owner field 912 is allowed to free the field in purge! */ 913 #define BTR_EXTERN_OWNER_FLAG 128 914 /** If the second most significant bit of BTR_EXTERN_LEN (i.e., the 915 second most significant bit of the byte at smallest address) is 1 then 916 it means that the externally stored field was inherited from an 917 earlier version of the row. In rollback we are not allowed to free an 918 inherited external field. */ 919 #define BTR_EXTERN_INHERITED_FLAG 64 920 921 /** Number of searches down the B-tree in btr_cur_search_to_nth_level(). */ 922 extern ulint btr_cur_n_non_sea; 923 /** Number of successful adaptive hash index lookups in 924 btr_cur_search_to_nth_level(). */ 925 extern ulint btr_cur_n_sea; 926 /** Old value of btr_cur_n_non_sea. Copied by 927 srv_refresh_innodb_monitor_stats(). Referenced by 928 srv_printf_innodb_monitor(). */ 929 extern ulint btr_cur_n_non_sea_old; 930 /** Old value of btr_cur_n_sea. Copied by 931 srv_refresh_innodb_monitor_stats(). Referenced by 932 srv_printf_innodb_monitor(). */ 933 extern ulint btr_cur_n_sea_old; 934 #endif /* !UNIV_HOTBACKUP */ 935 936 #ifdef UNIV_DEBUG 937 /* Flag to limit optimistic insert records */ 938 extern uint btr_cur_limit_optimistic_insert_debug; 939 #endif /* UNIV_DEBUG */ 940 941 #ifndef UNIV_NONINL 942 #include "btr0cur.ic" 943 #endif 944 945 #endif 946