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

diff --git a/mysql-test/main/join_cache.result b/mysql-test/main/join_cache.result
index fde6e0fec6b..d079cc8ba3a 100644
--- a/mysql-test/main/join_cache.result
+++ b/mysql-test/main/join_cache.result
@@ -6,6 +6,11 @@ set optimizer_switch='semijoin=on,firstmatch=on,loosescan=on';
 set @@optimizer_switch='semijoin_with_cache=on';
 set @@optimizer_switch='outer_join_with_cache=on';
 set optimizer_switch='mrr=on,mrr_sort_keys=on,index_condition_pushdown=on';
+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;
 set @local_join_cache_test_optimizer_switch_default=@@optimizer_switch;
 set names utf8;
 CREATE DATABASE world;
@@ -402,7 +407,7 @@ ON City.Country=Country.Code AND City.Population > 5000000
 WHERE Country.Name LIKE 'C%' AND Country.Population > 10000000;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	Country	ALL	NULL	NULL	NULL	NULL	239	Using where
-1	SIMPLE	City	hash_range	City_Population	#hash#$hj:City_Population	3:4	world.Country.Code	25	Using where; Rowid-ordered scan; Using join buffer (flat, BNLH join)
+1	SIMPLE	City	hash_range	City_Population	#hash#$hj:City_Population	3:4	world.Country.Code	24	Using where; Rowid-ordered scan; Using join buffer (flat, BNLH join)
 SELECT Country.Name, Country.Population, City.Name, City.Population 
 FROM Country LEFT JOIN City
 ON City.Country=Country.Code AND City.Population > 5000000
@@ -3037,13 +3042,13 @@ t6.formattypeid IN (2) AND (t3.formatid IN (31, 8, 76)) AND
 t1.metaid = t2.metaid AND t1.affiliateid = '2';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t6	system	PRIMARY	NULL	NULL	NULL	1	
-1	SIMPLE	t1	ref	t1_affiliateid,t1_metaid	t1_affiliateid	4	const	1	
-1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	4	test.t1.metaid	1	Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
-1	SIMPLE	t7	ref	PRIMARY	PRIMARY	4	test.t1.metaid	1	Using index
-1	SIMPLE	t8	eq_ref	PRIMARY	PRIMARY	4	test.t7.artistid	1	Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
+1	SIMPLE	t5	ref	PRIMARY,t5_formattypeid	t5_formattypeid	4	const	1	
+1	SIMPLE	t1	ref	t1_affiliateid,t1_metaid	t1_affiliateid	4	const	2	Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
+1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	4	test.t1.metaid	1	Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
 1	SIMPLE	t3	ref	t3_metaid,t3_formatid,t3_metaidformatid	t3_metaidformatid	4	test.t1.metaid	1	Using index condition; Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
 1	SIMPLE	t4	eq_ref	PRIMARY,t4_formatclassid,t4_formats_idx	PRIMARY	4	test.t3.formatid	1	Using where; Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
-1	SIMPLE	t5	eq_ref	PRIMARY,t5_formattypeid	PRIMARY	4	test.t4.formatclassid	1	Using where; Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
+1	SIMPLE	t7	ref	PRIMARY	PRIMARY	4	test.t1.metaid	1	Using index
+1	SIMPLE	t8	eq_ref	PRIMARY	PRIMARY	4	test.t7.artistid	1	Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
 1	SIMPLE	t9	index	PRIMARY,t9_subgenreid,t9_metaid	PRIMARY	8	NULL	2	Using where; Using index; Using join buffer (incremental, BNL join)
 1	SIMPLE	t10	eq_ref	PRIMARY,t10_genreid	PRIMARY	4	test.t9.subgenreid	1	Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
 1	SIMPLE	t11	eq_ref	PRIMARY	PRIMARY	4	test.t10.genreid	1	Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
@@ -3160,7 +3165,7 @@ Warning	1292	Truncated incorrect join_buffer_size value: '32'
 set join_cache_level=8;
 EXPLAIN SELECT * FROM t1,t2 WHERE t1.a=t2.a AND t1.b >= 30;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	idx	NULL	NULL	NULL	7	Using where
+1	SIMPLE	t1	range	idx	idx	5	NULL	3	Using index condition; Using where; Rowid-ordered scan
 1	SIMPLE	t2	ref	idx	idx	5	test.t1.a	2	Using join buffer (flat, BKAH join); Key-ordered Rowid-ordered scan
 SELECT * FROM t1,t2 WHERE t1.a=t2.a AND t1.b >= 30;
 a	b	a	b
@@ -5095,7 +5100,7 @@ SET SESSION join_cache_level = 1;
 EXPLAIN 
 SELECT * FROM t1,t2 WHERE t1.a < 3 and t2.a IS NULL;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	PRIMARY	PRIMARY	4	NULL	3	Using where; Using index
+1	SIMPLE	t1	range	PRIMARY	PRIMARY	4	NULL	2	Using where; Using index
 1	SIMPLE	t2	ref	idx	idx	5	const	4	Using index condition
 SELECT * FROM t1,t2 WHERE t1.a < 3 and t2.a IS NULL;
 a	a	b
@@ -5111,7 +5116,7 @@ SET SESSION join_cache_level = 4;
 EXPLAIN 
 SELECT * FROM t1,t2 WHERE t1.a < 3 and t2.a IS NULL;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	PRIMARY	PRIMARY	4	NULL	3	Using where; Using index
+1	SIMPLE	t1	range	PRIMARY	PRIMARY	4	NULL	2	Using where; Using index
 1	SIMPLE	t2	hash_range	idx	#hash#idx:idx	5:5	const	4	Using index condition; Using where; Rowid-ordered scan; Using join buffer (flat, BNLH join)
 SELECT * FROM t1,t2 WHERE t1.a < 3 and t2.a IS NULL;
 a	a	b
@@ -5414,7 +5419,7 @@ ORDER BY t2.b;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
 1	PRIMARY	t3	system	NULL	NULL	NULL	NULL	1	
-1	PRIMARY	t2	range	a,c	a	5	NULL	1	Using index condition; Using where; Using filesort
+1	PRIMARY	t2	range	a,c	a	5	NULL	2	Using index condition; Using where; Using filesort
 1	PRIMARY	t4	ref	c	c	5	test.t2.c	2	Using where; Start temporary; End temporary
 SELECT * FROM t1,t2
 WHERE t2.c IN (SELECT c FROM t3,t4 WHERE t4.a < 10) AND
@@ -5432,7 +5437,7 @@ ORDER BY t2.b;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	Using temporary; Using filesort
 1	PRIMARY	t3	system	NULL	NULL	NULL	NULL	1	
-1	PRIMARY	t2	range	a,c	a	5	NULL	1	Using index condition; Using where
+1	PRIMARY	t2	range	a,c	a	5	NULL	2	Using index condition; Using where
 1	PRIMARY	t4	ref	c	c	5	test.t2.c	2	Using where; Start temporary; End temporary
 SELECT * FROM t1,t2
 WHERE t2.c IN (SELECT c FROM t3,t4 WHERE t4.a < 10) AND
@@ -5451,7 +5456,7 @@ ORDER BY t2.b;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	Using temporary; Using filesort
 1	PRIMARY	t3	system	NULL	NULL	NULL	NULL	1	
-1	PRIMARY	t2	range	a,c	a	5	NULL	1	Using index condition; Using where
+1	PRIMARY	t2	range	a,c	a	5	NULL	2	Using index condition; Using where
 1	PRIMARY	t4	ref	c	c	5	test.t2.c	2	Using where; Start temporary; End temporary
 SELECT * FROM t1,t2
 WHERE t2.c IN (SELECT c FROM t3,t4 WHERE t4.a < 10) AND
@@ -5934,6 +5939,10 @@ CREATE TABLE t2 (i1 int, v1 varchar(1), KEY v1 (v1,i1)) ENGINE=InnoDB;
 INSERT INTO t2 VALUES
 (NULL,'x'),(1,'x'),(3,'x'),(5,'x'),(8,'x'),(48,'x'),
 (228,'x'),(3,'y'),(1,'z'),(9,'z');
+ANALYZE TABLE t1,t2;
+Table	Op	Msg_type	Msg_text
+test.t1	analyze	status	OK
+test.t2	analyze	status	OK
 CREATE TABLE temp
 SELECT t1.i1 AS f1, t1.v1 AS f2 FROM (t2 JOIN t1 ON (t1.v1 = t2.v1));
 SELECT * FROM temp
@@ -6050,3 +6059,6 @@ f2
 drop table t1, t2;
 set join_buffer_size = default;
 set @@optimizer_switch=@save_optimizer_switch;
+set global innodb_stats_persistent= @innodb_stats_persistent_save;
+set global innodb_stats_persistent_sample_pages=
+@innodb_stats_persistent_sample_pages_save;