On Dec, 19th, I have committed a patch that limits moving of predicates as described in the above spec.

The patch only affects the execution part (where Item* objects are wrapped and positioned in join_tab[i]->select_cond. The optimizer part (which makes the join optimizer take into account cost of attached predicates) works as if there were no limits.

The second part of the task is to account for predicate moving limits in the join optimizer.

The basic idea is: when the optimizer calculates join prefix cost, it should take into account the limits on predicate pushdown that are imposed by semi-join strategies.

The apparent solution would be to amend JOIN::static_pushdown_cost() so that it doesn't try to position expensive predicates where it is not allowed.

A deficiency of this approach (and a possible problem): static_pushdown_cost() is called after the join order has been constructed, and after the choice has been made about which semi-join strategy to use.

Suppose, there is a certain join order J_ORD1, for which there are two possible semi-join strategies, SJ1 and SJ2. Suppose, the optimizer picks SJ1 (without taking static pushdown cost into account).
Now, when static_pushdown_cost() is called for the

it will see that this choice is expensive, but there will be no way to return to consider

.

I am not sure if the above problem affects the primary example of MDEV-83. I suppose it might, because I remember a discussion with Timour about the example of MDEV-83, where the problem was that semi-join optimizer chose to use Materialization, and that was a particularly bad choice, because Materialization enumerates all possible matches that subquery could have, which causes more invocations of the expensive scalar-context subquery that was attached to one of the tables inside the SJ-Materialization nest.

IIRC the problem was solved by taking into account the cost of expensive scalar-context subquery in the join optimizer.

Another possible angle (discussed with Timour, w/o answer): What does current MDEV-83 code do for SJ-Materialization nests? Does optimize_semijoin_nests() include the cost of attached subquery predicates?

If it does, then SJ-Materialization is heavily penalized, because advance_sj_state() will compare SJ-Materialization costs which include expensive-predicate-cost, with e.g. FirstMatch costs which do not include expensive-predicate-cost.

Did some debugging to answer the question in the last comment: No, optimize_semijoin_nests() does not include costs of expensive predicates into costs of SJ-Materialization.

This way, the concern of SJ-Materialization being unfairly penalized by advance_sj_state() is invalid.

However, the concern about semi-join strategy choice remains. Current code will have this problem:
1. A join order J_ORD is built
2. SJ-Materialization is chosen (and FirstMatch is not, for example).
3. static_subquery_cost() looks at cost J_ORD+SJ_Materialization, finds it to be expensive, and J_ORD is discarded.
the fact that J_ORD+FirstMatch might have lower cost is ignored.

A possible solution for this is to take into account expensive-predicate-cost
as early as possible.

Suppose there EXPENSIVE_COND(tX, tY, tZ). Then, the optimizer should:

• as soon as tables tX, tY and tZ are in the join prefix, add cost of
  EXPENSIVE_COND into the join prefix.

• When a change is made to the query plan (a table is added, or a semi-join
  strategy is applied),check if EXPENSIVE_COND should/can be moved, and if yes,
  move it and adjust the cost.

This approach will let static-condition-pushdown to affect the choice of
semi-join strategies.

Possible issues:

• This approach requires many more static_subquery_cost() invocations.

• Does this work well with optimizer plan pruning? We have the following new
  property: adding a table can allow to move an EXPENSIVE_COND further in the
  plan, where it will be invoked fewer times, and the total cost will get
  cheaper. I suspect optimizer plan pruning doesn't work well when extending
  the query plan can make it cheaper.

• Is this all worth it? We know static pushdown doesn't do a very good job, it
  is only there to provide starting points for dynamic pushdown.