Bug #84070 Incorrect order-by behavior on a partitioned table with a composite prefix index
Submitted: 6 Dec 2016 6:53 Modified: 8 May 2020 22:11
Reporter: Jackie Xu Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S2 (Serious)
Version:5.6/5.7/8.0 OS:Ubuntu (16.04)
Assigned to: CPU Architecture:Any
Tags: order-by, partitions

[6 Dec 2016 6:53] Jackie Xu
Description:
The order-by clause gives wrong results when used on a partitioned table with a composite index that contains a prefix index as the leftmost column.

Some observations:
 - Happens on latest MySQL versions of 5.6 and 5.7.
 - Only shows this behavior when the prefix index is the leftmost column: (`id`,`data`(1)) works fine.
 - Only happens with multiple partitions.
 - Does not happen if the part of the `data` column that is in the prefix index is different. Only happens if that part is the same, but the remainder is different (e.g. 'ab' vs 'ac').
 - Breaks ascending and descending order based on the alphabetical comparison of the `data` column (i.e. alphabetically greater values will break ascending order, and alphabetically lesser values will break descending order).

How to repeat:
CREATE TABLE `test` (
  `id` int unsigned NOT NULL,
  `data` varchar(2) DEFAULT NULL,
  KEY `data_idx` (`data`(1),`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
/*!50100 PARTITION BY RANGE (`id`)
(PARTITION p10 VALUES LESS THAN (10) ENGINE = InnoDB,
 PARTITION p20 VALUES LESS THAN (20) ENGINE = InnoDB) */;

INSERT INTO `test` VALUES 
    (6, 'ab'),
    (4, 'ab'),
    (5, 'ab'), 
    (16, 'ab'),
    (14, 'ab'),
    (15, 'ab'),
/*The following values cause the weird behavior*/
    (5, 'ac'),
    (15, 'aa')
;

mysql> SELECT id FROM test WHERE data = 'ab' ORDER BY id ASC;
+----+
| id |
+----+
|  4 |
|  5 |
| 14 |
| 15 |
| 16 |
|  6 |
+----+

mysql> SELECT id FROM test WHERE data = 'ab' ORDER BY id DESC;
+----+
| id |
+----+
| 16 |
|  6 |
|  5 |
|  4 |
| 15 |
| 14 |
+----+
[6 Dec 2016 9:33] MySQL Verification Team
Thank you for the bug report. Verified as described.
[29 Sep 2019 4:01] Quanan Han
We have the same problem, and we solve this problem by modifying the execution plan.

When order by clause  using prefix index in partition table, the "ordered_index_order_by" plan would cause problems because of there is a problem with the comparison of the columns corresponding to the prefix index. This scene must be sorted using file sort.

As a result, we modify the execution plan:
In funcetion "test_if_skip_sort_order", we add the bellow code (For mysql5.6/5.7):

  if (is_perfix_index(table, ref_key, ref_key_parts) &&
    table && table->is_partition()
    && order)
  {
    DBUG_RETURN(0);
  }

bellow is the  function implementation of is_prefix_index:

bool is_perfix_index(TABLE* table, int key, uint key_parts)
{
  if (!table || !table->key_info)
  {
    return false;
  }
  KEY_PART_INFO* key_part = table->key_info[key].key_part;
  KEY* key_info = table->key_info;

  for (uint i = 0; i < key_parts; i++, key_parts++)
  {
    if (key_part->field &&
      (key_part->length !=
        table->field[key_part->fieldnr - 1]->key_length() &&
        !(key_info->flags & (HA_FULLTEXT | HA_SPATIAL))))
    {
      return true;
    }
  }
  return false;
}
[29 Sep 2019 6:23] Quanan Han
diff --git a/sql/sql_optimizer.cc b/sql/sql_optimizer.cc
index 255056ed4d5..9bac65b96e2 100644
--- a/sql/sql_optimizer.cc
+++ b/sql/sql_optimizer.cc
@@ -1802,6 +1802,28 @@ public:
 #endif
 };
 
+bool is_perfix_index(TABLE* table, int key, uint key_parts)
+{
+  if (!table || !table->key_info)
+  {
+    return false;
+  }
+  KEY_PART_INFO* key_part = table->key_info[key].key_part;
+  KEY* key_info = table->key_info;
+
+  for (uint i = 0; i < key_parts; i++, key_parts++)
+  {
+    if (key_part->field &&
+      (key_part->length !=
+        table->field[key_part->fieldnr - 1]->key_length() &&
+        !(key_info->flags & (HA_FULLTEXT | HA_SPATIAL))))
+    {
+      return true;
+    }
+  }
+  return false;
+}
+
 
 /**
   Test if we can skip ordering by using an index.
@@ -1983,6 +2005,14 @@ test_if_skip_sort_order(JOIN_TAB *tab, ORDER *order, ha_rows select_limit,
     ref_key_parts= actual_key_parts(&table->key_info[tab->index()]);
   }
 
+  if (sort_when_partition_prefix_order &&
+    is_perfix_index(table, ref_key, ref_key_parts) &&
+    table && table->is_partition()
+    && order)
+  {
+    DBUG_RETURN(0);
+  }
+
   Opt_trace_context * const trace= &thd->opt_trace;
   Opt_trace_object trace_wrapper(trace);
   Opt_trace_object
[23 Dec 2019 9:09] Quanan Han
diff --git a/sql/sql_optimizer.cc b/sql/sql_optimizer.cc
index 255056ed4d5..9bac65b96e2 100644
--- a/sql/sql_optimizer.cc
+++ b/sql/sql_optimizer.cc
@@ -1802,6 +1802,28 @@ public:
 #endif
 };
 
+bool is_perfix_index(TABLE* table, int key, uint key_parts)
+{
+  if (!table || !table->key_info)
+  {
+    return false;
+  }
+  KEY_PART_INFO* key_part = table->key_info[key].key_part;
+  KEY* key_info = table->key_info;
+
+  for (uint i = 0; i < key_parts; i++, key_part++)
+  {
+    if (key_part->field &&
+      (key_part->length !=
+        table->field[key_part->fieldnr - 1]->key_length() &&
+        !(key_info->flags & (HA_FULLTEXT | HA_SPATIAL))))
+    {
+      return true;
+    }
+  }
+  return false;
+}
+
 
 /**
   Test if we can skip ordering by using an index.
@@ -1983,6 +2005,14 @@ test_if_skip_sort_order(JOIN_TAB *tab, ORDER *order, ha_rows select_limit,
     ref_key_parts= actual_key_parts(&table->key_info[tab->index()]);
   }
 
+  if (sort_when_partition_prefix_order &&
+    is_perfix_index(table, ref_key, ref_key_parts) &&
+    table && table->is_partition()
+    && order)
+  {
+    DBUG_RETURN(0);
+  }
+
   Opt_trace_context * const trace= &thd->opt_trace;
   Opt_trace_object trace_wrapper(trace);
   Opt_trace_object
[23 Dec 2019 9:41] Quanan Han
diff --git a/sql/sql_optimizer.cc b/sql/sql_optimizer.cc
index 255056ed4d5..9bac65b96e2 100644
--- a/sql/sql_optimizer.cc
+++ b/sql/sql_optimizer.cc
@@ -1802,6 +1802,28 @@ public:
 #endif
 };
 
+bool is_perfix_index(TABLE* table, int key)
+{
+  if (!table || !table->key_info)
+  {
+    return false;
+  }
+  KEY_PART_INFO* key_part = table->key_info[key].key_part;
+  KEY* key_info = table->key_info;
+  uint key_parts = key_info[key].user_defined_key_parts;
+
+  for (uint i = 0; i < key_parts; i++, key_part++)
+  {
+    if (key_part->field &&
+      (key_part->length !=
+        table->field[key_part->fieldnr - 1]->key_length() &&
+        !(key_info->flags & (HA_FULLTEXT | HA_SPATIAL))))
+    {
+      return true;
+    }
+  }
+  return false;
+}
+
 
 /**
   Test if we can skip ordering by using an index.
@@ -1983,6 +2005,14 @@ test_if_skip_sort_order(JOIN_TAB *tab, ORDER *order, ha_rows select_limit,
     ref_key_parts= actual_key_parts(&table->key_info[tab->index()]);
   }
 
+  if (sort_when_partition_prefix_order &&
+    is_perfix_index(table, ref_key) &&
+    table && table->is_partition()
+    && order)
+  {
+    DBUG_RETURN(0);
+  }
+
   Opt_trace_context * const trace= &thd->opt_trace;
   Opt_trace_object trace_wrapper(trace);
   Opt_trace_object
[18 Aug 2020 3:28] Jon Stephens
Documented fix as follows in the MySQL 5.6.49, 5.7.31, and 8.0.21 changelogs:

  A query against a partitioned table, which used an ORDER BY, returned 
  unordered results under the following conditions:

    ·The table had a composite index with a prefix on one of the columns.

    ·The query's WHERE clause contained an equality condition on the 
    prefixed column.

    ·The column with the prefix was the leftmost column in the index.

    ·The column used in the ORDER BY was the rightmost column in the index.

    ·The index was used for handling the ORDER BY.

  Our thanks to Quanan Han for the suggestion.

Closed.