Bug #120285 Materialized Semijoin + Outer ORDER BY Loses Rows for Correlated EXISTS,Causing Plan-Dependent Result Divergence
Submitted: 18 Apr 15:49 Modified: 18 Apr 15:54
Reporter: Y F Email Updates:
Status: Open Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S2 (Serious)
Version:8.0.45 OS:Ubuntu (Ubuntu 20.04.4 LTS)
Assigned to: CPU Architecture:x86 (Intel(R) Xeon(R) Platinum 8358P @ 2.60GHz (64 Cores, 96MB L3 Cache))

[18 Apr 15:49] Y F
Description:
This issue can be described using two temporal states of the same tables.
For readability, the result and EXPLAIN outputs below are shown in simplified
form, because the raw `mysql` table rendering is excessively wide in this
case.

In the baseline state S1, after creating the replay tables and loading the
initial replay data, the following query returns 1 row:

------------------------------------
mysql> SELECT (COALESCE(`sub1`.`c4`, 0) + COALESCE(`sub1`.`c6`, 0)),
    ->        CONCAT(COALESCE(`sub1`.`c2`, ''), COALESCE(`sub1`.`c4`, '')),
    ->        (CASE WHEN `sub1`.`c3` IS NULL THEN 'missing' ELSE `sub1`.`c3` END),
    ->        UPPER(`sub1`.`c6`)
    -> FROM `subset3_ebeb1651` sub1
    -> WHERE (`sub1`.`c5` IS NOT NULL OR `sub1`.`c6` >= '2023-01-01')
    ->   AND `sub1`.`c4` = -6
    ->   AND EXISTS (
    ->       SELECT 1
    ->       FROM `subset3_ref_ebeb1651_t3` ex2
    ->       WHERE `ex2`.`c4` = `ex2`.`c10`
    ->         AND `sub1`.`c2` = `ex2`.`c4`
    ->   )
    -> ORDER BY `sub1`.`c6` DESC;
Result row:
    expr1 = -6.0
    expr2 = hv_7711-6
    expr3 = 0000-00-00
    expr4 = HV_4224
1 row in set
------------------------------------

The S1 plan uses the FirstMatch semijoin path:

------------------------------------
mysql> EXPLAIN FORMAT=TRADITIONAL SELECT ... ;
Plan summary:
    1. sub1: ref on i_s3_ebeb1651, key_len=5, ref=const, rows=3,
       Extra=Using temporary; Using filesort
    2. ex2:  ALL, rows=11, filtered=9.09,
       Extra=Using where; FirstMatch(sub1); Using join buffer (hash join)
------------------------------------

Then I transform S1 into S2 by executing the append-only transaction from the
original replay SQL, committing it, and running ANALYZE TABLE on
`subset3_ebeb1651`. In S2, the same query returns 0 rows:

------------------------------------
mysql> SELECT (COALESCE(`sub1`.`c4`, 0) + COALESCE(`sub1`.`c6`, 0)),
    ->        CONCAT(COALESCE(`sub1`.`c2`, ''), COALESCE(`sub1`.`c4`, '')),
    ->        (CASE WHEN `sub1`.`c3` IS NULL THEN 'missing' ELSE `sub1`.`c3` END),
    ->        UPPER(`sub1`.`c6`)
    -> FROM `subset3_ebeb1651` sub1
    -> WHERE (`sub1`.`c5` IS NOT NULL OR `sub1`.`c6` >= '2023-01-01')
    ->   AND `sub1`.`c4` = -6
    ->   AND EXISTS (
    ->       SELECT 1
    ->       FROM `subset3_ref_ebeb1651_t3` ex2
    ->       WHERE `ex2`.`c4` = `ex2`.`c10`
    ->         AND `sub1`.`c2` = `ex2`.`c4`
    ->   )
    -> ORDER BY `sub1`.`c6` DESC;
Empty set
------------------------------------

Because S2 is obtained from S1 by append-only inserts, the result set in S2
should be a superset of the corresponding result set in S1. Therefore the
monotonicity invariant requires that every row returned in S1 must still
appear in S2. Instead, the observed results are:

------------------------------------
COUNT(S1) = 1
COUNT(S2) = 0
------------------------------------

This violates the expected S1-to-S2 monotonicity relationship.

The S2 plan switches to a materialized semijoin shape:

------------------------------------
mysql> EXPLAIN FORMAT=TRADITIONAL SELECT ... ;
Plan summary:
    1. sub1: ref on i_s3_ebeb1651, key_len=5, ref=const, rows=62,
       Extra=Using filesort
    2. <subquery2>: eq_ref on <auto_distinct_key>, key_len=1,
       ref=test_replay.sub1.c2, rows=1, Extra=Using where
    3. ex2: MATERIALIZED subquery scan, type=ALL, rows=11, filtered=10.0,
       Extra=Using where
------------------------------------

Further diagnostics on the same replay show that this is not a simple data or
coercion issue. The subquery witness row is valid:

------------------------------------
mysql> SELECT 'witness' AS stage, ex2.c1, ex2.c4, ex2.c10,
    ->        (ex2.c4 = ex2.c10) AS eq_ok
    -> FROM subset3_ref_ebeb1651_t3 ex2
    -> WHERE ex2.c4 = ex2.c10;
stage = witness, c1 = 9000000, c4 = 0, c10 = nfyuvwel, eq_ok = 1
------------------------------------

And when the optimizer strategy is forced explicitly:

------------------------------------
mysql> -- FirstMatch semijoin
mysql> SELECT 'S1_count' AS stage, COUNT(*) AS cnt FROM (...same EXISTS query without ORDER BY...) q;
+----------+-----+
| stage    | cnt |
+----------+-----+
| S1_count | 45  |
+----------+-----+

mysql> -- Materialized semijoin, no ORDER BY
mysql> SELECT 'S2_no_order_count' AS stage, COUNT(*) AS cnt FROM (...same EXISTS query without ORDER BY...) q;
+-------------------+-----+
| stage             | cnt |
+-------------------+-----+
| S2_no_order_count | 45  |
+-------------------+-----+

mysql> -- Materialized semijoin, with outer ORDER BY
mysql> SELECT 'S2_with_order' AS stage, sub1.c1, sub1.c2, sub1.c6
    -> FROM subset3_ebeb1651 sub1
    -> WHERE (`sub1`.`c5` IS NOT NULL OR `sub1`.`c6` >= '2023-01-01')
    ->   AND sub1.c4 = -6
    ->   AND EXISTS (
    ->       SELECT 1
    ->       FROM subset3_ref_ebeb1651_t3 ex2
    ->       WHERE ex2.c4 = ex2.c10
    ->         AND sub1.c2 = ex2.c4
    ->   )
    -> ORDER BY sub1.c1;
Empty set
------------------------------------

So the rows are still found by the materialized semijoin path when no outer
sort is required, but the row-producing query becomes empty as soon as an
outer ORDER BY is added. This strongly suggests an executor bug in the
interaction between correlated EXISTS semijoin materialization and the outer
sorting/filesort path, rather than a pure comparison/coercion bug.

How to repeat:
1. Execute the original replay SQL in `relay_out.log`.

Notes:
- Attempts to aggressively reduce this replay into a tiny standalone schema
  changed the optimizer into a different materialized plan shape and lost the
  trigger. The original replay SQL is therefore the most reliable reproducer.
[18 Apr 15:50] Y F
reproduce sql code

Attachment: 20260418_1643.sql (application/octet-stream, text), 74.12 KiB.

[18 Apr 15:54] Y F
Sorry, there's an error in the "How to repeat" section. run "20260418_1643.sql" to repeat