- commits - lists.mariadb.org

[Commits] de442635810: MDEV-26996: Support descending indexes in the range optimizer
by psergey 14 Dec '21

14 Dec '21

revision-id: de4426358101575648e968b4cdae35527da74b23 (mariadb-10.6.1-249-gde442635810) parent(s): c95270df0bc0ba4c93eeb17f078ac85dfd5f5c1b author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2021-12-14 16:39:37 +0300 message: MDEV-26996: Support descending indexes in the range optimizer - Code cleanup - Disable "Using index for GROUP BY" over indexes with DESC keyparts --- mysql-test/main/desc_index_range.result | 25 ++++++++++- mysql-test/main/desc_index_range.test | 13 +++++- mysql-test/main/opt_trace.result | 52 +++++++++++----------- mysql-test/main/opt_trace_index_merge.result | 8 ++-- .../main/opt_trace_index_merge_innodb.result | 8 ++-- sql/opt_range.cc | 23 +++++----- 6 files changed, 82 insertions(+), 47 deletions(-) diff --git a/mysql-test/main/desc_index_range.result b/mysql-test/main/desc_index_range.result index 53a608fe2d9..feec5dc1720 100644 --- a/mysql-test/main/desc_index_range.result +++ b/mysql-test/main/desc_index_range.result @@ -154,5 +154,28 @@ json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) "(4,80) <= (a,b) <= (2,50)" ] ] -set optimizer_trace=default; drop table t2; +# +# Check that "Using index for group-by" is disabled (it's not supported, yet) +# +CREATE TABLE t1 (p int NOT NULL, a int NOT NULL, PRIMARY KEY (p,a desc)); +insert into t1 select 2,seq from seq_0_to_1000; +EXPLAIN select MIN(a) from t1 where p = 2 group by p; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ref PRIMARY PRIMARY 4 const 1000 Using index +select json_detailed(json_extract(trace, '$**.potential_group_range_indexes')) +from information_schema.optimizer_trace; +json_detailed(json_extract(trace, '$**.potential_group_range_indexes')) +[ + + [ + + { + "index": "PRIMARY", + "usable": false, + "cause": "Reverse-ordered (not supported yet)" + } + ] +] +drop table t1; +set optimizer_trace=default; diff --git a/mysql-test/main/desc_index_range.test b/mysql-test/main/desc_index_range.test index 94d6b76258d..bcb9ce83318 100644 --- a/mysql-test/main/desc_index_range.test +++ b/mysql-test/main/desc_index_range.test @@ -73,5 +73,16 @@ select * from t2 where a between 2 and 4 and b between 50 and 80; select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) from information_schema.optimizer_trace; -set optimizer_trace=default; drop table t2; + +--echo # +--echo # Check that "Using index for group-by" is disabled (it's not supported, yet) +--echo # +CREATE TABLE t1 (p int NOT NULL, a int NOT NULL, PRIMARY KEY (p,a desc)); +insert into t1 select 2,seq from seq_0_to_1000; +EXPLAIN select MIN(a) from t1 where p = 2 group by p; +select json_detailed(json_extract(trace, '$**.potential_group_range_indexes')) +from information_schema.optimizer_trace; +drop table t1; + +set optimizer_trace=default; diff --git a/mysql-test/main/opt_trace.result b/mysql-test/main/opt_trace.result index 4913aac6c30..f7f5476ab23 100644 --- a/mysql-test/main/opt_trace.result +++ b/mysql-test/main/opt_trace.result @@ -1203,8 +1203,8 @@ EXPLAIN SELECT DISTINCT a FROM t1 { }, { "index": "a", - "key_parts": ["a"], - "usable": true + "usable": true, + "key_parts": ["a"] } ], "best_covering_index_scan": { @@ -1386,8 +1386,8 @@ EXPLAIN SELECT MIN(d) FROM t1 where b=2 and c=3 group by a { "potential_range_indexes": [ { "index": "a", - "key_parts": ["a", "b", "c", "d"], - "usable": true + "usable": true, + "key_parts": ["a", "b", "c", "d"] } ], "best_covering_index_scan": { @@ -1585,8 +1585,8 @@ EXPLAIN SELECT id,MIN(a),MAX(a) FROM t1 WHERE a>=20010104e0 GROUP BY id { "potential_range_indexes": [ { "index": "id", - "key_parts": ["id", "a"], - "usable": true + "usable": true, + "key_parts": ["id", "a"] } ], "best_covering_index_scan": { @@ -1773,8 +1773,8 @@ EXPLAIN SELECT * FROM t1 WHERE a = 20010104e0 GROUP BY id { "potential_range_indexes": [ { "index": "id", - "key_parts": ["id", "a"], - "usable": true + "usable": true, + "key_parts": ["id", "a"] } ], "best_covering_index_scan": { @@ -2012,13 +2012,13 @@ explain select * from t1 where a=1 and b=2 order by c limit 1 { }, { "index": "a_c", - "key_parts": ["a", "c"], - "usable": true + "usable": true, + "key_parts": ["a", "c"] }, { "index": "a_b", - "key_parts": ["a", "b"], - "usable": true + "usable": true, + "key_parts": ["a", "b"] } ], "setup_range_conditions": [], @@ -2215,8 +2215,8 @@ explain select * from t1 where a=1 and b=2 order by c limit 1 { }, { "index": "a_c", - "key_parts": ["a", "c"], - "usable": true + "usable": true, + "key_parts": ["a", "c"] }, { "index": "a_b", @@ -3231,18 +3231,18 @@ explain select * from t1 where pk = 2 and a=5 and b=1 { "potential_range_indexes": [ { "index": "pk", - "key_parts": ["pk"], - "usable": true + "usable": true, + "key_parts": ["pk"] }, { "index": "pk_a", - "key_parts": ["pk", "a"], - "usable": true + "usable": true, + "key_parts": ["pk", "a"] }, { "index": "pk_a_b", - "key_parts": ["pk", "a", "b"], - "usable": true + "usable": true, + "key_parts": ["pk", "a", "b"] } ], "best_covering_index_scan": { @@ -3749,8 +3749,8 @@ explain delete from t0 where t0.a<3 { "potential_range_indexes": [ { "index": "a", - "key_parts": ["a"], - "usable": true + "usable": true, + "key_parts": ["a"] } ], "setup_range_conditions": [], @@ -3887,8 +3887,8 @@ explain delete t0,t1 from t0, t1 where t0.a=t1.a and t1.a<3 { "potential_range_indexes": [ { "index": "a", - "key_parts": ["a"], - "usable": true + "usable": true, + "key_parts": ["a"] } ], "best_covering_index_scan": { @@ -3952,8 +3952,8 @@ explain delete t0,t1 from t0, t1 where t0.a=t1.a and t1.a<3 { "potential_range_indexes": [ { "index": "a", - "key_parts": ["a"], - "usable": true + "usable": true, + "key_parts": ["a"] } ], "best_covering_index_scan": { diff --git a/mysql-test/main/opt_trace_index_merge.result b/mysql-test/main/opt_trace_index_merge.result index 011875762d1..f1e13586eda 100644 --- a/mysql-test/main/opt_trace_index_merge.result +++ b/mysql-test/main/opt_trace_index_merge.result @@ -78,13 +78,13 @@ explain select * from t1 where a=1 or b=1 { "potential_range_indexes": [ { "index": "a", - "key_parts": ["a"], - "usable": true + "usable": true, + "key_parts": ["a"] }, { "index": "b", - "key_parts": ["b"], - "usable": true + "usable": true, + "key_parts": ["b"] }, { "index": "c", diff --git a/mysql-test/main/opt_trace_index_merge_innodb.result b/mysql-test/main/opt_trace_index_merge_innodb.result index d372be85bd8..0ddaaeae89d 100644 --- a/mysql-test/main/opt_trace_index_merge_innodb.result +++ b/mysql-test/main/opt_trace_index_merge_innodb.result @@ -93,13 +93,13 @@ explain select * from t1 where pk1 != 0 and key1 = 1 { "potential_range_indexes": [ { "index": "PRIMARY", - "key_parts": ["pk1", "pk2"], - "usable": true + "usable": true, + "key_parts": ["pk1", "pk2"] }, { "index": "key1", - "key_parts": ["key1"], - "usable": true + "usable": true, + "key_parts": ["key1"] }, { "index": "key2", diff --git a/sql/opt_range.cc b/sql/opt_range.cc index 541a921435a..ae2b5060625 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -2809,12 +2809,11 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, trace_idx_details.add("usable", false).add("cause", "fulltext"); continue; // ToDo: ft-keys in non-ft ranges, if possible SerG } - + trace_idx_details.add("usable", true); param.key[param.keys]=key_parts; key_part_info= key_info->key_part; uint cur_key_len= 0; Json_writer_array trace_keypart(thd, "key_parts"); - bool unusable_has_desc_keyparts= false; for (uint part= 0 ; part < n_key_parts ; part++, key_parts++, key_part_info++) { @@ -2829,18 +2828,9 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, (key_info->flags & HA_SPATIAL) ? Field::itMBR : Field::itRAW; /* Only HA_PART_KEY_SEG is used */ key_parts->flag= (uint8) key_part_info->key_part_flag; - if (key_part_info->key_part_flag & HA_REVERSE_SORT) - unusable_has_desc_keyparts= true; trace_keypart.add(key_parts->field->field_name); } trace_keypart.end(); - trace_idx_details.add("usable", !unusable_has_desc_keyparts); - unusable_has_desc_keyparts= false; - if (unusable_has_desc_keyparts) // TODO MDEV-13756 - { - key_parts= param.key[param.keys]; - continue; - } param.real_keynr[param.keys++]=idx; if (cur_key_len > max_key_len) max_key_len= cur_key_len; @@ -13833,6 +13823,17 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree, double read_time) cause= "not covering"; goto next_index; } + + { + for (uint i= 0; i < table->actual_n_key_parts(cur_index_info); i++) + { + if (cur_index_info->key_part[i].key_part_flag & HA_REVERSE_SORT) + { + cause="Reverse-ordered (not supported yet)"; + goto next_index; + } + } + } /* This function is called on the precondition that the index is covering.

1 0

[Commits] 870143250c5: Post-rebase fix
by psergey 14 Dec '21

14 Dec '21

revision-id: 870143250c54fcff949f1d8985b9fe1d2c47e26a (mariadb-10.6.1-250-g870143250c5) parent(s): 7f69a3c91462d6625c5f32261b0c059471156e6a author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2021-12-14 16:06:37 +0300 message: Post-rebase fix --- sql/key.cc | 1 - 1 file changed, 1 deletion(-) diff --git a/sql/key.cc b/sql/key.cc index 467a4f75044..4509634da2d 100644 --- a/sql/key.cc +++ b/sql/key.cc @@ -578,7 +578,6 @@ int key_rec_cmp(void *key_p, uchar *first_rec, uchar *second_rec) const int LESS= -GREATER; field= key_part->field; - int sort_order = (key_part->key_part_flag & HA_REVERSE_SORT) ? -1 : 1; if (key_part->null_bit) {

1 0

[Commits] 7f69a3c9146: Descending indexes code exposed a gap in fix for MDEV-25858.
by psergey 14 Dec '21

14 Dec '21

revision-id: 7f69a3c91462d6625c5f32261b0c059471156e6a (mariadb-10.6.1-249-g7f69a3c9146) parent(s): 9f5aa2c1d3435d66ad922c04a961905bad1ab2b7 author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2021-12-14 16:02:44 +0300 message: Descending indexes code exposed a gap in fix for MDEV-25858. Extend the fix for MDEV-25858 to handle non-reverse-ordered ORDER BY: If test_if_skip_sort_order() decides to use an index to produce rows in the required ordering, it should disable "Range Checked for Each Record". The fix needs to be backported to earlier versions. --- mysql-test/main/order_by_innodb.result | 34 ++++++++++++++++++-- mysql-test/main/order_by_innodb.test | 37 ++++++++++++++++++++-- .../suite/engines/funcs/r/ix_using_order.result | 4 +-- sql/sql_select.cc | 8 +++++ 4 files changed, 77 insertions(+), 6 deletions(-) diff --git a/mysql-test/main/order_by_innodb.result b/mysql-test/main/order_by_innodb.result index 7083f04f7c4..77c40a8c0de 100644 --- a/mysql-test/main/order_by_innodb.result +++ b/mysql-test/main/order_by_innodb.result @@ -180,7 +180,7 @@ id id 1 NULL 2 1 3 3 -create index for_latest_sort on t2 (d1 desc, d2 desc, id desc); +create index for_latest_sort on t2 (d1, d2, id); select t1.id,t2.id from @@ -198,7 +198,37 @@ id id 1 NULL 2 1 3 3 -drop table t1,t2; +# Now, same as above but use a DESC index +CREATE TABLE t3 ( +id int NOT NULL PRIMARY KEY, +id2 int NOT NULL, +d1 datetime, +d2 timestamp NOT NULL, +KEY id2 (id2) +) engine=innodb; +insert into t3 values +(1,2,'2019-03-05 00:00:00','2019-03-06 00:00:00'), +(2,3,'2019-03-05 00:00:00','2019-03-06 00:00:00'), +(3,3,'2019-03-06 00:00:00','2019-03-05 00:00:00'); +create index for_latest_sort on t3 (d1 desc, d2 desc, id desc); +select +t1.id,t3.id +from +t1 left join +t3 on t3.id2 = t1.id and +t3.id = (select dd.id +from t3 dd +where +dd.id2 = t1.id and +d1 > '2019-02-06 00:00:00' + order by +dd.d1 desc, dd.d2 desc, dd.id desc limit 1 +); +id id +1 NULL +2 1 +3 3 +drop table t1,t2,t3; # End of 10.2 tests # # MDEV-26938 Support descending indexes internally in InnoDB diff --git a/mysql-test/main/order_by_innodb.test b/mysql-test/main/order_by_innodb.test index db801ef79f3..7fb036aaf5d 100644 --- a/mysql-test/main/order_by_innodb.test +++ b/mysql-test/main/order_by_innodb.test @@ -170,7 +170,7 @@ from dd.d1 desc, dd.d2 desc, dd.id desc limit 1 ); -create index for_latest_sort on t2 (d1 desc, d2 desc, id desc); +create index for_latest_sort on t2 (d1, d2, id); select t1.id,t2.id @@ -185,7 +185,40 @@ from order by dd.d1 desc, dd.d2 desc, dd.id desc limit 1 ); -drop table t1,t2; + +--echo # Now, same as above but use a DESC index + +CREATE TABLE t3 ( + id int NOT NULL PRIMARY KEY, + id2 int NOT NULL, + d1 datetime, + d2 timestamp NOT NULL, + KEY id2 (id2) +) engine=innodb; + +insert into t3 values + (1,2,'2019-03-05 00:00:00','2019-03-06 00:00:00'), + (2,3,'2019-03-05 00:00:00','2019-03-06 00:00:00'), + (3,3,'2019-03-06 00:00:00','2019-03-05 00:00:00'); +create index for_latest_sort on t3 (d1 desc, d2 desc, id desc); + + +select + t1.id,t3.id +from + t1 left join + t3 on t3.id2 = t1.id and + t3.id = (select dd.id + from t3 dd + where + dd.id2 = t1.id and + d1 > '2019-02-06 00:00:00' + order by + dd.d1 desc, dd.d2 desc, dd.id desc limit 1 + ); + + +drop table t1,t2,t3; --echo # End of 10.2 tests diff --git a/mysql-test/suite/engines/funcs/r/ix_using_order.result b/mysql-test/suite/engines/funcs/r/ix_using_order.result index 645b3fcfbc4..1e4389ce251 100644 --- a/mysql-test/suite/engines/funcs/r/ix_using_order.result +++ b/mysql-test/suite/engines/funcs/r/ix_using_order.result @@ -17,7 +17,7 @@ SHOW CREATE TABLE t1; Table Create Table t1 CREATE TABLE `t1` ( `c1` int(11) NOT NULL, - KEY `i1` (`c1`) USING BTREE + KEY `i1` (`c1` DESC) USING BTREE ) ENGINE=ENGINE DEFAULT CHARSET=latin1 DROP TABLE t1; SHOW TABLES; @@ -40,7 +40,7 @@ SHOW CREATE TABLE t1; Table Create Table t1 CREATE TABLE `t1` ( `c1` int(11) NOT NULL, - UNIQUE KEY `i1` (`c1`) USING BTREE + UNIQUE KEY `i1` (`c1` DESC) USING BTREE ) ENGINE=ENGINE DEFAULT CHARSET=latin1 DROP INDEX i1 ON t1; DROP TABLE t1; diff --git a/sql/sql_select.cc b/sql/sql_select.cc index b08f2dd2545..ed224cce5e6 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -24265,7 +24265,15 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit, } } else if (select && select->quick) + { + /* Cancel "Range checked for each record" */ + if (tab->use_quick == 2) + { + tab->use_quick= 1; + tab->read_first_record= join_init_read_record; + } select->quick->need_sorted_output(); + } if (tab->type == JT_EQ_REF) tab->read_record.unlock_row= join_read_key_unlock_row;

1 0

[Commits] 9f5aa2c1d34: Don't run main.desc_index_range under embedded. It uses optimizer trace
by psergey 14 Dec '21

14 Dec '21

revision-id: 9f5aa2c1d3435d66ad922c04a961905bad1ab2b7 (mariadb-10.6.1-248-g9f5aa2c1d34) parent(s): 809bda915484fb495fb31e30cdaf271e154ddd48 author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2021-12-14 16:02:34 +0300 message: Don't run main.desc_index_range under embedded. It uses optimizer trace --- mysql-test/main/desc_index_range.test | 3 +++ 1 file changed, 3 insertions(+) diff --git a/mysql-test/main/desc_index_range.test b/mysql-test/main/desc_index_range.test index 7fdf439c523..94d6b76258d 100644 --- a/mysql-test/main/desc_index_range.test +++ b/mysql-test/main/desc_index_range.test @@ -4,6 +4,9 @@ --source include/have_sequence.inc --source include/have_innodb.inc +# The test uses optimizer trace: +--source include/not_embedded.inc + create table t1 ( a int, key (a desc)

1 0

[Commits] 809bda91548: MDEV-26996: Support descending indexes in the range optimizer
by psergey 14 Dec '21

14 Dec '21

revision-id: 809bda915484fb495fb31e30cdaf271e154ddd48 (mariadb-10.6.1-247-g809bda91548) parent(s): b5ec3e30b59a75e68192be8fb4550237bd146a2f author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2021-12-14 16:02:17 +0300 message: MDEV-26996: Support descending indexes in the range optimizer Make the Range Optimizer support descending index key parts. We follow the approach taken in MySQL-8. See HowRangeOptimizerHandlesDescKeyparts for the description. --- mysql-test/main/desc_index_range.result | 158 ++++++++++++++++++++++ mysql-test/main/desc_index_range.test | 74 +++++++++++ sql/item_geofunc.cc | 3 +- sql/key.cc | 10 +- sql/opt_range.cc | 162 +++++++++++++++------- sql/opt_range.h | 229 ++++++++++++++++++++++++++++---- sql/opt_range_mrr.cc | 46 +++---- 7 files changed, 580 insertions(+), 102 deletions(-) diff --git a/mysql-test/main/desc_index_range.result b/mysql-test/main/desc_index_range.result new file mode 100644 index 00000000000..53a608fe2d9 --- /dev/null +++ b/mysql-test/main/desc_index_range.result @@ -0,0 +1,158 @@ +create table t1 ( +a int, +key (a desc) +); +insert into t1 select seq from seq_1_to_1000; +set optimizer_trace=1; +explain select * from t1 force index(a) where a in (2, 4, 6); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range a a 5 NULL 3 Using where; Using index +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; +json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +[ + + [ + "(6) <= (a) <= (6)", + "(4) <= (a) <= (4)", + "(2) <= (a) <= (2)" + ] +] +set optimizer_trace=default; +# These should go in reverse order: +select * from t1 force index(a) where a in (2, 4, 6); +a +6 +4 +2 +drop table t1; +# +# Multi-part key tests +# +create table t1 ( +a int not null, +b int not null, +key ab(a, b desc) +); +insert into t1 select A.seq, B.seq*10 from seq_1_to_10 A, seq_1_to_10 B; +set optimizer_trace=1; +explain select * from t1 force index(ab) where a>=8 and b>=50; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range ab ab 4 NULL 51 Using where; Using index +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; +json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +[ + + [ + "(8) <= (a)" + ] +] +explain select * from t1 force index(ab) where a>=8 and b<=50; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range ab ab 8 NULL 46 Using where; Using index +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; +json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +[ + + [ + "(8,50) <= (a,b)" + ] +] +select * from t1 force index(ab) where a>=8 and b<=50; +a b +8 50 +8 40 +8 30 +8 20 +8 10 +9 50 +9 40 +9 30 +9 20 +9 10 +10 50 +10 40 +10 30 +10 20 +10 10 +select * from t1 ignore index(ab) where a>=8 and b<=50 order by a, b desc; +a b +8 50 +8 40 +8 30 +8 20 +8 10 +9 50 +9 40 +9 30 +9 20 +9 10 +10 50 +10 40 +10 30 +10 20 +10 10 +explain +select * from t1 where a between 2 and 4 and b between 50 and 80; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range ab ab 8 NULL 17 Using where; Using index +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; +json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +[ + + [ + "(2,80) <= (a,b) <= (4,50)" + ] +] +select * from t1 where a between 2 and 4 and b between 50 and 80; +a b +2 80 +2 70 +2 60 +2 50 +3 80 +3 70 +3 60 +3 50 +4 80 +4 70 +4 60 +4 50 +drop table t1; +create table t2 ( +a int not null, +b int not null, +key ab(a desc, b desc) +); +insert into t2 select A.seq, B.seq*10 from seq_1_to_10 A, seq_1_to_10 B; +explain +select * from t2 where a between 2 and 4; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t2 range ab ab 4 NULL 40 Using where; Using index +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; +json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +[ + + [ + "(4) <= (a) <= (2)" + ] +] +explain +select * from t2 where a between 2 and 4 and b between 50 and 80; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t2 range ab ab 8 NULL 31 Using where; Using index +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; +json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +[ + + [ + "(4,80) <= (a,b) <= (2,50)" + ] +] +set optimizer_trace=default; +drop table t2; diff --git a/mysql-test/main/desc_index_range.test b/mysql-test/main/desc_index_range.test new file mode 100644 index 00000000000..7fdf439c523 --- /dev/null +++ b/mysql-test/main/desc_index_range.test @@ -0,0 +1,74 @@ +# +# Tests for range access and descending indexes +# +--source include/have_sequence.inc +--source include/have_innodb.inc + +create table t1 ( + a int, + key (a desc) +); +insert into t1 select seq from seq_1_to_1000; + +set optimizer_trace=1; +explain select * from t1 force index(a) where a in (2, 4, 6); + +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; +set optimizer_trace=default; + +--echo # These should go in reverse order: +select * from t1 force index(a) where a in (2, 4, 6); +drop table t1; + +--echo # +--echo # Multi-part key tests +--echo # +create table t1 ( + a int not null, + b int not null, + key ab(a, b desc) +); + +insert into t1 select A.seq, B.seq*10 from seq_1_to_10 A, seq_1_to_10 B; + +set optimizer_trace=1; +explain select * from t1 force index(ab) where a>=8 and b>=50; +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; + +explain select * from t1 force index(ab) where a>=8 and b<=50; +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; + +select * from t1 force index(ab) where a>=8 and b<=50; +select * from t1 ignore index(ab) where a>=8 and b<=50 order by a, b desc; + +explain +select * from t1 where a between 2 and 4 and b between 50 and 80; +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; + +select * from t1 where a between 2 and 4 and b between 50 and 80; + +drop table t1; + +create table t2 ( + a int not null, + b int not null, + key ab(a desc, b desc) +); +insert into t2 select A.seq, B.seq*10 from seq_1_to_10 A, seq_1_to_10 B; + +explain +select * from t2 where a between 2 and 4; +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; + +explain +select * from t2 where a between 2 and 4 and b between 50 and 80; +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; + +set optimizer_trace=default; +drop table t2; diff --git a/sql/item_geofunc.cc b/sql/item_geofunc.cc index 49b85e2213b..a2a99bcdf8f 100644 --- a/sql/item_geofunc.cc +++ b/sql/item_geofunc.cc @@ -1083,7 +1083,8 @@ Item_func_spatial_rel::get_mm_leaf(RANGE_OPT_PARAM *param, DBUG_RETURN(0); // out of memory field->get_key_image(str, key_part->length, key_part->image_type); SEL_ARG *tree; - if (!(tree= new (param->mem_root) SEL_ARG(field, str, str))) + + if (!(tree= new (param->mem_root) SEL_ARG(field, true, str, str))) DBUG_RETURN(0); // out of memory switch (type) { diff --git a/sql/key.cc b/sql/key.cc index ef1af849391..467a4f75044 100644 --- a/sql/key.cc +++ b/sql/key.cc @@ -495,6 +495,7 @@ int key_cmp(KEY_PART_INFO *key_part, const uchar *key, uint key_length) { int cmp; store_length= key_part->store_length; + int sort_order = (key_part->key_part_flag & HA_REVERSE_SORT) ? -1 : 1; if (key_part->null_bit) { /* This key part allows null values; NULL is lower than everything */ @@ -503,19 +504,19 @@ int key_cmp(KEY_PART_INFO *key_part, const uchar *key, uint key_length) { /* the range is expecting a null value */ if (!field_is_null) - return 1; // Found key is > range + return sort_order; // Found key is > range /* null -- exact match, go to next key part */ continue; } else if (field_is_null) - return -1; // NULL is less than any value + return -sort_order; // NULL is less than any value key++; // Skip null byte store_length--; } if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0) - return -1; + return -sort_order; if (cmp > 0) - return 1; + return sort_order; } return 0; // Keys are equal } @@ -577,6 +578,7 @@ int key_rec_cmp(void *key_p, uchar *first_rec, uchar *second_rec) const int LESS= -GREATER; field= key_part->field; + int sort_order = (key_part->key_part_flag & HA_REVERSE_SORT) ? -1 : 1; if (key_part->null_bit) { diff --git a/sql/opt_range.cc b/sql/opt_range.cc index 86539046a32..541a921435a 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -1879,6 +1879,7 @@ SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc() max_flag=arg.max_flag; maybe_flag=arg.maybe_flag; maybe_null=arg.maybe_null; + is_ascending= arg.is_ascending; part=arg.part; field=arg.field; min_value=arg.min_value; @@ -1904,9 +1905,10 @@ inline void SEL_ARG::make_root() use_count=0; elements=1; } -SEL_ARG::SEL_ARG(Field *f,const uchar *min_value_arg, +SEL_ARG::SEL_ARG(Field *f, bool is_asc, const uchar *min_value_arg, const uchar *max_value_arg) :min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()), + is_ascending(is_asc), elements(1), use_count(1), field(f), min_value((uchar*) min_value_arg), max_value((uchar*) max_value_arg), next(0),prev(0), next_key_part(0), color(BLACK), type(KEY_RANGE), weight(1) @@ -1915,11 +1917,12 @@ SEL_ARG::SEL_ARG(Field *f,const uchar *min_value_arg, max_part_no= 1; } -SEL_ARG::SEL_ARG(Field *field_,uint8 part_, +SEL_ARG::SEL_ARG(Field *field_,uint8 part_, bool is_asc_, uchar *min_value_, uchar *max_value_, uint8 min_flag_,uint8 max_flag_,uint8 maybe_flag_) :min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_), - part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1), + part(part_),maybe_null(field_->real_maybe_null()), is_ascending(is_asc_), + elements(1),use_count(1), field(field_), min_value(min_value_), max_value(max_value_), next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE), weight(1) { @@ -1938,8 +1941,8 @@ SEL_ARG::SEL_ARG(Field *field_,uint8 part_, class SEL_ARG_LE: public SEL_ARG { public: - SEL_ARG_LE(const uchar *key, Field *field) - :SEL_ARG(field, key, key) + SEL_ARG_LE(const uchar *key, Field *field, bool is_asc) + :SEL_ARG(field, is_asc, key, key) { if (!field->real_maybe_null()) min_flag= NO_MIN_RANGE; // From start @@ -1959,16 +1962,17 @@ class SEL_ARG_LT: public SEL_ARG_LE Use this constructor if value->save_in_field() went precisely, without any data rounding or truncation. */ - SEL_ARG_LT(const uchar *key, Field *field) - :SEL_ARG_LE(key, field) + SEL_ARG_LT(const uchar *key, Field *field, bool is_asc) + :SEL_ARG_LE(key, field, is_asc) { max_flag= NEAR_MAX; } /* Use this constructor if value->save_in_field() returned success, but we don't know if rounding or truncation happened (as some Field::store() do not report minor data changes). */ - SEL_ARG_LT(THD *thd, const uchar *key, Field *field, Item *value) - :SEL_ARG_LE(key, field) + SEL_ARG_LT(THD *thd, const uchar *key, Field *field, bool is_asc, + Item *value) + :SEL_ARG_LE(key, field, is_asc) { if (stored_field_cmp_to_item(thd, field, value) == 0) max_flag= NEAR_MAX; @@ -1984,7 +1988,7 @@ class SEL_ARG_GT: public SEL_ARG without any data rounding or truncation. */ SEL_ARG_GT(const uchar *key, const KEY_PART *key_part, Field *field) - :SEL_ARG(field, key, key) + :SEL_ARG(field, !(key_part->flag & HA_REVERSE_SORT), key, key) { // Don't use open ranges for partial key_segments if (!(key_part->flag & HA_PART_KEY_SEG)) @@ -1998,7 +2002,7 @@ class SEL_ARG_GT: public SEL_ARG */ SEL_ARG_GT(THD *thd, const uchar *key, const KEY_PART *key_part, Field *field, Item *value) - :SEL_ARG(field, key, key) + :SEL_ARG(field, !(key_part->flag & HA_REVERSE_SORT), key, key) { // Don't use open ranges for partial key_segments if ((!(key_part->flag & HA_PART_KEY_SEG)) && @@ -2016,8 +2020,8 @@ class SEL_ARG_GE: public SEL_ARG Use this constructor if value->save_in_field() went precisely, without any data rounding or truncation. */ - SEL_ARG_GE(const uchar *key, Field *field) - :SEL_ARG(field, key, key) + SEL_ARG_GE(const uchar *key, Field *field, bool is_asc) + :SEL_ARG(field, is_asc, key, key) { max_flag= NO_MAX_RANGE; } @@ -2028,7 +2032,7 @@ class SEL_ARG_GE: public SEL_ARG */ SEL_ARG_GE(THD *thd, const uchar *key, const KEY_PART *key_part, Field *field, Item *value) - :SEL_ARG(field, key, key) + :SEL_ARG(field, !(key_part->flag & HA_REVERSE_SORT), key, key) { // Don't use open ranges for partial key_segments if ((!(key_part->flag & HA_PART_KEY_SEG)) && @@ -2059,7 +2063,8 @@ SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, } else { - if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value, + if (!(tmp= new (param->mem_root) SEL_ARG(field, part, is_ascending, + min_value, max_value, min_flag, max_flag, maybe_flag))) return 0; // OOM tmp->parent=new_parent; @@ -2830,6 +2835,7 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, } trace_keypart.end(); trace_idx_details.add("usable", !unusable_has_desc_keyparts); + unusable_has_desc_keyparts= false; if (unusable_has_desc_keyparts) // TODO MDEV-13756 { key_parts= param.key[param.keys]; @@ -4420,12 +4426,14 @@ int find_used_partitions(PART_PRUNE_PARAM *ppar, SEL_ARG *key_tree) key_tree->next_key_part->store_min_key(ppar->key, &tmp_min_key, &tmp_min_flag, - ppar->last_part_partno); + ppar->last_part_partno, + true); if (!tmp_max_flag) key_tree->next_key_part->store_max_key(ppar->key, &tmp_max_key, &tmp_max_flag, - ppar->last_part_partno); + ppar->last_part_partno, + false); flag= tmp_min_flag | tmp_max_flag; } else @@ -8671,7 +8679,8 @@ Item_func_null_predicate::get_mm_leaf(RANGE_OPT_PARAM *param, if (!field->real_maybe_null()) DBUG_RETURN(type == ISNULL_FUNC ? &null_element : NULL); SEL_ARG *tree; - if (!(tree= new (alloc) SEL_ARG(field, is_null_string, is_null_string))) + bool is_asc= !(key_part->flag & HA_REVERSE_SORT); + if (!(tree= new (alloc) SEL_ARG(field, is_asc, is_null_string, is_null_string))) DBUG_RETURN(0); if (type == Item_func::ISNOTNULL_FUNC) { @@ -8771,7 +8780,8 @@ Item_func_like::get_mm_leaf(RANGE_OPT_PARAM *param, int2store(min_str + maybe_null, min_length); int2store(max_str + maybe_null, max_length); } - SEL_ARG *tree= new (param->mem_root) SEL_ARG(field, min_str, max_str); + bool is_asc= !(key_part->flag & HA_REVERSE_SORT); + SEL_ARG *tree= new (param->mem_root) SEL_ARG(field, is_asc, min_str, max_str); DBUG_RETURN(tree); } @@ -9019,18 +9029,19 @@ SEL_ARG *Field::stored_field_make_mm_leaf(RANGE_OPT_PARAM *param, if (!(str= make_key_image(param->mem_root, key_part))) DBUG_RETURN(0); + bool is_asc= !(key_part->flag & HA_REVERSE_SORT); switch (op) { case SCALAR_CMP_LE: - DBUG_RETURN(new (mem_root) SEL_ARG_LE(str, this)); + DBUG_RETURN(new (mem_root) SEL_ARG_LE(str, this, is_asc)); case SCALAR_CMP_LT: - DBUG_RETURN(new (mem_root) SEL_ARG_LT(thd, str, this, value)); + DBUG_RETURN(new (mem_root) SEL_ARG_LT(thd, str, this, is_asc, value)); case SCALAR_CMP_GT: DBUG_RETURN(new (mem_root) SEL_ARG_GT(thd, str, key_part, this, value)); case SCALAR_CMP_GE: DBUG_RETURN(new (mem_root) SEL_ARG_GE(thd, str, key_part, this, value)); case SCALAR_CMP_EQ: case SCALAR_CMP_EQUAL: - DBUG_RETURN(new (mem_root) SEL_ARG(this, str, str)); + DBUG_RETURN(new (mem_root) SEL_ARG(this, is_asc, str, str)); break; } DBUG_ASSERT(0); @@ -9048,18 +9059,19 @@ SEL_ARG *Field::stored_field_make_mm_leaf_exact(RANGE_OPT_PARAM *param, if (!(str= make_key_image(param->mem_root, key_part))) DBUG_RETURN(0); + bool is_asc= !(key_part->flag & HA_REVERSE_SORT); switch (op) { case SCALAR_CMP_LE: - DBUG_RETURN(new (param->mem_root) SEL_ARG_LE(str, this)); + DBUG_RETURN(new (param->mem_root) SEL_ARG_LE(str, this, is_asc)); case SCALAR_CMP_LT: - DBUG_RETURN(new (param->mem_root) SEL_ARG_LT(str, this)); + DBUG_RETURN(new (param->mem_root) SEL_ARG_LT(str, this, is_asc)); case SCALAR_CMP_GT: DBUG_RETURN(new (param->mem_root) SEL_ARG_GT(str, key_part, this)); case SCALAR_CMP_GE: - DBUG_RETURN(new (param->mem_root) SEL_ARG_GE(str, this)); + DBUG_RETURN(new (param->mem_root) SEL_ARG_GE(str, this, is_asc)); case SCALAR_CMP_EQ: case SCALAR_CMP_EQUAL: - DBUG_RETURN(new (param->mem_root) SEL_ARG(this, str, str)); + DBUG_RETURN(new (param->mem_root) SEL_ARG(this, is_asc, str, str)); break; } DBUG_ASSERT(0); @@ -11777,6 +11789,46 @@ get_quick_select(PARAM *param,uint idx,SEL_ARG *key_tree, uint mrr_flags, } +void SEL_ARG::store_next_min_max_keys(KEY_PART *key, + uchar **cur_min_key, uint *cur_min_flag, + uchar **cur_max_key, uint *cur_max_flag, + int *min_part, int *max_part) +{ + DBUG_ASSERT(next_key_part); + bool asc = next_key_part->is_ascending; + + if (!get_min_flag()) + { + if (asc) + { + *min_part += next_key_part->store_min_key(key, cur_min_key, + cur_min_flag, MAX_KEY, true); + } + else + { + uint tmp_flag = invert_min_flag(*cur_min_flag); + *min_part += next_key_part->store_max_key(key, cur_min_key, &tmp_flag, + MAX_KEY, true); + *cur_min_flag = invert_max_flag(tmp_flag); + } + } + if (!get_max_flag()) + { + if (asc) + { + *max_part += next_key_part->store_max_key(key, cur_max_key, + cur_max_flag, MAX_KEY, false); + } + else + { + uint tmp_flag = invert_max_flag(*cur_max_flag); + *max_part += next_key_part->store_min_key(key, cur_max_key, &tmp_flag, + MAX_KEY, false); + *cur_max_flag = invert_min_flag(tmp_flag); + } + } +} + /* ** Fix this to get all possible sub_ranges */ @@ -11790,17 +11842,19 @@ get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key, int min_part= key_tree->part-1, // # of keypart values in min_key buffer max_part= key_tree->part-1; // # of keypart values in max_key buffer - if (key_tree->left != &null_element) + SEL_ARG *next_tree = key_tree->is_ascending ? key_tree->left : key_tree->right; + if (next_tree != &null_element) { - if (get_quick_keys(param,quick,key,key_tree->left, + if (get_quick_keys(param,quick,key,next_tree, min_key,min_key_flag, max_key, max_key_flag)) return 1; } uchar *tmp_min_key=min_key,*tmp_max_key=max_key; - min_part+= key_tree->store_min(key[key_tree->part].store_length, - &tmp_min_key,min_key_flag); - max_part+= key_tree->store_max(key[key_tree->part].store_length, - &tmp_max_key,max_key_flag); + + key_tree->store_min_max(key[key_tree->part].store_length, + &tmp_min_key, min_key_flag, + &tmp_max_key, max_key_flag, + &min_part, &max_part); if (key_tree->next_key_part && key_tree->next_key_part->type == SEL_ARG::KEY_RANGE && @@ -11810,31 +11864,40 @@ get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key, memcmp(min_key, max_key, (uint)(tmp_max_key - max_key))==0 && key_tree->min_flag==0 && key_tree->max_flag==0) { + // psergey-note: simplified the parameters below as follows: + // min_key_flag | key_tree->min_flag -> min_key_flag + // max_key_flag | key_tree->max_flag -> max_key_flag if (get_quick_keys(param,quick,key,key_tree->next_key_part, - tmp_min_key, min_key_flag | key_tree->min_flag, - tmp_max_key, max_key_flag | key_tree->max_flag)) + tmp_min_key, min_key_flag, + tmp_max_key, max_key_flag)) return 1; goto end; // Ugly, but efficient } { - uint tmp_min_flag=key_tree->min_flag,tmp_max_flag=key_tree->max_flag; - if (!tmp_min_flag) - min_part+= key_tree->next_key_part->store_min_key(key, - &tmp_min_key, - &tmp_min_flag, - MAX_KEY); - if (!tmp_max_flag) - max_part+= key_tree->next_key_part->store_max_key(key, - &tmp_max_key, - &tmp_max_flag, - MAX_KEY); + uint tmp_min_flag= key_tree->get_min_flag(); + uint tmp_max_flag= key_tree->get_max_flag(); + + key_tree->store_next_min_max_keys(key, + &tmp_min_key, &tmp_min_flag, + &tmp_max_key, &tmp_max_flag, + &min_part, &max_part); flag=tmp_min_flag | tmp_max_flag; } } else { - flag = (key_tree->min_flag & GEOM_FLAG) ? - key_tree->min_flag : key_tree->min_flag | key_tree->max_flag; + if (key_tree->is_ascending) + { + flag= (key_tree->min_flag & GEOM_FLAG) ? key_tree->min_flag: + (key_tree->min_flag | + key_tree->max_flag); + } + else + { + // Invert flags for DESC keypart + flag= invert_min_flag(key_tree->min_flag) | + invert_max_flag(key_tree->max_flag); + } } /* @@ -11895,8 +11958,9 @@ get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key, return 1; end: - if (key_tree->right != &null_element) - return get_quick_keys(param,quick,key,key_tree->right, + next_tree = key_tree->is_ascending ? key_tree->right : key_tree->left; + if (next_tree != &null_element) + return get_quick_keys(param,quick,key,next_tree, min_key,min_key_flag, max_key,max_key_flag); return 0; diff --git a/sql/opt_range.h b/sql/opt_range.h index 1014176ecc5..6864a5c583a 100644 --- a/sql/opt_range.h +++ b/sql/opt_range.h @@ -54,6 +54,33 @@ struct KEY_PART { }; +/** + A helper function to invert min flags to max flags for DESC key parts. + It changes NEAR_MIN, NO_MIN_RANGE to NEAR_MAX, NO_MAX_RANGE appropriately +*/ + +inline uint invert_min_flag(uint min_flag) +{ + uint max_flag_out = min_flag & ~(NEAR_MIN | NO_MIN_RANGE); + if (min_flag & NEAR_MIN) max_flag_out |= NEAR_MAX; + if (min_flag & NO_MIN_RANGE) max_flag_out |= NO_MAX_RANGE; + return max_flag_out; +} + + +/** + A helper function to invert max flags to min flags for DESC key parts. + It changes NEAR_MAX, NO_MAX_RANGE to NEAR_MIN, NO_MIN_RANGE appropriately +*/ + +inline uint invert_max_flag(uint max_flag) +{ + uint min_flag_out = max_flag & ~(NEAR_MAX | NO_MAX_RANGE); + if (max_flag & NEAR_MAX) min_flag_out |= NEAR_MIN; + if (max_flag & NO_MAX_RANGE) min_flag_out |= NO_MIN_RANGE; + return min_flag_out; +} + class RANGE_OPT_PARAM; /* A construction block of the SEL_ARG-graph. @@ -267,6 +294,8 @@ class RANGE_OPT_PARAM; - it is a lot easier to compute than computing the number of ranges, - it can be updated incrementally when performing AND/OR operations on parts of the graph. + + 6. For handling DESC keyparts, See HowRangeOptimizerHandlesDescKeyparts */ class SEL_ARG :public Sql_alloc @@ -277,6 +306,11 @@ class SEL_ARG :public Sql_alloc uint8 min_flag,max_flag,maybe_flag; uint8 part; // Which key part uint8 maybe_null; + /* + Whether the keypart is ascending or descending. + See HowRangeOptimizerHandlesDescKeyparts for details. + */ + uint8 is_ascending; /* The ordinal number the least significant component encountered in the ranges of the SEL_ARG tree (the first component has number 1) @@ -327,11 +361,15 @@ class SEL_ARG :public Sql_alloc SEL_ARG() {} SEL_ARG(SEL_ARG &); - SEL_ARG(Field *,const uchar *, const uchar *); - SEL_ARG(Field *field, uint8 part, uchar *min_value, uchar *max_value, + SEL_ARG(Field *, bool is_asc, const uchar *, const uchar *); + SEL_ARG(Field *field, uint8 part, bool is_asc, + uchar *min_value, uchar *max_value, uint8 min_flag, uint8 max_flag, uint8 maybe_flag); + + /* This is used to construct degenerate SEL_ARGS like ALWAYS, IMPOSSIBLE, etc */ SEL_ARG(enum Type type_arg) - :min_flag(0), max_part_no(0) /* first key part means 1. 0 mean 'no parts'*/, + :min_flag(0), is_ascending(false), + max_part_no(0) /* first key part means 1. 0 mean 'no parts'*/, elements(1),use_count(1),left(0),right(0), next_key_part(0), color(BLACK), type(type_arg), weight(1) {} @@ -409,19 +447,20 @@ class SEL_ARG :public Sql_alloc { new_max=arg->max_value; flag_max=arg->max_flag; } - return new (thd->mem_root) SEL_ARG(field, part, new_min, new_max, flag_min, + return new (thd->mem_root) SEL_ARG(field, part, is_ascending, + new_min, new_max, flag_min, flag_max, MY_TEST(maybe_flag && arg->maybe_flag)); } SEL_ARG *clone_first(SEL_ARG *arg) { // min <= X < arg->min - return new SEL_ARG(field,part, min_value, arg->min_value, + return new SEL_ARG(field, part, is_ascending, min_value, arg->min_value, min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX, maybe_flag | arg->maybe_flag); } SEL_ARG *clone_last(SEL_ARG *arg) { // min <= X <= key_max - return new SEL_ARG(field, part, min_value, arg->max_value, + return new SEL_ARG(field, part, is_ascending, min_value, arg->max_value, min_flag, arg->max_flag, maybe_flag | arg->maybe_flag); } SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next); @@ -504,6 +543,56 @@ class SEL_ARG :public Sql_alloc return 0; } + /* Save minimum and maximum, taking index order into account */ + void store_min_max(uint length, + uchar **min_key, uint min_flag, + uchar **max_key, uint max_flag, + int *min_part, int *max_part) + { + if (is_ascending) { + *min_part += store_min(length, min_key, min_flag); + *max_part += store_max(length, max_key, max_flag); + } else { + *max_part += store_min(length, max_key, min_flag); + *min_part += store_max(length, min_key, max_flag); + } + } + /* + Get the flag for range's starting endpoint, taking index order into + account. + */ + uint get_min_flag() + { + return (is_ascending ? min_flag : invert_max_flag(max_flag)); + } + /* + Get the flag for range's starting endpoint, taking index order into + account. + */ + uint get_max_flag() + { + return (is_ascending ? max_flag : invert_min_flag(min_flag)); + } + /* Get the previous interval, taking index order into account */ + inline SEL_ARG* index_order_prev() + { + return is_ascending? prev: next; + } + /* Get the next interval, taking index order into account */ + inline SEL_ARG* index_order_next() + { + return is_ascending? next: prev; + } + + /* + Produce a single multi-part interval, taking key part ordering into + account. + */ + void store_next_min_max_keys(KEY_PART *key, uchar **cur_min_key, + uint *cur_min_flag, uchar **cur_max_key, + uint *cur_max_flag, int *min_part, + int *max_part); + /* Returns a number of keypart values appended to the key buffer for min key and max key. This function is used by both Range @@ -516,7 +605,8 @@ class SEL_ARG :public Sql_alloc int store_min_key(KEY_PART *key, uchar **range_key, uint *range_key_flag, - uint last_part) + uint last_part, + bool start_key) { SEL_ARG *key_tree= first(); uint res= key_tree->store_min(key[key_tree->part].store_length, @@ -525,15 +615,26 @@ class SEL_ARG :public Sql_alloc if (!res) return 0; *range_key_flag|= key_tree->min_flag; - if (key_tree->next_key_part && - key_tree->next_key_part->type == SEL_ARG::KEY_RANGE && + SEL_ARG *nkp= key_tree->next_key_part; + if (nkp && nkp->type == SEL_ARG::KEY_RANGE && key_tree->part != last_part && - key_tree->next_key_part->part == key_tree->part+1 && + nkp->part == key_tree->part+1 && !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN))) - res+= key_tree->next_key_part->store_min_key(key, - range_key, - range_key_flag, - last_part); + { + const bool asc = nkp->is_ascending; + if (start_key == asc) + { + res+= nkp->store_min_key(key, range_key, range_key_flag, last_part, + start_key); + } + else + { + uint tmp_flag = invert_min_flag(*range_key_flag); + res += nkp->store_max_key(key, range_key, &tmp_flag, last_part, + start_key); + *range_key_flag = invert_max_flag(tmp_flag); + } + } return res; } @@ -541,7 +642,8 @@ class SEL_ARG :public Sql_alloc int store_max_key(KEY_PART *key, uchar **range_key, uint *range_key_flag, - uint last_part) + uint last_part, + bool start_key) { SEL_ARG *key_tree= last(); uint res=key_tree->store_max(key[key_tree->part].store_length, @@ -549,15 +651,26 @@ class SEL_ARG :public Sql_alloc if (!res) return 0; *range_key_flag|= key_tree->max_flag; - if (key_tree->next_key_part && - key_tree->next_key_part->type == SEL_ARG::KEY_RANGE && + SEL_ARG *nkp= key_tree->next_key_part; + if (nkp && nkp->type == SEL_ARG::KEY_RANGE && key_tree->part != last_part && - key_tree->next_key_part->part == key_tree->part+1 && + nkp->part == key_tree->part+1 && !(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX))) - res+= key_tree->next_key_part->store_max_key(key, - range_key, - range_key_flag, - last_part); + { + const bool asc = nkp->is_ascending; + if ((!start_key && asc) || (start_key && !asc)) + { + res += nkp->store_max_key(key, range_key, range_key_flag, last_part, + start_key); + } + else + { + uint tmp_flag = invert_max_flag(*range_key_flag); + res += nkp->store_min_key(key, range_key, &tmp_flag, last_part, + start_key); + *range_key_flag = invert_min_flag(tmp_flag); + } + } return res; } @@ -661,13 +774,83 @@ class SEL_ARG :public Sql_alloc SEL_ARG *clone_tree(RANGE_OPT_PARAM *param); }; +/* + HowRangeOptimizerHandlesDescKeyparts + ==================================== + + Starting with MySQL-8.0 and MariaDB 10.8, index key parts may be descending, + for example: + + INDEX idx1(col1, col2 DESC, col3, col4 DESC) + + Range Optimizer handles this as follows: + + The SEL_ARG object has SEL_ARG::is_ascending which specifies whether the + keypart is ascending. + + Other than that, the SEL_ARG graph is built without any regard to DESC + keyparts. + + For example, for an index + + INDEX idx2(kp1 DESC, kp2) + + and range + + kp1 BETWEEN 10 and 20 (RANGE-1) + + the SEL_ARG will have min_value=10, max_value=20, is_ascending=false. + + The ordering of key parts is taken into account when SEL_ARG graph is + linearized to ranges, in sel_arg_range_seq_next() and get_quick_keys(). + + The storage engine expects the first bound to be the first in the index and + the last bound to be the last, that is, for (RANGE-1) we will flip min and + max and generate these key_range structures: + + start.key='20' , end.key='10' + + See SEL_ARG::store_min_max(). The flag values are flipped as well, see + SEL_ARG::get_min_flag(), get_max_flag(). + + == Handling multiple key parts == + + For multi-part keys, the order of key parts has an effect on which ranges are + generated. Consider + + kp1 >= 10 AND kp2 >'foo' + + for INDEX(kp1 ASC, kp2 ASC) the range will be + + (kp1, kp2) > (10, 'foo') + + while for INDEX(kp1 ASC, kp2 DESC) it will be just + + kp1 >= 10 + + Another example: + + (kp1 BETWEEN 10 AND 20) AND (kp2 BETWEEN 'foo' AND 'quux') + + with INDEX (kp1 ASC, kp2 ASC) will generate + + (10, 'foo') <= (kp1, kp2) < (20, 'quux') + + while with index INDEX (kp1 ASC, kp2 DESC) it will generate + + (10, 'quux') <= (kp1, kp2) < (20, 'foo') + + This is again achieved by sel_arg_range_seq_next() and get_quick_keys() + flipping SEL_ARG's min,max, their flags and next/prev as needed. +*/ + extern MYSQL_PLUGIN_IMPORT SEL_ARG null_element; class SEL_ARG_IMPOSSIBLE: public SEL_ARG { public: SEL_ARG_IMPOSSIBLE(Field *field) - :SEL_ARG(field, 0, 0) + :SEL_ARG(field, false, 0, 0) { type= SEL_ARG::IMPOSSIBLE; } diff --git a/sql/opt_range_mrr.cc b/sql/opt_range_mrr.cc index 20413f5df63..8877e15d5b5 100644 --- a/sql/opt_range_mrr.cc +++ b/sql/opt_range_mrr.cc @@ -34,7 +34,7 @@ typedef struct st_range_seq_entry uint min_key_flag, max_key_flag; /* Number of key parts */ - uint min_key_parts, max_key_parts; + int min_key_parts, max_key_parts; SEL_ARG *key_tree; } RANGE_SEQ_ENTRY; @@ -105,13 +105,14 @@ static void step_down_to(SEL_ARG_RANGE_SEQ *arg, SEL_ARG *key_tree) cur->max_key_parts= prev->max_key_parts; uint16 stor_length= arg->param->key[arg->keyno][key_tree->part].store_length; - cur->min_key_parts += key_tree->store_min(stor_length, &cur->min_key, - prev->min_key_flag); - cur->max_key_parts += key_tree->store_max(stor_length, &cur->max_key, - prev->max_key_flag); - cur->min_key_flag= prev->min_key_flag | key_tree->min_flag; - cur->max_key_flag= prev->max_key_flag | key_tree->max_flag; + key_tree->store_min_max(stor_length, + &cur->min_key, prev->min_key_flag, + &cur->max_key, prev->max_key_flag, + &cur->min_key_parts, &cur->max_key_parts); + + cur->min_key_flag= prev->min_key_flag | key_tree->get_min_flag(); + cur->max_key_flag= prev->max_key_flag | key_tree->get_max_flag(); if (key_tree->is_null_interval()) cur->min_key_flag |= NULL_RANGE; @@ -165,12 +166,12 @@ bool sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) /* Ok, we're at some "full tuple" position in the tree */ /* Step down if we can */ - if (key_tree->next && key_tree->next != &null_element) + if (key_tree->index_order_next() && key_tree->index_order_next() != &null_element) { //step down; (update the tuple, we'll step right and stay there) seq->i--; - step_down_to(seq, key_tree->next); - key_tree= key_tree->next; + step_down_to(seq, key_tree->index_order_next()); + key_tree= key_tree->index_order_next(); seq->is_ror_scan= FALSE; goto walk_right_n_up; } @@ -185,12 +186,12 @@ bool sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) key_tree= seq->stack[seq->i].key_tree; /* Step down if we can */ - if (key_tree->next && key_tree->next != &null_element) + if (key_tree->index_order_next() && key_tree->index_order_next() != &null_element) { // Step down; update the tuple seq->i--; - step_down_to(seq, key_tree->next); - key_tree= key_tree->next; + step_down_to(seq, key_tree->index_order_next()); + key_tree= key_tree->index_order_next(); break; } } @@ -214,16 +215,10 @@ bool sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) !key_tree->min_flag && !key_tree->max_flag)) { seq->is_ror_scan= FALSE; - if (!key_tree->min_flag) - cur->min_key_parts += - key_tree->next_key_part->store_min_key(seq->param->key[seq->keyno], - &cur->min_key, - &cur->min_key_flag, MAX_KEY); - if (!key_tree->max_flag) - cur->max_key_parts += - key_tree->next_key_part->store_max_key(seq->param->key[seq->keyno], - &cur->max_key, - &cur->max_key_flag, MAX_KEY); + key_tree->store_next_min_max_keys(seq->param->key[seq->keyno], + &cur->min_key, &cur->min_key_flag, + &cur->max_key, &cur->max_key_flag, + &cur->min_key_parts, &cur->max_key_parts); break; } } @@ -235,10 +230,11 @@ bool sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) key_tree= key_tree->next_key_part; walk_up_n_right: - while (key_tree->prev && key_tree->prev != &null_element) + while (key_tree->index_order_prev() && + key_tree->index_order_prev() != &null_element) { /* Step up */ - key_tree= key_tree->prev; + key_tree= key_tree->index_order_prev(); } step_down_to(seq, key_tree); }

1 0

[Commits] 0873cdf6bc5: Descending indexes code exposed a gap in fix for MDEV-25858.
by Sergei Petrunia 14 Dec '21

14 Dec '21

revision-id: 0873cdf6bc5139f606dc9ff834f81bea9bab66aa (mariadb-10.6.1-233-g0873cdf6bc5) parent(s): 53f0a8cdb8000b97ec079172f1911685714ab216 author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2021-12-14 15:35:10 +0300 message: Descending indexes code exposed a gap in fix for MDEV-25858. Extend the fix for MDEV-25858 to handle non-reverse-ordered ORDER BY: If test_if_skip_sort_order() decides to use an index to produce rows in the required ordering, it should disable "Range Checked for Each Record". The fix needs to be backported to earlier versions. --- mysql-test/main/order_by_innodb.result | 34 ++++++++++++++++++-- mysql-test/main/order_by_innodb.test | 37 ++++++++++++++++++++-- .../suite/engines/funcs/r/ix_using_order.result | 4 +-- sql/sql_select.cc | 8 +++++ 4 files changed, 77 insertions(+), 6 deletions(-) diff --git a/mysql-test/main/order_by_innodb.result b/mysql-test/main/order_by_innodb.result index 94bc5a3a858..74dd964cdce 100644 --- a/mysql-test/main/order_by_innodb.result +++ b/mysql-test/main/order_by_innodb.result @@ -180,7 +180,7 @@ id id 1 NULL 2 1 3 3 -create index for_latest_sort on t2 (d1 desc, d2 desc, id desc); +create index for_latest_sort on t2 (d1, d2, id); select t1.id,t2.id from @@ -198,7 +198,37 @@ id id 1 NULL 2 1 3 3 -drop table t1,t2; +# Now, same as above but use a DESC index +CREATE TABLE t3 ( +id int NOT NULL PRIMARY KEY, +id2 int NOT NULL, +d1 datetime, +d2 timestamp NOT NULL, +KEY id2 (id2) +) engine=innodb; +insert into t3 values +(1,2,'2019-03-05 00:00:00','2019-03-06 00:00:00'), +(2,3,'2019-03-05 00:00:00','2019-03-06 00:00:00'), +(3,3,'2019-03-06 00:00:00','2019-03-05 00:00:00'); +create index for_latest_sort on t3 (d1 desc, d2 desc, id desc); +select +t1.id,t3.id +from +t1 left join +t3 on t3.id2 = t1.id and +t3.id = (select dd.id +from t3 dd +where +dd.id2 = t1.id and +d1 > '2019-02-06 00:00:00' + order by +dd.d1 desc, dd.d2 desc, dd.id desc limit 1 +); +id id +1 NULL +2 1 +3 3 +drop table t1,t2,t3; # End of 10.2 tests # # MDEV-26938 Support descending indexes internally in InnoDB diff --git a/mysql-test/main/order_by_innodb.test b/mysql-test/main/order_by_innodb.test index 1eee4e3b626..ac737d9f20f 100644 --- a/mysql-test/main/order_by_innodb.test +++ b/mysql-test/main/order_by_innodb.test @@ -170,7 +170,7 @@ from dd.d1 desc, dd.d2 desc, dd.id desc limit 1 ); -create index for_latest_sort on t2 (d1 desc, d2 desc, id desc); +create index for_latest_sort on t2 (d1, d2, id); select t1.id,t2.id @@ -185,7 +185,40 @@ from order by dd.d1 desc, dd.d2 desc, dd.id desc limit 1 ); -drop table t1,t2; + +--echo # Now, same as above but use a DESC index + +CREATE TABLE t3 ( + id int NOT NULL PRIMARY KEY, + id2 int NOT NULL, + d1 datetime, + d2 timestamp NOT NULL, + KEY id2 (id2) +) engine=innodb; + +insert into t3 values + (1,2,'2019-03-05 00:00:00','2019-03-06 00:00:00'), + (2,3,'2019-03-05 00:00:00','2019-03-06 00:00:00'), + (3,3,'2019-03-06 00:00:00','2019-03-05 00:00:00'); +create index for_latest_sort on t3 (d1 desc, d2 desc, id desc); + + +select + t1.id,t3.id +from + t1 left join + t3 on t3.id2 = t1.id and + t3.id = (select dd.id + from t3 dd + where + dd.id2 = t1.id and + d1 > '2019-02-06 00:00:00' + order by + dd.d1 desc, dd.d2 desc, dd.id desc limit 1 + ); + + +drop table t1,t2,t3; --echo # End of 10.2 tests diff --git a/mysql-test/suite/engines/funcs/r/ix_using_order.result b/mysql-test/suite/engines/funcs/r/ix_using_order.result index 645b3fcfbc4..1e4389ce251 100644 --- a/mysql-test/suite/engines/funcs/r/ix_using_order.result +++ b/mysql-test/suite/engines/funcs/r/ix_using_order.result @@ -17,7 +17,7 @@ SHOW CREATE TABLE t1; Table Create Table t1 CREATE TABLE `t1` ( `c1` int(11) NOT NULL, - KEY `i1` (`c1`) USING BTREE + KEY `i1` (`c1` DESC) USING BTREE ) ENGINE=ENGINE DEFAULT CHARSET=latin1 DROP TABLE t1; SHOW TABLES; @@ -40,7 +40,7 @@ SHOW CREATE TABLE t1; Table Create Table t1 CREATE TABLE `t1` ( `c1` int(11) NOT NULL, - UNIQUE KEY `i1` (`c1`) USING BTREE + UNIQUE KEY `i1` (`c1` DESC) USING BTREE ) ENGINE=ENGINE DEFAULT CHARSET=latin1 DROP INDEX i1 ON t1; DROP TABLE t1; diff --git a/sql/sql_select.cc b/sql/sql_select.cc index 0dfe95e81b0..33a5dd95a90 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -24260,7 +24260,15 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit, } } else if (select && select->quick) + { + /* Cancel "Range checked for each record" */ + if (tab->use_quick == 2) + { + tab->use_quick= 1; + tab->read_first_record= join_init_read_record; + } select->quick->need_sorted_output(); + } if (tab->type == JT_EQ_REF) tab->read_record.unlock_row= join_read_key_unlock_row;

1 0

[Commits] ab66c4b10c6: Update test results
by psergey 14 Dec '21

14 Dec '21

revision-id: ab66c4b10c66c1c86c743d8abf8678b54ef86638 (mariadb-10.6.1-331-gab66c4b10c6) parent(s): 8708095a0256add4d06abf2d04a91f4f5b7800fb author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2021-12-14 14:45:47 +0300 message: Update test results --- mysql-test/main/derived_cond_pushdown.result | 8 ++++---- mysql-test/main/opt_trace.result | 28 ++++++++++++++-------------- 2 files changed, 18 insertions(+), 18 deletions(-) diff --git a/mysql-test/main/derived_cond_pushdown.result b/mysql-test/main/derived_cond_pushdown.result index fdd83143b05..88c82e25b7f 100644 --- a/mysql-test/main/derived_cond_pushdown.result +++ b/mysql-test/main/derived_cond_pushdown.result @@ -18387,7 +18387,7 @@ explain extended select t2.a,t2.b,t2.c,t.c as t_c,t.max,t.min from t2, t3, (select c, max(b) max, min(b) min from t4 group by c) t where t2.b < 40 and t2.a=t3.a and t3.c=t.c; id select_type table type possible_keys key key_len ref rows filtered Extra -1 PRIMARY t2 ALL NULL NULL NULL NULL 90 53.33 Using where +1 PRIMARY t2 ALL NULL NULL NULL NULL 90 60.00 Using where 1 PRIMARY t3 ref idx_a idx_a 5 test.t2.a 1 100.00 Using where 1 PRIMARY <derived2> ref key0 key0 128 test.t3.c 10 100.00 2 DERIVED t4 ALL idx_c NULL NULL NULL 160 100.00 Using temporary; Using filesort @@ -18406,7 +18406,7 @@ EXPLAIN "table_name": "t2", "access_type": "ALL", "rows": 90, - "filtered": 53.33333206, + "filtered": 60, "attached_condition": "t2.b < 40 and t2.a is not null" } }, @@ -18910,7 +18910,7 @@ explain extended select * from t2, t3, (select c, b, sum(b) over (partition by c) from t4 ) t where t2.b < 40 and t2.a=t3.a and t3.c=t.c; id select_type table type possible_keys key key_len ref rows filtered Extra -1 PRIMARY t2 ALL NULL NULL NULL NULL 90 53.33 Using where +1 PRIMARY t2 ALL NULL NULL NULL NULL 90 60.00 Using where 1 PRIMARY t3 ref idx_a idx_a 5 test.t2.a 1 100.00 Using where 1 PRIMARY <derived2> ref key0 key0 128 test.t3.c 10 100.00 2 DERIVED t4 ALL idx_c NULL NULL NULL 160 100.00 Using temporary @@ -18929,7 +18929,7 @@ EXPLAIN "table_name": "t2", "access_type": "ALL", "rows": 90, - "filtered": 53.33333206, + "filtered": 60, "attached_condition": "t2.b < 40 and t2.a is not null" } }, diff --git a/mysql-test/main/opt_trace.result b/mysql-test/main/opt_trace.result index 27158dcdde7..65c144c44df 100644 --- a/mysql-test/main/opt_trace.result +++ b/mysql-test/main/opt_trace.result @@ -8079,20 +8079,20 @@ JSON_DETAILED(JSON_EXTRACT(trace, '$**.considered_execution_plans')) { "access_type": "scan", - "resulting_rows": 4, - "cost": 3.217089844, + "resulting_rows": 5, + "cost": 3.017089844, "chosen": true } ], "chosen_access_method": { "type": "scan", - "records": 4, - "cost": 3.217089844, + "records": 5, + "cost": 3.017089844, "uses_join_buffering": false } }, - "rows_for_plan": 4, + "rows_for_plan": 5, "cost_for_plan": 4.017089844, "rest_of_plan": [ @@ -8111,7 +8111,7 @@ JSON_DETAILED(JSON_EXTRACT(trace, '$**.considered_execution_plans')) { "access_type": "scan", "resulting_rows": 800, - "cost": 176.7890625, + "cost": 220.9863281, "chosen": true } ], @@ -8119,13 +8119,13 @@ JSON_DETAILED(JSON_EXTRACT(trace, '$**.considered_execution_plans')) { "type": "scan", "records": 800, - "cost": 176.7890625, + "cost": 220.9863281, "uses_join_buffering": false } }, - "rows_for_plan": 3200, - "cost_for_plan": 820.8061523, - "estimated_join_cardinality": 3200 + "rows_for_plan": 4000, + "cost_for_plan": 1025.003418, + "estimated_join_cardinality": 4000 } ] }, @@ -8590,7 +8590,7 @@ JSON_DETAILED(JSON_EXTRACT(trace, '$**.selectivity_for_columns')) ] EXPLAIN EXTENDED SELECT * from t1 WHERE a != 5; id select_type table type possible_keys key key_len ref rows filtered Extra -1 SIMPLE t1 ALL NULL NULL NULL NULL 100 98.00 Using where +1 SIMPLE t1 ALL NULL NULL NULL NULL 100 99.00 Using where Warnings: Note 1003 select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from `test`.`t1` where `test`.`t1`.`a` <> 5 select JSON_DETAILED(JSON_EXTRACT(trace, '$**.selectivity_for_columns')) from INFORMATION_SCHEMA.OPTIMIZER_TRACE; @@ -8606,13 +8606,13 @@ JSON_DETAILED(JSON_EXTRACT(trace, '$**.selectivity_for_columns')) "NULL < a < 5", "5 < a" ], - "selectivity_from_histogram": 0.98 + "selectivity_from_histogram": 0.99 } ] ] EXPLAIN EXTENDED SELECT * from t1 WHERE b >= 10 and b < 25; id select_type table type possible_keys key key_len ref rows filtered Extra -1 SIMPLE t1 ALL NULL NULL NULL NULL 100 14.00 Using where +1 SIMPLE t1 ALL NULL NULL NULL NULL 100 15.00 Using where Warnings: Note 1003 select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from `test`.`t1` where `test`.`t1`.`b` >= 10 and `test`.`t1`.`b` < 25 select JSON_DETAILED(JSON_EXTRACT(trace, '$**.selectivity_for_columns')) from INFORMATION_SCHEMA.OPTIMIZER_TRACE; @@ -8627,7 +8627,7 @@ JSON_DETAILED(JSON_EXTRACT(trace, '$**.selectivity_for_columns')) [ "10 <= b < 25" ], - "selectivity_from_histogram": 0.14 + "selectivity_from_histogram": 0.15 } ] ]

1 0

[Commits] 53f0a8cdb80: Don't run main.desc_index_range under embedded. It uses optimizer trace
by Sergei Petrunia 14 Dec '21

14 Dec '21

revision-id: 53f0a8cdb8000b97ec079172f1911685714ab216 (mariadb-10.6.1-232-g53f0a8cdb80) parent(s): a0643458ca5bcd69e91cffcb9e637f544aca7cf1 author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2021-12-14 14:35:19 +0300 message: Don't run main.desc_index_range under embedded. It uses optimizer trace --- mysql-test/main/desc_index_range.test | 3 +++ 1 file changed, 3 insertions(+) diff --git a/mysql-test/main/desc_index_range.test b/mysql-test/main/desc_index_range.test index 7fdf439c523..94d6b76258d 100644 --- a/mysql-test/main/desc_index_range.test +++ b/mysql-test/main/desc_index_range.test @@ -4,6 +4,9 @@ --source include/have_sequence.inc --source include/have_innodb.inc +# The test uses optimizer trace: +--source include/not_embedded.inc + create table t1 ( a int, key (a desc)

1 0

[Commits] a0643458ca5: MDEV-26996: Support descending indexes in the range optimizer
by Sergei Petrunia 13 Dec '21

13 Dec '21

revision-id: a0643458ca5bcd69e91cffcb9e637f544aca7cf1 (mariadb-10.6.1-231-ga0643458ca5) parent(s): d3b5ea4c6b0d3abbe18bf63d9fe076dcb0a043ce author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2021-12-14 01:47:01 +0300 message: MDEV-26996: Support descending indexes in the range optimizer Make the Range Optimizer support descending index key parts. We follow the approach taken in MySQL-8. See HowRangeOptimizerHandlesDescKeyparts for the description. --- mysql-test/main/desc_index_range.result | 158 ++++++++++++++++++++++ mysql-test/main/desc_index_range.test | 74 +++++++++++ sql/item_geofunc.cc | 3 +- sql/key.cc | 16 ++- sql/opt_range.cc | 162 +++++++++++++++------- sql/opt_range.h | 229 ++++++++++++++++++++++++++++---- sql/opt_range_mrr.cc | 46 +++---- 7 files changed, 583 insertions(+), 105 deletions(-) diff --git a/mysql-test/main/desc_index_range.result b/mysql-test/main/desc_index_range.result new file mode 100644 index 00000000000..53a608fe2d9 --- /dev/null +++ b/mysql-test/main/desc_index_range.result @@ -0,0 +1,158 @@ +create table t1 ( +a int, +key (a desc) +); +insert into t1 select seq from seq_1_to_1000; +set optimizer_trace=1; +explain select * from t1 force index(a) where a in (2, 4, 6); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range a a 5 NULL 3 Using where; Using index +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; +json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +[ + + [ + "(6) <= (a) <= (6)", + "(4) <= (a) <= (4)", + "(2) <= (a) <= (2)" + ] +] +set optimizer_trace=default; +# These should go in reverse order: +select * from t1 force index(a) where a in (2, 4, 6); +a +6 +4 +2 +drop table t1; +# +# Multi-part key tests +# +create table t1 ( +a int not null, +b int not null, +key ab(a, b desc) +); +insert into t1 select A.seq, B.seq*10 from seq_1_to_10 A, seq_1_to_10 B; +set optimizer_trace=1; +explain select * from t1 force index(ab) where a>=8 and b>=50; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range ab ab 4 NULL 51 Using where; Using index +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; +json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +[ + + [ + "(8) <= (a)" + ] +] +explain select * from t1 force index(ab) where a>=8 and b<=50; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range ab ab 8 NULL 46 Using where; Using index +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; +json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +[ + + [ + "(8,50) <= (a,b)" + ] +] +select * from t1 force index(ab) where a>=8 and b<=50; +a b +8 50 +8 40 +8 30 +8 20 +8 10 +9 50 +9 40 +9 30 +9 20 +9 10 +10 50 +10 40 +10 30 +10 20 +10 10 +select * from t1 ignore index(ab) where a>=8 and b<=50 order by a, b desc; +a b +8 50 +8 40 +8 30 +8 20 +8 10 +9 50 +9 40 +9 30 +9 20 +9 10 +10 50 +10 40 +10 30 +10 20 +10 10 +explain +select * from t1 where a between 2 and 4 and b between 50 and 80; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range ab ab 8 NULL 17 Using where; Using index +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; +json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +[ + + [ + "(2,80) <= (a,b) <= (4,50)" + ] +] +select * from t1 where a between 2 and 4 and b between 50 and 80; +a b +2 80 +2 70 +2 60 +2 50 +3 80 +3 70 +3 60 +3 50 +4 80 +4 70 +4 60 +4 50 +drop table t1; +create table t2 ( +a int not null, +b int not null, +key ab(a desc, b desc) +); +insert into t2 select A.seq, B.seq*10 from seq_1_to_10 A, seq_1_to_10 B; +explain +select * from t2 where a between 2 and 4; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t2 range ab ab 4 NULL 40 Using where; Using index +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; +json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +[ + + [ + "(4) <= (a) <= (2)" + ] +] +explain +select * from t2 where a between 2 and 4 and b between 50 and 80; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t2 range ab ab 8 NULL 31 Using where; Using index +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; +json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +[ + + [ + "(4,80) <= (a,b) <= (2,50)" + ] +] +set optimizer_trace=default; +drop table t2; diff --git a/mysql-test/main/desc_index_range.test b/mysql-test/main/desc_index_range.test new file mode 100644 index 00000000000..7fdf439c523 --- /dev/null +++ b/mysql-test/main/desc_index_range.test @@ -0,0 +1,74 @@ +# +# Tests for range access and descending indexes +# +--source include/have_sequence.inc +--source include/have_innodb.inc + +create table t1 ( + a int, + key (a desc) +); +insert into t1 select seq from seq_1_to_1000; + +set optimizer_trace=1; +explain select * from t1 force index(a) where a in (2, 4, 6); + +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; +set optimizer_trace=default; + +--echo # These should go in reverse order: +select * from t1 force index(a) where a in (2, 4, 6); +drop table t1; + +--echo # +--echo # Multi-part key tests +--echo # +create table t1 ( + a int not null, + b int not null, + key ab(a, b desc) +); + +insert into t1 select A.seq, B.seq*10 from seq_1_to_10 A, seq_1_to_10 B; + +set optimizer_trace=1; +explain select * from t1 force index(ab) where a>=8 and b>=50; +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; + +explain select * from t1 force index(ab) where a>=8 and b<=50; +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; + +select * from t1 force index(ab) where a>=8 and b<=50; +select * from t1 ignore index(ab) where a>=8 and b<=50 order by a, b desc; + +explain +select * from t1 where a between 2 and 4 and b between 50 and 80; +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; + +select * from t1 where a between 2 and 4 and b between 50 and 80; + +drop table t1; + +create table t2 ( + a int not null, + b int not null, + key ab(a desc, b desc) +); +insert into t2 select A.seq, B.seq*10 from seq_1_to_10 A, seq_1_to_10 B; + +explain +select * from t2 where a between 2 and 4; +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; + +explain +select * from t2 where a between 2 and 4 and b between 50 and 80; +select json_detailed(json_extract(trace, '$**.range_access_plan.ranges')) +from information_schema.optimizer_trace; + +set optimizer_trace=default; +drop table t2; diff --git a/sql/item_geofunc.cc b/sql/item_geofunc.cc index 49b85e2213b..a2a99bcdf8f 100644 --- a/sql/item_geofunc.cc +++ b/sql/item_geofunc.cc @@ -1083,7 +1083,8 @@ Item_func_spatial_rel::get_mm_leaf(RANGE_OPT_PARAM *param, DBUG_RETURN(0); // out of memory field->get_key_image(str, key_part->length, key_part->image_type); SEL_ARG *tree; - if (!(tree= new (param->mem_root) SEL_ARG(field, str, str))) + + if (!(tree= new (param->mem_root) SEL_ARG(field, true, str, str))) DBUG_RETURN(0); // out of memory switch (type) { diff --git a/sql/key.cc b/sql/key.cc index f2cebfe6d82..c43d3c36d5d 100644 --- a/sql/key.cc +++ b/sql/key.cc @@ -495,6 +495,7 @@ int key_cmp(KEY_PART_INFO *key_part, const uchar *key, uint key_length) { int cmp; store_length= key_part->store_length; + int sort_order = (key_part->key_part_flag & HA_REVERSE_SORT) ? -1 : 1; if (key_part->null_bit) { /* This key part allows null values; NULL is lower than everything */ @@ -503,19 +504,19 @@ int key_cmp(KEY_PART_INFO *key_part, const uchar *key, uint key_length) { /* the range is expecting a null value */ if (!field_is_null) - return 1; // Found key is > range + return sort_order; // Found key is > range /* null -- exact match, go to next key part */ continue; } else if (field_is_null) - return -1; // NULL is less than any value + return -sort_order; // NULL is less than any value key++; // Skip null byte store_length--; } if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0) - return -1; + return -sort_order; if (cmp > 0) - return 1; + return sort_order; } return 0; // Keys are equal } @@ -574,6 +575,7 @@ int key_rec_cmp(void *key_p, uchar *first_rec, uchar *second_rec) do { field= key_part->field; + int sort_order = (key_part->key_part_flag & HA_REVERSE_SORT) ? -1 : 1; if (key_part->null_bit) { @@ -593,12 +595,12 @@ int key_rec_cmp(void *key_p, uchar *first_rec, uchar *second_rec) ; /* Fall through, no NULL fields */ else { - DBUG_RETURN(+1); + DBUG_RETURN(sort_order); } } else if (!sec_is_null) { - DBUG_RETURN(-1); + DBUG_RETURN(-sort_order); } else goto next_loop; /* Both were NULL */ @@ -612,7 +614,7 @@ int key_rec_cmp(void *key_p, uchar *first_rec, uchar *second_rec) */ if ((result= field->cmp_prefix(field->ptr+first_diff, field->ptr+sec_diff, key_part->length))) - DBUG_RETURN(result); + DBUG_RETURN(result * sort_order); next_loop: key_part++; key_part_num++; diff --git a/sql/opt_range.cc b/sql/opt_range.cc index 86539046a32..541a921435a 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -1879,6 +1879,7 @@ SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc() max_flag=arg.max_flag; maybe_flag=arg.maybe_flag; maybe_null=arg.maybe_null; + is_ascending= arg.is_ascending; part=arg.part; field=arg.field; min_value=arg.min_value; @@ -1904,9 +1905,10 @@ inline void SEL_ARG::make_root() use_count=0; elements=1; } -SEL_ARG::SEL_ARG(Field *f,const uchar *min_value_arg, +SEL_ARG::SEL_ARG(Field *f, bool is_asc, const uchar *min_value_arg, const uchar *max_value_arg) :min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()), + is_ascending(is_asc), elements(1), use_count(1), field(f), min_value((uchar*) min_value_arg), max_value((uchar*) max_value_arg), next(0),prev(0), next_key_part(0), color(BLACK), type(KEY_RANGE), weight(1) @@ -1915,11 +1917,12 @@ SEL_ARG::SEL_ARG(Field *f,const uchar *min_value_arg, max_part_no= 1; } -SEL_ARG::SEL_ARG(Field *field_,uint8 part_, +SEL_ARG::SEL_ARG(Field *field_,uint8 part_, bool is_asc_, uchar *min_value_, uchar *max_value_, uint8 min_flag_,uint8 max_flag_,uint8 maybe_flag_) :min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_), - part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1), + part(part_),maybe_null(field_->real_maybe_null()), is_ascending(is_asc_), + elements(1),use_count(1), field(field_), min_value(min_value_), max_value(max_value_), next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE), weight(1) { @@ -1938,8 +1941,8 @@ SEL_ARG::SEL_ARG(Field *field_,uint8 part_, class SEL_ARG_LE: public SEL_ARG { public: - SEL_ARG_LE(const uchar *key, Field *field) - :SEL_ARG(field, key, key) + SEL_ARG_LE(const uchar *key, Field *field, bool is_asc) + :SEL_ARG(field, is_asc, key, key) { if (!field->real_maybe_null()) min_flag= NO_MIN_RANGE; // From start @@ -1959,16 +1962,17 @@ class SEL_ARG_LT: public SEL_ARG_LE Use this constructor if value->save_in_field() went precisely, without any data rounding or truncation. */ - SEL_ARG_LT(const uchar *key, Field *field) - :SEL_ARG_LE(key, field) + SEL_ARG_LT(const uchar *key, Field *field, bool is_asc) + :SEL_ARG_LE(key, field, is_asc) { max_flag= NEAR_MAX; } /* Use this constructor if value->save_in_field() returned success, but we don't know if rounding or truncation happened (as some Field::store() do not report minor data changes). */ - SEL_ARG_LT(THD *thd, const uchar *key, Field *field, Item *value) - :SEL_ARG_LE(key, field) + SEL_ARG_LT(THD *thd, const uchar *key, Field *field, bool is_asc, + Item *value) + :SEL_ARG_LE(key, field, is_asc) { if (stored_field_cmp_to_item(thd, field, value) == 0) max_flag= NEAR_MAX; @@ -1984,7 +1988,7 @@ class SEL_ARG_GT: public SEL_ARG without any data rounding or truncation. */ SEL_ARG_GT(const uchar *key, const KEY_PART *key_part, Field *field) - :SEL_ARG(field, key, key) + :SEL_ARG(field, !(key_part->flag & HA_REVERSE_SORT), key, key) { // Don't use open ranges for partial key_segments if (!(key_part->flag & HA_PART_KEY_SEG)) @@ -1998,7 +2002,7 @@ class SEL_ARG_GT: public SEL_ARG */ SEL_ARG_GT(THD *thd, const uchar *key, const KEY_PART *key_part, Field *field, Item *value) - :SEL_ARG(field, key, key) + :SEL_ARG(field, !(key_part->flag & HA_REVERSE_SORT), key, key) { // Don't use open ranges for partial key_segments if ((!(key_part->flag & HA_PART_KEY_SEG)) && @@ -2016,8 +2020,8 @@ class SEL_ARG_GE: public SEL_ARG Use this constructor if value->save_in_field() went precisely, without any data rounding or truncation. */ - SEL_ARG_GE(const uchar *key, Field *field) - :SEL_ARG(field, key, key) + SEL_ARG_GE(const uchar *key, Field *field, bool is_asc) + :SEL_ARG(field, is_asc, key, key) { max_flag= NO_MAX_RANGE; } @@ -2028,7 +2032,7 @@ class SEL_ARG_GE: public SEL_ARG */ SEL_ARG_GE(THD *thd, const uchar *key, const KEY_PART *key_part, Field *field, Item *value) - :SEL_ARG(field, key, key) + :SEL_ARG(field, !(key_part->flag & HA_REVERSE_SORT), key, key) { // Don't use open ranges for partial key_segments if ((!(key_part->flag & HA_PART_KEY_SEG)) && @@ -2059,7 +2063,8 @@ SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, } else { - if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value, + if (!(tmp= new (param->mem_root) SEL_ARG(field, part, is_ascending, + min_value, max_value, min_flag, max_flag, maybe_flag))) return 0; // OOM tmp->parent=new_parent; @@ -2830,6 +2835,7 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, } trace_keypart.end(); trace_idx_details.add("usable", !unusable_has_desc_keyparts); + unusable_has_desc_keyparts= false; if (unusable_has_desc_keyparts) // TODO MDEV-13756 { key_parts= param.key[param.keys]; @@ -4420,12 +4426,14 @@ int find_used_partitions(PART_PRUNE_PARAM *ppar, SEL_ARG *key_tree) key_tree->next_key_part->store_min_key(ppar->key, &tmp_min_key, &tmp_min_flag, - ppar->last_part_partno); + ppar->last_part_partno, + true); if (!tmp_max_flag) key_tree->next_key_part->store_max_key(ppar->key, &tmp_max_key, &tmp_max_flag, - ppar->last_part_partno); + ppar->last_part_partno, + false); flag= tmp_min_flag | tmp_max_flag; } else @@ -8671,7 +8679,8 @@ Item_func_null_predicate::get_mm_leaf(RANGE_OPT_PARAM *param, if (!field->real_maybe_null()) DBUG_RETURN(type == ISNULL_FUNC ? &null_element : NULL); SEL_ARG *tree; - if (!(tree= new (alloc) SEL_ARG(field, is_null_string, is_null_string))) + bool is_asc= !(key_part->flag & HA_REVERSE_SORT); + if (!(tree= new (alloc) SEL_ARG(field, is_asc, is_null_string, is_null_string))) DBUG_RETURN(0); if (type == Item_func::ISNOTNULL_FUNC) { @@ -8771,7 +8780,8 @@ Item_func_like::get_mm_leaf(RANGE_OPT_PARAM *param, int2store(min_str + maybe_null, min_length); int2store(max_str + maybe_null, max_length); } - SEL_ARG *tree= new (param->mem_root) SEL_ARG(field, min_str, max_str); + bool is_asc= !(key_part->flag & HA_REVERSE_SORT); + SEL_ARG *tree= new (param->mem_root) SEL_ARG(field, is_asc, min_str, max_str); DBUG_RETURN(tree); } @@ -9019,18 +9029,19 @@ SEL_ARG *Field::stored_field_make_mm_leaf(RANGE_OPT_PARAM *param, if (!(str= make_key_image(param->mem_root, key_part))) DBUG_RETURN(0); + bool is_asc= !(key_part->flag & HA_REVERSE_SORT); switch (op) { case SCALAR_CMP_LE: - DBUG_RETURN(new (mem_root) SEL_ARG_LE(str, this)); + DBUG_RETURN(new (mem_root) SEL_ARG_LE(str, this, is_asc)); case SCALAR_CMP_LT: - DBUG_RETURN(new (mem_root) SEL_ARG_LT(thd, str, this, value)); + DBUG_RETURN(new (mem_root) SEL_ARG_LT(thd, str, this, is_asc, value)); case SCALAR_CMP_GT: DBUG_RETURN(new (mem_root) SEL_ARG_GT(thd, str, key_part, this, value)); case SCALAR_CMP_GE: DBUG_RETURN(new (mem_root) SEL_ARG_GE(thd, str, key_part, this, value)); case SCALAR_CMP_EQ: case SCALAR_CMP_EQUAL: - DBUG_RETURN(new (mem_root) SEL_ARG(this, str, str)); + DBUG_RETURN(new (mem_root) SEL_ARG(this, is_asc, str, str)); break; } DBUG_ASSERT(0); @@ -9048,18 +9059,19 @@ SEL_ARG *Field::stored_field_make_mm_leaf_exact(RANGE_OPT_PARAM *param, if (!(str= make_key_image(param->mem_root, key_part))) DBUG_RETURN(0); + bool is_asc= !(key_part->flag & HA_REVERSE_SORT); switch (op) { case SCALAR_CMP_LE: - DBUG_RETURN(new (param->mem_root) SEL_ARG_LE(str, this)); + DBUG_RETURN(new (param->mem_root) SEL_ARG_LE(str, this, is_asc)); case SCALAR_CMP_LT: - DBUG_RETURN(new (param->mem_root) SEL_ARG_LT(str, this)); + DBUG_RETURN(new (param->mem_root) SEL_ARG_LT(str, this, is_asc)); case SCALAR_CMP_GT: DBUG_RETURN(new (param->mem_root) SEL_ARG_GT(str, key_part, this)); case SCALAR_CMP_GE: - DBUG_RETURN(new (param->mem_root) SEL_ARG_GE(str, this)); + DBUG_RETURN(new (param->mem_root) SEL_ARG_GE(str, this, is_asc)); case SCALAR_CMP_EQ: case SCALAR_CMP_EQUAL: - DBUG_RETURN(new (param->mem_root) SEL_ARG(this, str, str)); + DBUG_RETURN(new (param->mem_root) SEL_ARG(this, is_asc, str, str)); break; } DBUG_ASSERT(0); @@ -11777,6 +11789,46 @@ get_quick_select(PARAM *param,uint idx,SEL_ARG *key_tree, uint mrr_flags, } +void SEL_ARG::store_next_min_max_keys(KEY_PART *key, + uchar **cur_min_key, uint *cur_min_flag, + uchar **cur_max_key, uint *cur_max_flag, + int *min_part, int *max_part) +{ + DBUG_ASSERT(next_key_part); + bool asc = next_key_part->is_ascending; + + if (!get_min_flag()) + { + if (asc) + { + *min_part += next_key_part->store_min_key(key, cur_min_key, + cur_min_flag, MAX_KEY, true); + } + else + { + uint tmp_flag = invert_min_flag(*cur_min_flag); + *min_part += next_key_part->store_max_key(key, cur_min_key, &tmp_flag, + MAX_KEY, true); + *cur_min_flag = invert_max_flag(tmp_flag); + } + } + if (!get_max_flag()) + { + if (asc) + { + *max_part += next_key_part->store_max_key(key, cur_max_key, + cur_max_flag, MAX_KEY, false); + } + else + { + uint tmp_flag = invert_max_flag(*cur_max_flag); + *max_part += next_key_part->store_min_key(key, cur_max_key, &tmp_flag, + MAX_KEY, false); + *cur_max_flag = invert_min_flag(tmp_flag); + } + } +} + /* ** Fix this to get all possible sub_ranges */ @@ -11790,17 +11842,19 @@ get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key, int min_part= key_tree->part-1, // # of keypart values in min_key buffer max_part= key_tree->part-1; // # of keypart values in max_key buffer - if (key_tree->left != &null_element) + SEL_ARG *next_tree = key_tree->is_ascending ? key_tree->left : key_tree->right; + if (next_tree != &null_element) { - if (get_quick_keys(param,quick,key,key_tree->left, + if (get_quick_keys(param,quick,key,next_tree, min_key,min_key_flag, max_key, max_key_flag)) return 1; } uchar *tmp_min_key=min_key,*tmp_max_key=max_key; - min_part+= key_tree->store_min(key[key_tree->part].store_length, - &tmp_min_key,min_key_flag); - max_part+= key_tree->store_max(key[key_tree->part].store_length, - &tmp_max_key,max_key_flag); + + key_tree->store_min_max(key[key_tree->part].store_length, + &tmp_min_key, min_key_flag, + &tmp_max_key, max_key_flag, + &min_part, &max_part); if (key_tree->next_key_part && key_tree->next_key_part->type == SEL_ARG::KEY_RANGE && @@ -11810,31 +11864,40 @@ get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key, memcmp(min_key, max_key, (uint)(tmp_max_key - max_key))==0 && key_tree->min_flag==0 && key_tree->max_flag==0) { + // psergey-note: simplified the parameters below as follows: + // min_key_flag | key_tree->min_flag -> min_key_flag + // max_key_flag | key_tree->max_flag -> max_key_flag if (get_quick_keys(param,quick,key,key_tree->next_key_part, - tmp_min_key, min_key_flag | key_tree->min_flag, - tmp_max_key, max_key_flag | key_tree->max_flag)) + tmp_min_key, min_key_flag, + tmp_max_key, max_key_flag)) return 1; goto end; // Ugly, but efficient } { - uint tmp_min_flag=key_tree->min_flag,tmp_max_flag=key_tree->max_flag; - if (!tmp_min_flag) - min_part+= key_tree->next_key_part->store_min_key(key, - &tmp_min_key, - &tmp_min_flag, - MAX_KEY); - if (!tmp_max_flag) - max_part+= key_tree->next_key_part->store_max_key(key, - &tmp_max_key, - &tmp_max_flag, - MAX_KEY); + uint tmp_min_flag= key_tree->get_min_flag(); + uint tmp_max_flag= key_tree->get_max_flag(); + + key_tree->store_next_min_max_keys(key, + &tmp_min_key, &tmp_min_flag, + &tmp_max_key, &tmp_max_flag, + &min_part, &max_part); flag=tmp_min_flag | tmp_max_flag; } } else { - flag = (key_tree->min_flag & GEOM_FLAG) ? - key_tree->min_flag : key_tree->min_flag | key_tree->max_flag; + if (key_tree->is_ascending) + { + flag= (key_tree->min_flag & GEOM_FLAG) ? key_tree->min_flag: + (key_tree->min_flag | + key_tree->max_flag); + } + else + { + // Invert flags for DESC keypart + flag= invert_min_flag(key_tree->min_flag) | + invert_max_flag(key_tree->max_flag); + } } /* @@ -11895,8 +11958,9 @@ get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key, return 1; end: - if (key_tree->right != &null_element) - return get_quick_keys(param,quick,key,key_tree->right, + next_tree = key_tree->is_ascending ? key_tree->right : key_tree->left; + if (next_tree != &null_element) + return get_quick_keys(param,quick,key,next_tree, min_key,min_key_flag, max_key,max_key_flag); return 0; diff --git a/sql/opt_range.h b/sql/opt_range.h index 1014176ecc5..6864a5c583a 100644 --- a/sql/opt_range.h +++ b/sql/opt_range.h @@ -54,6 +54,33 @@ struct KEY_PART { }; +/** + A helper function to invert min flags to max flags for DESC key parts. + It changes NEAR_MIN, NO_MIN_RANGE to NEAR_MAX, NO_MAX_RANGE appropriately +*/ + +inline uint invert_min_flag(uint min_flag) +{ + uint max_flag_out = min_flag & ~(NEAR_MIN | NO_MIN_RANGE); + if (min_flag & NEAR_MIN) max_flag_out |= NEAR_MAX; + if (min_flag & NO_MIN_RANGE) max_flag_out |= NO_MAX_RANGE; + return max_flag_out; +} + + +/** + A helper function to invert max flags to min flags for DESC key parts. + It changes NEAR_MAX, NO_MAX_RANGE to NEAR_MIN, NO_MIN_RANGE appropriately +*/ + +inline uint invert_max_flag(uint max_flag) +{ + uint min_flag_out = max_flag & ~(NEAR_MAX | NO_MAX_RANGE); + if (max_flag & NEAR_MAX) min_flag_out |= NEAR_MIN; + if (max_flag & NO_MAX_RANGE) min_flag_out |= NO_MIN_RANGE; + return min_flag_out; +} + class RANGE_OPT_PARAM; /* A construction block of the SEL_ARG-graph. @@ -267,6 +294,8 @@ class RANGE_OPT_PARAM; - it is a lot easier to compute than computing the number of ranges, - it can be updated incrementally when performing AND/OR operations on parts of the graph. + + 6. For handling DESC keyparts, See HowRangeOptimizerHandlesDescKeyparts */ class SEL_ARG :public Sql_alloc @@ -277,6 +306,11 @@ class SEL_ARG :public Sql_alloc uint8 min_flag,max_flag,maybe_flag; uint8 part; // Which key part uint8 maybe_null; + /* + Whether the keypart is ascending or descending. + See HowRangeOptimizerHandlesDescKeyparts for details. + */ + uint8 is_ascending; /* The ordinal number the least significant component encountered in the ranges of the SEL_ARG tree (the first component has number 1) @@ -327,11 +361,15 @@ class SEL_ARG :public Sql_alloc SEL_ARG() {} SEL_ARG(SEL_ARG &); - SEL_ARG(Field *,const uchar *, const uchar *); - SEL_ARG(Field *field, uint8 part, uchar *min_value, uchar *max_value, + SEL_ARG(Field *, bool is_asc, const uchar *, const uchar *); + SEL_ARG(Field *field, uint8 part, bool is_asc, + uchar *min_value, uchar *max_value, uint8 min_flag, uint8 max_flag, uint8 maybe_flag); + + /* This is used to construct degenerate SEL_ARGS like ALWAYS, IMPOSSIBLE, etc */ SEL_ARG(enum Type type_arg) - :min_flag(0), max_part_no(0) /* first key part means 1. 0 mean 'no parts'*/, + :min_flag(0), is_ascending(false), + max_part_no(0) /* first key part means 1. 0 mean 'no parts'*/, elements(1),use_count(1),left(0),right(0), next_key_part(0), color(BLACK), type(type_arg), weight(1) {} @@ -409,19 +447,20 @@ class SEL_ARG :public Sql_alloc { new_max=arg->max_value; flag_max=arg->max_flag; } - return new (thd->mem_root) SEL_ARG(field, part, new_min, new_max, flag_min, + return new (thd->mem_root) SEL_ARG(field, part, is_ascending, + new_min, new_max, flag_min, flag_max, MY_TEST(maybe_flag && arg->maybe_flag)); } SEL_ARG *clone_first(SEL_ARG *arg) { // min <= X < arg->min - return new SEL_ARG(field,part, min_value, arg->min_value, + return new SEL_ARG(field, part, is_ascending, min_value, arg->min_value, min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX, maybe_flag | arg->maybe_flag); } SEL_ARG *clone_last(SEL_ARG *arg) { // min <= X <= key_max - return new SEL_ARG(field, part, min_value, arg->max_value, + return new SEL_ARG(field, part, is_ascending, min_value, arg->max_value, min_flag, arg->max_flag, maybe_flag | arg->maybe_flag); } SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next); @@ -504,6 +543,56 @@ class SEL_ARG :public Sql_alloc return 0; } + /* Save minimum and maximum, taking index order into account */ + void store_min_max(uint length, + uchar **min_key, uint min_flag, + uchar **max_key, uint max_flag, + int *min_part, int *max_part) + { + if (is_ascending) { + *min_part += store_min(length, min_key, min_flag); + *max_part += store_max(length, max_key, max_flag); + } else { + *max_part += store_min(length, max_key, min_flag); + *min_part += store_max(length, min_key, max_flag); + } + } + /* + Get the flag for range's starting endpoint, taking index order into + account. + */ + uint get_min_flag() + { + return (is_ascending ? min_flag : invert_max_flag(max_flag)); + } + /* + Get the flag for range's starting endpoint, taking index order into + account. + */ + uint get_max_flag() + { + return (is_ascending ? max_flag : invert_min_flag(min_flag)); + } + /* Get the previous interval, taking index order into account */ + inline SEL_ARG* index_order_prev() + { + return is_ascending? prev: next; + } + /* Get the next interval, taking index order into account */ + inline SEL_ARG* index_order_next() + { + return is_ascending? next: prev; + } + + /* + Produce a single multi-part interval, taking key part ordering into + account. + */ + void store_next_min_max_keys(KEY_PART *key, uchar **cur_min_key, + uint *cur_min_flag, uchar **cur_max_key, + uint *cur_max_flag, int *min_part, + int *max_part); + /* Returns a number of keypart values appended to the key buffer for min key and max key. This function is used by both Range @@ -516,7 +605,8 @@ class SEL_ARG :public Sql_alloc int store_min_key(KEY_PART *key, uchar **range_key, uint *range_key_flag, - uint last_part) + uint last_part, + bool start_key) { SEL_ARG *key_tree= first(); uint res= key_tree->store_min(key[key_tree->part].store_length, @@ -525,15 +615,26 @@ class SEL_ARG :public Sql_alloc if (!res) return 0; *range_key_flag|= key_tree->min_flag; - if (key_tree->next_key_part && - key_tree->next_key_part->type == SEL_ARG::KEY_RANGE && + SEL_ARG *nkp= key_tree->next_key_part; + if (nkp && nkp->type == SEL_ARG::KEY_RANGE && key_tree->part != last_part && - key_tree->next_key_part->part == key_tree->part+1 && + nkp->part == key_tree->part+1 && !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN))) - res+= key_tree->next_key_part->store_min_key(key, - range_key, - range_key_flag, - last_part); + { + const bool asc = nkp->is_ascending; + if (start_key == asc) + { + res+= nkp->store_min_key(key, range_key, range_key_flag, last_part, + start_key); + } + else + { + uint tmp_flag = invert_min_flag(*range_key_flag); + res += nkp->store_max_key(key, range_key, &tmp_flag, last_part, + start_key); + *range_key_flag = invert_max_flag(tmp_flag); + } + } return res; } @@ -541,7 +642,8 @@ class SEL_ARG :public Sql_alloc int store_max_key(KEY_PART *key, uchar **range_key, uint *range_key_flag, - uint last_part) + uint last_part, + bool start_key) { SEL_ARG *key_tree= last(); uint res=key_tree->store_max(key[key_tree->part].store_length, @@ -549,15 +651,26 @@ class SEL_ARG :public Sql_alloc if (!res) return 0; *range_key_flag|= key_tree->max_flag; - if (key_tree->next_key_part && - key_tree->next_key_part->type == SEL_ARG::KEY_RANGE && + SEL_ARG *nkp= key_tree->next_key_part; + if (nkp && nkp->type == SEL_ARG::KEY_RANGE && key_tree->part != last_part && - key_tree->next_key_part->part == key_tree->part+1 && + nkp->part == key_tree->part+1 && !(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX))) - res+= key_tree->next_key_part->store_max_key(key, - range_key, - range_key_flag, - last_part); + { + const bool asc = nkp->is_ascending; + if ((!start_key && asc) || (start_key && !asc)) + { + res += nkp->store_max_key(key, range_key, range_key_flag, last_part, + start_key); + } + else + { + uint tmp_flag = invert_max_flag(*range_key_flag); + res += nkp->store_min_key(key, range_key, &tmp_flag, last_part, + start_key); + *range_key_flag = invert_min_flag(tmp_flag); + } + } return res; } @@ -661,13 +774,83 @@ class SEL_ARG :public Sql_alloc SEL_ARG *clone_tree(RANGE_OPT_PARAM *param); }; +/* + HowRangeOptimizerHandlesDescKeyparts + ==================================== + + Starting with MySQL-8.0 and MariaDB 10.8, index key parts may be descending, + for example: + + INDEX idx1(col1, col2 DESC, col3, col4 DESC) + + Range Optimizer handles this as follows: + + The SEL_ARG object has SEL_ARG::is_ascending which specifies whether the + keypart is ascending. + + Other than that, the SEL_ARG graph is built without any regard to DESC + keyparts. + + For example, for an index + + INDEX idx2(kp1 DESC, kp2) + + and range + + kp1 BETWEEN 10 and 20 (RANGE-1) + + the SEL_ARG will have min_value=10, max_value=20, is_ascending=false. + + The ordering of key parts is taken into account when SEL_ARG graph is + linearized to ranges, in sel_arg_range_seq_next() and get_quick_keys(). + + The storage engine expects the first bound to be the first in the index and + the last bound to be the last, that is, for (RANGE-1) we will flip min and + max and generate these key_range structures: + + start.key='20' , end.key='10' + + See SEL_ARG::store_min_max(). The flag values are flipped as well, see + SEL_ARG::get_min_flag(), get_max_flag(). + + == Handling multiple key parts == + + For multi-part keys, the order of key parts has an effect on which ranges are + generated. Consider + + kp1 >= 10 AND kp2 >'foo' + + for INDEX(kp1 ASC, kp2 ASC) the range will be + + (kp1, kp2) > (10, 'foo') + + while for INDEX(kp1 ASC, kp2 DESC) it will be just + + kp1 >= 10 + + Another example: + + (kp1 BETWEEN 10 AND 20) AND (kp2 BETWEEN 'foo' AND 'quux') + + with INDEX (kp1 ASC, kp2 ASC) will generate + + (10, 'foo') <= (kp1, kp2) < (20, 'quux') + + while with index INDEX (kp1 ASC, kp2 DESC) it will generate + + (10, 'quux') <= (kp1, kp2) < (20, 'foo') + + This is again achieved by sel_arg_range_seq_next() and get_quick_keys() + flipping SEL_ARG's min,max, their flags and next/prev as needed. +*/ + extern MYSQL_PLUGIN_IMPORT SEL_ARG null_element; class SEL_ARG_IMPOSSIBLE: public SEL_ARG { public: SEL_ARG_IMPOSSIBLE(Field *field) - :SEL_ARG(field, 0, 0) + :SEL_ARG(field, false, 0, 0) { type= SEL_ARG::IMPOSSIBLE; } diff --git a/sql/opt_range_mrr.cc b/sql/opt_range_mrr.cc index 20413f5df63..8877e15d5b5 100644 --- a/sql/opt_range_mrr.cc +++ b/sql/opt_range_mrr.cc @@ -34,7 +34,7 @@ typedef struct st_range_seq_entry uint min_key_flag, max_key_flag; /* Number of key parts */ - uint min_key_parts, max_key_parts; + int min_key_parts, max_key_parts; SEL_ARG *key_tree; } RANGE_SEQ_ENTRY; @@ -105,13 +105,14 @@ static void step_down_to(SEL_ARG_RANGE_SEQ *arg, SEL_ARG *key_tree) cur->max_key_parts= prev->max_key_parts; uint16 stor_length= arg->param->key[arg->keyno][key_tree->part].store_length; - cur->min_key_parts += key_tree->store_min(stor_length, &cur->min_key, - prev->min_key_flag); - cur->max_key_parts += key_tree->store_max(stor_length, &cur->max_key, - prev->max_key_flag); - cur->min_key_flag= prev->min_key_flag | key_tree->min_flag; - cur->max_key_flag= prev->max_key_flag | key_tree->max_flag; + key_tree->store_min_max(stor_length, + &cur->min_key, prev->min_key_flag, + &cur->max_key, prev->max_key_flag, + &cur->min_key_parts, &cur->max_key_parts); + + cur->min_key_flag= prev->min_key_flag | key_tree->get_min_flag(); + cur->max_key_flag= prev->max_key_flag | key_tree->get_max_flag(); if (key_tree->is_null_interval()) cur->min_key_flag |= NULL_RANGE; @@ -165,12 +166,12 @@ bool sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) /* Ok, we're at some "full tuple" position in the tree */ /* Step down if we can */ - if (key_tree->next && key_tree->next != &null_element) + if (key_tree->index_order_next() && key_tree->index_order_next() != &null_element) { //step down; (update the tuple, we'll step right and stay there) seq->i--; - step_down_to(seq, key_tree->next); - key_tree= key_tree->next; + step_down_to(seq, key_tree->index_order_next()); + key_tree= key_tree->index_order_next(); seq->is_ror_scan= FALSE; goto walk_right_n_up; } @@ -185,12 +186,12 @@ bool sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) key_tree= seq->stack[seq->i].key_tree; /* Step down if we can */ - if (key_tree->next && key_tree->next != &null_element) + if (key_tree->index_order_next() && key_tree->index_order_next() != &null_element) { // Step down; update the tuple seq->i--; - step_down_to(seq, key_tree->next); - key_tree= key_tree->next; + step_down_to(seq, key_tree->index_order_next()); + key_tree= key_tree->index_order_next(); break; } } @@ -214,16 +215,10 @@ bool sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) !key_tree->min_flag && !key_tree->max_flag)) { seq->is_ror_scan= FALSE; - if (!key_tree->min_flag) - cur->min_key_parts += - key_tree->next_key_part->store_min_key(seq->param->key[seq->keyno], - &cur->min_key, - &cur->min_key_flag, MAX_KEY); - if (!key_tree->max_flag) - cur->max_key_parts += - key_tree->next_key_part->store_max_key(seq->param->key[seq->keyno], - &cur->max_key, - &cur->max_key_flag, MAX_KEY); + key_tree->store_next_min_max_keys(seq->param->key[seq->keyno], + &cur->min_key, &cur->min_key_flag, + &cur->max_key, &cur->max_key_flag, + &cur->min_key_parts, &cur->max_key_parts); break; } } @@ -235,10 +230,11 @@ bool sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range) key_tree= key_tree->next_key_part; walk_up_n_right: - while (key_tree->prev && key_tree->prev != &null_element) + while (key_tree->index_order_prev() && + key_tree->index_order_prev() != &null_element) { /* Step up */ - key_tree= key_tree->prev; + key_tree= key_tree->index_order_prev(); } step_down_to(seq, key_tree); }

1 0

[Commits] 8708095a025: MDEV-27230: Estimation for filtered rows less precise ...
by psergey 13 Dec '21

13 Dec '21

revision-id: 8708095a0256add4d06abf2d04a91f4f5b7800fb (mariadb-10.6.1-330-g8708095a025) parent(s): 917f636563ea2e300c7f7f9ab0f240749525da51 author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2021-12-13 23:46:04 +0300 message: MDEV-27230: Estimation for filtered rows less precise ... Fix the code in Histogram_json_hb::range_selectivity that handles special cases: a non-inclusive endpoint hitting a bucket boundary... --- mysql-test/main/statistics_json.result | 17 +++++++++++++++++ mysql-test/main/statistics_json.test | 10 ++++++++++ sql/opt_histogram_json.cc | 1 + 3 files changed, 28 insertions(+) diff --git a/mysql-test/main/statistics_json.result b/mysql-test/main/statistics_json.result index 7373da0570b..a54d5fd4151 100644 --- a/mysql-test/main/statistics_json.result +++ b/mysql-test/main/statistics_json.result @@ -8194,3 +8194,20 @@ analyze select * from t2 where a =100; id select_type table type possible_keys key key_len ref rows r_rows filtered r_filtered Extra 1 SIMPLE t2 ALL NULL NULL NULL NULL 1011 1011.00 0.10 0.10 Using where drop table t0,t1,t2; +# +# MDEV-27230: Estimation for filtered rows less precise ... +# +create table t1 (a char(1)); +insert into t1 select chr(seq%26+97) from seq_1_to_50; +insert into t1 select ':' from t1; +analyze table t1 persistent for all; +Table Op Msg_type Msg_text +test.t1 analyze status Engine-independent statistics collected +test.t1 analyze status OK +analyze select COUNT(*) FROM t1 WHERE a <> 'a'; +id select_type table type possible_keys key key_len ref rows r_rows filtered r_filtered Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 100 100.00 99.00 99.00 Using where +analyze select COUNT(*) FROM t1 WHERE a < 'a'; +id select_type table type possible_keys key key_len ref rows r_rows filtered r_filtered Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 100 100.00 50.00 50.00 Using where +drop table t1; diff --git a/mysql-test/main/statistics_json.test b/mysql-test/main/statistics_json.test index b67df41d9ba..024cb55e540 100644 --- a/mysql-test/main/statistics_json.test +++ b/mysql-test/main/statistics_json.test @@ -380,3 +380,13 @@ analyze select * from t2 where a =100; drop table t0,t1,t2; +--echo # +--echo # MDEV-27230: Estimation for filtered rows less precise ... +--echo # +create table t1 (a char(1)); +insert into t1 select chr(seq%26+97) from seq_1_to_50; +insert into t1 select ':' from t1; +analyze table t1 persistent for all; +analyze select COUNT(*) FROM t1 WHERE a <> 'a'; +analyze select COUNT(*) FROM t1 WHERE a < 'a'; +drop table t1; diff --git a/sql/opt_histogram_json.cc b/sql/opt_histogram_json.cc index d65bb225477..2ee6cd73dbe 100644 --- a/sql/opt_histogram_json.cc +++ b/sql/opt_histogram_json.cc @@ -1022,6 +1022,7 @@ double Histogram_json_hb::range_selectivity(Field *field, key_range *min_endp, $CONST. Move to the previous bucket. */ idx--; + equal= false; } double left_fract= get_left_fract(idx);

1 0