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, 6 insertions, 2 deletions

diff --git a/mysql-test/main/select.test b/mysql-test/main/select.test
index 52ef4aa2111..0d43dfd55b9 100644
--- a/mysql-test/main/select.test
+++ b/mysql-test/main/select.test
@@ -2915,7 +2915,7 @@ 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'),
@@ -3048,7 +3048,7 @@ 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
@@ -3230,6 +3230,8 @@ 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;
+
 SELECT COUNT(*) FROM t1 WHERE ID1_with_null IS NULL AND ID2_with_null=3;
 SELECT COUNT(*) FROM t1 WHERE ID1_with_null=3 AND ID2_with_null IS NULL;
 SELECT COUNT(*) FROM t1 WHERE ID1_with_null IS NULL AND ID2_with_null IS NULL;
@@ -3311,6 +3313,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;
 SELECT * FROM t2 ORDER BY name;
 SELECT name, LENGTH(name), n FROM t2 ORDER BY name;
@@ -3332,6 +3335,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;
 SELECT * FROM t2 ORDER BY name;
 SELECT name, LENGTH(name), n FROM t2 ORDER BY name;