MDEV-22377: Subquery in an UPDATE query uses full scan instead of range

[Patch idea by Igor Babaev]

Symptom: for IN (SELECT ...) subqueries using IN-to-EXISTS transformation,
the optimizer was unable to make inferences using multiple equalities.

The cause is code Item_in_subselect::inject_in_to_exists_cond() which may
break invariants that Multiple-Equality code relies on. In particular, it
may produce a WHERE condition with an empty Item_cond::m_cond_equal.

Fixed this by making Item_cond::m_cond_equal.

7 files changed, 92 insertions, 14 deletions

diff --git a/mysql-test/r/subselect2.result b/mysql-test/r/subselect2.result
index 155d5ab2a50..91d3e445b48 100644
--- a/mysql-test/r/subselect2.result
+++ b/mysql-test/r/subselect2.result
@@ -262,7 +262,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 2	DEPENDENT SUBQUERY	t2c	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where; Using join buffer (incremental, BNL join)
 Warnings:
 Note	1276	Field or reference 'test.t1.a' of SELECT #2 was resolved in SELECT #1
-Note	1003	select `test`.`t1`.`a` AS `a`,`test`.`t1`.`c1` AS `c1` from `test`.`t1` where !<expr_cache><`test`.`t1`.`c1`,`test`.`t1`.`a`>(<in_optimizer>(`test`.`t1`.`c1`,<exists>(select `test`.`t2a`.`c2` from `test`.`t2` `t2a` join `test`.`t2` `t2b` join `test`.`t2` `t2c` where (`test`.`t2b`.`m` <> `test`.`t1`.`a` or `test`.`t2b`.`m` = `test`.`t2a`.`m`) and trigcond(<cache>(`test`.`t1`.`c1`) = `test`.`t2a`.`c2` or `test`.`t2a`.`c2` is null) and `test`.`t2c`.`c2` = `test`.`t2b`.`c2` and `test`.`t2b`.`n` = `test`.`t2a`.`m` having trigcond(`test`.`t2a`.`c2` is null))))
+Note	1003	select `test`.`t1`.`a` AS `a`,`test`.`t1`.`c1` AS `c1` from `test`.`t1` where !<expr_cache><`test`.`t1`.`c1`,`test`.`t1`.`a`>(<in_optimizer>(`test`.`t1`.`c1`,<exists>(select `test`.`t2a`.`c2` from `test`.`t2` `t2a` join `test`.`t2` `t2b` join `test`.`t2` `t2c` where `test`.`t2c`.`c2` = `test`.`t2b`.`c2` and `test`.`t2b`.`n` = `test`.`t2a`.`m` and (`test`.`t2b`.`m` <> `test`.`t1`.`a` or `test`.`t2b`.`m` = `test`.`t2a`.`m`) and trigcond(<cache>(`test`.`t1`.`c1`) = `test`.`t2a`.`c2` or `test`.`t2a`.`c2` is null) having trigcond(`test`.`t2a`.`c2` is null))))
 DROP TABLE t1,t2;
 #
 # MDEV-614, also MDEV-536, also LP:1050806:
diff --git a/mysql-test/r/subselect3.result b/mysql-test/r/subselect3.result
index 8d33e4e1606..d92626380ef 100644
--- a/mysql-test/r/subselect3.result
+++ b/mysql-test/r/subselect3.result
@@ -169,7 +169,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 2	DEPENDENT SUBQUERY	t2	ref	a	a	5	test.t1.b	1	100.00	Using where
 Warnings:
 Note	1276	Field or reference 'test.t3.oref' of SELECT #2 was resolved in SELECT #1
-Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where `test`.`t2`.`b` = `test`.`t3`.`oref` and trigcond(<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a` or `test`.`t1`.`a` is null) and `test`.`t2`.`a` = `test`.`t1`.`b` having trigcond(`test`.`t1`.`a` is null)))) AS `Z` from `test`.`t3`
+Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where `test`.`t2`.`a` = `test`.`t1`.`b` and `test`.`t2`.`b` = `test`.`t3`.`oref` and trigcond(<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a` or `test`.`t1`.`a` is null) having trigcond(`test`.`t1`.`a` is null)))) AS `Z` from `test`.`t3`
 drop table t1, t2, t3;
 create table t1 (a int NOT NULL, b int NOT NULL, key(a));
 insert into t1 values 
@@ -197,7 +197,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 2	DEPENDENT SUBQUERY	t2	ref	a	a	4	test.t1.b	1	100.00	Using where
 Warnings:
 Note	1276	Field or reference 'test.t3.oref' of SELECT #2 was resolved in SELECT #1
-Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where `test`.`t2`.`b` = `test`.`t3`.`oref` and trigcond(<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a`) and `test`.`t2`.`a` = `test`.`t1`.`b`))) AS `Z` from `test`.`t3`
+Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where `test`.`t2`.`a` = `test`.`t1`.`b` and `test`.`t2`.`b` = `test`.`t3`.`oref` and trigcond(<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a`)))) AS `Z` from `test`.`t3`
 drop table t1,t2,t3;
 create table t1 (oref int, grp int);
 insert into t1 (oref, grp) values
diff --git a/mysql-test/r/subselect3_jcl6.result b/mysql-test/r/subselect3_jcl6.result
index 6d1e305bc49..2df3f2eea35 100644
--- a/mysql-test/r/subselect3_jcl6.result
+++ b/mysql-test/r/subselect3_jcl6.result
@@ -172,7 +172,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 2	DEPENDENT SUBQUERY	t2	ref	a	a	5	test.t1.b	1	100.00	Using where; Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
 Warnings:
 Note	1276	Field or reference 'test.t3.oref' of SELECT #2 was resolved in SELECT #1
-Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where `test`.`t2`.`b` = `test`.`t3`.`oref` and trigcond(<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a` or `test`.`t1`.`a` is null) and `test`.`t2`.`a` = `test`.`t1`.`b` having trigcond(`test`.`t1`.`a` is null)))) AS `Z` from `test`.`t3`
+Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where `test`.`t2`.`a` = `test`.`t1`.`b` and `test`.`t2`.`b` = `test`.`t3`.`oref` and trigcond(<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a` or `test`.`t1`.`a` is null) having trigcond(`test`.`t1`.`a` is null)))) AS `Z` from `test`.`t3`
 drop table t1, t2, t3;
 create table t1 (a int NOT NULL, b int NOT NULL, key(a));
 insert into t1 values 
@@ -200,7 +200,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 2	DEPENDENT SUBQUERY	t2	ref	a	a	4	test.t1.b	1	100.00	Using where; Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
 Warnings:
 Note	1276	Field or reference 'test.t3.oref' of SELECT #2 was resolved in SELECT #1
-Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where `test`.`t2`.`b` = `test`.`t3`.`oref` and trigcond(<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a`) and `test`.`t2`.`a` = `test`.`t1`.`b`))) AS `Z` from `test`.`t3`
+Note	1003	select `test`.`t3`.`a` AS `a`,`test`.`t3`.`oref` AS `oref`,<expr_cache><`test`.`t3`.`a`,`test`.`t3`.`oref`>(<in_optimizer>(`test`.`t3`.`a`,<exists>(select `test`.`t1`.`a` from `test`.`t1` join `test`.`t2` where `test`.`t2`.`a` = `test`.`t1`.`b` and `test`.`t2`.`b` = `test`.`t3`.`oref` and trigcond(<cache>(`test`.`t3`.`a`) = `test`.`t1`.`a`)))) AS `Z` from `test`.`t3`
 drop table t1,t2,t3;
 create table t1 (oref int, grp int);
 insert into t1 (oref, grp) values
diff --git a/mysql-test/r/subselect4.result b/mysql-test/r/subselect4.result
index 2657977dae7..43e698d2b56 100644
--- a/mysql-test/r/subselect4.result
+++ b/mysql-test/r/subselect4.result
@@ -2351,7 +2351,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t2	system	NULL	NULL	NULL	NULL	1	100.00	
 2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where
 Warnings:
-Note	1003	select 3 AS `f` from dual where !<expr_cache><3>(<in_optimizer>(3,<exists>(select `test`.`t1`.`b` from `test`.`t1` where (`test`.`t1`.`c` = 'USA' or `test`.`t1`.`c` <> 'USA') and trigcond(<cache>(3) = `test`.`t1`.`b` or `test`.`t1`.`b` is null) and `test`.`t1`.`b` = `test`.`t1`.`a` having trigcond(`test`.`t1`.`b` is null))))
+Note	1003	select 3 AS `f` from dual where !<expr_cache><3>(<in_optimizer>(3,<exists>(select `test`.`t1`.`b` from `test`.`t1` where `test`.`t1`.`b` = `test`.`t1`.`a` and (`test`.`t1`.`c` = 'USA' or `test`.`t1`.`c` <> 'USA') and trigcond(<cache>(3) = `test`.`t1`.`b` or `test`.`t1`.`b` is null) having trigcond(`test`.`t1`.`b` is null))))
 SELECT * FROM t2 
 WHERE f NOT IN (SELECT b FROM t1
 WHERE 0 OR (c IN ('USA') OR c NOT IN ('USA')) AND a = b);
@@ -2803,4 +2803,42 @@ FROM (t1 JOIN t1 AS ref_t1 ON
 (t1.i1 > (SELECT ref_t1.i1 AS c0 FROM t1 b ORDER BY -c0)));
 ERROR 21000: Subquery returns more than 1 row
 DROP TABLE t1;
+#
+# MDEV-22377: Subquery in an UPDATE query uses full scan instead of range
+#
+CREATE TABLE t1 (
+key1 varchar(30) NOT NULL,
+col1 int(11) NOT NULL,
+filler char(100)
+);
+insert into t1 select seq, seq, seq from seq_1_to_100;
+CREATE TABLE t10 (
+key1 varchar(30) NOT NULL,
+col1 int,
+filler char(100),
+PRIMARY KEY (key1)
+);
+insert into t10 select seq, seq, seq from seq_1_to_1000;
+CREATE TABLE t11 (
+key1 varchar(30) NOT NULL,
+filler char(100),
+PRIMARY KEY (key1)
+);
+insert into t11 select seq, seq from seq_1_to_1000;
+set @tmp_os=@@optimizer_switch;
+set optimizer_switch='semijoin=off,materialization=off';
+# Must use range access (not full scan) for table tms:
+explain select * from t1 hist
+WHERE
+key1 IN ('1','2','3','4','5','6','7','8','9','10') AND
+hist.col1 NOT IN (SELECT tn.col1
+FROM t10 tn JOIN t11 tms ON tms.key1 = tn.key1
+WHERE tn.key1 IN ('1','2','3','4','5','6','7','8','9','10')
+);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	hist	ALL	NULL	NULL	NULL	NULL	100	Using where
+2	DEPENDENT SUBQUERY	tms	range	PRIMARY	PRIMARY	32	NULL	10	Using where; Using index
+2	DEPENDENT SUBQUERY	tn	eq_ref	PRIMARY	PRIMARY	32	test.tms.key1	1	Using where
+set optimizer_switch=@tmp_os;
+drop table t1, t10, t11;
 # End of 10.2 tests
diff --git a/mysql-test/r/subselect_mat_cost_bugs.result b/mysql-test/r/subselect_mat_cost_bugs.result
index fd768b1efd4..87cbc1bb078 100644
--- a/mysql-test/r/subselect_mat_cost_bugs.result
+++ b/mysql-test/r/subselect_mat_cost_bugs.result
@@ -100,7 +100,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 2	DEPENDENT SUBQUERY	t2	index	c3	c3	9	NULL	2	100.00	Using where; Using index; Using join buffer (flat, BNL join)
 Warnings:
 Note	1276	Field or reference 'test.t1.pk' of SELECT #2 was resolved in SELECT #1
-Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` where <expr_cache><`test`.`t1`.`c1`,`test`.`t1`.`pk`>(<in_optimizer>(`test`.`t1`.`c1`,<exists>(select `test`.`t1a`.`c1` from `test`.`t1b` join `test`.`t2` left join `test`.`t1a` on(`test`.`t1a`.`c2` = `test`.`t1b`.`pk` and 2) where `test`.`t1`.`pk` <> 0 and <cache>(`test`.`t1`.`c1`) = `test`.`t1a`.`c1` and `test`.`t2`.`c3` = `test`.`t1b`.`c4`)))
+Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` where <expr_cache><`test`.`t1`.`c1`,`test`.`t1`.`pk`>(<in_optimizer>(`test`.`t1`.`c1`,<exists>(select `test`.`t1a`.`c1` from `test`.`t1b` join `test`.`t2` left join `test`.`t1a` on(`test`.`t1a`.`c2` = `test`.`t1b`.`pk` and 2) where `test`.`t2`.`c3` = `test`.`t1b`.`c4` and `test`.`t1`.`pk` <> 0 and <cache>(`test`.`t1`.`c1`) = `test`.`t1a`.`c1`)))
 SELECT pk
 FROM t1
 WHERE c1 IN
@@ -363,7 +363,7 @@ AND a = SOME (SELECT b FROM t5));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	2	Using where
 2	DEPENDENT SUBQUERY	t5	index	c	c	10	NULL	2	Using where; Using index; Start temporary
-2	DEPENDENT SUBQUERY	t4	eq_ref	PRIMARY	PRIMARY	4	test.t5.b	1	Using index condition; Using where; End temporary
+2	DEPENDENT SUBQUERY	t4	eq_ref	PRIMARY	PRIMARY	4	test.t5.b	1	Using where; End temporary
 SELECT *
 FROM t3
 WHERE t3.b > ALL (
diff --git a/mysql-test/t/subselect4.test b/mysql-test/t/subselect4.test
index 93389571c5c..1313d2e49e7 100644
--- a/mysql-test/t/subselect4.test
+++ b/mysql-test/t/subselect4.test
@@ -2308,4 +2308,47 @@ FROM (t1 JOIN t1 AS ref_t1 ON
 
 DROP TABLE t1;
 
+--echo #
+--echo # MDEV-22377: Subquery in an UPDATE query uses full scan instead of range
+--echo #
+
+CREATE TABLE t1 (
+  key1 varchar(30) NOT NULL,
+  col1 int(11) NOT NULL,
+  filler char(100)
+);
+insert into t1 select seq, seq, seq from seq_1_to_100;
+
+CREATE TABLE t10 (
+  key1 varchar(30) NOT NULL,
+  col1 int,
+  filler char(100),
+  PRIMARY KEY (key1)
+);
+insert into t10 select seq, seq, seq from seq_1_to_1000;
+
+CREATE TABLE t11 (
+  key1 varchar(30) NOT NULL,
+  filler char(100),
+  PRIMARY KEY (key1)
+);
+insert into t11 select seq, seq from seq_1_to_1000;
+
+
+set @tmp_os=@@optimizer_switch;
+set optimizer_switch='semijoin=off,materialization=off';
+
+--echo # Must use range access (not full scan) for table tms:
+explain select * from t1 hist
+WHERE
+  key1 IN ('1','2','3','4','5','6','7','8','9','10') AND
+  hist.col1 NOT IN (SELECT tn.col1
+                    FROM t10 tn JOIN t11 tms ON tms.key1 = tn.key1
+                    WHERE tn.key1 IN ('1','2','3','4','5','6','7','8','9','10')
+                   );
+
+set optimizer_switch=@tmp_os;
+
+drop table t1, t10, t11;
+
 --echo # End of 10.2 tests
diff --git a/sql/item_subselect.cc b/sql/item_subselect.cc
index 25621dfe104..92ba085af5b 100644
--- a/sql/item_subselect.cc
+++ b/sql/item_subselect.cc
@@ -2769,12 +2769,9 @@ bool Item_in_subselect::inject_in_to_exists_cond(JOIN *join_arg)
     {
       /* The argument list of the top-level AND may change after fix fields. */
       and_args= ((Item_cond*) join_arg->conds)->argument_list();
-      List_iterator<Item_equal> li(join_arg->cond_equal->current_level);
-      Item_equal *elem;
-      while ((elem= li++))
-      {
-        and_args->push_back(elem, thd->mem_root);
-      }
+      ((Item_cond_and *) (join_arg->conds))->m_cond_equal=
+                                             *join_arg->cond_equal;
+      and_args->append((List<Item> *)&join_arg->cond_equal->current_level);
     }
   }