Re: Query containing IN subquery with OR in the where clause returns a wrong result
== Analysis ==

Equality propagation converts the WHERE clause into this:

(multiple equal(7, t1.a, t2.a) or (t2.b <= 1))
and
multiple equal(t1.a, t2.a)

This is ok.

Then, equality substitution produces this WHERE clause:

(t1.a = 7) or (t2.b <= 1)

we dont expect this kind of WHERE clauses to be produced when
SJ-Materialization-Lookup strategy is used.

With that strategy, we expect that the WHERE clause can be broken into two
AND-parts:

• Part#1. depend only on SJ-inner tables
• Part#2. depend only on SJ-outer tables

The only thing joining the two parts is the IN-equality. IN-equality is not
put into the WHERE condition, it is generated and checked inside the
SJ-Materialization code.

However, make_join_select() gets this clause:

(t1.a = 7) or (t2.b <= 1)

which can only be checked when one has both t1.a and t2.b. This never happens,
so make_join_select() is unable to attach this condition anywhere, and it is
never checked.

Re: Query containing IN subquery with OR in the where clause returns a wrong result
Some fix of this bug was pushed into mysql-5.6 (see the fix for bug #13414014).
I did not review this fix, so I cannot say anything about about its validity.

Re: Query containing IN subquery with OR in the where clause returns a wrong result
== Analysis continued ==

Equality propagation assumes certain ordering of tables, and tries to
move make all substitutions to evaluate as early as possible.

Graphically, if we draw join order like this:

>tb1->-tbl2->-tbl3-...

equality propagation will try pushing conditions to the left. The problem
with semi-joins (or bushy joins in general) is that there is no global
ordering anymore.

If we take a query

select * from ot1,ot2,ot3,ot4... where col in (select ... from it1, it2)

and its SJM query plan:

>ot1-ot2>------------(sjm)>ot3--ot4-....

it1>it2>+

then one can push the condition left along the top line through tables otX, or
go down to tables itX, and follow to the left along the lower level.

What equality substitution currently does is to assume the ordering of
(ot1, ot2, it1, it2, sjm, ot3, ...) and mostly ignore the fact that there are
multiple ways to go to the left.

This almost works, because materialization is only applied to un-
correlated queries, which gives us warranty that there are no expressions
that refer to both an otX.col and an itY.col.
The only exception is the IN-equality, which usually has the form of

otX.col=itY.col

presense of equalities of this form changes a lot.

Re: Query containing IN subquery with OR in the where clause returns a wrong result
=== Deficiency ===

First, the approach "move each condition as much as possible to the left"
doesn't guarantee maximum possible filtering anymore. When one is following left
and he reaches the (sjm) split, he should not take one way. He should use both!

Consider the queries:

Q1 select * from t1 where t1.col in (select t2.col from t2 where cond(t2.col))
Q2 select * from t1 where t1.col in (select t2.col from t2) and cond(t1.col)

Suppose they both are executed with this query plan:

id select_type table type
1 PRIMARY t1 ALL
1 PRIMARY <subquery2> eq_ref
2 MATERIALIZED t2 ALL

it is apparent that, for both queries

1. cond(t1.col) should be attached to table t1
2. cond(t2.col) should be attached to table t2

yet, current equality propagation/substituion scheme will not do that, at least
not when 'cond' is a condition other than equality.

Fixing this is a non-trivial though, because the fix will need to change the
whole concept of equality substition from the

walk through the WHERE clause and substitute certain occurences of
"tblX.colA" for "tblY.colB"

to something else. (the above definition doesn't cover substitution of
Item_equal objects)

Re: Query containing IN subquery with OR in the where clause returns a wrong result
=== Fixing the wrong query result ===

Let's set a more modest goal of

• not producing wrong query results
• not generating regressions wrt non-semijoin materialization

The idea is that given this chart

>ot1-ot2>------------(sjm)>ot3--ot4-....

it1>it2>+

we

"must not attempt to move a condition from one line to another"

e.g. don't move the condition from the top line into the bottom or vice
versa. (This bug is a result of us moving one part of OR-clause from
bottom to the top).

The implementation of is:

• Don't substitute SJ-inner columns for SJ-outer, or vice versa (however it
  is always okay to substitute with references to const tables)

• When exploding multiple-equalities:

if (equality has a const item)

else
{
for X in

}

As for not producing equalities that were "fixed on the upper level":
don't produce them only as long as they would have been produced at this
level.

Launchpad bug id: 928048