Bug #120935 Duplicate equivalent EXISTS predicate is not eliminated and causes a much slower execution plan

• Submitted: 15 Jul 10:45
• Modified: 22 Jul 14:06
• Reporter: cl hl
• Status: Verified
• Category: MySQL Server: Optimizer
• Severity: S2 (Serious)
• Version: 8.0.46, 8.4.10, 9.7.1
• OS: Any
• CPU Architecture: Any

[15 Jul 10:45] cl hl

Description:
A query becomes much slower after adding a semantically redundant duplicate EXISTS predicate.

The original query contains a predicate of the following form:

    P AND EXISTS (subquery)

The mutated query rewrites it into the equivalent form:

    EXISTS (subquery) AND (P AND EXISTS (subquery))

This transformation is logically equivalent because the same EXISTS predicate is duplicated under AND. However, MySQL does not eliminate or reuse the duplicated EXISTS predicate. Instead, the optimizer expands the duplicated subquery into the execution plan again, producing a much larger plan and significantly slower execution.

In the observed case, the original query has median runtime around 50 ms, while the mutated equivalent query has median runtime around 3094 ms.

Observed timing:
    original median: 50.658 ms
    mutated median:  3094.383 ms
    ratio original/mutated: 0.0164

The mutated query is about 61x slower.

Compared with #Bug120899,the redundant predicate is different.This is the exists subquery, additionally,#Bug120899' is in subquery

How to repeat:
The simplest SQL used to reproduced:

DROP DATABASE IF EXISTS rift_exists_min;
CREATE DATABASE rift_exists_min;
USE rift_exists_min;

CREATE TABLE outer_t (
  id INT PRIMARY KEY,
  v INT
);

CREATE TABLE a (
  x INT
);

CREATE TABLE b (
  y INT
);

INSERT INTO outer_t VALUES (1, 1);

INSERT INTO a
WITH RECURSIVE seq(n) AS (
  SELECT 1
  UNION ALL
  SELECT n + 1 FROM seq WHERE n < 1000
)
SELECT n FROM seq;

INSERT INTO b
WITH RECURSIVE seq(n) AS (
  SELECT 1
  UNION ALL
  SELECT n + 1 FROM seq WHERE n < 1000
)
SELECT n FROM seq;

-- Original query: one EXISTS predicate.
EXPLAIN FORMAT=TREE
SELECT COUNT(*)
FROM outer_t
WHERE v = 1
  AND EXISTS (
    SELECT 1
    FROM a CROSS JOIN b
    WHERE a.x + b.y = 2000
  );

SELECT COUNT(*)
FROM outer_t
WHERE v = 1
  AND EXISTS (
    SELECT 1
    FROM a CROSS JOIN b
    WHERE a.x + b.y = 2000
  );

-- Mutated query: the same EXISTS predicate is duplicated under AND.
-- This is semantically equivalent to the original query.
EXPLAIN FORMAT=TREE
SELECT COUNT(*)
FROM outer_t
WHERE EXISTS (
    SELECT 1
    FROM a CROSS JOIN b
    WHERE a.x + b.y = 2000
  )
  AND (
    v = 1
    AND EXISTS (
      SELECT 1
      FROM a CROSS JOIN b
      WHERE a.x + b.y = 2000
    )
  );

SELECT COUNT(*)
FROM outer_t
WHERE EXISTS (
    SELECT 1
    FROM a CROSS JOIN b
    WHERE a.x + b.y = 2000
  )
  AND (
    v = 1
    AND EXISTS (
      SELECT 1
      FROM a CROSS JOIN b
      WHERE a.x + b.y = 2000
    )
  );

[22 Jul 14:06] Chaithra Marsur Gopala Reddy

Hi cl hl,

Thank you for the test case. We do not see a 61x slowdown. We do see a 2x slowdown. 

Thanks,
Chaithra