[Commits] a0643458ca5: MDEV-26996: Support descending indexes in the range optimizer

13 Dec 2021

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

    