MTR testcase: https://gist.github.com/spetrunia/d217e9d7df562e575afec8f8221be023

Your comments above does not clarify the problem too much.

igor Did you check the commit comment also? Anyway, let me go through it again.

I'll be using the simplified testcase from https://gist.github.com/spetrunia/d217e9d7df562e575afec8f8221be023

Consider a table

CREATE TABLE t2 (

  ...

  PRIMARY KEY (`stationId`,`startTime`)

);

and a query

SELECT *

FROM

   t1,t2,t3

WHERE   

  t2.startTime <= 100 and

  t2.stationId = t1.stationId and

  (t1.stationid = 1 or t1.stationid = 2 or t1.stationid = 3) and

  key1 >0 and

  t2.key2=t3.a;

Let's follow what the optimizer does for it.

Step 1. t2.stationId = t1.stationId is used to construct a multiple equality.
Step 2. make_join_statistics() invokes the range optimizer for table t2. The entire WHERE condition is passed as a parameter.
Step 2.1 Range optimizer analyzes the condition

   (t1.stationid = 1 or t1.stationid = 2 or t1.stationid = 3)

due to the multiple equality it is able to infer

   (t2.stationId = 1 or t2.stationId = 2 or t2.stationId = 3)

and construct ranges

   (1,-inf) < (stationId, startTime) <= (1,100)

   (2,-inf) < (stationId, startTime) <= (2,100)

   (3,-inf) < (stationId, startTime) <= (3,100)

This has about 203 rows, so a quick select is built for it.

Step 3. Join optimizer is ran, it picks the join order: t1,t2,t3. For t2, it chooses to use the quick select.

Step 4. Execution enters make_join_select() function and reaches this point:

          if (!tab->table->is_filled_at_execution() &&                                                                                                                 

              !tab->loosescan_match_tab &&              // (1)

              ((cond && (!tab->keys.is_subset(tab->const_keys) && i > 0)) ||

               (!tab->const_keys.is_clear_all() && i == join->const_tables &&

                join->unit->select_limit_cnt <

                join->best_positions[i].records_read &&

                !(join->select_options & OPTION_FOUND_ROWS))))

where tab points to table t2's JOIN_TAB.
The if branch is taken.

Step 5: Execution proceeds to make this call a few lines below:

            sel->cond= and_conds(thd, sel->cond, *tab->on_expr_ref);

...

            if (sel->test_quick_select(thd, tab->keys,

                                       ((used_tables & ~ current_map) |

                                        OUTER_REF_TABLE_BIT),

                                       (join->select_options &

                                        OPTION_FOUND_ROWS ?

                                        HA_POS_ERROR :

                                        join->unit->select_limit_cnt), 0,

                                        FALSE, FALSE) < 0)

Note that the parameter to this range optimizer call is the condition that is attached to table t2:

(gdb) p dbug_print_item(sel->cond)

 ... "t2.stationId = t1.stationid and t2.startTime <= 100 and t2.key1 > 0 and t2.key2 is not null"

The condition "t1.stationid=1 or t1.stationid=2 or t1.stationid=3" is not present here as it is attached to table t1 (and so is not attached to table t2).

Step 5.1 Because of this , the range optimizer is not able to construct a range access over the (stationId, startTime), and makes t2 use a full table scan.

Where did things go wrong?

• One can argue it is Step #5. The optimizer should not try to build a quick select if it already has one.
• OTOH, there may be edge cases where re-trying to build a quick select may produce a better quick select.

So, the patch is "conservative". Its action is:

• Right before the Step 5, save the quick select we have.
• If Step 5 didn't succeed in building the quick select, or has built a quick select that's more expensive than the saved one, put the saved quick select back.

Still it's not clear for me why we have difference in 5.2 and 10.3.

Let me go through that again also.

Let's recall Step #4:

Step 4. Execution enters make_join_select() function and reaches this point:

          if (!tab->table->is_filled_at_execution() &&

              !tab->loosescan_match_tab &&              // (1)

              ((cond && (!tab->keys.is_subset(tab->const_keys) && i > 0)) ||

               (!tab->const_keys.is_clear_all() && i == join->const_tables &&

                join->unit->select_limit_cnt <

                join->best_positions[i].records_read &&

                !(join->select_options & OPTION_FOUND_ROWS))))

Look at line #4:

            ((cond && (!tab->keys.is_subset(tab->const_keys) && i > 0)) ||

Here, in 5.2, we have

tab->keys= {map=7}   // 7 = {PRIMARY, key1, key2}

tab->const_keys= {map=7}

which means tab->keys.is_subset(tab->const_keys)==true, which causes the
if-branch not to be taken.

OTOH in 10.3 we have:

(gdb) p tab->keys

  $12 = {map = 7}  // {PRIMARY, key1, key2}

(gdb) p tab->const_keys

  $13 = {map = 3}  // {PRIMARY, key1}

which means tab->keys.is_subset(tab->const_keys)==false, which means the
if-branch IS taken.

If one looks at the query text, the only predicate with t2.key2 is
"t2.key2=t3.a", so it key2 should not be in tab->const_keys.

Sergei,
The condition that is passed in the call sel->test_quick_select() (step 5) must be a conjunction of all the conditions attached to the tables in the prefix and multiple equalities from cond_equal. In this case you'll be able to construct the needed quick select.

igor, attempt to implement this suggestion exposes another issue. Please find the description below.

So, the code from Step #6 now gets invoked with this condition:

(t1.stationid = 1 or t1.stationid = 2 or t1.stationid = 3) and 

t2.stationId = t1.stationid and t2.startTime <= 100 and t2.key1 > 0 and t2.key2 is not null

The structure of the condition is such that range optimizer performs operations in the following order:

$tree1 = get_mm_tree("t1.stationid = 1 or t1.stationid = 2 or t1.stationid =3");

$tree2 = get_mm_tree("t2.stationId = t1.stationid");

$tree3 = get_mm_tree("t2.startTime <= 100")

$tree2_3 = tree_and($tree2, $tree3)

and the result is that

$tree2_3=$tree2

that is, the SEL_ARG for "t2.startTime <= 100" is discarded.

The reason for that is:

$tree2->keys[0]= SEL_ARG(key=0, part=0, type=SEL_ARG::MAYBE_KEY)

$tree3->keys[0]= SEL_ARG(key=0, part=1, SEL_ARG::KEY_RANGE, ...)

then, we call tree_and() for those, and the execution reaches and_all_keys() which discards $tree3->keys[0] because it has a bigger key part number.

I've made an obvious change to fix this (discard the SEL_ARG with type=MAYBE_KEY even if its part # is smaller).

The patch is here:
http://lists.askmonty.org/pipermail/commits/2020-January/014145.html

Sergei,
You forgot to add multiple equalities. They are eliminated, but still can be accessed through JOIN::cond_equal / JOIN_TAB::cond_equal. Regular equalities does not help range optimizer.

igor wrote:

You forgot to add multiple equalities. They are eliminated, but still can be accessed through JOIN::cond_equal / JOIN_TAB::cond_equal. Regular equalities does not help range optimizer.

I don't see any need to do this.

Proof
Suppose the WHERE condition has a multiple-equality

t1.col=t2.col=...

First, let's assume that the multiple equality doesn't include a constant.
The multiple equality is usable by the optimizer as such (i.e. is not sargable)
but it can make other conditions sargable, e.g. the optimizer may use it infer
from "t1.col < 100" that "t2.col<100" also must hold, and use that to
construct ranges.
This inference happens because the optmizer encounters "t1.col <100", sees that
t1 is a member of multiple equality (by looking at
Item_field("t1.col")->item_equal), and examines other members of the multiple
equality.

Second, let's assume that multiple equality does include a constant. In this
case, the optimizer will generate pair-wise

t1.col=const
t2.col=const

and they will get attached to their respective tables (and so will be usable by
the optimizer).
Check for an example: https://gist.github.com/spetrunia/d6f7135b02c547430949353e0d0e36b9

Is there something missing in the above logic?

Got ok to push after discussion