mirror of
https://github.com/MariaDB/server.git
synced 2026-10-23 18:49:29 +03:00
81a047b1c2
Row_sel_get_clust_rec_for_mysql::operator() descends the clustered B-tree from the root for every row whose clustered-index record a secondary-index scan must read, although consecutive rows land on the same clustered leaf page wherever the secondary order tracks the clustered one. A non-covering scan needs one for every row, a locking read needs one whatever the secondary index holds, because an exclusive select lock type makes ha_innobase::build_template() build its template against the clustered index, and a covering scan needs one for every row of a secondary leaf whose PAGE_MAX_TRX_ID its read view cannot see. ANALYZE FORMAT=JSON charges each descent its full height, and those descents are nearly the whole cost: the secondary index is charged its own descent and one page for each further leaf, and nothing per row, because the position that its cursor holds between two rows is restored optimistically, which latches the leaf again without counting an access. So pages_accessed is the row count times the height of the clustered index, plus a handful: 1000 rows over a 2-level clustered index cost 2006 and 750 rows over a 3-level one cost 2291, where a full table scan of the same data costs 23 and 110. Let a handle remember the clustered leaves that the lookups of one statement reached, and let the next lookup try them before it descends again. The reasoning behind each value and each rejection is in the comments beside it. row0mysql.h defines clust_leaf_hint_slot, which names one leaf: its page number, copies of its first and last user record truncated to the key fields, which bound the key range that the leaf held when it was remembered, and the rec_get_offsets() of both. A slot of a leaf that had no right sibling names no last key, because every key above the last record of the rightmost leaf still belongs to it. CLUST_LEAF_HINT_SLOTS (4) slots hang off the new row_prebuilt_t::clust_leaf_hint, beside clust_leaf_hint_mru, the most recently used order held as slot numbers, and clust_leaf_hint_n and clust_leaf_hint_miss, the used-slot count and the miss counter. row0sel.cc holds the policy. row_sel_clust_leaf_hint_covers() compares a key against the remembered ranges, so a lookup that no slot can answer costs no buffer pool access and no pages_accessed. row_sel_clust_leaf_hint_search() probes the first slot that covers the key and moves it to the front of the order. row_sel_clust_leaf_hint_remember() records the leaf that a descent landed on, and refreshes the slot of a leaf that is remembered already rather than spend a second one on the same page. Two descents fill no slot: the lookups of a statement before lookup CLUST_LEAF_HINT_MIN_LOOKUPS (4), and a leaf that is the root. row_sel_clust_leaf_hint_armed() stands a scan down once the slots stop paying for themselves: a miss adds CLUST_LEAF_HINT_MISS_WEIGHT (2) to the miss counter and a hit takes one away, so a scan gives the slots up where it answers too little of its lookups to pay for them, CLUST_LEAF_HINT_MAX_MISSES (8) misses with no hit between them still reach the threshold, and one lookup in CLUST_LEAF_HINT_RETRY (1024) starts the count again, so a scan whose order becomes correlated only later recovers. Both halves of the cost stop there, the test of the slots and the copies that refresh them. Row_sel_get_clust_rec_for_mysql::operator() calls all of this in place of its btr_pcur_open_with_no_init(), and only where the adaptive hash index is disabled. A guess of that index lands on the record with no page-local search and no page access to charge, but neither of the two is faster for every shape of index and scan, and a hint that runs first stops that index from adding entries. The adaptive hash index is off by default, so the hints are active in a default configuration. btr0cur.h and btr0cur.cc add btr_cur_t::try_leaf_hint(), a PAGE_CUR_LE, BTR_SEARCH_LEAF search on one named leaf, which starts from the record where the last search of that leaf landed while that record is still valid, and from a binary search of the page otherwise. It acquires the page with buf_page_try_get(): a hint is never derived from a latched parent page, so by the time it is tried it can precede the caller's already-latched secondary-index leaf in the latching order, where a blocking wait can deadlock. It then rejects the page unless the checks that it makes on the latched frame put the match on it. Those checks are the sole authority on the result, so a stale range costs a wasted probe or a needless descent, never a wrong result, and the ranges need no invalidation protocol. A slot also holds a btr_leaf_step, where the last search of its leaf landed: the block, its buf_block_t::modify_clock() and the record. A record pointer stays valid while the block holds the same page and the clock has not moved, because eviction, deletion and reorganization advance the clock and an insertion moves no record. While the step is valid, btr_cur_t::try_leaf_hint() starts from that record instead of a binary search of the page. page0cur.cc adds page_cur_search_near(), which compares the key with the record and with one neighbour, and positions the cursor on the record, on the record after it or on the record before it. It refuses any other answer and leaves it to page_cur_search_with_match(). So a scan whose consecutive rows are neighbours in the clustered index finds each row with two comparisons. A scan that reads the clustered leaf in falling key order does the same: a secondary key that falls as the primary key rises, or a secondary index read backward. Where the secondary order tracks the clustered one with gaps between the rows, the step fails, and btr_leaf_step::expect (below) leaves the leaf to the binary search. The step refuses the metadata pseudo-record, which compares below every key on 0 fields, and a record before it that is the infimum. A debug build checks every successful step against the binary search. A failed step costs comparisons whose outcome no branch predictor can guess, so btr_leaf_step::expect gates it. The next search tries the step only where this one landed where a step would have: on the remembered record, or right before or after it. The successor link of the landing record tells the record right before, because finding a predecessor takes a walk of the page directory. So a scan in random order over a few leaves, which the slots answer in full, keeps the binary search and pays only the tests that set expect. row_sel_clust_leaf_hint_remember() sets the step on the record where a descent landed, with expect set. ha_innodb.cc: ha_innobase::reset() zeroes the used-slot count and the miss counter per statement, matching autoinc_last_value. row0mysql.cc: row_prebuilt_free() frees the key buffers that the slots own. innodb.clust_leaf_hint measures pages_accessed over key orders that differ in how closely the secondary order tracks the clustered one, and further tables check query results over the record formats and key shapes that a clustered-index lookup has to read, down to the metadata pseudo-record of instant ALTER TABLE, to leaves that split and merge while a locking read walks them, and to a record that a remembered leaf supplies for a scan that must then rebuild an older version of it. Two of the tables scan a covering index, which reads a clustered record under an exclusive select lock type and under a PAGE_MAX_TRX_ID that the read view cannot see. clust_leaf_hint_off_debug runs the same body with the hints turned off, through a debug switch that returns before a lookup tests or refreshes the slots, so a diff of the two .result files is what the hints save: 2006 to 1031 (2-level clustered index), 2291 to 1011 (3-level), 4006 to 2015 (two interleaved key ranges), 12016 to 9078 (locality in the second half alone) and 20020 to 10045 for a covering scan that FOR UPDATE makes non-covering, where the same scan without FOR UPDATE costs 20 in both files. Two orders with too little locality to pay for the slots give them up early and end within a hundred accesses of the unhinted count: 20020 to 19966 (decorrelated) and 20020 to 19999 (shuffled). Two further tables in innodb.clust_leaf_hint cover the step back. t16 scans a secondary index whose keys fall as the primary key rises, and reads an ascending secondary index backward: 20020 to 10047 for both. t17 runs the inverse scan on ROW_FORMAT=REDUNDANT with an instantly added column. innodb.clust_leaf_hint_backward_debug reaches the two refusals of the step back that no count shows, at the infimum and at the metadata pseudo-record. A lookup reaches either only for a key that left the clustered index while the slot still covers it. The rollback of an insert over a delete-marked record removes the key while purge leaves the secondary entry, and a PAGE_MAX_TRX_ID that the read view cannot see makes the reader look that entry up. A debug switch writes each refusal to the error log, and the case reads both back. A slot stays valid when dict_index_t::clear_instant_alter() changes the index under a reader that holds a shared metadata lock, between two lookups or during one. That clear runs where purge or rollback removes the last user record of a single-page table whose only instant change was ADD COLUMN, and it raises dict_index_t::n_core_fields. rec_copy_prefix_to_buf() writes the copies in the format of an index without instant ADD COLUMN, their offsets are made with them, and the comparisons depend on the key fields alone, which no instant change moves. So the slots do not record n_core_fields, and the hints read it only under a latch on a clustered leaf. innodb.clust_leaf_hint_instant_alter makes a lookup compare against a slot that a clear has outlived. The clear needs the clustered index to lose the last user record of its root page, while no leaf that is the root fills a slot, so the tree has to shrink between the two, which purge does there. The reader therefore reads uncommitted rows at READ UNCOMMITTED and waits in a stored function while a rollback and purge take them away, and one row that arrives above the position it stopped at is the lookup that tests the slots. main.rowid_filter_innodb: 90 to 88, and its ahi combination unchanged. A static_assert in Row_sel_get_clust_rec_for_mysql::operator() fails to compile if btr_search.enabled stops being a Boolean that applies to every index, because the test !btr_search.enabled that stands the hints down would then have to become !btr_search.is_enabled(clust_index).
Code status:
ci.appveyor.com
MariaDB: The innovative open source database
MariaDB was designed as a drop-in replacement of MySQL(R) with more features, new storage engines, fewer bugs, and better performance.
MariaDB is brought to you by the MariaDB Foundation and the MariaDB Corporation. Please read the CREDITS file for details about the MariaDB Foundation, and who is developing MariaDB.
MariaDB is developed by many of the original developers of MySQL who now work for the MariaDB Corporation, the MariaDB Foundation and by many people in the community.
MySQL, which is the base of MariaDB, is a product and trademark of Oracle Corporation, Inc. For a list of developers and other contributors, see the Credits appendix. You can also run 'SHOW authors' to get a list of active contributors.
A description of the MariaDB project and a manual can be found at:
https://mariadb.com/docs/release-notes
Getting the code, building it and testing it
Refer to the following guide: https://mariadb.org/get-involved/getting-started-for-developers/get-code-build-test/ which outlines how to build the source code correctly and run the MariaDB testing framework, as well as which branch to target for your contributions.
Help
More help is available from the Maria Discuss mailing list https://lists.mariadb.org/postorius/lists/discuss.lists.mariadb.org/ and MariaDB's Zulip instance, https://mariadb.zulipchat.com/
Licensing
MariaDB is specifically available only under version 2 of the GNU General Public License (GPLv2). (I.e. Without the "any later version" clause.) This is inherited from MySQL. Please see the README file in the MySQL distribution for more information.
License information can be found in the COPYING file. Third party license information can be found in the THIRDPARTY file.
Bug Reports
Bug and/or error reports regarding MariaDB should be submitted at: https://jira.mariadb.org
For reporting security vulnerabilities, see our security-policy.
The code for MariaDB, including all revision history, can be found at: https://github.com/MariaDB/server