MDEV-30699: Updated prev_record_reads() to be more exact

The old code in prev_record_reads() did give wrong estimates when a
join_buffer was used or if the table was depending on more than one
other tables. When join_cache is used, it will cause a re-order of row
combinations, which causes more calls to the engine for tables that
are depending on tables before the join_cached one.

The new prev_records_read() code provides more exact estimates and
should never give a 'too low estimate', assuming that the data to the
function is correct

The definition of prev_record_read() is also updated.
The new definition is:
  "Estimate the number of engine ha_index_read_calls for EQ_REF tables
  when taking into account the one-row-cache in join_read_always_key()"

The cost of using prev_record_reads() value is changed. The value is
now used similar as before to calculate the cost of the storage engine
calls. However the cost of the WHERE cost is changed to take into
account the total number of row combinations as the WHERE has to be
checked even if the one-row-cache is used. This makes the cost
slightly higher than before (for the same prev_record_reads() value).

Other things:
- Cached return value of prev_record_read() in best_access_path() to
  avoid some function calls.
- Fixed bug where position[].use_join_buffer was set in
  best_acess_path() when join buffer was not used. This confused the
  semi join optimizer to try to reoptimize plans that did not need to be
  reoptimized.
  The effect of the bug fix is that we avoid doing some re-optimziations
  with semi-joins when join_buffer is not used. In these cases the value
  shown for the 'Filtering' column in EXPLAIN EXTENDED may change.
- Added 'prev_record.cc' that was used to verify the logic in
  prev_record_reads().

Changes in test suite:
- EQ_REF tables are moved up to be earlier. This is because either the
  higher WHERE cost when EQ_REF is used with more row combination or
  change of cost when using join_cache.
- Filtered has changed (to the better) for some cases using semi-joins
  subselect_sj.test subselect_sj_jcl6.test

15 files changed, 898 insertions, 239 deletions

diff --git a/mysql-test/main/greedy_optimizer.result b/mysql-test/main/greedy_optimizer.result
index 2bf67d5f6d8..5ff3bd62e89 100644
--- a/mysql-test/main/greedy_optimizer.result
+++ b/mysql-test/main/greedy_optimizer.result
@@ -127,7 +127,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t6.c62	1	Using index
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	1.650935
+Last_query_cost	4.284314
 explain select t1.c11 from t7, t6, t5, t4, t3, t2, t1 where t1.c12 = t2.c21 and t2.c22 = t3.c31 and t3.c32 = t4.c41 and t4.c42 = t5.c51 and t5.c52 = t6.c61 and t6.c62 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	
@@ -139,7 +139,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t6.c62	1	Using index
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	1.650935
+Last_query_cost	4.284314
 explain select t1.c11 from t1, t2, t3, t4, t5, t6, t7 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
@@ -198,76 +198,76 @@ select @@optimizer_search_depth;
 0
 explain select t1.c11 from t1, t2, t3, t4, t5, t6, t7 where t1.c12 = t2.c21 and t2.c22 = t3.c31 and t3.c32 = t4.c41 and t4.c42 = t5.c51 and t5.c52 = t6.c61 and t6.c62 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
+1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t2.c22	1	
 1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t4.c42	1	
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
-1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t2.c22	1	Using where
-1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t4.c42	1	Using where
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t6.c62	1	Using index
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	1.405838
+Last_query_cost	2.998640
 explain select t1.c11 from t7, t6, t5, t4, t3, t2, t1 where t1.c12 = t2.c21 and t2.c22 = t3.c31 and t3.c32 = t4.c41 and t4.c42 = t5.c51 and t5.c52 = t6.c61 and t6.c62 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
+1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t2.c22	1	
 1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t4.c42	1	
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t6.c62	1	Using index
-1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t4.c42	1	Using where
-1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t2.c22	1	Using where
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	1.405838
+Last_query_cost	2.998640
 explain select t1.c11 from t1, t2, t3, t4, t5, t6, t7 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
-1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using join buffer (flat, BNL join)
-1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using join buffer (flat, BNL join)
 1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	4	test.t2.c21	1	Using where
 1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t1.c12	1	Using index
 1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t1.c14	1	Using index
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t1.c16	1	Using index
+1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	0.494824
+Last_query_cost	0.602062
 explain select t1.c11 from t7, t6, t5, t4, t3, t2, t1 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
-1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using join buffer (flat, BNL join)
-1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using join buffer (flat, BNL join)
 1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	4	test.t2.c21	1	Using where
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t1.c16	1	Using index
 1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t1.c14	1	Using index
 1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t1.c12	1	Using index
+1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	0.494824
+Last_query_cost	0.602062
 explain select t1.c11 from t1, t2, t3, t4, t5, t6, t7 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71 and t2.c22 = t3.c32 and t2.c23 = t4.c42 and t2.c24 = t5.c52 and t2.c25 = t6.c62 and t2.c26 = t7.c72 and t3.c33 = t4.c43 and t3.c34 = t5.c53 and t3.c35 = t6.c63 and t3.c36 = t7.c73 and t4.c42 = t5.c54 and t4.c43 = t6.c64 and t4.c44 = t7.c74 and t5.c52 = t6.c65 and t5.c53 = t7.c75 and t6.c62 = t7.c76;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
-1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
-1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	4	test.t2.c21	1	Using where
 1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t1.c12	1	Using where
 1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t1.c14	1	Using where
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t1.c16	1	Using where
+1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	0.453844
+Last_query_cost	0.621783
 explain select t1.c11 from t7, t6, t5, t4, t3, t2, t1 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71 and t2.c22 = t3.c32 and t2.c23 = t4.c42 and t2.c24 = t5.c52 and t2.c25 = t6.c62 and t2.c26 = t7.c72 and t3.c33 = t4.c43 and t3.c34 = t5.c53 and t3.c35 = t6.c63 and t3.c36 = t7.c73 and t4.c42 = t5.c54 and t4.c43 = t6.c64 and t4.c44 = t7.c74 and t5.c52 = t6.c65 and t5.c53 = t7.c75 and t6.c62 = t7.c76;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
-1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
-1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	4	test.t2.c21	1	Using where
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t1.c16	1	Using where
 1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t1.c14	1	Using where
 1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t1.c12	1	Using where
+1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	0.453844
+Last_query_cost	0.621783
 set optimizer_search_depth=1;
 select @@optimizer_search_depth;
 @@optimizer_search_depth
@@ -283,7 +283,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	34.291074
+Last_query_cost	42.599713
 explain select t1.c11 from t7, t6, t5, t4, t3, t2, t1 where t1.c12 = t2.c21 and t2.c22 = t3.c31 and t3.c32 = t4.c41 and t4.c42 = t5.c51 and t5.c52 = t6.c61 and t6.c62 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t7	index	PRIMARY	PRIMARY	4	NULL	21	Using index
@@ -295,7 +295,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	34.291074
+Last_query_cost	42.599713
 explain select t1.c11 from t1, t2, t3, t4, t5, t6, t7 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t3	index	PRIMARY	PRIMARY	4	NULL	9	Using index
@@ -307,7 +307,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	14.789792
+Last_query_cost	14.817907
 explain select t1.c11 from t7, t6, t5, t4, t3, t2, t1 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t3	index	PRIMARY	PRIMARY	4	NULL	9	Using index
@@ -319,7 +319,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	14.789792
+Last_query_cost	14.817907
 explain select t1.c11 from t1, t2, t3, t4, t5, t6, t7 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71 and t2.c22 = t3.c32 and t2.c23 = t4.c42 and t2.c24 = t5.c52 and t2.c25 = t6.c62 and t2.c26 = t7.c72 and t3.c33 = t4.c43 and t3.c34 = t5.c53 and t3.c35 = t6.c63 and t3.c36 = t7.c73 and t4.c42 = t5.c54 and t4.c43 = t6.c64 and t4.c44 = t7.c74 and t5.c52 = t6.c65 and t5.c53 = t7.c75 and t6.c62 = t7.c76;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ALL	PRIMARY	NULL	NULL	NULL	3	Using where
@@ -350,76 +350,76 @@ select @@optimizer_search_depth;
 62
 explain select t1.c11 from t1, t2, t3, t4, t5, t6, t7 where t1.c12 = t2.c21 and t2.c22 = t3.c31 and t3.c32 = t4.c41 and t4.c42 = t5.c51 and t5.c52 = t6.c61 and t6.c62 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
+1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t2.c22	1	
 1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t4.c42	1	
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
-1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t2.c22	1	Using where
-1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t4.c42	1	Using where
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t6.c62	1	Using index
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	1.405838
+Last_query_cost	2.998640
 explain select t1.c11 from t7, t6, t5, t4, t3, t2, t1 where t1.c12 = t2.c21 and t2.c22 = t3.c31 and t3.c32 = t4.c41 and t4.c42 = t5.c51 and t5.c52 = t6.c61 and t6.c62 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
+1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t2.c22	1	
 1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t4.c42	1	
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t6.c62	1	Using index
-1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t4.c42	1	Using where
-1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t2.c22	1	Using where
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	1.405838
+Last_query_cost	2.998640
 explain select t1.c11 from t1, t2, t3, t4, t5, t6, t7 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
-1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using join buffer (flat, BNL join)
-1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using join buffer (flat, BNL join)
 1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	4	test.t2.c21	1	Using where
 1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t1.c12	1	Using index
 1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t1.c14	1	Using index
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t1.c16	1	Using index
+1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	0.494824
+Last_query_cost	0.602062
 explain select t1.c11 from t7, t6, t5, t4, t3, t2, t1 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
-1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using join buffer (flat, BNL join)
-1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using join buffer (flat, BNL join)
 1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	4	test.t2.c21	1	Using where
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t1.c16	1	Using index
 1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t1.c14	1	Using index
 1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t1.c12	1	Using index
+1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	0.494824
+Last_query_cost	0.602062
 explain select t1.c11 from t1, t2, t3, t4, t5, t6, t7 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71 and t2.c22 = t3.c32 and t2.c23 = t4.c42 and t2.c24 = t5.c52 and t2.c25 = t6.c62 and t2.c26 = t7.c72 and t3.c33 = t4.c43 and t3.c34 = t5.c53 and t3.c35 = t6.c63 and t3.c36 = t7.c73 and t4.c42 = t5.c54 and t4.c43 = t6.c64 and t4.c44 = t7.c74 and t5.c52 = t6.c65 and t5.c53 = t7.c75 and t6.c62 = t7.c76;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
-1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
-1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	4	test.t2.c21	1	Using where
 1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t1.c12	1	Using where
 1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t1.c14	1	Using where
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t1.c16	1	Using where
+1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	0.453844
+Last_query_cost	0.621783
 explain select t1.c11 from t7, t6, t5, t4, t3, t2, t1 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71 and t2.c22 = t3.c32 and t2.c23 = t4.c42 and t2.c24 = t5.c52 and t2.c25 = t6.c62 and t2.c26 = t7.c72 and t3.c33 = t4.c43 and t3.c34 = t5.c53 and t3.c35 = t6.c63 and t3.c36 = t7.c73 and t4.c42 = t5.c54 and t4.c43 = t6.c64 and t4.c44 = t7.c74 and t5.c52 = t6.c65 and t5.c53 = t7.c75 and t6.c62 = t7.c76;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
-1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
-1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	4	test.t2.c21	1	Using where
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t1.c16	1	Using where
 1	SIMPLE	t5	eq_ref	PRIMARY	PRIMARY	4	test.t1.c14	1	Using where
 1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	4	test.t1.c12	1	Using where
+1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	0.453844
+Last_query_cost	0.621783
 set optimizer_prune_level=2;
 select @@optimizer_prune_level;
 @@optimizer_prune_level
@@ -439,7 +439,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t6.c62	1	Using index
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	1.650935
+Last_query_cost	4.284314
 explain select t1.c11 from t7, t6, t5, t4, t3, t2, t1 where t1.c12 = t2.c21 and t2.c22 = t3.c31 and t3.c32 = t4.c41 and t4.c42 = t5.c51 and t5.c52 = t6.c61 and t6.c62 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	
@@ -451,7 +451,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t6.c62	1	Using index
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	1.650935
+Last_query_cost	4.284314
 explain select t1.c11 from t1, t2, t3, t4, t5, t6, t7 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
@@ -515,7 +515,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	34.291074
+Last_query_cost	42.599713
 explain select t1.c11 from t7, t6, t5, t4, t3, t2, t1 where t1.c12 = t2.c21 and t2.c22 = t3.c31 and t3.c32 = t4.c41 and t4.c42 = t5.c51 and t5.c52 = t6.c61 and t6.c62 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t7	index	PRIMARY	PRIMARY	4	NULL	21	Using index
@@ -527,7 +527,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	34.291074
+Last_query_cost	42.599713
 explain select t1.c11 from t1, t2, t3, t4, t5, t6, t7 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t3	index	PRIMARY	PRIMARY	4	NULL	9	Using index
@@ -539,7 +539,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	14.789792
+Last_query_cost	14.817907
 explain select t1.c11 from t7, t6, t5, t4, t3, t2, t1 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t3	index	PRIMARY	PRIMARY	4	NULL	9	Using index
@@ -551,7 +551,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	18	Using where; Using join buffer (flat, BNL join)
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	14.789792
+Last_query_cost	14.817907
 explain select t1.c11 from t1, t2, t3, t4, t5, t6, t7 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71 and t2.c22 = t3.c32 and t2.c23 = t4.c42 and t2.c24 = t5.c52 and t2.c25 = t6.c62 and t2.c26 = t7.c72 and t3.c33 = t4.c43 and t3.c34 = t5.c53 and t3.c35 = t6.c63 and t3.c36 = t7.c73 and t4.c42 = t5.c54 and t4.c43 = t6.c64 and t4.c44 = t7.c74 and t5.c52 = t6.c65 and t5.c53 = t7.c75 and t6.c62 = t7.c76;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ALL	PRIMARY	NULL	NULL	NULL	3	Using where
@@ -591,7 +591,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t6.c62	1	Using index
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	1.650935
+Last_query_cost	4.284314
 explain select t1.c11 from t7, t6, t5, t4, t3, t2, t1 where t1.c12 = t2.c21 and t2.c22 = t3.c31 and t3.c32 = t4.c41 and t4.c42 = t5.c51 and t5.c52 = t6.c61 and t6.c62 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	
@@ -603,7 +603,7 @@ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t7	eq_ref	PRIMARY	PRIMARY	4	test.t6.c62	1	Using index
 show status like 'Last_query_cost';
 Variable_name	Value
-Last_query_cost	1.650935
+Last_query_cost	4.284314
 explain select t1.c11 from t1, t2, t3, t4, t5, t6, t7 where t1.c11 = t2.c21 and t1.c12 = t3.c31 and t1.c13 = t4.c41 and t1.c14 = t5.c51 and t1.c15 = t6.c61 and t1.c16 = t7.c71;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
@@ -1194,14 +1194,17 @@ AND t10000.I=t10.I;
 COUNT(*)
 9000
 ### NOTE: Handler_reads: 9030, expected: 9045 ###
+#####
+## EQ_REF & REF join two instances of t10000 with t10:
+#####
 flush status;
-EXPLAIN SELECT STRAIGHT_JOIN COUNT(*) FROM t10000 y, t10, t10000 x
+EXPLAIN SELECT STRAIGHT_JOIN COUNT(*) FROM t10,t10000 x,t10000 y
 WHERE x.k=t10.i;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	y	index	NULL	PRIMARY	4	NULL	10000	Using index
-1	SIMPLE	t10	range	IX	IX	5	NULL	10	Using where; Using index; Using join buffer (flat, BNL join)
+1	SIMPLE	t10	index	IX	IX	5	NULL	10	Using where; Using index
 1	SIMPLE	x	eq_ref	PRIMARY	PRIMARY	4	test.t10.I	1	Using index
-SELECT STRAIGHT_JOIN COUNT(*) FROM t10000 y, t10, t10000 x
+1	SIMPLE	y	index	NULL	PRIMARY	4	NULL	10000	Using index; Using join buffer (flat, BNL join)
+SELECT STRAIGHT_JOIN COUNT(*) FROM t10,t10000 x,t10000 y
 WHERE x.k=t10.i;
 COUNT(*)
 90000
@@ -1209,9 +1212,9 @@ flush status;
 EXPLAIN SELECT COUNT(*) FROM t10,t10000 x,t10000 y
 WHERE x.k=t10.i;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	y	index	NULL	PRIMARY	4	NULL	10000	Using index
-1	SIMPLE	t10	range	IX	IX	5	NULL	10	Using where; Using index; Using join buffer (flat, BNL join)
+1	SIMPLE	t10	index	IX	IX	5	NULL	10	Using where; Using index
 1	SIMPLE	x	eq_ref	PRIMARY	PRIMARY	4	test.t10.I	1	Using index
+1	SIMPLE	y	index	NULL	PRIMARY	4	NULL	10000	Using index; Using join buffer (flat, BNL join)
 SELECT COUNT(*) FROM t10,t10000 x,t10000 y
 WHERE x.k=t10.i;
 COUNT(*)
@@ -1220,9 +1223,9 @@ flush status;
 EXPLAIN SELECT COUNT(*) FROM t10,t10000 y,t10000 x
 WHERE x.k=t10.i;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	y	index	NULL	PRIMARY	4	NULL	10000	Using index
-1	SIMPLE	t10	range	IX	IX	5	NULL	10	Using where; Using index; Using join buffer (flat, BNL join)
+1	SIMPLE	t10	index	IX	IX	5	NULL	10	Using where; Using index
 1	SIMPLE	x	eq_ref	PRIMARY	PRIMARY	4	test.t10.I	1	Using index
+1	SIMPLE	y	index	NULL	PRIMARY	4	NULL	10000	Using index; Using join buffer (flat, BNL join)
 SELECT COUNT(*) FROM t10,t10000 y,t10000 x
 WHERE x.k=t10.i;
 COUNT(*)
diff --git a/mysql-test/main/greedy_optimizer.test b/mysql-test/main/greedy_optimizer.test
index 04f765e815a..8e90a91d7fa 100644
--- a/mysql-test/main/greedy_optimizer.test
+++ b/mysql-test/main/greedy_optimizer.test
@@ -654,15 +654,15 @@ WHERE t100.K=t10.I
 --source include/check_qep.inc
 
 
-#####
-## EQ_REF & REF join two instances of t10000 with t10:
-#####
+--echo #####
+--echo ## EQ_REF & REF join two instances of t10000 with t10:
+--echo #####
 
 #####
 ## Expect this QEP, cost & #handler_read
 # Expected QEP: 'join EQ_REF(X) on X.K=t10.I' before 'cross' ALL(Y)
 let $query=
-SELECT STRAIGHT_JOIN COUNT(*) FROM t10000 y, t10, t10000 x
+SELECT STRAIGHT_JOIN COUNT(*) FROM t10,t10000 x,t10000 y
 WHERE x.k=t10.i;
 --source include/expect_qep.inc
 
diff --git a/mysql-test/main/join_cache.result b/mysql-test/main/join_cache.result
index eddae76a724..c02ac192dde 100644
--- a/mysql-test/main/join_cache.result
+++ b/mysql-test/main/join_cache.result
@@ -4398,9 +4398,9 @@ SELECT t2.v FROM t1, t2, t3
 WHERE t3.v <> t2.v AND t3.pk = t2.i AND t1.v = t3.v AND t1.pk*2<100 
 GROUP BY t2.v ORDER BY t1.pk,t2.v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	idx2	NULL	NULL	NULL	44	Using where; Using temporary; Using filesort
-1	SIMPLE	t2	index	idx1	idx2	7	NULL	20	Using where; Using index; Using join buffer (flat, BNL join)
+1	SIMPLE	t2	index	idx1	idx2	7	NULL	20	Using index; Using temporary; Using filesort
 1	SIMPLE	t3	eq_ref	PRIMARY,idx2	PRIMARY	4	test.t2.i	1	Using where
+1	SIMPLE	t1	ref	idx2	idx2	3	test.t3.v	5	Using where
 SELECT t2.v FROM t1, t2, t3
 WHERE t3.v <> t2.v AND t3.pk = t2.i AND t1.v = t3.v AND t1.pk*2<100 
 GROUP BY t2.v ORDER BY t1.pk,t2.v;
@@ -4415,9 +4415,9 @@ SELECT t2.v FROM t1, t2, t3
 WHERE t2.v <> t3.v AND t3.pk = t2.i AND t1.v = t3.v AND t1.pk*2<100
 GROUP BY t2.v ORDER BY t1.pk,t2.v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	idx2	NULL	NULL	NULL	44	Using where; Using temporary; Using filesort
-1	SIMPLE	t2	index	idx1	idx2	7	NULL	20	Using where; Using index; Using join buffer (flat, BNL join)
+1	SIMPLE	t2	index	idx1	idx2	7	NULL	20	Using index; Using temporary; Using filesort
 1	SIMPLE	t3	eq_ref	PRIMARY,idx2	PRIMARY	4	test.t2.i	1	Using where
+1	SIMPLE	t1	ref	idx2	idx2	3	test.t3.v	5	Using where
 SELECT t2.v FROM t1, t2, t3
 WHERE t2.v <> t3.v AND t3.pk = t2.i AND t1.v = t3.v AND t1.pk*2<100
 GROUP BY t2.v ORDER BY t1.pk,t2.v;
@@ -4433,9 +4433,9 @@ SELECT t2.v FROM t1, t2, t3
 WHERE t3.v <> t2.v AND t3.pk = t2.i AND t1.v = t3.v AND t1.pk*2<100 
 GROUP BY t2.v ORDER BY t1.pk,t2.v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	idx2	NULL	NULL	NULL	44	Using where; Using temporary; Using filesort
-1	SIMPLE	t2	index	idx1	idx2	7	NULL	20	Using where; Using index; Using join buffer (flat, BNL join)
-1	SIMPLE	t3	eq_ref	PRIMARY,idx2	PRIMARY	4	test.t2.i	1	Using where; Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
+1	SIMPLE	t2	index	idx1	idx2	7	NULL	20	Using index; Using temporary; Using filesort
+1	SIMPLE	t3	eq_ref	PRIMARY,idx2	PRIMARY	4	test.t2.i	1	Using where; Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
+1	SIMPLE	t1	ref	idx2	idx2	3	test.t3.v	5	Using where; Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
 SELECT t2.v FROM t1, t2, t3 
 WHERE t3.v <> t2.v AND t3.pk = t2.i AND t1.v = t3.v AND t1.pk*2<100 
 GROUP BY t2.v ORDER BY t1.pk,t2.v;
@@ -4450,9 +4450,9 @@ SELECT t2.v FROM t1, t2, t3
 WHERE t2.v <> t3.v AND t3.pk = t2.i AND t1.v = t3.v AND t1.pk*2<100
 GROUP BY t2.v ORDER BY t1.pk,t2.v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	idx2	NULL	NULL	NULL	44	Using where; Using temporary; Using filesort
-1	SIMPLE	t2	index	idx1	idx2	7	NULL	20	Using where; Using index; Using join buffer (flat, BNL join)
-1	SIMPLE	t3	eq_ref	PRIMARY,idx2	PRIMARY	4	test.t2.i	1	Using where; Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
+1	SIMPLE	t2	index	idx1	idx2	7	NULL	20	Using index; Using temporary; Using filesort
+1	SIMPLE	t3	eq_ref	PRIMARY,idx2	PRIMARY	4	test.t2.i	1	Using where; Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan
+1	SIMPLE	t1	ref	idx2	idx2	3	test.t3.v	5	Using where; Using join buffer (incremental, BKA join); Key-ordered Rowid-ordered scan
 SELECT t2.v FROM t1, t2, t3
 WHERE t2.v <> t3.v AND t3.pk = t2.i AND t1.v = t3.v AND t1.pk*2<100
 GROUP BY t2.v ORDER BY t1.pk,t2.v;
@@ -4468,9 +4468,9 @@ SELECT t2.v FROM t1, t2, t3
 WHERE t3.v <> t2.v AND t3.pk = t2.i AND t1.v = t3.v AND t1.pk*2<100 
 GROUP BY t2.v ORDER BY t1.pk,t2.v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	idx2	NULL	NULL	NULL	44	Using where; Using temporary; Using filesort
-1	SIMPLE	t2	index	idx1	idx2	7	NULL	20	Using where; Using index; Using join buffer (flat, BNL join)
-1	SIMPLE	t3	hash_ALL	PRIMARY,idx2	#hash#PRIMARY	4	test.t2.i	20	Using where; Using join buffer (incremental, BNLH join)
+1	SIMPLE	t2	index	idx1	idx2	7	NULL	20	Using index; Using temporary; Using filesort
+1	SIMPLE	t3	hash_ALL	PRIMARY,idx2	#hash#PRIMARY	4	test.t2.i	20	Using where; Using join buffer (flat, BNLH join)
+1	SIMPLE	t1	hash_ALL	idx2	#hash#idx2	3	test.t3.v	44	Using where; Using join buffer (incremental, BNLH join)
 SELECT t2.v FROM t1, t2, t3
 WHERE t3.v <> t2.v AND t3.pk = t2.i AND t1.v = t3.v AND t1.pk*2<100 
 GROUP BY t2.v ORDER BY t1.pk,t2.v;
@@ -4485,9 +4485,9 @@ SELECT t2.v FROM t1, t2, t3
 WHERE t2.v <> t3.v AND t3.pk = t2.i AND t1.v = t3.v AND t1.pk*2<100
 GROUP BY t2.v ORDER BY t1.pk,t2.v;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	idx2	NULL	NULL	NULL	44	Using where; Using temporary; Using filesort
-1	SIMPLE	t2	index	idx1	idx2	7	NULL	20	Using where; Using index; Using join buffer (flat, BNL join)
-1	SIMPLE	t3	hash_ALL	PRIMARY,idx2	#hash#PRIMARY	4	test.t2.i	20	Using where; Using join buffer (incremental, BNLH join)
+1	SIMPLE	t2	index	idx1	idx2	7	NULL	20	Using index; Using temporary; Using filesort
+1	SIMPLE	t3	hash_ALL	PRIMARY,idx2	#hash#PRIMARY	4	test.t2.i	20	Using where; Using join buffer (flat, BNLH join)
+1	SIMPLE	t1	hash_ALL	idx2	#hash#idx2	3	test.t3.v	44	Using where; Using join buffer (incremental, BNLH join)
 SELECT t2.v FROM t1, t2, t3
 WHERE t2.v <> t3.v AND t3.pk = t2.i AND t1.v = t3.v AND t1.pk*2<100
 GROUP BY t2.v ORDER BY t1.pk,t2.v;
diff --git a/mysql-test/main/opt_trace.result b/mysql-test/main/opt_trace.result
index b28c342fd96..cb08c4150d8 100644
--- a/mysql-test/main/opt_trace.result
+++ b/mysql-test/main/opt_trace.result
@@ -11181,9 +11181,9 @@ insert into t3 values (1),(2),(3),(4),(5),(6),(7),(8),(9),(10);
 explain 
 select * from t3 where (a,a) in (select t1.a, t2.a from t1, t2 where t1.b=t2.b);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	10	Using where
-1	PRIMARY	t1	ALL	PRIMARY	NULL	NULL	NULL	5	Using where; Using join buffer (flat, BNL join)
-1	PRIMARY	t2	eq_ref	PRIMARY	PRIMARY	4	test.t3.a	1	Using where
+1	PRIMARY	t1	ALL	PRIMARY	NULL	NULL	NULL	5	
+1	PRIMARY	t2	eq_ref	PRIMARY	PRIMARY	4	test.t1.a	1	Using where
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	10	Using where; Using join buffer (flat, BNL join)
 select JSON_DETAILED(JSON_EXTRACT(trace, '$**.semijoin_table_pullout')) from INFORMATION_SCHEMA.OPTIMIZER_TRACE;
 JSON_DETAILED(JSON_EXTRACT(trace, '$**.semijoin_table_pullout'))
 [
diff --git a/mysql-test/main/show_explain.result b/mysql-test/main/show_explain.result
index 20333c925d4..ce335819324 100644
--- a/mysql-test/main/show_explain.result
+++ b/mysql-test/main/show_explain.result
@@ -730,8 +730,8 @@ SELECT * FROM t2 WHERE (5, 78) IN (SELECT `a1`, MAX(`a1`) FROM t2 GROUP BY `a1`)
 connection default;
 show explain for $thr2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	20	
 1	PRIMARY	<subquery2>	const	distinct_key	distinct_key	8	const,const	1	
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	20	Using join buffer (flat, BNL join)
 2	MATERIALIZED	t2	index	NULL	a1	4	NULL	20	Using index
 Warnings:
 Note	1003	SELECT * FROM t2 WHERE (5, 78) IN (SELECT `a1`, MAX(`a1`) FROM t2 GROUP BY `a1`)
diff --git a/mysql-test/main/stat_tables.result b/mysql-test/main/stat_tables.result
index 414497d5ad1..a6642d66fb7 100644
--- a/mysql-test/main/stat_tables.result
+++ b/mysql-test/main/stat_tables.result
@@ -251,11 +251,11 @@ and p_name like '%green%') as profit
 group by nation, o_year
 order by nation, o_year desc;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	part	ALL	PRIMARY	NULL	NULL	NULL	200	Using where; Using temporary; Using filesort
-1	SIMPLE	partsupp	ref	PRIMARY,i_ps_partkey,i_ps_suppkey	i_ps_partkey	4	dbt3_s001.part.p_partkey	3	
-1	SIMPLE	supplier	ALL	PRIMARY,i_s_nationkey	NULL	NULL	NULL	10	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	supplier	ALL	PRIMARY,i_s_nationkey	NULL	NULL	NULL	10	Using where; Using temporary; Using filesort
 1	SIMPLE	nation	eq_ref	PRIMARY	PRIMARY	4	dbt3_s001.supplier.s_nationkey	1	
-1	SIMPLE	lineitem	ref	PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity	i_l_suppkey_partkey	10	dbt3_s001.part.p_partkey,dbt3_s001.partsupp.ps_suppkey	8	
+1	SIMPLE	partsupp	ref	PRIMARY,i_ps_partkey,i_ps_suppkey	i_ps_suppkey	4	dbt3_s001.supplier.s_suppkey	70	
+1	SIMPLE	part	eq_ref	PRIMARY	PRIMARY	4	dbt3_s001.partsupp.ps_partkey	1	Using where
+1	SIMPLE	lineitem	ref	PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity	i_l_suppkey_partkey	10	dbt3_s001.partsupp.ps_partkey,dbt3_s001.supplier.s_suppkey	8	
 1	SIMPLE	orders	eq_ref	PRIMARY	PRIMARY	4	dbt3_s001.lineitem.l_orderkey	1	
 EXPLAIN EXTENDED select nation, o_year, sum(amount) as sum_profit
 from (select n_name as nation, 
@@ -269,14 +269,14 @@ and p_name like '%green%') as profit
 group by nation, o_year
 order by nation, o_year desc;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	SIMPLE	part	ALL	PRIMARY	NULL	NULL	NULL	200	100.00	Using where; Using temporary; Using filesort
-1	SIMPLE	partsupp	ref	PRIMARY,i_ps_partkey,i_ps_suppkey	i_ps_partkey	4	dbt3_s001.part.p_partkey	3	100.00	
-1	SIMPLE	supplier	ALL	PRIMARY,i_s_nationkey	NULL	NULL	NULL	10	10.00	Using where; Using join buffer (flat, BNL join)
+1	SIMPLE	supplier	ALL	PRIMARY,i_s_nationkey	NULL	NULL	NULL	10	100.00	Using where; Using temporary; Using filesort
 1	SIMPLE	nation	eq_ref	PRIMARY	PRIMARY	4	dbt3_s001.supplier.s_nationkey	1	100.00	
-1	SIMPLE	lineitem	ref	PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity	i_l_suppkey_partkey	10	dbt3_s001.part.p_partkey,dbt3_s001.partsupp.ps_suppkey	8	100.00	
+1	SIMPLE	partsupp	ref	PRIMARY,i_ps_partkey,i_ps_suppkey	i_ps_suppkey	4	dbt3_s001.supplier.s_suppkey	70	100.00	
+1	SIMPLE	part	eq_ref	PRIMARY	PRIMARY	4	dbt3_s001.partsupp.ps_partkey	1	100.00	Using where
+1	SIMPLE	lineitem	ref	PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity	i_l_suppkey_partkey	10	dbt3_s001.partsupp.ps_partkey,dbt3_s001.supplier.s_suppkey	8	100.00	
 1	SIMPLE	orders	eq_ref	PRIMARY	PRIMARY	4	dbt3_s001.lineitem.l_orderkey	1	100.00	
 Warnings:
-Note	1003	select `dbt3_s001`.`nation`.`n_name` AS `nation`,extract(year from `dbt3_s001`.`orders`.`o_orderDATE`) AS `o_year`,sum(`dbt3_s001`.`lineitem`.`l_extendedprice` * (1 - `dbt3_s001`.`lineitem`.`l_discount`) - `dbt3_s001`.`partsupp`.`ps_supplycost` * `dbt3_s001`.`lineitem`.`l_quantity`) AS `sum_profit` from `dbt3_s001`.`part` join `dbt3_s001`.`supplier` join `dbt3_s001`.`lineitem` join `dbt3_s001`.`partsupp` join `dbt3_s001`.`orders` join `dbt3_s001`.`nation` where `dbt3_s001`.`supplier`.`s_suppkey` = `dbt3_s001`.`partsupp`.`ps_suppkey` and `dbt3_s001`.`lineitem`.`l_suppkey` = `dbt3_s001`.`partsupp`.`ps_suppkey` and `dbt3_s001`.`partsupp`.`ps_partkey` = `dbt3_s001`.`part`.`p_partkey` and `dbt3_s001`.`lineitem`.`l_partkey` = `dbt3_s001`.`part`.`p_partkey` and `dbt3_s001`.`orders`.`o_orderkey` = `dbt3_s001`.`lineitem`.`l_orderkey` and `dbt3_s001`.`nation`.`n_nationkey` = `dbt3_s001`.`supplier`.`s_nationkey` and `dbt3_s001`.`part`.`p_name` like '%green%' group by `dbt3_s001`.`nation`.`n_name`,extract(year from `dbt3_s001`.`orders`.`o_orderDATE`) desc order by `dbt3_s001`.`nation`.`n_name`,extract(year from `dbt3_s001`.`orders`.`o_orderDATE`) desc
+Note	1003	select `dbt3_s001`.`nation`.`n_name` AS `nation`,extract(year from `dbt3_s001`.`orders`.`o_orderDATE`) AS `o_year`,sum(`dbt3_s001`.`lineitem`.`l_extendedprice` * (1 - `dbt3_s001`.`lineitem`.`l_discount`) - `dbt3_s001`.`partsupp`.`ps_supplycost` * `dbt3_s001`.`lineitem`.`l_quantity`) AS `sum_profit` from `dbt3_s001`.`part` join `dbt3_s001`.`supplier` join `dbt3_s001`.`lineitem` join `dbt3_s001`.`partsupp` join `dbt3_s001`.`orders` join `dbt3_s001`.`nation` where `dbt3_s001`.`partsupp`.`ps_suppkey` = `dbt3_s001`.`supplier`.`s_suppkey` and `dbt3_s001`.`lineitem`.`l_suppkey` = `dbt3_s001`.`supplier`.`s_suppkey` and `dbt3_s001`.`part`.`p_partkey` = `dbt3_s001`.`partsupp`.`ps_partkey` and `dbt3_s001`.`lineitem`.`l_partkey` = `dbt3_s001`.`partsupp`.`ps_partkey` and `dbt3_s001`.`orders`.`o_orderkey` = `dbt3_s001`.`lineitem`.`l_orderkey` and `dbt3_s001`.`nation`.`n_nationkey` = `dbt3_s001`.`supplier`.`s_nationkey` and `dbt3_s001`.`part`.`p_name` like '%green%' group by `dbt3_s001`.`nation`.`n_name`,extract(year from `dbt3_s001`.`orders`.`o_orderDATE`) desc order by `dbt3_s001`.`nation`.`n_name`,extract(year from `dbt3_s001`.`orders`.`o_orderDATE`) desc
 select nation, o_year, sum(amount) as sum_profit
 from (select n_name as nation, 
 extract(year from o_orderdate) as o_year,
diff --git a/mysql-test/main/subselect2.result b/mysql-test/main/subselect2.result
index e62f0617574..0d2f7372887 100644
--- a/mysql-test/main/subselect2.result
+++ b/mysql-test/main/subselect2.result
@@ -125,8 +125,8 @@ DOCID	DOCNAME	DOCTYPEID	FOLDERID	AUTHOR	CREATED	TITLE	SUBTITLE	DOCABSTRACT	PUBLI
 c373e9f5ad07993f3859444553544200	Last Discussion	c373e9f5ad079174ff17444553544200	c373e9f5ad0796c0eca4444553544200	Goldilocks	2003-06-09 11:21:06	Title: Last Discussion	NULL	Setting new abstract and keeping doc checked out	2003-06-09 10:51:26	2003-06-09 10:51:26	NULL	NULL	NULL	03eea05112b845949f3fd03278b5fe43	2003-06-09 11:21:06	admin	0	NULL	Discussion	NULL	NULL
 EXPLAIN SELECT t2.*, t4.DOCTYPENAME, t1.CONTENTSIZE,t1.MIMETYPE FROM t2 INNER JOIN t4 ON t2.DOCTYPEID = t4.DOCTYPEID LEFT OUTER JOIN t1 ON t2.DOCID = t1.DOCID WHERE t2.FOLDERID IN(SELECT t3_a.FOLDERID FROM t3 as t3_a WHERE t3_a.PARENTID IN(SELECT t3_b.FOLDERID FROM t3 as t3_b WHERE t3_b.PARENTID IN(SELECT t3_c.FOLDERID FROM t3 as t3_c WHERE t3_c.PARENTID IN(SELECT t3_d.FOLDERID FROM t3 as t3_d WHERE t3_d.PARENTID IN(SELECT t3_e.FOLDERID FROM t3 as t3_e WHERE t3_e.PARENTID='2f6161e879db43c1a5b82c21ddc49089' AND t3_e.FOLDERNAME = 'Level1') AND t3_d.FOLDERNAME = 'Level2') AND t3_c.FOLDERNAME = 'Level3') AND t3_b.FOLDERNAME = 'CopiedFolder') AND t3_a.FOLDERNAME = 'Movie Reviews') AND t2.DOCNAME = 'Last Discussion';
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t4	ALL	PRIMARY	NULL	NULL	NULL	10	
-1	PRIMARY	t2	ALL	DDOCTYPEID_IDX,DFOLDERID_IDX	NULL	NULL	NULL	9	Using where; Using join buffer (flat, BNL join)
+1	PRIMARY	t2	ALL	DDOCTYPEID_IDX,DFOLDERID_IDX	NULL	NULL	NULL	9	Using where
+1	PRIMARY	t4	eq_ref	PRIMARY	PRIMARY	34	test.t2.DOCTYPEID	1	
 1	PRIMARY	t1	eq_ref	PRIMARY	PRIMARY	34	test.t2.DOCID	1	
 1	PRIMARY	t3_a	eq_ref	PRIMARY,FFOLDERID_IDX,CMFLDRPARNT_IDX	PRIMARY	34	test.t2.FOLDERID	1	Using where
 1	PRIMARY	t3_b	eq_ref	PRIMARY,FFOLDERID_IDX,CMFLDRPARNT_IDX	PRIMARY	34	test.t3_a.PARENTID	1	Using where
diff --git a/mysql-test/main/subselect_mat.result b/mysql-test/main/subselect_mat.result
index 3d7f6d601b6..038acfbb1cb 100644
--- a/mysql-test/main/subselect_mat.result
+++ b/mysql-test/main/subselect_mat.result
@@ -1959,11 +1959,11 @@ EXPLAIN EXTENDED
 SELECT * FROM t1
 WHERE a IN (SELECT MAX(c) FROM t2) AND b=7 AND (a IS NULL OR a=b);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where
-1	PRIMARY	<subquery2>	const	distinct_key	distinct_key	4	const	1	100.00	Using where
+1	PRIMARY	<subquery2>	const	distinct_key	distinct_key	4	const	1	100.00	
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (flat, BNL join)
 2	MATERIALIZED	t2	ALL	NULL	NULL	NULL	NULL	3	100.00	
 Warnings:
-Note	1003	/* select#1 */ select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from  <materialize> (/* select#2 */ select max(`test`.`t2`.`c`) from `test`.`t2` having `MAX(c)` is null or `MAX(c)` = 7) join `test`.`t1` where `test`.`t1`.`b` = 7 and `<subquery2>`.`MAX(c)` = `test`.`t1`.`a` and (`test`.`t1`.`a` is null or `test`.`t1`.`a` = 7)
+Note	1003	/* select#1 */ select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from  <materialize> (/* select#2 */ select max(`test`.`t2`.`c`) from `test`.`t2` having `MAX(c)` is null or `MAX(c)` = 7) join `test`.`t1` where `test`.`t1`.`b` = 7 and `test`.`t1`.`a` = `<subquery2>`.`MAX(c)` and (<cache>(/*always not null*/ 1 is null) or `<subquery2>`.`MAX(c)` = 7)
 SELECT * FROM t1
 WHERE a IN (SELECT MAX(c) FROM t2) AND b=7 AND (a IS NULL OR a=b);
 a	b
@@ -1972,8 +1972,8 @@ EXPLAIN
 SELECT * FROM t1
 WHERE a IN (SELECT MAX(c) FROM t2 WHERE c < 4) AND b=7 AND (a IS NULL OR a=b);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where
-1	PRIMARY	<subquery2>	const	distinct_key	distinct_key	4	const	1	Using where
+1	PRIMARY	<subquery2>	const	distinct_key	distinct_key	4	const	1	
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; Using join buffer (flat, BNL join)
 2	MATERIALIZED	t2	ALL	NULL	NULL	NULL	NULL	3	Using where
 SELECT * FROM t1
 WHERE a IN (SELECT MAX(c) FROM t2 WHERE c < 4) AND b=7 AND (a IS NULL OR a=b);
diff --git a/mysql-test/main/subselect_sj.result b/mysql-test/main/subselect_sj.result
index a33fb8cea6e..054c71351d0 100644
--- a/mysql-test/main/subselect_sj.result
+++ b/mysql-test/main/subselect_sj.result
@@ -806,7 +806,7 @@ insert into t2 (pk) values (-1),(0);
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (a, b) IN (SELECT a, b FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`a` = `test`.`t1`.`a` and `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (a, b) IN (SELECT a, b FROM t2 WHERE pk > 0);
@@ -815,7 +815,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, c) IN (SELECT b, c FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`c` = `test`.`t1`.`c` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, c) IN (SELECT b, c FROM t2 WHERE pk > 0);
@@ -825,7 +825,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, d) IN (SELECT b, d FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`d` = `test`.`t1`.`d` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, d) IN (SELECT b, d FROM t2 WHERE pk > 0);
@@ -834,7 +834,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, e) IN (SELECT b, e FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`e` = `test`.`t1`.`e` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, e) IN (SELECT b, e FROM t2 WHERE pk > 0);
@@ -844,7 +844,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, f) IN (SELECT b, f FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`f` = `test`.`t1`.`f` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, f) IN (SELECT b, f FROM t2 WHERE pk > 0);
@@ -854,7 +854,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, g) IN (SELECT b, g FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`g` = `test`.`t1`.`g` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, g) IN (SELECT b, g FROM t2 WHERE pk > 0);
@@ -864,7 +864,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, h) IN (SELECT b, h FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`h` = `test`.`t1`.`h` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, h) IN (SELECT b, h FROM t2 WHERE pk > 0);
@@ -874,7 +874,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, i) IN (SELECT b, i FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`i` = `test`.`t1`.`i` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, i) IN (SELECT b, i FROM t2 WHERE pk > 0);
@@ -884,7 +884,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, j) IN (SELECT b, j FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`j` = `test`.`t1`.`j` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, j) IN (SELECT b, j FROM t2 WHERE pk > 0);
@@ -894,7 +894,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, k) IN (SELECT b, k FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`k` = `test`.`t1`.`k` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, k) IN (SELECT b, k FROM t2 WHERE pk > 0);
diff --git a/mysql-test/main/subselect_sj_jcl6.result b/mysql-test/main/subselect_sj_jcl6.result
index 9028b1c8aac..8b1042142f8 100644
--- a/mysql-test/main/subselect_sj_jcl6.result
+++ b/mysql-test/main/subselect_sj_jcl6.result
@@ -817,7 +817,7 @@ insert into t2 (pk) values (-1),(0);
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (a, b) IN (SELECT a, b FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`a` = `test`.`t1`.`a` and `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (a, b) IN (SELECT a, b FROM t2 WHERE pk > 0);
@@ -826,7 +826,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, c) IN (SELECT b, c FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`c` = `test`.`t1`.`c` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, c) IN (SELECT b, c FROM t2 WHERE pk > 0);
@@ -836,7 +836,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, d) IN (SELECT b, d FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`d` = `test`.`t1`.`d` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, d) IN (SELECT b, d FROM t2 WHERE pk > 0);
@@ -845,7 +845,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, e) IN (SELECT b, e FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`e` = `test`.`t1`.`e` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, e) IN (SELECT b, e FROM t2 WHERE pk > 0);
@@ -855,7 +855,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, f) IN (SELECT b, f FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`f` = `test`.`t1`.`f` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, f) IN (SELECT b, f FROM t2 WHERE pk > 0);
@@ -865,7 +865,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, g) IN (SELECT b, g FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`g` = `test`.`t1`.`g` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, g) IN (SELECT b, g FROM t2 WHERE pk > 0);
@@ -875,7 +875,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, h) IN (SELECT b, h FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`h` = `test`.`t1`.`h` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, h) IN (SELECT b, h FROM t2 WHERE pk > 0);
@@ -885,7 +885,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, i) IN (SELECT b, i FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`i` = `test`.`t1`.`i` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, i) IN (SELECT b, i FROM t2 WHERE pk > 0);
@@ -895,7 +895,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, j) IN (SELECT b, j FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`j` = `test`.`t1`.`j` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, j) IN (SELECT b, j FROM t2 WHERE pk > 0);
@@ -905,7 +905,7 @@ pk
 EXPLAIN EXTENDED SELECT pk FROM t1 WHERE (b, k) IN (SELECT b, k FROM t2 WHERE pk > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	100.00	
-1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
+1	PRIMARY	t2	range	PRIMARY	PRIMARY	4	NULL	2	50.00	Using index condition; Using where; Rowid-ordered scan; FirstMatch(t1); Using join buffer (flat, BNL join)
 Warnings:
 Note	1003	select `test`.`t1`.`pk` AS `pk` from `test`.`t1` semi join (`test`.`t2`) where `test`.`t2`.`b` = `test`.`t1`.`b` and `test`.`t2`.`k` = `test`.`t1`.`k` and `test`.`t2`.`pk` > 0
 SELECT pk FROM t1 WHERE (b, k) IN (SELECT b, k FROM t2 WHERE pk > 0);
diff --git a/mysql-test/main/subselect_sj_mat.result b/mysql-test/main/subselect_sj_mat.result
index 7bec603abef..ec052d3cc4c 100644
--- a/mysql-test/main/subselect_sj_mat.result
+++ b/mysql-test/main/subselect_sj_mat.result
@@ -1985,11 +1985,11 @@ EXPLAIN EXTENDED
 SELECT * FROM t1
 WHERE a IN (SELECT MAX(c) FROM t2) AND b=7 AND (a IS NULL OR a=b);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where
-1	PRIMARY	<subquery2>	const	distinct_key	distinct_key	4	const	1	100.00	Using where
+1	PRIMARY	<subquery2>	const	distinct_key	distinct_key	4	const	1	100.00	
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (flat, BNL join)
 2	MATERIALIZED	t2	ALL	NULL	NULL	NULL	NULL	3	100.00	
 Warnings:
-Note	1003	/* select#1 */ select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from  <materialize> (/* select#2 */ select max(`test`.`t2`.`c`) from `test`.`t2` having `MAX(c)` is null or `MAX(c)` = 7) join `test`.`t1` where `test`.`t1`.`b` = 7 and `<subquery2>`.`MAX(c)` = `test`.`t1`.`a` and (`test`.`t1`.`a` is null or `test`.`t1`.`a` = 7)
+Note	1003	/* select#1 */ select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from  <materialize> (/* select#2 */ select max(`test`.`t2`.`c`) from `test`.`t2` having `MAX(c)` is null or `MAX(c)` = 7) join `test`.`t1` where `test`.`t1`.`b` = 7 and `test`.`t1`.`a` = `<subquery2>`.`MAX(c)` and (<cache>(/*always not null*/ 1 is null) or `<subquery2>`.`MAX(c)` = 7)
 SELECT * FROM t1
 WHERE a IN (SELECT MAX(c) FROM t2) AND b=7 AND (a IS NULL OR a=b);
 a	b
@@ -1998,8 +1998,8 @@ EXPLAIN
 SELECT * FROM t1
 WHERE a IN (SELECT MAX(c) FROM t2 WHERE c < 4) AND b=7 AND (a IS NULL OR a=b);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where
-1	PRIMARY	<subquery2>	const	distinct_key	distinct_key	4	const	1	Using where
+1	PRIMARY	<subquery2>	const	distinct_key	distinct_key	4	const	1	
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; Using join buffer (flat, BNL join)
 2	MATERIALIZED	t2	ALL	NULL	NULL	NULL	NULL	3	Using where
 SELECT * FROM t1
 WHERE a IN (SELECT MAX(c) FROM t2 WHERE c < 4) AND b=7 AND (a IS NULL OR a=b);
diff --git a/sql/rowid_filter.cc b/sql/rowid_filter.cc
index 2c257b11e47..47846fa82fd 100644
--- a/sql/rowid_filter.cc
+++ b/sql/rowid_filter.cc
@@ -472,8 +472,7 @@ void Range_rowid_filter_cost_info::trace_info(THD *thd)
   @param fetch_cost_factor  The cost of fetching 'records' rows
   @param index_only_cost    The cost of fetching 'records' rows with
                             index only reads
-  @param prev_records       How many row combinations we have in
-                            preceding tables
+  @param prev_records       How many index_read_calls() we expect to make
   @parma records_out        Will be updated to the minimum result rows for any
                             usable filter.
   @details
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 48b6f9e2dfc..571d87579bc 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -349,6 +349,9 @@ static void fix_items_after_optimize(THD *thd, SELECT_LEX *select_lex);
 static void optimize_rownum(THD *thd, SELECT_LEX_UNIT *unit, Item *cond);
 static bool process_direct_rownum_comparison(THD *thd, SELECT_LEX_UNIT *unit,
                                              Item *cond);
+static double prev_record_reads(const POSITION *positions, uint idx,
+                                table_map found_ref, double record_count,
+                                double *same_keys);
 
 #ifndef DBUG_OFF
 
@@ -8003,7 +8006,7 @@ apply_filter(THD *thd, TABLE *table, ALL_READ_COST *cost,
   /* We are going to read 'selectivity' fewer rows */
   adjusted_cost.row_cost.io*= selectivity;
   adjusted_cost.row_cost.cpu*= selectivity;
-  adjusted_cost.copy_cost*= selectivity;
+  adjusted_cost.copy_cost*= selectivity;        // Cost of copying row or key
   adjusted_cost.index_cost.cpu+= filter_lookup_cost;
 
   tmp= prev_records * WHERE_COST_THD(thd);
@@ -8085,15 +8088,18 @@ struct best_plan
   double records_read;                   // Records accessed
   double records_after_filter;           // Records_read + filter
   double records_out;                    // Smallest record count seen
+  double prev_record_reads;              // Save value from prev_record_reads
+  double identical_keys;                 // Save value from prev_record_reads
   Range_rowid_filter_cost_info *filter;  // Best filter
   KEYUSE *key;                           // Best key
   SplM_plan_info *spl_plan;
   table_map ref_depends_map;
+  ulonglong refills;                     // Join cache refills
   enum join_type type;
   uint forced_index;
   uint max_key_part;
   table_map found_ref;
-  bool uses_jbuf;
+  bool use_join_buffer;
 };
 
 
@@ -8145,6 +8151,7 @@ best_access_path(JOIN      *join,
   best.records_read= DBL_MAX;
   best.records_after_filter= DBL_MAX;
   best.records_out= table->stat_records() * table->cond_selectivity;
+  best.prev_record_reads= best.identical_keys= 0;
   best.filter= 0;
   best.key= 0;
   best.max_key_part= 0;
@@ -8152,7 +8159,8 @@ best_access_path(JOIN      *join,
   best.forced_index= MAX_KEY;
   best.found_ref= 0;
   best.ref_depends_map= 0;
-  best.uses_jbuf= FALSE;
+  best.refills= 0;
+  best.use_join_buffer= FALSE;
   best.spl_plan= 0;
 
   disable_jbuf= disable_jbuf || idx == join->const_tables;
@@ -8178,7 +8186,8 @@ best_access_path(JOIN      *join,
     KEYUSE *keyuse, *start_key= 0;
     uint max_key_part=0;
     enum join_type type= JT_UNKNOWN;
-    double cur_cost;
+    double cur_cost, copy_cost, cached_prev_record_reads= 0.0;
+    table_map cached_prev_ref= ~(table_map) 0;
 
     /* Test how we can use keys */
     rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE;  // Assumed records/key
@@ -8202,6 +8211,8 @@ best_access_path(JOIN      *join,
       double startup_cost= s->startup_cost;
       double records_after_filter, records_best_filter, records;
       Range_rowid_filter_cost_info *filter= 0;
+      double prev_record_count= record_count;
+      double identical_keys= 0;
 
       if (is_hash_join_key_no(key))
       {
@@ -8243,6 +8254,7 @@ best_access_path(JOIN      *join,
             If 1. expression does not refer to forward tables
                2. we won't get two ref-or-null's
           */
+          double ignore;
           all_parts|= keyuse->keypart_map;
           if (!(remaining_tables & keyuse->used_tables) &&
               (!keyuse->validity_ref || *keyuse->validity_ref) &&
@@ -8259,13 +8271,19 @@ best_access_path(JOIN      *join,
             if (!keyuse->val->maybe_null() || keyuse->null_rejecting)
               notnull_part|=keyuse->keypart_map;
 
-            double tmp2= prev_record_reads(join_positions, idx,
-                                           (found_ref | keyuse->used_tables));
-            if (tmp2 < best_prev_record_reads)
+            if ((found_ref | keyuse->used_tables) != cached_prev_ref)
             {
+              cached_prev_ref= (found_ref | keyuse->used_tables);
+              cached_prev_record_reads=
+                prev_record_reads(join_positions, idx,
+                                  cached_prev_ref, record_count,
+                                  &ignore);
+            }
+            if (cached_prev_record_reads < best_prev_record_reads)
+            {
+              best_prev_record_reads= cached_prev_record_reads;
               best_part_found_ref= (keyuse->used_tables &
                                     ~join->const_table_map);
-              best_prev_record_reads= tmp2;
             }
             if (rec > keyuse->ref_table_rows)
               rec= keyuse->ref_table_rows;
@@ -8363,7 +8381,6 @@ best_access_path(JOIN      *join,
               (!(key_flags & HA_NULL_PART_KEY) ||            //  (2)
                all_key_parts == notnull_part))               //  (3)
           {
-            double adjusted_cost;
             /* Check that eq_ref_tables are correctly updated */
             DBUG_ASSERT(join->eq_ref_tables & table->map);
             type= JT_EQ_REF;
@@ -8381,14 +8398,12 @@ best_access_path(JOIN      *join,
               tmp= cost_for_index_read(thd, table, key, 1, 1);
             }
             /*
-              Calculate an adjusted cost based on how many records are read
-              This will be multipled by record_count.
+              Calculate how many record read calls will be made taking
+              into account that we will cache the last read row.
             */
-            adjusted_cost= (prev_record_reads(join_positions, idx, found_ref) /
-                            record_count);
-            set_if_smaller(adjusted_cost, 1.0);
-            tmp.row_cost.cpu*=   adjusted_cost;
-            tmp.index_cost.cpu*= adjusted_cost;
+            prev_record_count= prev_record_reads(join_positions, idx,
+                                                 found_ref, record_count,
+                                                 &identical_keys);
             records= 1.0;
           }
           else
@@ -8751,22 +8766,34 @@ best_access_path(JOIN      *join,
                                                records,
                                                file->cost(&tmp),
                                                file->cost(tmp.index_cost),
-                                               record_count,
+                                               prev_record_count,
                                                &records_best_filter);
         set_if_smaller(best.records_out, records_best_filter);
         if (filter)
           filter= filter->apply_filter(thd, table, &tmp,
                                        &records_after_filter,
                                        &startup_cost,
-                                       1, record_count);
+                                       1, prev_record_count);
       }
 
-      tmp.copy_cost+= records_after_filter * WHERE_COST_THD(thd);
-      cur_cost= file->cost_for_reading_multiple_times(record_count, &tmp);
-      cur_cost= COST_ADD(cur_cost, startup_cost);
+      /*
+        Take into account WHERE and setup cost.
+        We have to check the WHERE for all previous row combinations
+        (record_count).
+        'prev_record_count' is either 'record_count', or in case of
+        EQ_REF the estimated number of index_read() calls to the
+        engine when taking the one row read cache into account.
+      */
+      copy_cost= (record_count * records_after_filter * WHERE_COST_THD(thd) +
+                  startup_cost);
+
+      cur_cost= (file->cost_for_reading_multiple_times(prev_record_count, &tmp) +
+                 copy_cost);
 
       if (unlikely(trace_access_idx.trace_started()))
       {
+        if (prev_record_count != record_count)
+          trace_access_idx.add("prev_record_count", prev_record_count);
         trace_access_idx.
           add("rows", records_after_filter).
           add("cost", cur_cost);
@@ -8796,6 +8823,8 @@ best_access_path(JOIN      *join,
         best.records_after_filter= ((use_cond_selectivity > 1) ?
                                     records_after_filter :
                                     records_best_filter);
+        best.prev_record_reads= prev_record_count;
+        best.identical_keys= identical_keys;
         best.key= start_key;
         best.found_ref= found_ref;
         best.max_key_part= max_key_part;
@@ -8908,9 +8937,10 @@ best_access_path(JOIN      *join,
     best.records= rnd_records;
     best.key= hj_start_key;
     best.ref_depends_map= 0;
-    best.uses_jbuf= TRUE;
+    best.use_join_buffer= TRUE;
     best.filter= 0;
     best.type= JT_HASH;
+    best.refills= (ulonglong) ceil(refills);
     Json_writer_object trace_access_hash(thd);
     if (unlikely(trace_access_hash.trace_started()))
       trace_access_hash.
@@ -8977,7 +9007,8 @@ best_access_path(JOIN      *join,
     const char *scan_type= "";
     enum join_type type;
     uint forced_index= MAX_KEY;
-    bool force_plan= 0;
+    bool force_plan= 0, use_join_buffer= 0;
+    ulonglong refills= 1;
 
     /*
       Range optimizer never proposes a RANGE if it isn't better
@@ -9150,7 +9181,7 @@ best_access_path(JOIN      *join,
         s->cached_forced_index= forced_index;
       }
 
-      if ((table->map & join->outer_join) || disable_jbuf)
+      if (disable_jbuf || (table->map & join->outer_join))
       {
         /*
           Simple scan
@@ -9169,7 +9200,7 @@ best_access_path(JOIN      *join,
       else
       {
         /* Scan trough join cache */
-        double cmp_time, row_copy_cost, refills;
+        double cmp_time, row_copy_cost, tmp_refills;
 
         /*
           Note that the cost of checking all rows against the table specific
@@ -9178,10 +9209,11 @@ best_access_path(JOIN      *join,
         scan_type= "scan_with_join_cache";
 
         /* Calculate cost of refills */
-        refills= (1.0 + floor((double) cache_record_length(join,idx) *
-                              (record_count /
-                               (double) thd->variables.join_buff_size)));
-        cur_cost= COST_MULT(cur_cost, refills);
+        tmp_refills= (1.0 + floor((double) cache_record_length(join,idx) *
+                                  (record_count /
+                                   (double) thd->variables.join_buff_size)));
+        cur_cost= COST_MULT(cur_cost, tmp_refills);
+        refills= (ulonglong) tmp_refills;
 
         /* We come here only if there are already rows in the join cache */
         DBUG_ASSERT(idx != join->const_tables);
@@ -9201,6 +9233,7 @@ best_access_path(JOIN      *join,
                    ((idx - join->const_tables) * row_copy_cost +
                     WHERE_COST_THD(thd)));
         cur_cost= COST_ADD(cur_cost, cmp_time);
+        use_join_buffer= 1;
       }
     }
 
@@ -9259,8 +9292,8 @@ best_access_path(JOIN      *join,
       best.filter= filter;
       /* range/index_merge/ALL/index access method are "independent", so: */
       best.ref_depends_map= 0;
-      best.uses_jbuf= MY_TEST(!disable_jbuf && !((table->map &
-                                                  join->outer_join)));
+      best.use_join_buffer= use_join_buffer;
+      best.refills= (ulonglong) ceil(refills);
       best.spl_plan= 0;
       best.type= type;
       trace_access_scan.add("chosen", true);
@@ -9286,6 +9319,8 @@ best_access_path(JOIN      *join,
   pos->records_after_filter= best.records_after_filter;
   pos->records_read= best.records;
   pos->records_out=  best.records_out;
+  pos->prev_record_reads= best.prev_record_reads;
+  pos->identical_keys=   best.identical_keys;
   pos->read_time=    best.cost;
   pos->key=          best.key;
   pos->forced_index= best.forced_index;
@@ -9293,11 +9328,12 @@ best_access_path(JOIN      *join,
   pos->table=        s;
   pos->ref_depend_map= best.ref_depends_map;
   pos->loosescan_picker.loosescan_key= MAX_KEY;
-  pos->use_join_buffer= best.uses_jbuf;
+  pos->use_join_buffer= best.use_join_buffer;
   pos->spl_plan= best.spl_plan;
   pos->range_rowid_filter_info= best.filter;
   pos->key_dependent= (best.type == JT_EQ_REF ? (table_map) 0 :
                        key_dependent & remaining_tables);
+  pos->refills=  best.refills;
 
   loose_scan_opt.save_to_position(s, record_count, pos->records_out,
                                   loose_scan_pos);
@@ -11571,89 +11607,241 @@ cache_record_length(JOIN *join,uint idx)
   return length;
 }
 
-
 /*
-  Get the number of different row combinations for subset of partial join
+  Estimate the number of engine ha_index_read_calls for EQ_REF tables
+  when taking into account the one-row-cache in join_read_always_key()
 
   SYNOPSIS
-    prev_record_reads()
-      join       The join structure
-      idx        Number of tables in the partial join order (i.e. the
-                 partial join order is in join->positions[0..idx-1])
-      found_ref  Bitmap of tables for which we need to find # of distinct
-                 row combinations.
+    @param position      All previous tables best_access_path() information.
+    @param idx           Number of (previous) tables in positions.
+    @param record_count  Number of incoming record combinations
+    @param found_ref     Bitmap of tables that is used to construct the key
+                         used with the index read.
 
-  DESCRIPTION
-    Given a partial join order (in join->positions[0..idx-1]) and a subset of
-    tables within that join order (specified in found_ref), find out how many
-    distinct row combinations of subset tables will be in the result of the
-    partial join order.
-     
-    This is used as follows: Suppose we have a table accessed with a ref-based
-    method. The ref access depends on current rows of tables in found_ref.
-    We want to count # of different ref accesses. We assume two ref accesses
-    will be different if at least one of access parameters is different.
-    Example: consider a query
-
-    SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
-
-    and a join order:
-      t1,  ref access on t1.key=c1
-      t2,  ref access on t2.key=c2       
-      t3,  ref access on t3.key=t1.field 
-    
-    For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
-    For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
-    For t3: n_ref_scans = records_read(t1)*records_read(t2)
-            n_distinct_ref_scans = #records_read(t1)
-    
-    The reason for having this function (at least the latest version of it)
-    is that we need to account for buffering in join execution. 
-    
-    An edge-case example: if we have a non-first table in join accessed via
-    ref(const) or ref(param) where there is a small number of different
-    values of param, then the access will likely hit the disk cache and will
-    not require any disk seeks.
-    
-    The proper solution would be to assume an LRU disk cache of some size,
-    calculate probability of cache hits, etc. For now we just count
-    identical ref accesses as one.
+    @return # The number of estimated calls that cannot be cached by the
+              the one-row-cache. In other words, number of expected
+              calls to engine ha_read_read_map().
+              Between 1 and record_count or 0 if record_count == 0
 
-  RETURN 
-    Expected number of row combinations
-*/
+  DESCRIPTION
+    The one-row-cache gives a great benefit when there are multiple consecutive
+    calls to ha_index_read() with the same key. In this case we can skip
+    calling the engine (and in the future also skip to check the key
+    condition), which can notably increase the performance.
+
+    Assuming most of the rows are cached, there is no notable saving to be
+    made trying to calculate the total number of distinct key values that will
+    be used. The performance of a ha_index_read_call() is about the same even
+    if we repeatedly read the same set of rows.
+
+    This code works by calculating the number of identical key sequences
+    found in the record stream.
+    The number of expected distinct calls can then be calculated as
+    records_count / sequences.
+
+    Some things to note:
+     - record_count == PRODUCT(records_out) over all tables[0...idx-1]
+     - position->prev_record_reads contains the number of identical
+       sequences found for previous EQ_REF tables.
+
+    Assume a join prefix of t1,t2,t3,t4 and t4 is an EQ_REF table.
+    We have the following combinations that we have to consider:
+
+======
+1) No JOIN_CACHE usage, tables depend only on one previous table
+
+   Row combinations are generated as:
+   - for all rows in t1
+     - for all rows in t2
+       - for all rows in t3
+   or
+   t1.1,t2.1,t3.1, t1.1,t2.1,t3.2, t1.1,t2.1,t3.3...  # Only t3 row changes
+   (until no more rows in t3., ie t3.records_out times)
+   t1.1,t2.2,t3.1, t1.1,t2.2,t3.2, t1.1,t2.2,t3.3...  # t2.2 read
+   (above repeated until no more rows in t2 and t3)
+   t1.2,t2.1,t3.1, t1.2,t2.1,t3.2, t1.2,t2.1,t3.3...  # t1.2 read
+
+   If t4 is an EQ_REF table that is depending of one of the
+   previous tables, the number of identical keys can be calculated
+   as the multiplication of records_out of the tables in between
+   the t4 and its first dependency.
+
+   Let's consider cases where t4 depends on different previous tables:
+   WHERE t4.a=t3.a
+     no caching as t3 can change for each row
+     engine_calls: record_count
+
+   WHERE t4.a=t2.a
+     t4 is not depending on t3. The number of repeated rows are:
+     t1.1,t2.1,t3.1       to t1.1,t2.1,t3.last   # t3.records_out rows
+     t1.1,t2.2,t3.1       to t1.1,t2.2,t3.last   # t3.records_out rows
+     ...
+     t1.2,t2.1,t3.1       to t1.2,t2.1,t3.last
+     ...
+     t1.last,t2.last.t3.1 to t1.last,t2.last.1,t3.last
+
+     For each combination of t1 and t2 there are t3.records_out repeated
+     rows with equal key value
+     engine_calls: record_count / t3.records_out calls =
+                    t1.records_out * t2.records_out
+
+   WHERE t4.a=t1.a
+     The repeated sequences:
+     t1.1,t2.1,t3.1 to t1.1,t2.last,t3.last
+     t1.2,t2.1,t3.1 to t2.1,t2.last,t3.last
+     repeated rows: t2.records_out * t3.records_out
+     engine_calls: record_count/repeated_rows = t1.records_out
+
+   If t4 depends on a table that uses EQ_REF access, we can multipy that
+   table's repeated_rows with current table's repeated_rows to take that
+   into account.
+
+=====
+2) Keys depending on multiple tables
+
+   In this case we have to stop searching after we find the first
+   table we depend upon.
+   We have to also disregard the number of repeated rows for the
+   found table. This can be seen from (assuming tables t1...t6):
+
+   WHERE t6.a=t4.a and t6.a=t3.a and t4.a= t2.a
+   - Here t4 is not depending on t3 (and thus there is a
+     t3.records_out identical keys for t4). However t6 key will
+     change for each t3 row and t6 cannot thus use
+     t3.identical_keys
+
+   WHERE t4.key_part1=t1.a and t4.key_part2= t3.a
+     As t4.key_part2 will change for every row, one-row-cache will not
+     be hit
+
+   WHERE t4.key_part1=t1.a and t4.key_part2= t2.a
+     t4.key will change when t1 or t2 changes
+     This is the same case as above for WHERE t4.a = t2.a
+      engine_calls: record_count / t3.records_out calls
+
+=====
+3) JOIN_CACHE is used
+
+   If any table is using join_cache as this changes the row
+   combinations seen by following tables.  Using join cache for a
+   table T# will have T# rows repeated for the next table as many
+   times there are combinations in the cache. The the cache will
+   re-read and the operations repeats 'refill-1' number of times.
+
+   Table rows from table just before T# will come in 'random order',
+   from the point of the next tables.
+
+   Assuming t3 is using a cache, t4 will see the rows coming in the
+   following order:
+   t1.1,t2.1,t3.1, t1.1,t2.2,t3.1, t1.1,t2.3,t3.1...
+   (t3.1 repeated 't2.records_out' times)
+   t1.2,t2.1,t3.1, t1.2,t2.2,t3.1, t1.2,t2.3,t3.1...
+   (Next row in t1 used)
+   t1.1,t2.1,t3.2, t1.1,t2.2,t3.2, t1.1,t2.3,t3.2...
+   (Restarting all t1 & t2 combinations for t3.2)
+
+   WHERE t4.a=t3.a
+   - There is a repeated sequence of t3.records_out rows for
+     each t1,t2 row combination.
+     engine_calls= record_count / t3.records_out
+
+   WHERE t4.a=t2.a
+     t2 changes for each row
+     engine_calls= record_count
+
+   WHERE t4.a=t1.a
+     repeated rows= t2.records_out
+     engine_calls= record_count / t2.records_out
+
+   A refill of the join cache will restart the row sequences
+   (we have 'refill' more sequences), so we will have to do 'refill' times
+   more engine read calls.
+
+=====
+   Expectations of the accuracy of the return value
+
+   - The value is always between 1 and record_count
+   - The returned value should almost always larger than the true number of
+     engine calls.
+
+   - Assuming that every row has different values for all other columns for
+     echo unique key value and record_count is accurate:
+     - If a table is depending on multiple tables, the return value may be
+       notable larger than real value.
+     - If there is no join cache the value should be exact.
+     - If there is a join cache, but no refills calculated or done then
+       the value should be exact.
+     - If there was more join_cache refills than was calculated, the value
+       may be slightly to low.
+     - If the number of refills is equal or less than was calculated the value
+       should be larger than the expected engine read calls. The more refills,
+       the less exact the number will be.
+*/
+
+static double
+prev_record_reads(const POSITION *position, uint idx, table_map found_ref,
+                  double record_count, double *identical_keys)
+{
+  double found= 1.0;
+  const POSITION *pos_end= position - 1;
+  const POSITION *cur_pos= position + idx;
+
+  /* Safety against const tables */
+  if (unlikely(!found_ref))
+    goto end;
 
-double
-prev_record_reads(const POSITION *positions, uint idx, table_map found_ref)
-{
-  double found=1.0;
-  const POSITION *pos_end= positions - 1;
-  for (const POSITION *pos= positions + idx - 1; pos != pos_end; pos--)
+  for (const POSITION *pos= cur_pos-1; pos != pos_end; pos--)
   {
-    if (pos->table->table->map & found_ref)
+    if (found_ref & pos->table->table->map)
     {
-      found_ref|= pos->ref_depend_map;
-      /* 
-        For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table 
-        with no matching row we will get position[t2].records_read==0. 
-        Actually the size of output is one null-complemented row, therefore 
-        we will use value of 1 whenever we get records_read==0.
-
-        Note
-        - the above case can't occur if inner part of outer join has more 
-          than one table: table with no matches will not be marked as const.
-
-        - Ideally we should add 1 to records_read for every possible null-
-          complemented row. We're not doing it because: 1. it will require
-          non-trivial code and add overhead. 2. The value of records_read
-          is an inprecise estimate and adding 1 (or, in the worst case,
-          #max_nested_outer_joins=64-1) will not make it any more precise.
+      /* Found a table we depend on */
+      found_ref= ~pos->table->table->map;
+      if (!found_ref)
+      {
+        /*
+          No more dependencies. We can use the cached values to improve things
+          a bit
+        */
+        if (pos->type == JT_EQ_REF)
+          found= COST_MULT(found, pos->identical_keys);
+        else if (pos->use_join_buffer)
+          found= COST_MULT(found, pos->loops / pos->refills);
+      }
+      break;
+    }
+    if (unlikely(pos->use_join_buffer))
+    {
+      /* Each refill can change the cached key */
+      found/= pos->refills;
+    }
+    else
+    {
+      /*
+        We are not depending on the current table.
+        There are 'records_out' rows with identical rows
+        value for our depending tables.
       */
-      if (pos->records_out)
-        found= COST_MULT(found, pos->records_out);
+      found= COST_MULT(found, pos->records_out);
     }
   }
-  return found;
+
+  /*
+    In most case found should <= record_count.
+
+    However if there was a reduction of rows (records_out < 1) before
+    the referencing table then found could be >= record_count.
+    To get resonable numbers, we limit prev_record_read to be between
+    1.0 and record_count as we have to always do at least one read
+    anyway.
+  */
+
+end:
+  if (unlikely(found > record_count))
+    found= record_count;
+  if (unlikely(found <= 1.0))
+    found= 1.0;
+  *identical_keys= found;
+  return record_count / found;
 }
 
 
diff --git a/sql/sql_select.h b/sql/sql_select.h
index 032437defc0..5113d1d36aa 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -410,7 +410,7 @@ typedef struct st_join_table {
   uint          index;
   uint		status;				///< Save status for cache
   uint		used_fields;
-  uint          cached_covering_key;            /* Set by estimate_scan_time() */
+  uint          cached_covering_key;            // Set by estimate_scan_time()
   ulong         used_fieldlength;
   ulong         max_used_fieldlength;
   uint          used_blobs;
@@ -1012,6 +1012,9 @@ public:
   */
   double records_out;
 
+  /* Values from prev_record_reads call for EQ_REF table*/
+  double        prev_record_reads, identical_keys;
+
   /* The selectivity of the pushed down conditions */
   double cond_selectivity;
 
@@ -1061,6 +1064,7 @@ public:
   LooseScan_picker          loosescan_picker;
   Sj_materialization_picker sjmat_picker;
 
+  ulonglong refills;
   /*
     Current optimization state: Semi-join strategy to be used for this
     and preceding join tables.
@@ -2537,7 +2541,6 @@ bool instantiate_tmp_table(TABLE *table, KEY *keyinfo,
                            TMP_ENGINE_COLUMNDEF **recinfo,
                            ulonglong options);
 bool open_tmp_table(TABLE *table);
-double prev_record_reads(const POSITION *positions, uint idx, table_map found_ref);
 void fix_list_after_tbl_changes(SELECT_LEX *new_parent, List<TABLE_LIST> *tlist);
 void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
 bool sort_and_filter_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse,
diff --git a/tests/prev_record.cc b/tests/prev_record.cc
new file mode 100644
index 00000000000..66fe8e6a464
--- /dev/null
+++ b/tests/prev_record.cc
@@ -0,0 +1,466 @@
+/* Copyright (c) 2023 MariaDB Corporation
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+/*
+  This program simulates the MariaDB query process execution using
+  the SCAN, EQ_REF,  REF and join_cache (CACHE) row lookup methods.
+
+  The purpose is to verify that 'prev_record_reads()' function correctly
+  estimates the number of lookups we have to do for EQ_REF access
+  assuming we have 'one-row-cache' before the lookup.
+
+  The logic for the prev_record_reads() function in this file should
+  match the logic in sql_select.cc::prev_record_reads() in MariaDB 11.0
+  and above.
+
+  The program generates first a randomized plan with the above
+  methods, then executes a full 'query' processing and then lastly
+  checks that the number of EQ_REF engine lookups matches the
+  estimated number of lookups.
+
+  If the number of estimated lookups are not exact, the plan and
+  lookup numbers are printed. That a plan is printed is not to be
+  regarded as a failure. It's a failure only of the number of engine
+  calls are far greater than the number of estimated lookups.
+
+  Note that the estimated number of lookups are exact only if CACHE
+  refills == 1 and if the EQ_REF table only depends on one earlier
+  table.
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <time.h>
+
+#define TABLES 21
+#define DEFAULT_TABLES 10
+#define CACHED_ROWS 10000
+#define unlikely(A) A
+
+enum JOIN_TYPE { SCAN, EQ_REF,  REF, CACHE };
+const char *type[]= { "SCAN", "EQ_REF", "REF", "CACHE"};
+
+typedef unsigned long long DEPEND;
+typedef unsigned int uint;
+typedef unsigned long long ulonglong;
+
+struct TABLE
+{
+  ulonglong data;
+  JOIN_TYPE type;
+  DEPEND map;
+  DEPEND ref_depend_map;
+  uint records_in_table;
+  uint matching_records;
+  uint last_key;
+  ulonglong lookups;
+  ulonglong *cache;                             // join cache
+  ulong cached_records;
+  ulong flushed_caches;
+};
+
+struct POSITION
+{
+  TABLE *table;
+  JOIN_TYPE type;
+  double records;
+  double record_count;
+  double records_out;
+  double prev_record_read;
+  double same_keys;
+  ulong refills;
+};
+
+uint opt_tables= DEFAULT_TABLES;
+bool verbose=0;
+uint rand_init;
+struct TABLE table[TABLES];
+struct POSITION positions[TABLES];
+
+void do_select(uint table_index);
+
+
+static void
+prev_record_reads(POSITION *position, uint idx, DEPEND found_ref,
+                  double record_count)
+{
+  double found= 1.0;
+  POSITION *pos_end= position - 1;
+  POSITION *cur_pos= position + idx;
+
+  /* Safety against const tables */
+  if (!found_ref)
+    goto end;
+
+  for (POSITION *pos= cur_pos-1; pos != pos_end; pos--)
+  {
+    if (found_ref & pos->table->map)
+    {
+      found_ref&= ~pos->table->map;
+
+      /* Found depent table */
+      if (pos->type == EQ_REF)
+      {
+        if (!found_ref)
+          found*= pos->same_keys;
+      }
+      else if (pos->type == CACHE)
+      {
+        if (!found_ref)
+          found*= pos->record_count / pos->refills;
+      }
+      break;
+    }
+    if (pos->type != CACHE)
+    {
+      /*
+        We are not depending on the curren table
+        There are 'records_out' rows with idenitical rows
+        value for our depending tables.
+        We are ignoring join_cache as in this case the
+        preceding tables row combination can change for
+        each call.
+      */
+      found*= pos->records_out;
+    }
+    else
+      found/= pos->refills;
+  }
+
+end:
+  cur_pos->record_count= record_count;
+  cur_pos->same_keys= found;
+  assert(record_count >= found);
+
+  if (unlikely(found <= 1.0))
+    cur_pos->prev_record_read= record_count;
+  else if (unlikely(found > record_count))
+    cur_pos->prev_record_read=1;
+  else
+    cur_pos->prev_record_read= record_count / found;
+  return;
+}
+
+
+void cleanup()
+{
+  for (uint i= 0; i < opt_tables ; i++)
+  {
+    free(table[i].cache);
+    table[i].cache= 0;
+  }
+}
+
+
+void intialize_tables()
+{
+  int eq_ref_tables;
+
+restart:
+  eq_ref_tables= 0;
+  for (uint i= 0; i < opt_tables ; i++)
+  {
+    if (i == 0)
+      table[i].type= SCAN;
+    else
+      table[i].type= (JOIN_TYPE) (rand() % 4);
+    table[i].records_in_table= rand() % 5+3;
+    table[i].matching_records= 2 + rand() % 3;
+    table[i].map= (DEPEND) 1 << i;
+    table[i].ref_depend_map= 0;
+
+/* The following is for testing */
+#ifdef FORCE_COMB
+    if (i == 5 || i == 6)
+    {
+      table[i].type= REF;
+      table[i].matching_records= 5;
+    }
+#endif
+    if (table[i].type != SCAN)
+    {
+      /* This just to make do_select a bit easier */
+      table[i].ref_depend_map=  ((DEPEND) 1) << (rand() % i);
+      if (rand() & 1)
+      {
+        uint second_depend= rand() % i;
+        if (!(table[i].ref_depend_map & second_depend))
+          table[i].ref_depend_map|= ((DEPEND) 1) << second_depend;
+      }
+    }
+
+    if (table[i].type == EQ_REF)
+    {
+      table[i].matching_records= 1;
+      eq_ref_tables++;
+    }
+    else if (table[i].type != REF)
+      table[i].matching_records= table[i].records_in_table;
+
+    table[i].last_key= 0;
+    table[i].lookups= 0;
+    table[i].cached_records= 0;
+    table[i].flushed_caches= 0;
+    table[i].cache= 0;
+    if (table[i].type == CACHE)
+      table[i].cache= (ulonglong*) malloc(CACHED_ROWS *
+                                          sizeof(table[i].data) * i);
+  }
+
+  /* We must have at least one EQ_REF table */
+  if (!eq_ref_tables)
+  {
+    cleanup();
+    goto restart;
+  }
+}
+
+
+void optimize_tables()
+{
+  double record_count= 1.0, records;
+
+  for (uint i= 0; i < opt_tables ; i++)
+  {
+    TABLE *tab= table+i;
+    positions[i].refills= 0;
+
+    switch (tab->type) {
+    case SCAN:
+      records= tab->records_in_table;
+      break;
+    case EQ_REF:
+      records= 1.0;
+      prev_record_reads(positions, i, tab->ref_depend_map, record_count);
+      break;
+    case REF:
+      records= tab->matching_records;
+      break;
+    case CACHE:
+      records= tab->records_in_table;
+      positions[i].refills= (record_count + CACHED_ROWS-1)/ CACHED_ROWS;
+      break;
+    default:
+      assert(0);
+    }
+    positions[i].table= table + i;
+    positions[i].type= table[i].type;
+    positions[i].records= records;
+    positions[i].record_count= record_count;
+    positions[i].records_out= records;
+
+    record_count*= records;
+  }
+}
+
+
+
+void process_join_cache(TABLE *tab, uint table_index)
+{
+  if (!tab->cached_records)
+    return;
+
+#ifdef PRINT_CACHE
+  putc('>', stdout);
+  for (uint k= 0 ; k < table_index ; k++)
+  {
+    printf("%8lld ", tab->cache[k]);
+  }
+  putc('\n',stdout);
+  putc('<', stdout);
+  for (uint k= 0 ; k < table_index ; k++)
+  {
+    printf("%8lld ", tab->cache[k+(tab->cached_records-1)*table_index]);
+  }
+  putc('\n',stdout);
+#endif
+
+  for (uint k= 0 ; k < tab->records_in_table; k++)
+  {
+    table[table_index].data= k+1;
+    ulonglong *cache= tab->cache;
+    for (uint i= 0 ; i < tab->cached_records ; i++)
+    {
+      for (uint j= 0 ; j < table_index ; j++)
+        table[j].data= *cache++;
+      do_select(table_index+1);
+    }
+  }
+  tab->flushed_caches++;
+  tab->cached_records= 0;
+}
+
+/*
+  Calculate a key depending on multiple tables
+*/
+
+ulonglong calc_ref_key(DEPEND depend_map)
+{
+  ulonglong value= 1;
+  TABLE *t= table;
+
+  do
+  {
+    if (t->map & depend_map)
+    {
+      depend_map&= ~t->map;
+      value*= t->data;
+    }
+    t++;
+  } while (depend_map);
+  return value;
+}
+
+
+void do_select(uint table_index)
+{
+  if (table_index == opt_tables)
+    return;
+
+  TABLE *tab= table + table_index;
+  switch (tab->type) {
+  case SCAN:
+    for (uint i= 1 ; i <= tab->records_in_table ; i++)
+    {
+      tab->data= i;
+      do_select(table_index+1);
+    }
+    break;
+  case REF:
+  {
+    ulonglong ref_key= calc_ref_key(tab->ref_depend_map);
+    for (uint i=1 ; i <= tab->matching_records ; i++)
+    {
+      tab->data= ref_key * tab->matching_records + i;
+      do_select(table_index+1);
+    }
+    break;
+  }
+  case EQ_REF:
+  {
+    ulonglong ref_key= calc_ref_key(tab->ref_depend_map);
+    if (ref_key != tab->last_key)
+    {
+      tab->lookups++;
+#ifdef PRINT_EQ_KEY
+      if (table_index == 9)
+        printf("ref_key: %lld\n", ref_key);
+#endif
+      tab->last_key= ref_key;
+      tab->data= ref_key * tab->matching_records;
+    }
+    else
+    {
+      assert(tab->lookups != 0);
+    }
+    do_select(table_index+1);
+    break;
+  }
+  case CACHE:
+  {
+    ulonglong *cache= tab->cache + tab->cached_records * table_index;
+    for (uint i= 0 ; i <= table_index ; i++)
+      *cache++ = table[i].data;
+    if (++tab->cached_records == CACHED_ROWS)
+      process_join_cache(tab, table_index);
+    break;
+  }
+  default:
+    break;
+  }
+  return;
+}
+
+
+void do_select_end(uint table_index)
+{
+  if (table_index == opt_tables)
+    return;
+
+  TABLE *tab= table + table_index;
+  switch (tab->type) {
+  case CACHE:
+    process_join_cache(tab, table_index);
+    break;
+  default:
+    break;
+  }
+  do_select_end(table_index+1);
+}
+
+
+void execute()
+{
+  do_select(0);
+  do_select_end(0);
+}
+
+int check_prev_records()
+{
+  int errors= 0;
+  for (uint i= 0; i < opt_tables ; i++)
+  {
+    TABLE *tab= table + i;
+    if (tab->type == EQ_REF)
+    {
+      if (positions[i].prev_record_read != (double) tab->lookups)
+      {
+        fprintf(stdout, "table: %d  lookups: %lld  prev_record_read: %g\n",
+                i, tab->lookups, positions[i].prev_record_read);
+        errors++;
+      }
+    }
+  }
+  if (errors || verbose)
+  {
+    fprintf(stdout, "tables:     %u\n", opt_tables);
+    fprintf(stdout, "rand_init:  %u\n", rand_init);
+    fprintf(stdout, "cache_size: %u\n", (uint) CACHED_ROWS);
+    for (uint i= 0; i < opt_tables ; i++)
+    {
+      TABLE *tab= table + i;
+      fprintf(stdout, "table: %2d (%3lx)  type: %-6s  comb: %3lg  out: %2lg  lookups: %lld  prev: %lg  depend: %llx\n",
+              i, (uint) 1 << i, type[tab->type], positions[i].record_count,
+              positions[i].records_out, tab->lookups,
+              positions[i].prev_record_read, tab->ref_depend_map);
+    }
+  }
+  return errors;
+}
+
+
+int main(int argc, char **argv)
+{
+  if (argc > 1)
+  {
+    opt_tables=atoi(argv[1]);
+    if (opt_tables <= 3)
+      opt_tables= 3;
+    if (opt_tables > TABLES)
+      opt_tables= TABLES;
+  }
+  if (argc > 2)
+    rand_init= atoi(argv[2]);
+  else
+    rand_init= (uint) time(0);
+  srand(rand_init);
+
+  intialize_tables();
+  optimize_tables();
+  execute();
+  cleanup();
+  exit(check_prev_records() > 0);
+}