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, 19 insertions, 16 deletions

diff --git a/mysql-test/main/index_intersect.test b/mysql-test/main/index_intersect.test
index 1be963cb9e5..c77eccc6335 100644
--- a/mysql-test/main/index_intersect.test
+++ b/mysql-test/main/index_intersect.test
@@ -33,6 +33,7 @@ ANALYZE TABLE City;
 --enable_result_log
 --enable_query_log
 
+SET SESSION optimizer_switch='rowid_filter=off';
 SET SESSION optimizer_switch='index_merge_sort_intersection=on';
 
 SELECT COUNT(*) FROM City;
@@ -117,6 +118,7 @@ SELECT COUNT(*) FROM City WHERE Population > 1000000;
 SELECT COUNT(*) FROM City WHERE Population > 500000;
 SELECT COUNT(*) FROM City WHERE Country LIKE 'C%';
 SELECT COUNT(*) FROM City WHERE Country LIKE 'B%';
+SELECT COUNT(*) FROM City WHERE Country LIKE 'J%';
 
 
 # The pattern of the WHERE condition used in the following 3 queries is
@@ -134,7 +136,7 @@ SELECT * FROM City
 --replace_column 9 #
 EXPLAIN
 SELECT * FROM City 
-  WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+  WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'J%';
 
 --replace_column 7 # 9 #
 --replace_result Population,Country,Name Population,Name,Country
@@ -156,11 +158,11 @@ SELECT * FROM City
 
 
 SELECT * FROM City USE INDEX ()
-  WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+  WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'J%';
 
 --sorted_result
 SELECT * FROM City 
-  WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+  WHERE Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'J%';
 
 
 SELECT * FROM City USE INDEX ()
@@ -207,7 +209,7 @@ SELECT * FROM City
 --replace_column 9 #
 EXPLAIN
 SELECT * FROM City
-  WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+  WHERE ID BETWEEN 1 AND 500 AND Population > 700000 AND Country LIKE 'C%';
 
 --replace_column 9 #
 EXPLAIN
@@ -241,10 +243,10 @@ SELECT * FROM City
 
 --sorted_result
 SELECT * FROM City USE INDEX ()
-  WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+  WHERE ID BETWEEN 1 AND 500 AND Population > 700000 AND Country LIKE 'C%';
 --sorted_result
 SELECT * FROM City
-  WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+  WHERE ID BETWEEN 1 AND 500 AND Population > 700000 AND Country LIKE 'C%';
 
 
 SELECT * FROM City USE INDEX ()
@@ -293,7 +295,7 @@ SELECT * FROM City WHERE
 --replace_column 9 #
 EXPLAIN
 SELECT * FROM City 
-  WHERE  Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'B%';
+  WHERE  Name BETWEEN 'G' AND 'J' AND Population > 1000000 AND Country LIKE 'J%';
 
 --replace_column 9 #
 EXPLAIN
@@ -304,7 +306,7 @@ SELECT * FROM City
 --replace_column 9 #
 EXPLAIN
 SELECT * FROM City
-  WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+  WHERE ID BETWEEN 1 AND 500 AND Population > 700000 AND Country LIKE 'C%';
 
 --replace_column 9 #
 --replace_result PRIMARY,Country,Population PRIMARY,Population,Country 4,7,4 4,4,7
@@ -326,7 +328,7 @@ SELECT * FROM City WHERE
 
 --sorted_result
 SELECT * FROM City 
-  WHERE  Name BETWEEN 'G' AND 'J' AND Population > 700000 AND Country LIKE 'B%';
+  WHERE  Name BETWEEN 'G' AND 'J' AND Population > 700000 AND Country LIKE 'J%';
 
 --sorted_result
 SELECT * FROM City 
@@ -334,7 +336,7 @@ SELECT * FROM City
 
 
 SELECT * FROM City
-  WHERE ID BETWEEN 1 AND 500 AND Population > 1000000 AND Country LIKE 'A%';
+  WHERE ID BETWEEN 1 AND 500 AND Population > 700000 AND Country LIKE 'C%';
 --sorted_result
 SELECT * FROM City 
   WHERE ID BETWEEN 3001 AND 4000 AND Population > 600000
@@ -371,12 +373,12 @@ SELECT * FROM City
 --replace_column 9 #
 EXPLAIN
 SELECT * FROM City 
-  WHERE Country='CHN' AND Population > 1500000;
+  WHERE Country='USA' AND Population > 1000000;
 
 --replace_column 9 #
 EXPLAIN
 SELECT * FROM City 
-  WHERE Country='CHN' AND Population > 1500000 AND Name LIKE 'C%';
+  WHERE Country='USA' AND Population > 1500000 AND Name LIKE 'C%';
 
 
 # Check that the previous 3 plans return the right results when executed
@@ -390,18 +392,18 @@ SELECT * FROM City
 
 --sorted_result
 SELECT * FROM City USE INDEX ()
-  WHERE Country='CHN' AND Population > 1500000;
+  WHERE Country='USA' AND Population > 1000000;
 --sorted_result
 SELECT * FROM City 
-  WHERE Country='CHN' AND Population > 1500000;
+  WHERE Country='USA' AND Population > 1000000;
 
 
 SELECT * FROM City USE INDEX ()
-  WHERE Country='CHN' AND Population > 1500000 AND Name LIKE 'C%';
+  WHERE Country='USA' AND Population > 1500000 AND Name LIKE 'C%';
 
 --sorted_result
 SELECT * FROM City 
-  WHERE Country='CHN' AND Population > 1500000 AND Name LIKE 'C%';
+  WHERE Country='USA' AND Population > 1500000 AND Name LIKE 'C%';
 
 
 #
@@ -459,3 +461,4 @@ WHERE (f1 < 535  OR  f1 > 985) AND ( f4='r' OR f4 LIKE 'a%' ) ;
 DROP TABLE t1;
 
 SET SESSION optimizer_switch='index_merge_sort_intersection=on';
+SET SESSION optimizer_switch='rowid_filter=default';