WL#1074: Add Descending indexes support
Affects: Server-8.0 — Status: Complete
Goal of this WL is to provide support for indexes in descending order. I.e during forward index scan, values in such index are going in the descending order, unlike ascending order which is supported by server now. There're two reasons for this. First is often descending order is needed, but backward index scan (which could be employed to execute queries in question) is noticeably slower than forward index scan. Second reason is to be able to use indexes instead of filesort for ORDER BY clause with mixed ASC/DESC sort key parts. This WL will only support btree indexes. User would get an error when try to create descending FTS / GIS index. This WL should include: *) Support in parser to allow to create indexes with DESC key parts. Parser already allows DESC option, but simply ignores it *) Enable SHOW commands to correctly report DESC key parts *) Enable optimizer to detect when desc index could be used for ORDER BY *) Enable optimizer to use indexes with mixed ASC/DESC keyparts when they match ORDER BY clause *) Indicate backward/forward index scans *) Support for desc indexes in InnoDB (patch would be provided by InnoDB) *) Support for range/loose index scans over indexes with DESC key parts Limitations ----------- *) An expected drawback that won't be covered by this WL is that when user has two indexes, one ASC and another DESC over the same column, optimizer won't necessary will be able to pick the right index. This is limitation of current server architecture and planned to be addressed by WL#6179. *) This WL won't add support for ROR scans over indexes with DESC key parts. *) Backward range scans over indexes with mixed ASC/DESC key parts won't be fully supported as they might require tricky reordering of ranges in order to return record in proper order. *) To limit the scope of the worklog, MIN/MAX optimization for queries without GROUP BY is not performed for DESC keyparts. Examples: CREATE TABLE t1( a INT, b INT, KEY a_desc_b_asc (a DESC, b)); -- Should use (forward) index scan SELECT * FROM t1 ORDER BY a DESC; -- Should use backward index scan SELECT * FROM t1 ORDER BY a ASC; -- Should use (forward) index scan SELECT * FROM t1 ORDER BY a DESC, b ASC; -- Should use backward index scan SELECT * FROM t1 ORDER BY a ASC, b DESC; -- Should use filesort, not index SELECT * FROM t1 ORDER BY a ASC, b ASC; -- Should use filesort, not index SELECT * FROM t1 ORDER BY a DESC, b DESC; References ---------- Feature request: BUG#13375 Index with Desc sort feature User Documentation ================== * http://dev.mysql.com/doc/relnotes/mysql/8.0/en/news-8-0-1.html * http://dev.mysql.com/doc/refman/8.0/en/descending-indexes.html
Functional requirements ----------------------- f1) Server should allow to create indexes with desc key parts f2) It should be allowed to create indexes with mixed asc/desc key parts, e.g. an_index(a asc, b desc, c asc). f3) Server should be able to use index with desc key parts in forward scan mode when it matches ORDER BY clause, and in backward scan mode when it matches opposite to ORDER BY clause, e.g: -- should use forward scan on an_index defined above SELECT ... ORDER BY a ASC, b DESC -- should use backward scan on an_index defined above SELECT ... ORDER BY a DESC, b ASC f4) Only InnoDB should be fully supported, MyISAM would have limited support and might have bugs that won't be fixed. f5) SHOW commands that print index info (e.g SHOW CREATE TABLE) should print DESC for key parts that were defined as DESC f6) Both variants of EXPLAIN should print nothing for forward index scans and "Backward index scan" for backward scans. f7) DESC indexes should be supported for all data types, for which ASC indexes are available. f8) DESC indexes should be supported for both ordinary and both types of generated columns. f9) Attempt to add fulltext or spatial index with a desc keypart via CREATE/ALTER should cause an error. f10) GROUP BY no longer does implicit ordering. Order is taken into account only for those columns, for which ASC/DESC is explicitly specified. f11) DISTINCT could use any index containing matching columns. f12) MIX/MAX optimization for queries with aggregates and no GROUP BY won't use indexes with DESC key parts, to limit the scope of WL. Non-functional requirements --------------------------- nf1) An error should be thrown when creating a non-btree index with explicitly specified ASC/DESC key parts (e.g GIS/FTS/HASH index), as those indexes are naturally unordered.
After this WL user should be able to do following CREATE TABLE t1 (a INT, b INT, KEY a_idx(a DESC, b ASC)); INSERT INTO t1 VALUES(1,1),(2,2),(3,3); SELECT * FROM t1 ORDER BY a DESC, b; 3 3 2 2 1 1 and EXPLAIN will no longer print "Using filesort" This means that an index with descending key part was created over the "t1" table and server uses it in forward scan mode to retrieve values in required order. Prior to this WL filesort is used. DESC indexes may also be used for joins, GROUP BY and DISTINCT. In these cases the optimizer will always use forward scan, independently of index order and ASC/DESC flags specified in GROUP BY. It's acceptable, as we deprecated any particular sort order after GROUP BY in 5.6 and such approach would allow us to better use available indexes. Effectively this means that order of rows may be different, compared to when an ASC index is used, and this will affect some tests cases results. Server already contains almost all necessary code to handle both ASC and DESC indexes. In scope of this WL only small adjustments are made to take index order into account. MyISAM also already supports desc indexes, no changes are needed there. Biggest changes are: *) Parser now saves DESC flag, instead of ignoring it *) The order of key parts are stored in data dictionary *) SHOW CREATE TABLE/SHOW INDEX code prints DESC for key parts having descending order. For SHOW INDEX key part's order is indicated in the Collation field, by "D" or "A" for DESC or ASC, respectively. Same is shown in the information_schema.statistics table. *) Traditional EXPLAIN shows "Backward index scan" in the Extra field, when backward index scan in used. Structured EXPLAIN shows "backward_index_scan: true" to indicate that. If forward scan is used, no additional information is printed. *) Optimizer, at various places, takes sort order into account, e.g. when comparing key values in key_rec_cmp(). *) Range optimizer to allow range scans over indexes with mixed ASC/DESC keyparts *) Since FTS/HASH/SPATIAL indexes are naturally unordered, usage of explicit ASC/DESC on key parts of such indexes will result in error. This is a change in behavior from 5.7 and potentially could break replication.
Changes to parser ================= Key_part_spec now has is_ascending flag that indicates order of the key part. Parser now sets it with Key_part_spec::set_ascending(), instead of ignoring the given DESC flag. Key_part_spec::operator== also takes is_ascending into account. Changes in data dictionary ========================== New DD already has methods to save/read DESC flag. fill_dd_index_elements_from_key_parts() and fill_index_element_from_dd() are taking care about saving/restoring the flag to/from DD. Changes in range optimizer ========================== Overall range optimizer algorithm is remained as is: 1) generate SEL_ARG tree 2) generate keys for range estimates, in sel_arg_range_seq_next() 3) collect estimates via handler API 4) generate keys for quick selects, in get_quick_keys() 5) do the range scan This WL alters steps 2 and 4. In both steps 2 and 4 approach to DESC key parts is the same: generally speaking, range optimizer uses max value from SEL_ARG tree to generate min key for a desc key part and vice versa. Min/max flags are also need to be "inverted" appropriately. Such "inversion" consists of changing NO_MIN_RANGE/NEAR_MIN to NO_MAX_RANGE/NEAR_MAX appropriately, and vice versa. This approach is implemented in several places: 1) SEL_ARG class: now it has is_ascending flag that indicates order direction of the key part. Two new helper functions, get_min_flag()/get_max_flag(), are returning min/max_flags according to value of is_ascending. E.g for ASC key parts, get_min_flag() returns min_flag, for DESC key parts "inverted" max_flag is returned. Same (but opposite) is done my get_max_flag(). The inversion itself is done by two new helper functions, invert_min_flag() and invert_max_flag(). SEL_ARG::store_min()/store_max() are renamed to SEL_ARG::store_min_value() and store_max_value() for easier reading. SEL_ARG::store_min_key()/store_max_key() also take is_ascending into account when recursing for a next key part. Changes to SEL_ARG::stack_push_range(), sel_arg_range_seq_next() and get_quick_keys() are very similar - depending on is_ascending flag, for storing start key they call either store_min/store_min_key (for ASC key part) or store_max/store_max_key (for DESC key part). Same (but opposite) for end key. quick_range_seq_init() depending of whether the first key part is ASC or DESC, this function will initialize traversal of ranges in forward, or backward direction, to preserve order or records when multiple ranges are retrieved. quick_range_seq_next() is adjusted appropriately. Changes to loose index scan =========================== LIS optimization for MIN()/MAX() aggregates supports indexes with DESC key parts. Changes are made to QUICK_GROUP_MIN_MAX_SELECT::get_next() function. Instead of updating MIN() on the first key and MAX() on the last, it resets and updates both on the first key, and only updates both on the last. The point is that it's unknown whether the first key will be min or max, so both are updated and functions will pick appropriate value on their own. Other changes ============= As before, the order flag HA_REVERSE_SORT is stored in the KEY_PART_INFO::key_part_flag and taken care of (in addition) at many places: has_index_def_changed() - check key definitions to match key_rec_cmp() - compare key values find_key_for_maxmin() - block MIX/MAX optimization for DESC key parts test_if_cheaper_ordering() - prefer forward scans over backward check_duplicate_key() - compare keys definitions mysql_prepare_create_table() - prepare info for table creation mysql_prepare_alter_table() - prepare info for table alteration store_create_info() - print info for SHOW CREATE TABLE Explain_join::explain_extra() - reports backward scan for EXPLAIN
Copyright (c) 2000, 2022, Oracle Corporation and/or its affiliates. All rights reserved.