AliSQL: duplicating an equivalent EXISTS predicate causes a 424x slowdown

[chen8908917]

Description

For any SQL boolean expression P, the conjunction P AND P is equivalent to P, including under SQL three-valued logic. Repeating the same uncorrelated EXISTS predicate should therefore either be eliminated or, at minimum, should not cause the optimizer to choose a substantially worse join order.

In this case, adding a second identical EXISTS predicate changes the plan from an indexed lookup on the outer table to a plan that evaluates both copies of the expensive subquery first. The two queries return exactly the same empty result.

Expected behavior

AliSQL should recognize the duplicate predicate in:

EXISTS(subquery) AND outer_predicate AND EXISTS(subquery)

and simplify it to:

outer_predicate AND EXISTS(subquery)

Both queries should begin with the indexed t1.c6 = 'absent' lookup, discover that no outer row matches, and avoid evaluating the remaining joins.

Actual behavior

The query containing one EXISTS starts with table o and uses the c6 index:

table=o  type=ref  key=c6  ref=const  Extra=Using index

The query containing two identical EXISTS predicates starts with table a, creates a temporary semijoin structure, repeats the subquery tables, and postpones the indexed lookup:

table=a  type=range  key=c5  Extra=Using index condition; Using where; Start temporary
table=o  type=ref    key=c6  ref=const
...
table=y  type=index  Extra=Using index; End temporary; Using join buffer (hash join)

With 1,000 rows in t1, an empty t3, warm-up executions, and alternating execution order, 14 measured executions of each query produced:

Query	Median	Average	Range
One EXISTS	1.109 ms	1.146 ms	0.575–2.134 ms
Duplicate EXISTS	470.320 ms	469.203 ms	461.339–474.568 ms

The query containing the redundant predicate was approximately 424.29 times slower. Both queries returned zero rows.

How to repeat

Run the following complete SQL script in AliSQL:

SELECT VERSION(), @@version_comment, @@port;

DROP DATABASE IF EXISTS alisql_duplicate_exists_mre;
CREATE DATABASE alisql_duplicate_exists_mre;
USE alisql_duplicate_exists_mre;

CREATE TABLE t1 (
    id INT PRIMARY KEY,
    c5 DATE,
    c6 VARCHAR(40),
    INDEX(c5),
    INDEX(c6)
);

CREATE TABLE t3 (
    c9 INT,
    c15 INT
);

SET cte_max_recursion_depth = 2000;

INSERT INTO t1
WITH RECURSIVE seq(i) AS (
    SELECT 1
    UNION ALL
    SELECT i + 1 FROM seq WHERE i < 1000
)
SELECT i, DATE '2024-01-01', CONCAT('value_', i)
FROM seq;

ANALYZE TABLE t1, t3;

-- Original plan: begins with the indexed lookup on o.c6.
EXPLAIN
WITH c AS (
    SELECT c9 AS q2, c15 % 95 AS q4
    FROM t3
)
SELECT o.id
FROM t1 AS o
WHERE o.c6 = 'absent'
  AND EXISTS (
      SELECT 1
      FROM t1 AS a
      CROSS JOIN c AS b
        ON a.c6 NOT LIKE 'sample_14'
       AND EXISTS (
           SELECT 1
           FROM t3 AS x
           CROSS JOIN t1 AS y
           WHERE EXISTS (
               SELECT 1
               FROM c AS z
               WHERE z.q4 BETWEEN 8 AND 50
           )
       )
      JOIN c AS d
        ON a.c5 BETWEEN DATE '2023-01-01' AND DATE '2023-12-31'
      WHERE d.q2 BETWEEN 46 AND 71
      LIMIT 39
  );

-- Mutated plan: the identical EXISTS is repeated.
EXPLAIN
WITH c AS (
    SELECT c9 AS q2, c15 % 95 AS q4
    FROM t3
)
SELECT o.id
FROM t1 AS o
WHERE EXISTS (
      SELECT 1
      FROM t1 AS a
      CROSS JOIN c AS b
        ON a.c6 NOT LIKE 'sample_14'
       AND EXISTS (
           SELECT 1
           FROM t3 AS x
           CROSS JOIN t1 AS y
           WHERE EXISTS (
               SELECT 1
               FROM c AS z
               WHERE z.q4 BETWEEN 8 AND 50
           )
       )
      JOIN c AS d
        ON a.c5 BETWEEN DATE '2023-01-01' AND DATE '2023-12-31'
      WHERE d.q2 BETWEEN 46 AND 71
      LIMIT 39
  )
  AND o.c6 = 'absent'
  AND EXISTS (
      SELECT 1
      FROM t1 AS a
      CROSS JOIN c AS b
        ON a.c6 NOT LIKE 'sample_14'
       AND EXISTS (
           SELECT 1
           FROM t3 AS x
           CROSS JOIN t1 AS y
           WHERE EXISTS (
               SELECT 1
               FROM c AS z
               WHERE z.q4 BETWEEN 8 AND 50
           )
       )
      JOIN c AS d
        ON a.c5 BETWEEN DATE '2023-01-01' AND DATE '2023-12-31'
      WHERE d.q2 BETWEEN 46 AND 71
      LIMIT 39
  );

-- Execute the two SELECT statements from the EXPLAIN commands without the
-- EXPLAIN keyword. Both return zero rows. Alternate their execution order
-- over multiple repetitions to obtain stable timing measurements.

Version

AliSQL source commit: 9e121f27d404cad6cdb1cc695eab4276469adace
VERSION(): 8.0.44
@@version_comment: Source distribution
Platform: Linux x86_64