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, 27 deletions

diff --git a/mysql-test/main/select.result b/mysql-test/main/select.result
index 94a92315acc..220f500e37a 100644
--- a/mysql-test/main/select.result
+++ b/mysql-test/main/select.result
@@ -2786,7 +2786,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index	key1	key1	5	NULL	4	Using where; Using index
 explain select min(key1) from t1 where key1 >= 0.3762 and rand() + 0.5 >= 0.5;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	key1	key1	5	NULL	3	Using where; Using index
+1	SIMPLE	t1	index	key1	key1	5	NULL	4	Using where; Using index
 select max(key1) from t1 where key1 <= 0.6158;
 max(key1)
 0.6158000230789185
@@ -3408,7 +3408,7 @@ ERROR 42000: You have an error in your SQL syntax; check the manual that corresp
 CREATE TABLE t1 (sku int PRIMARY KEY, pr int);
 CREATE TABLE t2 (sku int PRIMARY KEY, sppr int, name varchar(255));
 INSERT INTO t1 VALUES
-(10, 10), (20, 10), (30, 20), (40, 30), (50, 10), (60, 10);
+(10, 10), (20, 10), (30, 20), (40, 30), (50, 10), (60, 10), (70, 10);
 INSERT INTO t2 VALUES 
 (10, 10, 'aaa'), (20, 10, 'bbb'), (30, 10, 'ccc'), (40, 20, 'ddd'),
 (50, 10, 'eee'), (60, 20, 'fff'), (70, 20, 'ggg'), (80, 30, 'hhh');
@@ -3522,7 +3522,7 @@ INSERT INTO t2 VALUES
 EXPLAIN SELECT b FROM t1, t2 WHERE b=c AND a=1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
-1	SIMPLE	t2	ref	idx	idx	4	const	7	Using index
+1	SIMPLE	t2	ref	idx	idx	4	const	8	Using index
 EXPLAIN SELECT b FROM t1, t2 WHERE b=c AND a=4;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
@@ -3533,14 +3533,14 @@ INSERT INTO t1 VALUES (1,2), (2,NULL), (3,2);
 CREATE TABLE t2 (b int, c INT, INDEX idx1(b));
 INSERT INTO t2 VALUES (2,1), (3,2);
 CREATE TABLE t3 (d int,  e int, INDEX idx1(d));
-INSERT INTO t3 VALUES (2,10), (2,20), (1,30), (2,40), (2,50);
+INSERT INTO t3 VALUES (2,10), (2,20), (1,30), (2,40), (2,50), (1,60), (3,70), (1,80), (3,90);
 EXPLAIN
 SELECT * FROM t1 LEFT JOIN t2 ON t2.b=t1.a INNER JOIN t3 ON t3.d=t1.id
 WHERE t1.id=2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
 1	SIMPLE	t2	const	idx1	NULL	NULL	NULL	1	
-1	SIMPLE	t3	ref	idx1	idx1	5	const	3	
+1	SIMPLE	t3	ref	idx1	idx1	5	const	4	
 SELECT * FROM t1 LEFT JOIN t2 ON t2.b=t1.a INNER JOIN t3 ON t3.d=t1.id
 WHERE t1.id=2;
 id	a	b	c	d	e
@@ -3569,7 +3569,7 @@ EXPLAIN SELECT t2.*
 FROM t1 JOIN t2 ON t2.fk=t1.pk
 WHERE t2.fk < 'c' AND t2.pk=t1.fk;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	3	Using index condition; Using where
+1	SIMPLE	t1	range	PRIMARY	PRIMARY	12	NULL	2	Using index condition; Using where
 1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	18	test.t1.fk	1	Using where
 EXPLAIN SELECT t2.* 
 FROM t1 JOIN t2 ON t2.fk=t1.pk 
@@ -3616,7 +3616,7 @@ t3.a=t2.a AND t3.c IN ('bb','ee');
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
 1	SIMPLE	t2	range	si	si	5	NULL	4	Using index condition; Using where
-1	SIMPLE	t3	eq_ref	PRIMARY,ci	PRIMARY	4	test.t2.a	1	Using where
+1	SIMPLE	t3	eq_ref|filter	PRIMARY,ci	PRIMARY|ci	4|5	test.t2.a	1 (30%)	Using where; Using filter
 EXPLAIN
 SELECT t3.a FROM t1,t2,t3
 WHERE t1.id = 8 AND t2.i BETWEEN t1.b AND t1.e AND
@@ -3624,7 +3624,7 @@ t3.a=t2.a AND t3.c IN ('bb','ee') ;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	const	PRIMARY	PRIMARY	4	const	1	
 1	SIMPLE	t2	range	si,ai	si	5	NULL	4	Using index condition; Using where
-1	SIMPLE	t3	eq_ref	PRIMARY,ci	PRIMARY	4	test.t2.a	1	Using where
+1	SIMPLE	t3	eq_ref|filter	PRIMARY,ci	PRIMARY|ci	4|5	test.t2.a	1 (30%)	Using where; Using filter
 EXPLAIN 
 SELECT t3.a FROM t1,t2 FORCE INDEX (si),t3
 WHERE t1.id = 8 AND (t2.i=t1.b OR t2.i=t1.e) AND t3.a=t2.a AND
@@ -3698,6 +3698,9 @@ INSERT INTO t1 SELECT * FROM t1 WHERE ID1_with_null IS NULL;
 INSERT INTO t1 SELECT * FROM t1 WHERE ID2_with_null IS NULL;
 INSERT INTO t1 SELECT * FROM t1 WHERE ID1_with_null IS NULL;
 INSERT INTO t1 SELECT * FROM t1 WHERE ID2_with_null IS NULL;
+ANALYZE TABLE t1;
+Table	Op	Msg_type	Msg_text
+test.t1	analyze	status	OK
 SELECT COUNT(*) FROM t1 WHERE ID1_with_null IS NULL AND ID2_with_null=3;
 COUNT(*)
 24
@@ -3713,34 +3716,34 @@ COUNT(*)
 EXPLAIN SELECT * FROM t1
 WHERE ID_better=1 AND ID1_with_null IS NULL AND ID2_with_null=3 ;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ref	idx1,idx2	idx2	4	const	1	Using where
+1	SIMPLE	t1	ref	idx1,idx2	idx2	4	const	2	Using where
 EXPLAIN SELECT * FROM t1
 WHERE ID_better=1 AND ID1_with_null=3 AND ID2_with_null=3 IS NULL ;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ref	idx1,idx2	idx2	4	const	1	Using where
+1	SIMPLE	t1	ref	idx1,idx2	idx2	4	const	2	Using where
 EXPLAIN SELECT * FROM t1
 WHERE ID_better=1 AND ID1_with_null IS NULL AND ID2_with_null IS NULL;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ref	idx1,idx2	idx2	4	const	1	Using where
+1	SIMPLE	t1	ref	idx1,idx2	idx2	4	const	2	Using where
 DROP INDEX idx1 ON t1;
 CREATE UNIQUE INDEX idx1 ON t1(ID1_with_null,ID2_with_null);
 EXPLAIN SELECT * FROM t1
 WHERE ID_better=1 AND ID1_with_null IS NULL AND ID2_with_null=3 ;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ref	idx1,idx2	idx2	4	const	1	Using where
+1	SIMPLE	t1	ref	idx1,idx2	idx2	4	const	2	Using where
 EXPLAIN SELECT * FROM t1
 WHERE ID_better=1 AND ID1_with_null=3 AND ID2_with_null IS NULL ;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ref	idx1,idx2	idx2	4	const	1	Using where
+1	SIMPLE	t1	ref	idx1,idx2	idx2	4	const	2	Using where
 EXPLAIN SELECT * FROM t1
 WHERE ID_better=1 AND ID1_with_null IS NULL AND ID2_with_null IS NULL;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ref	idx1,idx2	idx2	4	const	1	Using where
+1	SIMPLE	t1	ref	idx1,idx2	idx2	4	const	2	Using where
 EXPLAIN SELECT * FROM t1
 WHERE ID_better=1 AND ID1_with_null IS NULL AND 
 (ID2_with_null=1 OR ID2_with_null=2);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ref	idx1,idx2	idx2	4	const	1	Using where
+1	SIMPLE	t1	ref|filter	idx1,idx2	idx1|idx2	5|4	const	2 (1%)	Using index condition; Using where; Using filter
 DROP TABLE t1;
 CREATE TABLE t1 (a INT, ts TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP, KEY ts(ts));
 INSERT INTO t1 VALUES (30,"2006-01-03 23:00:00"), (31,"2006-01-03 23:00:00");
@@ -3759,7 +3762,7 @@ AND t1.ts BETWEEN t2.dt1 AND t2.dt2
 AND t1.ts BETWEEN "2006-01-01" AND "2006-12-31";
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	const	PRIMARY	PRIMARY	4	const	1	
-1	SIMPLE	t1	range	ts	ts	4	NULL	1	Using index condition; Using where
+1	SIMPLE	t1	range	ts	ts	4	NULL	2	Using index condition; Using where
 SELECT * FROM t1 LEFT JOIN t2 ON (t1.a=t2.a) WHERE t1.a=30
 AND t1.ts BETWEEN t2.dt1 AND t2.dt2
 AND t1.ts BETWEEN "2006-01-01" AND "2006-12-31";
@@ -3801,6 +3804,7 @@ INSERT INTO t1 VALUES ('ccc'), ('bb'), ('cc '), ('aa  '), ('aa');
 INSERT INTO t2 VALUES ('bb',1), ('aa',2), ('cc   ',3);
 INSERT INTO t2 VALUES (concat('cc ', 0x06), 4);
 INSERT INTO t2 VALUES ('cc',5), ('bb ',6), ('cc ',7);
+INSERT INTO t2 VALUES ('bb ',8), ('aa',9), ('aa',10), ('bb',11);
 SELECT * FROM t2;
 name	n
 bb	1
@@ -3810,27 +3814,39 @@ cc 	4
 cc	5
 bb 	6
 cc 	7
+bb 	8
+aa	9
+aa	10
+bb	11
 SELECT * FROM t2 ORDER BY name;
 name	n
 aa	2
+aa	10
+aa	9
 bb	1
+bb 	8
 bb 	6
+bb	11
 cc 	4
-cc   	3
-cc	5
 cc 	7
+cc	5
+cc   	3
 SELECT name, LENGTH(name), n FROM t2 ORDER BY name;
 name	LENGTH(name)	n
 aa	2	2
+aa	2	10
+aa	2	9
 bb	2	1
+bb 	3	8
 bb 	3	6
+bb	2	11
 cc 	4	4
-cc   	5	3
-cc	2	5
 cc 	3	7
+cc	2	5
+cc   	5	3
 EXPLAIN SELECT name, LENGTH(name), n FROM t2 WHERE name='cc ';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ref	name	name	6	const	3	Using where
+1	SIMPLE	t2	ref	name	name	6	const	4	Using where
 SELECT name, LENGTH(name), n FROM t2 WHERE name='cc ';
 name	LENGTH(name)	n
 cc   	5	3
@@ -3838,7 +3854,7 @@ cc	2	5
 cc 	3	7
 EXPLAIN SELECT name , LENGTH(name), n FROM t2 WHERE name LIKE 'cc%';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	range	name	name	6	NULL	3	Using where
+1	SIMPLE	t2	range	name	name	6	NULL	4	Using where
 SELECT name , LENGTH(name), n FROM t2 WHERE name LIKE 'cc%';
 name	LENGTH(name)	n
 cc   	5	3
@@ -3847,7 +3863,7 @@ cc	2	5
 cc 	3	7
 EXPLAIN SELECT name , LENGTH(name), n FROM t2 WHERE name LIKE 'cc%' ORDER BY name;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	range	name	name	6	NULL	3	Using where; Using filesort
+1	SIMPLE	t2	range	name	name	6	NULL	4	Using where; Using filesort
 SELECT name , LENGTH(name), n FROM t2 WHERE name LIKE 'cc%' ORDER BY name;
 name	LENGTH(name)	n
 cc 	4	4
@@ -3863,11 +3879,17 @@ name	name	n
 ccc	NULL	NULL
 bb	bb	1
 bb	bb 	6
+bb	bb 	8
+bb	bb	11
 cc 	cc   	3
 cc 	cc	5
 cc 	cc 	7
 aa  	aa	2
+aa  	aa	9
+aa  	aa	10
 aa	aa	2
+aa	aa	9
+aa	aa	10
 DROP TABLE t1,t2;
 CREATE TABLE t1 (name text);
 CREATE TABLE t2 (name text, n int, KEY (name(3)));
@@ -3875,6 +3897,7 @@ INSERT INTO t1 VALUES ('ccc'), ('bb'), ('cc '), ('aa  '), ('aa');
 INSERT INTO t2 VALUES ('bb',1), ('aa',2), ('cc   ',3);
 INSERT INTO t2 VALUES (concat('cc ', 0x06), 4);
 INSERT INTO t2 VALUES ('cc',5), ('bb ',6), ('cc ',7);
+INSERT INTO t2 VALUES ('bb ',8), ('aa',9), ('aa',10), ('bb',11);
 SELECT * FROM t2;
 name	n
 bb	1
@@ -3884,11 +3907,19 @@ cc 	4
 cc	5
 bb 	6
 cc 	7
+bb 	8
+aa	9
+aa	10
+bb	11
 SELECT * FROM t2 ORDER BY name;
 name	n
 aa	2
+aa	9
+aa	10
 bb	1
 bb 	6
+bb 	8
+bb	11
 cc 	4
 cc   	3
 cc	5
@@ -3896,15 +3927,19 @@ cc 	7
 SELECT name, LENGTH(name), n FROM t2 ORDER BY name;
 name	LENGTH(name)	n
 aa	2	2
+aa	2	9
+aa	2	10
 bb	2	1
 bb 	3	6
+bb 	3	8
+bb	2	11
 cc 	4	4
 cc   	5	3
 cc	2	5
 cc 	3	7
 EXPLAIN SELECT name, LENGTH(name), n FROM t2 WHERE name='cc ';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ref	name	name	6	const	3	Using where
+1	SIMPLE	t2	ref	name	name	6	const	4	Using where
 SELECT name, LENGTH(name), n FROM t2 WHERE name='cc ';
 name	LENGTH(name)	n
 cc   	5	3
@@ -3912,7 +3947,7 @@ cc	2	5
 cc 	3	7
 EXPLAIN SELECT name , LENGTH(name), n FROM t2 WHERE name LIKE 'cc%';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	range	name	name	6	NULL	3	Using where
+1	SIMPLE	t2	range	name	name	6	NULL	4	Using where
 SELECT name , LENGTH(name), n FROM t2 WHERE name LIKE 'cc%';
 name	LENGTH(name)	n
 cc   	5	3
@@ -3921,7 +3956,7 @@ cc	2	5
 cc 	3	7
 EXPLAIN SELECT name , LENGTH(name), n FROM t2 WHERE name LIKE 'cc%' ORDER BY name;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	range	name	name	6	NULL	3	Using where; Using filesort
+1	SIMPLE	t2	range	name	name	6	NULL	4	Using where; Using filesort
 SELECT name , LENGTH(name), n FROM t2 WHERE name LIKE 'cc%' ORDER BY name;
 name	LENGTH(name)	n
 cc 	4	4
@@ -3937,11 +3972,17 @@ name	name	n
 ccc	NULL	NULL
 bb	bb	1
 bb	bb 	6
+bb	bb 	8
+bb	bb	11
 cc 	cc   	3
 cc 	cc	5
 cc 	cc 	7
 aa  	aa	2
+aa  	aa	9
+aa  	aa	10
 aa	aa	2
+aa	aa	9
+aa	aa	10
 DROP TABLE t1,t2;
 CREATE TABLE t1 (
 access_id int NOT NULL default '0',
@@ -5211,7 +5252,7 @@ INSERT INTO `CC` VALUES
 EXPLAIN SELECT `varchar_nokey` G1  FROM CC  WHERE `int_nokey` AND `int_key`  <= 4
 HAVING G1  ORDER  BY `varchar_key` LIMIT  6   ;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	CC	range	int_key	int_key	4	NULL	10	Using index condition; Using where; Using filesort
+1	SIMPLE	CC	range	int_key	int_key	4	NULL	9	Using index condition; Using where; Using filesort
 SELECT `varchar_nokey` G1  FROM CC  WHERE `int_nokey` AND `int_key`  <= 4
 HAVING G1  ORDER  BY `varchar_key` LIMIT  6   ;
 G1