Details
-
Task
-
Status: In Review (View Workflow)
-
Major
-
Resolution: Unresolved
Description
EXISTS-to-IN optimization performs trivial correlation detection and removal.
MySQL 8 has got it too, but in addition to EXISTS subqueries, they perform de-correlation also for IN subqueries. This allows them to use Materialization strategy for trivially-correlated IN- subqueries:
create table ten(a int primary key);
|
insert into ten values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
|
create table t1 (a int, b int, c int);
|
insert into t1 select a,a,a from ten;
|
create table t2 select * from t1;
|
explain select * from t1 where a in (select a from t2 where t1.b=t2.b);
|
id select_type table partitions type possible_keys key key_len ref rows filtered Extra
|
1 SIMPLE t1 NULL ALL NULL NULL NULL NULL 10 100.00 Using where
|
1 SIMPLE <subquery2> NULL eq_ref <auto_distinct_key> <auto_distinct_key> 10 test.t1.a,test.t1.b 1 100.00 NULL
|
2 MATERIALIZED t2 NULL ALL NULL NULL NULL NULL 10 100.00 NULL
|
Attachments
Issue Links
- blocks
-
-
- Open
-
- is blocked by
-
MDEV-30073 Wrong result on 2nd execution of PS for query with NOT EXISTS
-
- In Progress
-
- relates to
-
MDEV-3881
Endless loop for query with EXISTS predicate using outer reference to view
-
- Closed
-
-
-
- Open
-
-
-
- Closed
-
-
-
- Open
-
Activity
This is a reply to a message from igor on slack about the
relation between this task and MDEV-3881. Messages in commits to
MDEV-22534 reference MDEV-3881 because the issues seen in MDEV-3881
are encountered in MDEV-22534. They have the same symptom, but
nobody can say for sure whether it is the same issue caused by the
same problem because MDEV-3881 is so ancient. Now let's assume it is
the same.
Looking at the fix for MDEV-3881, I cannot verify it myself whether
the commit did fix it. First, it is not even clear which commit was
meant as a fix for MDEV-3881. I suspect it is
e3ac306157ab9ade137c9afc9fff270a2f50d7ec[0] because that is where
the MDEV-3881 test case was added. But as you can see, it was also
the commit that introduced the exists-to-in transformation. The
bug relied on exists-to-in to manifest, so in this case, it is not
even possible to determine which version of the feature that caused
the bug, let alone studying the fix. Second, it was a commit from 10
years ago, and even the author could not recall what was the fix,
see the thread[1].
On the face value, my suspicion is that the bug was not fixed, and
we have just been relying on a workaround (see below) to avoid it.
Or maybe it was fixed then, but some new changes over the last 10
years caused a regression (e.g. the Gallina commit mentioned by
psergei). In any case, I don't think archaeology helps fix this
bug. In the current codebase, the exists-to-in code relies on a
(perhaps unintentional) workaround to avoid the bug, which is, when
the subselect is a toplevel NOT, we need to AND the new IN subquery
with IS NOT NULLs because 3-value logic is funny[2]. When doing so,
the exists2in processor constructs the AND item in different orders
depending on the number of picked-out equalities. If there is only
one, then the AND item has the IS NOT NULL item as the first
argument. If there is more than one, then the AND item has the IN
subquery as the first argument. There's no reason the two cases
should be treated differently, and the infinite loop happens when we
try to unify the two cases and always have the IN subquery as the
first argument, see for example [1]. Note that this was already the
case in the initial exists-to-in commit[0]. I also made a minimal
change that has nothing to do with the main task in MDEV-22534 to
reproduce the issue[3], just run the test
main.subselect_exists2in that contains the MDEV-3881 test. We
can keep the workaround in the new transformation introduced in this
ticket, which is the case in earlier patches, but I was told by
psergei and monty that it is generally not a good idea have a
workaround like this unless there is a compelling reason.
By the way, the commit [3] (and [5] for a 10.4 version) below also
answers the following question in the previous comment. The testcase
is main.subselect_exists2in, more specifically the MDEV-3881
part in that test, also quoted in comment[4] above.
> ** The bug is apparently in the old (pre-MDEV-22534) code. Can one
> construct a testcase for it?
As to the question why swapping the orders matter, here's an
explanation, using the self-contained example given by psergei
above.
Exists2in transforms NOT EXISTS ( SELECT * FROM t3 WHERE c = b )
to
!(Item_in_optimizer and Item_func_is_not_null) # patched version
or
!(Item_func_is_not_null and Item_in_optimizer) # original version
where we have the following structures for the two items in the
conjunction
Item_func_is_not_null(
|
Item_direct_ref( // denote this r
|
Item_direct_view_ref( // denote this vr
|
Item_field("t2.b") // denote this fld
|
)
|
)
|
and
Item_in_optimizer(
|
Item_direct_view_ref( // same vr
|
Item_field("t2.b") // same fld
|
),
|
...
|
)
|
In Item_cond::propagate_equal_fields() for the conjunction, it
iterates over the two items and call propagate_equal_fields() on
them one by one, and whatever side effects happen during these
calls, the last call "wins". So in the patched version,
r->propagate_equal_fields() is called after and we end up with fld
rather than vr participating in the multiple equality which is
wrong. In the original version, vr->propagate_equal_fields() is
called after and we end up with vr participating which is correct.
If we can make it always correct as we do in patches in this ticket,
then we don't have to worry about the order.
[0] https://github.com/MariaDB/server/commit/e3ac306157ab9ade137c9afc9fff270a2f50d7ec
[1] https://mariadb.slack.com/archives/C021E77G7K2/p1690952975445929
[2]
https://lists.mariadb.org/hyperkitty/list/developers@lists.mariadb.org/message/CEPJCC7GCZ4H44L276AFRIUB7LYIJOPI/
[3] https://github.com/MariaDB/server/commit/02da5af0aa1
[4]
https://jira.mariadb.org/browse/MDEV-22534?focusedCommentId=265762&page=com.atlassian.jira.plugin.system.issuetabpanels%3Acomment-tabpanel#comment-265762
[5] https://github.com/MariaDB/server/commit/8c0835459aa
After digesting psergei's comment above, and discussions with him,
here is an explanation why not allowing Item_fields to participate in
multiple equalities when they are referenced by Item_direct_view_ref
fixes the self-reference bug (provided some assumption mentioned at the
end of this comment holds).
The job of Item::propagate_equal_fields() is to assign a multiple
equality to the item, or make it so field-like items participate in
the correct multiple equalities. Here we say an item i participates in
multiple equality e if i->item_equal == e, and we say i does not
participate in any multiple equality if i->item_equal == NULL.
We say an Item_direct_view_ref vr points to a Item_field
field if vr->real_item() == field. Multiple
Item_direct_view_ref's in different contexts may point to the same
Item_field. To avoid joining disjoint equalities, when an
Item_field is pointed to by an Item_direct_view_ref, the
former should no longer participate in a multiple equality, but the
latter should. For example, consider {{alias.a = t.col1 OR alias.a =
t.col2}}. If the field underlying alias.a participates in both
multiple equalities, the two multiple equalities will join into one
with three elements all equal to each other, which is a logical error.
(It would be nice to have a test case for this, though.) However, this
is not the case in the codebase, the violation of this rule causes the
bug, and the rectification fixes the bug provided certain assumptions
hold.
The job of Item::replace_equal_field() is to replace a field-like item
by an equal field-like item. When the Item is an Item_field, it
replaces itself by the const or first item of the multiple equality it
participates, if any and if it agrees with cond_equal. When the Item i
is an Item_ref, including Item_direct_view_ref, in
Item_ref::transform(.., replace_equal_field, ..), it calls the
transformer on the item it derefs to (i.e. *i->ref).
Item *new_item= (*ref)->transform(thd, transformer, arg); /* 1 */ |
And if the transformer returns a new item that is different from
*i->ref, we make i deref to this new item.
if (*ref != new_item) |
thd->change_item_tree(ref, new_item); /* 2 */ |
After that we replace call replace_equal_field on i itself.
return (this->*transformer)(thd, arg); /* 3 */ |
So when we have Item_direct_view_ref vr1 that derefs to an Item_field
field, i.e. *vr1->ref == field, and field participates in a
multiple equality whose const item is another Item_direct_view_ref vr2
that not only also derefs to field, but also has the same ref field as
vr1 (vr1->ref == vr2->ref), step 1 above returns vr2, and step 2
above makes vr1 deref to vr2, causing a self-reference:
*vr2->ref == *vr1->ref == vr2.
Now, if we do not allow Item_field to participate in a multiple
equality (i.e. when vr1->ref == field, we do {{vr1->item_equal=
item_equal}} and field->item_equal = NULL), then the
self-reference would not occur in this case. In step 1 above, the
right hand side will evaluate to Item_field, because its cond_equal is
NULL.
Item *Item_field::replace_equal_field(THD *thd, uchar *arg)
|
{
|
REPLACE_EQUAL_FIELD_ARG* param= (REPLACE_EQUAL_FIELD_ARG*)arg;
|
if (item_equal && item_equal == param->item_equal) |
{
|
...
|
}
|
return this; |
}
|
It will therefore skip step 2, and in step 3 above, vr1 temporarily
lets field participate in the multiple equality, and we get vr2 as a
result, which is then used to replace vr1 directly, rather than
*vr1->ref.
We can also answer the following question in a previous comment:
> Igor: doesn't Item_direct_view_ref::propagate_equal_items() have the
> same bug? what happens if there are nested views?
If there are nested views, say *vr1->ref == vr2,
*vr2->ref == field, vr1->item_equal->get_const() == vr3,
vr1->item_equal == cond_equal->current_level->item_equal,
and {{vr2->item_equal == field->item_equal == NULL}
then the following happens, and vr3 replaces vr1, and no
self-reference occurs.
vr1->transform: new_item= vr2->transform(...)
|
vr2->transform: new_item= field->transform(...)
|
field->replace_equal_field: returns itself because its item_equal is NULL
|
vr2->replace_equal_field: returns itself because its item_equal is NULL
|
vr1->replace_equal_field: temporarily lets field participate and returns vr3
|
Because an Item_direct_view_ref does not allow anything downstream
to participate in a multiple equality, anything returned by the
replace_equal_field call on an Item_field would replace the
top-level Item_direct_view_ref. As such, no self-reference occurs.
Anyway here are the latest commits. I wonder how important it is to
add a test covering nested Item_direct_view_ref and one that shows
logical errors may occur if an Item_field participates in a multiple
equality when there is more than one Item_direct_view_ref pointing
to it. What do you think psergei?
1084af9e91a MDEV-22534 Fix self-referencing Item_direct_view_ref
|
4d72160ae4e MDEV-22534 Simplify the workaround for MDEV-31269
|
f393ecea3af MDEV-22534 Decorrelate IN subquery
|
I think the plan should be:
1. Have the self-reference fix as the first commit and push it to
10.4, since 10.4 is affected
2. wait for there to be an 11.3 version of the MDEV-30073 patch so
that we can test our main patch on top
3. wait for the MDEV-30073 patch to have made it to 11.3, get rid of
our MDEV-31269 workaround and push our main patch to 11.3
OTOH our patch does not make the problem in MDEV-31269 worse, so
maybe step 2 and 3 are redundant, but then again none of the
workarounds has gained consensus support...
On why Item_direct_ref's are used in the creation of the extra "IS
NOT NULL" items.
If we replace them with Item_ref's, then MDEV-3906 resurfaces,
i.e. the testcase in main.subselect_exists2in corresponding to
MDEV-3906 fails with a crash.
Like MDEV-3881, the fix of MDEV-3906 is "included" in the original
commit adding the exists2in transformation.
e3ac306157ab9ade137c9afc9fff270a2f50d7ec
|
Commit: unknown <sanja@montyprogram.com>
|
CommitDate: Tue Feb 26 01:20:17 2013 +0200
|
|
|
[NOT] EXISTS to IN transformation.
|
sanja's last comment in MDEV-3906[1] seems to suggest that
Item_direct_ref was used to fix this issue.
Interestingly, if we apply the more crude workaround for MDEV-31269,
then the MDEV-3906 regression is gone:
80a094f1355 * upstream/bb-11.3-mdev-22534-item-ref-no-direct MDEV-22534 [demo] Use Item_ref instead of Item_direct_ref
|
fc1027ef992 * MDEV-22534 Simplify the workaround for MDEV-31269
|
f393ecea3af * MDEV-22534 Decorrelate IN subquery
|
Given this, and the fact that MDEV-3906 is also a 2nd PS crash issue,
I also made the changes of using Item_ref on top of a commit for
MDEV-30073, and the regression also does not appear:
8dffff917bc upstream/bb-10.4-mdev-31269-3906-fixed-by-mdev-30073 MDEV-22534 [demo] MDEV-30073 fixes MDEV-31269 and MDEV-3906
|
34083cf34bc upstream/bb-10.4-mdev-30073 MDEV-30073 Wrong result on 2nd execution of PS for query with NOT EXISTS
|
So it seems:
- MDEV-30073 fixes both 2nd PS issues, and thus allows the use of
Item_ref in the creations of extra IS NOT NULL's in
exists2in/decorrelation transformation - Without the fix of MDEV-30073, the only way to pass all tests,
including the ps-protocol ones, is to check for free list
intersections during ps execution, as well as keep the
Item_direct_ref with the infinite cycle fix - The infinite cycle fix is probably still needed because the
IS_NOT_NULL item creations are not the only place using
Item_direct_ref. Though if we rely on the MDEV-30073 fix, this could
be separated out as an independent bug, if a testcase can be
created.
There are two ways moving forward:
1. Block this ticket with MDEV-30073, and use Item_ref and no
workaround in our patches once MDEV-30073 is fixed
2. Use the Item_direct_ref, the infinite cycle fix, and either the
fourth or the fifth workaround options in the previous comment[2].
Status update from the calls this week:
MDEV-22434code is rebased on top of that commit (but didn't clarify what for?)