revision-id: f8148e77b0c956fa739b71e688340cd12ab5ebbd (mariadb-10.3.10-35-gf8148e77b0c) parent(s): 1595ff8a2ce7ef0153203041a850b4ec8d144b8d author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2018-10-22 16:17:10 +0200 message: MDEV-17518: Range optimization doesn't use ON expressions from nested outer joins --- mysql-test/main/join_nested_jcl6.result | 2 +- mysql-test/main/join_outer.result | 21 +++++ mysql-test/main/join_outer.test | 20 +++++ mysql-test/main/join_outer_jcl6.result | 21 +++++ sql/sql_select.cc | 151 +++++++++++++++++++++++++------- 5 files changed, 181 insertions(+), 34 deletions(-) diff --git a/mysql-test/main/join_nested_jcl6.result b/mysql-test/main/join_nested_jcl6.result index eb59531b7d2..2f8e1712672 100644 --- a/mysql-test/main/join_nested_jcl6.result +++ b/mysql-test/main/join_nested_jcl6.result @@ -2055,7 +2055,7 @@ ON (t5.b=t8.b); id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t5 ALL NULL NULL NULL NULL 2 1 SIMPLE t6 ALL NULL NULL NULL NULL 1 Using join buffer (flat, BNL join) -1 SIMPLE t7 ref b_i b_i 5 const 0 Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan +1 SIMPLE t7 ref b_i b_i 5 const 1 Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan 1 SIMPLE t8 ALL b_i NULL NULL NULL 1 Using where; Using join buffer (incremental, BNL join) SELECT t5.a,t5.b,t6.a,t6.b,t7.a,t7.b,t8.a,t8.b FROM t5 LEFT JOIN diff --git a/mysql-test/main/join_outer.result b/mysql-test/main/join_outer.result index 9245111369f..5a123826d79 100644 --- a/mysql-test/main/join_outer.result +++ b/mysql-test/main/join_outer.result @@ -2511,4 +2511,25 @@ ORDER BY tb1.i1; v2 DROP TABLE t1,t2; # end of 5.5 tests +# +# MDEV-17518: Range optimization doesn't use ON expressions from nested outer joins +# +create table t1(a int); +insert into t1 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); +create table t2(a int); +insert into t2 values (0),(1); +create table t3 (a int, b int, key(a)); +insert into t3 select A.a + B.a* 10 + C.a * 100, 12345 from t1 A, t1 B, t1 C; +# Uses range for table t3: +explain select * from t1 left join t3 on t1.a=t3.b and t3.a<5; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 10 +1 SIMPLE t3 range a a 5 NULL 5 Using where +# This must use range for table t3, too: +explain select * from t1 left join (t3 join t2) on t1.a=t3.b and t3.a<5; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 10 +1 SIMPLE t2 ALL NULL NULL NULL NULL 2 +1 SIMPLE t3 range a a 5 NULL 5 Using where +drop table t1,t2,t3; SET optimizer_switch=@save_optimizer_switch; diff --git a/mysql-test/main/join_outer.test b/mysql-test/main/join_outer.test index 6d20c089bd9..28f544dec7d 100644 --- a/mysql-test/main/join_outer.test +++ b/mysql-test/main/join_outer.test @@ -2042,4 +2042,24 @@ DROP TABLE t1,t2; --echo # end of 5.5 tests +--echo # +--echo # MDEV-17518: Range optimization doesn't use ON expressions from nested outer joins +--echo # +create table t1(a int); +insert into t1 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); + +create table t2(a int); +insert into t2 values (0),(1); + +create table t3 (a int, b int, key(a)); +insert into t3 select A.a + B.a* 10 + C.a * 100, 12345 from t1 A, t1 B, t1 C; + +--echo # Uses range for table t3: +explain select * from t1 left join t3 on t1.a=t3.b and t3.a<5; + +--echo # This must use range for table t3, too: +explain select * from t1 left join (t3 join t2) on t1.a=t3.b and t3.a<5; + +drop table t1,t2,t3; + SET optimizer_switch=@save_optimizer_switch; diff --git a/mysql-test/main/join_outer_jcl6.result b/mysql-test/main/join_outer_jcl6.result index cb582b1399f..842ab19e20a 100644 --- a/mysql-test/main/join_outer_jcl6.result +++ b/mysql-test/main/join_outer_jcl6.result @@ -2522,6 +2522,27 @@ ORDER BY tb1.i1; v2 DROP TABLE t1,t2; # end of 5.5 tests +# +# MDEV-17518: Range optimization doesn't use ON expressions from nested outer joins +# +create table t1(a int); +insert into t1 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); +create table t2(a int); +insert into t2 values (0),(1); +create table t3 (a int, b int, key(a)); +insert into t3 select A.a + B.a* 10 + C.a * 100, 12345 from t1 A, t1 B, t1 C; +# Uses range for table t3: +explain select * from t1 left join t3 on t1.a=t3.b and t3.a<5; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 10 +1 SIMPLE t3 range a a 5 NULL 5 Using where; Rowid-ordered scan; Using join buffer (flat, BNL join) +# This must use range for table t3, too: +explain select * from t1 left join (t3 join t2) on t1.a=t3.b and t3.a<5; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 10 +1 SIMPLE t2 ALL NULL NULL NULL NULL 2 Using join buffer (flat, BNL join) +1 SIMPLE t3 range a a 5 NULL 5 Using where; Rowid-ordered scan; Using join buffer (incremental, BNL join) +drop table t1,t2,t3; SET optimizer_switch=@save_optimizer_switch; set join_cache_level=default; show variables like 'join_cache_level'; diff --git a/sql/sql_select.cc b/sql/sql_select.cc index a3003285f87..91d9326854b 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -4300,6 +4300,40 @@ struct SARGABLE_PARAM }; +/* + Mark all tables inside a join nest as constant. + + @detail This is called when there is a local "Impossible WHERE" inside + a multi-table LEFT JOIN. +*/ + +void mark_join_nest_as_const(JOIN *join, + TABLE_LIST *join_nest, + table_map *found_const_table_map, + uint *const_count) +{ + List_iterator<TABLE_LIST> it(join_nest->nested_join->join_list); + TABLE_LIST *tbl; + while ((tbl= it++)) + { + if (tbl->nested_join) + { + mark_join_nest_as_const(join, tbl, found_const_table_map, const_count); + continue; + } + JOIN_TAB *tab= tbl->table->reginfo.join_tab; + + tab->type= JT_CONST; + tab->info= ET_IMPOSSIBLE_ON_CONDITION; + tab->table->const_table= 1; + + join->const_table_map|= tab->table->map; + *found_const_table_map|= tab->table->map; + set_position(join,(*const_count)++,tab,(KEYUSE*) 0); + mark_as_null_row(tab->table); // All fields are NULL + } +} + /** Calculate the best possible join and initialize the join structure. @@ -4871,39 +4905,80 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list, /* Perform range analysis if there are keys it could use (1). - Don't do range analysis if we're on the inner side of an outer join (2). - Do range analysis if we're on the inner side of a semi-join (3). - Don't do range analysis for materialized subqueries (4). - Don't do range analysis for materialized derived tables (5) + Don't do range analysis for materialized subqueries (2). + Don't do range analysis for materialized derived tables (3) */ if ((!s->const_keys.is_clear_all() || !bitmap_is_clear_all(&s->table->cond_set)) && // (1) - (!s->table->pos_in_table_list->embedding || // (2) - (s->table->pos_in_table_list->embedding && // (3) - s->table->pos_in_table_list->embedding->sj_on_expr)) && // (3) - !s->table->is_filled_at_execution() && // (4) - !(s->table->pos_in_table_list->derived && // (5) - s->table->pos_in_table_list->is_materialized_derived())) // (5) + !s->table->is_filled_at_execution() && // (2) + !(s->table->pos_in_table_list->derived && // (3) + s->table->pos_in_table_list->is_materialized_derived())) // (3) { bool impossible_range= FALSE; ha_rows records= HA_POS_ERROR; SQL_SELECT *select= 0; if (!s->const_keys.is_clear_all()) { + Item *sargable_cond; + int cond_source; + /* + Figure out which condition we should use for range analysis. For + INNER JOIN, we use the WHERE, for inner side of LEFT JOIN we should + use the ON expression. + */ + if (*s->on_expr_ref) + { + /* + This is an inner table from a single-table LEFT JOIN, "t1 LEFT JOIN + t2 ON cond". Use the condition cond. + */ + cond_source= 0; + sargable_cond= *s->on_expr_ref; + } + else if (s->table->pos_in_table_list->embedding && + !s->table->pos_in_table_list->embedding->sj_on_expr) + { + /* + This is the inner side of a multi-table outer join. Use the + appropriate ON expression. + */ + cond_source= 1; + sargable_cond= s->table->pos_in_table_list->embedding->on_expr; + } + else + { + /* The table is not inner wrt some LEFT JOIN. Use the WHERE clause */ + cond_source= 2; + sargable_cond= join->conds; + } + select= make_select(s->table, found_const_table_map, found_const_table_map, - *s->on_expr_ref ? *s->on_expr_ref : join->conds, + sargable_cond, (SORT_INFO*) 0, 1, &error); if (!select) goto error; records= get_quick_record_count(join->thd, select, s->table, &s->const_keys, join->row_limit); - /* Range analyzer could modify the condition. */ - if (*s->on_expr_ref) - *s->on_expr_ref= select->cond; - else - join->conds= select->cond; + + /* + Range analyzer might have modified the condition. Put it the new + condition to where we got it from. + */ + switch (cond_source) { + case 0: + *s->on_expr_ref= select->cond; + break; + case 1: + s->table->pos_in_table_list->embedding->on_expr= select->cond; + break; + case 2: + join->conds= select->cond; + break; + default: + DBUG_ASSERT(0); + } s->quick=select->quick; s->needed_reg=select->needed_reg; @@ -4924,23 +4999,33 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list, } if (impossible_range) { - /* - Impossible WHERE or ON expression - In case of ON, we mark that the we match one empty NULL row. - In case of WHERE, don't set found_const_table_map to get the - caller to abort with a zero row result. - */ - join->const_table_map|= s->table->map; - set_position(join,const_count++,s,(KEYUSE*) 0); - s->type= JT_CONST; - s->table->const_table= 1; - if (*s->on_expr_ref) - { - /* Generate empty row */ - s->info= ET_IMPOSSIBLE_ON_CONDITION; - found_const_table_map|= s->table->map; - mark_as_null_row(s->table); // All fields are NULL - } + /* + Impossible WHERE or ON expression + In case of ON, we mark that the we match one empty NULL row. + In case of WHERE, don't set found_const_table_map to get the + caller to abort with a zero row result. + */ + TABLE_LIST *emb= s->table->pos_in_table_list->embedding; + if (emb && !emb->sj_on_expr) + { + /* Mark all tables in a multi-table join nest as const */ + mark_join_nest_as_const(join, emb, &found_const_table_map, + &const_count); + } + else + { + join->const_table_map|= s->table->map; + set_position(join,const_count++,s,(KEYUSE*) 0); + s->type= JT_CONST; + s->table->const_table= 1; + if (*s->on_expr_ref) + { + /* Generate empty row */ + s->info= ET_IMPOSSIBLE_ON_CONDITION; + found_const_table_map|= s->table->map; + mark_as_null_row(s->table); // All fields are NULL + } + } } if (records != HA_POS_ERROR) {