MySQL Bugs: #120809: Optimizer misses DISTINCT early-out and chooses 40M-row hash join Cartesian product

Bug #120809	Optimizer misses DISTINCT early-out and chooses 40M-row hash join Cartesian product
Submitted:	29 Jun 7:31	Modified:	2 Jul 14:07
Reporter:	ZHAOYANG ZHANG	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S5 (Performance)
Version:	9.7.1 and 8.0.31	OS:	Ubuntu (22.04.4 LTS)
Assigned to:		CPU Architecture:	Any
Tags:	distinct, firstmatch, hash join, JOIN_ORDER, Optimizer, performance, semijoin

Description:
I found a performance issue in MySQL 9.7.1 where the optimizer misses a DISTINCT early-out opportunity and chooses a much slower hash join plan.

The query selects DISTINCT columns only from table t1. Table t0 is only used to test whether at least one matching row exists for each t1 row. Therefore, a nested-loop plan can stop after the first matching t0 row for each t1 row.

However, the default optimizer chooses an inner hash join with no join condition, produces a large Cartesian product, evaluates the filter for all joined rows, and then performs duplicate elimination using a temporary table.

In my reduced testcase:

t0 has 2,000 rows.
t1 has 20,000 rows.
The default plan produces about 40,000,000 joined rows before duplicate elimination.
The default query takes about 22.7 seconds.
The same query with JOIN_ORDER(t1,t0) takes about 0.16 seconds.
An equivalent EXISTS rewrite also takes about 0.15 seconds and uses a Nested loop semijoin (FirstMatch).

The performance difference is about 140x.

This is not caused by warning generation. SHOW WARNINGS after the default and hinted queries returns an empty set.

The issue appears to be that the optimizer does not recognize or does not choose the existence-style / FirstMatch-style execution opportunity for the original SELECT DISTINCT join form.

This may be related to existing DISTINCT/hash join optimizer issues, but this testcase reproduces the problem on MySQL 9.7.1 with a simple two-table query and shows that an equivalent EXISTS rewrite gets the intended FirstMatch-style behavior.

Default plan excerpt:

EXPLAIN ANALYZE
SELECT DISTINCTROW t1.c4 AS ref0, t1.c3 AS ref1, t1.c2 AS ref2
FROM t1, t0
WHERE t0.c1 < CAST(GREATEST(t1.c3, '0.8727017201037127') AS SIGNED);

Plan shape:

-> Table scan on <temporary> (actual time=22667..22669 rows=20000)
-> Temporary table with deduplication (actual time=22667..22667 rows=20000)
-> Filter: t0.c1 < CAST(GREATEST(t1.c3,'0.8727017201037127') AS SIGNED)
(actual time=0.993..7933 rows=40000000)
-> Inner hash join (no condition)
(actual time=0.987..1746 rows=40000000)
-> Table scan on t1 (actual rows=20000)
-> Hash
-> Covering index scan on t0 using i1 (actual rows=2000)

Hinted plan:

EXPLAIN ANALYZE
SELECT /*+ JOIN_ORDER(t1, t0) */ DISTINCTROW t1.c4 AS ref0, t1.c3 AS ref1, t1.c2 AS ref2
FROM t1, t0
WHERE t0.c1 < CAST(GREATEST(t1.c3, '0.8727017201037127') AS SIGNED);

Plan shape:

-> Table scan on <temporary> (actual time=151..153 rows=20000)
-> Temporary table with deduplication (actual time=151..151 rows=20000)
-> Nested loop inner join (actual time=0.0478..137 rows=20000)
-> Table scan on t1 (actual rows=20000)
-> Limit: 1 row(s) (actual rows=1 loops=20000)
-> Filter: t0.c1 < CAST(GREATEST(t1.c3,'0.8727017201037127') AS SIGNED)
-> Index range scan on t0 (re-planned for each iteration)

Equivalent EXISTS rewrite:

EXPLAIN ANALYZE
SELECT DISTINCTROW t1.c4 AS ref0, t1.c3 AS ref1, t1.c2 AS ref2
FROM t1
WHERE EXISTS (
SELECT 1
FROM t0
WHERE t0.c1 < CAST(GREATEST(t1.c3, '0.8727017201037127') AS SIGNED)
);

Plan shape:

-> Nested loop semijoin (FirstMatch)
actual time is about 0.153 seconds.

This shows that the original DISTINCT query has an existence-style execution opportunity, but the default optimizer plan does not exploit it.

How to repeat:
1. Start MySQL 9.7.1.
2. Run the attached SQL script mysql_distinct_earlyout.sql.

3. The script creates two InnoDB tables t0 and t1, inserts 2,000 rows into t0 and 20,000 rows into t1, creates indexes, runs ANALYZE TABLE, and then runs the following checks:

SELECT COUNT() AS t0_count FROM t0;
SELECT COUNT() AS t1_count FROM t1;

Expected:
t0_count = 2000
t1_count = 20000

4. Run the baseline EXPLAIN ANALYZE:

EXPLAIN ANALYZE
SELECT DISTINCTROW t1.c4 AS ref0, t1.c3 AS ref1, t1.c2 AS ref2
FROM t1, t0
WHERE t0.c1 < CAST(GREATEST(t1.c3, '0.8727017201037127') AS SIGNED);

Observed:
The optimizer chooses an Inner hash join with no condition, produces about 40,000,000 rows, and then performs temporary-table duplicate elimination. Runtime is about 22.7 seconds.

5. Run the hinted query:

EXPLAIN ANALYZE
SELECT /*+ JOIN_ORDER(t1, t0) */ DISTINCTROW t1.c4 AS ref0, t1.c3 AS ref1, t1.c2 AS ref2
FROM t1, t0
WHERE t0.c1 < CAST(GREATEST(t1.c3, '0.8727017201037127') AS SIGNED);

Observed:
The optimizer uses a nested-loop plan with inner LIMIT 1. Runtime is about 0.16 seconds.

6. Run the equivalent EXISTS rewrite:

EXPLAIN ANALYZE
SELECT DISTINCTROW t1.c4 AS ref0, t1.c3 AS ref1, t1.c2 AS ref2
FROM t1
WHERE EXISTS (
SELECT 1
FROM t0
WHERE t0.c1 < CAST(GREATEST(t1.c3, '0.8727017201037127') AS SIGNED)
);

Observed:
The optimizer uses Nested loop semijoin (FirstMatch). Runtime is about 0.15 seconds.

Expected behavior:
The optimizer should avoid materializing/evaluating the full Cartesian product for this SELECT DISTINCT query when the selected DISTINCT columns only come from t1 and t0 is only needed to prove the existence of at least one matching row. It should prefer an early-out / FirstMatch-style plan similar to the hinted plan or the EXISTS rewrite.

Actual behavior:
The default plan chooses a hash join with no condition, produces about 40 million intermediate rows, evaluates the filter for all of them, and then performs temporary-table deduplication. This makes the query about 140x slower than the equivalent early-out plans.

Suggested fix:
The optimizer should consider a semijoin/FirstMatch-style transformation or a DISTINCT early-out plan when all DISTINCT output columns depend only on one side of the join and the other table is only needed for existence checking.

In this case, for each t1 row, once one matching t0 row is found, additional matching t0 rows cannot produce additional DISTINCT output rows. Therefore, a nested-loop plan with an inner early-out condition is much cheaper than a hash join over the full Cartesian product.

The costing model should account for this DISTINCT early-out opportunity and should avoid choosing a hash join Cartesian product when an early-out nested-loop or semijoin plan is available and significantly cheaper.

Test case sql file

Attachment: mysql_distinct_earlyout.sql (application/octet-stream, text), 3.69 KiB.

I found a smaller and more targeted reproducer for the same issue. I will upload it as:

  bug120809_distinct_earlyout_unused_table.sql

In this reduced case, the SELECT DISTINCT key only contains columns from t1 and t2:

  SELECT DISTINCTROW t2.c2 AS ref0, t1.c1 AS ref1
  FROM t2, t1 STRAIGHT_JOIN t0 ON (NOT (t0.c0));

No column from t0 is used in the SELECT list or the DISTINCT key. Table t0 only checks whether there exists at least one row satisfying NOT(t0.c0). Therefore, multiple matching rows from t0 only generate duplicate DISTINCT keys.

The data size is:

  t0 matching rows where NOT(c0): 200
  t1 rows: 600
  t2 rows: 600
  final DISTINCT rows: 360,000
  duplicate-expanded rows before deduplication: 72,000,000

The default plan expands all matching t0 rows and generates 72M rows before duplicate removal:

  -> Table scan on <temporary>
       (cost=23.8e+6..24.7e+6 rows=72e+6)
       (actual time=51187..51283 rows=360000 loops=1)
      -> Temporary table with deduplication
           (cost=23.8e+6..23.8e+6 rows=72e+6)
           (actual time=51187..51187 rows=360000 loops=1)
          -> Inner hash join (no condition)
               (cost=7.21e+6 rows=72e+6)
               (actual time=117..3839 rows=72e+6 loops=1)
              -> Covering index scan on t2 using i7
                   (actual time=0.0111..0.402 rows=600 loops=1)
              -> Hash
                  -> Nested loop inner join
                       (actual time=0.0156..63.6 rows=120000 loops=1)
                      -> Covering index scan on t1 using i4
                           (actual time=0.00989..0.286 rows=600 loops=1)
                      -> Covering index lookup on t0 using i0 (c0 = 0)
                           (actual time=839e-6..0.0938 rows=200 loops=600)

Runtime of the default query:

  51.371 sec

With a JOIN_ORDER hint, MySQL finds a much faster valid plan. The important difference is that the t0 lookup is executed with "Limit: 1 row(s)", avoiding the duplicate expansion from t0:

  -> Table scan on <temporary>
       (actual time=1250..1346 rows=360000 loops=1)
      -> Temporary table with deduplication
           (actual time=1250..1250 rows=360000 loops=1)
          -> Nested loop inner join
               (actual time=0.327..439 rows=360000 loops=1)
              -> Inner hash join (no condition)
                   (actual time=0.312..27.3 rows=360000 loops=1)
                  -> Covering index scan on t1 using i4
                       (actual time=0.00276..0.338 rows=600 loops=1)
                  -> Hash
                      -> Covering index scan on t2 using i7
                           (actual time=0.00935..0.261 rows=600 loops=1)
              -> Limit: 1 row(s)
                   (actual time=922e-6..953e-6 rows=1 loops=360000)
                  -> Covering index lookup on t0 using i0 (c0 = 0)
                       (actual time=809e-6..809e-6 rows=1 loops=360000)

Runtime of the hinted query:

  1.434 sec

An equivalent EXISTS rewrite also confirms that t0 is only an existence check:

  SELECT DISTINCTROW t2.c2 AS ref0, t1.c1 AS ref1
  FROM t2, t1
  WHERE EXISTS (
    SELECT 1 FROM t0 WHERE NOT t0.c0
  );

Its plan evaluates the t0 existence check with "Limit: 1 row(s)" only once:

  -> Temporary table with deduplication
       (actual time=832..832 rows=360000 loops=1)
      -> Inner hash join (no condition)
           (actual time=0.408..23.2 rows=360000 loops=1)
          -> Covering index scan on t1 using i4
               (actual time=0.0024..0.402 rows=600 loops=1)
          -> Hash
              -> Inner hash join (FirstMatch)
                   (actual time=0.0265..0.339 rows=600 loops=1)
                  -> Covering index scan on t2 using i7
                       (actual time=0.00443..0.258 rows=600 loops=1)
                  -> Hash
                      -> Limit: 1 row(s)
                           (actual time=0.0122..0.0123 rows=1 loops=1)
                          -> Covering index lookup on t0 using i0 (c0 = 0)
                               (actual time=0.0115..0.0115 rows=1 loops=1)

Runtime of the EXISTS rewrite:

  1.018 sec

So the default plan is about 35.8x slower than the JOIN_ORDER hinted plan and about 50.5x slower than the equivalent EXISTS rewrite.

This seems to be a missed DISTINCT early-out / FirstMatch-style optimization for a joined table whose columns are not used in the DISTINCT key. The default plan materializes all duplicate-producing rows from t0, while the hinted and rewritten plans show that only one matching t0 row is needed.

bug120809_distinct_earlyout_unused_table

Attachment: bug120809_distinct_earlyout_unused_table.sql (application/octet-stream, text), 4.06 KiB.

Hi ZHAOYANG ZHANG,

Thank you for the test case. Verified as described.