MDEV-16188 Use in-memory PK filters built from range index scans

This patch contains a full implementation of the optimization
that allows to use in-memory rowid / primary filters built for range  
conditions over indexes. In many cases usage of such filters reduce  
the number of disk seeks spent for fetching table rows.

In this implementation the choice of what possible filter to be applied  
(if any) is made purely on cost-based considerations.

This implementation re-achitectured the partial implementation of
the feature pushed by Galina Shalygina in the commit
8d5a11122c32f4d9eb87536886c6e893377bdd07.

Besides this patch contains a better implementation of the generic  
handler function handler::multi_range_read_info_const() that
takes into account gaps between ranges when calculating the cost of
range index scans. It also contains some corrections of the
implementation of the handler function records_in_range() for MyISAM.

This patch supports the feature for InnoDB and MyISAM.

1 files changed, 68 insertions, 62 deletions

diff --git a/mysql-test/main/index_merge_myisam.result b/mysql-test/main/index_merge_myisam.result
index 725a888c914..8e83bdf6bbb 100644
--- a/mysql-test/main/index_merge_myisam.result
+++ b/mysql-test/main/index_merge_myisam.result
@@ -1,4 +1,5 @@
 set @optimizer_switch_save= @@optimizer_switch;
+set optimizer_switch='rowid_filter=off';
 set optimizer_switch='index_merge_sort_intersection=off';
 #---------------- Index merge test 1 -------------------------------------------
 SET SESSION STORAGE_ENGINE = MyISAM;
@@ -19,27 +20,26 @@ update t0 set key2=key1,key3=key1,key4=key1,key5=key1,key6=key1,key7=key1,key8=1
 analyze table t0;
 Table	Op	Msg_type	Msg_text
 test.t0	analyze	status	OK
-explain select * from t0 where key1 < 3 or key1 > 1020;
+explain select * from t0 where key1 < 3 or key1 > 920 and key1 < 924;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	range	i1	i1	4	NULL	78	Using index condition; Using where
+1	SIMPLE	t0	range	i1	i1	4	NULL	5	Using index condition; Using where
 explain
-select * from t0 where key1 < 3 or key2 > 1020;
+select * from t0 where key1 < 3 or key2 > 920 and key2 < 924;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2	i1,i2	4,4	NULL	45	Using sort_union(i1,i2); Using where
-select * from t0 where key1 < 3 or key2 > 1020;
+1	SIMPLE	t0	index_merge	i1,i2	i1,i2	4,4	NULL	5	Using sort_union(i1,i2); Using where
+select * from t0 where key1 < 3 or key2 > 920 and key2 < 924;
 key1	key2	key3	key4	key5	key6	key7	key8
 1	1	1	1	1	1	1	1023
 2	2	2	2	2	2	2	1022
-1021	1021	1021	1021	1021	1021	1021	3
-1022	1022	1022	1022	1022	1022	1022	2
-1023	1023	1023	1023	1023	1023	1023	1
-1024	1024	1024	1024	1024	1024	1024	0
+921	921	921	921	921	921	921	103
+922	922	922	922	922	922	922	102
+923	923	923	923	923	923	923	101
 select * from t0 where key1=1022;
 key1	key2	key3	key4	key5	key6	key7	key8
 1022	1022	1022	1022	1022	1022	1022	2
 explain select * from t0 where key1 < 3 or key2 <4;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2	i1,i2	4,4	NULL	7	Using sort_union(i1,i2); Using where
+1	SIMPLE	t0	index_merge	i1,i2	i1,i2	4,4	NULL	5	Using sort_union(i1,i2); Using where
 explain
 select * from t0 where (key1 > 30 and key1<35) or (key2 >32 and key2 < 40);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
@@ -63,7 +63,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t0	ref	i1,i2,i3	i3	4	const	1	Using where
 explain select * from t0 use index (i1,i2) where (key1 < 3 or key2 <4) and key3 = 50;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2	i1,i2	4,4	NULL	7	Using sort_union(i1,i2); Using where
+1	SIMPLE	t0	index_merge	i1,i2	i1,i2	4,4	NULL	5	Using sort_union(i1,i2); Using where
 explain select * from t0 where (key1 > 1 or key2  > 2);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t0	ALL	i1,i2	NULL	NULL	NULL	1024	Using where
@@ -74,7 +74,7 @@ explain
 select * from t0 where key1<3 or key2<3 or (key1>5 and key1<8) or
 (key1>10 and key1<12) or (key2>100 and key2<110);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2	i1,i2	4,4	NULL	17	Using sort_union(i1,i2); Using where
+1	SIMPLE	t0	index_merge	i1,i2	i1,i2	4,4	NULL	15	Using sort_union(i1,i2); Using where
 explain select * from t0 where key2 = 45 or key1 <=> null;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t0	range	i1,i2	i2	4	NULL	1	Using index condition
@@ -93,19 +93,19 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 explain select key1 from t0 where (key1 <=> null) or (key2 < 5) or
 (key3=10) or (key4 <=> null);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2,i3,i4	i2,i3	4,4	NULL	6	Using sort_union(i2,i3); Using where
+1	SIMPLE	t0	index_merge	i1,i2,i3,i4	i2,i3	4,4	NULL	5	Using sort_union(i2,i3); Using where
 explain select key1 from t0 where (key1 <=> null) or (key1 < 5) or
 (key3=10) or (key4 <=> null);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i3,i4	i1,i3	4,4	NULL	6	Using sort_union(i1,i3); Using where
+1	SIMPLE	t0	index_merge	i1,i3,i4	i1,i3	4,4	NULL	5	Using sort_union(i1,i3); Using where
 explain select * from t0 where
 (key1 < 3 or key2 < 3) and (key3 < 4 or key4 < 4) and (key5 < 5 or key6 < 5);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2,i3,i4,i5,i6	i1,i2	4,4	NULL	6	Using sort_union(i1,i2); Using where
+1	SIMPLE	t0	index_merge	i1,i2,i3,i4,i5,i6	i1,i2	4,4	NULL	4	Using sort_union(i1,i2); Using where
 explain
 select * from t0 where (key1 < 3 or key2 < 6) and (key1 < 7 or key3 < 4);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2,i3	i1,i2	4,4	NULL	9	Using sort_union(i1,i2); Using where
+1	SIMPLE	t0	index_merge	i1,i2,i3	i1,i2	4,4	NULL	7	Using sort_union(i1,i2); Using where
 select * from t0 where (key1 < 3 or key2 < 6) and (key1 < 7 or key3 < 4);
 key1	key2	key3	key4	key5	key6	key7	key8
 1	1	1	1	1	1	1	1023
@@ -116,15 +116,15 @@ key1	key2	key3	key4	key5	key6	key7	key8
 explain select * from t0 where
 (key1 < 3 or key2 < 3) and (key3 < 4 or key4 < 4) and (key5 < 2 or key6 < 2);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2,i3,i4,i5,i6	i1,i2	4,4	NULL	6	Using sort_union(i1,i2); Using where
+1	SIMPLE	t0	index_merge	i1,i2,i3,i4,i5,i6	i5,i6	4,4	NULL	2	Using sort_union(i5,i6); Using where
 explain select * from t0 where
 (key1 < 3 or key2 < 3) and (key3 < 100);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2,i3	i1,i2	4,4	NULL	6	Using sort_union(i1,i2); Using where
+1	SIMPLE	t0	index_merge	i1,i2,i3	i1,i2	4,4	NULL	4	Using sort_union(i1,i2); Using where
 explain select * from t0 where
 (key1 < 3 or key2 < 3) and (key3 < 1000);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2,i3	i1,i2	4,4	NULL	6	Using sort_union(i1,i2); Using where
+1	SIMPLE	t0	index_merge	i1,i2,i3	i1,i2	4,4	NULL	4	Using sort_union(i1,i2); Using where
 explain select * from t0 where
 ((key1 < 4 or key2 < 4) and (key2 <5 or key3 < 4))
 or
@@ -136,7 +136,7 @@ explain select * from t0 where
 or
 key1 < 7;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2,i3	i1,i2	4,4	NULL	10	Using sort_union(i1,i2); Using where
+1	SIMPLE	t0	index_merge	i1,i2,i3	i1,i2	4,4	NULL	8	Using sort_union(i1,i2); Using where
 select * from t0 where
 ((key1 < 4 or key2 < 4) and (key2 <5 or key3 < 4))
 or
@@ -148,30 +148,36 @@ key1	key2	key3	key4	key5	key6	key7	key8
 4	4	4	4	4	4	4	1020
 5	5	5	5	5	5	5	1019
 6	6	6	6	6	6	6	1018
+select count(*) from t0 where
+((key1 < 4 or key2 < 4) and (key3 <5 or key5 < 4))
+or
+((key5 < 5 or key6 < 6) and (key7 <7 or key8 < 4));
+count(*)
+5
 explain select * from t0 where
 ((key1 < 4 or key2 < 4) and (key3 <5 or key5 < 4))
 or
 ((key5 < 5 or key6 < 6) and (key7 <7 or key8 < 4));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2,i3,i5,i6,i7,i8	i1,i2,i5,i6	4,4,4,4	NULL	19	Using sort_union(i1,i2,i5,i6); Using where
+1	SIMPLE	t0	index_merge	i1,i2,i3,i5,i6,i7,i8	i1,i2,i5,i6	4,4,4,4	NULL	15	Using sort_union(i1,i2,i5,i6); Using where
 explain select * from t0 where
 ((key3 <5 or key5 < 4) and (key1 < 4 or key2 < 4))
 or
 ((key7 <7 or key8 < 4) and (key5 < 5 or key6 < 6));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2,i3,i5,i6,i7,i8	i3,i5,i7,i8	4,4,4,4	NULL	20	Using sort_union(i3,i5,i7,i8); Using where
+1	SIMPLE	t0	index_merge	i1,i2,i3,i5,i6,i7,i8	i3,i5,i7,i8	4,4,4,4	NULL	16	Using sort_union(i3,i5,i7,i8); Using where
 explain select * from t0 where
 ((key3 <5 or key5 < 4) and (key1 < 4 or key2 < 4))
 or
 ((key3 <7 or key5 < 2) and (key5 < 5 or key6 < 6));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2,i3,i5,i6	i3,i5	4,4	NULL	11	Using sort_union(i3,i5); Using where
+1	SIMPLE	t0	index_merge	i1,i2,i3,i5,i6	i3,i5	4,4	NULL	9	Using sort_union(i3,i5); Using where
 explain select * from t0 where
 ((key3 <5 or key5 < 4) and (key1 < 4 or key2 < 4))
 or
 (((key3 <7 and key7 < 6) or key5 < 2) and (key5 < 5 or key6 < 6));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2,i3,i5,i6,i7	i3,i5	4,4	NULL	11	Using sort_union(i3,i5); Using where
+1	SIMPLE	t0	index_merge	i1,i2,i3,i5,i6,i7	i3,i5	4,4	NULL	9	Using sort_union(i3,i5); Using where
 explain select * from t0 where
 ((key3 <5 or key5 < 4) and (key1 < 4 or key2 < 4))
 or
@@ -197,7 +203,7 @@ key1	key2	key3	key4	key5	key6	key7	key8
 explain
 select * from t0 where key1 < 5 or key8 < 4 order by key1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i8	i1,i8	4,4	NULL	9	Using sort_union(i1,i8); Using where; Using filesort
+1	SIMPLE	t0	index_merge	i1,i8	i1,i8	4,4	NULL	7	Using sort_union(i1,i8); Using where; Using filesort
 create table t2 like t0;
 insert into t2 select * from t0;
 alter table t2 add index i1_3(key1, key3);
@@ -213,7 +219,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	index	i1_3,i2_3	i321	12	NULL	1024	Using where; Using index
 explain select key7 from t2 where key1 <100 or key2 < 100;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	index_merge	i1_3,i2_3	i1_3,i2_3	4,4	NULL	188	Using sort_union(i1_3,i2_3); Using where
+1	SIMPLE	t2	index_merge	i1_3,i2_3	i1_3,i2_3	4,4	NULL	186	Using sort_union(i1_3,i2_3); Using where
 create table t4 (
 key1a int not null,
 key1b int not null,
@@ -238,10 +244,10 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t4	index_merge	i1a,i1b	i1a,i1b	4,4	NULL	2	Using sort_union(i1a,i1b); Using where
 explain select * from t4 where key2 = 1 and (key2_1 = 1 or key3 = 5);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t4	ref	i2_1,i2_2	i2_1	4	const	10	Using where
+1	SIMPLE	t4	ref	i2_1,i2_2	i2_1	4	const	9	Using where
 explain select * from t4 where key2 = 1 and (key2_1 = 1 or key2_2 = 5);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t4	ref	i2_1,i2_2	i2_1	4	const	10	Using where
+1	SIMPLE	t4	ref	i2_1,i2_2	i2_1	4	const	9	Using where
 explain select * from t4 where key2_1 = 1 or key2_2 = 5;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	1024	Using where
@@ -282,13 +288,13 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 explain select * from t0,t1 where t0.key1 < 3 and
 (t1.key1 = t0.key1 or t1.key8 = t0.key1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	range	i1	i1	4	NULL	3	Using index condition
+1	SIMPLE	t0	range	i1	i1	4	NULL	2	Using index condition
 1	SIMPLE	t1	ALL	i1,i8	NULL	NULL	NULL	1024	Range checked for each record (index map: 0x81)
 explain select * from t1 where key1=3 or key2=4
 union select * from t1 where key1<4 or key3=5;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	index_merge	i1,i2	i1,i2	4,4	NULL	2	Using union(i1,i2); Using where
-2	UNION	t1	index_merge	i1,i3	i1,i3	4,4	NULL	5	Using sort_union(i1,i3); Using where
+2	UNION	t1	index_merge	i1,i3	i1,i3	4,4	NULL	4	Using sort_union(i1,i3); Using where
 NULL	UNION RESULT	<union1,2>	ALL	NULL	NULL	NULL	NULL	NULL	
 set @tmp_optimizer_switch=@@optimizer_switch;
 set optimizer_switch='derived_merge=off,derived_with_keys=off';
@@ -329,7 +335,7 @@ key1	key2	key3	key4	key5	key6	key7	key8	key9	keyA	keyB	keyC
 1016	1016	1016	1016	1016	1016	1016	8	1016	1016	1016	1016
 explain select * from t0 where key1 < 3 or key2 < 4;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t0	index_merge	i1,i2	i1,i2	4,4	NULL	7	Using sort_union(i1,i2); Using where
+1	SIMPLE	t0	index_merge	i1,i2	i1,i2	4,4	NULL	5	Using sort_union(i1,i2); Using where
 select * from t0 where key1 < 3 or key2 < 4;
 key1	key2	key3	key4	key5	key6	key7	key8
 1	1	1	1	1	1	1	1023
@@ -357,8 +363,8 @@ from t0 as A force index(i1,i2), t0 as B force index (i1,i2)
 where (A.key1 < 500000 or A.key2 < 3)
 and   (B.key1 < 500000 or B.key2 < 3);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	A	index_merge	i1,i2	i1,i2	4,4	NULL	1013	Using sort_union(i1,i2); Using where
-1	SIMPLE	B	index_merge	i1,i2	i1,i2	4,4	NULL	1013	Using sort_union(i1,i2); Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	A	index_merge	i1,i2	i1,i2	4,4	NULL	1010	Using sort_union(i1,i2); Using where
+1	SIMPLE	B	index_merge	i1,i2	i1,i2	4,4	NULL	1010	Using sort_union(i1,i2); Using where; Using join buffer (flat, BNL join)
 select max(A.key1 + B.key1 + A.key2 + B.key2 + A.key3 + B.key3 + A.key4 + B.key4 + A.key5 + B.key5)
 from t0 as A force index(i1,i2), t0 as B force index (i1,i2)
 where (A.key1 < 500000 or A.key2 < 3)
@@ -371,8 +377,8 @@ from t0 as A force index(i1,i2), t0 as B force index (i1,i2)
 where (A.key1 = 1 or A.key2 = 1)
 and   (B.key1 = 1 or B.key2 = 1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	A	index_merge	i1,i2	i1,i2	4,4	NULL	1020	Using union(i1,i2); Using where
-1	SIMPLE	B	index_merge	i1,i2	i1,i2	4,4	NULL	1020	Using union(i1,i2); Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	A	index_merge	i1,i2	i1,i2	4,4	NULL	1021	Using union(i1,i2); Using where
+1	SIMPLE	B	index_merge	i1,i2	i1,i2	4,4	NULL	1021	Using union(i1,i2); Using where; Using join buffer (flat, BNL join)
 select max(A.key1 + B.key1 + A.key2 + B.key2 + A.key3 + B.key3 + A.key4 + B.key4 + A.key5 + B.key5)
 from t0 as A force index(i1,i2), t0 as B force index (i1,i2)
 where (A.key1 = 1 or A.key2 = 1)
@@ -517,7 +523,7 @@ a	filler	b
 must use union, not sort-union:
 explain select * from t2 where a=4 or b=4;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	index_merge	a,b	a,b	5,5	NULL	#	Using union(a,b); Using where
+1	SIMPLE	t2	ALL	a,b	NULL	NULL	NULL	#	Using where
 select * from t2 where a=4 or b=4;
 a	filler	b
 4	4	0
@@ -705,19 +711,19 @@ select key1,key2,filler1 from t1 where key2=100 and key2=200;
 key1	key2	filler1
 explain select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key1,key2,key3,key4	5,5,5,5	NULL	152	Using union(intersect(key1,key2),intersect(key3,key4)); Using where
+1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key1,key2,key3,key4	5,5,5,5	NULL	154	Using union(intersect(key1,key2),intersect(key3,key4)); Using where
 select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
 key1	key2	key3	key4	filler1
 -1	-1	100	100	key4-key3
 delete from t1 where key3=100 and key4=100;
 explain select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key1,key2,key3,key4	5,5,5,5	NULL	152	Using union(intersect(key1,key2),intersect(key3,key4)); Using where
+1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key1,key2,key3,key4	5,5,5,5	NULL	154	Using union(intersect(key1,key2),intersect(key3,key4)); Using where
 select key1,key2,key3,key4,filler1 from t1 where key1=100 and key2=100 or key3=100 and key4=100;
 key1	key2	key3	key4	filler1
 explain select key1,key2 from t1 where key1=100 and key2=100;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index_merge	key1,key2	key1,key2	5,5	NULL	76	Using intersect(key1,key2); Using where; Using index
+1	SIMPLE	t1	index_merge	key1,key2	key1,key2	5,5	NULL	77	Using intersect(key1,key2); Using where; Using index
 select key1,key2 from t1 where key1=100 and key2=100;
 key1	key2
 insert into t1 (key1, key2, key3, key4, filler1) values (100, 100, 200, 200,'key1-key2-key3-key4-1');
@@ -725,7 +731,7 @@ insert into t1 (key1, key2, key3, key4, filler1) values (100, 100, 200, 200,'key
 insert into t1 (key1, key2, key3, key4, filler1) values (100, 100, 200, 200,'key1-key2-key3-key4-3');
 explain select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key3,key1,key2,key4	5,5,5,5	NULL	136	Using union(key3,intersect(key1,key2),key4); Using where
+1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key3,key1,key2,key4	5,5,5,5	NULL	137	Using union(key3,intersect(key1,key2),key4); Using where
 select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
 key1	key2	key3	key4	filler1
 100	100	200	200	key1-key2-key3-key4-3
@@ -734,7 +740,7 @@ key1	key2	key3	key4	filler1
 insert into t1 (key1, key2, key3, key4, filler1) values (-1, -1, -1, 200,'key4');
 explain select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key3,key1,key2,key4	5,5,5,5	NULL	146	Using union(key3,intersect(key1,key2),key4); Using where
+1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key3,key1,key2,key4	5,5,5,5	NULL	148	Using union(key3,intersect(key1,key2),key4); Using where
 select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
 key1	key2	key3	key4	filler1
 100	100	200	200	key1-key2-key3-key4-3
@@ -744,7 +750,7 @@ key1	key2	key3	key4	filler1
 insert into t1 (key1, key2, key3, key4, filler1) values (-1, -1, 200, -1,'key3');
 explain select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key3,key1,key2,key4	5,5,5,5	NULL	156	Using union(key3,intersect(key1,key2),key4); Using where
+1	SIMPLE	t1	index_merge	key1,key2,key3,key4	key3,key1,key2,key4	5,5,5,5	NULL	159	Using union(key3,intersect(key1,key2),key4); Using where
 select key1,key2,key3,key4,filler1 from t1 where key3=200 or (key1=100 and key2=100) or key4=200;
 key1	key2	key3	key4	filler1
 100	100	200	200	key1-key2-key3-key4-3
@@ -760,7 +766,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	sta_swt12a,sta_swt1a,sta_swt2a,sta_swt21a,st_a,stb_swt1a_2b,stb_swt1b,st_b	st_a,st_b	4,4	NULL	3515	Using intersect(st_a,st_b); Using where; Using index
 explain select st_a from t1 ignore index (st_a) where st_a=1 and st_b=1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ref	sta_swt12a,sta_swt1a,sta_swt2a,sta_swt21a,stb_swt1a_2b,stb_swt1b,st_b	st_b	4	const	15093	Using where
+1	SIMPLE	t1	ref	sta_swt12a,sta_swt1a,sta_swt2a,sta_swt21a,stb_swt1a_2b,stb_swt1b,st_b	st_b	4	const	15094	Using where
 explain select * from t1 where st_a=1 and swt1a=1 and swt2a=1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	sta_swt12a,sta_swt1a,sta_swt2a,sta_swt21a,st_a	sta_swt21a	12	const,const,const	971	
@@ -850,7 +856,7 @@ INDEX i2(key2)
 );
 explain select * from t1 where key1 < 5 or key2 > 197;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index_merge	i1,i2	i1,i2	4,4	NULL	10	Using sort_union(i1,i2); Using where
+1	SIMPLE	t1	index_merge	i1,i2	i1,i2	4,4	NULL	8	Using sort_union(i1,i2); Using where
 select * from t1 where key1 < 5 or key2 > 197;
 key1	key2
 0	200
@@ -860,7 +866,7 @@ key1	key2
 4	196
 explain select * from t1 where key1 < 3 or key2 > 195;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index_merge	i1,i2	i1,i2	4,4	NULL	10	Using sort_union(i1,i2); Using where
+1	SIMPLE	t1	index_merge	i1,i2	i1,i2	4,4	NULL	8	Using sort_union(i1,i2); Using where
 select * from t1 where key1 < 3 or key2 > 195;
 key1	key2
 0	200
@@ -876,7 +882,7 @@ update t1 set str1='aaa', str2='bbb', str3=concat(key2, '-', key1 div 2, '_' ,if
 alter table t1 add primary key (str1, zeroval, str2, str3);
 explain select * from t1 where key1 < 5 or key2 > 197;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index_merge	i1,i2	i1,i2	4,4	NULL	10	Using sort_union(i1,i2); Using where
+1	SIMPLE	t1	index_merge	i1,i2	i1,i2	4,4	NULL	8	Using sort_union(i1,i2); Using where
 select * from t1 where key1 < 5 or key2 > 197;
 key1	key2	str1	zeroval	str2	str3
 0	200	aaa	0	bbb	200-0_a
@@ -886,7 +892,7 @@ key1	key2	str1	zeroval	str2	str3
 4	196	aaa	0	bbb	196-2_a
 explain select * from t1 where key1 < 3 or key2 > 195;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index_merge	i1,i2	i1,i2	4,4	NULL	10	Using sort_union(i1,i2); Using where
+1	SIMPLE	t1	index_merge	i1,i2	i1,i2	4,4	NULL	8	Using sort_union(i1,i2); Using where
 select * from t1 where key1 < 3 or key2 > 195;
 key1	key2	str1	zeroval	str2	str3
 0	200	aaa	0	bbb	200-0_a
@@ -1444,7 +1450,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	key1,pktail4bad	pktail4bad	4	const	82	Using where
 explain select * from t1 where pktail5bad=1 and key1=10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ref	key1,pktail5bad	pktail5bad	4	const	70	Using where
+1	SIMPLE	t1	ref	key1,pktail5bad	pktail5bad	4	const	69	Using where
 explain select pk1,pk2,key1,key2 from t1 where key1 = 10 and key2=10 limit 10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	key1,key2	key1,key2	4,4	NULL	1	Using intersect(key1,key2); Using where
@@ -1498,7 +1504,7 @@ EXPLAIN SELECT t1.f1 FROM t1
 WHERE (SELECT COUNT(*) FROM t2 WHERE t2.f3 = 'h' AND t2.f2 = t1.f1) = 0 AND t1.f1 = 2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	system	PRIMARY	NULL	NULL	NULL	1	
-2	SUBQUERY	t2	ref	f2,f3	f2	5	const	1	Using where
+2	SUBQUERY	t2	ref	f2,f3	f2	5	const	2	Using where
 DROP TABLE t1,t2;
 create table t0 (a int);
 insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
@@ -1515,12 +1521,12 @@ explain select * from t1 where a=1 or b=1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	a,b	a,b	5,5	NULL	2	Using union(a,b); Using where
 This should use ALL:
-set optimizer_switch='default,index_merge=off';
+set optimizer_switch='default,index_merge=off,rowid_filter=off';
 explain select * from t1 where a=1 or b=1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ALL	a,b	NULL	NULL	NULL	1000	Using where
 This should use sort-union:
-set optimizer_switch='default,index_merge_union=off';
+set optimizer_switch='default,index_merge_union=off,rowid_filter=off';
 explain select * from t1 where a=1 or b=1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	a,b	a,b	5,5	NULL	2	Using sort_union(a,b); Using where
@@ -1530,17 +1536,17 @@ explain select * from t1 where a<1 or b <1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	a,b	a,b	5,5	NULL	38	Using sort_union(a,b); Using where
 This should use ALL:
-set optimizer_switch='default,index_merge_sort_union=off';
+set optimizer_switch='default,index_merge_sort_union=off,rowid_filter=off';
 explain select * from t1 where a<1 or b <1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ALL	a,b	NULL	NULL	NULL	1000	Using where
 This should use ALL:
-set optimizer_switch='default,index_merge=off';
+set optimizer_switch='default,index_merge=off,rowid_filter=off';
 explain select * from t1 where a<1 or b <1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ALL	a,b	NULL	NULL	NULL	1000	Using where
 This will use sort-union:
-set optimizer_switch='default,index_merge_union=off';
+set optimizer_switch='default,index_merge_union=off,rowid_filter=off';
 explain select * from t1 where a<1 or b <1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	a,b	a,b	5,5	NULL	38	Using sort_union(a,b); Using where
@@ -1552,7 +1558,7 @@ explain select * from t1 where (a=3 or b in (1,2)) and (c=3 or d=4);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	a,b,c,d	a,b	5,5	NULL	3	Using sort_union(a,b); Using where
 And if we disable sort_union, union:
-set optimizer_switch='default,index_merge_sort_union=off';
+set optimizer_switch='default,index_merge_sort_union=off,rowid_filter=off';
 explain select * from t1 where (a=3 or b in (1,2)) and (c=3 or d=4);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	a,b,c,d	c,d	5,5	NULL	100	Using union(c,d); Using where
@@ -1571,22 +1577,22 @@ explain select * from t1 where a=10 and b=10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	a,b	a,b	5,5	NULL	1	Using intersect(a,b); Using where
 No intersect when index_merge is disabled:
-set optimizer_switch='default,index_merge=off';
+set optimizer_switch='default,index_merge=off,rowid_filter=off';
 explain select * from t1 where a=10 and b=10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	a,b	a	5	const	49	Using where
 No intersect if it is disabled:
-set optimizer_switch='default,index_merge_sort_intersection=off,index_merge_intersection=off';
+set optimizer_switch='default,index_merge_sort_intersection=off,index_merge_intersection=off,rowid_filter=off';
 explain select * from t1 where a=10 and b=10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	a,b	a	5	const	49	Using where
 Do intersect when union was disabled
-set optimizer_switch='default,index_merge_union=off';
+set optimizer_switch='default,index_merge_union=off,rowid_filter=off';
 explain select * from t1 where a=10 and b=10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	a,b	a,b	5,5	NULL	1	Using intersect(a,b); Using where
 Do intersect when sort_union was disabled
-set optimizer_switch='default,index_merge_sort_union=off';
+set optimizer_switch='default,index_merge_sort_union=off,rowid_filter=off';
 explain select * from t1 where a=10 and b=10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	a,b	a,b	5,5	NULL	1	Using intersect(a,b); Using where
@@ -1596,13 +1602,13 @@ explain select * from t1 where a=10 and b=10 or c=10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	a,b,c	a,b,c	5,5,5	NULL	6	Using union(intersect(a,b),c); Using where
 Should be only union left:
-set optimizer_switch='default,index_merge_intersection=off';
+set optimizer_switch='default,index_merge_intersection=off,rowid_filter=off';
 explain select * from t1 where a=10 and b=10 or c=10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	a,b,c	a,c	5,5	NULL	54	Using union(a,c); Using where
 This will switch to sort-union (intersection will be gone, too,
 that's a known limitation:
-set optimizer_switch='default,index_merge_union=off';
+set optimizer_switch='default,index_merge_union=off,rowid_filter=off';
 explain select * from t1 where a=10 and b=10 or c=10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	a,b,c	a,c	5,5	NULL	54	Using sort_union(a,c); Using where
@@ -1647,7 +1653,7 @@ SELECT * FROM t1 FORCE INDEX ( PRIMARY, population_rate, area_rate, code )
 WHERE pk = 1 OR population_rate = 1 OR ( area_rate IN ( 1,2 ) OR area_rate IS NULL )
 AND (population_rate = 25 OR area_rate BETWEEN 2 AND 25 OR code BETWEEN 'MA' AND 'TX');
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index_merge	PRIMARY,code,population_rate,area_rate	PRIMARY,population_rate,area_rate	4,5,5	NULL	2	Using sort_union(PRIMARY,population_rate,area_rate); Using where
+1	SIMPLE	t1	index_merge	PRIMARY,code,population_rate,area_rate	PRIMARY,population_rate,area_rate,code	4,5,5,3	NULL	2	Using sort_union(PRIMARY,population_rate,area_rate,code); Using where
 SELECT * FROM t1 FORCE INDEX ( PRIMARY, population_rate, area_rate, code ) 
 WHERE pk = 1 OR population_rate = 1 OR ( area_rate IN ( 1,2 ) OR area_rate IS NULL )
 AND (population_rate = 25 OR area_rate BETWEEN 2 AND 25 OR code BETWEEN 'MA' AND 'TX');