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, 9 insertions, 9 deletions

diff --git a/mysql-test/main/join_nested_jcl6.result b/mysql-test/main/join_nested_jcl6.result
index 6b1901d8642..bc65286588c 100644
--- a/mysql-test/main/join_nested_jcl6.result
+++ b/mysql-test/main/join_nested_jcl6.result
@@ -1073,9 +1073,9 @@ t0.b=t1.b AND
 (t8.b=t9.b OR t8.c IS NULL) AND
 (t9.a=1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	SIMPLE	t0	ref	idx_a	idx_a	5	const	1	100.00	Using where
-1	SIMPLE	t1	ref	idx_b	idx_b	5	test.t0.b	2	100.00	Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
-1	SIMPLE	t9	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (incremental, BNL join)
+1	SIMPLE	t0	ref	idx_a	idx_a	5	const	2	100.00	
+1	SIMPLE	t9	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t1	ALL	idx_b	NULL	NULL	NULL	7	85.71	Using where; Using join buffer (incremental, BNL join)
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	8	100.00	Using where; Using join buffer (incremental, BNL join)
 1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where; Using join buffer (incremental, BNL join)
 1	SIMPLE	t4	ref	idx_b	idx_b	5	test.t2.b	2	100.00	Using where; Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
@@ -1220,13 +1220,13 @@ INSERT INTO t3 VALUES (0), (1), (2), (3), (4), (5);
 EXPLAIN SELECT a, b, c FROM t1 LEFT JOIN (t2, t3) ON c < 3 and b = c;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index	NULL	a	5	NULL	21	Using index
-1	SIMPLE	t3	index	c	c	5	NULL	6	Using where; Using index
-1	SIMPLE	t2	ref	b	b	5	test.t3.c	2	Using index
+1	SIMPLE	t2	range	b	b	5	NULL	3	Using where; Using index
+1	SIMPLE	t3	ref	c	c	5	test.t2.b	2	Using index
 EXPLAIN SELECT a, b, c FROM t1 LEFT JOIN (t2, t3) ON b < 3 and b = c;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	index	NULL	a	5	NULL	21	Using index
-1	SIMPLE	t3	index	c	c	5	NULL	6	Using where; Using index
-1	SIMPLE	t2	ref	b	b	5	test.t3.c	2	Using index
+1	SIMPLE	t2	range	b	b	5	NULL	3	Using where; Using index
+1	SIMPLE	t3	ref	c	c	5	test.t2.b	2	Using index
 SELECT a, b, c FROM t1 LEFT JOIN (t2, t3) ON b < 3 and b = c;
 a	b	c
 NULL	0	0
@@ -2002,8 +2002,8 @@ ON t6.b >= 2 AND t5.b=t7.b AND
 (t8.a > 0 OR t8.c IS NULL) AND t6.a>0 AND t7.a>0;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t5	ALL	NULL	NULL	NULL	NULL	3	
-1	SIMPLE	t7	ref	PRIMARY,b_i	b_i	5	test.t5.b	2	Using where; Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
-1	SIMPLE	t6	ALL	PRIMARY,b_i	NULL	NULL	NULL	7	Using where; Using join buffer (incremental, BNL join)
+1	SIMPLE	t7	ref|filter	PRIMARY,b_i	b_i|PRIMARY	5|4	test.t5.b	2 (29%)	Using where; Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan; Using filter
+1	SIMPLE	t6	range|filter	PRIMARY,b_i	PRIMARY|b_i	4|5	NULL	3 (86%)	Using where; Rowid-ordered scan; Using join buffer (incremental, BNL join); Using filter
 1	SIMPLE	t8	ref	b_i	b_i	5	test.t5.b	2	Using where; Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
 SELECT t5.a,t5.b,t6.a,t6.b,t7.a,t7.b,t8.a,t8.b
 FROM t5