| Bug #121026 | Semijoin duplicate-weedout missing from plan: EXISTS + NOT EXISTS returns duplicate rows | ||
|---|---|---|---|
| Submitted: | 29 Jul 3:26 | Modified: | 31 Jul 11:37 |
| Reporter: | hiroki nagai | Email Updates: | |
| Status: | Verified | Impact on me: | |
| Category: | MySQL Server: Optimizer | Severity: | S2 (Serious) |
| Version: | 8.0.42, 8.0.46, 8.4.9, 9.7.2 | OS: | Any (official mysql Docker images, linux/arm64 and linux/amd64) |
| Assigned to: | CPU Architecture: | Any | |
| Tags: | duplicateweedout, semijoin, wrong result | ||
[29 Jul 3:26]
hiroki nagai
[29 Jul 3:57]
hiroki nagai
[Part 1/2: correction to the necessary conditions + smaller test case]
Correction to the "necessary conditions" list in the original report, plus a
smaller test case. A root-cause analysis from reading the 8.0.42 source follows
in the next comment.
(Note on the database name: the script in the original report creates
`weedout_dup`, but the `EXPLAIN` outputs pasted there were taken in a database
named `repro_check`, which is why the `ref` column shows `repro_check.b.id`.
Everything below consistently uses `repro_check`.)
1. The list of necessary conditions in the original report is wrong
-------------------------------------------------------------------
I listed four conditions as each being necessary. Two of them are not. They were
confounds: removing either one happened to make the cost model pick FirstMatch
instead of duplicate-weedout on that particular dataset, so the wrong result
disappeared for a reason unrelated to the condition itself.
With the strategy pinned to duplicate-weedout in every case, measured on 8.0.42:
Q1 from the original report -> 225 rows (correct: 1)
Q1 with a.id IN (1) replaced by a range predicate -> 225 rows (correct: 1)
Q1 with the filter on a removed entirely -> 675 rows (correct: 3)
Q1 with one nested EXISTS removed -> 15 rows (correct: 1)
Flat single EXISTS, three tables only -> 5 rows (correct: 1)
So neither the primary-key constant filter nor the second nested EXISTS is
required. The revised list of necessary conditions is:
- one EXISTS subquery (nesting is not required)
- one correlated NOT EXISTS subquery
- a duplicate-weedout range whose first table is the antijoin table
Note the third row: with no filter on `a` at all, the result is 675 = 3 x 225,
i.e. exactly (number of outer rows) x (fan-out). No deduplication of any kind is
taking place. This matters for the root-cause analysis in the next comment.
2. Smaller test case: three tables, one EXISTS, one NOT EXISTS
--------------------------------------------------------------
DROP DATABASE IF EXISTS repro_check;
CREATE DATABASE repro_check;
USE repro_check;
CREATE TABLE a (id INT PRIMARY KEY);
CREATE TABLE b (id INT PRIMARY KEY, a_id INT, KEY(a_id));
CREATE TABLE e (a_id INT, KEY(a_id));
INSERT INTO a VALUES (1),(2),(3);
INSERT INTO b VALUES (1,1),(2,1),(3,1),(4,1),(5,1),
(6,2),(7,2),(8,2),(9,2),(10,2),
(11,3),(12,3),(13,3),(14,3),(15,3);
-- e is left empty
ANALYZE TABLE a, b, e;
SET SESSION optimizer_switch='firstmatch=off,loosescan=off,materialization=off';
-- Returns 5 rows. Must return 1.
SELECT * FROM a
WHERE EXISTS (SELECT * FROM b WHERE a.id = b.a_id)
AND NOT EXISTS (SELECT 1 FROM e WHERE e.a_id = a.id)
AND a.id IN (1);
Five identical copies of the single row (1). Table `e` is empty; deleting the
NOT EXISTS line makes the query return the correct single row. Traditional
EXPLAIN shows `Start temporary` on `e` and `End temporary` on `b`; EXPLAIN
ANALYZE shows no weedout operator and a `Limit: 1 row(s)` above the lookup on
`e`, inside the antijoin.
This is a much more ordinary query shape than the one in the original report:
a single-table select with one EXISTS permission-style predicate and one
NOT EXISTS exclusion predicate. That combination is what ORMs generate
routinely, which suggests the exposure is considerably wider than the original
five-table case implied.
[29 Jul 3:57]
hiroki nagai
[Part 2/2: root cause in the 8.0.42 source + suggested fix]
The following is from reading the 8.0.42 source. I have not confirmed it under a
debugger, but it accounts for every measurement in the previous comment,
including the 675 case.
Step 1: the weedout range starts at the antijoin table `e` (`Start temporary`),
and the outer table `a` sits in the prefix, before the range. I originally
attributed this to `a` being a const table. That was wrong: the wrong result
persists when `a` is read through a range scan. `a` is outside the weedout
range because of its position in the plan, not its access type, so it is never
a candidate for the deduplication key either way.
Step 2: setup_semijoin_dups_elimination() (sql/sql_select.cc) walks the range
and collects the tables whose row IDs form the deduplication key, via
sj_table_is_included(), which starts with:
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab) {
if (join_tab->emb_sj_nest) return false;
`b` is excluded because it is semijoin-inner. `e` is excluded too, because
antijoin nests are marked with the same flag as semijoin nests: sql/table.h
distinguishes them only via is_sj_nest()/is_aj_nest() on top of the shared
m_is_sj_or_aj_nest, and JOIN::set_semijoin_embedding() sets emb_sj_nest to
"the closest semi-join or anti-join nest". (For the same reason, the
assert(tab_in_sj_nest) at the top of the SJ_OPT_DUPS_WEEDOUT case passes on
debug builds, so the unusual shape of this range - first table not
semijoin-inner - is not caught there either.) With `a` outside the range and
both in-range tables excluded, the key table list is empty.
Step 3: create_sj_tmp_table() (sql/sql_select.cc) infers confluence from the
accumulated row ID width:
if (jt_rowid_offset) { /* Temptable has at least one rowid */
sjtbl->is_confluent = false;
...
} else {
/*
This is confluent case where the entire subquery predicate does
not depend on anything at all, ie this is
WHERE const IN (uncorrelated select)
*/
sjtbl->is_confluent = true;
The comment states what the branch was written for: an uncorrelated predicate.
That is not the situation here - the predicates are correlated and the semijoin
does fan out; the key is empty only because no table in the range was eligible
to contribute a row ID. The two cases are indistinguishable at this point, and
the second is silently treated as the first.
Step 4: this is where the deduplication is actually lost. In FindSubstructure()
(sql/sql_executor.cc), the helper ConnectJoins() uses to classify each table
range before building iterators:
if (is_outer_join && is_weedout) {
if (outer_join_end > weedout_end) {
is_weedout = false; // handled at a lower level
} else {
if (qep_tab->flush_weedout_table->is_confluent) {
// We have the case where the right side of an outer join is a
// confluent weedout. The weedout will return at most one row, so
// replace the weedout with LIMIT 1.
*add_limit_1 = true;
} else {
MarkUnhandledDuplicates(qep_tab->flush_weedout_table, this_idx,
weedout_end, unhandled_duplicates);
}
is_weedout = false;
}
}
is_outer_join is true here because `e` is the first inner table of the outer
join used to execute the antijoin. When the non-confluent path (or the
analogous is_semijoin branch below) drops a weedout, it calls
MarkUnhandledDuplicates() first, so the top level installs a compensating
weedout. The confluent shortcut does not: it sets *add_limit_1 and records
nothing. Combined with step 3:
- the weedout is dropped,
- no compensating weedout is added at the top level,
- ConnectJoins() adds the LIMIT 1 to the inner side of the antijoin -
the "Limit: 1 row(s)" above the lookup on `e` in the broken plans.
The comment's premise, "The weedout will return at most one row", is false
here, because is_confluent was set for the wrong reason in step 3.
Why the 675 case confirms this: if the substituted LIMIT 1 wrapped the weedout
range subtree, the no-filter query would return one row per outer row, i.e. 3.
If it wrapped the whole join output, it would return 1. The measured value is
675 = 3 x 225, the full undeduplicated product. So the LIMIT 1 lands somewhere
that constrains nothing (the inner side of an antijoin against an empty table),
and no deduplication happens at any level - consistent with step 4, and not
with the weedout merely being misplaced.
Suggested fix
-------------
(a) The root fix, in create_sj_tmp_table(): stop inferring confluence from
jt_rowid_offset == 0. Pass the genuinely-confluent case
(WHERE const IN (uncorrelated select)) in explicitly from the caller, which
knows it. An empty deduplication key arising from an ineligible range is a
different condition and should leave is_confluent false. With is_confluent
false, step 4 takes the existing else branch, MarkUnhandledDuplicates() runs,
and the top level installs a weedout keyed on the tables outside the range -
`a` - which is the correct key. No new mechanism is needed.
(b) A narrower, defensive change, in FindSubstructure(): have the is_confluent
shortcut also call MarkUnhandledDuplicates(), making the is_outer_join branch
symmetric with the is_semijoin branch below it.
I would expect (a) to be the correct fix. (b) alone would restore correct
results in this case - the compensating weedout keyed on `a` performs the
missing deduplication - but it over-corrects the genuinely confluent case,
where the LIMIT 1 substitution is already correct and (b) would additionally
install a redundant top-level weedout. A third possibility, extending the
weedout range to begin before the antijoin table so it includes a key-eligible
table, would also avoid the empty-key condition, but it changes plan shapes
more broadly and I have not evaluated the consequences.
This is a description of the defect rather than a patch; I have not signed the
OCA. If a patch would be useful I am willing to look into arranging that, but I
would want to confirm the intended direction first, since the choice between
(a) and the range-extension option is not one I can make from outside.
[31 Jul 11:37]
Chaithra Marsur Gopala Reddy
Hi hiroki nagai, Thank you for the test case. Verified as described.
