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, 11 insertions, 10 deletions

diff --git a/mysql-test/main/func_group.result b/mysql-test/main/func_group.result
index 9f3928615ec..5526acb8825 100644
--- a/mysql-test/main/func_group.result
+++ b/mysql-test/main/func_group.result
@@ -612,12 +612,12 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 explain
 select max(a3) from t1 where a2 < 2 and a3 < 'SEA';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	range	k1	k1	3	NULL	6	Using where; Using index
+1	SIMPLE	t1	range	k1	k1	3	NULL	7	Using where; Using index
 explain
-select max(t1.a3), min(t2.a2) from t1, t2 where t1.a2 = 2 and t1.a3 < 'MIN' and t2.a3 > 'CA';
+select max(t1.a3), min(t2.a2) from t1, t2 where t1.a2 = 2 and t1.a3 < 'DEN' and t2.a3 >= 'LA';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	range	k1	k1	7	NULL	1	Using where; Using index
-1	SIMPLE	t2	range	k1	k1	3	NULL	4	Using where; Using index; Using join buffer (flat, BNL join)
+1	SIMPLE	t2	range	k1	k1	3	NULL	2	Using where; Using index; Using join buffer (flat, BNL join)
 explain
 select min(a4 - 0.01) from t1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
@@ -653,7 +653,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 explain
 select concat(min(t1.a1),min(t2.a4)) from t1, t2 where t2.a4 <> 'AME';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	range	k2	k2	4	NULL	6	Using where; Using index
+1	SIMPLE	t2	index	k2	k2	4	NULL	7	Using where; Using index
 1	SIMPLE	t1	index	NULL	PRIMARY	3	NULL	15	Using index; Using join buffer (flat, BNL join)
 drop table t1, t2;
 create table t1 (a char(10));
@@ -1333,10 +1333,11 @@ SELECT MIN(a), MIN(b) FROM t1;
 MIN(a)	MIN(b)
 NULL	1
 CREATE TABLE t2( a INT, b INT, c INT, KEY(a, b) );
-INSERT INTO t2 ( a, b, c ) VALUES ( 1, NULL, 2 ), ( 1, 3, 4 ), ( 1, 4, 4 );
+INSERT INTO t2 ( a, b, c ) VALUES
+( 1, NULL, 2 ), ( 1, 3, 4 ), ( 1, 4, 4 ), ( 2, NULL, 2 ), ( 2, 3, 4 ), ( 2, 4, 4 );
 EXPLAIN SELECT MIN(b), MIN(c) FROM t2 WHERE a = 1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ref	a	a	5	const	2	
+1	SIMPLE	t2	ref	a	a	5	const	3	
 SELECT MIN(b), MIN(c) FROM t2 WHERE a = 1;
 MIN(b)	MIN(c)
 3	2
@@ -1839,12 +1840,12 @@ End of 5.1 tests
 # Bug #904345: MIN/MAX optimization  with constant FALSE condition
 #
 CREATE TABLE t1 (a int NOT NULL, KEY(a));
-INSERT INTO t1 VALUES (10), (8), (11), (7), (15), (12), (9);
+INSERT INTO t1 VALUES (10), (8), (11), (7), (15), (12), (9), (13), (15), (17);
 CREATE TABLE t2 (a int, b int);
 INSERT INTO t2 VALUES
 (8,2), (6,9), (8,4), (5,3), (9,1);
 EXPLAIN EXTENDED
-SELECT MAX(a) FROM t1 WHERE (1,2) IN (SELECT 3,4) AND a<10;
+SELECT MAX(a) FROM t1 WHERE (1,2) IN (SELECT 3,4) AND a<8;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
 2	SUBQUERY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	No tables used
@@ -1857,7 +1858,7 @@ EXPLAIN EXTENDED
 SELECT MAX(a) FROM t1 WHERE (1,2) IN (SELECT a,b FROM t2 WHERE b<5) and a<10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	<subquery2>	eq_ref	distinct_key	distinct_key	8	func,func	1	100.00	
-1	PRIMARY	t1	range	a	a	4	NULL	4	100.00	Using where; Using index; Using join buffer (flat, BNL join)
+1	PRIMARY	t1	range	a	a	4	NULL	3	100.00	Using where; Using index; Using join buffer (flat, BNL join)
 2	MATERIALIZED	t2	ALL	NULL	NULL	NULL	NULL	5	100.00	Using where
 Warnings:
 Note	1003	select max(`test`.`t1`.`a`) AS `MAX(a)` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`a` = 1 and `test`.`t2`.`b` = 2 and `test`.`t1`.`a` < 10
@@ -1867,7 +1868,7 @@ NULL
 EXPLAIN EXTENDED
 SELECT MAX(a) FROM t1 WHERE RAND()*0<>0 AND a<10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	SIMPLE	t1	range	a	a	4	NULL	4	100.00	Using where; Using index
+1	SIMPLE	t1	range	a	a	4	NULL	3	100.00	Using where; Using index
 Warnings:
 Note	1003	select max(`test`.`t1`.`a`) AS `MAX(a)` from `test`.`t1` where rand() * 0 <> 0 and `test`.`t1`.`a` < 10
 SELECT MAX(a) FROM t1 WHERE RAND()*0<>0 AND a<10;