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); }