MDEV-22866: Crash in join optimizer with constant outer join nest

Starting from 10.3, the optimizer is able to detect that entire outer join
nests are constants (because of "Impossible ON") and remove them (see
mark_join_nest_as_const)

However, this was not properly accounted for in NESTED_JOIN structure
and the way check_interleaving_with_nj() uses its n_tables member to
check if the join prefix order is allowed.

(The result was that the optimizer could conclude that no join prefix is
allowed and fail an assertion)

5 files changed, 114 insertions, 7 deletions

diff --git a/mysql-test/main/join_outer.result b/mysql-test/main/join_outer.result
index 7a230ccd15a..796d01a0996 100644
--- a/mysql-test/main/join_outer.result
+++ b/mysql-test/main/join_outer.result
@@ -2752,3 +2752,34 @@ WHERE t3.pk IN (2);
 drop view v4;
 drop table t1,t2,t3,t4;
 SET optimizer_switch=@org_optimizer_switch;
+#
+# MDEV-22866: Crash in join optimizer with constant outer join nest
+#
+CREATE TABLE t1 (a INT) ENGINE=MyISAM;
+INSERT INTO t1 VALUES (1),(2);
+CREATE TABLE t2 (b INT) ENGINE=MyISAM;
+INSERT INTO t2 VALUES (3),(4);
+CREATE TABLE t3 (c INT, KEY(c)) ENGINE=MyISAM;
+CREATE TABLE t4 (d INT, KEY(d)) ENGINE=MyISAM;
+INSERT INTO t4 VALUES (5),(6);
+CREATE TABLE t5 (e INT) ENGINE=MyISAM;
+INSERT INTO t5 VALUES (7),(8);
+CREATE TABLE t6 (f INT) ENGINE=MyISAM;
+INSERT INTO t6 VALUES (9),(10);
+SELECT *
+FROM
+t1
+LEFT JOIN (
+t2 LEFT JOIN (
+t3 JOIN
+t4 ON t3.c = t4.d and t3.c >2 and t3.c<0
+) ON t2.b >= t4.d
+) ON t1.a <= t2.b
+LEFT JOIN t5 ON t2.b = t5.e
+LEFT JOIN t6 ON t3.c = t6.f;
+a	b	c	d	e	f
+1	3	NULL	NULL	NULL	NULL
+2	3	NULL	NULL	NULL	NULL
+1	4	NULL	NULL	NULL	NULL
+2	4	NULL	NULL	NULL	NULL
+drop table t1,t2,t3,t4,t5,t6;
diff --git a/mysql-test/main/join_outer.test b/mysql-test/main/join_outer.test
index 2e5fc65ebb6..f835d8af5a8 100644
--- a/mysql-test/main/join_outer.test
+++ b/mysql-test/main/join_outer.test
@@ -2252,3 +2252,38 @@ drop view v4;
 drop table t1,t2,t3,t4;
 
 SET optimizer_switch=@org_optimizer_switch;
+
+--echo #
+--echo # MDEV-22866: Crash in join optimizer with constant outer join nest
+--echo #
+
+CREATE TABLE t1 (a INT) ENGINE=MyISAM;
+INSERT INTO t1 VALUES (1),(2);
+
+CREATE TABLE t2 (b INT) ENGINE=MyISAM;
+INSERT INTO t2 VALUES (3),(4);
+
+CREATE TABLE t3 (c INT, KEY(c)) ENGINE=MyISAM;
+
+CREATE TABLE t4 (d INT, KEY(d)) ENGINE=MyISAM;
+INSERT INTO t4 VALUES (5),(6);
+
+CREATE TABLE t5 (e INT) ENGINE=MyISAM;
+INSERT INTO t5 VALUES (7),(8);
+
+CREATE TABLE t6 (f INT) ENGINE=MyISAM;
+INSERT INTO t6 VALUES (9),(10);
+
+SELECT *
+FROM
+  t1
+  LEFT JOIN (
+    t2 LEFT JOIN (
+       t3 JOIN
+       t4 ON t3.c = t4.d and t3.c >2 and t3.c<0
+    ) ON t2.b >= t4.d
+  ) ON t1.a <= t2.b
+  LEFT JOIN t5 ON t2.b = t5.e
+  LEFT JOIN t6 ON t3.c = t6.f;
+
+drop table t1,t2,t3,t4,t5,t6;
diff --git a/mysql-test/main/join_outer_jcl6.result b/mysql-test/main/join_outer_jcl6.result
index d3276de88ea..4f66b004cfc 100644
--- a/mysql-test/main/join_outer_jcl6.result
+++ b/mysql-test/main/join_outer_jcl6.result
@@ -2759,3 +2759,34 @@ WHERE t3.pk IN (2);
 drop view v4;
 drop table t1,t2,t3,t4;
 SET optimizer_switch=@org_optimizer_switch;
+#
+# MDEV-22866: Crash in join optimizer with constant outer join nest
+#
+CREATE TABLE t1 (a INT) ENGINE=MyISAM;
+INSERT INTO t1 VALUES (1),(2);
+CREATE TABLE t2 (b INT) ENGINE=MyISAM;
+INSERT INTO t2 VALUES (3),(4);
+CREATE TABLE t3 (c INT, KEY(c)) ENGINE=MyISAM;
+CREATE TABLE t4 (d INT, KEY(d)) ENGINE=MyISAM;
+INSERT INTO t4 VALUES (5),(6);
+CREATE TABLE t5 (e INT) ENGINE=MyISAM;
+INSERT INTO t5 VALUES (7),(8);
+CREATE TABLE t6 (f INT) ENGINE=MyISAM;
+INSERT INTO t6 VALUES (9),(10);
+SELECT *
+FROM
+t1
+LEFT JOIN (
+t2 LEFT JOIN (
+t3 JOIN
+t4 ON t3.c = t4.d and t3.c >2 and t3.c<0
+) ON t2.b >= t4.d
+) ON t1.a <= t2.b
+LEFT JOIN t5 ON t2.b = t5.e
+LEFT JOIN t6 ON t3.c = t6.f;
+a	b	c	d	e	f
+1	3	NULL	NULL	NULL	NULL
+2	3	NULL	NULL	NULL	NULL
+1	4	NULL	NULL	NULL	NULL
+2	4	NULL	NULL	NULL	NULL
+drop table t1,t2,t3,t4,t5,t6;
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 1f35754a8fe..ee5144fafe6 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -15826,10 +15826,15 @@ static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list,
 
 
 /**
-  Set NESTED_JOIN::counter=0 in all nested joins in passed list.
+  Set NESTED_JOIN::counter and n_tables in all nested joins in passed list.
 
-    Recursively set NESTED_JOIN::counter=0 for all nested joins contained in
-    the passed join_list.
+  For all nested joins contained in the passed join_list (including its
+  children), set:
+   - nested_join->counter=0
+   - nested_join->n_tables= {number of non-degenerate direct children}.
+
+  Non-degenerate means non-const base table or a join nest that has a
+  non-degenerate child.
 
   @param join_list  List of nested joins to process. It may also contain base
                     tables which will be ignored.
@@ -15852,8 +15857,11 @@ static uint reset_nj_counters(JOIN *join, List<TABLE_LIST> *join_list)
       if (!nested_join->n_tables)
         is_eliminated_nest= TRUE;
     }
-    if ((table->nested_join && !is_eliminated_nest) || 
-        (!table->nested_join && (table->table->map & ~join->eliminated_tables)))
+    const table_map removed_tables= join->eliminated_tables |
+                                    join->const_table_map;
+
+    if ((table->nested_join && !is_eliminated_nest) ||
+        (!table->nested_join && (table->table->map & ~removed_tables)))
       n++;
   }
   DBUG_RETURN(n);
diff --git a/sql/table.h b/sql/table.h
index 2bad6cbf32f..d289b6e0ab2 100644
--- a/sql/table.h
+++ b/sql/table.h
@@ -2932,9 +2932,11 @@ typedef struct st_nested_join
     Before each use the counters are zeroed by reset_nj_counters.
   */
   uint              counter;
+
   /*
-    Number of elements in join_list that were not (or contain table(s) that 
-    weren't) removed by table elimination.
+    Number of elements in join_list that participate in the join plan choice:
+    - Base tables that were not removed by table elimination
+    - Join nests that were not removed by mark_join_nest_as_const
   */
   uint              n_tables;
   nested_join_map   nj_map;          /* Bit used to identify this nested join*/