MWL#89: Cost-based choice between Materialization and IN->EXISTS transformation

Merge 5.3-mwl89 into 5.3 main.

There is one remaining test failure in this merge:
innodb_mysql_lock2. All other tests have been checked to
deliver the same results/explains as 5.3-mwl89, including
the few remaining wrong results.

3 files changed, 298 insertions, 21 deletions

diff --git a/mysql-test/t/subselect3.test b/mysql-test/t/subselect3.test
index a621c4c776c..3f63149ce96 100644
--- a/mysql-test/t/subselect3.test
+++ b/mysql-test/t/subselect3.test
@@ -681,7 +681,8 @@ SELECT a, ROW(11, 12) = (SELECT a, 12), ROW(11, 12) IN (SELECT a, 12) FROM t1;
 # The x alias is used below to workaround bug #40674.
 # Regression tests for sum function on outer column in subselect from dual:
 SELECT a AS x, ROW(11, 12) = (SELECT MAX(x), 22), ROW(11, 12) IN (SELECT MAX(x), 22) FROM t1;
---echo # 2nd and 3rd columns should be same for x == 11 only
+--echo # 2nd and 3rd columns should be same
+EXPLAIN SELECT a AS x, ROW(11, 12) = (SELECT MAX(x), 12), ROW(11, 12) IN (SELECT MAX(x), 12) FROM t1;
 SELECT a AS x, ROW(11, 12) = (SELECT MAX(x), 12), ROW(11, 12) IN (SELECT MAX(x), 12) FROM t1;
 
 DROP TABLE t1;
diff --git a/mysql-test/t/subselect_mat.test b/mysql-test/t/subselect_mat.test
index 0209bf66a57..9a3e8352a2c 100644
--- a/mysql-test/t/subselect_mat.test
+++ b/mysql-test/t/subselect_mat.test
@@ -48,7 +48,7 @@ insert into t2i select * from t2;
 insert into t3i select * from t3;
 
 # force the use of materialization
-set @@optimizer_switch='semijoin=off';
+set @@optimizer_switch='materialization=on,in_to_exists=off,semijoin=off';
 
 /******************************************************************************
 * Simple tests.
@@ -111,22 +111,22 @@ select * from t1 where (a1, a2) in (select b1, min(b2) from t2i limit 1,1);
 
 # test re-optimization/re-execution with different execution methods
 # prepare once, exec with different modes
-set @@optimizer_switch='default,semijoin=off';
+set @@optimizer_switch='materialization=on,in_to_exists=off,semijoin=on';
 prepare st1 from
 "select * from t1 where (a1, a2) in (select b1, min(b2) from t2 where b1 > '0' group by b1)";
-set @@optimizer_switch='default,materialization=off';
+set @@optimizer_switch='materialization=off,in_to_exists=on,semijoin=on';
 execute st1;
-set @@optimizer_switch='default,semijoin=off';
+set @@optimizer_switch='materialization=on,in_to_exists=off,semijoin=on';
 execute st1;
 
-set @@optimizer_switch='default,materialization=off';
+set @@optimizer_switch='materialization=off,in_to_exists=on,semijoin=on';
 prepare st1 from
 "select * from t1 where (a1, a2) in (select b1, min(b2) from t2 where b1 > '0' group by b1)";
-set @@optimizer_switch='default,semijoin=off';
+set @@optimizer_switch='materialization=on,in_to_exists=off,semijoin=off';
 execute st1;
-set @@optimizer_switch='default,materialization=off';
+set @@optimizer_switch='materialization=off,in_to_exists=on,semijoin=on';
 execute st1;
-set @@optimizer_switch='default,semijoin=off';
+set @@optimizer_switch='materialization=on,in_to_exists=off,semijoin=off';
 
 # materialize the result of ORDER BY
 # non-indexed fields
@@ -327,7 +327,7 @@ select * from t1 order by (select col from columns limit 1);
   Test that BLOBs are not materialized (except when arguments of some functions).
 */
 # force materialization to be always considered
-set @@optimizer_switch='semijoin=off';
+set @@optimizer_switch='materialization=on,in_to_exists=off,semijoin=off';
 set @prefix_len = 6;
 
 # BLOB == 16 (small blobs that could be stored in HEAP tables)
@@ -680,7 +680,7 @@ insert into t2bit values (b'001', b'101');
 insert into t2bit values (b'010', b'110');
 insert into t2bit values (b'110', b'111');
 
-set @@optimizer_switch='semijoin=off';
+set @@optimizer_switch='materialization=on,in_to_exists=off,semijoin=off';
 
 explain extended select bin(a1), bin(a2)
 from t1bit
@@ -718,7 +718,7 @@ drop table t1, t2, t3, t1i, t2i, t3i, columns;
 /******************************************************************************
 * Test the cache of the left operand of IN.
 ******************************************************************************/
-set @@optimizer_switch='semijoin=off';
+set @@optimizer_switch='materialization=on,in_to_exists=off,semijoin=off';
 
 # Test that default values of Cached_item are not used for comparison
 create table t1 (s1 int);
@@ -812,23 +812,28 @@ drop table t2;
 create table t1 (a1 int key);
 create table t2 (b1 int);
 insert into t1 values (5);
-
+-- echo Only the last query returns correct result. Filed as BUG#40037.
 # Query with group by, executed via materialization
+set @@optimizer_switch='materialization=on,in_to_exists=off,semijoin=off';
 explain select min(a1) from t1 where 7 in (select b1 from t2 group by b1);
 select min(a1) from t1 where 7 in (select b1 from t2 group by b1);
 # Query with group by, executed via IN=>EXISTS
-set @@optimizer_switch='default,materialization=off';
+set @@optimizer_switch='materialization=off,in_to_exists=on,semijoin=off';
 explain select min(a1) from t1 where 7 in (select b1 from t2 group by b1);
 select min(a1) from t1 where 7 in (select b1 from t2 group by b1);
 
 # Executed with materialization
-set @@optimizer_switch='default,semijoin=off';
+set @@optimizer_switch='materialization=on,in_to_exists=off,semijoin=off';
+explain select min(a1) from t1 where 7 in (select b1 from t2);
+select min(a1) from t1 where 7 in (select b1 from t2);
+# Executed via IN=>EXISTS
+set @@optimizer_switch='materialization=off,in_to_exists=on,semijoin=off';
 explain select min(a1) from t1 where 7 in (select b1 from t2);
 select min(a1) from t1 where 7 in (select b1 from t2);
 # Executed with semi-join. Notice, this time we get a different result (NULL).
-# This is the only correct result of all four queries. This difference is
+# This is the only correct result of all five queries. This difference is
 # filed as BUG#40037.
-set @@optimizer_switch='default,materialization=off';
+set @@optimizer_switch='materialization=off,in_to_exists=off,semijoin=on';
 explain select min(a1) from t1 where 7 in (select b1 from t2);
 select min(a1) from t1 where 7 in (select b1 from t2);
 drop table t1,t2;
@@ -840,7 +845,7 @@ create table t1 (a char(2), b varchar(10));
 insert into t1 values ('a',  'aaa');
 insert into t1 values ('aa', 'aaaa');
 
-set @@optimizer_switch='default,semijoin=off';
+set @@optimizer_switch='materialization=on,in_to_exists=off,semijoin=off';
 explain select a,b from t1 where b in (select a from t1);
 select a,b from t1 where b in (select a from t1);
 prepare st1 from "select a,b from t1 where b in (select a from t1)";
@@ -861,7 +866,7 @@ CREATE TABLE t2 LIKE t1;
 INSERT INTO t2 VALUES (1, 1.789);
 INSERT INTO t2 VALUES (13, 1.454);
 
-SET @@optimizer_switch='default,semijoin=on,materialization=on';
+SET @@optimizer_switch='materialization=on,in_to_exists=off,semijoin=on';
 EXPLAIN SELECT COUNT(*) FROM t1 WHERE (f1,f2) IN (SELECT f1,f2 FROM t2);
 SELECT COUNT(*) FROM t1 WHERE (f1,f2) IN (SELECT f1,f2 FROM t2);
 
@@ -883,7 +888,7 @@ INSERT INTO t1 VALUES (1,'o','ffff','ffff','ffoo'),(2,'f','ffff','ffff','ffff');
 CREATE TABLE t2 LIKE t1;
 INSERT INTO t2 VALUES (1,'i','iiii','iiii','iiii'),(2,'f','ffff','ffff','ffff');
 
-SET @@optimizer_switch='default,semijoin=on,materialization=on';
+SET @@optimizer_switch='materialization=on,in_to_exists=off,semijoin=on';
 EXPLAIN SELECT pk FROM t1 WHERE (a) IN (SELECT a FROM t2 WHERE pk > 0);
 SELECT pk FROM t1 WHERE (a) IN (SELECT a FROM t2 WHERE pk > 0);
 SELECT pk FROM t1 WHERE (b,c,d) IN (SELECT b,c,d FROM t2 WHERE pk > 0);
@@ -900,7 +905,7 @@ create table t3(i int);
 insert into t3 values (1), (2), (3), (4), (5), (6), (7), (8), (9), (10);
 select * from t1 where t1.i in (select t2.i from t2 join t3 where t2.i + t3.i = 5);
 set @save_optimizer_switch=@@optimizer_switch;
-set session optimizer_switch='materialization=off';
+set session optimizer_switch='materialization=off,in_to_exists=on';
 select * from t1 where t1.i in (select t2.i from t2 join t3 where t2.i + t3.i = 5);
 set session optimizer_switch=@save_optimizer_switch;
 drop table t1, t2, t3;
diff --git a/mysql-test/t/subselect_mat_cost.test b/mysql-test/t/subselect_mat_cost.test
new file mode 100644
index 00000000000..b817c05f7d4
--- /dev/null
+++ b/mysql-test/t/subselect_mat_cost.test
@@ -0,0 +1,271 @@
+#
+# Tets of cost-based choice between the materialization and in-to-exists
+# subquery execution strategies (MWL#89)
+#
+
+--disable_warnings
+drop table if exists t1, t2, t1_1024, t2_1024;
+drop procedure if exists make_t1_indexes;
+drop procedure if exists make_t2_indexes;
+drop procedure if exists remove_t1_indexes;
+drop procedure if exists remove_t2_indexes;
+drop procedure if exists add_materialization_data;
+drop procedure if exists delete_materialization_data;
+drop procedure if exists set_all_columns_not_null;
+drop procedure if exists set_all_columns_nullable;
+--enable_warnings
+
+create table t1 (a1 char(8), a2 char(8), a3 char(8), a4 int);
+insert into t1 values ('1 - 00', '2 - 00', '3 - 00', 0);
+insert into t1 values ('1 - 01', '2 - 01', '3 - 01', 1);
+insert into t1 values ('1 - 02', '2 - 02', '3 - 02', 2);
+
+create table t2 (b1 char(8), b2 char(8), b3 char(8), b4 int);
+insert into t2 values ('1 - 01', '2 - 01', '3 - 01', 1);
+insert into t2 values ('1 - 01', '2 - 01', '3 - 02', 2);
+insert into t2 values ('1 - 02', '2 - 02', '3 - 03', 3);
+insert into t2 values ('1 - 02', '2 - 02', '3 - 04', 4);
+insert into t2 values ('1 - 03', '2 - 03', '3 - 05', 5);
+
+create table t1_1024 (a1 blob(1024), a2 blob(1024));
+insert into t1_1024 values (concat('1 - 00', repeat('x', 1018)), concat('2 - 00', repeat('x', 1018)));
+insert into t1_1024 values (concat('1 - 01', repeat('x', 1018)), concat('2 - 01', repeat('x', 1018)));
+
+create table t2_1024 (b1 blob(1024), b2 blob(1024));
+insert into t2_1024 values (concat('1 - 01', repeat('x', 1018)), concat('2 - 01', repeat('x', 1018)));
+insert into t2_1024 values (concat('1 - 02', repeat('x', 1018)), concat('2 - 02', repeat('x', 1018)));
+insert into t2_1024 values (concat('1 - 03', repeat('x', 1018)), concat('2 - 03', repeat('x', 1018)));
+insert into t2_1024 values (concat('1 - 04', repeat('x', 1018)), concat('2 - 04', repeat('x', 1018)));
+
+delimiter |;
+create procedure make_t1_indexes()
+begin
+  create index it1i1 on t1 (a1);
+  create index it1i2 on t1 (a2);
+  create index it1i3 on t1 (a1, a2);
+  create index it1_1024i1 on t1_1024 (a1(6));
+  create index it1_1024i2 on t1_1024 (a2(6));
+  create index it1_1024i3 on t1_1024 (a1(6), a2(6));
+end|
+
+create procedure make_t2_indexes()
+begin
+  create index it2i1 on t2 (b1);
+  create index it2i2 on t2 (b2);
+  create index it2i3 on t2 (b1, b2);
+  create unique index it2i4 on t2 (b1, b2, b3);
+  create index it2_1024i1 on t2_1024 (b1(6));
+  create index it2_1024i2 on t2_1024 (b2(6));
+  create index it2_1024i3 on t2_1024 (b1(6), b2(6));
+end|
+
+create procedure remove_t1_indexes()
+begin
+  drop index it1i1 on t1;
+  drop index it1i2 on t1;
+  drop index it1i3 on t1;
+  drop index it1_1024i1 on t1_1024;
+  drop index it1_1024i2 on t1_1024;
+  drop index it1_1024i3 on t1_1024;
+end|
+
+create procedure remove_t2_indexes()
+begin
+  drop index it2i1 on t2;
+  drop index it2i2 on t2;
+  drop index it2i3 on t2;
+  drop index it2i4 on t2;
+  drop index it2_1024i1 on t2_1024;
+  drop index it2_1024i2 on t2_1024;
+  drop index it2_1024i3 on t2_1024;
+end|
+
+create procedure add_materialization_data()
+begin
+insert into t1 values ('1 - 03', '2 - 03', '3 - 03', 3);
+insert into t1 values ('1 - 04', '2 - 04', '3 - 04', 4);
+insert into t1 values ('1 - 05', '2 - 05', '3 - 05', 5);
+insert into t1 values ('1 - 06', '2 - 06', '3 - 06', 6);
+insert into t1 values ('1 - 07', '2 - 07', '3 - 07', 7);
+insert into t1_1024 values (concat('1 - 03', repeat('x', 1018)), concat('2 - 03', repeat('x', 1018)));
+end|
+
+create procedure delete_materialization_data()
+begin
+delete from t1 where a1 >= '1 - 03';
+delete from t1_1024 where a1 >= '1 - 03';
+end|
+
+create procedure set_all_columns_not_null()
+begin
+alter table t1 modify a1 char(8) not null, modify a2 char(8) not null, modify a3 char(8) not null;
+alter table t2 modify b1 char(8) not null, modify b2 char(8) not null, modify b3 char(8) not null;
+end|
+
+create procedure set_all_columns_nullable()
+begin
+alter table t1 modify a1 char(8) null, modify a2 char(8) null, modify a3 char(8) null;
+alter table t2 modify b1 char(8) null, modify b2 char(8) null, modify b3 char(8) null;
+end|
+
+delimiter ;|
+-- echo
+
+-- echo /******************************************************************************
+-- echo 1. Both materialization and in-to-exists are ON, make a cost-based choice.
+-- echo ******************************************************************************/
+set @@optimizer_switch='materialization=on,in_to_exists=on';
+-- echo 
+-- echo /* 1.1 In-to-exists is cheaper */
+call make_t1_indexes();
+
+-- echo /* 1.1.1 non-indexed table access */
+-- source include/subselect_mat_cost.inc
+
+-- echo /* 1.1.2 indexed table access, nullabale columns. */
+call make_t2_indexes();
+-- source include/subselect_mat_cost.inc
+
+-- echo /* 1.1.3 indexed table access, non-nullabale columns. */
+call set_all_columns_not_null();
+-- source include/subselect_mat_cost.inc
+call set_all_columns_nullable();
+
+-- echo 
+-- echo /* 1.2 Materialization is cheaper */
+# make materialization cheaper
+call add_materialization_data();
+call remove_t1_indexes();
+
+-- echo /* 1.2.1 non-indexed table access */
+call remove_t2_indexes();
+-- source include/subselect_mat_cost.inc
+
+-- echo /* 1.2.2 indexed table access, nullabale columns. */
+call make_t2_indexes();
+-- source include/subselect_mat_cost.inc
+
+-- echo /* 1.2.3 indexed table access, non-nullabale columns. */
+call set_all_columns_not_null();
+-- source include/subselect_mat_cost.inc
+call set_all_columns_nullable();
+
+
+-- echo /******************************************************************************
+-- echo 2. Materialization is OFF, in-to-exists is ON, materialization is cheaper.
+-- echo ******************************************************************************/
+set @@optimizer_switch='materialization=off,in_to_exists=on';
+
+-- echo /* 2.1 non-indexed table access */
+call remove_t2_indexes();
+-- source include/subselect_mat_cost.inc
+
+-- echo /* 2.2 indexed table access, nullabale columns. */
+call make_t2_indexes();
+-- source include/subselect_mat_cost.inc
+
+-- echo /* 2.3 indexed table access, non-nullabale columns. */
+call set_all_columns_not_null();
+-- source include/subselect_mat_cost.inc
+call set_all_columns_nullable();
+
+
+-- echo /******************************************************************************
+-- echo 3. Materialization is ON, in-to-exists is OFF, in-to-exists is cheaper.
+-- echo ******************************************************************************/
+set @@optimizer_switch='materialization=on,in_to_exists=off';
+# make IN-TO-EXISTS cheaper
+call delete_materialization_data();
+call make_t1_indexes();
+
+-- echo /* 3.1 non-indexed table access */
+call remove_t2_indexes();
+-- source include/subselect_mat_cost.inc
+
+-- echo /* 3.2 indexed table access, nullabale columns. */
+call make_t2_indexes();
+-- source include/subselect_mat_cost.inc
+
+-- echo /* 3.3 indexed table access, non-nullabale columns. */
+call set_all_columns_not_null();
+-- source include/subselect_mat_cost.inc
+call set_all_columns_nullable();
+
+
+drop procedure make_t1_indexes;
+drop procedure make_t2_indexes;
+drop procedure remove_t1_indexes;
+drop procedure remove_t2_indexes;
+drop procedure add_materialization_data;
+drop procedure delete_materialization_data;
+drop procedure set_all_columns_not_null;
+drop procedure set_all_columns_nullable;
+drop table t1, t2, t1_1024, t2_1024;
+
+--echo #
+--echo # LP BUG#643424 valgrind warning in choose_subquery_plan()
+--echo #
+
+CREATE TABLE t1 (
+  pk int(11) NOT NULL AUTO_INCREMENT,
+  c1 int(11) DEFAULT NULL,
+  c2 int(11) DEFAULT NULL,
+  PRIMARY KEY (pk),
+  KEY c2 (c2));
+
+INSERT INTO t1 VALUES (1,NULL,2);
+INSERT INTO t1 VALUES (2,7,9);
+INSERT INTO t1 VALUES (9,NULL,8);
+
+CREATE TABLE t2 (
+  pk int(11) NOT NULL AUTO_INCREMENT,
+  c1 int(11) DEFAULT NULL,
+  c2 int(11) DEFAULT NULL,
+  PRIMARY KEY (pk),
+  KEY c2 (c2));
+
+INSERT INTO t2 VALUES (1,1,7);
+
+set @save_optimizer_switch=@@optimizer_switch;
+set @@optimizer_switch='materialization=on,in_to_exists=on,semijoin=off';
+
+SELECT pk FROM t1 WHERE (c2, c1) IN (SELECT c2, c2 FROM t2);
+
+set session optimizer_switch=@save_optimizer_switch;
+
+drop table t1, t2;
+
+
+--echo #
+--echo # LP BUG#652727 Crash in create_ref_for_key()
+--echo #
+
+CREATE TABLE t2 (
+  pk int(11) NOT NULL AUTO_INCREMENT,
+  c1 int(11) DEFAULT NULL,
+  PRIMARY KEY (pk));
+
+INSERT INTO t2 VALUES (10,7);
+INSERT INTO t2 VALUES (11,1);
+INSERT INTO t2 VALUES (17,NULL);
+
+CREATE TABLE t1 (
+  pk int(11) NOT NULL AUTO_INCREMENT,
+  c1 int(11) DEFAULT NULL,
+  PRIMARY KEY (pk));
+
+INSERT INTO t1 VALUES (15,1);
+INSERT INTO t1 VALUES (19,NULL);
+
+CREATE TABLE t3 (c2 int(11) DEFAULT NULL, KEY c2 (c2));
+INSERT INTO t3 VALUES (1);
+
+set @save_optimizer_switch=@@optimizer_switch;
+set @@optimizer_switch='materialization=on,in_to_exists=on,semijoin=off';
+
+SELECT c2
+FROM t3
+WHERE (2, 6) IN (SELECT t1.c1, t1.c1 FROM t1 STRAIGHT_JOIN t2 ON t2.pk = t1.pk);
+
+set session optimizer_switch=@save_optimizer_switch;
+drop table t1, t2, t3;