Description:
A `SELECT DISTINCT c2 ... WHERE NOT EXISTS (...)` query silently returns too few rows —
in the worst case an empty result set where a large number of rows qualify — when the
optimizer picks the `Covering index skip scan for deduplication` access method.
The access method emits **exactly one representative row per group of the grouping
column**, namely the first row of the group in index order. The antijoin condition,
which references `c1` (a key part of the *same* index following the grouping prefix),
is only evaluated **above** that access path. Therefore, for each group, the condition
is tested against a single arbitrary member of the group instead of against all of its
rows.
This replaces the required existential semantics
```
{ g : EXISTS r IN R such that r.c2 = g AND P(r) }
```
with a single-witness test
```
{ g : P(first_row_in_index_order_of_group(g)) }
```
Whenever the first row of a group fails `P` but some other row of the group satisfies
it, the whole group is wrongly dropped from the result.
Equivalently, in relational algebra terms: the plan computes `σ_P(δ_c2(R))` while the
query means `δ_c2(σ_P(R))`. Pushing a deduplication `δ_G` below a filter `σ_P` is only
valid when `P` is functionally determined by `G`. Here `P` depends on `c1`, which varies
within a `c2` group, so the transformation is unsound.
### Why this is a regression introduced in 8.0.41
The group skip scan was historically restricted to single-table queries. In that setting
the invariant holds, because any condition on the index key parts following the grouping
prefix is incorporated **into** the scan by the range optimizer, so the scan performs an
existential search inside each group.
This is directly observable — the following returns the correct `{0}` even though
`c1 = 1099` matches only the *last* row of group `c2 = 0`:
```
mysql> EXPLAIN FORMAT=TREE SELECT DISTINCT c2 FROM h WHERE c1 = 1099;
-> Filter: (h.c1 = 1099) (cost=1 rows=3)
-> Covering index skip scan for deduplication on h using k0 (cost=1 rows=3)
mysql> SELECT DISTINCT c2 FROM h WHERE c1 = 1099;
+----+
| c2 |
+----+
| 0 |
+----+
```
The fix for Bug #112362 / Bug #35842412 (documented in the 8.0.41, 8.4.4 and 9.2.0
changelogs) relaxed the eligibility rule from "single-table query" to "single table in
the *original* query, no aggregate functions, access method used only for duplicate
removal". Semijoin/antijoin transformation, however, introduces precisely the kind of
condition the invariant forbids: a join condition `a0.c1 = s1.c4` on a post-prefix key
part of the chosen index, which cannot be pushed into the scan and must be evaluated
above it. The relaxed eligibility test does not exclude this case.
### Scope
* Affects `DISTINCT` and `GROUP BY` without aggregate functions (both verified).
* Adding an aggregate function disables the optimization and yields correct results —
which conveniently confirms how many rows really qualify (99 per group in case B).
* Triggered when the semi/antijoin condition references a key part of the chosen index
that follows the grouping prefix. If the join column is not in that index, the access
method is not chosen (not covering) and results are correct.
* Independent of `NULL`s and of `DESC` index parts. Case B below uses `NOT NULL`
columns and a plain ascending index.
---
How to repeat:
### Case A — minimal, 5 rows
```sql
CREATE TABLE t (c1 INT, c2 INT, c4 BIGINT, KEY k0 (c2 DESC, c1 DESC)) ENGINE=InnoDB;
INSERT INTO t (c1, c2, c4) VALUES
(NULL,-3,12), (3,NULL,302), (6,NULL,451), (12,NULL,224), (NULL,NULL,807);
SELECT DISTINCT a0.c2 FROM t a0
WHERE NOT EXISTS (SELECT 1 FROM t s1 WHERE s1.c4 = a0.c1);
```
Actual result (8.0.41+):
```
+------+
| c2 |
+------+
| -3 |
+------+
1 row in set
```
Expected result:
```
+------+
| c2 |
+------+
| -3 |
| NULL |
+------+
2 rows in set
```
`IGNORE INDEX (k0)` returns the expected 2 rows. The rows that actually satisfy the
antijoin are `(c2,c1)` = `(-3,NULL) (NULL,6) (NULL,3) (NULL,NULL)`, so the `c2 = NULL`
group must be present in the result.
In index order for `k0 (c2 DESC, c1 DESC)` the `c2 = NULL` group begins with `c1 = 12`,
and `12` is present in `c4` — so the retained representative is filtered out and the
whole group disappears.
### Case B — no NULLs, ascending index, empty result instead of 2 rows
```sql
CREATE TABLE h (c1 INT NOT NULL, c2 INT NOT NULL, c4 BIGINT NOT NULL,
KEY k0 (c2 ASC, c1 ASC)) ENGINE=InnoDB;
-- group c2=0: c1 = 1000..1099 ; group c2=1: c1 = 2000..2099
-- c4 contains exactly 1000 and 2000, i.e. the smallest c1 of each group,
-- which is precisely the representative an ascending scan retains.
INSERT INTO h (c1, c2, c4)
WITH RECURSIVE seq(n) AS (SELECT 0 UNION ALL SELECT n+1 FROM seq WHERE n < 99)
SELECT 1000+n, 0, IF(n=0, 1000, 900000+n) FROM seq
UNION ALL
SELECT 2000+n, 1, IF(n=0, 2000, 800000+n) FROM seq;
ANALYZE TABLE h;
SELECT DISTINCT a0.c2 FROM h a0
WHERE NOT EXISTS (SELECT 1 FROM h s1 WHERE s1.c4 = a0.c1);
```
Actual result: `Empty set`. Expected result: 2 rows, `{0, 1}`.
99 of the 100 rows in each group satisfy the antijoin, as the aggregate variant (for
which the optimization is disabled) correctly reports:
```sql
SELECT a0.c2, COUNT(*) FROM h a0
WHERE NOT EXISTS (SELECT 1 FROM h s1 WHERE s1.c4 = a0.c1) GROUP BY a0.c2;
+----+----------+
| c2 | COUNT(*) |
+----+----------+
| 0 | 99 |
| 1 | 99 |
+----+----------+
```
`EXPLAIN ANALYZE` shows the access path emitting only 2 rows for the 200-row table, and
the antijoin then discarding both:
```
-> Nested loop antijoin (cost=1.6 rows=3) (actual time=0.185..0.185 rows=0 loops=1)
-> Covering index skip scan for deduplication on a0 using k0 (cost=1 rows=3) (actual time=0.0102..0.015 rows=2 loops=1)
-> Filter: (a0.c1 = `<subquery2>`.c4) (cost=0.002 rows=1) (actual time=0.0846..0.0846 rows=1 loops=2)
-> Single-row index lookup on <subquery2> using <auto_distinct_key> (c4 = a0.c1) (cost=66.3..66.3 rows=1) (actual time=0.0841..0.0841 rows=1 loops=2)
-> Materialize with deduplication (cost=66.3..66.3 rows=200) (actual time=0.166..0.166 rows=200 loops=1)
-> Filter: (s1.c4 is not null) (cost=20.2 rows=200) (actual time=0.00246..0.126 rows=200 loops=1)
-> Table scan on s1 (cost=20.2 rows=200) (actual time=0.00204..0.112 rows=200 loops=1)
```
The `GROUP BY` form is wrong in exactly the same way:
```sql
SELECT a0.c2 FROM h a0
WHERE NOT EXISTS (SELECT 1 FROM h s1 WHERE s1.c4 = a0.c1) GROUP BY a0.c2; -- Empty set
```
### Confirming that the retained row is the first row of the group
Probing the antijoin against one value at a time on table `h` shows that only the first
row of the group in index order can eliminate the group:
| probed `c1` value | position in group `c2=0` | result | group `c2=0` present? |
|---|---|---|---|
| 1000 | first | `{1}` | no |
| 1001 | second | `{0,1}` | yes |
| 1050 | middle | `{0,1}` | yes |
| 1099 | last | `{0,1}` | yes |
```sql
CREATE TABLE probe (c4 BIGINT NOT NULL) ENGINE=InnoDB;
TRUNCATE probe; INSERT INTO probe VALUES (1000); -- then 1001, 1050, 1099
SELECT DISTINCT a0.c2 FROM h a0 WHERE NOT EXISTS (SELECT 1 FROM probe s1 WHERE s1.c4 = a0.c1);
```
### Version bisect
Same script, official Docker images:
| Version | Case A (expect 2 rows) | Case B (expect 2 rows) | Access path for case B |
|---|---|---|---|
| 8.0.40 | 2 — correct | 2 — correct | `Index scan on a0 using k0` + temporary table with deduplication |
| 8.0.41 | 1 — **wrong** | 0 — **wrong** | `Covering index skip scan for deduplication` |
| 8.4.11 | 1 — **wrong** | 0 — **wrong** | `Covering index skip scan for deduplication` |
| 9.4.0 | 1 — **wrong** | 0 — **wrong** | `Covering index skip scan for deduplication` |
| 9.7.1 | 1 — **wrong** | 0 — **wrong** | `Covering index skip scan for deduplication` |
---
Suggested fix:
The eligibility condition for using the group skip scan as a duplicate-removal access
method needs one additional check beyond "single original table, no aggregate functions":
> The access method may only be used if no column of the table other than the grouping
> key columns is referenced by any condition evaluated above the access path.
Concretely, when the range optimizer proposes a group skip scan whose purpose is
duplicate removal, reject the candidate if any key part of the index following the
grouping prefix (or any other column of the table) is referenced by a semijoin/antijoin
condition, or by any residual filter that is not itself incorporated into the scan's
range conditions. In such cases the pre-8.0.41 plan — a full index scan feeding a
temporary table with deduplication — must be used, because deduplication may not be
performed before the condition has been applied.
A less restrictive alternative that preserves most of the performance benefit of the
Bug #112362 fix: keep using the skip scan, but extend the grouping prefix to include
every index key part referenced by conditions above the access path (here, dedup on
`(c2, c1)` rather than on `(c2)` alone), and let the existing final deduplication step
remove the remaining duplicates. `SELECT DISTINCT a0.c2, a0.c1 ...` on case B already
returns the correct 198 rows, confirming this variant is sound.
Description: A `SELECT DISTINCT c2 ... WHERE NOT EXISTS (...)` query silently returns too few rows — in the worst case an empty result set where a large number of rows qualify — when the optimizer picks the `Covering index skip scan for deduplication` access method. The access method emits **exactly one representative row per group of the grouping column**, namely the first row of the group in index order. The antijoin condition, which references `c1` (a key part of the *same* index following the grouping prefix), is only evaluated **above** that access path. Therefore, for each group, the condition is tested against a single arbitrary member of the group instead of against all of its rows. This replaces the required existential semantics ``` { g : EXISTS r IN R such that r.c2 = g AND P(r) } ``` with a single-witness test ``` { g : P(first_row_in_index_order_of_group(g)) } ``` Whenever the first row of a group fails `P` but some other row of the group satisfies it, the whole group is wrongly dropped from the result. Equivalently, in relational algebra terms: the plan computes `σ_P(δ_c2(R))` while the query means `δ_c2(σ_P(R))`. Pushing a deduplication `δ_G` below a filter `σ_P` is only valid when `P` is functionally determined by `G`. Here `P` depends on `c1`, which varies within a `c2` group, so the transformation is unsound. ### Why this is a regression introduced in 8.0.41 The group skip scan was historically restricted to single-table queries. In that setting the invariant holds, because any condition on the index key parts following the grouping prefix is incorporated **into** the scan by the range optimizer, so the scan performs an existential search inside each group. This is directly observable — the following returns the correct `{0}` even though `c1 = 1099` matches only the *last* row of group `c2 = 0`: ``` mysql> EXPLAIN FORMAT=TREE SELECT DISTINCT c2 FROM h WHERE c1 = 1099; -> Filter: (h.c1 = 1099) (cost=1 rows=3) -> Covering index skip scan for deduplication on h using k0 (cost=1 rows=3) mysql> SELECT DISTINCT c2 FROM h WHERE c1 = 1099; +----+ | c2 | +----+ | 0 | +----+ ``` The fix for Bug #112362 / Bug #35842412 (documented in the 8.0.41, 8.4.4 and 9.2.0 changelogs) relaxed the eligibility rule from "single-table query" to "single table in the *original* query, no aggregate functions, access method used only for duplicate removal". Semijoin/antijoin transformation, however, introduces precisely the kind of condition the invariant forbids: a join condition `a0.c1 = s1.c4` on a post-prefix key part of the chosen index, which cannot be pushed into the scan and must be evaluated above it. The relaxed eligibility test does not exclude this case. ### Scope * Affects `DISTINCT` and `GROUP BY` without aggregate functions (both verified). * Adding an aggregate function disables the optimization and yields correct results — which conveniently confirms how many rows really qualify (99 per group in case B). * Triggered when the semi/antijoin condition references a key part of the chosen index that follows the grouping prefix. If the join column is not in that index, the access method is not chosen (not covering) and results are correct. * Independent of `NULL`s and of `DESC` index parts. Case B below uses `NOT NULL` columns and a plain ascending index. --- How to repeat: ### Case A — minimal, 5 rows ```sql CREATE TABLE t (c1 INT, c2 INT, c4 BIGINT, KEY k0 (c2 DESC, c1 DESC)) ENGINE=InnoDB; INSERT INTO t (c1, c2, c4) VALUES (NULL,-3,12), (3,NULL,302), (6,NULL,451), (12,NULL,224), (NULL,NULL,807); SELECT DISTINCT a0.c2 FROM t a0 WHERE NOT EXISTS (SELECT 1 FROM t s1 WHERE s1.c4 = a0.c1); ``` Actual result (8.0.41+): ``` +------+ | c2 | +------+ | -3 | +------+ 1 row in set ``` Expected result: ``` +------+ | c2 | +------+ | -3 | | NULL | +------+ 2 rows in set ``` `IGNORE INDEX (k0)` returns the expected 2 rows. The rows that actually satisfy the antijoin are `(c2,c1)` = `(-3,NULL) (NULL,6) (NULL,3) (NULL,NULL)`, so the `c2 = NULL` group must be present in the result. In index order for `k0 (c2 DESC, c1 DESC)` the `c2 = NULL` group begins with `c1 = 12`, and `12` is present in `c4` — so the retained representative is filtered out and the whole group disappears. ### Case B — no NULLs, ascending index, empty result instead of 2 rows ```sql CREATE TABLE h (c1 INT NOT NULL, c2 INT NOT NULL, c4 BIGINT NOT NULL, KEY k0 (c2 ASC, c1 ASC)) ENGINE=InnoDB; -- group c2=0: c1 = 1000..1099 ; group c2=1: c1 = 2000..2099 -- c4 contains exactly 1000 and 2000, i.e. the smallest c1 of each group, -- which is precisely the representative an ascending scan retains. INSERT INTO h (c1, c2, c4) WITH RECURSIVE seq(n) AS (SELECT 0 UNION ALL SELECT n+1 FROM seq WHERE n < 99) SELECT 1000+n, 0, IF(n=0, 1000, 900000+n) FROM seq UNION ALL SELECT 2000+n, 1, IF(n=0, 2000, 800000+n) FROM seq; ANALYZE TABLE h; SELECT DISTINCT a0.c2 FROM h a0 WHERE NOT EXISTS (SELECT 1 FROM h s1 WHERE s1.c4 = a0.c1); ``` Actual result: `Empty set`. Expected result: 2 rows, `{0, 1}`. 99 of the 100 rows in each group satisfy the antijoin, as the aggregate variant (for which the optimization is disabled) correctly reports: ```sql SELECT a0.c2, COUNT(*) FROM h a0 WHERE NOT EXISTS (SELECT 1 FROM h s1 WHERE s1.c4 = a0.c1) GROUP BY a0.c2; +----+----------+ | c2 | COUNT(*) | +----+----------+ | 0 | 99 | | 1 | 99 | +----+----------+ ``` `EXPLAIN ANALYZE` shows the access path emitting only 2 rows for the 200-row table, and the antijoin then discarding both: ``` -> Nested loop antijoin (cost=1.6 rows=3) (actual time=0.185..0.185 rows=0 loops=1) -> Covering index skip scan for deduplication on a0 using k0 (cost=1 rows=3) (actual time=0.0102..0.015 rows=2 loops=1) -> Filter: (a0.c1 = `<subquery2>`.c4) (cost=0.002 rows=1) (actual time=0.0846..0.0846 rows=1 loops=2) -> Single-row index lookup on <subquery2> using <auto_distinct_key> (c4 = a0.c1) (cost=66.3..66.3 rows=1) (actual time=0.0841..0.0841 rows=1 loops=2) -> Materialize with deduplication (cost=66.3..66.3 rows=200) (actual time=0.166..0.166 rows=200 loops=1) -> Filter: (s1.c4 is not null) (cost=20.2 rows=200) (actual time=0.00246..0.126 rows=200 loops=1) -> Table scan on s1 (cost=20.2 rows=200) (actual time=0.00204..0.112 rows=200 loops=1) ``` The `GROUP BY` form is wrong in exactly the same way: ```sql SELECT a0.c2 FROM h a0 WHERE NOT EXISTS (SELECT 1 FROM h s1 WHERE s1.c4 = a0.c1) GROUP BY a0.c2; -- Empty set ``` ### Confirming that the retained row is the first row of the group Probing the antijoin against one value at a time on table `h` shows that only the first row of the group in index order can eliminate the group: | probed `c1` value | position in group `c2=0` | result | group `c2=0` present? | |---|---|---|---| | 1000 | first | `{1}` | no | | 1001 | second | `{0,1}` | yes | | 1050 | middle | `{0,1}` | yes | | 1099 | last | `{0,1}` | yes | ```sql CREATE TABLE probe (c4 BIGINT NOT NULL) ENGINE=InnoDB; TRUNCATE probe; INSERT INTO probe VALUES (1000); -- then 1001, 1050, 1099 SELECT DISTINCT a0.c2 FROM h a0 WHERE NOT EXISTS (SELECT 1 FROM probe s1 WHERE s1.c4 = a0.c1); ``` ### Version bisect Same script, official Docker images: | Version | Case A (expect 2 rows) | Case B (expect 2 rows) | Access path for case B | |---|---|---|---| | 8.0.40 | 2 — correct | 2 — correct | `Index scan on a0 using k0` + temporary table with deduplication | | 8.0.41 | 1 — **wrong** | 0 — **wrong** | `Covering index skip scan for deduplication` | | 8.4.11 | 1 — **wrong** | 0 — **wrong** | `Covering index skip scan for deduplication` | | 9.4.0 | 1 — **wrong** | 0 — **wrong** | `Covering index skip scan for deduplication` | | 9.7.1 | 1 — **wrong** | 0 — **wrong** | `Covering index skip scan for deduplication` | --- Suggested fix: The eligibility condition for using the group skip scan as a duplicate-removal access method needs one additional check beyond "single original table, no aggregate functions": > The access method may only be used if no column of the table other than the grouping > key columns is referenced by any condition evaluated above the access path. Concretely, when the range optimizer proposes a group skip scan whose purpose is duplicate removal, reject the candidate if any key part of the index following the grouping prefix (or any other column of the table) is referenced by a semijoin/antijoin condition, or by any residual filter that is not itself incorporated into the scan's range conditions. In such cases the pre-8.0.41 plan — a full index scan feeding a temporary table with deduplication — must be used, because deduplication may not be performed before the condition has been applied. A less restrictive alternative that preserves most of the performance benefit of the Bug #112362 fix: keep using the skip scan, but extend the grouping prefix to include every index key part referenced by conditions above the access path (here, dedup on `(c2, c1)` rather than on `(c2)` alone), and let the existing final deduplication step remove the remaining duplicates. `SELECT DISTINCT a0.c2, a0.c1 ...` on case B already returns the correct 198 rows, confirming this variant is sound.