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, 13 insertions, 4 deletions

diff --git a/mysql-test/main/subselect_sj_mat.test b/mysql-test/main/subselect_sj_mat.test
index 7b8179bba38..2cffa2e82b8 100644
--- a/mysql-test/main/subselect_sj_mat.test
+++ b/mysql-test/main/subselect_sj_mat.test
@@ -55,6 +55,7 @@ create index it3i3 on t3i (c1, c2);
 insert into t1i select * from t1;
 insert into t2i select * from t2;
 insert into t3i select * from t3;
+analyze table t1,t2,t3,t1i,t2i,t3i;
 
 # force the use of materialization
 set @@optimizer_switch='materialization=on,in_to_exists=off,firstmatch=off';
@@ -108,16 +109,24 @@ select * from t1i where (a1, a2) in (select b1, min(b2) from t2i where b1 > '0'
 select * from t1i where (a1, a2) in (select b1, min(b2) from t2i where b1 > '0' group by b1);
 
 # BUG#31639: Wrong plan for uncorrelated subquery when loose scan is applicable.
+create table t2i_c like t2i;
+insert into t2i_c select * from t2i;
+insert into t2i_c select * from t2i;
+insert into t2i_c select * from t2i;
+insert into t2i_c select * from t2i;
+analyze table t2i_c;
+show create table t2i_c;
 explain extended
-select * from t1 where (a1, a2) in (select b1, max(b2) from t2i group by b1);
-select * from t1 where (a1, a2) in (select b1, max(b2) from t2i group by b1);
+select * from t1 where (a1, a2) in (select b1, max(b2) from t2i_c group by b1);
+select * from t1 where (a1, a2) in (select b1, max(b2) from t2i_c group by b1);
 
-prepare st1 from "explain select * from t1 where (a1, a2) in (select b1, max(b2) from t2i group by b1)";
+prepare st1 from "explain select * from t1 where (a1, a2) in (select b1, max(b2) from t2i_c group by b1)";
 execute st1;
 execute st1;
-prepare st2 from "select * from t1 where (a1, a2) in (select b1, max(b2) from t2i group by b1)";
+prepare st2 from "select * from t1 where (a1, a2) in (select b1, max(b2) from t2i_c group by b1)";
 execute st2;
 execute st2;
+drop table t2i_c;
 
 explain extended
 select * from t1 where (a1, a2) in (select b1, min(b2) from t2i where b1 > '0' group by b1);