Wednesday, February 13, 2013

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.

6 comments:

  1. Replies
    1. 2 CPUs with 4 cores each (Intel(R) Xeon(R) CPU E5450 @ 3.00GHz)
      48GB RAM
      Hitachi H101414SCSUN146G (146GB, 10K RPM) HDD

      But keep in mind that the queries in DBT-3 are run back-to-back, so for this test there were probably 7 almost idle cores.

      Delete
    2. Jorgen,

      I executed query 3 for DBT3 SF10 on both mysq 5.6.9 and 5.6.10 on
      cold cache. I got approximately the same time for both releases.

      What is the earliest revision where the bug was fixed?

      Regards,
      Igor.

      Delete
    3. MySQL 5.6.10. Did you use InnoDB with persistent statistics? You should see a plan change from range:i_o_orderdate to table scan for table order.

      Delete
  2. Jorgen,

    It would be good if you could tell us:
    1. What exactly Q3 from DBT3 SF10 you executed,
    2. On what two versions/revisions of mysql 5.6 you run it to get
    the performance improvement of 6x.

    So far all my attempts to catch this improvement on mysql 5.6.10 using innodb persistent statistics were unsuccessful.

    Regards,
    Igor.

    ReplyDelete
  3. Hi again Igor,

    The query is

    select
    l_orderkey,
    sum(l_extendedprice * (1 - l_discount)) as revenue,
    o_orderdate,
    o_shippriority
    from
    customer,
    orders,
    lineitem
    where
    c_mktsegment = 'BUILDING'
    and c_custkey = o_custkey
    and l_orderkey = o_orderkey
    and o_orderdate < date '1995-03-15'
    and l_shipdate > date '1995-03-15'
    group by
    l_orderkey,
    o_orderdate,
    o_shippriority
    order by
    revenue desc,
    o_orderdate
    limit 10

    The compared MySQL versions are 5.6.9 and 5.6.10 as they were released. I don't know what the issue is in your case but the change comes straight out of the box on our server. Do you get this change for EXPLAIN? Otherwise I suspect you have an issue with statistics.

    id select_type table type possible_keys key key_len ref rows Extra
    -1 SIMPLE orders range PRIMARY,i_o_orderdate,i_o_custkey i_o_orderdate 4 NULL 7500000 Using index condition; Using where; Using MRR; Using temporary; Using filesort
    +1 SIMPLE orders ALL PRIMARY,i_o_orderdate,i_o_custkey NULL NULL NULL 15000000 Using where; Using temporary; Using filesort
    1 SIMPLE customer eq_ref PRIMARY PRIMARY 4 dbt3.orders.o_custkey 1 Using where
    1 SIMPLE lineitem ref PRIMARY,i_l_shipdate,i_l_orderkey,i_l_orderkey_quantity PRIMARY 4 dbt3.orders.o_orderkey 1 Using where

    ReplyDelete