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, 12 insertions, 12 deletions

diff --git a/mysql-test/main/type_varchar.result b/mysql-test/main/type_varchar.result
index 53f390e8b38..a23de349e4e 100644
--- a/mysql-test/main/type_varchar.result
+++ b/mysql-test/main/type_varchar.result
@@ -108,7 +108,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	v	v	257	const	3	Using where; Using index
 explain select * from t1 where v like 'S%' order by v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	v	v	257	NULL	2	Using where; Using index
+1	SIMPLE	t1	range	v	v	257	NULL	3	Using where; Using index
 alter table t1 change v v varchar(255);
 select * from t1 where v like 'This is a test' order by v;
 v
@@ -132,7 +132,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	v	v	258	const	3	Using where; Using index
 explain select * from t1 where v like 'S%' order by v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	v	v	258	NULL	2	Using where; Using index
+1	SIMPLE	t1	range	v	v	258	NULL	3	Using where; Using index
 alter table t1 change v v varchar(256);
 select * from t1 where v like 'This is a test' order by v;
 v
@@ -156,7 +156,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	v	v	259	const	3	Using where; Using index
 explain select * from t1 where v like 'S%' order by v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	v	v	259	NULL	2	Using where; Using index
+1	SIMPLE	t1	range	v	v	259	NULL	3	Using where; Using index
 alter table t1 change v v varchar(257);
 select * from t1 where v like 'This is a test' order by v;
 v
@@ -180,7 +180,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	v	v	260	const	3	Using where; Using index
 explain select * from t1 where v like 'S%' order by v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	v	v	260	NULL	2	Using where; Using index
+1	SIMPLE	t1	range	v	v	260	NULL	3	Using where; Using index
 alter table t1 change v v varchar(258);
 select * from t1 where v like 'This is a test' order by v;
 v
@@ -204,7 +204,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	v	v	261	const	3	Using where; Using index
 explain select * from t1 where v like 'S%' order by v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	v	v	261	NULL	2	Using where; Using index
+1	SIMPLE	t1	range	v	v	261	NULL	3	Using where; Using index
 alter table t1 change v v varchar(259);
 select * from t1 where v like 'This is a test' order by v;
 v
@@ -228,7 +228,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	v	v	262	const	3	Using where; Using index
 explain select * from t1 where v like 'S%' order by v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	v	v	262	NULL	2	Using where; Using index
+1	SIMPLE	t1	range	v	v	262	NULL	3	Using where; Using index
 alter table t1 change v v varchar(258);
 select * from t1 where v like 'This is a test' order by v;
 v
@@ -252,7 +252,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	v	v	261	const	3	Using where; Using index
 explain select * from t1 where v like 'S%' order by v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	v	v	261	NULL	2	Using where; Using index
+1	SIMPLE	t1	range	v	v	261	NULL	3	Using where; Using index
 alter table t1 change v v varchar(257);
 select * from t1 where v like 'This is a test' order by v;
 v
@@ -276,7 +276,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	v	v	260	const	3	Using where; Using index
 explain select * from t1 where v like 'S%' order by v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	v	v	260	NULL	2	Using where; Using index
+1	SIMPLE	t1	range	v	v	260	NULL	3	Using where; Using index
 alter table t1 change v v varchar(256);
 select * from t1 where v like 'This is a test' order by v;
 v
@@ -300,7 +300,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	v	v	259	const	3	Using where; Using index
 explain select * from t1 where v like 'S%' order by v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	v	v	259	NULL	2	Using where; Using index
+1	SIMPLE	t1	range	v	v	259	NULL	3	Using where; Using index
 alter table t1 change v v varchar(255);
 select * from t1 where v like 'This is a test' order by v;
 v
@@ -324,7 +324,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	v	v	258	const	3	Using where; Using index
 explain select * from t1 where v like 'S%' order by v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	v	v	258	NULL	2	Using where; Using index
+1	SIMPLE	t1	range	v	v	258	NULL	3	Using where; Using index
 alter table t1 change v v varchar(254);
 select * from t1 where v like 'This is a test' order by v;
 v
@@ -348,7 +348,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	v	v	257	const	3	Using where; Using index
 explain select * from t1 where v like 'S%' order by v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	v	v	257	NULL	2	Using where; Using index
+1	SIMPLE	t1	range	v	v	257	NULL	3	Using where; Using index
 alter table t1 change v v varchar(253);
 alter table t1 change v v varchar(254), drop key v;
 alter table t1 change v v varchar(300), add key (v(10));
@@ -374,7 +374,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ref	v	v	13	const	4	Using where
 explain select * from t1 where v like 'S%' order by v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	v	v	13	NULL	2	Using where; Using filesort
+1	SIMPLE	t1	range	v	v	13	NULL	3	Using where; Using filesort
 drop table t1;
 create table t1 (pkcol varchar(16), othercol varchar(16), primary key (pkcol));
 insert into t1 values ('test', 'something');