Bug #121315 Redundant outer DISTINCT over UNION causes a second temporary-table deduplication

• Submitted: 18 Sep 11:42
• Reporter: Aaditya Dubey
• Status: Open
• Category: MySQL Server: Optimizer
• Severity: S3 (Non-critical)
• Version: 8.4.11, 9.7.1
• OS: Any
• CPU Architecture: Any

[18 Sep 11:42] Aaditya Dubey

Description:
UNION without ALL already removes duplicate rows. Therefore, applying DISTINCT to the complete result of a UNION is redundant and cannot change the result.

MySQL does not eliminate this redundant outer DISTINCT. The execution plan contains one deduplication operation for UNION and a second temporary-table deduplication for the outer DISTINCT.

Expected behaviour

The optimizer should recognize that the output of UNION is already unique for all projected columns and remove the outer DISTINCT.

The following two forms should use the same execution plan, containing only the deduplication required by UNION:

SELECT s.id
FROM (
    (SELECT id FROM lhs)
    UNION
    (SELECT id FROM rhs)
) AS s;
SELECT DISTINCT s.id
FROM (
    (SELECT id FROM lhs)
    UNION
    (SELECT id FROM rhs)
) AS s;
Actual behaviour

Without the outer DISTINCT, MySQL uses one set-operation deduplication:

Table scan on s
└─ Union materialize with deduplication
   ├─ Table scan on lhs
   └─ Table scan on rhs

With the redundant outer DISTINCT, MySQL creates another temporary table and performs a second deduplication:

Table scan on <temporary>
└─ Temporary table with deduplication
   └─ Table scan on s
      └─ Union materialize with deduplication
         ├─ Table scan on lhs
         └─ Table scan on rhs

Both queries return 150,000 rows.

In seven alternating executions after warm-up, using COUNT(*) wrappers to avoid client result-transfer cost, the observed medians were:

UNION without outer DISTINCT: 55.62 ms
UNION with outer DISTINCT:    60.22 ms
Slowdown:                      1.083x

How to repeat:
Run the following complete SQL script on MySQL. The EXPLAIN
statements show the additional deduplication operator. Execute the final two
COUNT(*) queries are repeatedly run in alternating order to compare execution time.

DROP DATABASE IF EXISTS mysql_union_outer_distinct;
CREATE DATABASE mysql_union_outer_distinct;
USE mysql_union_outer_distinct;

CREATE TABLE digits (
    d INT PRIMARY KEY
);

INSERT INTO digits VALUES
    (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);

CREATE TABLE lhs (
    id INT NOT NULL,
    v INT,
    INDEX (v)
);

CREATE TABLE rhs (
    id INT NOT NULL,
    v INT,
    INDEX (v)
);

-- lhs contains 1 through 100000.
INSERT INTO lhs
SELECT n, MOD(n, 1000)
FROM (
    SELECT
        a.d
        + b.d * 10
        + c.d * 100
        + d.d * 1000
        + e.d * 10000
        + 1 AS n
    FROM digits AS a
    CROSS JOIN digits AS b
    CROSS JOIN digits AS c
    CROSS JOIN digits AS d
    CROSS JOIN digits AS e
) AS numbers;

-- rhs contains 50001 through 150000, giving 50000 overlapping values.
INSERT INTO rhs
SELECT n, MOD(n, 1000)
FROM (
    SELECT
        a.d
        + b.d * 10
        + c.d * 100
        + d.d * 1000
        + e.d * 10000
        + 50001 AS n
    FROM digits AS a
    CROSS JOIN digits AS b
    CROSS JOIN digits AS c
    CROSS JOIN digits AS d
    CROSS JOIN digits AS e
) AS numbers;

ANALYZE TABLE lhs, rhs;

-- One deduplication: UNION itself.
EXPLAIN FORMAT=TREE
SELECT s.id
FROM (
    (SELECT id FROM lhs)
    UNION
    (SELECT id FROM rhs)
) AS s;

-- Two deduplications: UNION plus the redundant outer DISTINCT.
EXPLAIN FORMAT=TREE
SELECT DISTINCT s.id
FROM (
    (SELECT id FROM lhs)
    UNION
    (SELECT id FROM rhs)
) AS s;

-- Timing query without the redundant outer DISTINCT.
SELECT COUNT(*)
FROM (
    (SELECT id FROM lhs)
    UNION
    (SELECT id FROM rhs)
) AS s;

-- Equivalent timing query with the redundant outer DISTINCT.
SELECT COUNT(*)
FROM (
    SELECT DISTINCT s.id
    FROM (
        (SELECT id FROM lhs)
        UNION
        (SELECT id FROM rhs)
    ) AS s
) AS q;