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.

3 files changed, 13 insertions, 6 deletions

diff --git a/mysql-test/include/explain_non_select.inc b/mysql-test/include/explain_non_select.inc
index 57b96994d20..d22310c9813 100644
--- a/mysql-test/include/explain_non_select.inc
+++ b/mysql-test/include/explain_non_select.inc
@@ -158,7 +158,7 @@ CREATE TABLE t1 ( a int PRIMARY KEY );
 --let $query =  DELETE   FROM t1 WHERE t1.a > 0 ORDER BY t1.a
 --let $select = SELECT * FROM t1 WHERE t1.a > 0 ORDER BY t1.a
 --source include/explain_utils.inc
-INSERT INTO t1 VALUES (1), (2), (3);
+INSERT INTO t1 VALUES (1), (2), (3), (-1), (-2), (-3);
 --let $query =  DELETE   FROM t1 WHERE t1.a > 0 ORDER BY t1.a
 --let $select = SELECT * FROM t1 WHERE t1.a > 0 ORDER BY t1.a
 --source include/explain_utils.inc
@@ -640,7 +640,7 @@ DROP VIEW v1;
 
 --echo #63
 CREATE TABLE t1 (a INT, PRIMARY KEY(a));
-INSERT INTO t1 VALUES (1), (2), (3), (4), (5);
+INSERT INTO t1 VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9);
 CREATE VIEW v1 (a) AS SELECT a FROM t1;
 --let $query =  DELETE   FROM v1 WHERE a < 4
 --let $select = SELECT * FROM v1 WHERE a < 4
diff --git a/mysql-test/include/icp_tests.inc b/mysql-test/include/icp_tests.inc
index f29088887d0..f82a5a21b87 100644
--- a/mysql-test/include/icp_tests.inc
+++ b/mysql-test/include/icp_tests.inc
@@ -633,6 +633,8 @@ CREATE TABLE t2 (
 );
 INSERT INTO t2 VALUES (4,1);
 
+ANALYZE TABLE t1,t2;
+
 EXPLAIN
 SELECT t1.d1, t2.pk, t2.i1 FROM t1 STRAIGHT_JOIN t2 ON t2.i1
   WHERE t2.pk <> t1.d1 AND t2.pk = 4;
@@ -840,6 +842,8 @@ INSERT INTO t2 (g,h) VALUES
 (3,'e'),(1,'u'),(4,'v'),(9,'u'),(6,'i'),(1,'x'),
 (7,'f'),(5,'j'),(3,'e'),(1,'u'),(4,'v'),(9,'u');
 
+ANALYZE TABLE t1,t2;
+
 SET @save_optimize_switch=@@optimizer_switch;
 SET optimizer_switch='materialization=on';
 
diff --git a/mysql-test/include/index_merge1.inc b/mysql-test/include/index_merge1.inc
index b63b2db78da..f2ef38f72f8 100644
--- a/mysql-test/include/index_merge1.inc
+++ b/mysql-test/include/index_merge1.inc
@@ -57,12 +57,12 @@ update t0 set key2=key1,key3=key1,key4=key1,key5=key1,key6=key1,key7=key1,key8=1
 analyze table t0;
 
 # 1. One index
-explain select * from t0 where key1 < 3 or key1 > 1020;
+explain select * from t0 where key1 < 3 or key1 > 920 and key1 < 924;
 
 # 2. Simple cases
 explain
-select * from t0 where key1 < 3 or key2 > 1020;
-select * from t0 where key1 < 3 or key2 > 1020;
+select * from t0 where key1 < 3 or key2 > 920 and key2 < 924;
+select * from t0 where key1 < 3 or key2 > 920 and key2 < 924;
 
 select * from t0 where key1=1022; # MDEV-13535 no-key-read select after keyread
 
@@ -115,7 +115,6 @@ select * from t0 where (key1 < 3 or key2 < 6) and (key1 < 7 or key3 < 4);
 
 select * from t0 where (key1 < 3 or key2 < 6) and (key1 < 7 or key3 < 4);
 
-
 explain select * from t0 where
   (key1 < 3 or key2 < 3) and (key3 < 4 or key4 < 4) and (key5 < 2 or key6 < 2);
 
@@ -146,6 +145,10 @@ select * from t0 where
     key1 < 7;
 
 #   tree_or(List<SEL_IMERGE>, List<SEL_IMERGE>).
+select count(*) from t0 where
+    ((key1 < 4 or key2 < 4) and (key3 <5 or key5 < 4))
+  or
+    ((key5 < 5 or key6 < 6) and (key7 <7 or key8 < 4));
 explain select * from t0 where
     ((key1 < 4 or key2 < 4) and (key3 <5 or key5 < 4))
   or