Fix bug lp:869036

Apart from the fix, the patch also adds few more unrelated test
cases for partial matching, and fixes few typos.

Analysis:
This bug uncovered that partial matching via rowid intersection
didn't handle the case when:
- the left IN argument has some NULLs,
- there are no non-null value matches, and there is no non-null
  column,
- the subquery columns that are not covered with the NULLs in
  the left IN argument contain at least one row, such that it
  has NULL values in all columns where the left IN operand has
  no NULLs.
In this case there is a partial match.

In addition the analysis of the related code uncovered incorrect
handling of few other related cases.

Solution:
The solution for the bug is to check if there exists a row with
NULLs in all columns other than the ones having NULL in the
let IN operand.

The check is implemented via checking whether the bitmaps that
store NULL information in class Ordered_key have a non-empty
intersection for the relevant columns.

The intersection itself is implemented via the function
bitmap_exists_intersection() in my_bitmap.c.

1 files changed, 593 insertions, 17 deletions

diff --git a/mysql-test/r/subselect_partial_match.result b/mysql-test/r/subselect_partial_match.result
index 1b39381b42b..dddf5e2d8d6 100644
--- a/mysql-test/r/subselect_partial_match.result
+++ b/mysql-test/r/subselect_partial_match.result
@@ -3,11 +3,13 @@ set @save_optimizer_switch=@@optimizer_switch;
 Part 1: Feature tests.
 -------------------------------
 Default for all tests.
-set @@optimizer_switch="materialization=on,in_to_exists=off,semijoin=off,subquery_cache=off";
-
+set @@optimizer_switch = "materialization=on,in_to_exists=off,semijoin=off,subquery_cache=off";
+set @test_default_opt_switch = @@optimizer_switch;
+set @in_exists = "materialization=off,in_to_exists=on,semijoin=off,subquery_cache=off";
+-------------------------------------------------------------------------
 Schema requires partial matching, but data analysis discoveres there is
 no need. This is possible only if all outer columns are not NULL.
-
+-------------------------------------------------------------------------
 create table t1 (a1 char(8) not null, a2 char(8) not null);
 create table t2 (b1 char(8), b2 char(8));
 insert into t1 values ('1 - 00', '2 - 00');
@@ -26,9 +28,9 @@ a1	a2	in_res
 1 - 00	2 - 00	0
 1 - 01	2 - 01	NULL
 drop table t1, t2;
-
+-------------------------------------------------------------------------
 NULLs in the outer columns, no NULLs in the suqbuery 
-
+-------------------------------------------------------------------------
 create table t1 (a1 char(8), a2 char(8));
 create table t2 (b1 char(8) not null, b2 char(8) not null);
 insert into t1 values (NULL    , '2 - 00');
@@ -55,17 +57,532 @@ NULL	2 - 00	NULL
 1 - 01	2 - 01	1
 NULL	NULL	NULL
 drop table t1, t2;
-
+-------------------------------------------------------------------------
+NULLs in the outer column, NULLs in the subquery, there is
+no value match in any column, but there is a partial match
+such that some of the matching NULLs are in the outer columns,
+the other NULLs are in the inner columns.
+-------------------------------------------------------------------------
+create table t1 (a1 char(1), a2 char(1), a3 char(1));
+create table t2 (b1 char(1), b2 char(1), b3 char(1));
+insert into t1 values ('c',  NULL, 'a');
+insert into t2 values (NULL,  'x', NULL);
+insert into t2 values (NULL,  'y', NULL);
+insert into t2 values ('o',   'z', 'p');
+set @@optimizer_switch='partial_match_rowid_merge=on,partial_match_table_scan=off';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	3	
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+a1	a2	a3	in_res
+c	NULL	a	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	3	
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+a1	a2	a3
+set @@optimizer_switch='partial_match_rowid_merge=off,partial_match_table_scan=on';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	3	
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+a1	a2	a3	in_res
+c	NULL	a	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	3	
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+a1	a2	a3
+set @@optimizer_switch=@in_exists;
+EXPLAIN
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	3	Using where
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+a1	a2	a3	in_res
+c	NULL	a	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	3	Using where
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+a1	a2	a3
+set @@optimizer_switch = @test_default_opt_switch;
+drop table t1, t2;
+create table t1 (a1 char(1), a2 char(1) not null, a3 char(1));
+create table t2 (b1 char(1), b2 char(1),          b3 char(1));
+insert into t1 values (NULL,  'y', NULL);
+insert into t2 values ('v', 'x', NULL);
+insert into t2 values (NULL, 'y', 'w');
+set @@optimizer_switch='partial_match_rowid_merge=on,partial_match_table_scan=off';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+a1	a2	a3	in_res
+NULL	y	NULL	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+a1	a2	a3
+set @@optimizer_switch='partial_match_rowid_merge=off,partial_match_table_scan=on';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+a1	a2	a3	in_res
+NULL	y	NULL	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+a1	a2	a3
+set @@optimizer_switch=@in_exists;
+EXPLAIN
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+a1	a2	a3	in_res
+NULL	y	NULL	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+a1	a2	a3
+set @@optimizer_switch = @test_default_opt_switch;
+drop table t1, t2;
+-------------------------------------------------------------------------
+There is only one column in the subquery to complement the NULLs in the
+outer reference. It is a NULL column, so a match is guaranteed.
+-------------------------------------------------------------------------
+create table t1 (a1 char(1), a2 char(1), a3 char(1));
+create table t2 (b1 char(1), b2 char(1), b3 char(1));
+insert into t1 values (NULL,  'g', NULL);
+insert into t2 values ('z',  NULL, 'y');
+insert into t2 values (NULL, 'z', 'y');
+set @@optimizer_switch='partial_match_rowid_merge=on,partial_match_table_scan=off';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+a1	a2	a3	in_res
+NULL	g	NULL	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+a1	a2	a3
+set @@optimizer_switch='partial_match_rowid_merge=off,partial_match_table_scan=on';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+a1	a2	a3	in_res
+NULL	g	NULL	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+a1	a2	a3
+set @@optimizer_switch=@in_exists;
+EXPLAIN
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+a1	a2	a3	in_res
+NULL	g	NULL	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+a1	a2	a3
+set @@optimizer_switch = @test_default_opt_switch;
+drop table t1, t2;
+-------------------------------------------------------------------------
+The intersection of the NULL bitmaps is empty because the ranges
+of NULL bits do not overlap.
+-------------------------------------------------------------------------
+create table t1 (a1 char(1), a2 char(1), a3 char(1));
+create table t2 (b1 char(1), b2 char(1), b3 char(1));
+insert into t1 values ('b',  'g', NULL);
+insert into t2 values ('z',  NULL, 'y');
+insert into t2 values (NULL, 'z', 'y');
+set @@optimizer_switch='partial_match_rowid_merge=on,partial_match_table_scan=off';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+a1	a2	a3	in_res
+b	g	NULL	0
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+a1	a2	a3
+b	g	NULL
+set @@optimizer_switch='partial_match_rowid_merge=off,partial_match_table_scan=on';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+a1	a2	a3	in_res
+b	g	NULL	0
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+a1	a2	a3
+b	g	NULL
+set @@optimizer_switch=@in_exists;
+EXPLAIN
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
+SELECT t1.*, (a1, a2, a3) IN (select * from t2) as in_res from t1;
+a1	a2	a3	in_res
+b	g	NULL	0
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
+SELECT * from t1 where (a1, a2, a3) NOT IN (select * from t2);
+a1	a2	a3
+b	g	NULL
+drop table t1, t2;
+-------------------------------------------------------------------------
+The intersection of the NULL bitmaps is non-empty, and there is a
+non-NULL column.
+-------------------------------------------------------------------------
+create table t1 (a1 char(1), a2 char(1), a3 char(1) not null, a4 char(10));
+create table t2 (b1 char(1), b2 char(1), b3 char(1),          b4 char(1));
+insert into t1 values ('a',  'g', 'x', NULL);
+insert into t2 values ('z',  NULL, 'y', 'x');
+insert into t2 values (NULL, NULL, 'x', 'y');
+insert into t2 values ('x',  'w', 'z', NULL);
+set @@optimizer_switch='partial_match_rowid_merge=on,partial_match_table_scan=off';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	3	Using where
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+a1	a2	a3	a4	in_res
+a	g	x	NULL	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	3	Using where
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+a1	a2	a3	a4
+set @@optimizer_switch='partial_match_rowid_merge=off,partial_match_table_scan=on';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	3	Using where
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+a1	a2	a3	a4	in_res
+a	g	x	NULL	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	3	Using where
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+a1	a2	a3	a4
+set @@optimizer_switch=@in_exists;
+EXPLAIN
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	3	Using where
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+a1	a2	a3	a4	in_res
+a	g	x	NULL	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	3	Using where
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+a1	a2	a3	a4
+drop table t1, t2;
+-------------------------------------------------------------------------
+Value match in one row, but the NULL complement match in another.
+The result must be false.
+-------------------------------------------------------------------------
+create table t1 (a1 char(2), a2 char(1), a3 char(1) not null, a4 char(10));
+create table t2 (b1 char(2), b2 char(1), b3 char(1),          b4 char(1));
+insert into t1 values ('99',  NULL, 'j', 'f');
+insert into t2 values ('01',  NULL, 'y', NULL);
+insert into t2 values ('02',  NULL, 'x', 'y');
+insert into t2 values ('03',  'q', 'y', 'x');
+insert into t2 values (NULL,  'q', 'm', 'p');
+insert into t2 values ('m', 'z', 'j', NULL);
+insert into t2 values (NULL, 'z', 'b', NULL);
+insert into t2 values (NULL, 'z', 'a', NULL);
+insert into t2 values ('34',  'q', 'y', 'x');
+set @@optimizer_switch='partial_match_rowid_merge=on,partial_match_table_scan=off';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	8	Using where
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+a1	a2	a3	a4	in_res
+99	NULL	j	f	0
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	8	Using where
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+a1	a2	a3	a4
+99	NULL	j	f
+set @@optimizer_switch='partial_match_rowid_merge=off,partial_match_table_scan=on';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	8	Using where
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+a1	a2	a3	a4	in_res
+99	NULL	j	f	0
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	8	Using where
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+a1	a2	a3	a4
+99	NULL	j	f
+set @@optimizer_switch=@in_exists;
+EXPLAIN
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	8	Using where
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+a1	a2	a3	a4	in_res
+99	NULL	j	f	0
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	8	Using where
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+a1	a2	a3	a4
+99	NULL	j	f
+drop table t1, t2;
+-------------------------------------------------------------------------
+Test the intersection of larger number of rows with NULL, such that
+the number is at the boundary 32. This test is based on the implementation
+of MY_BITMAP which uses 32 bit words, and the intersection operation works
+by intersecting the bitmap word by word.
+-------------------------------------------------------------------------
+create table t1 (a1 char(2), a2 char(2), a3 char(1), a4 char(10)) ENGINE=MyISAM;
+create table t2 (b1 char(2), b2 char(2), b3 char(1), b4 char(1)) ENGINE=MyISAM;
+insert into t1 values (NULL, '98', NULL, 'b');
+insert into t1 values (NULL, '99', NULL, 'c');
+insert into t2 values ('00',  'rr', 'y', NULL);
+insert into t2 values ('01',  'rr', 'y', NULL);
+insert into t2 values ('02',  NULL, 'x', 'y');
+insert into t2 values ('03',  'qq', 'y', 'x');
+insert into t2 values ('04',  'qq', 'm', 'p');
+insert into t2 values ('05',  'rr', 'y', NULL);
+insert into t2 values ('06',  NULL, 'x', 'y');
+insert into t2 values ('07',  'qq', 'y', 'x');
+insert into t2 values ('08',  'qq', 'm', 'q');
+insert into t2 values ('09',  'rr', 'y', NULL);
+insert into t2 values ('10',  NULL, 'x', 'y');
+insert into t2 values ('11',  'qq', 'y', 'x');
+insert into t2 values ('12',  'qq', 'm', 'k');
+insert into t2 values ('13',  'rr', 'y', NULL);
+insert into t2 values ('14',  NULL, 'x', 'y');
+insert into t2 values ('15',  'qq', 'y', 'x');
+insert into t2 values ('16',  'qq', 'm', 's');
+insert into t2 values ('17',  'rr', 'y', NULL);
+insert into t2 values ('18',  NULL, 'x', 'y');
+insert into t2 values ('19',  'qq', 'y', 'x');
+insert into t2 values ('20',  'qq', 'm', 't');
+insert into t2 values ('21',  'rr', 'y', NULL);
+insert into t2 values ('22',  NULL, 'x', 'y');
+insert into t2 values ('23',  'qq', 'y', 'x');
+insert into t2 values ('24',  'qq', 'm', 'u');
+insert into t2 values ('25',  'rr', 'y', NULL);
+insert into t2 values ('26',  NULL, 'x', 'y');
+insert into t2 values ('27',  'qq', 'y', 'x');
+insert into t2 values ('28',  'qq', 'm', 'y');
+insert into t2 values ('29',  'rr', 'y', NULL);
+insert into t2 values ('30',  NULL, 'x', 'z');
+insert into t2 values ('31',  'ss', 'h', NULL);
+insert into t2 values ('32',  'vv', 'i', NULL);
+the only partial matching row
+insert into t2 values ('33',  NULL, 'j', NULL);
+insert into t2 values ('34',  'qq', 'y', 'x');
+set @@optimizer_switch='partial_match_rowid_merge=on,partial_match_table_scan=off';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	35	Using where
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+a1	a2	a3	a4	in_res
+NULL	98	NULL	b	NULL
+NULL	99	NULL	c	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	35	Using where
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+a1	a2	a3	a4
+set @@optimizer_switch='partial_match_rowid_merge=off,partial_match_table_scan=on';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	35	Using where
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+a1	a2	a3	a4	in_res
+NULL	98	NULL	b	NULL
+NULL	99	NULL	c	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	35	Using where
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+a1	a2	a3	a4
+set @@optimizer_switch=@in_exists;
+EXPLAIN
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	35	Using where
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+a1	a2	a3	a4	in_res
+NULL	98	NULL	b	NULL
+NULL	99	NULL	c	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	35	Using where
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+a1	a2	a3	a4
+change the mathcing row to be the last one in the first bitmap word
+update t2 set b2 = 'zz' where b1 = 33;
+update t2 set b2 = NULL where b1 = 31;
+set @@optimizer_switch='partial_match_rowid_merge=on,partial_match_table_scan=off';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	35	Using where
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+a1	a2	a3	a4	in_res
+NULL	98	NULL	b	NULL
+NULL	99	NULL	c	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	35	Using where
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+a1	a2	a3	a4
+set @@optimizer_switch='partial_match_rowid_merge=off,partial_match_table_scan=on';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	35	Using where
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+a1	a2	a3	a4	in_res
+NULL	98	NULL	b	NULL
+NULL	99	NULL	c	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	35	Using where
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+a1	a2	a3	a4
+set @@optimizer_switch=@in_exists;
+EXPLAIN
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	35	Using where
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+a1	a2	a3	a4	in_res
+NULL	98	NULL	b	NULL
+NULL	99	NULL	c	NULL
+EXPLAIN
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	35	Using where
+SELECT * from t1 where (a1, a2, a3, a4) NOT IN (select * from t2);
+a1	a2	a3	a4
+drop table t1, t2;
+-------------------------------------------------------------------------
 All columns require partial matching (no non-null columns)
-
+-------------------------------------------------------------------------
 TODO
-
+-------------------------------------------------------------------------
 Both non-NULL columns and columns with NULLs
-
+-------------------------------------------------------------------------
 TODO
-
+-------------------------------------------------------------------------
 Covering NULL rows
-
+-------------------------------------------------------------------------
 create table t1 (a1 char(8), a2 char(8));
 create table t2 (b1 char(8), b2 char(8));
 insert into t1 values ('1 - 00', '2 - 00');
@@ -98,9 +615,9 @@ a1	a2	in_res
 1 - 00	2 - 00	NULL
 1 - 01	2 - 01	1
 drop table t1, t2;
-
+-------------------------------------------------------------------------
 Covering NULL columns
-
+-------------------------------------------------------------------------
 this case affects only the rowid-merge algorithm
 set @@optimizer_switch="partial_match_rowid_merge=on,partial_match_table_scan=off";
 create table t1 (a1 char(8) not null, a2 char(8), a3 char(8) not null);
@@ -149,9 +666,9 @@ a1	a2	a3	in_res
 1 - 00	2 - 00	3 - 00	NULL
 1 - 01	2 - 01	3 - 01	0
 drop table t1, t2;
-
+-------------------------------------------------------------------------
 Covering NULL row, and a NULL column
-
+-------------------------------------------------------------------------
 create table t1 (a1 char(8) not null, a2 char(8), a3 char(8));
 create table t2 (b1 char(8),          b2 char(8), b3 char(8));
 insert into t1 values ('1 - 00', '2 - 00', '3 - 00');
@@ -174,9 +691,9 @@ a1	a2	a3	in_res
 1 - 00	2 - 00	3 - 00	NULL
 1 - 01	2 - 01	3 - 01	NULL
 drop table t1, t2;
-
+-------------------------------------------------------------------------
 Covering NULL row, and covering NULL columns
-
+-------------------------------------------------------------------------
 create table t1 (a1 char(8) not null, a2 char(8), a3 char(8));
 create table t2 (b1 char(8),          b2 char(8), b3 char(8));
 insert into t1 values ('1 - 00', '2 - 00', '3 - 00');
@@ -198,6 +715,32 @@ a1	a2	a3	in_res
 1 - 00	2 - 00	3 - 00	NULL
 1 - 01	2 - 01	3 - 01	NULL
 drop table t1, t2;
+-------------------------------------------------------------------------
+Small buffer for the rowid_merge partial match algorithm that forces
+reverting to table scan partial match.
+-------------------------------------------------------------------------
+set @save_rowid_merge_buff_size = @@rowid_merge_buff_size;
+set @@rowid_merge_buff_size = 0;
+create table t1 (a1 char(2), a2 char(2), a3 char(1), a4 char(10));
+create table t2 (b1 char(2), b2 char(2), b3 char(1), b4 char(1));
+insert into t1 values (NULL, '98', NULL, 'b');
+insert into t1 values (NULL, '99', NULL, 'c');
+insert into t2 values ('00',  'rr', 'y', NULL);
+insert into t2 values ('01',  'rr', 'y', NULL);
+insert into t2 values ('02',  NULL, 'x', 'y');
+insert into t2 values ('03',  'qq', 'y', 'x');
+set @@optimizer_switch='partial_match_rowid_merge=on,partial_match_table_scan=off';
+EXPLAIN
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	
+2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	4	Using where
+SELECT t1.*, (a1, a2, a3, a4) IN (select * from t2) as in_res from t1;
+a1	a2	a3	a4	in_res
+NULL	98	NULL	b	0
+NULL	99	NULL	c	0
+drop table t1, t2;
+set @@rowid_merge_buff_size = @save_rowid_merge_buff_size;
 -------------------------------
 Part 2: Test cases for bugs.
 -------------------------------
@@ -372,4 +915,37 @@ SELECT * FROM t2 WHERE ( 3 , 1 ) NOT IN ( SELECT f1 , f2 FROM t1 );
 f3
 5
 drop table t1, t2;
+#
+# LP BUG#869036 Wrong result with in_to_exists=ON and NOT IN
+#
+create table outer_sq (f1 char(1), f2 char(1));
+insert into outer_sq values (NULL, 'c'), ('g', 'c');
+create table inner_sq (f3 char(1), f4 char(1));
+insert into inner_sq values(null, 'i'), ('v', null);
+All three strategies below must produce the same result.
+set @@optimizer_switch='in_to_exists=off,materialization=on,partial_match_rowid_merge=on,partial_match_table_scan=off';
+SELECT outer_sq.*, (f1, f2) IN (select * from inner_sq) from outer_sq;
+f1	f2	(f1, f2) IN (select * from inner_sq)
+NULL	c	NULL
+g	c	0
+SELECT * from outer_sq where (f1, f2) NOT IN (select * from inner_sq);
+f1	f2
+g	c
+set @@optimizer_switch='in_to_exists=off,materialization=on,partial_match_rowid_merge=off,partial_match_table_scan=on';
+SELECT outer_sq.*, (f1, f2) IN (select * from inner_sq) from outer_sq;
+f1	f2	(f1, f2) IN (select * from inner_sq)
+NULL	c	NULL
+g	c	0
+SELECT * from outer_sq where (f1, f2) NOT IN (select * from inner_sq);
+f1	f2
+g	c
+set @@optimizer_switch='in_to_exists=on,materialization=off';
+SELECT outer_sq.*, (f1, f2) IN (select * from inner_sq) from outer_sq;
+f1	f2	(f1, f2) IN (select * from inner_sq)
+NULL	c	NULL
+g	c	0
+SELECT * from outer_sq where (f1, f2) NOT IN (select * from inner_sq);
+f1	f2
+g	c
+drop table outer_sq, inner_sq;
 set @@optimizer_switch=@save_optimizer_switch;