[#MDEV-24439] Major optimizer regression with ORDER BY PK + short LIMIT

[MDEV-24439] Major optimizer regression with ORDER BY PK + short LIMIT Created: 2020-12-18 Updated: 2023-12-05
Status:	Stalled
Project:	MariaDB Server
Component/s:	Optimizer
Affects Version/s:	10.2, 10.3, 10.4
Fix Version/s:	10.4

Type:

Bug

Priority:

Major

Reporter:

Jaime Crespo

Assignee:

Sergei Petrunia

Resolution:

Unresolved

Votes:

Labels:

filesort, optimizer, optimizer_trace, order-by-optimization

Environment:

Debian 10, RAID10 HW

Description

I am creating a database of Wikipedia images metadata to handle backups on my database of preference (MariaDB). The structure is a relatively common one "a single large table" plus some of its properties normalized to external, small tables. This is the structure of the relevant tables:

files.sql
db1133.eqiad.wmnet[mediabackups]> show create table files\G
************************* 1. row *************************
Table: files
Create Table: CREATE TABLE `files` (
`id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`wiki` int(10) unsigned NOT NULL,
`upload_name` varbinary(255) DEFAULT NULL,
`swift_container` int(10) unsigned DEFAULT NULL,
`swift_name` varbinary(270) DEFAULT NULL,
`file_type` tinyint(3) unsigned DEFAULT NULL,
`status` tinyint(3) unsigned DEFAULT NULL,
`sha1` varbinary(40) DEFAULT NULL,
`md5` varbinary(32) DEFAULT NULL,
`size` int(10) unsigned DEFAULT NULL,
`upload_timestamp` timestamp NOT NULL DEFAULT '0000-00-00 00:00:00',
`archived_timestamp` timestamp NULL DEFAULT NULL,
`deleted_timestamp` timestamp NULL DEFAULT NULL,
`backup_status` tinyint(3) unsigned DEFAULT 1,
PRIMARY KEY (`id`),
KEY `sha1` (`sha1`),
KEY `file_type` (`file_type`),
KEY `status` (`status`),
KEY `backup_status` (`backup_status`),
KEY `wiki` (`wiki`),
KEY `swift_container` (`swift_container`),
KEY `upload_name` (`upload_name`,`status`),
KEY `upload_timestamp` (`upload_timestamp`),
CONSTRAINT `files_ibfk_1` FOREIGN KEY (`file_type`) REFERENCES `file_types` (`id`),
CONSTRAINT `files_ibfk_2` FOREIGN KEY (`status`) REFERENCES `file_status` (`id`),
CONSTRAINT `files_ibfk_3` FOREIGN KEY (`wiki`) REFERENCES `wikis` (`id`),
CONSTRAINT `files_ibfk_4` FOREIGN KEY (`backup_status`) REFERENCES `backup_status` (`id`),
CONSTRAINT `files_ibfk_5` FOREIGN KEY (`swift_container`) REFERENCES `swift_containers` (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=4549852 DEFAULT CHARSET=binary
1 row in set (0.001 sec)

file_status.sql
db1133.eqiad.wmnet[mediabackups]> show create table file_status\G
************************* 1. row *************************
Table: file_status
Create Table: CREATE TABLE `file_status` (
`id` tinyint(3) unsigned NOT NULL AUTO_INCREMENT,
`status_name` varbinary(100) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=5 DEFAULT CHARSET=binary
1 row in set (0.001 sec)

db1133.eqiad.wmnet[mediabackups]> select * FROM file_status;
+----+--------------+
\| id \| status_name \|
+----+--------------+
\| 1 \| public \|
\| 2 \| archived \|
\| 3 \| deleted \|
\| 4 \| hard-deleted \|
+----+--------------+
4 rows in set (0.001 sec)

backup_status.sql
db1133.eqiad.wmnet[mediabackups]> show create table backup_status\G
************************* 1. row *************************
Table: backup_status
Create Table: CREATE TABLE `backup_status` (
`id` tinyint(3) unsigned NOT NULL,
`backup_status_name` varbinary(100) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=binary
1 row in set (0.000 sec)

db1133.eqiad.wmnet[mediabackups]> select * FROM backup_status;
+----+--------------------+
\| id \| backup_status_name \|
+----+--------------------+
\| 1 \| pending \|
\| 2 \| processing \|
\| 3 \| backedup \|
\| 4 \| error \|
+----+--------------------+
4 rows in set (0.001 sec)

wikis.sql
db1133.eqiad.wmnet[mediabackups]> show create table wikis\G
************************* 1. row *************************
Table: wikis
Create Table: CREATE TABLE `wikis` (
`id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`wiki_name` varbinary(255) DEFAULT NULL,
`type` tinyint(3) unsigned DEFAULT NULL,
PRIMARY KEY (`id`),
UNIQUE KEY `wiki_name` (`wiki_name`)
) ENGINE=InnoDB AUTO_INCREMENT=1206 DEFAULT CHARSET=binary
1 row in set (0.001 sec)

db1133.eqiad.wmnet[mediabackups]> select count(*) FROM wikis;
+----------+
\| count(*) \|
+----------+
\| 999 \|
+----------+
1 row in set (0.001 sec)

When I try to run a query with an ORDER BY, followed by a short limit, using the PRIMARY KEY, it preferes to scan the whole table and perform a filesort rather than using the index efectively to scan just ~10 rows:

query.sql
-- simple query, just denormalize the data so it is in "human" readable form
db1133.eqiad.wmnet[mediabackups]> SELECT wiki_name, upload_name, size, status_name, sha1, backup_status_name
FROM files JOIN file_status ON file_status.id = files.status
JOIN backup_status ON backup_status.id = files.backup_status
JOIN wikis ON wikis.id = files.wiki
ORDER BY files.id
LIMIT 10;

<---- waiting for minutes...

^CCtrl-C -- query killed. Continuing normally.
ERROR 1317 (70100): Query execution was interrupted

db1133.eqiad.wmnet[mediabackups]> EXPLAIN select wiki_name, upload_name, size, status_name, sha1, backup_status_name FROM files JOIN file_status ON file_status.id = files.status JOIN backup_status ON backup_status.id = files.backup_status JOIN wikis ON wikis.id = files.wiki ORDER BY files.id LIMIT 10\G
************************* 1. row *************************
id: 1
select_type: SIMPLE
table: files
type: ALL <--------------------------------------------------- ?????
possible_keys: status,backup_status,wiki
key: NULL
key_len: NULL
ref: NULL
rows: 4549851
Extra: Using where; Using temporary; Using filesort <------------------------- ??????
************************* 2. row *************************
id: 1
select_type: SIMPLE
table: wikis
type: eq_ref
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: mediabackups.files.wiki
rows: 1
Extra:
************************* 3. row *************************
id: 1
select_type: SIMPLE
table: backup_status
type: ALL
possible_keys: PRIMARY
key: NULL
key_len: NULL
ref: NULL
rows: 4
Extra: Using where; Using join buffer (flat, BNL join)
************************* 4. row *************************
id: 1
select_type: SIMPLE
table: file_status
type: eq_ref
possible_keys: PRIMARY
key: PRIMARY
key_len: 1
ref: mediabackups.files.status
rows: 1
Extra:
4 rows in set (0.001 sec)

This is a major regression because being able to select ranges in order is a top feature of a MySQL-type db, and has to be fast. Most of our web pages are just "list of items in order". I can see an issue with a secondary index among many, but refusing to use the primary key?

The table was analyzed and rebuilt, to the same results. Optimizer trace and more information is available at our web tracker: https://phabricator.wikimedia.org/P13595#74956

To check it was not something I was doing wrong, I checked the same query, after importing a copy of the database on Percona Server 8, and I got this:

percona_query.sql
db2102.codfw.wmnet[mediabackups]> explain select wiki_name, upload_name, size, status_name, sha1, backup_status_name FROM files JOIN file_status ON file_status.id = files.status JOIN backup_status ON backup_status.id = files.backup_status JOIN wikis ON wikis.id = files.wiki ORDER BY files.id LIMIT 10\G
************************* 1. row *************************
id: 1
select_type: SIMPLE
table: files
partitions: NULL
type: index
possible_keys: status,backup_status,wiki
key: PRIMARY <------------------------------------- preferred index
key_len: 4
ref: NULL
rows: 10
filtered: 100.00
Extra: Using where <------------------------------------ no filesort
************************* 2. row *************************
id: 1
select_type: SIMPLE
table: file_status
partitions: NULL
type: eq_ref
possible_keys: PRIMARY
key: PRIMARY
key_len: 1
ref: mediabackups.files.status
rows: 1
filtered: 100.00
Extra: NULL
************************* 3. row *************************
id: 1
select_type: SIMPLE
table: backup_status
partitions: NULL
type: eq_ref
possible_keys: PRIMARY
key: PRIMARY
key_len: 1
ref: mediabackups.files.backup_status
rows: 1
filtered: 100.00
Extra: NULL
************************* 4. row *************************
id: 1
select_type: SIMPLE
table: wikis
partitions: NULL
type: eq_ref
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: mediabackups.files.wiki
rows: 1
filtered: 100.00
Extra: NULL
4 rows in set, 1 warning (0.035 sec)

db2102.codfw.wmnet[mediabackups]> select wiki_name, upload_name, size, status_name, sha1, backup_status_name FROM files JOIN file_status ON file_status.id = files.status JOIN backup_status ON backup_status.id = files.backup_status JOIN wikis ON wikis.id = files.wiki ORDER BY files.id LIMIT 10;
+-----------+---------------------------------------------------------+--------+-------------+------------------------------------------+--------------------+
\| wiki_name \| upload_name \| size \| status_name \| sha1 \| backup_status_name \|
+-----------+---------------------------------------------------------+--------+-------------+------------------------------------------+--------------------+
\| enwiki \| !!!_(Chk_Chk_Chk)_-_One_Girl_One_Boy_cover_art.jpg \| 31850 \| public \| 2c5f4c5ff0e57ffcea85c1da92b4599336d75fb9 \| backedup \|
\| enwiki \| !!!_-_!!!_album_cover.jpg \| 43672 \| public \| 25c046a856d14314cda3c741539f41fbc6c63fe2 \| backedup \|
\| enwiki \| !!!_-_Wallop.png \| 118745 \| public \| 3fccf40bfd27ccfac1d057198fd4315afd50b42d \| backedup \|
\| enwiki \| !0_Trombones_Like_2_Pianos.jpg \| 25319 \| public \| 3ec8b40e128ad8c677b869ef9280104c03bff2e5 \| backedup \|
\| enwiki \| !ClaudiaPascoal.png \| 26203 \| public \| 66a8f68f1ac4708aaa600dcc5a5690836868a2c9 \| backedup \|
\| enwiki \| !Haunu.ogg \| 13450 \| public \| 77577544869768e619829c4e9e6e0ddde94f9421 \| backedup \|
\| enwiki \| !Hero_(album).jpg \| 38664 \| public \| c42574f1639e0bd96749f0ac3e76b69573ce2ba3 \| backedup \|
\| enwiki \| !Women_Art_Revolution_(documentary_film)_poster_art.jpg \| 15446 \| public \| fd33557daf97103c72401e7a33723360cd0db9f4 \| backedup \|
\| enwiki \| !_(The_Song_Formely_Known_As)_by_Regurgitator.png \| 146525 \| public \| c491daf7642bfa1d192b22bc83cc41c721d1092e \| backedup \|
\| enwiki \| ""Motor-Cycle"_LP_cover-Lotti_Golden.jpg \| 17001 \| public \| dbc8dcac96e647d0dfcba702c88e86a0935e2d88 \| backedup \|
+-----------+---------------------------------------------------------+--------+-------------+------------------------------------------+--------------------+
10 rows in set (0.035 sec)

~10 rows read, using the index to avoid the sort + short circuit the scan.

I could not make the query on MariaDB behave as expected with index hints. The only way I could do it is by doing:

workaround-not-really.sql
db1133.eqiad.wmnet[mediabackups]> select wiki_name, upload_name, size, status_name, sha1, backup_status_name FROM files JOIN file_status ON file_status.id = files.status JOIN backup_status ON backup_status.id = files.backup_status JOIN wikis ON wikis.id = files.wiki WHERE files.id BETWEEN 1 AND 10; -- note the only change at the end
+-----------+---------------------------------------------------------+--------+-----------
\| wiki_name \| upload_name \| size \| status_nam
+-----------+---------------------------------------------------------+--------+-----------
\| enwiki \| !!!_(Chk_Chk_Chk)_-_One_Girl_One_Boy_cover_art.jpg \| 31850 \| public
\| enwiki \| !!!_-_!!!_album_cover.jpg \| 43672 \| public
\| enwiki \| !!!_-_Wallop.png \| 118745 \| public
\| enwiki \| !0_Trombones_Like_2_Pianos.jpg \| 25319 \| public
\| enwiki \| !ClaudiaPascoal.png \| 26203 \| public
\| enwiki \| !Haunu.ogg \| 13450 \| public
\| enwiki \| !Hero_(album).jpg \| 38664 \| public
\| enwiki \| !Women_Art_Revolution_(documentary_film)_poster_art.jpg \| 15446 \| public
\| enwiki \| !_(The_Song_Formely_Known_As)_by_Regurgitator.png \| 146525 \| public
\| enwiki \| ""Motor-Cycle"_LP_cover-Lotti_Golden.jpg \| 17001 \| public
+-----------+---------------------------------------------------------+--------+-----------
10 rows in set (0.001 sec)

But the between usage is not really practical in a general case (gaps on PKs).

I can provide a partial dump of the table (the public part of it), if needed.

Comments

Comment by Jaime Crespo [ 2020-12-18 ]

Could it be related to MDEV-13275 or MDEV-8306?

Comment by Sergei Petrunia [ 2020-12-24 ]

Ok so the optimizer picks a join order that allows to use index to resolve ORDER BY... but then doesn't switch to using the index.

This is not related to MDEV-8306 : that MDEV is about handling cases where the join order picked by the current optimizer will not allow to use an index for ORDER BY.

This is not related to MDEV-13275: that MDEV is about multiple equalities, that is, handling "WHERE x=y ORDER BY x LIMIT ..." where the index is on Y. (for certain queries and certain datatypes of x and y).

Comment by Sergei Petrunia [ 2020-12-25 ]

Ok, I was able to reproduce on 10.4 when I've faked statistics/costs to match those in the provided optimizer trace.

The code which changes the join order is here:

JOIN::optimize_stage2

{code:cpp}

    else if (order &&                      // ORDER BY wo/ preceding GROUP BY

             (simple_order || skip_sort_order)) // which is possibly skippable

      if (test_if_skip_sort_order(tab, order, select_limit, false,

                                  &tab->table->keys_in_use_for_order_by))

        ordered_index_usage= ordered_index_order_by;

{code:cpp}

The branch is not taken, because simple_order=false, skip_sort_order=false.

simple_order=false is set here:

  // Can't use sort on head table if using join buffering

  if (full_join || hash_join)

    TABLE *stable= (sort_by_table == (TABLE *) 1 ?

      join_tab[const_tables].table : sort_by_table);

/*

      FORCE INDEX FOR ORDER BY can be used to prevent join buffering when

      sorting on the first table.

*/

    if (!stable || (!stable->force_index_order &&

                    !map2table[stable->tablenr]->keep_current_rowid))

      if (group_list)

        simple_group= 0;

      if (order)

        simple_order= 0;

full_join=1, because the query plan has this table access that uses full table scan and join buffering:

*************************** 3. row ***************************

           id: 1

  select_type: SIMPLE

        table: backup_status

         type: ALL

possible_keys: PRIMARY

          key: NULL

      key_len: NULL

          ref: NULL

         rows: 4

        Extra: Using where; Using join buffer (flat, BNL join)

Comment by Sergei Petrunia [ 2020-12-25 ]

... while in the provided EXPLAIN from Percona Server the table is using eq_ref:

*************************** 3. row ***************************

           id: 1

  select_type: SIMPLE

        table: backup_status

   partitions: NULL

         type: eq_ref

possible_keys: PRIMARY

          key: PRIMARY

      key_len: 1

          ref: mediabackups.files.backup_status

         rows: 1

     filtered: 100.00

        Extra: NULL

Comment by Sergei Petrunia [ 2020-12-25 ]

A workaround: add force index(primary) for very small tables, file_status and backup_status:

explain

SELECT

  wiki_name, upload_name, size, status_name, sha1, backup_status_name

FROM

       files

  JOIN file_status force index(primary) ON file_status.id = files.status

  JOIN backup_status force index(primary) ON backup_status.id = files.backup_status

  JOIN wikis ON wikis.id = files.wiki

ORDER BY

  files.id

LIMIT 10;

One shouldn't need to use hints, though. I will continue to look at the issue.

Comment by Sergei Petrunia [ 2020-12-26 ]

I've created a mock dataset that allows to reproduce the issue on MariaDB: [^mdev24439-try-testcase.sql] .

It also allows to reproduce the issue on Percona Server 8.0.22-13:

+----+-------------+---------------+------------+--------+---------------------------+---------+---------+---------------+---------+----------+--------------------------------------------+

| id | select_type | table         | partitions | type   | possible_keys             | key     | key_len | ref           | rows    | filtered | Extra                                      |

+----+-------------+---------------+------------+--------+---------------------------+---------+---------+---------------+---------+----------+--------------------------------------------+

|  1 | SIMPLE      | files         | NULL       | ALL    | status,backup_status,wiki | NULL    | NULL    | NULL          | 4902500 |   100.00 | Using temporary; Using filesort            |

|  1 | SIMPLE      | file_status   | NULL       | ALL    | PRIMARY                   | NULL    | NULL    | NULL          |       4 |    25.00 | Using where; Using join buffer (hash join) |

|  1 | SIMPLE      | backup_status | NULL       | ALL    | PRIMARY                   | NULL    | NULL    | NULL          |       4 |    25.00 | Using where; Using join buffer (hash join) |

|  1 | SIMPLE      | wikis         | NULL       | eq_ref | PRIMARY                   | PRIMARY | 4       | j1.files.wiki |       1 |   100.00 | NULL                                       |

+----+-------------+---------------+------------+--------+---------------------------+---------+---------+---------------+---------+----------+--------------------------------------------+

Comment by Sergei Petrunia [ 2020-12-26 ]

hmm but after I run ANALYZE TABLE for the small tables analyze table file_status; analyze table backup_status; I get the good plan again:

+----+-------------+---------------+------------+--------+---------------------------+---------+---------+------------------------+------+----------+-------------+

| id | select_type | table         | partitions | type   | possible_keys             | key     | key_len | ref                    | rows | filtered | Extra       |

+----+-------------+---------------+------------+--------+---------------------------+---------+---------+------------------------+------+----------+-------------+

|  1 | SIMPLE      | files         | NULL       | index  | status,backup_status,wiki | PRIMARY | 4       | NULL                   |   10 |   100.00 | Using where |

|  1 | SIMPLE      | file_status   | NULL       | eq_ref | PRIMARY                   | PRIMARY | 1       | j1.files.status        |    1 |   100.00 | NULL        |

|  1 | SIMPLE      | backup_status | NULL       | eq_ref | PRIMARY                   | PRIMARY | 1       | j1.files.backup_status |    1 |   100.00 | NULL        |

|  1 | SIMPLE      | wikis         | NULL       | eq_ref | PRIMARY                   | PRIMARY | 4       | j1.files.wiki          |    1 |   100.00 | NULL        |

+----+-------------+---------------+------------+--------+---------------------------+---------+---------+------------------------+------+----------+-------------+

It's interesting, what was missing?

Both ANALYZEd tables have only the PRIMARY keys (which don't need statistics) and as the previous EXPLAIN shows, the optimizer had the precise estimate of #rows in the table (4) before the ANALYZE.

Comment by Sergei Petrunia [ 2020-12-26 ]

--- trace-before-analyze

+++ trace-after-analyze

@@ -600,7 +610,7 @@

                    "rest_of_plan": [

                        "plan_prefix": [

                              "rows_to_scan": 4,

                              "filtering_effect": [

],

                              "final_filtering_effect": 1,

                              "access_type": "scan",

                          "`file_status`",

                          "`files`"

],

                        "table": "`backup_status`",

                        "best_access_path": {

                          "considered_access_paths": [

                               "access_type": "eq_ref",

                               "index": "PRIMARY",

                               "rows": 1,

-                              "cost": 7.19e6,

+                              "cost": 2.29e6,

                               "chosen": true,

                               "cause": "clustered_pk_chosen_by_heuristics"

},

After ANALYZE, the cost of eq_ref lookup becomes 3x less.

@@ -613,14 +623,14 @@

                              "rows_to_scan": 4,

                              "filtering_effect": [

],

                              "final_filtering_effect": 1,

                              "access_type": "scan",

                               "using_join_cache": true,

                               "buffers_needed": 10374,

                               "resulting_rows": 4,

-                              "cost": 2.63e6,

-                              "chosen": true

+                              "cost": 2.62e6,

+                              "chosen": false

},

The cost of full table scan remains the same, but now it is more expensive than eq_ref. So, it is not chosen.

I assume the rest of the logic is the same: use of join buffer prevents use of an index to resolve ORDER BY .. LIMIT clause

Comment by Sergei Petrunia [ 2020-12-26 ]

This case will be fixed when MDEV-8306 (including MDEV-22360) are done.

As for fixing it before that... this could be achieved by fixing one of the two:

Issue #1: It is not clear for me why the optimizer prefers a full table scan over a PK lookup. It seems, the cost formula is inadequate.

Issue #2: the "join buffering disables use of index to resolve filesort" . Fixing this is basically a [small] subset of what MDEV-8306 will do..

any fix for issue #1 or #2 would be rather intrusive. It will probably be too risky to put it into any stable release...

EDIT
to reiterate: at the moment I'm not convinced that good plan in Percona Server is actual optimizer choice, not pure luck. (See my testcase above which hints at the contrary. running ANALYZE caused it to use the good query plan but this looks like luck and not a meaningful change)

Comment by Sergei Petrunia [ 2020-12-26 ]

Note: all tables except files have PKs (have at most one matching row), and table files has foreign keys which guarantee that all tables always do have a matching row.

This means, the query may be rewritten as follows:

explain

SELECT

  (select wiki_name from wikis where wikis.id=files.wiki),

  upload_name, size,

  (select status_name from file_status where file_status.id = files.status),

  sha1,

  (select backup_status_name from backup_status

   where backup_status.id = files.backup_status)

FROM

  files

ORDER BY

  files.id

LIMIT 10;

This will always use a good query plan:

+------+--------------------+---------------+--------+---------------+---------+---------+------------------------+------+-------+

| id   | select_type        | table         | type   | possible_keys | key     | key_len | ref                    | rows | Extra |

+------+--------------------+---------------+--------+---------------+---------+---------+------------------------+------+-------+

|    1 | PRIMARY            | files         | index  | NULL          | PRIMARY | 4       | NULL                   | 10   |       |

|    4 | DEPENDENT SUBQUERY | backup_status | eq_ref | PRIMARY       | PRIMARY | 1       | j2.files.backup_status | 1    |       |

|    3 | DEPENDENT SUBQUERY | file_status   | eq_ref | PRIMARY       | PRIMARY | 1       | j2.files.status        | 1    |       |

|    2 | DEPENDENT SUBQUERY | wikis         | eq_ref | PRIMARY       | PRIMARY | 4       | j2.files.wiki          | 1    |       |

+------+--------------------+---------------+--------+---------------+---------+---------+------------------------+------+-------+

(jcrespo is this a good enough workaround?)

Comment by Julien Fritsch [ 2023-12-05 ]

Automated message:
----------------------------
Since this issue has not been updated since 6 weeks, it's time to move it back to Stalled.

Comment by JiraAutomate [ 2023-12-05 ]

Automated message:
----------------------------
Since this issue has not been updated since 6 weeks, it's time to move it back to Stalled.

Generated at Thu Feb 08 09:30:00 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.

[MDEV-24439] Major optimizer regression with ORDER BY PK + short LIMIT Created: 2020-12-18 Updated: 2023-12-05