From b21832ef1525e37f0dda4e17853bcca9e4e20f2b Mon Sep 17 00:00:00 2001 From: Igor Babaev Date: Wed, 26 Oct 2022 22:08:32 -0700 Subject: MDEV-27624 Wrong result for nested left join using not_exists optimization This bug affected queries with nested left joins having the same last inner table such that not_exists optimization could be applied to the most inner outer join when optimizer chose to use join buffers. The bug could lead to producing wrong a result set. If the WHERE condition a query contains a conjunctive IS NULL predicate over a non-nullable column of an inner table of a not nested outer join then not_exists optimization can be applied to tho the outer join. With this optimization when looking for matches for a certain record from the outer table of the join the records of the inner table can be ignored right after the first match satisfying the ON condition is found. In the case of nested outer joins having the same last inner table this optimization still can be applied but only if all ON conditions of the embedding outer joins are satisfied. Such check was missing in the code that tried to apply not_exists optimization when join buffers were used for outer join operations. This problem has been already fixed in the patch for bug MDEV-7992. Yet there it was resolved only for the cases when join buffers were not used for outer joins. Approved by Oleksandr Byelkin --- mysql-test/main/join_nested.result | 52 +++++++++++++++++++++++++++++++++ mysql-test/main/join_nested.test | 38 ++++++++++++++++++++++++ mysql-test/main/join_nested_jcl6.result | 52 +++++++++++++++++++++++++++++++++ sql/sql_join_cache.cc | 35 ++++++++++++++++++---- 4 files changed, 171 insertions(+), 6 deletions(-) diff --git a/mysql-test/main/join_nested.result b/mysql-test/main/join_nested.result index 5ab94a6b568..1efb2e64116 100644 --- a/mysql-test/main/join_nested.result +++ b/mysql-test/main/join_nested.result @@ -1999,3 +1999,55 @@ Note 1003 select `test`.`t3`.`pk` AS `pk`,`test`.`t3`.`c1` AS `c1`,`test`.`t3`.` DROP TABLE t1,t2,t3; set join_cache_level= @save_join_cache_level; set optimizer_switch=@save_optimizer_switch; +# +# MDEV-27624: Nested left joins with not_exists optimization +# for most inner left join +# +set @save_join_cache_level= @@join_cache_level; +CREATE TABLE t1 (a INT NOT NULL, b INT, c INT); +INSERT INTO t1 VALUES (1,1,1), (1,2,1), (1,3,1); +CREATE TABLE t2(a INT NOT NULL); +INSERT INTO t2 VALUES (1), (2); +CREATE TABLE t3(a INT not null, b INT); +INSERT INTO t3 VALUES (1, 1), (2, 1), (3, 1); +set join_cache_level = 0; +EXPLAIN SELECT * +FROM t1 +LEFT JOIN +( t2 LEFT JOIN t3 ON t2.a = t3.b ) +ON t2.a = 1 AND (t3.b = t1.a AND t3.a > t1.b OR t3.a is NULL) +WHERE t1.c = 1 AND t3.a is NULL; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 3 Using where +1 SIMPLE t2 ALL NULL NULL NULL NULL 2 Using where +1 SIMPLE t3 ALL NULL NULL NULL NULL 3 Using where; Not exists +SELECT * +FROM t1 +LEFT JOIN +( t2 LEFT JOIN t3 ON t2.a = t3.b ) +ON t2.a = 1 AND (t3.b = t1.a AND t3.a > t1.b OR t3.a is NULL) +WHERE t1.c = 1 AND t3.a is NULL; +a b c a a b +1 3 1 NULL NULL NULL +set join_cache_level = 2; +EXPLAIN SELECT * +FROM t1 +LEFT JOIN +( t2 LEFT JOIN t3 ON t2.a = t3.b ) +ON t2.a = 1 AND (t3.b = t1.a AND t3.a > t1.b OR t3.a is NULL) +WHERE t1.c = 1 AND t3.a is NULL; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 3 Using where +1 SIMPLE t2 ALL NULL NULL NULL NULL 2 Using where; Using join buffer (flat, BNL join) +1 SIMPLE t3 ALL NULL NULL NULL NULL 3 Using where; Not exists; Using join buffer (incremental, BNL join) +SELECT * +FROM t1 +LEFT JOIN +( t2 LEFT JOIN t3 ON t2.a = t3.b ) +ON t2.a = 1 AND (t3.b = t1.a AND t3.a > t1.b OR t3.a is NULL) +WHERE t1.c = 1 AND t3.a is NULL; +a b c a a b +1 3 1 NULL NULL NULL +DROP TABLE t1, t2, t3; +set join_cache_level= @save_join_cache_level; +# end of 10.3 tests diff --git a/mysql-test/main/join_nested.test b/mysql-test/main/join_nested.test index eaf754fb0ca..6b2ae9a457f 100644 --- a/mysql-test/main/join_nested.test +++ b/mysql-test/main/join_nested.test @@ -1419,3 +1419,41 @@ DROP TABLE t1,t2,t3; set join_cache_level= @save_join_cache_level; set optimizer_switch=@save_optimizer_switch; + +--echo # +--echo # MDEV-27624: Nested left joins with not_exists optimization +--echo # for most inner left join +--echo # + +set @save_join_cache_level= @@join_cache_level; + +CREATE TABLE t1 (a INT NOT NULL, b INT, c INT); +INSERT INTO t1 VALUES (1,1,1), (1,2,1), (1,3,1); + +CREATE TABLE t2(a INT NOT NULL); +INSERT INTO t2 VALUES (1), (2); + +CREATE TABLE t3(a INT not null, b INT); +INSERT INTO t3 VALUES (1, 1), (2, 1), (3, 1); + +let $q= +SELECT * +FROM t1 + LEFT JOIN + ( t2 LEFT JOIN t3 ON t2.a = t3.b ) + ON t2.a = 1 AND (t3.b = t1.a AND t3.a > t1.b OR t3.a is NULL) +WHERE t1.c = 1 AND t3.a is NULL; + +set join_cache_level = 0; +eval EXPLAIN $q; +eval $q; + +set join_cache_level = 2; +eval EXPLAIN $q; +eval $q; + +DROP TABLE t1, t2, t3; + +set join_cache_level= @save_join_cache_level; + +--echo # end of 10.3 tests diff --git a/mysql-test/main/join_nested_jcl6.result b/mysql-test/main/join_nested_jcl6.result index 541cd47bf04..338705c0a29 100644 --- a/mysql-test/main/join_nested_jcl6.result +++ b/mysql-test/main/join_nested_jcl6.result @@ -2008,6 +2008,58 @@ Note 1003 select `test`.`t3`.`pk` AS `pk`,`test`.`t3`.`c1` AS `c1`,`test`.`t3`.` DROP TABLE t1,t2,t3; set join_cache_level= @save_join_cache_level; set optimizer_switch=@save_optimizer_switch; +# +# MDEV-27624: Nested left joins with not_exists optimization +# for most inner left join +# +set @save_join_cache_level= @@join_cache_level; +CREATE TABLE t1 (a INT NOT NULL, b INT, c INT); +INSERT INTO t1 VALUES (1,1,1), (1,2,1), (1,3,1); +CREATE TABLE t2(a INT NOT NULL); +INSERT INTO t2 VALUES (1), (2); +CREATE TABLE t3(a INT not null, b INT); +INSERT INTO t3 VALUES (1, 1), (2, 1), (3, 1); +set join_cache_level = 0; +EXPLAIN SELECT * +FROM t1 +LEFT JOIN +( t2 LEFT JOIN t3 ON t2.a = t3.b ) +ON t2.a = 1 AND (t3.b = t1.a AND t3.a > t1.b OR t3.a is NULL) +WHERE t1.c = 1 AND t3.a is NULL; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 3 Using where +1 SIMPLE t2 ALL NULL NULL NULL NULL 2 Using where +1 SIMPLE t3 ALL NULL NULL NULL NULL 3 Using where; Not exists +SELECT * +FROM t1 +LEFT JOIN +( t2 LEFT JOIN t3 ON t2.a = t3.b ) +ON t2.a = 1 AND (t3.b = t1.a AND t3.a > t1.b OR t3.a is NULL) +WHERE t1.c = 1 AND t3.a is NULL; +a b c a a b +1 3 1 NULL NULL NULL +set join_cache_level = 2; +EXPLAIN SELECT * +FROM t1 +LEFT JOIN +( t2 LEFT JOIN t3 ON t2.a = t3.b ) +ON t2.a = 1 AND (t3.b = t1.a AND t3.a > t1.b OR t3.a is NULL) +WHERE t1.c = 1 AND t3.a is NULL; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 3 Using where +1 SIMPLE t2 ALL NULL NULL NULL NULL 2 Using where; Using join buffer (flat, BNL join) +1 SIMPLE t3 ALL NULL NULL NULL NULL 3 Using where; Not exists; Using join buffer (incremental, BNL join) +SELECT * +FROM t1 +LEFT JOIN +( t2 LEFT JOIN t3 ON t2.a = t3.b ) +ON t2.a = 1 AND (t3.b = t1.a AND t3.a > t1.b OR t3.a is NULL) +WHERE t1.c = 1 AND t3.a is NULL; +a b c a a b +1 3 1 NULL NULL NULL +DROP TABLE t1, t2, t3; +set join_cache_level= @save_join_cache_level; +# end of 10.3 tests CREATE TABLE t5 (a int, b int, c int, PRIMARY KEY(a), KEY b_i (b)); CREATE TABLE t6 (a int, b int, c int, PRIMARY KEY(a), KEY b_i (b)); CREATE TABLE t7 (a int, b int, c int, PRIMARY KEY(a), KEY b_i (b)); diff --git a/sql/sql_join_cache.cc b/sql/sql_join_cache.cc index 86df1d32bd9..0804f4f9463 100644 --- a/sql/sql_join_cache.cc +++ b/sql/sql_join_cache.cc @@ -2287,11 +2287,7 @@ enum_nested_loop_state JOIN_CACHE::join_matching_records(bool skip_last) int error; enum_nested_loop_state rc= NESTED_LOOP_OK; join_tab->table->null_row= 0; - bool check_only_first_match= - join_tab->check_only_first_match() && - (!join_tab->first_inner || // semi-join case - join_tab->first_inner == join_tab->first_unmatched); // outer join case - bool outer_join_first_inner= join_tab->is_first_inner_for_outer_join(); + bool check_only_first_match= join_tab->check_only_first_match(); DBUG_ENTER("JOIN_CACHE::join_matching_records"); /* Return at once if there are no records in the join buffer */ @@ -2355,7 +2351,34 @@ enum_nested_loop_state JOIN_CACHE::join_matching_records(bool skip_last) Also those records that must be null complemented are not considered as candidates for matches. */ - if ((!check_only_first_match && !outer_join_first_inner) || + + bool not_exists_opt_is_applicable= true; + if (check_only_first_match && join_tab->first_inner) + { + /* + This is the case with not_exists optimization for nested outer join + when join_tab is the last inner table for one or more embedding outer + joins. To safely use 'not_exists' optimization in this case we have + to check that the match flags for all these embedding outer joins are + in the 'on' state. + (See also a similar check in evaluate_join_record() for the case when + join buffer are not used.) + */ + for (JOIN_TAB *tab= join_tab->first_inner; + tab && tab->first_inner && tab->last_inner == join_tab; + tab= tab->first_inner->first_upper) + { + if (get_match_flag_by_pos_from_join_buffer(rec_ptr, tab) != + MATCH_FOUND) + { + not_exists_opt_is_applicable= false; + break; + } + } + } + + if (!check_only_first_match || + (join_tab->first_inner && !not_exists_opt_is_applicable) || !skip_next_candidate_for_match(rec_ptr)) { read_next_candidate_for_match(rec_ptr); -- cgit v1.2.1