Tuesday, November 15, 2022

Bad Optimizer Plan on Queries Combining WHERE, ORDER BY and LIMIT

Sometimes, the MySQL Optimizer chooses a wrong plan, and a query that should execute in less than 0.1 second ends-up running for 12 minutes !  This is not a new problem: bugs about this can be traced back to 2014, and a blog post on the subject dates of 2015.  But even if this is old news, because this problem recently came to my attention, it is a problem worth writing on.

This is an improved version of a post published on the Percona Community Blog in 2019 (MySQL Optimizer: Naughty Aberration on Queries Combining WHERE, ORDER BY and LIMIT).  In my day-to-day work, I regularly find myself linking to this post, wishing a few things would be explained differently with more details.  So this is the improved post, with a change log and wish list below.

  • 2022-11-15: repost, adding the section on instability, giving more details about the Late Row Lookup trick, adding the new index with ICP solution and the IGNORE INDEX trick, mentioning Jeremy Cole's work and the new optimizer flag, and doing other cosmetic changes not worth listing in detail;
  • TODO: simplify the example query and table, and provide dbdeployer examples of the problem.

A surprising behavior of the problem described in this post is it instability.  Even if everything has been running smoothly for some time, most queries being fast and resource consumption being normal, things can change for the worse in an instant !  For no apparent reasons, the queries suddenly take longer to execute and what was a well-behaving MySQL instance becomes very slow with CPU or storage saturation.  This is because query plans are sensitive to table statistics, and statistics change over time, which might tip things in the wrong direction.  Moreover, a primary failover, or a planned switchover (what Vitess calls a reparent), can also trigger the performance degradations of bad plans because the statistics on the new primary are not the same as on the old primary.  Executing another switchover / reparent might temporarily restore good performances, but the bad plans would still be lingering, ready to resurface.  Problems that disappear by magic have a tendency to reappear by magic, so let's fully understand the subject and explore solutions.

The MySQL Optimizer

Before looking at the problematic query, we have to say a few words about the optimizer.  The Query Optimizer is the part of query execution that chooses the query plan.  A Query Execution Plan is the way a database chooses to run a specific query.  It includes index choices, join types, table query order, temporary table usage, sorting type, ...  The execution plan for a specific query can be obtained using the EXPLAIN command.

A Case in Question

The table being queried is the following:

mysql> SHOW CREATE TABLE _test_jfg_201907\G
*************************** 1. row ***************************
       Table: _test_jfg_201907
Create Table: CREATE TABLE `_test_jfg_201907` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `str1` varchar(150) DEFAULT NULL,
  `id1` int(10) unsigned NOT NULL,
  `id2` bigint(20) unsigned DEFAULT NULL,
  `str2` varchar(255) DEFAULT NULL,
[...many more id and str fields...]
  `create_datetime` datetime NOT NULL,
  `update_datetime` datetime DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `key1` (`id1`,`id2`)
) ENGINE=InnoDB AUTO_INCREMENT=_a_big_number_ DEFAULT CHARSET=utf8
1 row in set (0.00 sec)

And this is not a small table (it is not very big either though):

# ls -lh _test_jfg_201907.ibd 
-rw-r----- 1 mysql mysql 11G Jul 23 13:21 _test_jfg_201907.ibd

The problematic query, with running PAGER cat > /dev/null before for hiding the result, is the following:

mysql> SELECT * FROM _test_jfg_201907
  WHERE id1 = @v AND id2 IS NOT NULL
  ORDER BY id DESC LIMIT 20;
20 rows in set (27.22 sec)

Hum, the query takes a long time to execute (27.22 sec).  A faster execution is expected because of the index on id1,id2.  Let's check the query plan:

mysql> EXPLAIN SELECT * FROM _test_jfg_201907
  WHERE id1 = @v AND id2 IS NOT NULL
  ORDER BY id DESC LIMIT 20\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: _test_jfg_201907
   partitions: NULL
         type: index
possible_keys: key1
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 13000
     filtered: 0.15
        Extra: Using where
1 row in set, 1 warning (0.00 sec)

What: the query is not using the index key1 !  It is scanning the table (key: PRIMARY in above), how can this be ?  The short explanation is that the optimizer thinks — or should I say hopes — that scanning the table, already sorted by id, will find the limited rows quickly enough, which does not need sorting.  So by trying to avoid a sort, the optimizer ends-up loosing time scanning the table.

Some Solutions

The first solution for avoiding a scan of the table is to hint MySQL to use the key1 index as shown below.  With this, the query is almost instant, but it is not my favorite solution because it fails if the index is dropped or if its name is changed.

mysql> SELECT * FROM _test_jfg_201907 USE INDEX (key1)
  WHERE id1 = @v AND id2 IS NOT NULL
  ORDER BY id DESC LIMIT 20;
20 rows in set (0.00 sec)

A more elegant, but still very hack-ish solution, is to prevent the optimizer from using an index for sorting.  This can be achieved with the modified ORDER BY clause below (thanks to Shlomi Noach for suggesting this solution).  This was my preferred solution at the time of the original post, but I found a better one which I added below (IGNORE INDEX).

mysql> SELECT * FROM _test_jfg_201907
  WHERE id1 = @v AND id2 IS NOT NULL
  ORDER BY (id+0) DESC LIMIT 20;
20 rows in set (0.00 sec)

Another solution is to use a variation on the Late Row Lookup trick (thanks to my colleague Michal Skrzypecki for bringing this to my attention).  This trick forces the optimizer to choose the good plan because the query is modified for making the plan explicit.  This is an elegant hack, but as it makes the query more complicated, and at the time of the original post, I preferred other solutions.  But I changed my mind since then, mostly because I understand ICP better...

mysql> SELECT y.* FROM (
  SELECT id FROM _test_jfg_201907
    WHERE id1 = @v AND id2 IS NOT NULL
    ORDER BY id DESC LIMIT 20) x
  JOIN _test_jfg_201907 y ON x.id = y.id
  ORDER BY y.id DESC;
20 rows in set (0.00 sec)

Something I did not realize at the time of the original post is that rewriting the query like above avoids doing too many Primary Key lookups.  When using the index key1, MySQL fetches all rows matching the where clause, doing as many Primary Key lookups as there are matching rows, sorts by id, and then returns the 20 rows of the LIMIT discarding the unused rows.  With a more complex query, the Late Row Lookup trick only do as many Primary Key lookups as needed, 20 in this case.  So with this query and table structure, using this trick is the best optimization I know, which makes it my new favorite solution, but only when adding an index cannot be done.

And this brings us to a solution that I did not have in the original post: adding an index on id1,id,id2.  This index allows serving the query more efficiently than with the Late Rows Lookup trick because it does not need a sort (the ORDER BY id being served by the second column of this new index, after serving the equality on id1 with the first column).  So with this index, MySQL potentially scans fewer rows (once MySQL has 20 rows matching the where clause, no more rows are scanned), all this without doing extra Primary Key lookups because of Index Condition Pushdown (I give more details about ICP in my post Rows Examined not Trustworthy because of ICP).

Sticking with the index present on the table, another solution not in the original post is to prevent using the bad plan by adding a IGNORE INDEX (PRIMARY) hint to the query like below.  This is the solution I recommend when the complexity introduced by the Late Row Lookup trick is unwelcome, and adding an index cannot be done.

mysql> SELECT * FROM _test_jfg_201907 IGNORE INDEX (PRIMARY)
  WHERE id1 = @v AND id2 IS NOT NULL
  ORDER BY id DESC LIMIT 20;
20 rows in set (0.00 sec)

The Ideal Solution

The ideal solution would be to fix the bugs below (I claim Bug#74602 is not fixed even if it is marked as such in the bug system, but I will not make too much noise about this as Bug#78612 also raises attention on this problem):

A Good Workaround

Even if the bugs above are not fixed, a good workaround has been provided by Jeremy Cole since my original post.  Jeremy submitted a patch in Bug#97001 which allows telling the optimizer to not prefer an ordering index, and Oracle accepted the patch.  The good behavior, avoiding the bad plan, can be achieved by setting the flag prefer_ordering_index to OFF (default ON) in the optimizer switch.  Jeremy also describes this work in his post Reconsidering access paths for index ordering… a dangerous optimization… and a fix!.


One last thing before ending this post: I only gave a short explanation about the reason for the bad choice by the optimizer.  A longer explanation has already been given by Domas Mituzas in 2015, so I am referring you to his post for more details: on ORDER BY optimization.

And another post has been published by Mydbaops in 2020 on the same subject, so if you want to have other examples of this problem, you can read Row scanned equals to 1, Is the query is [sic] optimally tuned ?.

No comments:

Post a Comment