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 <sanja@mariadb.com>

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);