MySQL Bugs: #120607: Join-order enumeration ignores ORDER BY sort cost

Bug #120607	Join-order enumeration ignores ORDER BY sort cost
Submitted:	3 Jun 7:22	Modified:	15 Jun 10:48
Reporter:	Yuchen Sun	Email Updates:
Status:	Duplicate	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S5 (Performance)
Version:	9.6	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
Hi, MySQL developers, thanks for reading my report. I find an optimizer bug in MySQL.

Through analysis of the optimizer trace, when a two-table join carries `ORDER BY t1.x LIMIT n`, the join-order enumeration in `considered_execution_plans` compares candidate join orders by join cost only — the sort cost required to satisfy the `ORDER BY` is missing from the comparison. The chosen join order therefore looks cheap, but its result is unordered and must go through a full filesort; the sort cost is only charged afterwards (in the `reconsidering_access_paths_for_index_ordering` phase), once the order is frozen, and the optimizer will not re-enumerates. Because the comparison omits sort cost, the optimizer commits to a plan that runs three orders of magnitude slower than a naturally-ordered join order it had already considered and rejected.

The logically equivalent query with `/*+ JOIN_ORDER(t1, t0) */` produces the expected plan:
`t1` is scanned in `idx_t1_x` order, only the matching rows are read, no filesort is performed,
the result is identical, and it runs far faster.

How to repeat:
CREATE DATABASE IF NOT EXISTS optcov_target;
USE optcov_target;
DROP TABLE IF EXISTS optcov_t1;
DROP TABLE IF EXISTS optcov_t0;

CREATE TABLE optcov_t0 (
  id   INT          NOT NULL PRIMARY KEY,
  a    INT          NULL,
  b    INT          NOT NULL,
  c    VARCHAR(64)  NULL,
  d    DATETIME     NOT NULL,
  flag TINYINT      NOT NULL,
  KEY idx_t0_a       (a),
  KEY idx_t0_b       (b),
  KEY idx_t0_ab      (a, b),
  KEY idx_t0_c       (c),
  KEY idx_t0_flag_a  (flag, a),
  KEY idx_t0_b_c     (b, c)
) ENGINE=InnoDB;

CREATE TABLE optcov_t1 (
  id    INT          NOT NULL PRIMARY KEY,
  t0_id INT          NOT NULL,
  x     INT          NULL,
  y     VARCHAR(64)  NULL,
  flag  TINYINT      NOT NULL,
  KEY idx_t1_t0_id    (t0_id),
  KEY idx_t1_x        (x),
  KEY idx_t1_t0_x     (t0_id, x),
  KEY idx_t1_flag_x   (flag, x),
  KEY idx_t1_y_prefix (y(10))
) ENGINE=InnoDB;

INSERT INTO optcov_t0 (id, a, b, c, d, flag)
SELECT
  i,
  IF(i % 23 = 0, NULL, IF(i % 10 = 0, 1, i % 101)),
  (i * 7) % 997,
  IF(i % 17 = 0, NULL, CONCAT('s', i % 37)),
  '2024-01-01 00:00:00',
  i % 2
FROM (
  SELECT d1.n + d2.n*10 + d3.n*100 + d4.n*1000
       + d5.n*10000 + d6.n*100000 + 1 AS i
  FROM       (SELECT 0 n UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) d1
  CROSS JOIN (SELECT 0 n UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) d2
  CROSS JOIN (SELECT 0 n UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) d3
  CROSS JOIN (SELECT 0 n UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) d4
  CROSS JOIN (SELECT 0 n UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) d5
  CROSS JOIN (SELECT 0 n UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) d6
) t
WHERE i <= 1000000;

INSERT INTO optcov_t1 (id, t0_id, x, y, flag)
SELECT
  i,
  ((i * 13) % 1000000) + 1,
  IF(i % 29 = 0, NULL, IF(i % 11 = 0, 3, (i * 5) % 503)),
  IF(i % 19 = 0, NULL, CONCAT('y', i % 53)),
  IF(i % 5 = 0, 1, 0)
FROM (
  SELECT d1.n + d2.n*10 + d3.n*100 + d4.n*1000
       + d5.n*10000 + d6.n*100000 + d7.n*1000000 + 1 AS i
  FROM       (SELECT 0 n UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) d1
  CROSS JOIN (SELECT 0 n UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) d2
  CROSS JOIN (SELECT 0 n UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) d3
  CROSS JOIN (SELECT 0 n UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) d4
  CROSS JOIN (SELECT 0 n UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) d5
  CROSS JOIN (SELECT 0 n UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) d6
  CROSS JOIN (SELECT 0 n UNION ALL SELECT 1 UNION ALL SELECT 2) d7
) t
WHERE i <= 3000000;

EXPLAIN FORMAT=TREE
SELECT t0.id, t1.x FROM optcov_t0 AS t0
  JOIN optcov_t1 AS t1 ON t0.id = t1.t0_id
  WHERE t0.flag = 1 ORDER BY t1.x LIMIT 10;

EXPLAIN FORMAT=TREE
SELECT /*+ JOIN_ORDER(t1, t0) */ t0.id, t1.x FROM optcov_t0 AS t0
  JOIN optcov_t1 AS t1 ON t0.id = t1.t0_id
  WHERE t0.flag = 1 ORDER BY t1.x LIMIT 10;

SELECT t0.id, t1.x FROM optcov_t0 AS t0
  JOIN optcov_t1 AS t1 ON t0.id = t1.t0_id
  WHERE t0.flag = 1 ORDER BY t1.x LIMIT 10;

SELECT /*+ JOIN_ORDER(t1, t0) */ t0.id, t1.x FROM optcov_t0 AS t0
  JOIN optcov_t1 AS t1 ON t0.id = t1.t0_id
  WHERE t0.flag = 1 ORDER BY t1.x LIMIT 10;

Hi Yuchen Sun,

Thank you for the test case. Verified as described. However, we have a few known issues complaining about this problem already like in Bug#83323 and Bug#88786.
Brief analysis of the issue:
The bad plan happens because the ordered-index access path for ORDER BY ... LIMIT is considered only
later, after the join order has already been fixed. For the unhinted query, join planner chooses t0 -> t1. Since the first non-const table is t0 and the ORDER BY is on t1.x, while simplifying the order by clause, it sees that ordering column is not on the first table in join, and there fore optimizer does not reconsider access paths for ordering. This makes optimizer to then use a filesort.
With JOIN_ORDER(t1,t0), the first table is t1, so ORDER BY t1.x is simple. This makes optimizer to reconsider access paths for ordering, resulting in change of  access path to idx_t1_x, allowing the query to stop after finding the first 10 matching rows.
However, the hypergraph_optimizer chooses the ordered t1 -> t0 plan without the join-order hint.

So we do not plan to fix this in the traditional optimizer path. The recommended workaround is to enable the hypergraph optimizer for this workload/query, or use a join-order hint when the classic optimizer must be used.