DBT-3 Q3: 6 x performance in MySQL 5.6.10

When MySQL gets a query, it is the job of the optimizer to find the cheapest way to execute that query. Decisions include access method (range access, table scan, index lookup etc), join order, sorting strategy etc. If we simplify a bit, the optimizer first identifies the different ways to access each table and calculate their cost. After that, the join order is decided.

However, some access methods can only be considered after the join order has been decided and therefore gets special treatment in the MySQL optimizer. For join conditions, e.g. "WHERE table1.col1 = table2.col2",  index lookup can only be used in table2 if table1 is earlier in the join sequence. Another class of access methods is only meaningful for tables that are first in the join order. An example is queries with ORDER BY ... LIMIT. Prior to MySQL 5.6.10 there was a bug in MySQL that made the optimizer choose inefficient execution plans for this query type. That's the topic I discuss below.


The following database schema will be used:

CREATE TABLE orders( 
  order_id INT PRIMARY KEY, 
  cust_id INT, 
  value INT, 
  INDEX cid (cust_id) 
) ENGINE = InnoDB; 

CREATE TABLE customers( 
  cust_id INT PRIMARY KEY, 
  name VARCHAR (128), 
  address VARCHAR (128) 
) ENGINE = InnoDB; 

Consider the following query (some EXPLAIN columns removed for readability):

mysql> EXPLAIN 
    -> SELECT * 
    -> FROM orders, customers 
    -> WHERE orders.cust_id=customers.cust_id AND 
    ->       orders.cust_id != 4
    -> ORDER BY orders.value;
+----+-------------+-----------+--------+---------------+---------+------+----------------+
| id | select_type | table     | type   | possible_keys | key     | rows | Extra          |
+----+-------------+-----------+--------+---------------+---------+------+----------------+
|  1 | SIMPLE      | orders    | ALL    | cid           | NULL    | 1024 | Using filesort |
|  1 | SIMPLE      | customers | eq_ref | PRIMARY       | PRIMARY |    1 | NULL           |
+----+-------------+-----------+--------+---------------+---------+------+----------------+

For this query, MySQL can choose between table scan, index scan and range access for table 'orders'. Optimizer tracing shows why table scan is chosen:

mysql> SELECT trace FROM information_schema.optimizer_trace;
...
           "rows_estimation": [
              {
                "table": "`orders`",
                "range_analysis": {
                  "table_scan": {
                    "rows": 1024,
                    "cost": 212.15
                  },
                  ...
                  ,
                  "analyzing_range_alternatives": {
                    "range_scan_alternatives": [
                      {
                        "index": "cid",
                        "index_dives_for_eq_ranges": true,
                        "ranges": [
                          "NULL < cust_id < 4",
                          "4 < cust_id"
                        ],
                        "index_only": false,
                        "rows": 1014,
                        "cost": 1218.8,
                        "rowid_ordered": false,
                        "chosen": false,
                        "cause": "cost"
                      }
                    ]
                  }
                }

As you can see, table scan is much cheaper than range scan. The reason is that not only does the range scan need to read 99% of the index entries, but it also has to read 99% of all rows in the table in a random access fashion. Random access = bad :-) But now look what happens if we are only interested in the first 10 rows:

mysql> EXPLAIN
    -> SELECT * 
    -> FROM orders, customers 
    -> WHERE orders.cust_id=customers.cust_id AND 
    -> orders.cust_id != 4
    -> ORDER BY orders.value
    -> LIMIT 10;
+----+-------------+-----------+--------+---------------+---------+------+----------------+
| id | select_type | table     | type   | possible_keys | key     | rows | Extra          |
+----+-------------+-----------+--------+---------------+---------+------+----------------+
|  1 | SIMPLE      | orders    | range  | cid           | cid     | 1014 | Using filesort |
|  1 | SIMPLE      | customers | eq_ref | PRIMARY       | PRIMARY |    1 | NULL           |
+----+-------------+-----------+--------+---------------+---------+------+----------------+

Huh... This plan doesn't make sense at all! We already know from optimizer tracing that table scan is way cheaper than range access for this query. The change of plans didn't remove the need for sorting either. So why did MySQL prior to 5.6.10 make this bad decision?

The answer is that the optimizer recognizes that 'LIMIT 10' can be used to short-cut execution of the query once the 10 first rows in the result set have been found. In theory, only 10 out of 1000 rows need to be read if the rows are read in the required order. Because of this, the optimizer rechecks if range access can be used on the first table if there is a LIMIT clause (with options set that almost always favour range access over table scan). Unfortunately, the range optimizer was allowed to pick any index, not only those that provided the necessary ordering. In the example above, range access on a very inefficient index was chosen. We ended up with an inefficient access method and no query short-cut after 10 rows because the index does not provide the right ordering. In MySQL 5.6.10, the optimizer still reconsiders if range access can be used for queries with LIMIT. The difference is that only indexes that provide the requested ordering are considered.

Performance implications
Since the bug has been fixed in MySQL 5.6.10, range access will no longer be used for the query above. It would be easy to insert a lot of rows in those two tables and show a massive performance improvement, but I find it more interesting to show the effect it has on DBT-3.

The following results are from DBT-3 query 3 with a scale factor of 10 (InnoDB tables and indexes total about 23 GB) stored on HDD. The query was run 10 times for warm-up. The average response time of the next 10 executions are shown in the charts below:

Ohh... and keep in mind that this improvement is in addition to the huge improvements already reported by Øystein for DBT-3 in MySQL 5.6.5. For disk-bound workloads, MySQL 5.6 is now down to about 1% of the MySQL 5.5 response time for DBT-3 query 3.