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, 15 insertions, 2 deletions

diff --git a/mysql-test/main/partition_innodb.result b/mysql-test/main/partition_innodb.result
index d27abc07984..46353c63ce3 100644
--- a/mysql-test/main/partition_innodb.result
+++ b/mysql-test/main/partition_innodb.result
@@ -1,6 +1,11 @@
 call mtr.add_suppression("Deadlock found when trying to get lock; try restarting transaction");
 set global default_storage_engine='innodb';
 set session default_storage_engine='innodb';
+set @innodb_stats_persistent_save= @@innodb_stats_persistent;
+set @innodb_stats_persistent_sample_pages_save=
+@@innodb_stats_persistent_sample_pages;
+set global innodb_stats_persistent= 1;
+set global innodb_stats_persistent_sample_pages=100;
 drop table if exists t1, t2;
 #
 # Bug#13694811: THE OPTIMIZER WRONGLY USES THE FIRST
@@ -24,12 +29,15 @@ INSERT INTO t1 VALUES (0, 'Mod Zero'), (1, 'One'), (2, 'Two'), (3, 'Three'),
 (20, '0'), (21, '1'), (22, '2'), (23, '3'),
 (4, '4'), (5, '5'), (6, '6'), (7, '7'), (8, '8'), (9, '9');
 INSERT INTO t1 SELECT a + 30, b FROM t1 WHERE a >= 0;
+INSERT INTO t1 SELECT a + 60, b FROM t1 WHERE a >= 0;
+INSERT INTO t1 SELECT a + 120, b FROM t1 WHERE a >= 0;
+INSERT INTO t1 SELECT a + 240, b FROM t1 WHERE a >= 0;
 ANALYZE TABLE t1;
 Table	Op	Msg_type	Msg_text
 test.t1	analyze	status	OK
 EXPLAIN SELECT b FROM t1 WHERE b between 'L' and 'N' AND a > -100;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	PRIMARY,b	b	67	NULL	34	Using where; Using index
+1	SIMPLE	t1	range	PRIMARY,b	b	67	NULL	90	Using where; Using index
 DROP TABLE t1;
 #
 # Bug#13007154: Crash in keys_to_use_for_scanning with ORDER BY
@@ -663,7 +671,7 @@ EXPLAIN SELECT * FROM t1 WHERE col1 = 1 AND col2 = 2
 AND col3 BETWEEN '2013-03-08 00:00:00' AND '2013-03-12 12:00:00'
 GROUP BY 1, 2, 3;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	PRIMARY,col1,col2	PRIMARY	5	NULL	#	Using where; Using filesort
+1	SIMPLE	t1	ref	PRIMARY,col1,col2	col1	8	const	#	Using where; Using filesort
 SELECT * FROM t1 USE INDEX () WHERE col1 = 1 AND col2 = 2
 AND col3 BETWEEN '2013-03-08 00:00:00' AND '2013-03-12 12:00:00'
 GROUP BY 1, 2, 3;
@@ -696,9 +704,11 @@ insert into t1 select 10+A.a + 10*B.a + 100*C.a + 1000*D.a,
 10+A.a + 10*B.a + 100*C.a  + 1000*D.a, 
 2000 + A.a + 10*B.a + 100*C.a + 1000*D.a
 from t2 A, t2 B, t2 C ,t2 D;
+set statement optimizer_switch='rowid_filter=off' for
 explain select * from t1 where a=1 and b=2 and  pk between 1 and 999999 ;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index_merge	PRIMARY,a,b	b,a	4,4	NULL	#	Using intersect(b,a); Using where; Using index
+set statement optimizer_switch='rowid_filter=off' for
 create temporary table t3 as
 select * from t1 where a=1 and b=2 and  pk between 1 and 999 ;
 select count(*) from t3;
@@ -925,3 +935,6 @@ test_jfg	test_jfg11
 test_jfg	test_jfg12#P#p1000
 test_jfg	test_jfg12#P#pmax
 DROP DATABASE test_jfg;
+set global innodb_stats_persistent= @innodb_stats_persistent_save;
+set global innodb_stats_persistent_sample_pages=
+@innodb_stats_persistent_sample_pages_save;