Thursday, February 1, 2018

Speaking at FOSDEM

I will be speaking at FOSDEM the coming Sunday (February 4) on Histogram support in MySQL 8.0. If you are at FOSDEM, and want to learn about how you can use histograms to improve your query execution plans, visit the MySQL and Friends devroom at 11:10.

Also, please, checkout the entire program for the MySQL devroom.  It is full of interesting talks.

Friday, January 26, 2018

Query Optimizer Takes Data Buffering into Account

Last month I published a blog post at mysqlserverteam.com about how the Query Optimizer in MySQL 8.0 takes advantage of that InnoDB provides buffer estimates per table and index. In that blog post I showed how we got different query plans for Query 8 of the DBT-3 benchmark depending on whether the data was cached InnoDB's buffer pool or not.

In MySQL 5.6, we got a query plan that was well suited for a disk-bound scenario, while MySQL 5.7 switched to a query plan that reduces the execution time by 90% when all data is in memory. However, that came at the expense of longer execution times when data had to be read from disk. In MySQL 8.0 you get the best of both worlds. One query plan will be used when all data is in memory, and another plan will be used when most data need to be fetched from disk.

DBT-3 Query 21

I earlier blogged about another DBT-3 query, Query 21. This query showed a performance regression from MySQL 5.6 to MySQL 5.7 because the query optimizer overestimated the filtering effect of the WHERE clause. In that blog post, I promised that this can be avoided in MySQL 8.0 since you can create histograms to improve the filtering estimates. It turns out that the problem is avoided even without histograms.

In MySQL 5.7 we got this query plan for Query 21:

As discussed in the previous blog post, in MySQL 5.7, the optimizer chooses to start with table orders because it overestimates the filtering on this table. In MySQL 8.0 we still get the above query plan when all the data needs to be read from disk. However, if all data is in memory we get the following query plan:

As you can see from the diagram, the join order has been reversed. Using this new query plan reduces the execution time by 85% when all data is in memory. However, since this plan uses secondary indexes for two of the tables, it is not a good plan when most data has to be read from disk. In fact, if the optimizer had picked this plan in a disk-bound scenario, the query would have been 2.5 times slower than with the plan from 5.7. Hence, by taking into account whether data is in memory or needs to be read from disk, the optimizer is able to find a good plan for Query 21 in both scenarios.

Caveat

One thing to be aware of with this new optimizer behavior, is that running EXPLAIN on a query after it was executed, will not necessarily show the query plan that was used during execution. The previous execution of the query may have changed the content of the buffer pool. Hence, the optimizer may pick a different query plan for the next execution of the query.

Friday, November 24, 2017

Going Beyond Tabular EXPLAIN

A while ago, Lukas Eder posted a very interesting article on query optimizations that do not depend on the cost model. We often call such optimizations query transformations since they can be applied by rewriting the query.

In his blog post, Lukas investigated how different database systems handle different opportunities for query transformations. For MySQL, he complained that in some cases, the output from EXPLAIN is not sufficient to tell what is going on. However, as I will show in this blog post, there are other ways to get the information that he was looking for.

The EXPLAIN Warning

What may easily be overlooked when executing EXPLAIN for a query, is that it literally comes with a warning. This warning shows the query after the query transformations have been applied. Let's look at the query Lukas used to explore Transitive Closure:

SELECT first_name, last_name, film_id
FROM actor a
JOIN film_actor fa ON a.actor_id = fa.actor_id
WHERE a.actor_id = 1;

If we run EXPLAIN for this query, and display the associated warning, we see:

mysql> EXPLAIN SELECT first_name, last_name, film_id FROM actor a JOIN film_actor fa ON a.actor_id = fa.actor_id WHERE a.actor_id = 1;
+----+-------------+-------+------------+-------+---------------+---------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type  | possible_keys | key     | key_len | ref   | rows | filtered | Extra       |
+----+-------------+-------+------------+-------+---------------+---------+---------+-------+------+----------+-------------+
|  1 | SIMPLE      | a     | NULL       | const | PRIMARY       | PRIMARY | 2       | const |    1 |   100.00 | NULL        |
|  1 | SIMPLE      | fa    | NULL       | ref   | PRIMARY       | PRIMARY | 2       | const |   19 |   100.00 | Using index |
+----+-------------+-------+------------+-------+---------------+---------+---------+-------+------+----------+-------------+
2 rows in set, 1 warning (0,00 sec)

mysql> show warnings;
+-------+------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Level | Code | Message                                                                                                                                                                                                       |
+-------+------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Note  | 1003 | /* select#1 */ select 'PENELOPE' AS `first_name`,'GUINESS' AS `last_name`,`sakila`.`fa`.`film_id` AS `film_id` from `sakila`.`actor` `a` join `sakila`.`film_actor` `fa` where (`sakila`.`fa`.`actor_id` = 1) |
+-------+------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0,00 sec)

If you scroll to the right, you will see that the warning contains: `sakila`.`fa`.`actor_id` = 1. In other words, the predicate actor_id = 1 has been applied to the film_actor table because of transitive closure.

The above warning message also illustrates another aspect of MySQL query optimization. Since the query specifies the value for the primary key of the actor table, the primary key look-up will be done in the optimizer phase. Hence, the warning shows that columns from the actor table have been replaced by the column values for the requested row.

Structured EXPLAIN

MySQL 5.6 introduced Structured EXPLAIN. Its output describes the query plan in JSON format. This output contains additional information compared to traditional EXPLAIN. For example, while the tabular EXPLAIN only says "Using where" when a condition is applied when reading a table, the JSON output will display the actual condition. Let's look at the output for the first example on Removing “Silly” Predicates:

mysql> EXPLAIN FORMAT=JSON SELECT * FROM film WHERE release_year = release_year;
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| {
  "query_block": {
    "select_id": 1,
    "cost_info": {
      "query_cost": "212.00"
    },
    "table": {
      "table_name": "film",
      "access_type": "ALL",
      "rows_examined_per_scan": 1000,
      "rows_produced_per_join": 100,
      "filtered": "10.00",
      "cost_info": {
        "read_cost": "192.00",
        "eval_cost": "20.00",
        "prefix_cost": "212.00",
        "data_read_per_join": "78K"
      },
      "used_columns": [
        "film_id",
        "title",
        "description",
        "release_year",
        "language_id",
        "original_language_id",
        "rental_duration",
        "rental_rate",
        "length",
        "replacement_cost",
        "rating",
        "special_features",
        "last_update"
      ],
      "attached_condition": "(`sakila`.`film`.`release_year` = `sakila`.`film`.`release_year`)"
    }
  }
} |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

The value for "attached_condition" shows that MySQL does not simplify the condition release_year = release_year to release_year IS NOT NULL. So Lukas is right in his educated guess that MySQL does not optimize this. However, if we look at a similar silly predicate on a NOT NULL column, we see that such predicates are eliminated by MySQL:

mysql> EXPLAIN FORMAT=JSON SELECT * FROM film WHERE film_id = film_id;
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| {
  "query_block": {
    "select_id": 1,
    "cost_info": {
      "query_cost": "212.00"
    },
    "table": {
      "table_name": "film",
      "access_type": "ALL",
      "rows_examined_per_scan": 1000,
      "rows_produced_per_join": 1000,
      "filtered": "100.00",
      "cost_info": {
        "read_cost": "12.00",
        "eval_cost": "200.00",
        "prefix_cost": "212.00",
        "data_read_per_join": "781K"
      },
      "used_columns": [
        "film_id",
        "title",
        "description",
        "release_year",
        "language_id",
        "original_language_id",
        "rental_duration",
        "rental_rate",
        "length",
        "replacement_cost",
        "rating",
        "special_features",
        "last_update"
      ]
    }
  }
} |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

In this case, there is no "attached_condition" in the JSON output. In other words, the silly predicate has been removed.

Optimizer Trace

Predicate Merging investigates whether the optimizer will merge two predicates on the same column. There are actually two different aspects here:

  1. Whether predicates are merged and evaluated as a single predicate
  2. Whether key ranges as specified by the query are merged when setting up index range scans
The latter is the most important since it ensures that not more rows than necessary are accessed. Lukas concludes that MySQL does predicate merging based on the estimated number of rows that tabular EXPLAIN shows:
mysql> EXPLAIN SELECT * 
    -> FROM actor
    -> WHERE actor_id IN (2, 3, 4)
    -> AND actor_id IN (1, 2, 3);
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | actor | NULL       | range | PRIMARY       | PRIMARY | 2       | NULL |    2 |   100.00 | Using where |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0,00 sec)
Here EXPLAIN shows that the estimated number of rows to be read is 2, and this fits with how many rows satisfy the merged predicates.

If we look at the output from structured EXPLAIN, we get a different picture:

mysql> EXPLAIN FORMAT=JSON SELECT *  FROM actor WHERE actor_id IN (2, 3, 4) AND actor_id IN (1, 2, 3);
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| {
  "query_block": {
    "select_id": 1,
    "cost_info": {
      "query_cost": "2.81"
    },
    "table": {
      "table_name": "actor",
      "access_type": "range",
      "possible_keys": [
        "PRIMARY"
      ],
      "key": "PRIMARY",
      "used_key_parts": [
        "actor_id"
      ],
      "key_length": "2",
      "rows_examined_per_scan": 2,
      "rows_produced_per_join": 2,
      "filtered": "100.00",
      "cost_info": {
        "read_cost": "2.41",
        "eval_cost": "0.40",
        "prefix_cost": "2.81",
        "data_read_per_join": "560"
      },
      "used_columns": [
        "actor_id",
        "first_name",
        "last_name",
        "last_update"
      ],
      "attached_condition": "((`sakila`.`actor`.`actor_id` in (2,3,4)) and (`sakila`.`actor`.`actor_id` in (1,2,3)))"
    }
  }
} |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
As you can see from "attached_condition", the predicates are not actually merged. It is only the key ranges that are merged. Structured EXPLAIN does not show what key ranges are used for the index range scan. However, we can use Optimizer Trace to find this information. (See instructions on how to obtain the optimizer trace.) The optimizer trace for the above query contains this part:
                  "chosen_range_access_summary": {
                    "range_access_plan": {
                      "type": "range_scan",
                      "index": "PRIMARY",
                      "rows": 2,
                      "ranges": [
                        "2 <= actor_id <= 2",
                        "3 <= actor_id <= 3"
                      ]
                    },
                    "rows_for_plan": 2,
                    "cost_for_plan": 2.41,
                    "chosen": true
                  }
This shows that the range optimizer has actually set up two ranges here; one for actor_id = 2 and one for actor_id = 3. (In other words, the range optimizer does not seem to take into account that actor_id is an integer column.)

It is the same story for Lukas' other query investigating predicate merging. That query specifies two overlapping key ranges:

SELECT *
FROM film
WHERE film_id BETWEEN 1 AND 100
AND film_id BETWEEN 99 AND 200;

Also in this case structured EXPLAIN shows that predicates are not merged, while optimizer trace shows that the key ranges are merged:

                  "chosen_range_access_summary": {
                    "range_access_plan": {
                      "type": "range_scan",
                      "index": "PRIMARY",
                      "rows": 2,
                      "ranges": [
                        "99 <= film_id <= 100"
                      ]
                    },
                    "rows_for_plan": 2,
                    "cost_for_plan": 2.41,
                    "chosen": true
                  }
Since this query has range predicates instead of equality predicates, MySQL will here set up a single range scan from 99 to 100.

Concluding Remarks

I have in this blog post shown some examples of how you can get additional information about a query plan, beyond what you can see in the output of tabular EXPLAIN. There is a lot of other information that you can deduct from looking at the EXPLAIN Warning, Structured EXPLAIN, or Optimizer Trace than what I have discussed here. That can be the topic for later blog posts.

Friday, April 21, 2017

Speaking at Percona Live

Percona Live is next week, and on Monday morning I will give a tutorial on "How to Analyze and Tune MySQL Queries for Better Performance".  I hope to see some of you there!  

For those of you that are not able to come, I recommend my on demand webinar on the same topic.  I will also give talks about query tuning at the upcoming Oracle MySQL Innovation Days to be held in the Bay Area (April 28) and in the Boston Area (May 2).

I would also like to recommend the following MySQL optimizer related talks at Percona Live:

Wednesday, April 19, 2017

MySQL 8.0: Improved performance with CTE

Last week I published a blog post in the MySQL Server Blog where I showed how the execution time of a query was reduced by 50% by using a Common Table Expression (CTE) instead of a view.

In the coming weeks, there will be several opportunities to attend a presentation on CTE and another SQL feature that will arrive in MySQL 8.0, Window Functions.  This presentation is part of the Oracle MySQL Innovation Day that will be held both in the Bay Area (April 28) and in the Boston Area (May 2).

I will also give the presentation at the Boston MySQL Meetup on May 1st.

I hope to see some of you there!


 

Friday, March 24, 2017

What to Do When the MySQL Optimizer Overestimates the Condition Filtering Effect

In my previous blog post, I showed an example of how the MySQL Optimizer found a better join order by taking into account the filtering effects of conditions. I also explained that for non-indexed columns the filtering estimate is just a guess, and that there is a risk for non-optimal query plans if the guess is off.

We have received a few bug reports on performance regressions when upgrading from 5.6 to 5.7 that are caused by the optimizer overestimating the filtering effect. In most cases, the cause of the regression is inaccurate filtering estimates for equality conditions on non-indexed columns with low cardinality. In this blog post, I will discuss three ways to handle such regressions:

  1. Create an index
  2. Use an optimizer hint to change the join order
  3. Disable condition filtering
First, I will show an example where overestimating the condition filtering effects gives a non-optimal query plan.

Example: DBT-3 Query 21

We will look at Query 21 in the DBT-3 benchmark:

SELECT s_name, COUNT(*) AS numwait
FROM supplier
JOIN lineitem l1 ON s_suppkey = l1.l_suppkey
JOIN orders ON o_orderkey = l1.l_orderkey
JOIN nation ON s_nationkey = n_nationkey
WHERE o_orderstatus = 'F'
  AND l1.l_receiptdate > l1.l_commitdate
  AND EXISTS (SELECT * FROM lineitem l2
              WHERE l2.l_orderkey = l1.l_orderkey
                AND l2.l_suppkey <> l1.l_suppkey)
  AND NOT EXISTS (SELECT * FROM lineitem l3
                  WHERE l3.l_orderkey = l1.l_orderkey
                    AND l3.l_suppkey <> l1.l_suppkey
                    AND l3.l_receiptdate > l3.l_commitdate)
  AND n_name = 'JAPAN'
GROUP BY s_name ORDER BY numwait DESC, s_name LIMIT 100;

Query 21 is called Suppliers Who Kept Orders Waiting Query. In MySQL 5.7, Visual EXPLAIN shows the following query plan for Query 21:

The four tables of the join are joined from left-to-right, starting with a full table scan of the orders table. There are also two dependent subqueries on the lineitem table that will be executed for each row of the outer lineitem table. The execution time for this query plan is almost 25 seconds on a scale factor 1 DBT-3 database. This is more than ten times as long as the query plan used in MySQL 5.6!

The filtered column of tabular EXPLAIN shows the optimizer's estimates for the condition filter effects (some of the columns have been removed to save space):

id select_type table type key rows filtered Extra
1 PRIMARY orders ALL NULL 1500000 10.00 Using where; Using temporary; Using filesort
1 PRIMARY l1 ref PRIMARY 4 33.33 Using where
1 PRIMARY supplier eq_ref PRIMARY 1 100.00 Using index condition
1 PRIMARY nation ALL NULL 25 4.00 Using where; Using join buffer (Block Nested Loop)
3 DEPENDENT SUBQUERY l3 ref PRIMARY 4 30.00 Using where
2 DEPENDENT SUBQUERY l2 ref PRIMARY 4 90.00 Using where

This shows that the optimizer assumes that the condition o_orderstatus = 'F' is satisfied by 10% of the rows in the orders table. Hence, the optimizer thinks that it will be possible to filter out a lot of orders early by starting with the orders table. However, the truth is that almost 50% of the rows have the requested order status. In other words, by overestimating the filtering effect for orders, query plans that start with the orders table will appear to be less costly than is actually the case.

We will now look at how we can influence the optimizer to pick a better query plan for this query.

Option 1: Create an Index

As mentioned, the optimizer does not have any statistics on non-indexed columns. So one way to improve the optimizer's precision is to create an index on the column. For Query 21, since the filtering estimate for o_orderstatus is way off, we can try to see what happens if we create an index on this column:

CREATE INDEX i_o_orderstatus ON orders(o_orderstatus);
With this index, the query plan has changed:
id select_type table type key rows filtered Extra
1 PRIMARY nation ALL NULL 25 10.00 Using where; Using temporary; Using filesort
1 PRIMARY supplier ref i_s_nationkey 400 100.00 NULL
1 PRIMARY l1 ref i_l_suppkey 600 33.33 Using where
1 PRIMARY orders eq_ref PRIMARY 1 50.00 Using where
3 DEPENDENT SUBQUERY l3 ref PRIMARY 4 30.00 Using where
2 DEPENDENT SUBQUERY l2 ref PRIMARY 4 90.00 Using where

We see from the EXPLAIN output that the estimated filtering effect for orders is now 50%. Given that, the optimizer prefers a different join order, starting with the nation table. This is the same join order as one got in MySQL 5.6, and the execution time with this plan is 2.5 seconds. Instead of accessing 50% of all orders, the query will now just access orders for suppliers in Japan. However, this improvement comes at the cost of having to maintain an index that will probably never be used!

Looking at Query 21, there is also an equality condition on another column without an index; n_name of the nation table. For this column, 10% is actually a too high estimate. There are 25 nations in the table. Hence, the correct estimate should be 4%. What if we, instead, create an index on this column?

DROP INDEX i_o_orderstatus ON orders;
CREATE INDEX i_n_name ON nation(n_name);
Then we get this query plan:
id select_type table type key rows filtered Extra
1 PRIMARY nation ref i_n_name 1 100.00 Using index; Using temporary; Using filesort
1 PRIMARY supplier ref i_s_nationkey 400 100.00 NULL
1 PRIMARY l1 ref i_l_suppkey 600 33.33 Using where
1 PRIMARY orders eq_ref PRIMARY 1 10.00 Using where
3 DEPENDENT SUBQUERY l3 ref PRIMARY 4 30.00 Using where
2 DEPENDENT SUBQUERY l2 ref PRIMARY 4 90.00 Using where

In this case, our new index is actually used! Since scanning a table with 25 rows takes a neglible part of the total execution time, the savings for Query 21 are insignificant, but there might be other queries where such an index could be more useful.

Option 2: Join Order Hint

Instead of trying to improve statistics to get a better query plan, we can use hints to influence the optimizer's choice of query plan. The STRAIGHT_JOIN hint can be used to change the join order. It comes in two flavors:

We will use the second variant and specify that nation should be processed before orders:
SELECT s_name, COUNT(*) AS numwait
FROM supplier
JOIN lineitem l1 ON s_suppkey = l1.l_suppkey
JOIN nation ON s_nationkey = n_nationkey
STRAIGHT_JOIN orders ON o_orderkey = l1.l_orderkey
WHERE o_orderstatus = 'F'
  AND l1.l_receiptdate > l1.l_commitdate
  AND EXISTS (SELECT * FROM lineitem l2
              WHERE l2.l_orderkey = l1.l_orderkey
                AND l2.l_suppkey <> l1.l_suppkey)
  AND NOT EXISTS (SELECT * FROM lineitem l3
                  WHERE l3.l_orderkey = l1.l_orderkey
                    AND l3.l_suppkey <> l1.l_suppkey
                    AND l3.l_receiptdate > l3.l_commitdate)
  AND n_name = 'JAPAN'
GROUP BY s_name ORDER BY numwait DESC, s_name LIMIT 100;
This way we force the optimizer to pick a query plan where nation comes before orders, and the resulting query plan is the "good one":
id select_type table type key rows filtered Extra
1 PRIMARY nation ALL NULL 25 10.00 Using where; Using temporary; Using filesort
1 PRIMARY supplier ref i_s_nationkey 400 100.00 NULL
1 PRIMARY l1 ref i_l_suppkey 600 33.33 Using where
1 PRIMARY orders eq_ref PRIMARY 1 10.00 Using where
3 DEPENDENT SUBQUERY l3 ref PRIMARY 4 30.00 Using where
2 DEPENDENT SUBQUERY l2 ref PRIMARY 4 90.00 Using where

In order to user STRAIGHT_JOIN we had to rearrange the tables in the FROM clause. This is a bit cumbersome, and to avoid this, we have in MySQL 8.0 introduced new join order hints that uses the new optimizer hint syntax. Using this syntax, we can add hints right after SELECT and avoid editing the rest of the query. In the case of Query 21, we can add hints like

SELECT /*+ JOIN_PREFIX(nation) */ …
or
SELECT /*+ JOIN_ORDER(nation, orders) */ …
to achieve the desired query plan.

Option 3: Disable Condition Filtering

Many optimizer features can be disabled by setting the optimizer_switch variable. The following statement will make the optimizer not use condition filtering estimates:
SET optimizer_switch='condition_fanout_filter=off';
Looking that the query plan as presented by EXPLAIN, we see that filtering is no longer taken into account:
id select_type table type key rows filtered Extra
1 PRIMARY nation ALL NULL 25 100.00 Using where; Using temporary; Using filesort
1 PRIMARY supplier ref i_s_nationkey 400 100.00 NULL
1 PRIMARY l1 ref i_l_suppkey 600 100.00 Using where
1 PRIMARY orders eq_ref PRIMARY 1 100.00 Using where
3 DEPENDENT SUBQUERY l3 ref PRIMARY 4 100.00 Using where
2 DEPENDENT SUBQUERY l2 ref PRIMARY 4 100.00 Using where

Note that you can set optimizer_switch at session level. Hence, it is possible to disable condition filtering for individual queries. However, this requires extra round-trips to the server to set optimizer_switch before and after the execution of the query.

(Option 4: Wait for Histograms)

We are working to improve the statistics available to the optimizer by introducing histograms. A histogram provides more detailed information about the data distribution in a table column. With histograms, the optimizer will be able to estimate pretty accurately the filtering effects also for conditions on non-indexed columns. Until then, you will have to resort to one of options presented above to improve bad query plans caused by inaccurate filtering estimates.

Friday, March 17, 2017

MySQL 5.7: Improved JOIN Order by Taking Condition Filter Effect into Account

One of the major challenges of query optimizers is to correctly estimate how many rows qualify from each table of a join. If the estimates are wrong, the optimizer may choose a non-optimal join order.

Before MySQL 5.7, the estimated number of rows from a table only took into account the conditions from the WHERE clause that were used to set up the access method (e.g., the size of an index range scan). This often led to row estimates that were far too high, resulting in very wrong cost estimates for join plans. To improve this issue, MySQL 5.7 introduced a cost model that considered the entire WHERE condition when estimating the number of qualifying rows from each table. This model estimates the filtering effect of the table’s conditions.

As shown in the above figure, the condition filter effect will reduce the estimated number of rows from tx that will lead to an index look-up on tx+1. For more details on how condition filtering works, see two earlier blog posts on this topic: part1, part2.

Taking condition filtering into account, the join optimizer will in many cases be able to find a more optimal join order. However, there are cases where the optimizer will overestimate the filtering effect and choose a non-optimal query plan. In this blog post, I will show an example of a query that benefits from condition filtering, and in a follow-up blog post I will discuss what could be done if condition filtering does not have the desired effect.

Example: DBT-3 Query 8

To show the benefits of condition filtering, we will look at Query 8 in the DBT-3 benchmark:

SELECT o_year,
       SUM(CASE WHEN nation = 'FRANCE' THEN volume ELSE 0 END) / SUM(volume) AS mkt_share
FROM (
    SELECT EXTRACT(YEAR FROM o_orderdate) AS o_year,
           l_extendedprice * (1 - l_discount) AS volume, n2.n_name AS nation
    FROM part
    JOIN lineitem ON p_partkey = l_partkey
    JOIN supplier ON s_suppkey = l_suppkey
    JOIN orders ON l_orderkey = o_orderkey
    JOIN customer ON o_custkey = c_custkey
    JOIN nation n1 ON c_nationkey = n1.n_nationkey
    JOIN region ON  n1.n_regionkey = r_regionkey   
    JOIN nation n2 ON s_nationkey = n2.n_nationkey
    WHERE r_name = 'EUROPE' AND o_orderdate BETWEEN '1995-01-01' AND '1996-12-31'
      AND p_type = 'PROMO BRUSHED STEEL'
) AS all_nations GROUP BY o_year ORDER BY o_year;

Query 8 is called National Market Share Query, and it finds the market share in Europe for French suppliers of a given part type. You do not need to understand this query in detail. The main point is that 8 tables are joined, and that it is important to find an efficient join order for the query to perform well.

In MySQL 5.6, Visual EXPLAIN shows the following query plan for Query 8:

Tables are joined from left-to-right, starting with a full table scan of the region table, doing index look-ups into all other tables, with the part table as the last table. The execution time for this query is around 6 seconds on a scale factor 1 DBT-3 database.

If we look at the WHERE clause of the query, we see that there is one condition with high selectivity: We are interested in just one particular of many possible part types. That the region should be Europe, and that the time period is restricted to two years, will still leave many candidate rows, so these conditions have low selectivity. In other words, a query plan that put the part table at the end is not optimal. If part was processed early, we would be able to filter out many rows, and the number of index look-ups into other tables could be significantly reduced.

In MySQL 5.7, the use of condition filtering estimates changes the query plan for Query 8, and the new query plan looks as follows:

As you see, part is now processed early. (We see that region is still processed first, but this is a small table with only 5 rows of which only one row matches its condition. Hence, it will not impact the fan-out of the join.) This new query plan takes 0.5 seconds to execute. In other words, execution time is reduced by 92% by changing the join order! The main saving is that, instead of going through all orders for customers in Europe, one will only look at orders of parts of a given type.

(The observant reader will have noticed another difference between the Visual EXPLAIN diagrams: The box around the tables is no longer present in the 5.7 diagram. If you look a Query 8, you notice that the many-table join is in a sub-query in the FROM clause; aka derived table. In MySQL 5.6 and earlier, the result of derived tables where materialized in a temporary table, before the main query was executed. The extra box in the 5.6 diagram, represents such a temporary table. In MySQL 5.7, derived tables will be merged into the outer query if possible, and the materialization of the derived table is avoided.)

To see the optimizer's estimates for condition filter effects, we can look at the filtered column of tabular EXPLAIN (some of the columns have been removed to save space):

id select_type table type key rows filtered Extra
1 SIMPLE region ALL NULL 5 20.00 Using where; Using temporary; Using filesort
1 SIMPLE part ALL NULL 200000 10.00 Using where; Using join buffer (Block Nested Loop)
1 SIMPLE lineitem ref i_l_partkey_suppkey 30 100.00 Using index condition
1 SIMPLE supplier eq_ref PRIMARY 1 100.00 Using where
1 SIMPLE n2 eq_ref PRIMARY 1 100.00 NULL
1 SIMPLE orders eq_ref PRIMARY 1 50.00 Using where
1 SIMPLE customer eq_ref PRIMARY 1 100.00 Using where
1 SIMPLE n1 eq_ref PRIMARY 1 20.00 Using where

We can see that there are 4 tables for which the optimizer assumes some filtering; region, part, orders, and n1 (nation). The optimizer has three sources for its estimates:

  1. Range estimates:

    For indexed columns, the range optimizer will ask the storage engine for an estimate as to how many rows are within a given range. This estimate will be pretty accurate. For our query, this is the case for the region and orders table. Europe is 1 out of 5 regions and the requested two year period contains 50% of the orders in the database.

  2. Index statistics:

    For indexed columns, MySQL also keep statistics on the average number of rows per value (records_per_key). This can be used to estimate the filtering effect of conditions that refers to columns of preceeding tables in the join order. For our query this is the case for n1. The query has two conditions involving n1, but the condition on n_nationkey is used for the index look-up and will not contribute to extra filtering. On the other hand, the condition on n_regionkey will provide some extra filtering, and since records_per_key tells that there are 5 distinct values for this column, the estimated filtering effect will be 20%.

    The assumption is that values are evenly distributed. If the distribution is skewed, the filtering estimate will be less accurate. Another cause of estimation errors is that index statistics are based on sampling, so it may not precisely reflect the actual distribution of values.

  3. Guesstimates:

    For non-indexed columns, MySQL does not have any statistics. The optimizer will then resort to heuristics. For equality conditions, the filtering effect is assumed to be 10%. The DBT-3 database does not have an index on part_type. Hence, the filtering effect for the part table will be set to 10%. This is actually a bit off since there are 150 different parts. However, in this case, just assuming that there is some filtering, made the optimizer choose a better plan.

Caveat

As shown in this blog post, taking condition filtering into account may give better query plans. However, as discussed, there is a risk that the filtering estimate are inaccurate, especially for conditions on non-indexed columns. Another cause of estimation errors is that it is assumed that columns are not correlated. Hence, when here are conditions on correlated columns, the optimizer will overestimate the filtering effect of those conditions.

We have got a few bug reports on performance regressions when upgrading from 5.6 to 5.7 that are caused by the optimizer overestimating the filtering effect. In most cases, this is because the query contains equality conditions on non-indexed columns with low cardinality, so the guesstimate of 10% is too optimistic. In my next blog post, I will discuss what can be done when this happens. We are also working on adding histograms to MySQL. Histograms will give a much better basis for estimating the filtering effects of conditions on non-indexed columns.