List:Commits« Previous MessageNext Message »
From:Jorgen Loland Date:February 23 2012 11:23am
Subject:bzr push into mysql-trunk branch (jorgen.loland:3947 to 3948) WL#6158
View as plain text  
 3948 Jorgen Loland	2012-02-23
      WL#6158: SORTING OF TABLES BEFORE GREEDY_SEARCH DOES NOT TAKE KEY 
               DEPENDENCY INTO ACCOUNT
      
      Earlier, the following algorithm was used to order tables 
      before doing greedy search: 
       1) Outer tables before inner tables 
          (as in "outer LEFT JOIN inner")
       2) Increasing number of expected rows 
      
      By taking key dependency into account when doing this 
      pre-sorting, greedy search will be able to considerably 
      reduce the number of plans because pruning is more likely
      to happen.
      
      In addition, merge and insert sort is implemented because
      the std::stable_sort implementation differs between platforms.
      This results in different QEPs which in turn is a problem for 
      mtr testing.
     @ mysql-test/include/greedy_search_drop_tables.inc
        Add test for WL#6158
     @ mysql-test/include/greedy_search_load_tables.inc
        Add test for WL#6158
     @ mysql-test/include/print_greedy_search_count.inc
        Add test for WL#6158. Prints how many partial plans was 
        generated by greedy search
        Add test for WL#6158
     @ mysql-test/r/greedy_search.result
        Add test for WL#6158
     @ mysql-test/r/join_cache_bka.result
        Plan changes. New plan has same cost as the previous cost so 
        the plans are equal as far as greedy search is concerned. 
        They also produce the same amount of handler calls. The new
        plan enables the use of range scan (which happens here) which
        is good.
        Note: Both the old and new greedy search algorithm depends on the name of the tables if they are otherwise equal. If t1 
        is renamed to tx1 in the existing test (without applying the changeset from this WL) you end up with the same plan recorded.
     @ mysql-test/r/join_cache_bka_nixbnl.result
        Plan changes. New plan has same cost as the previous cost so 
        the plans are equal as far as greedy search is concerned. 
        They also produce the same amount of handler calls. The new
        plan enables the use of range scan (which happens here) which
        is good.
     @ mysql-test/r/join_cache_bkaunique.result
        Plan changes. New plan has same cost as the previous cost so 
        the plans are equal as far as greedy search is concerned. 
        They also produce the same amount of handler calls. The new
        plan enables the use of range scan (which happens here) which
        is good.
     @ mysql-test/r/join_cache_bnl.result
        Plan changes. New plan has same cost as the previous cost so 
        the plans are equal as far as greedy search is concerned. 
        They also produce the same amount of handler calls. The new
        plan enables the use of range scan (which happens here) which
        is good.
        Note: Both the old and new greedy search algorithm depends on the name of the tables if they are otherwise equal. If t1 
        is renamed to tx1 in the existing test (without applying the changeset from this WL) you end up with the same plan recorded.
     @ mysql-test/r/join_cache_nojb.result
        Plan changes. New plan has same cost as the previous cost so 
        the plans are equal as far as greedy search is concerned. 
        They also produce the same amount of handler calls. The new
        plan enables the use of range scan (which happens here) which
        is good.
     @ mysql-test/r/join_nested.result
        Plan changes. New plan has same cost as the previous cost so 
        the plans are equal as far as greedy search is concerned.
     @ mysql-test/r/join_nested_bka.result
        Plan changes. New plan has same cost as the previous cost so 
        the plans are equal as far as greedy search is concerned.
     @ mysql-test/r/join_nested_bka_nixbnl.result
        Plan changes. New plan has same cost as the previous cost so 
        the plans are equal as far as greedy search is concerned.
     @ mysql-test/r/subquery_all.result
        Plan changes. New plan has same cost as the previous cost so 
        the plans are equal as far as greedy search is concerned.
     @ mysql-test/r/subquery_all_bka.result
        Plan changes. New plan has same cost as the previous cost so 
        the plans are equal as far as greedy search is concerned.
     @ mysql-test/r/subquery_mat_all.result
        Plan changes. The new plan is not better than the old one, but
        Roy agrees that this is due to too agressive pruning for
        SJ. Will be fixed by WL 6156.
     @ mysql-test/r/subquery_sj_dupsweed.result
        Plan changes. 
        * "During work with BUG#45863": The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
        * bug 12797534: The new plan has the same number of expected 
          rows, and the same calculated cost. Therefore, disabling 
          pruning has no effect with or without this changeset. 
          However, it makes more sense to do eq-ref early so the new
          plan is good.
        * BUG#13589848: The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
     @ mysql-test/r/subquery_sj_dupsweed_bka.result
        Plan changes. 
        * "During work with BUG#45863": The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
        * bug 12797534: The new plan has the same number of expected 
          rows, and the same calculated cost. Therefore, disabling 
          pruning has no effect with or without this changeset. 
          However, it makes more sense to do eq-ref early so the new
          plan is good.
        * BUG#13589848: The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
     @ mysql-test/r/subquery_sj_dupsweed_bka_nixbnl.result
        Plan changes. 
        * "During work with BUG#45863": The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
        * bug 12797534: The new plan has the same number of expected 
          rows, and the same calculated cost. Therefore, disabling 
          pruning has no effect with or without this changeset. 
          However, it makes more sense to do eq-ref early so the new
          plan is good.
     @ mysql-test/r/subquery_sj_dupsweed_bkaunique.result
        Plan changes. 
        * "During work with BUG#45863": The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
        * bug 12797534: The new plan has the same number of expected 
          rows, and the same calculated cost. Therefore, disabling 
          pruning has no effect with or without this changeset. 
          However, it makes more sense to do eq-ref early so the new
          plan is good.
        * BUG#13589848: The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
     @ mysql-test/r/subquery_sj_firstmatch.result
        Plan changes. 
        * "During work with BUG#45863": The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
        * bug 12797534: The new plan has the same number of expected 
          rows, and the same calculated cost. Therefore, disabling 
          pruning has no effect with or without this changeset. 
          However, it makes more sense to do eq-ref early so the new
          plan is good.
        * BUG#13589848: The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
     @ mysql-test/r/subquery_sj_firstmatch_bka.result
        Plan changes. 
        * "During work with BUG#45863": The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
        * bug 12797534: The new plan has the same number of expected 
          rows, and the same calculated cost. Therefore, disabling 
          pruning has no effect with or without this changeset. 
          However, it makes more sense to do eq-ref early so the new
          plan is good.
        * BUG#13589848: The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
     @ mysql-test/r/subquery_sj_firstmatch_bka_nixbnl.result
        Plan changes. 
        * "During work with BUG#45863": The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
        * bug 12797534: The new plan has the same number of expected 
          rows, and the same calculated cost. Therefore, disabling 
          pruning has no effect with or without this changeset. 
          However, it makes more sense to do eq-ref early so the new
          plan is good.
     @ mysql-test/r/subquery_sj_firstmatch_bkaunique.result
        Plan changes. 
        * "During work with BUG#45863": The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
        * bug 12797534: The new plan has the same number of expected 
          rows, and the same calculated cost. Therefore, disabling 
          pruning has no effect with or without this changeset. 
          However, it makes more sense to do eq-ref early so the new
          plan is good.
        * BUG#13589848: The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
     @ mysql-test/r/subquery_sj_loosescan.result
        Plan changes. 
        * "During work with BUG#45863": The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
        * bug 12797534: The new plan has the same number of expected 
          rows, and the same calculated cost. Therefore, disabling 
          pruning has no effect with or without this changeset. 
          However, it makes more sense to do eq-ref early so the new
          plan is good.
     @ mysql-test/r/subquery_sj_loosescan_bka.result
        Plan changes. 
        * "During work with BUG#45863": The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
        * bug 12797534: The new plan has the same number of expected 
          rows, and the same calculated cost. Therefore, disabling 
          pruning has no effect with or without this changeset. 
          However, it makes more sense to do eq-ref early so the new
          plan is good.
     @ mysql-test/r/subquery_sj_loosescan_bka_nixbnl.result
        Plan changes. 
        * "During work with BUG#45863": The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
        * bug 12797534: The new plan has the same number of expected 
          rows, and the same calculated cost. Therefore, disabling 
          pruning has no effect with or without this changeset. 
          However, it makes more sense to do eq-ref early so the new
          plan is good.
     @ mysql-test/r/subquery_sj_loosescan_bkaunique.result
        Plan changes. 
        * "During work with BUG#45863": The new plan is identical to 
          the plan created without this changeset if pruning is
          disabled. Hence, this CS makes the optimizer find a better 
          plan
        * bug 12797534: The new plan has the same number of expected 
          rows, and the same calculated cost. Therefore, disabling 
          pruning has no effect with or without this changeset. 
          However, it makes more sense to do eq-ref early so the new
          plan is good.
     @ mysql-test/suite/opt_trace/r/bugs_no_prot_all.result
        Different trace due to initially different order of the tables
        (WL6158)
     @ mysql-test/suite/opt_trace/r/bugs_ps_prot_all.result
        Different trace due to initially different order of the tables
        (WL6158)
     @ mysql-test/suite/opt_trace/r/subquery_no_prot.result
        Different trace due to initially different order of the tables
        (WL6158)
     @ mysql-test/suite/opt_trace/r/subquery_ps_prot.result
        Different trace due to initially different order of the tables
        (WL6158)
     @ mysql-test/t/greedy_search.test
        Add test for WL#6158
     @ sql/merge_sort.h
        Implementation of STL compliant insert sort and merge sort
     @ sql/mysqld.cc
        Add system variable Opt_partial_plans: count number of partial
        plans explored by greedy search.
     @ sql/sql_class.h
        Add system variable Opt_partial_plans: count number of partial
        plans explored by greedy search.
     @ sql/sql_planner.cc
        Change pre-greedysort ordering of tables to merge_sort
        Add system variable Opt_partial_plans: count number of partial
        plans explored by greedy search.
     @ sql/sql_planner.h
        Updated comment
     @ sql/sql_select.h
        Implementation of JOIN_TAB comparison functions for use with 
        sorting. The new comparison functions take key dependency into
        account in pre-greedysort ordering
     @ unittest/gunit/join_tab_sort-t.cc
        Add unit tests for JOIN_TAB sorting

    added:
      mysql-test/include/greedy_search_drop_tables.inc
      mysql-test/include/greedy_search_load_tables.inc
      mysql-test/include/print_greedy_search_count.inc
      mysql-test/r/greedy_search.result
      mysql-test/t/greedy_search.test
      sql/merge_sort.h
      unittest/gunit/join_tab_sort-t.cc
    modified:
      mysql-test/r/join_cache_bka.result
      mysql-test/r/join_cache_bka_nixbnl.result
      mysql-test/r/join_cache_bkaunique.result
      mysql-test/r/join_cache_bnl.result
      mysql-test/r/join_cache_nojb.result
      mysql-test/r/join_nested.result
      mysql-test/r/join_nested_bka.result
      mysql-test/r/join_nested_bka_nixbnl.result
      mysql-test/r/subquery_all.result
      mysql-test/r/subquery_all_bka.result
      mysql-test/r/subquery_mat_all.result
      mysql-test/r/subquery_sj_dupsweed.result
      mysql-test/r/subquery_sj_dupsweed_bka.result
      mysql-test/r/subquery_sj_dupsweed_bka_nixbnl.result
      mysql-test/r/subquery_sj_dupsweed_bkaunique.result
      mysql-test/r/subquery_sj_firstmatch.result
      mysql-test/r/subquery_sj_firstmatch_bka.result
      mysql-test/r/subquery_sj_firstmatch_bka_nixbnl.result
      mysql-test/r/subquery_sj_firstmatch_bkaunique.result
      mysql-test/r/subquery_sj_loosescan.result
      mysql-test/r/subquery_sj_loosescan_bka.result
      mysql-test/r/subquery_sj_loosescan_bka_nixbnl.result
      mysql-test/r/subquery_sj_loosescan_bkaunique.result
      mysql-test/suite/opt_trace/r/bugs_no_prot_all.result
      mysql-test/suite/opt_trace/r/bugs_ps_prot_all.result
      mysql-test/suite/opt_trace/r/subquery_no_prot.result
      mysql-test/suite/opt_trace/r/subquery_ps_prot.result
      sql/mysqld.cc
      sql/sql_class.h
      sql/sql_planner.cc
      sql/sql_planner.h
      sql/sql_select.h
      unittest/gunit/CMakeLists.txt
 3947 Mattias Jonsson	2012-02-23
      post push fix for testcase under valgrind, Bug#12750920

    modified:
      mysql-test/r/mysql_client_test_embedded.result
      mysql-test/t/mysql_client_test_embedded.test
=== added file 'mysql-test/include/greedy_search_drop_tables.inc'
--- a/mysql-test/include/greedy_search_drop_tables.inc	1970-01-01 00:00:00 +0000
+++ b/mysql-test/include/greedy_search_drop_tables.inc	2012-02-23 11:22:34 +0000
@@ -0,0 +1,3 @@
+DROP TABLE tbl10, tbl100;
+DROP TABLE t10_1,t10_2,t10_3,t10_4,t10_5,t10_6,t10_7,t10_8,t10_9;
+DROP TABLE t100_1,t100_2,t100_3,t100_4,t100_5,t100_6,t100_7,t100_8,t100_9;

=== added file 'mysql-test/include/greedy_search_load_tables.inc'
--- a/mysql-test/include/greedy_search_load_tables.inc	1970-01-01 00:00:00 +0000
+++ b/mysql-test/include/greedy_search_load_tables.inc	2012-02-23 11:22:34 +0000
@@ -0,0 +1,35 @@
+--disable_query_log
+--disable_result_log
+
+# tbl10 and tbl100 are only used to fill the tables used during testing
+CREATE TABLE tbl10(
+  k INT NOT NULL AUTO_INCREMENT,
+  i INT,
+  PRIMARY KEY(k)
+);
+INSERT INTO tbl10(i) VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(0);
+
+CREATE TABLE tbl100 LIKE tbl10;
+INSERT INTO tbl100(i) SELECT x.i FROM tbl10 AS x, tbl10 AS y;
+
+let $i= 1;
+WHILE ($i < 10)
+{
+  --let $stmt= CREATE TABLE t10_$i (pk int PRIMARY KEY AUTO_INCREMENT, colidx int, col int, index (colidx))
+  --eval $stmt;
+  --let $stmt= INSERT INTO t10_$i (colidx, col) SELECT k, k FROM tbl10
+  --eval $stmt;
+  # Update index statistics
+  ANALYZE TABLE t10_$i;
+  
+  --let $stmt= CREATE TABLE t100_$i (pk int PRIMARY KEY AUTO_INCREMENT, colidx int, col int, index (colidx))
+  --eval $stmt;
+  --let $stmt= INSERT INTO t100_$i (colidx, col) SELECT a.k, a.k FROM tbl10 a JOIN tbl10 b;
+  --eval $stmt;
+  # Update index statistics
+  ANALYZE TABLE t10_$i;
+
+  inc $i;
+}  
+--enable_result_log
+--enable_query_log

=== added file 'mysql-test/include/print_greedy_search_count.inc'
--- a/mysql-test/include/print_greedy_search_count.inc	1970-01-01 00:00:00 +0000
+++ b/mysql-test/include/print_greedy_search_count.inc	2012-02-23 11:22:34 +0000
@@ -0,0 +1,25 @@
+# include/print_greedy_search_count.inc
+#
+# SUMMARY
+#
+#    $query should be assigned a select statement. 
+#    The query will be EXPLAINed and the number of 
+#    partial plans greedy search went through to 
+#    create the QEP is printed.
+#
+# USAGE
+#
+#    let $query= <query>;
+#    --source include/print_greedy_search_count.inc
+#
+# EXAMPLE
+#    t/greedy_search.test
+#
+
+eval EXPLAIN $query;
+
+let $greedy_search_partial_plans=
+  query_get_value(SHOW STATUS LIKE 'Opt_partial_plans', Value, 1);
+
+--echo ### Opt_partial_plans: $greedy_search_partial_plans
+FLUSH STATUS;

=== added file 'mysql-test/r/greedy_search.result'
--- a/mysql-test/r/greedy_search.result	1970-01-01 00:00:00 +0000
+++ b/mysql-test/r/greedy_search.result	2012-02-23 11:22:34 +0000
@@ -0,0 +1,194 @@
+#
+# TEST 1
+# Greedy search iteration test for 16-way join: star schema
+#
+# Creation of 16 tables hidden
+#
+SET SESSION optimizer_search_depth = 25;
+FLUSH STATUS;
+#
+# 16-way join - all 15 fact tables joined on column with key
+#
+EXPLAIN SELECT *
+FROM vehicles
+JOIN models        ON vehicles.model_id        = models.id_pk
+JOIN subtypes      ON vehicles.subtype_id      = subtypes.id_pk
+JOIN colors        ON vehicles.color_id        = colors.id_pk
+JOIN heating       ON vehicles.heating_id      = heating.id_pk
+JOIN windows       ON vehicles.window_id       = windows.id_pk
+JOIN fuels         ON vehicles.fuel_id         = fuels.id_pk
+JOIN transmissions ON vehicles.transmission_id = transmissions.id_pk
+JOIN steerings     ON vehicles.steering_id     = steerings.id_pk
+JOIN interiors     ON vehicles.interior_id     = interiors.id_pk
+JOIN drives        ON vehicles.drive_id        = drives.id_pk
+JOIN wheels        ON vehicles.wheels_id       = wheels.id_pk
+JOIN engine        ON vehicles.engine_id       = engine.id_pk
+JOIN price_ranges  ON vehicles.price_range_id  = price_ranges.id_pk
+JOIN countries     ON vehicles.assembled_in    = countries.id_pk
+JOIN brands        ON models.brand_id          = brands.id_pk;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	vehicles	ALL	NULL	NULL	NULL	NULL	80	Using where
+1	SIMPLE	subtypes	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.subtype_id	1	
+1	SIMPLE	heating	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.heating_id	1	
+1	SIMPLE	windows	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.window_id	1	
+1	SIMPLE	fuels	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.fuel_id	1	
+1	SIMPLE	transmissions	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.transmission_id	1	
+1	SIMPLE	steerings	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.steering_id	1	
+1	SIMPLE	drives	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.drive_id	1	
+1	SIMPLE	wheels	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.wheels_id	1	
+1	SIMPLE	engine	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.engine_id	1	
+1	SIMPLE	price_ranges	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.price_range_id	1	
+1	SIMPLE	colors	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.color_id	1	
+1	SIMPLE	interiors	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.interior_id	1	
+1	SIMPLE	countries	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.assembled_in	1	
+1	SIMPLE	models	eq_ref	PRIMARY,brand_id	PRIMARY	4	test.vehicles.model_id	1	Using where
+1	SIMPLE	brands	eq_ref	PRIMARY	PRIMARY	4	test.models.brand_id	1	
+### Opt_partial_plans: 50922
+FLUSH STATUS;
+#
+# 16-way join - 10 fact tables joined on column with key and
+#                5 fact tables joined on column without key
+#
+EXPLAIN SELECT *
+FROM vehicles
+JOIN models        ON vehicles.model_id        = models.id_nokey
+JOIN subtypes      ON vehicles.subtype_id      = subtypes.id_pk
+JOIN colors        ON vehicles.color_id        = colors.id_pk
+JOIN heating       ON vehicles.heating_id      = heating.id_nokey
+JOIN windows       ON vehicles.window_id       = windows.id_pk
+JOIN fuels         ON vehicles.fuel_id         = fuels.id_pk
+JOIN transmissions ON vehicles.transmission_id = transmissions.id_nokey
+JOIN steerings     ON vehicles.steering_id     = steerings.id_pk
+JOIN interiors     ON vehicles.interior_id     = interiors.id_pk
+JOIN drives        ON vehicles.drive_id        = drives.id_pk
+JOIN wheels        ON vehicles.wheels_id       = wheels.id_nokey
+JOIN engine        ON vehicles.engine_id       = engine.id_pk
+JOIN price_ranges  ON vehicles.price_range_id  = price_ranges.id_pk
+JOIN countries     ON vehicles.assembled_in    = countries.id_pk
+JOIN brands        ON models.brand_id          = brands.id_nokey;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	brands	ALL	NULL	NULL	NULL	NULL	7	Using where
+1	SIMPLE	models	ref	brand_id	brand_id	5	test.brands.id_nokey	4	
+1	SIMPLE	heating	ALL	NULL	NULL	NULL	NULL	10	Using join buffer (Block Nested Loop)
+1	SIMPLE	transmissions	ALL	NULL	NULL	NULL	NULL	10	Using join buffer (Block Nested Loop)
+1	SIMPLE	wheels	ALL	NULL	NULL	NULL	NULL	10	Using join buffer (Block Nested Loop)
+1	SIMPLE	vehicles	ALL	NULL	NULL	NULL	NULL	80	Using where; Using join buffer (Block Nested Loop)
+1	SIMPLE	windows	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.window_id	1	
+1	SIMPLE	fuels	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.fuel_id	1	
+1	SIMPLE	steerings	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.steering_id	1	
+1	SIMPLE	drives	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.drive_id	1	
+1	SIMPLE	engine	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.engine_id	1	
+1	SIMPLE	price_ranges	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.price_range_id	1	
+1	SIMPLE	interiors	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.interior_id	1	
+1	SIMPLE	countries	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.assembled_in	1	
+1	SIMPLE	subtypes	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.subtype_id	1	
+1	SIMPLE	colors	eq_ref	PRIMARY	PRIMARY	4	test.vehicles.color_id	1	
+### Opt_partial_plans: 483932
+FLUSH STATUS;
+select @@optimizer_search_depth;
+@@optimizer_search_depth
+25
+select @@optimizer_prune_level;
+@@optimizer_prune_level
+1
+DROP TABLE vehicles, models, subtypes, colors, heating, windows, 
+fuels, transmissions, steerings, interiors, drives, 
+price_ranges, countries, brands, wheels, engine;
+#
+# TEST 2
+# Greedy search iteration test for chain of tables
+#
+#
+# Chain test a:      colidx):(pk,colidx):(pk,colidx)
+#
+EXPLAIN SELECT * FROM t10_1 JOIN t100_1 ON t10_1.colidx = t100_1.pk JOIN t10_2 ON t100_1.colidx = t10_2.pk JOIN t100_2 ON t10_2.colidx = t100_2.pk JOIN t10_3 ON t100_2.colidx = t10_3.pk JOIN t100_3 ON t10_3.colidx = t100_3.pk JOIN t10_4 ON t100_3.colidx = t10_4.pk JOIN t100_4 ON t10_4.colidx = t100_4.pk JOIN t10_5 ON t100_4.colidx = t10_5.pk JOIN t100_5 ON t10_5.colidx = t100_5.pk JOIN t10_6 ON t100_5.colidx = t10_6.pk JOIN t100_6 ON t10_6.colidx = t100_6.pk JOIN t10_7 ON t100_6.colidx = t10_7.pk JOIN t100_7 ON t10_7.colidx = t100_7.pk JOIN t10_8 ON t100_7.colidx = t10_8.pk;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t10_1	ALL	colidx	NULL	NULL	NULL	10	Using where
+1	SIMPLE	t100_1	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t10_1.colidx	1	Using where
+1	SIMPLE	t10_2	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t100_1.colidx	1	Using where
+1	SIMPLE	t100_2	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t10_2.colidx	1	Using where
+1	SIMPLE	t10_3	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t100_2.colidx	1	Using where
+1	SIMPLE	t100_3	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t10_3.colidx	1	Using where
+1	SIMPLE	t10_4	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t100_3.colidx	1	Using where
+1	SIMPLE	t100_4	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t10_4.colidx	1	Using where
+1	SIMPLE	t10_5	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t100_4.colidx	1	Using where
+1	SIMPLE	t100_5	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t10_5.colidx	1	Using where
+1	SIMPLE	t10_6	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t100_5.colidx	1	Using where
+1	SIMPLE	t100_6	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t10_6.colidx	1	Using where
+1	SIMPLE	t10_7	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t100_6.colidx	1	Using where
+1	SIMPLE	t100_7	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t10_7.colidx	1	Using where
+1	SIMPLE	t10_8	eq_ref	PRIMARY	PRIMARY	4	test.t100_7.colidx	1	
+### Opt_partial_plans: 3669
+FLUSH STATUS;
+#
+# Chain test b: (...,col):(colidx, col):(pk,col):(colidx,col):(pk,...)
+#
+EXPLAIN SELECT * FROM t10_1 JOIN t100_1 ON t10_1.col = t100_1.colidx JOIN t10_2 ON t100_1.col = t10_2.pk JOIN t100_2 ON t10_2.col = t100_2.colidx JOIN t10_3 ON t100_2.col = t10_3.pk JOIN t100_3 ON t10_3.col = t100_3.colidx JOIN t10_4 ON t100_3.col = t10_4.pk JOIN t100_4 ON t10_4.col = t100_4.colidx JOIN t10_5 ON t100_4.col = t10_5.pk JOIN t100_5 ON t10_5.col = t100_5.colidx JOIN t10_6 ON t100_5.col = t10_6.pk JOIN t100_6 ON t10_6.col = t100_6.colidx JOIN t10_7 ON t100_6.col = t10_7.pk JOIN t100_7 ON t10_7.col = t100_7.colidx JOIN t10_8 ON t100_7.col = t10_8.pk;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t10_1	ALL	NULL	NULL	NULL	NULL	10	Using where
+1	SIMPLE	t100_1	ref	colidx	colidx	5	test.t10_1.col	10	Using where
+1	SIMPLE	t10_2	eq_ref	PRIMARY	PRIMARY	4	test.t100_1.col	1	Using where
+1	SIMPLE	t100_2	ref	colidx	colidx	5	test.t10_2.col	10	Using where
+1	SIMPLE	t10_3	eq_ref	PRIMARY	PRIMARY	4	test.t100_2.col	1	Using where
+1	SIMPLE	t100_3	ref	colidx	colidx	5	test.t10_3.col	10	Using where
+1	SIMPLE	t10_4	eq_ref	PRIMARY	PRIMARY	4	test.t100_3.col	1	Using where
+1	SIMPLE	t100_4	ref	colidx	colidx	5	test.t10_4.col	10	Using where
+1	SIMPLE	t10_5	eq_ref	PRIMARY	PRIMARY	4	test.t100_4.col	1	Using where
+1	SIMPLE	t100_5	ref	colidx	colidx	5	test.t10_5.col	10	Using where
+1	SIMPLE	t10_6	eq_ref	PRIMARY	PRIMARY	4	test.t100_5.col	1	Using where
+1	SIMPLE	t100_6	ref	colidx	colidx	5	test.t10_6.col	10	Using where
+1	SIMPLE	t10_7	eq_ref	PRIMARY	PRIMARY	4	test.t100_6.col	1	Using where
+1	SIMPLE	t100_7	ref	colidx	colidx	5	test.t10_7.col	10	Using where
+1	SIMPLE	t10_8	eq_ref	PRIMARY	PRIMARY	4	test.t100_7.col	1	
+### Opt_partial_plans: 692133
+FLUSH STATUS;
+#
+# Chain test c: (...,colidx):(col, pk):(col,colidx):(col,...)
+#
+EXPLAIN SELECT * FROM t10_1 JOIN t100_1 ON t10_1.colidx = t100_1.col JOIN t10_2 ON t100_1.pk = t10_2.col JOIN t100_2 ON t10_2.colidx = t100_2.col JOIN t10_3 ON t100_2.pk = t10_3.col JOIN t100_3 ON t10_3.colidx = t100_3.col JOIN t10_4 ON t100_3.pk = t10_4.col JOIN t100_4 ON t10_4.colidx = t100_4.col JOIN t10_5 ON t100_4.pk = t10_5.col JOIN t100_5 ON t10_5.colidx = t100_5.col JOIN t10_6 ON t100_5.pk = t10_6.col JOIN t100_6 ON t10_6.colidx = t100_6.col JOIN t10_7 ON t100_6.pk = t10_7.col JOIN t100_7 ON t10_7.colidx = t100_7.col JOIN t10_8 ON t100_7.pk = t10_8.col;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t10_8	ALL	NULL	NULL	NULL	NULL	10	Using where
+1	SIMPLE	t100_7	eq_ref	PRIMARY	PRIMARY	4	test.t10_8.col	1	Using where
+1	SIMPLE	t10_7	ref	colidx	colidx	5	test.t100_7.col	1	Using where
+1	SIMPLE	t100_6	eq_ref	PRIMARY	PRIMARY	4	test.t10_7.col	1	Using where
+1	SIMPLE	t10_6	ref	colidx	colidx	5	test.t100_6.col	1	Using where
+1	SIMPLE	t100_5	eq_ref	PRIMARY	PRIMARY	4	test.t10_6.col	1	Using where
+1	SIMPLE	t10_5	ref	colidx	colidx	5	test.t100_5.col	1	Using where
+1	SIMPLE	t100_4	eq_ref	PRIMARY	PRIMARY	4	test.t10_5.col	1	Using where
+1	SIMPLE	t10_4	ref	colidx	colidx	5	test.t100_4.col	1	Using where
+1	SIMPLE	t100_3	eq_ref	PRIMARY	PRIMARY	4	test.t10_4.col	1	Using where
+1	SIMPLE	t10_3	ref	colidx	colidx	5	test.t100_3.col	1	Using where
+1	SIMPLE	t100_2	eq_ref	PRIMARY	PRIMARY	4	test.t10_3.col	1	Using where
+1	SIMPLE	t10_2	ref	colidx	colidx	5	test.t100_2.col	1	Using where
+1	SIMPLE	t100_1	eq_ref	PRIMARY	PRIMARY	4	test.t10_2.col	1	Using where
+1	SIMPLE	t10_1	ref	colidx	colidx	5	test.t100_1.col	1	
+### Opt_partial_plans: 12025
+FLUSH STATUS;
+#
+# Chain test d: (...,colidx):(pk, col):(pk,colidx):(pk,col):(pk,...)
+#
+EXPLAIN SELECT * FROM t10_1 JOIN t100_1 ON t10_1.colidx = t100_1.pk JOIN t10_2 ON t100_1.col = t10_2.pk JOIN t100_2 ON t10_2.colidx = t100_2.pk JOIN t10_3 ON t100_2.col = t10_3.pk JOIN t100_3 ON t10_3.colidx = t100_3.pk JOIN t10_4 ON t100_3.col = t10_4.pk JOIN t100_4 ON t10_4.colidx = t100_4.pk JOIN t10_5 ON t100_4.col = t10_5.pk JOIN t100_5 ON t10_5.colidx = t100_5.pk JOIN t10_6 ON t100_5.col = t10_6.pk JOIN t100_6 ON t10_6.colidx = t100_6.pk JOIN t10_7 ON t100_6.col = t10_7.pk JOIN t100_7 ON t10_7.colidx = t100_7.pk JOIN t10_8 ON t100_7.col = t10_8.pk;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t10_1	ALL	colidx	NULL	NULL	NULL	10	Using where
+1	SIMPLE	t100_1	eq_ref	PRIMARY	PRIMARY	4	test.t10_1.colidx	1	Using where
+1	SIMPLE	t10_2	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t100_1.col	1	Using where
+1	SIMPLE	t100_2	eq_ref	PRIMARY	PRIMARY	4	test.t10_2.colidx	1	Using where
+1	SIMPLE	t10_3	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t100_2.col	1	Using where
+1	SIMPLE	t100_3	eq_ref	PRIMARY	PRIMARY	4	test.t10_3.colidx	1	Using where
+1	SIMPLE	t10_4	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t100_3.col	1	Using where
+1	SIMPLE	t100_4	eq_ref	PRIMARY	PRIMARY	4	test.t10_4.colidx	1	Using where
+1	SIMPLE	t10_5	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t100_4.col	1	Using where
+1	SIMPLE	t100_5	eq_ref	PRIMARY	PRIMARY	4	test.t10_5.colidx	1	Using where
+1	SIMPLE	t10_6	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t100_5.col	1	Using where
+1	SIMPLE	t100_6	eq_ref	PRIMARY	PRIMARY	4	test.t10_6.colidx	1	Using where
+1	SIMPLE	t10_7	eq_ref	PRIMARY,colidx	PRIMARY	4	test.t100_6.col	1	Using where
+1	SIMPLE	t100_7	eq_ref	PRIMARY	PRIMARY	4	test.t10_7.colidx	1	Using where
+1	SIMPLE	t10_8	eq_ref	PRIMARY	PRIMARY	4	test.t100_7.col	1	
+### Opt_partial_plans: 1445
+FLUSH STATUS;
+#
+# Cleanup after TEST 2
+#
+DROP TABLE tbl10, tbl100;
+DROP TABLE t10_1,t10_2,t10_3,t10_4,t10_5,t10_6,t10_7,t10_8,t10_9;
+DROP TABLE t100_1,t100_2,t100_3,t100_4,t100_5,t100_6,t100_7,t100_8,t100_9;

=== modified file 'mysql-test/r/join_cache_bka.result'
--- a/mysql-test/r/join_cache_bka.result	2012-02-21 10:31:44 +0000
+++ b/mysql-test/r/join_cache_bka.result	2012-02-23 11:22:34 +0000
@@ -2387,33 +2387,33 @@ WHERE t3.c1 = SOME (SELECT t1.c2_key FRO
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 = ANY (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 NOT IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index; Start temporary
-1	PRIMARY	t1	ALL	col_int_key	NULL	NULL	NULL	1	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t1	ALL	col_int_key	NULL	NULL	NULL	1	Start temporary
+1	PRIMARY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 1	PRIMARY	t3	ref	k1	k1	5	test.t1.c2_key	1	Using index; End temporary
 SELECT t3.c1 FROM t3
 WHERE t3.c1 = SOME (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)

=== modified file 'mysql-test/r/join_cache_bka_nixbnl.result'
--- a/mysql-test/r/join_cache_bka_nixbnl.result	2012-02-21 10:31:44 +0000
+++ b/mysql-test/r/join_cache_bka_nixbnl.result	2012-02-23 11:22:34 +0000
@@ -2387,33 +2387,33 @@ WHERE t3.c1 = SOME (SELECT t1.c2_key FRO
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 = ANY (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 NOT IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index; Start temporary
-1	PRIMARY	t1	ALL	col_int_key	NULL	NULL	NULL	1	Using where
+1	PRIMARY	t1	ALL	col_int_key	NULL	NULL	NULL	1	Start temporary
+1	PRIMARY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 1	PRIMARY	t3	ref	k1	k1	5	test.t1.c2_key	1	Using index; End temporary
 SELECT t3.c1 FROM t3
 WHERE t3.c1 = SOME (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)

=== modified file 'mysql-test/r/join_cache_bkaunique.result'
--- a/mysql-test/r/join_cache_bkaunique.result	2012-02-21 10:31:44 +0000
+++ b/mysql-test/r/join_cache_bkaunique.result	2012-02-23 11:22:34 +0000
@@ -2388,33 +2388,33 @@ WHERE t3.c1 = SOME (SELECT t1.c2_key FRO
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 = ANY (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 NOT IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index; Start temporary
-1	PRIMARY	t1	ALL	col_int_key	NULL	NULL	NULL	1	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t1	ALL	col_int_key	NULL	NULL	NULL	1	Start temporary
+1	PRIMARY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 1	PRIMARY	t3	ref	k1	k1	5	test.t1.c2_key	1	Using index; End temporary
 SELECT t3.c1 FROM t3
 WHERE t3.c1 = SOME (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)

=== modified file 'mysql-test/r/join_cache_bnl.result'
--- a/mysql-test/r/join_cache_bnl.result	2012-02-21 10:31:44 +0000
+++ b/mysql-test/r/join_cache_bnl.result	2012-02-23 11:22:34 +0000
@@ -2388,33 +2388,33 @@ WHERE t3.c1 = SOME (SELECT t1.c2_key FRO
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 = ANY (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 NOT IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index; Start temporary
-1	PRIMARY	t1	ALL	col_int_key	NULL	NULL	NULL	1	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t1	ALL	col_int_key	NULL	NULL	NULL	1	Start temporary
+1	PRIMARY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 1	PRIMARY	t3	ref	k1	k1	5	test.t1.c2_key	1	Using index; End temporary
 SELECT t3.c1 FROM t3
 WHERE t3.c1 = SOME (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)

=== modified file 'mysql-test/r/join_cache_nojb.result'
--- a/mysql-test/r/join_cache_nojb.result	2012-02-21 10:31:44 +0000
+++ b/mysql-test/r/join_cache_nojb.result	2012-02-23 11:22:34 +0000
@@ -2388,33 +2388,33 @@ WHERE t3.c1 = SOME (SELECT t1.c2_key FRO
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 = ANY (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)
 XOR TRUE;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 NOT IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	index	NULL	k1	5	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index
 2	DEPENDENT SUBQUERY	t1	ref	col_int_key	col_int_key	4	func	1	Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 explain SELECT t3.c1 FROM t3
 WHERE t3.c1 IN (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	index	PRIMARY	PRIMARY	4	NULL	1	Using index; Start temporary
-1	PRIMARY	t1	ALL	col_int_key	NULL	NULL	NULL	1	Using where
+1	PRIMARY	t1	ALL	col_int_key	NULL	NULL	NULL	1	Start temporary
+1	PRIMARY	t2	ALL	PRIMARY	NULL	NULL	NULL	1	Range checked for each record (index map: 0x1)
 1	PRIMARY	t3	ref	k1	k1	5	test.t1.c2_key	1	Using index; End temporary
 SELECT t3.c1 FROM t3
 WHERE t3.c1 = SOME (SELECT t1.c2_key FROM t2 JOIN t1 ON t2.pk < t1.c1)

=== modified file 'mysql-test/r/join_nested.result'
--- a/mysql-test/r/join_nested.result	2012-01-20 15:30:14 +0000
+++ b/mysql-test/r/join_nested.result	2012-02-23 11:22:34 +0000
@@ -546,8 +546,8 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	t0	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where
 1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (Block Nested Loop)
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (Block Nested Loop)
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where; Using join buffer (Block Nested Loop)
 1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where; Using join buffer (Block Nested Loop)
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where; Using join buffer (Block Nested Loop)
 1	SIMPLE	t5	ALL	NULL	NULL	NULL	NULL	3	100.00	Using join buffer (Block Nested Loop)
 1	SIMPLE	t7	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where; Using join buffer (Block Nested Loop)
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (Block Nested Loop)

=== modified file 'mysql-test/r/join_nested_bka.result'
--- a/mysql-test/r/join_nested_bka.result	2012-01-20 15:30:14 +0000
+++ b/mysql-test/r/join_nested_bka.result	2012-02-23 11:22:34 +0000
@@ -547,8 +547,8 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	t0	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where
 1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (Block Nested Loop)
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (Block Nested Loop)
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where; Using join buffer (Block Nested Loop)
 1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where; Using join buffer (Block Nested Loop)
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where; Using join buffer (Block Nested Loop)
 1	SIMPLE	t5	ALL	NULL	NULL	NULL	NULL	3	100.00	Using join buffer (Block Nested Loop)
 1	SIMPLE	t7	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where; Using join buffer (Block Nested Loop)
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (Block Nested Loop)

=== modified file 'mysql-test/r/join_nested_bka_nixbnl.result'
--- a/mysql-test/r/join_nested_bka_nixbnl.result	2012-01-20 15:30:14 +0000
+++ b/mysql-test/r/join_nested_bka_nixbnl.result	2012-02-23 11:22:34 +0000
@@ -547,8 +547,8 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	t0	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where
 1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where
 1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where
 1	SIMPLE	t5	ALL	NULL	NULL	NULL	NULL	3	100.00	
 1	SIMPLE	t7	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where
 1	SIMPLE	t6	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where

=== modified file 'mysql-test/r/subquery_all.result'
--- a/mysql-test/r/subquery_all.result	2012-02-08 15:25:17 +0000
+++ b/mysql-test/r/subquery_all.result	2012-02-23 11:22:34 +0000
@@ -904,10 +904,10 @@ a	t1.a in (select t2.a from t2,t3 where 
 explain extended SELECT t1.a, t1.a in (select t2.a from t2,t3 where t3.a=t2.a) FROM t1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	index	NULL	PRIMARY	4	NULL	4	100.00	Using index
-2	SUBQUERY	t2	index	a	a	5	NULL	3	100.00	Using index
-2	SUBQUERY	t3	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (Block Nested Loop)
+2	SUBQUERY	t3	ALL	NULL	NULL	NULL	NULL	3	100.00	
+2	SUBQUERY	t2	index	a	a	5	NULL	3	100.00	Using where; Using index; Using join buffer (Block Nested Loop)
 Warnings:
-Note	1003	/* select#1 */ select `test`.`t1`.`a` AS `a`,<in_optimizer>(`test`.`t1`.`a`,`test`.`t1`.`a` in ( <materialize> (/* select#2 */ select `test`.`t2`.`a` from `test`.`t2` join `test`.`t3` where (`test`.`t3`.`a` = `test`.`t2`.`a`) ), <primary_index_lookup>(`test`.`t1`.`a` in <temporary table> on distinct_key where ((`test`.`t1`.`a` = `materialized subselect`.`a`))))) AS `t1.a in (select t2.a from t2,t3 where t3.a=t2.a)` from `test`.`t1`
+Note	1003	/* select#1 */ select `test`.`t1`.`a` AS `a`,<in_optimizer>(`test`.`t1`.`a`,`test`.`t1`.`a` in ( <materialize> (/* select#2 */ select `test`.`t2`.`a` from `test`.`t2` join `test`.`t3` where (`test`.`t2`.`a` = `test`.`t3`.`a`) ), <primary_index_lookup>(`test`.`t1`.`a` in <temporary table> on distinct_key where ((`test`.`t1`.`a` = `materialized subselect`.`a`))))) AS `t1.a in (select t2.a from t2,t3 where t3.a=t2.a)` from `test`.`t1`
 drop table t1,t2,t3;
 create table t1 (a float);
 select 10.5 IN (SELECT * from t1 LIMIT 1);

=== modified file 'mysql-test/r/subquery_all_bka.result'
--- a/mysql-test/r/subquery_all_bka.result	2012-02-08 15:25:17 +0000
+++ b/mysql-test/r/subquery_all_bka.result	2012-02-23 11:22:34 +0000
@@ -905,10 +905,10 @@ a	t1.a in (select t2.a from t2,t3 where 
 explain extended SELECT t1.a, t1.a in (select t2.a from t2,t3 where t3.a=t2.a) FROM t1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t1	index	NULL	PRIMARY	4	NULL	4	100.00	Using index
-2	SUBQUERY	t2	index	a	a	5	NULL	3	100.00	Using index
-2	SUBQUERY	t3	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (Block Nested Loop)
+2	SUBQUERY	t3	ALL	NULL	NULL	NULL	NULL	3	100.00	
+2	SUBQUERY	t2	index	a	a	5	NULL	3	100.00	Using where; Using index; Using join buffer (Block Nested Loop)
 Warnings:
-Note	1003	/* select#1 */ select `test`.`t1`.`a` AS `a`,<in_optimizer>(`test`.`t1`.`a`,`test`.`t1`.`a` in ( <materialize> (/* select#2 */ select `test`.`t2`.`a` from `test`.`t2` join `test`.`t3` where (`test`.`t3`.`a` = `test`.`t2`.`a`) ), <primary_index_lookup>(`test`.`t1`.`a` in <temporary table> on distinct_key where ((`test`.`t1`.`a` = `materialized subselect`.`a`))))) AS `t1.a in (select t2.a from t2,t3 where t3.a=t2.a)` from `test`.`t1`
+Note	1003	/* select#1 */ select `test`.`t1`.`a` AS `a`,<in_optimizer>(`test`.`t1`.`a`,`test`.`t1`.`a` in ( <materialize> (/* select#2 */ select `test`.`t2`.`a` from `test`.`t2` join `test`.`t3` where (`test`.`t2`.`a` = `test`.`t3`.`a`) ), <primary_index_lookup>(`test`.`t1`.`a` in <temporary table> on distinct_key where ((`test`.`t1`.`a` = `materialized subselect`.`a`))))) AS `t1.a in (select t2.a from t2,t3 where t3.a=t2.a)` from `test`.`t1`
 drop table t1,t2,t3;
 create table t1 (a float);
 select 10.5 IN (SELECT * from t1 LIMIT 1);

=== modified file 'mysql-test/r/subquery_mat_all.result'
--- a/mysql-test/r/subquery_mat_all.result	2012-02-08 15:25:17 +0000
+++ b/mysql-test/r/subquery_mat_all.result	2012-02-23 11:22:34 +0000
@@ -630,10 +630,10 @@ insert into t2 values (1,10);
 explain extended
 select a from t1 where a in (select c from t2 where d >= 20);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	t1	index	it1a	it1a	4	NULL	7	100.00	Using index
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	7	100.00	Using where; Materialize
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	7	100.00	Using where; Materialize; Scan
+1	PRIMARY	t1	ref	it1a	it1a	4	test.t2.c	2	100.00	Using index
 Warnings:
-Note	1003	/* select#1 */ select `test`.`t1`.`a` AS `a` from `test`.`t1` semi join (`test`.`t2`) where ((`test`.`t2`.`c` = `test`.`t1`.`a`) and (`test`.`t2`.`d` >= 20))
+Note	1003	/* select#1 */ select `test`.`t1`.`a` AS `a` from `test`.`t1` semi join (`test`.`t2`) where ((`test`.`t1`.`a` = `test`.`t2`.`c`) and (`test`.`t2`.`d` >= 20))
 select a from t1 where a in (select c from t2 where d >= 20);
 a
 2
@@ -682,12 +682,12 @@ explain extended
 select a from t1
 where a in (select c from t2 where d >= some(select e from t3 where b=e));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	t1	index	it1a,iab	iab	8	NULL	7	100.00	Using index
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	7	100.00	Using where; FirstMatch(t1); Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	7	100.00	Start temporary
+1	PRIMARY	t1	ref	it1a,iab	iab	4	test.t2.c	1	100.00	Using where; Using index; End temporary
 3	DEPENDENT SUBQUERY	t3	ALL	NULL	NULL	NULL	NULL	4	100.00	Using where
 Warnings:
 Note	1276	Field or reference 'test.t1.b' of SELECT #3 was resolved in SELECT #1
-Note	1003	/* select#1 */ select `test`.`t1`.`a` AS `a` from `test`.`t1` semi join (`test`.`t2`) where ((`test`.`t2`.`c` = `test`.`t1`.`a`) and <nop>(<in_optimizer>(`test`.`t2`.`d`,<exists>(/* select#3 */ select 1 from `test`.`t3` where ((`test`.`t1`.`b` = `test`.`t3`.`e`) and (<cache>(`test`.`t2`.`d`) >= `test`.`t3`.`e`))))))
+Note	1003	/* select#1 */ select `test`.`t1`.`a` AS `a` from `test`.`t1` semi join (`test`.`t2`) where ((`test`.`t1`.`a` = `test`.`t2`.`c`) and <nop>(<in_optimizer>(`test`.`t2`.`d`,<exists>(/* select#3 */ select 1 from `test`.`t3` where ((`test`.`t1`.`b` = `test`.`t3`.`e`) and (<cache>(`test`.`t2`.`d`) >= `test`.`t3`.`e`))))))
 select a from t1
 where a in (select c from t2 where d >= some(select e from t3 where b=e));
 a

=== modified file 'mysql-test/r/subquery_sj_dupsweed.result'
--- a/mysql-test/r/subquery_sj_dupsweed.result	2012-02-16 08:51:53 +0000
+++ b/mysql-test/r/subquery_sj_dupsweed.result	2012-02-23 11:22:34 +0000
@@ -5039,9 +5039,9 @@ WHERE PNUM IN
 FROM t2
 WHERE PTYPE = 'Design'));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 PREPARE stmt FROM "EXPLAIN SELECT EMPNAME
 FROM t1
 WHERE EMPNUM IN
@@ -5053,14 +5053,14 @@ WHERE EMPNUM IN
         WHERE PTYPE = 'Design'))";
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 DEALLOCATE PREPARE stmt;
 DROP INDEX t1_IDX ON t1;
 EXPLAIN SELECT EMPNAME
@@ -6630,8 +6630,8 @@ AND grandparent1.col_varchar_key IS NOT 
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
 2	DEPENDENT SUBQUERY	parent1	ALL	NULL	NULL	NULL	NULL	20	Start temporary
-2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where
-2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index; End temporary
+2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index
+2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where; End temporary
 SELECT *
 FROM t1
 WHERE g1 NOT IN
@@ -7532,8 +7532,8 @@ id	select_type	table	type	possible_keys	
 1	PRIMARY	GP2	system	NULL	NULL	NULL	NULL	1	
 1	PRIMARY	GP1	ALL	NULL	NULL	NULL	NULL	3	Using where
 2	DEPENDENT SUBQUERY	t2	index	col_varchar_key	col_varchar_key	4	NULL	1	Using index; Start temporary
-2	DEPENDENT SUBQUERY	t3	ref	col_varchar_key	col_varchar_key	4	test.t2.col_varchar_key	2	Using index
-2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; End temporary; Using join buffer (Block Nested Loop)
+2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; Using join buffer (Block Nested Loop)
+2	DEPENDENT SUBQUERY	t3	index	col_varchar_key	col_varchar_key	4	NULL	1	Using where; Using index; End temporary; Using join buffer (Block Nested Loop)
 SELECT GP1.id
 FROM t1 AS GP1 JOIN t3 AS GP2
 ON GP2.col_varchar_key <> GP1.col_varchar_nokey

=== modified file 'mysql-test/r/subquery_sj_dupsweed_bka.result'
--- a/mysql-test/r/subquery_sj_dupsweed_bka.result	2012-02-16 08:51:53 +0000
+++ b/mysql-test/r/subquery_sj_dupsweed_bka.result	2012-02-23 11:22:34 +0000
@@ -5040,9 +5040,9 @@ WHERE PNUM IN
 FROM t2
 WHERE PTYPE = 'Design'));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 PREPARE stmt FROM "EXPLAIN SELECT EMPNAME
 FROM t1
 WHERE EMPNUM IN
@@ -5054,14 +5054,14 @@ WHERE EMPNUM IN
         WHERE PTYPE = 'Design'))";
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 DEALLOCATE PREPARE stmt;
 DROP INDEX t1_IDX ON t1;
 EXPLAIN SELECT EMPNAME
@@ -6631,8 +6631,8 @@ AND grandparent1.col_varchar_key IS NOT 
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
 2	DEPENDENT SUBQUERY	parent1	ALL	NULL	NULL	NULL	NULL	20	Start temporary
-2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where
-2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index; End temporary
+2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index
+2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where; End temporary
 SELECT *
 FROM t1
 WHERE g1 NOT IN
@@ -7533,8 +7533,8 @@ id	select_type	table	type	possible_keys	
 1	PRIMARY	GP2	system	NULL	NULL	NULL	NULL	1	
 1	PRIMARY	GP1	ALL	NULL	NULL	NULL	NULL	3	Using where
 2	DEPENDENT SUBQUERY	t2	index	col_varchar_key	col_varchar_key	4	NULL	1	Using index; Start temporary
-2	DEPENDENT SUBQUERY	t3	ref	col_varchar_key	col_varchar_key	4	test.t2.col_varchar_key	2	Using index
-2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; End temporary; Using join buffer (Block Nested Loop)
+2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; Using join buffer (Block Nested Loop)
+2	DEPENDENT SUBQUERY	t3	index	col_varchar_key	col_varchar_key	4	NULL	1	Using where; Using index; End temporary; Using join buffer (Block Nested Loop)
 SELECT GP1.id
 FROM t1 AS GP1 JOIN t3 AS GP2
 ON GP2.col_varchar_key <> GP1.col_varchar_nokey

=== modified file 'mysql-test/r/subquery_sj_dupsweed_bka_nixbnl.result'
--- a/mysql-test/r/subquery_sj_dupsweed_bka_nixbnl.result	2012-02-16 08:51:53 +0000
+++ b/mysql-test/r/subquery_sj_dupsweed_bka_nixbnl.result	2012-02-23 11:22:34 +0000
@@ -5040,9 +5040,9 @@ WHERE PNUM IN
 FROM t2
 WHERE PTYPE = 'Design'));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; End temporary
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ref	t1_IDX	t1_IDX	3	test.t3.EMPNUM	2	
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary
 PREPARE stmt FROM "EXPLAIN SELECT EMPNAME
 FROM t1
 WHERE EMPNUM IN
@@ -5054,14 +5054,14 @@ WHERE EMPNUM IN
         WHERE PTYPE = 'Design'))";
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; End temporary
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ref	t1_IDX	t1_IDX	3	test.t3.EMPNUM	2	
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; End temporary
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	SIMPLE	t1	ref	t1_IDX	t1_IDX	3	test.t3.EMPNUM	2	
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary
 DEALLOCATE PREPARE stmt;
 DROP INDEX t1_IDX ON t1;
 EXPLAIN SELECT EMPNAME
@@ -6631,8 +6631,8 @@ AND grandparent1.col_varchar_key IS NOT 
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
 2	DEPENDENT SUBQUERY	parent1	ALL	NULL	NULL	NULL	NULL	20	Start temporary
-2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where
-2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index; End temporary
+2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index
+2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where; End temporary
 SELECT *
 FROM t1
 WHERE g1 NOT IN

=== modified file 'mysql-test/r/subquery_sj_dupsweed_bkaunique.result'
--- a/mysql-test/r/subquery_sj_dupsweed_bkaunique.result	2012-02-16 08:51:53 +0000
+++ b/mysql-test/r/subquery_sj_dupsweed_bkaunique.result	2012-02-23 11:22:34 +0000
@@ -5041,9 +5041,9 @@ WHERE PNUM IN
 FROM t2
 WHERE PTYPE = 'Design'));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 PREPARE stmt FROM "EXPLAIN SELECT EMPNAME
 FROM t1
 WHERE EMPNUM IN
@@ -5055,14 +5055,14 @@ WHERE EMPNUM IN
         WHERE PTYPE = 'Design'))";
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 DEALLOCATE PREPARE stmt;
 DROP INDEX t1_IDX ON t1;
 EXPLAIN SELECT EMPNAME
@@ -6632,8 +6632,8 @@ AND grandparent1.col_varchar_key IS NOT 
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
 2	DEPENDENT SUBQUERY	parent1	ALL	NULL	NULL	NULL	NULL	20	Start temporary
-2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where
-2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index; End temporary
+2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index
+2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where; End temporary
 SELECT *
 FROM t1
 WHERE g1 NOT IN
@@ -7534,8 +7534,8 @@ id	select_type	table	type	possible_keys	
 1	PRIMARY	GP2	system	NULL	NULL	NULL	NULL	1	
 1	PRIMARY	GP1	ALL	NULL	NULL	NULL	NULL	3	Using where
 2	DEPENDENT SUBQUERY	t2	index	col_varchar_key	col_varchar_key	4	NULL	1	Using index; Start temporary
-2	DEPENDENT SUBQUERY	t3	ref	col_varchar_key	col_varchar_key	4	test.t2.col_varchar_key	2	Using index
-2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; End temporary; Using join buffer (Block Nested Loop)
+2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; Using join buffer (Block Nested Loop)
+2	DEPENDENT SUBQUERY	t3	index	col_varchar_key	col_varchar_key	4	NULL	1	Using where; Using index; End temporary; Using join buffer (Block Nested Loop)
 SELECT GP1.id
 FROM t1 AS GP1 JOIN t3 AS GP2
 ON GP2.col_varchar_key <> GP1.col_varchar_nokey

=== modified file 'mysql-test/r/subquery_sj_firstmatch.result'
--- a/mysql-test/r/subquery_sj_firstmatch.result	2012-02-16 08:51:53 +0000
+++ b/mysql-test/r/subquery_sj_firstmatch.result	2012-02-23 11:22:34 +0000
@@ -5040,9 +5040,9 @@ WHERE PNUM IN
 FROM t2
 WHERE PTYPE = 'Design'));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 PREPARE stmt FROM "EXPLAIN SELECT EMPNAME
 FROM t1
 WHERE EMPNUM IN
@@ -5054,14 +5054,14 @@ WHERE EMPNUM IN
         WHERE PTYPE = 'Design'))";
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 DEALLOCATE PREPARE stmt;
 DROP INDEX t1_IDX ON t1;
 EXPLAIN SELECT EMPNAME
@@ -6631,8 +6631,8 @@ AND grandparent1.col_varchar_key IS NOT 
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
 2	DEPENDENT SUBQUERY	parent1	ALL	NULL	NULL	NULL	NULL	20	Start temporary
-2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where
-2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index; End temporary
+2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index
+2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where; End temporary
 SELECT *
 FROM t1
 WHERE g1 NOT IN
@@ -7533,8 +7533,8 @@ id	select_type	table	type	possible_keys	
 1	PRIMARY	GP2	system	NULL	NULL	NULL	NULL	1	
 1	PRIMARY	GP1	ALL	NULL	NULL	NULL	NULL	3	Using where
 2	DEPENDENT SUBQUERY	t2	index	col_varchar_key	col_varchar_key	4	NULL	1	Using index; Start temporary
-2	DEPENDENT SUBQUERY	t3	ref	col_varchar_key	col_varchar_key	4	test.t2.col_varchar_key	2	Using index
-2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; End temporary; Using join buffer (Block Nested Loop)
+2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; Using join buffer (Block Nested Loop)
+2	DEPENDENT SUBQUERY	t3	index	col_varchar_key	col_varchar_key	4	NULL	1	Using where; Using index; End temporary; Using join buffer (Block Nested Loop)
 SELECT GP1.id
 FROM t1 AS GP1 JOIN t3 AS GP2
 ON GP2.col_varchar_key <> GP1.col_varchar_nokey

=== modified file 'mysql-test/r/subquery_sj_firstmatch_bka.result'
--- a/mysql-test/r/subquery_sj_firstmatch_bka.result	2012-02-16 08:51:53 +0000
+++ b/mysql-test/r/subquery_sj_firstmatch_bka.result	2012-02-23 11:22:34 +0000
@@ -5041,9 +5041,9 @@ WHERE PNUM IN
 FROM t2
 WHERE PTYPE = 'Design'));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 PREPARE stmt FROM "EXPLAIN SELECT EMPNAME
 FROM t1
 WHERE EMPNUM IN
@@ -5055,14 +5055,14 @@ WHERE EMPNUM IN
         WHERE PTYPE = 'Design'))";
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 DEALLOCATE PREPARE stmt;
 DROP INDEX t1_IDX ON t1;
 EXPLAIN SELECT EMPNAME
@@ -6632,8 +6632,8 @@ AND grandparent1.col_varchar_key IS NOT 
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
 2	DEPENDENT SUBQUERY	parent1	ALL	NULL	NULL	NULL	NULL	20	Start temporary
-2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where
-2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index; End temporary
+2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index
+2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where; End temporary
 SELECT *
 FROM t1
 WHERE g1 NOT IN
@@ -7534,8 +7534,8 @@ id	select_type	table	type	possible_keys	
 1	PRIMARY	GP2	system	NULL	NULL	NULL	NULL	1	
 1	PRIMARY	GP1	ALL	NULL	NULL	NULL	NULL	3	Using where
 2	DEPENDENT SUBQUERY	t2	index	col_varchar_key	col_varchar_key	4	NULL	1	Using index; Start temporary
-2	DEPENDENT SUBQUERY	t3	ref	col_varchar_key	col_varchar_key	4	test.t2.col_varchar_key	2	Using index
-2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; End temporary; Using join buffer (Block Nested Loop)
+2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; Using join buffer (Block Nested Loop)
+2	DEPENDENT SUBQUERY	t3	index	col_varchar_key	col_varchar_key	4	NULL	1	Using where; Using index; End temporary; Using join buffer (Block Nested Loop)
 SELECT GP1.id
 FROM t1 AS GP1 JOIN t3 AS GP2
 ON GP2.col_varchar_key <> GP1.col_varchar_nokey

=== modified file 'mysql-test/r/subquery_sj_firstmatch_bka_nixbnl.result'
--- a/mysql-test/r/subquery_sj_firstmatch_bka_nixbnl.result	2012-02-16 08:51:53 +0000
+++ b/mysql-test/r/subquery_sj_firstmatch_bka_nixbnl.result	2012-02-23 11:22:34 +0000
@@ -5041,9 +5041,9 @@ WHERE PNUM IN
 FROM t2
 WHERE PTYPE = 'Design'));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; FirstMatch(t1)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ref	t1_IDX	t1_IDX	3	test.t3.EMPNUM	2	
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary
 PREPARE stmt FROM "EXPLAIN SELECT EMPNAME
 FROM t1
 WHERE EMPNUM IN
@@ -5055,14 +5055,14 @@ WHERE EMPNUM IN
         WHERE PTYPE = 'Design'))";
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; FirstMatch(t1)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ref	t1_IDX	t1_IDX	3	test.t3.EMPNUM	2	
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; FirstMatch(t1)
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	SIMPLE	t1	ref	t1_IDX	t1_IDX	3	test.t3.EMPNUM	2	
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary
 DEALLOCATE PREPARE stmt;
 DROP INDEX t1_IDX ON t1;
 EXPLAIN SELECT EMPNAME
@@ -6632,8 +6632,8 @@ AND grandparent1.col_varchar_key IS NOT 
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
 2	DEPENDENT SUBQUERY	parent1	ALL	NULL	NULL	NULL	NULL	20	Start temporary
-2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where
-2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index; End temporary
+2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index
+2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where; End temporary
 SELECT *
 FROM t1
 WHERE g1 NOT IN

=== modified file 'mysql-test/r/subquery_sj_firstmatch_bkaunique.result'
--- a/mysql-test/r/subquery_sj_firstmatch_bkaunique.result	2012-02-16 08:51:53 +0000
+++ b/mysql-test/r/subquery_sj_firstmatch_bkaunique.result	2012-02-23 11:22:34 +0000
@@ -5042,9 +5042,9 @@ WHERE PNUM IN
 FROM t2
 WHERE PTYPE = 'Design'));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 PREPARE stmt FROM "EXPLAIN SELECT EMPNAME
 FROM t1
 WHERE EMPNUM IN
@@ -5056,14 +5056,14 @@ WHERE EMPNUM IN
         WHERE PTYPE = 'Design'))";
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 DEALLOCATE PREPARE stmt;
 DROP INDEX t1_IDX ON t1;
 EXPLAIN SELECT EMPNAME
@@ -6633,8 +6633,8 @@ AND grandparent1.col_varchar_key IS NOT 
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
 2	DEPENDENT SUBQUERY	parent1	ALL	NULL	NULL	NULL	NULL	20	Start temporary
-2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where
-2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index; End temporary
+2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index
+2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where; End temporary
 SELECT *
 FROM t1
 WHERE g1 NOT IN
@@ -7535,8 +7535,8 @@ id	select_type	table	type	possible_keys	
 1	PRIMARY	GP2	system	NULL	NULL	NULL	NULL	1	
 1	PRIMARY	GP1	ALL	NULL	NULL	NULL	NULL	3	Using where
 2	DEPENDENT SUBQUERY	t2	index	col_varchar_key	col_varchar_key	4	NULL	1	Using index; Start temporary
-2	DEPENDENT SUBQUERY	t3	ref	col_varchar_key	col_varchar_key	4	test.t2.col_varchar_key	2	Using index
-2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; End temporary; Using join buffer (Block Nested Loop)
+2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	3	Using where; Using join buffer (Block Nested Loop)
+2	DEPENDENT SUBQUERY	t3	index	col_varchar_key	col_varchar_key	4	NULL	1	Using where; Using index; End temporary; Using join buffer (Block Nested Loop)
 SELECT GP1.id
 FROM t1 AS GP1 JOIN t3 AS GP2
 ON GP2.col_varchar_key <> GP1.col_varchar_nokey

=== modified file 'mysql-test/r/subquery_sj_loosescan.result'
--- a/mysql-test/r/subquery_sj_loosescan.result	2012-02-16 08:51:53 +0000
+++ b/mysql-test/r/subquery_sj_loosescan.result	2012-02-23 11:22:34 +0000
@@ -5040,9 +5040,9 @@ WHERE PNUM IN
 FROM t2
 WHERE PTYPE = 'Design'));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 PREPARE stmt FROM "EXPLAIN SELECT EMPNAME
 FROM t1
 WHERE EMPNUM IN
@@ -5054,14 +5054,14 @@ WHERE EMPNUM IN
         WHERE PTYPE = 'Design'))";
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 DEALLOCATE PREPARE stmt;
 DROP INDEX t1_IDX ON t1;
 EXPLAIN SELECT EMPNAME
@@ -6631,8 +6631,8 @@ AND grandparent1.col_varchar_key IS NOT 
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
 2	DEPENDENT SUBQUERY	parent1	ALL	NULL	NULL	NULL	NULL	20	Start temporary
-2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where
-2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index; End temporary
+2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index
+2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where; End temporary
 SELECT *
 FROM t1
 WHERE g1 NOT IN

=== modified file 'mysql-test/r/subquery_sj_loosescan_bka.result'
--- a/mysql-test/r/subquery_sj_loosescan_bka.result	2012-02-16 08:51:53 +0000
+++ b/mysql-test/r/subquery_sj_loosescan_bka.result	2012-02-23 11:22:34 +0000
@@ -5041,9 +5041,9 @@ WHERE PNUM IN
 FROM t2
 WHERE PTYPE = 'Design'));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 PREPARE stmt FROM "EXPLAIN SELECT EMPNAME
 FROM t1
 WHERE EMPNUM IN
@@ -5055,14 +5055,14 @@ WHERE EMPNUM IN
         WHERE PTYPE = 'Design'))";
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 DEALLOCATE PREPARE stmt;
 DROP INDEX t1_IDX ON t1;
 EXPLAIN SELECT EMPNAME
@@ -6632,8 +6632,8 @@ AND grandparent1.col_varchar_key IS NOT 
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
 2	DEPENDENT SUBQUERY	parent1	ALL	NULL	NULL	NULL	NULL	20	Start temporary
-2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where
-2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index; End temporary
+2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index
+2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where; End temporary
 SELECT *
 FROM t1
 WHERE g1 NOT IN

=== modified file 'mysql-test/r/subquery_sj_loosescan_bka_nixbnl.result'
--- a/mysql-test/r/subquery_sj_loosescan_bka_nixbnl.result	2012-02-16 08:51:53 +0000
+++ b/mysql-test/r/subquery_sj_loosescan_bka_nixbnl.result	2012-02-23 11:22:34 +0000
@@ -5041,9 +5041,9 @@ WHERE PNUM IN
 FROM t2
 WHERE PTYPE = 'Design'));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; End temporary
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ref	t1_IDX	t1_IDX	3	test.t3.EMPNUM	2	
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary
 PREPARE stmt FROM "EXPLAIN SELECT EMPNAME
 FROM t1
 WHERE EMPNUM IN
@@ -5055,14 +5055,14 @@ WHERE EMPNUM IN
         WHERE PTYPE = 'Design'))";
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; End temporary
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ref	t1_IDX	t1_IDX	3	test.t3.EMPNUM	2	
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; End temporary
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	SIMPLE	t1	ref	t1_IDX	t1_IDX	3	test.t3.EMPNUM	2	
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary
 DEALLOCATE PREPARE stmt;
 DROP INDEX t1_IDX ON t1;
 EXPLAIN SELECT EMPNAME
@@ -6632,8 +6632,8 @@ AND grandparent1.col_varchar_key IS NOT 
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
 2	DEPENDENT SUBQUERY	parent1	ALL	NULL	NULL	NULL	NULL	20	Start temporary
-2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where
-2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index; End temporary
+2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index
+2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where; End temporary
 SELECT *
 FROM t1
 WHERE g1 NOT IN

=== modified file 'mysql-test/r/subquery_sj_loosescan_bkaunique.result'
--- a/mysql-test/r/subquery_sj_loosescan_bkaunique.result	2012-02-16 08:51:53 +0000
+++ b/mysql-test/r/subquery_sj_loosescan_bkaunique.result	2012-02-23 11:22:34 +0000
@@ -5042,9 +5042,9 @@ WHERE PNUM IN
 FROM t2
 WHERE PTYPE = 'Design'));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 PREPARE stmt FROM "EXPLAIN SELECT EMPNAME
 FROM t1
 WHERE EMPNUM IN
@@ -5056,14 +5056,14 @@ WHERE EMPNUM IN
         WHERE PTYPE = 'Design'))";
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	PRIMARY	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; Start temporary
-1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Using where; Using join buffer (Block Nested Loop)
-1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; End temporary; Using join buffer (Block Nested Loop)
+1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	12	Start temporary
+1	SIMPLE	t1	ALL	t1_IDX	NULL	NULL	NULL	5	Using where; Using join buffer (Block Nested Loop)
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	6	Using where; End temporary; Using join buffer (Block Nested Loop)
 DEALLOCATE PREPARE stmt;
 DROP INDEX t1_IDX ON t1;
 EXPLAIN SELECT EMPNAME
@@ -6633,8 +6633,8 @@ AND grandparent1.col_varchar_key IS NOT 
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where
 2	DEPENDENT SUBQUERY	parent1	ALL	NULL	NULL	NULL	NULL	20	Start temporary
-2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where
-2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index; End temporary
+2	DEPENDENT SUBQUERY	parent2	eq_ref	PRIMARY	PRIMARY	4	test.parent1.pk	1	Using index
+2	DEPENDENT SUBQUERY	grandparent1	ref	col_varchar_key	col_varchar_key	3	test.parent1.col_varchar_nokey	1	Using where; End temporary
 SELECT *
 FROM t1
 WHERE g1 NOT IN

=== modified file 'mysql-test/suite/opt_trace/r/bugs_no_prot_all.result'
--- a/mysql-test/suite/opt_trace/r/bugs_no_prot_all.result	2012-02-21 10:31:44 +0000
+++ b/mysql-test/suite/opt_trace/r/bugs_no_prot_all.result	2012-02-23 11:22:34 +0000
@@ -1259,77 +1259,137 @@ ON table2 .col_int_key = table1 .col_int
             "considered_execution_plans": [
               {
                 "database": "test",
-                "table": "table1",
+                "table": "where_subselect_20070",
                 "best_access_path": {
                   "considered_access_paths": [
                     {
-                      "access_type": "ref",
-                      "index": "col_int_key",
-                      "usable": false,
-                      "chosen": false
-                    },
-                    {
                       "access_type": "scan",
-                      "rows": 4,
-                      "cost": 2.0068,
+                      "rows": 6,
+                      "cost": 2.019,
                       "chosen": true
                     }
                   ] /* considered_access_paths */
                 } /* best_access_path */,
-                "cost_for_plan": 2.8068,
-                "rows_for_plan": 4,
+                "cost_for_plan": 3.219,
+                "rows_for_plan": 6,
                 "semijoin_strategy_choice": [
                 ] /* semijoin_strategy_choice */,
                 "rest_of_plan": [
                   {
                     "database": "test",
-                    "table": "table2",
+                    "table": "table1",
                     "best_access_path": {
                       "considered_access_paths": [
                         {
                           "access_type": "ref",
                           "index": "col_int_key",
                           "rows": 2,
-                          "cost": 4.493,
+                          "cost": 6.5395,
                           "chosen": true
                         },
                         {
                           "access_type": "scan",
                           "using_join_cache": true,
                           "rows": 3,
-                          "cost": 2.2071,
+                          "cost": 2.208,
                           "chosen": true
                         }
                       ] /* considered_access_paths */
                     } /* best_access_path */,
-                    "cost_for_plan": 7.414,
-                    "rows_for_plan": 12,
+                    "cost_for_plan": 9.0271,
+                    "rows_for_plan": 18,
                     "semijoin_strategy_choice": [
                     ] /* semijoin_strategy_choice */,
                     "rest_of_plan": [
                       {
                         "database": "test",
-                        "table": "where_subselect_20070",
+                        "table": "table2",
                         "best_access_path": {
                           "considered_access_paths": [
                             {
+                              "access_type": "ref",
+                              "index": "col_int_key",
+                              "rows": 2,
+                              "cost": 18.819,
+                              "chosen": true
+                            },
+                            {
                               "access_type": "scan",
                               "using_join_cache": true,
-                              "rows": 6,
-                              "cost": 2.0209,
+                              "rows": 3,
+                              "cost": 2.2118,
                               "chosen": true
                             }
                           ] /* considered_access_paths */
                         } /* best_access_path */,
-                        "cost_for_plan": 23.835,
-                        "rows_for_plan": 72,
+                        "cost_for_plan": 22.039,
+                        "rows_for_plan": 54,
                         "semijoin_strategy_choice": [
                           {
-                            "strategy": "DuplicatesWeedout",
-                            "cost": 41.435,
+                            "strategy": "FirstMatch",
+                            "recalculate_access_paths_and_cost": {
+                              "tables": [
+                                {
+                                  "database": "test",
+                                  "table": "table1",
+                                  "best_access_path": {
+                                    "considered_access_paths": [
+                                      {
+                                        "access_type": "ref",
+                                        "index": "col_int_key",
+                                        "rows": 2,
+                                        "cost": 6.5395,
+                                        "chosen": true
+                                      },
+                                      {
+                                        "access_type": "scan",
+                                        "rows": 3,
+                                        "cost": 13.241,
+                                        "chosen": false
+                                      }
+                                    ] /* considered_access_paths */
+                                  } /* best_access_path */
+                                },
+                                {
+                                  "database": "test",
+                                  "table": "table2",
+                                  "best_access_path": {
+                                    "considered_access_paths": [
+                                      {
+                                        "access_type": "ref",
+                                        "index": "col_int_key",
+                                        "rows": 2,
+                                        "cost": 12.679,
+                                        "chosen": true
+                                      },
+                                      {
+                                        "access_type": "scan",
+                                        "rows": 3,
+                                        "cost": 26.482,
+                                        "chosen": false
+                                      }
+                                    ] /* considered_access_paths */
+                                  } /* best_access_path */
+                                }
+                              ] /* tables */
+                            } /* recalculate_access_paths_and_cost */,
+                            "cost": 28.838,
                             "rows": 6,
-                            "duplicate_tables_left": true,
                             "chosen": true
+                          },
+                          {
+                            "strategy": "MaterializeLookup",
+                            "cost": 16.233,
+                            "rows": 6,
+                            "duplicate_tables_left": false,
+                            "chosen": true
+                          },
+                          {
+                            "strategy": "DuplicatesWeedout",
+                            "cost": 36.039,
+                            "rows": 6,
+                            "duplicate_tables_left": false,
+                            "chosen": false
                           }
                         ] /* semijoin_strategy_choice */,
                         "chosen": true
@@ -1338,53 +1398,119 @@ ON table2 .col_int_key = table1 .col_int
                   },
                   {
                     "database": "test",
-                    "table": "where_subselect_20070",
+                    "table": "table2",
                     "best_access_path": {
                       "considered_access_paths": [
                         {
+                          "access_type": "ref",
+                          "index": "col_int_key",
+                          "rows": 2,
+                          "cost": 6.5395,
+                          "chosen": true
+                        },
+                        {
                           "access_type": "scan",
                           "using_join_cache": true,
-                          "rows": 6,
-                          "cost": 2.0194,
+                          "rows": 3,
+                          "cost": 2.208,
                           "chosen": true
                         }
                       ] /* considered_access_paths */
                     } /* best_access_path */,
-                    "cost_for_plan": 9.6262,
-                    "rows_for_plan": 24,
+                    "cost_for_plan": 9.0271,
+                    "rows_for_plan": 18,
                     "semijoin_strategy_choice": [
                     ] /* semijoin_strategy_choice */,
                     "rest_of_plan": [
                       {
                         "database": "test",
-                        "table": "table2",
+                        "table": "table1",
                         "best_access_path": {
                           "considered_access_paths": [
                             {
                               "access_type": "ref",
                               "index": "col_int_key",
                               "rows": 2,
-                              "cost": 24.958,
+                              "cost": 18.819,
                               "chosen": true
                             },
                             {
                               "access_type": "scan",
                               "using_join_cache": true,
                               "rows": 3,
-                              "cost": 2.2135,
+                              "cost": 2.2118,
                               "chosen": true
                             }
                           ] /* considered_access_paths */
                         } /* best_access_path */,
-                        "cost_for_plan": 26.24,
-                        "rows_for_plan": 72,
+                        "cost_for_plan": 22.039,
+                        "rows_for_plan": 54,
                         "semijoin_strategy_choice": [
                           {
-                            "strategy": "DuplicatesWeedout",
-                            "cost": 43.84,
+                            "strategy": "FirstMatch",
+                            "recalculate_access_paths_and_cost": {
+                              "tables": [
+                                {
+                                  "database": "test",
+                                  "table": "table2",
+                                  "best_access_path": {
+                                    "considered_access_paths": [
+                                      {
+                                        "access_type": "ref",
+                                        "index": "col_int_key",
+                                        "rows": 2,
+                                        "cost": 6.5395,
+                                        "chosen": true
+                                      },
+                                      {
+                                        "access_type": "scan",
+                                        "rows": 3,
+                                        "cost": 13.241,
+                                        "chosen": false
+                                      }
+                                    ] /* considered_access_paths */
+                                  } /* best_access_path */
+                                },
+                                {
+                                  "database": "test",
+                                  "table": "table1",
+                                  "best_access_path": {
+                                    "considered_access_paths": [
+                                      {
+                                        "access_type": "ref",
+                                        "index": "col_int_key",
+                                        "rows": 2,
+                                        "cost": 12.679,
+                                        "chosen": true
+                                      },
+                                      {
+                                        "access_type": "scan",
+                                        "rows": 3,
+                                        "cost": 26.482,
+                                        "chosen": false
+                                      }
+                                    ] /* considered_access_paths */
+                                  } /* best_access_path */
+                                }
+                              ] /* tables */
+                            } /* recalculate_access_paths_and_cost */,
+                            "cost": 28.838,
                             "rows": 6,
-                            "duplicate_tables_left": true,
                             "chosen": true
+                          },
+                          {
+                            "strategy": "MaterializeLookup",
+                            "cost": 16.233,
+                            "rows": 6,
+                            "duplicate_tables_left": false,
+                            "chosen": true
+                          },
+                          {
+                            "strategy": "DuplicatesWeedout",
+                            "cost": 36.039,
+                            "rows": 6,
+                            "duplicate_tables_left": false,
+                            "chosen": false
                           }
                         ] /* semijoin_strategy_choice */,
                         "pruned_by_cost": true
@@ -1395,14 +1521,13 @@ ON table2 .col_int_key = table1 .col_int
               },
               {
                 "database": "test",
-                "table": "table2",
+                "table": "table1",
                 "best_access_path": {
                   "considered_access_paths": [
                     {
                       "access_type": "ref",
                       "index": "col_int_key",
-                      "rows": 2e308,
-                      "cost": 0,
+                      "usable": false,
                       "chosen": false
                     },
                     {
@@ -1420,50 +1545,50 @@ ON table2 .col_int_key = table1 .col_int
                 "rest_of_plan": [
                   {
                     "database": "test",
-                    "table": "table1",
+                    "table": "where_subselect_20070",
                     "best_access_path": {
                       "considered_access_paths": [
                         {
-                          "access_type": "ref",
-                          "index": "col_int_key",
-                          "rows": 2,
-                          "cost": 4.493,
-                          "chosen": true
-                        },
-                        {
                           "access_type": "scan",
                           "using_join_cache": true,
-                          "rows": 3,
-                          "cost": 2.2071,
+                          "rows": 6,
+                          "cost": 2.0194,
                           "chosen": true
                         }
                       ] /* considered_access_paths */
                     } /* best_access_path */,
-                    "cost_for_plan": 7.414,
-                    "rows_for_plan": 12,
+                    "cost_for_plan": 9.6262,
+                    "rows_for_plan": 24,
                     "semijoin_strategy_choice": [
                     ] /* semijoin_strategy_choice */,
                     "rest_of_plan": [
                       {
                         "database": "test",
-                        "table": "where_subselect_20070",
+                        "table": "table2",
                         "best_access_path": {
                           "considered_access_paths": [
                             {
+                              "access_type": "ref",
+                              "index": "col_int_key",
+                              "rows": 2,
+                              "cost": 24.958,
+                              "chosen": true
+                            },
+                            {
                               "access_type": "scan",
                               "using_join_cache": true,
-                              "rows": 6,
-                              "cost": 2.0209,
+                              "rows": 3,
+                              "cost": 2.2135,
                               "chosen": true
                             }
                           ] /* considered_access_paths */
                         } /* best_access_path */,
-                        "cost_for_plan": 23.835,
+                        "cost_for_plan": 26.24,
                         "rows_for_plan": 72,
                         "semijoin_strategy_choice": [
                           {
                             "strategy": "DuplicatesWeedout",
-                            "cost": 41.435,
+                            "cost": 43.84,
                             "rows": 6,
                             "duplicate_tables_left": true,
                             "chosen": true
@@ -1475,50 +1600,50 @@ ON table2 .col_int_key = table1 .col_int
                   },
                   {
                     "database": "test",
-                    "table": "where_subselect_20070",
+                    "table": "table2",
                     "best_access_path": {
                       "considered_access_paths": [
                         {
+                          "access_type": "ref",
+                          "index": "col_int_key",
+                          "rows": 2,
+                          "cost": 4.493,
+                          "chosen": true
+                        },
+                        {
                           "access_type": "scan",
                           "using_join_cache": true,
-                          "rows": 6,
-                          "cost": 2.0194,
+                          "rows": 3,
+                          "cost": 2.2071,
                           "chosen": true
                         }
                       ] /* considered_access_paths */
                     } /* best_access_path */,
-                    "cost_for_plan": 9.6262,
-                    "rows_for_plan": 24,
+                    "cost_for_plan": 7.414,
+                    "rows_for_plan": 12,
                     "semijoin_strategy_choice": [
                     ] /* semijoin_strategy_choice */,
                     "rest_of_plan": [
                       {
                         "database": "test",
-                        "table": "table1",
+                        "table": "where_subselect_20070",
                         "best_access_path": {
                           "considered_access_paths": [
                             {
-                              "access_type": "ref",
-                              "index": "col_int_key",
-                              "rows": 2,
-                              "cost": 24.958,
-                              "chosen": true
-                            },
-                            {
                               "access_type": "scan",
                               "using_join_cache": true,
-                              "rows": 3,
-                              "cost": 2.2135,
+                              "rows": 6,
+                              "cost": 2.0209,
                               "chosen": true
                             }
                           ] /* considered_access_paths */
                         } /* best_access_path */,
-                        "cost_for_plan": 26.24,
+                        "cost_for_plan": 23.835,
                         "rows_for_plan": 72,
                         "semijoin_strategy_choice": [
                           {
                             "strategy": "DuplicatesWeedout",
-                            "cost": 43.84,
+                            "cost": 41.435,
                             "rows": 6,
                             "duplicate_tables_left": true,
                             "chosen": true
@@ -1532,258 +1657,133 @@ ON table2 .col_int_key = table1 .col_int
               },
               {
                 "database": "test",
-                "table": "where_subselect_20070",
+                "table": "table2",
                 "best_access_path": {
                   "considered_access_paths": [
                     {
+                      "access_type": "ref",
+                      "index": "col_int_key",
+                      "rows": 2e308,
+                      "cost": 0,
+                      "chosen": false
+                    },
+                    {
                       "access_type": "scan",
-                      "rows": 6,
-                      "cost": 2.019,
+                      "rows": 4,
+                      "cost": 2.0068,
                       "chosen": true
                     }
                   ] /* considered_access_paths */
                 } /* best_access_path */,
-                "cost_for_plan": 3.219,
-                "rows_for_plan": 6,
+                "cost_for_plan": 2.8068,
+                "rows_for_plan": 4,
                 "semijoin_strategy_choice": [
                 ] /* semijoin_strategy_choice */,
                 "rest_of_plan": [
                   {
                     "database": "test",
-                    "table": "table1",
+                    "table": "where_subselect_20070",
                     "best_access_path": {
                       "considered_access_paths": [
                         {
-                          "access_type": "ref",
-                          "index": "col_int_key",
-                          "rows": 2,
-                          "cost": 6.5395,
-                          "chosen": true
-                        },
-                        {
                           "access_type": "scan",
                           "using_join_cache": true,
-                          "rows": 3,
-                          "cost": 2.208,
+                          "rows": 6,
+                          "cost": 2.0194,
                           "chosen": true
                         }
                       ] /* considered_access_paths */
                     } /* best_access_path */,
-                    "cost_for_plan": 9.0271,
-                    "rows_for_plan": 18,
+                    "cost_for_plan": 9.6262,
+                    "rows_for_plan": 24,
                     "semijoin_strategy_choice": [
                     ] /* semijoin_strategy_choice */,
                     "rest_of_plan": [
                       {
                         "database": "test",
-                        "table": "table2",
+                        "table": "table1",
                         "best_access_path": {
                           "considered_access_paths": [
                             {
                               "access_type": "ref",
                               "index": "col_int_key",
                               "rows": 2,
-                              "cost": 18.819,
+                              "cost": 24.958,
                               "chosen": true
                             },
                             {
                               "access_type": "scan",
                               "using_join_cache": true,
                               "rows": 3,
-                              "cost": 2.2118,
+                              "cost": 2.2135,
                               "chosen": true
                             }
                           ] /* considered_access_paths */
                         } /* best_access_path */,
-                        "cost_for_plan": 22.039,
-                        "rows_for_plan": 54,
+                        "cost_for_plan": 26.24,
+                        "rows_for_plan": 72,
                         "semijoin_strategy_choice": [
                           {
-                            "strategy": "FirstMatch",
-                            "recalculate_access_paths_and_cost": {
-                              "tables": [
-                                {
-                                  "database": "test",
-                                  "table": "table1",
-                                  "best_access_path": {
-                                    "considered_access_paths": [
-                                      {
-                                        "access_type": "ref",
-                                        "index": "col_int_key",
-                                        "rows": 2,
-                                        "cost": 6.5395,
-                                        "chosen": true
-                                      },
-                                      {
-                                        "access_type": "scan",
-                                        "rows": 3,
-                                        "cost": 13.241,
-                                        "chosen": false
-                                      }
-                                    ] /* considered_access_paths */
-                                  } /* best_access_path */
-                                },
-                                {
-                                  "database": "test",
-                                  "table": "table2",
-                                  "best_access_path": {
-                                    "considered_access_paths": [
-                                      {
-                                        "access_type": "ref",
-                                        "index": "col_int_key",
-                                        "rows": 2,
-                                        "cost": 12.679,
-                                        "chosen": true
-                                      },
-                                      {
-                                        "access_type": "scan",
-                                        "rows": 3,
-                                        "cost": 26.482,
-                                        "chosen": false
-                                      }
-                                    ] /* considered_access_paths */
-                                  } /* best_access_path */
-                                }
-                              ] /* tables */
-                            } /* recalculate_access_paths_and_cost */,
-                            "cost": 28.838,
-                            "rows": 6,
-                            "chosen": true
-                          },
-                          {
-                            "strategy": "MaterializeLookup",
-                            "cost": 16.233,
-                            "rows": 6,
-                            "duplicate_tables_left": false,
-                            "chosen": true
-                          },
-                          {
                             "strategy": "DuplicatesWeedout",
-                            "cost": 36.039,
+                            "cost": 43.84,
                             "rows": 6,
-                            "duplicate_tables_left": false,
-                            "chosen": false
+                            "duplicate_tables_left": true,
+                            "chosen": true
                           }
                         ] /* semijoin_strategy_choice */,
-                        "chosen": true
+                        "pruned_by_cost": true
                       }
                     ] /* rest_of_plan */
                   },
                   {
                     "database": "test",
-                    "table": "table2",
+                    "table": "table1",
                     "best_access_path": {
                       "considered_access_paths": [
                         {
                           "access_type": "ref",
                           "index": "col_int_key",
                           "rows": 2,
-                          "cost": 6.5395,
+                          "cost": 4.493,
                           "chosen": true
                         },
                         {
                           "access_type": "scan",
                           "using_join_cache": true,
                           "rows": 3,
-                          "cost": 2.208,
+                          "cost": 2.2071,
                           "chosen": true
                         }
                       ] /* considered_access_paths */
                     } /* best_access_path */,
-                    "cost_for_plan": 9.0271,
-                    "rows_for_plan": 18,
+                    "cost_for_plan": 7.414,
+                    "rows_for_plan": 12,
                     "semijoin_strategy_choice": [
                     ] /* semijoin_strategy_choice */,
                     "rest_of_plan": [
                       {
                         "database": "test",
-                        "table": "table1",
+                        "table": "where_subselect_20070",
                         "best_access_path": {
                           "considered_access_paths": [
                             {
-                              "access_type": "ref",
-                              "index": "col_int_key",
-                              "rows": 2,
-                              "cost": 18.819,
-                              "chosen": true
-                            },
-                            {
                               "access_type": "scan",
                               "using_join_cache": true,
-                              "rows": 3,
-                              "cost": 2.2118,
+                              "rows": 6,
+                              "cost": 2.0209,
                               "chosen": true
                             }
                           ] /* considered_access_paths */
                         } /* best_access_path */,
-                        "cost_for_plan": 22.039,
-                        "rows_for_plan": 54,
+                        "cost_for_plan": 23.835,
+                        "rows_for_plan": 72,
                         "semijoin_strategy_choice": [
                           {
-                            "strategy": "FirstMatch",
-                            "recalculate_access_paths_and_cost": {
-                              "tables": [
-                                {
-                                  "database": "test",
-                                  "table": "table2",
-                                  "best_access_path": {
-                                    "considered_access_paths": [
-                                      {
-                                        "access_type": "ref",
-                                        "index": "col_int_key",
-                                        "rows": 2,
-                                        "cost": 6.5395,
-                                        "chosen": true
-                                      },
-                                      {
-                                        "access_type": "scan",
-                                        "rows": 3,
-                                        "cost": 13.241,
-                                        "chosen": false
-                                      }
-                                    ] /* considered_access_paths */
-                                  } /* best_access_path */
-                                },
-                                {
-                                  "database": "test",
-                                  "table": "table1",
-                                  "best_access_path": {
-                                    "considered_access_paths": [
-                                      {
-                                        "access_type": "ref",
-                                        "index": "col_int_key",
-                                        "rows": 2,
-                                        "cost": 12.679,
-                                        "chosen": true
-                                      },
-                                      {
-                                        "access_type": "scan",
-                                        "rows": 3,
-                                        "cost": 26.482,
-                                        "chosen": false
-                                      }
-                                    ] /* considered_access_paths */
-                                  } /* best_access_path */
-                                }
-                              ] /* tables */
-                            } /* recalculate_access_paths_and_cost */,
-                            "cost": 28.838,
-                            "rows": 6,
-                            "chosen": true
-                          },
-                          {
-                            "strategy": "MaterializeLookup",
-                            "cost": 16.233,
-                            "rows": 6,
-                            "duplicate_tables_left": false,
-                            "chosen": true
-                          },
-                          {
                             "strategy": "DuplicatesWeedout",
-                            "cost": 36.039,
+                            "cost": 41.435,
                             "rows": 6,
-                            "duplicate_tables_left": false,
-                            "chosen": false
+                            "duplicate_tables_left": true,
+                            "chosen": true
                           }
                         ] /* semijoin_strategy_choice */,
                         "pruned_by_cost": true

=== modified file 'mysql-test/suite/opt_trace/r/bugs_ps_prot_all.result'
--- a/mysql-test/suite/opt_trace/r/bugs_ps_prot_all.result	2012-02-21 10:31:44 +0000
+++ b/mysql-test/suite/opt_trace/r/bugs_ps_prot_all.result	2012-02-23 11:22:34 +0000
@@ -1259,77 +1259,137 @@ ON table2 .col_int_key = table1 .col_int
             "considered_execution_plans": [
               {
                 "database": "test",
-                "table": "table1",
+                "table": "where_subselect_20070",
                 "best_access_path": {
                   "considered_access_paths": [
                     {
-                      "access_type": "ref",
-                      "index": "col_int_key",
-                      "usable": false,
-                      "chosen": false
-                    },
-                    {
                       "access_type": "scan",
-                      "rows": 4,
-                      "cost": 2.0068,
+                      "rows": 6,
+                      "cost": 2.019,
                       "chosen": true
                     }
                   ] /* considered_access_paths */
                 } /* best_access_path */,
-                "cost_for_plan": 2.8068,
-                "rows_for_plan": 4,
+                "cost_for_plan": 3.219,
+                "rows_for_plan": 6,
                 "semijoin_strategy_choice": [
                 ] /* semijoin_strategy_choice */,
                 "rest_of_plan": [
                   {
                     "database": "test",
-                    "table": "table2",
+                    "table": "table1",
                     "best_access_path": {
                       "considered_access_paths": [
                         {
                           "access_type": "ref",
                           "index": "col_int_key",
                           "rows": 2,
-                          "cost": 4.493,
+                          "cost": 6.5395,
                           "chosen": true
                         },
                         {
                           "access_type": "scan",
                           "using_join_cache": true,
                           "rows": 3,
-                          "cost": 2.2071,
+                          "cost": 2.208,
                           "chosen": true
                         }
                       ] /* considered_access_paths */
                     } /* best_access_path */,
-                    "cost_for_plan": 7.414,
-                    "rows_for_plan": 12,
+                    "cost_for_plan": 9.0271,
+                    "rows_for_plan": 18,
                     "semijoin_strategy_choice": [
                     ] /* semijoin_strategy_choice */,
                     "rest_of_plan": [
                       {
                         "database": "test",
-                        "table": "where_subselect_20070",
+                        "table": "table2",
                         "best_access_path": {
                           "considered_access_paths": [
                             {
+                              "access_type": "ref",
+                              "index": "col_int_key",
+                              "rows": 2,
+                              "cost": 18.819,
+                              "chosen": true
+                            },
+                            {
                               "access_type": "scan",
                               "using_join_cache": true,
-                              "rows": 6,
-                              "cost": 2.0209,
+                              "rows": 3,
+                              "cost": 2.2118,
                               "chosen": true
                             }
                           ] /* considered_access_paths */
                         } /* best_access_path */,
-                        "cost_for_plan": 23.835,
-                        "rows_for_plan": 72,
+                        "cost_for_plan": 22.039,
+                        "rows_for_plan": 54,
                         "semijoin_strategy_choice": [
                           {
-                            "strategy": "DuplicatesWeedout",
-                            "cost": 41.435,
+                            "strategy": "FirstMatch",
+                            "recalculate_access_paths_and_cost": {
+                              "tables": [
+                                {
+                                  "database": "test",
+                                  "table": "table1",
+                                  "best_access_path": {
+                                    "considered_access_paths": [
+                                      {
+                                        "access_type": "ref",
+                                        "index": "col_int_key",
+                                        "rows": 2,
+                                        "cost": 6.5395,
+                                        "chosen": true
+                                      },
+                                      {
+                                        "access_type": "scan",
+                                        "rows": 3,
+                                        "cost": 13.241,
+                                        "chosen": false
+                                      }
+                                    ] /* considered_access_paths */
+                                  } /* best_access_path */
+                                },
+                                {
+                                  "database": "test",
+                                  "table": "table2",
+                                  "best_access_path": {
+                                    "considered_access_paths": [
+                                      {
+                                        "access_type": "ref",
+                                        "index": "col_int_key",
+                                        "rows": 2,
+                                        "cost": 12.679,
+                                        "chosen": true
+                                      },
+                                      {
+                                        "access_type": "scan",
+                                        "rows": 3,
+                                        "cost": 26.482,
+                                        "chosen": false
+                                      }
+                                    ] /* considered_access_paths */
+                                  } /* best_access_path */
+                                }
+                              ] /* tables */
+                            } /* recalculate_access_paths_and_cost */,
+                            "cost": 28.838,
                             "rows": 6,
-                            "duplicate_tables_left": true,
                             "chosen": true
+                          },
+                          {
+                            "strategy": "MaterializeLookup",
+                            "cost": 16.233,
+                            "rows": 6,
+                            "duplicate_tables_left": false,
+                            "chosen": true
+                          },
+                          {
+                            "strategy": "DuplicatesWeedout",
+                            "cost": 36.039,
+                            "rows": 6,
+                            "duplicate_tables_left": false,
+                            "chosen": false
                           }
                         ] /* semijoin_strategy_choice */,
                         "chosen": true
@@ -1338,53 +1398,119 @@ ON table2 .col_int_key = table1 .col_int
                   },
                   {
                     "database": "test",
-                    "table": "where_subselect_20070",
+                    "table": "table2",
                     "best_access_path": {
                       "considered_access_paths": [
                         {
+                          "access_type": "ref",
+                          "index": "col_int_key",
+                          "rows": 2,
+                          "cost": 6.5395,
+                          "chosen": true
+                        },
+                        {
                           "access_type": "scan",
                           "using_join_cache": true,
-                          "rows": 6,
-                          "cost": 2.0194,
+                          "rows": 3,
+                          "cost": 2.208,
                           "chosen": true
                         }
                       ] /* considered_access_paths */
                     } /* best_access_path */,
-                    "cost_for_plan": 9.6262,
-                    "rows_for_plan": 24,
+                    "cost_for_plan": 9.0271,
+                    "rows_for_plan": 18,
                     "semijoin_strategy_choice": [
                     ] /* semijoin_strategy_choice */,
                     "rest_of_plan": [
                       {
                         "database": "test",
-                        "table": "table2",
+                        "table": "table1",
                         "best_access_path": {
                           "considered_access_paths": [
                             {
                               "access_type": "ref",
                               "index": "col_int_key",
                               "rows": 2,
-                              "cost": 24.958,
+                              "cost": 18.819,
                               "chosen": true
                             },
                             {
                               "access_type": "scan",
                               "using_join_cache": true,
                               "rows": 3,
-                              "cost": 2.2135,
+                              "cost": 2.2118,
                               "chosen": true
                             }
                           ] /* considered_access_paths */
                         } /* best_access_path */,
-                        "cost_for_plan": 26.24,
-                        "rows_for_plan": 72,
+                        "cost_for_plan": 22.039,
+                        "rows_for_plan": 54,
                         "semijoin_strategy_choice": [
                           {
-                            "strategy": "DuplicatesWeedout",
-                            "cost": 43.84,
+                            "strategy": "FirstMatch",
+                            "recalculate_access_paths_and_cost": {
+                              "tables": [
+                                {
+                                  "database": "test",
+                                  "table": "table2",
+                                  "best_access_path": {
+                                    "considered_access_paths": [
+                                      {
+                                        "access_type": "ref",
+                                        "index": "col_int_key",
+                                        "rows": 2,
+                                        "cost": 6.5395,
+                                        "chosen": true
+                                      },
+                                      {
+                                        "access_type": "scan",
+                                        "rows": 3,
+                                        "cost": 13.241,
+                                        "chosen": false
+                                      }
+                                    ] /* considered_access_paths */
+                                  } /* best_access_path */
+                                },
+                                {
+                                  "database": "test",
+                                  "table": "table1",
+                                  "best_access_path": {
+                                    "considered_access_paths": [
+                                      {
+                                        "access_type": "ref",
+                                        "index": "col_int_key",
+                                        "rows": 2,
+                                        "cost": 12.679,
+                                        "chosen": true
+                                      },
+                                      {
+                                        "access_type": "scan",
+                                        "rows": 3,
+                                        "cost": 26.482,
+                                        "chosen": false
+                                      }
+                                    ] /* considered_access_paths */
+                                  } /* best_access_path */
+                                }
+                              ] /* tables */
+                            } /* recalculate_access_paths_and_cost */,
+                            "cost": 28.838,
                             "rows": 6,
-                            "duplicate_tables_left": true,
                             "chosen": true
+                          },
+                          {
+                            "strategy": "MaterializeLookup",
+                            "cost": 16.233,
+                            "rows": 6,
+                            "duplicate_tables_left": false,
+                            "chosen": true
+                          },
+                          {
+                            "strategy": "DuplicatesWeedout",
+                            "cost": 36.039,
+                            "rows": 6,
+                            "duplicate_tables_left": false,
+                            "chosen": false
                           }
                         ] /* semijoin_strategy_choice */,
                         "pruned_by_cost": true
@@ -1395,14 +1521,13 @@ ON table2 .col_int_key = table1 .col_int
               },
               {
                 "database": "test",
-                "table": "table2",
+                "table": "table1",
                 "best_access_path": {
                   "considered_access_paths": [
                     {
                       "access_type": "ref",
                       "index": "col_int_key",
-                      "rows": 2e308,
-                      "cost": 0,
+                      "usable": false,
                       "chosen": false
                     },
                     {
@@ -1420,50 +1545,50 @@ ON table2 .col_int_key = table1 .col_int
                 "rest_of_plan": [
                   {
                     "database": "test",
-                    "table": "table1",
+                    "table": "where_subselect_20070",
                     "best_access_path": {
                       "considered_access_paths": [
                         {
-                          "access_type": "ref",
-                          "index": "col_int_key",
-                          "rows": 2,
-                          "cost": 4.493,
-                          "chosen": true
-                        },
-                        {
                           "access_type": "scan",
                           "using_join_cache": true,
-                          "rows": 3,
-                          "cost": 2.2071,
+                          "rows": 6,
+                          "cost": 2.0194,
                           "chosen": true
                         }
                       ] /* considered_access_paths */
                     } /* best_access_path */,
-                    "cost_for_plan": 7.414,
-                    "rows_for_plan": 12,
+                    "cost_for_plan": 9.6262,
+                    "rows_for_plan": 24,
                     "semijoin_strategy_choice": [
                     ] /* semijoin_strategy_choice */,
                     "rest_of_plan": [
                       {
                         "database": "test",
-                        "table": "where_subselect_20070",
+                        "table": "table2",
                         "best_access_path": {
                           "considered_access_paths": [
                             {
+                              "access_type": "ref",
+                              "index": "col_int_key",
+                              "rows": 2,
+                              "cost": 24.958,
+                              "chosen": true
+                            },
+                            {
                               "access_type": "scan",
                               "using_join_cache": true,
-                              "rows": 6,
-                              "cost": 2.0209,
+                              "rows": 3,
+                              "cost": 2.2135,
                               "chosen": true
                             }
                           ] /* considered_access_paths */
                         } /* best_access_path */,
-                        "cost_for_plan": 23.835,
+                        "cost_for_plan": 26.24,
                         "rows_for_plan": 72,
                         "semijoin_strategy_choice": [
                           {
                             "strategy": "DuplicatesWeedout",
-                            "cost": 41.435,
+                            "cost": 43.84,
                             "rows": 6,
                             "duplicate_tables_left": true,
                             "chosen": true
@@ -1475,50 +1600,50 @@ ON table2 .col_int_key = table1 .col_int
                   },
                   {
                     "database": "test",
-                    "table": "where_subselect_20070",
+                    "table": "table2",
                     "best_access_path": {
                       "considered_access_paths": [
                         {
+                          "access_type": "ref",
+                          "index": "col_int_key",
+                          "rows": 2,
+                          "cost": 4.493,
+                          "chosen": true
+                        },
+                        {
                           "access_type": "scan",
                           "using_join_cache": true,
-                          "rows": 6,
-                          "cost": 2.0194,
+                          "rows": 3,
+                          "cost": 2.2071,
                           "chosen": true
                         }
                       ] /* considered_access_paths */
                     } /* best_access_path */,
-                    "cost_for_plan": 9.6262,
-                    "rows_for_plan": 24,
+                    "cost_for_plan": 7.414,
+                    "rows_for_plan": 12,
                     "semijoin_strategy_choice": [
                     ] /* semijoin_strategy_choice */,
                     "rest_of_plan": [
                       {
                         "database": "test",
-                        "table": "table1",
+                        "table": "where_subselect_20070",
                         "best_access_path": {
                           "considered_access_paths": [
                             {
-                              "access_type": "ref",
-                              "index": "col_int_key",
-                              "rows": 2,
-                              "cost": 24.958,
-                              "chosen": true
-                            },
-                            {
                               "access_type": "scan",
                               "using_join_cache": true,
-                              "rows": 3,
-                              "cost": 2.2135,
+                              "rows": 6,
+                              "cost": 2.0209,
                               "chosen": true
                             }
                           ] /* considered_access_paths */
                         } /* best_access_path */,
-                        "cost_for_plan": 26.24,
+                        "cost_for_plan": 23.835,
                         "rows_for_plan": 72,
                         "semijoin_strategy_choice": [
                           {
                             "strategy": "DuplicatesWeedout",
-                            "cost": 43.84,
+                            "cost": 41.435,
                             "rows": 6,
                             "duplicate_tables_left": true,
                             "chosen": true
@@ -1532,258 +1657,133 @@ ON table2 .col_int_key = table1 .col_int
               },
               {
                 "database": "test",
-                "table": "where_subselect_20070",
+                "table": "table2",
                 "best_access_path": {
                   "considered_access_paths": [
                     {
+                      "access_type": "ref",
+                      "index": "col_int_key",
+                      "rows": 2e308,
+                      "cost": 0,
+                      "chosen": false
+                    },
+                    {
                       "access_type": "scan",
-                      "rows": 6,
-                      "cost": 2.019,
+                      "rows": 4,
+                      "cost": 2.0068,
                       "chosen": true
                     }
                   ] /* considered_access_paths */
                 } /* best_access_path */,
-                "cost_for_plan": 3.219,
-                "rows_for_plan": 6,
+                "cost_for_plan": 2.8068,
+                "rows_for_plan": 4,
                 "semijoin_strategy_choice": [
                 ] /* semijoin_strategy_choice */,
                 "rest_of_plan": [
                   {
                     "database": "test",
-                    "table": "table1",
+                    "table": "where_subselect_20070",
                     "best_access_path": {
                       "considered_access_paths": [
                         {
-                          "access_type": "ref",
-                          "index": "col_int_key",
-                          "rows": 2,
-                          "cost": 6.5395,
-                          "chosen": true
-                        },
-                        {
                           "access_type": "scan",
                           "using_join_cache": true,
-                          "rows": 3,
-                          "cost": 2.208,
+                          "rows": 6,
+                          "cost": 2.0194,
                           "chosen": true
                         }
                       ] /* considered_access_paths */
                     } /* best_access_path */,
-                    "cost_for_plan": 9.0271,
-                    "rows_for_plan": 18,
+                    "cost_for_plan": 9.6262,
+                    "rows_for_plan": 24,
                     "semijoin_strategy_choice": [
                     ] /* semijoin_strategy_choice */,
                     "rest_of_plan": [
                       {
                         "database": "test",
-                        "table": "table2",
+                        "table": "table1",
                         "best_access_path": {
                           "considered_access_paths": [
                             {
                               "access_type": "ref",
                               "index": "col_int_key",
                               "rows": 2,
-                              "cost": 18.819,
+                              "cost": 24.958,
                               "chosen": true
                             },
                             {
                               "access_type": "scan",
                               "using_join_cache": true,
                               "rows": 3,
-                              "cost": 2.2118,
+                              "cost": 2.2135,
                               "chosen": true
                             }
                           ] /* considered_access_paths */
                         } /* best_access_path */,
-                        "cost_for_plan": 22.039,
-                        "rows_for_plan": 54,
+                        "cost_for_plan": 26.24,
+                        "rows_for_plan": 72,
                         "semijoin_strategy_choice": [
                           {
-                            "strategy": "FirstMatch",
-                            "recalculate_access_paths_and_cost": {
-                              "tables": [
-                                {
-                                  "database": "test",
-                                  "table": "table1",
-                                  "best_access_path": {
-                                    "considered_access_paths": [
-                                      {
-                                        "access_type": "ref",
-                                        "index": "col_int_key",
-                                        "rows": 2,
-                                        "cost": 6.5395,
-                                        "chosen": true
-                                      },
-                                      {
-                                        "access_type": "scan",
-                                        "rows": 3,
-                                        "cost": 13.241,
-                                        "chosen": false
-                                      }
-                                    ] /* considered_access_paths */
-                                  } /* best_access_path */
-                                },
-                                {
-                                  "database": "test",
-                                  "table": "table2",
-                                  "best_access_path": {
-                                    "considered_access_paths": [
-                                      {
-                                        "access_type": "ref",
-                                        "index": "col_int_key",
-                                        "rows": 2,
-                                        "cost": 12.679,
-                                        "chosen": true
-                                      },
-                                      {
-                                        "access_type": "scan",
-                                        "rows": 3,
-                                        "cost": 26.482,
-                                        "chosen": false
-                                      }
-                                    ] /* considered_access_paths */
-                                  } /* best_access_path */
-                                }
-                              ] /* tables */
-                            } /* recalculate_access_paths_and_cost */,
-                            "cost": 28.838,
-                            "rows": 6,
-                            "chosen": true
-                          },
-                          {
-                            "strategy": "MaterializeLookup",
-                            "cost": 16.233,
-                            "rows": 6,
-                            "duplicate_tables_left": false,
-                            "chosen": true
-                          },
-                          {
                             "strategy": "DuplicatesWeedout",
-                            "cost": 36.039,
+                            "cost": 43.84,
                             "rows": 6,
-                            "duplicate_tables_left": false,
-                            "chosen": false
+                            "duplicate_tables_left": true,
+                            "chosen": true
                           }
                         ] /* semijoin_strategy_choice */,
-                        "chosen": true
+                        "pruned_by_cost": true
                       }
                     ] /* rest_of_plan */
                   },
                   {
                     "database": "test",
-                    "table": "table2",
+                    "table": "table1",
                     "best_access_path": {
                       "considered_access_paths": [
                         {
                           "access_type": "ref",
                           "index": "col_int_key",
                           "rows": 2,
-                          "cost": 6.5395,
+                          "cost": 4.493,
                           "chosen": true
                         },
                         {
                           "access_type": "scan",
                           "using_join_cache": true,
                           "rows": 3,
-                          "cost": 2.208,
+                          "cost": 2.2071,
                           "chosen": true
                         }
                       ] /* considered_access_paths */
                     } /* best_access_path */,
-                    "cost_for_plan": 9.0271,
-                    "rows_for_plan": 18,
+                    "cost_for_plan": 7.414,
+                    "rows_for_plan": 12,
                     "semijoin_strategy_choice": [
                     ] /* semijoin_strategy_choice */,
                     "rest_of_plan": [
                       {
                         "database": "test",
-                        "table": "table1",
+                        "table": "where_subselect_20070",
                         "best_access_path": {
                           "considered_access_paths": [
                             {
-                              "access_type": "ref",
-                              "index": "col_int_key",
-                              "rows": 2,
-                              "cost": 18.819,
-                              "chosen": true
-                            },
-                            {
                               "access_type": "scan",
                               "using_join_cache": true,
-                              "rows": 3,
-                              "cost": 2.2118,
+                              "rows": 6,
+                              "cost": 2.0209,
                               "chosen": true
                             }
                           ] /* considered_access_paths */
                         } /* best_access_path */,
-                        "cost_for_plan": 22.039,
-                        "rows_for_plan": 54,
+                        "cost_for_plan": 23.835,
+                        "rows_for_plan": 72,
                         "semijoin_strategy_choice": [
                           {
-                            "strategy": "FirstMatch",
-                            "recalculate_access_paths_and_cost": {
-                              "tables": [
-                                {
-                                  "database": "test",
-                                  "table": "table2",
-                                  "best_access_path": {
-                                    "considered_access_paths": [
-                                      {
-                                        "access_type": "ref",
-                                        "index": "col_int_key",
-                                        "rows": 2,
-                                        "cost": 6.5395,
-                                        "chosen": true
-                                      },
-                                      {
-                                        "access_type": "scan",
-                                        "rows": 3,
-                                        "cost": 13.241,
-                                        "chosen": false
-                                      }
-                                    ] /* considered_access_paths */
-                                  } /* best_access_path */
-                                },
-                                {
-                                  "database": "test",
-                                  "table": "table1",
-                                  "best_access_path": {
-                                    "considered_access_paths": [
-                                      {
-                                        "access_type": "ref",
-                                        "index": "col_int_key",
-                                        "rows": 2,
-                                        "cost": 12.679,
-                                        "chosen": true
-                                      },
-                                      {
-                                        "access_type": "scan",
-                                        "rows": 3,
-                                        "cost": 26.482,
-                                        "chosen": false
-                                      }
-                                    ] /* considered_access_paths */
-                                  } /* best_access_path */
-                                }
-                              ] /* tables */
-                            } /* recalculate_access_paths_and_cost */,
-                            "cost": 28.838,
-                            "rows": 6,
-                            "chosen": true
-                          },
-                          {
-                            "strategy": "MaterializeLookup",
-                            "cost": 16.233,
-                            "rows": 6,
-                            "duplicate_tables_left": false,
-                            "chosen": true
-                          },
-                          {
                             "strategy": "DuplicatesWeedout",
-                            "cost": 36.039,
+                            "cost": 41.435,
                             "rows": 6,
-                            "duplicate_tables_left": false,
-                            "chosen": false
+                            "duplicate_tables_left": true,
+                            "chosen": true
                           }
                         ] /* semijoin_strategy_choice */,
                         "pruned_by_cost": true

=== modified file 'mysql-test/suite/opt_trace/r/subquery_no_prot.result'
--- a/mysql-test/suite/opt_trace/r/subquery_no_prot.result	2012-02-16 13:09:08 +0000
+++ b/mysql-test/suite/opt_trace/r/subquery_no_prot.result	2012-02-23 11:22:34 +0000
@@ -1563,16 +1563,10 @@ field4,field5,field6	{
                                   "considered_execution_plans": [
                                     {
                                       "database": "test",
-                                      "table": "sq1_alias2",
+                                      "table": "sq1_alias3",
                                       "best_access_path": {
                                         "considered_access_paths": [
                                           {
-                                            "access_type": "ref",
-                                            "index": "col_varchar_key",
-                                            "usable": false,
-                                            "chosen": false
-                                          },
-                                          {
                                             "access_type": "scan",
                                             "rows": 3,
                                             "cost": 2.0342,
@@ -1585,14 +1579,21 @@ field4,field5,field6	{
                                       "rest_of_plan": [
                                         {
                                           "database": "test",
-                                          "table": "sq1_alias3",
+                                          "table": "sq1_alias2",
                                           "best_access_path": {
                                             "considered_access_paths": [
                                               {
+                                                "access_type": "ref",
+                                                "index": "col_varchar_key",
+                                                "rows": 1,
+                                                "cost": 4.1,
+                                                "chosen": true
+                                              },
+                                              {
                                                 "access_type": "scan",
                                                 "using_join_cache": true,
                                                 "rows": 3,
-                                                "cost": 2.0345,
+                                                "cost": 2.0344,
                                                 "chosen": true
                                               }
                                             ] /* considered_access_paths */
@@ -1605,10 +1606,16 @@ field4,field5,field6	{
                                     },
                                     {
                                       "database": "test",
-                                      "table": "sq1_alias3",
+                                      "table": "sq1_alias2",
                                       "best_access_path": {
                                         "considered_access_paths": [
                                           {
+                                            "access_type": "ref",
+                                            "index": "col_varchar_key",
+                                            "usable": false,
+                                            "chosen": false
+                                          },
+                                          {
                                             "access_type": "scan",
                                             "rows": 3,
                                             "cost": 2.0342,
@@ -1618,33 +1625,7 @@ field4,field5,field6	{
                                       } /* best_access_path */,
                                       "cost_for_plan": 2.6342,
                                       "rows_for_plan": 3,
-                                      "rest_of_plan": [
-                                        {
-                                          "database": "test",
-                                          "table": "sq1_alias2",
-                                          "best_access_path": {
-                                            "considered_access_paths": [
-                                              {
-                                                "access_type": "ref",
-                                                "index": "col_varchar_key",
-                                                "rows": 1,
-                                                "cost": 4.1,
-                                                "chosen": true
-                                              },
-                                              {
-                                                "access_type": "scan",
-                                                "using_join_cache": true,
-                                                "rows": 3,
-                                                "cost": 2.0344,
-                                                "chosen": true
-                                              }
-                                            ] /* considered_access_paths */
-                                          } /* best_access_path */,
-                                          "cost_for_plan": 6.4686,
-                                          "rows_for_plan": 9,
-                                          "pruned_by_cost": true
-                                        }
-                                      ] /* rest_of_plan */
+                                      "pruned_by_heuristic": true
                                     }
                                   ] /* considered_execution_plans */
                                 }

=== modified file 'mysql-test/suite/opt_trace/r/subquery_ps_prot.result'
--- a/mysql-test/suite/opt_trace/r/subquery_ps_prot.result	2012-02-16 13:09:08 +0000
+++ b/mysql-test/suite/opt_trace/r/subquery_ps_prot.result	2012-02-23 11:22:34 +0000
@@ -1541,16 +1541,10 @@ field4,field5,field6	{
                                   "considered_execution_plans": [
                                     {
                                       "database": "test",
-                                      "table": "sq1_alias2",
+                                      "table": "sq1_alias3",
                                       "best_access_path": {
                                         "considered_access_paths": [
                                           {
-                                            "access_type": "ref",
-                                            "index": "col_varchar_key",
-                                            "usable": false,
-                                            "chosen": false
-                                          },
-                                          {
                                             "access_type": "scan",
                                             "rows": 3,
                                             "cost": 2.0342,
@@ -1563,14 +1557,21 @@ field4,field5,field6	{
                                       "rest_of_plan": [
                                         {
                                           "database": "test",
-                                          "table": "sq1_alias3",
+                                          "table": "sq1_alias2",
                                           "best_access_path": {
                                             "considered_access_paths": [
                                               {
+                                                "access_type": "ref",
+                                                "index": "col_varchar_key",
+                                                "rows": 1,
+                                                "cost": 4.1,
+                                                "chosen": true
+                                              },
+                                              {
                                                 "access_type": "scan",
                                                 "using_join_cache": true,
                                                 "rows": 3,
-                                                "cost": 2.0345,
+                                                "cost": 2.0344,
                                                 "chosen": true
                                               }
                                             ] /* considered_access_paths */
@@ -1583,10 +1584,16 @@ field4,field5,field6	{
                                     },
                                     {
                                       "database": "test",
-                                      "table": "sq1_alias3",
+                                      "table": "sq1_alias2",
                                       "best_access_path": {
                                         "considered_access_paths": [
                                           {
+                                            "access_type": "ref",
+                                            "index": "col_varchar_key",
+                                            "usable": false,
+                                            "chosen": false
+                                          },
+                                          {
                                             "access_type": "scan",
                                             "rows": 3,
                                             "cost": 2.0342,
@@ -1596,33 +1603,7 @@ field4,field5,field6	{
                                       } /* best_access_path */,
                                       "cost_for_plan": 2.6342,
                                       "rows_for_plan": 3,
-                                      "rest_of_plan": [
-                                        {
-                                          "database": "test",
-                                          "table": "sq1_alias2",
-                                          "best_access_path": {
-                                            "considered_access_paths": [
-                                              {
-                                                "access_type": "ref",
-                                                "index": "col_varchar_key",
-                                                "rows": 1,
-                                                "cost": 4.1,
-                                                "chosen": true
-                                              },
-                                              {
-                                                "access_type": "scan",
-                                                "using_join_cache": true,
-                                                "rows": 3,
-                                                "cost": 2.0344,
-                                                "chosen": true
-                                              }
-                                            ] /* considered_access_paths */
-                                          } /* best_access_path */,
-                                          "cost_for_plan": 6.4686,
-                                          "rows_for_plan": 9,
-                                          "pruned_by_cost": true
-                                        }
-                                      ] /* rest_of_plan */
+                                      "pruned_by_heuristic": true
                                     }
                                   ] /* considered_execution_plans */
                                 }

=== added file 'mysql-test/t/greedy_search.test'
--- a/mysql-test/t/greedy_search.test	1970-01-01 00:00:00 +0000
+++ b/mysql-test/t/greedy_search.test	2012-02-23 11:22:34 +0000
@@ -0,0 +1,423 @@
+--echo #
+--echo # TEST 1
+--echo # Greedy search iteration test for 16-way join: star schema
+--echo #
+--echo # Creation of 16 tables hidden
+--echo #
+
+--disable_result_log
+--disable_query_log
+
+let $brands=7;
+let $models_pr_brand=5;
+let $misc_properties_big=20;
+let $misc_properties_small=10;
+let $vehicles=100;
+
+eval 
+CREATE TABLE brands (
+  id_pk int PRIMARY KEY, 
+  id_nokey int, 
+  name varchar(100)
+);
+
+let $i=0;
+while ($i<$brands)
+{
+  inc $i;
+  eval INSERT INTO brands VALUES ($i, $i, concat('brand',$i));
+}
+
+eval 
+CREATE TABLE models (
+  id_pk int PRIMARY KEY, 
+  id_nokey int, 
+  brand_id int, 
+  name varchar(100), 
+  INDEX(`brand_id`)
+);
+
+let $i=0;
+let $cnt=0;
+while ($i<$brands)
+{
+  inc $i;
+  let $j=0;
+  while ($j<$models_pr_brand)
+  { 
+    inc $cnt;
+    inc $j;
+    eval INSERT INTO models VALUES ($cnt, $cnt, $i, concat('brandmodel',$cnt));  
+  }
+}
+
+eval 
+CREATE TABLE subtypes (
+  id_pk int primary key, 
+  id_nokey int, 
+  name varchar(100)
+);
+
+let $i=0;
+while ($i<$misc_properties_small)
+{
+  inc $i;
+  eval INSERT INTO subtypes VALUES ($i, $i, concat('subtype',$i));
+}
+
+eval 
+CREATE TABLE colors (
+  id_pk int primary key, 
+  id_nokey int, 
+  name varchar(100)
+);
+
+let $i=0;
+while ($i<$misc_properties_big)
+{
+  inc $i;
+  eval INSERT INTO colors VALUES ($i, $i, concat('color',$i));
+}
+
+eval 
+CREATE TABLE heating (
+  id_pk int primary key, 
+  id_nokey int, 
+  name varchar(100)
+);
+
+let $i=0;
+while ($i<$misc_properties_small)
+{
+  inc $i;
+  eval INSERT INTO heating VALUES ($i, $i, concat('heating',$i));
+}
+
+eval 
+CREATE TABLE windows (
+  id_pk int primary key, 
+  id_nokey int, 
+  name varchar(100)
+);
+
+let $i=0;
+while ($i<$misc_properties_small)
+{
+  inc $i;
+  eval INSERT INTO windows VALUES ($i, $i, concat('window',$i));
+}
+
+eval 
+CREATE TABLE fuels (
+  id_pk int primary key, 
+  id_nokey int, 
+  name varchar(100)
+);
+
+let $i=0;
+while ($i<$misc_properties_small)
+{
+  inc $i;
+  eval INSERT INTO fuels VALUES ($i, $i, concat('fuel',$i));
+}
+
+eval 
+CREATE TABLE transmissions (
+  id_pk int primary key, 
+  id_nokey int, 
+  name varchar(100)
+);
+
+let $i=0;
+while ($i<$misc_properties_small)
+{
+  inc $i;
+  eval INSERT INTO transmissions VALUES ($i, $i, concat('transmission',$i));
+}
+
+eval 
+CREATE TABLE steerings (
+  id_pk int primary key, 
+  id_nokey int, 
+  name varchar(100)
+);
+
+let $i=0;
+while ($i<$misc_properties_small)
+{
+  inc $i;
+  eval INSERT INTO steerings VALUES ($i, $i, concat('steering',$i));
+}
+
+eval 
+CREATE TABLE interiors (
+  id_pk int primary key, 
+  id_nokey int, 
+  name varchar(100)
+);
+
+let $i=0;
+while ($i<$misc_properties_big)
+{
+  inc $i;
+  eval INSERT INTO interiors VALUES ($i, $i, concat('interior',$i));
+}
+
+eval 
+CREATE TABLE drives (
+  id_pk int primary key, 
+  id_nokey int, 
+  name varchar(100)
+);
+let $i=0;
+while ($i<$misc_properties_small)
+{
+  inc $i;
+  eval INSERT INTO drives VALUES ($i, $i, concat('drive',$i));
+}
+
+eval 
+CREATE TABLE wheels (
+  id_pk int primary key, 
+  id_nokey int, 
+  name varchar(100)
+);
+let $i=0;
+while ($i<$misc_properties_small)
+{
+  inc $i;
+  eval INSERT INTO wheels VALUES ($i, $i, concat('wheel',$i));
+}
+
+eval 
+CREATE TABLE engine (
+  id_pk int primary key, 
+  id_nokey int, 
+  name varchar(100)
+);
+let $i=0;
+while ($i<$misc_properties_small)
+{
+  inc $i;
+  eval INSERT INTO engine VALUES ($i, $i, concat('engine',$i));
+}
+
+eval 
+CREATE TABLE price_ranges (
+  id_pk int primary key, 
+  id_nokey int, 
+  name varchar(100)
+);
+let $i=0;
+while ($i<$misc_properties_small)
+{
+  inc $i;
+  eval INSERT INTO price_ranges VALUES ($i, $i, concat('price',$i));
+}
+
+eval 
+CREATE TABLE countries (
+  id_pk int primary key, 
+  id_nokey int, 
+  name varchar(100)
+);
+let $i=0;
+while ($i<$misc_properties_big)
+{
+  inc $i;
+  eval INSERT INTO countries VALUES ($i, $i, concat('country',$i));
+}
+
+eval 
+CREATE TABLE vehicles (
+  id int primary key, 
+  model_id int, 
+  subtype_id int, 
+  color_id int, 
+  heating_id int, 
+  window_id int, 
+  fuel_id int, 
+  transmission_id int, 
+  steering_id int, 
+  interior_id int, 
+  drive_id int, 
+  price_range_id int, 
+  assembled_in int, 
+  engine_id int, 
+  wheels_id int
+);
+
+
+let $brands=7;
+let $models_pr_brand=3;
+let $misc_properties_big=20;
+let $misc_properties_small=$misc_properties_big/2;
+
+while ($i<$vehicles)
+{
+  inc $i;
+  eval INSERT INTO vehicles VALUES ($i, $i%2, $i%3, $i%4, $i%5, $i%6, $i%7, 
+                                    $i, $i%2, $i%3, $i%4, $i%5, $i%6, $i%7, 
+                                    $i );
+}
+--enable_result_log
+--enable_query_log
+
+SET SESSION optimizer_search_depth = 25; 
+# print_greedy_search_count will do it's own FLUSH STATUS after
+# executing each query, but we need to reset counters before 
+# the first query is executed as well.
+FLUSH STATUS;
+
+--echo #
+--echo # 16-way join - all 15 fact tables joined on column with key
+--echo #
+
+let $query=
+SELECT *
+FROM vehicles
+  JOIN models        ON vehicles.model_id        = models.id_pk
+  JOIN subtypes      ON vehicles.subtype_id      = subtypes.id_pk
+  JOIN colors        ON vehicles.color_id        = colors.id_pk
+  JOIN heating       ON vehicles.heating_id      = heating.id_pk
+  JOIN windows       ON vehicles.window_id       = windows.id_pk
+  JOIN fuels         ON vehicles.fuel_id         = fuels.id_pk
+  JOIN transmissions ON vehicles.transmission_id = transmissions.id_pk
+  JOIN steerings     ON vehicles.steering_id     = steerings.id_pk
+  JOIN interiors     ON vehicles.interior_id     = interiors.id_pk
+  JOIN drives        ON vehicles.drive_id        = drives.id_pk
+  JOIN wheels        ON vehicles.wheels_id       = wheels.id_pk
+  JOIN engine        ON vehicles.engine_id       = engine.id_pk
+  JOIN price_ranges  ON vehicles.price_range_id  = price_ranges.id_pk
+  JOIN countries     ON vehicles.assembled_in    = countries.id_pk
+  JOIN brands        ON models.brand_id          = brands.id_pk;
+--source include/print_greedy_search_count.inc
+
+--echo #
+--echo # 16-way join - 10 fact tables joined on column with key and
+--echo #                5 fact tables joined on column without key
+--echo #
+
+let $query=
+SELECT *
+FROM vehicles
+  JOIN models        ON vehicles.model_id        = models.id_nokey
+  JOIN subtypes      ON vehicles.subtype_id      = subtypes.id_pk
+  JOIN colors        ON vehicles.color_id        = colors.id_pk
+  JOIN heating       ON vehicles.heating_id      = heating.id_nokey
+  JOIN windows       ON vehicles.window_id       = windows.id_pk
+  JOIN fuels         ON vehicles.fuel_id         = fuels.id_pk
+  JOIN transmissions ON vehicles.transmission_id = transmissions.id_nokey
+  JOIN steerings     ON vehicles.steering_id     = steerings.id_pk
+  JOIN interiors     ON vehicles.interior_id     = interiors.id_pk
+  JOIN drives        ON vehicles.drive_id        = drives.id_pk
+  JOIN wheels        ON vehicles.wheels_id       = wheels.id_nokey
+  JOIN engine        ON vehicles.engine_id       = engine.id_pk
+  JOIN price_ranges  ON vehicles.price_range_id  = price_ranges.id_pk
+  JOIN countries     ON vehicles.assembled_in    = countries.id_pk
+  JOIN brands        ON models.brand_id          = brands.id_nokey;
+--source include/print_greedy_search_count.inc
+
+select @@optimizer_search_depth;
+select @@optimizer_prune_level;
+
+DROP TABLE vehicles, models, subtypes, colors, heating, windows, 
+           fuels, transmissions, steerings, interiors, drives, 
+           price_ranges, countries, brands, wheels, engine;
+
+
+--echo #
+--echo # TEST 2
+--echo # Greedy search iteration test for chain of tables
+--echo #
+
+--source include/greedy_search_load_tables.inc
+
+# Explanation to the test
+#
+# A chain of tables is joined like this:
+#    t1 JOIN t2 ON t1.<some_col>=t2.<some_col> JOIN t3 ON ...
+#
+# Different variants of table sizes and columns in the join conditions
+# are tested. 
+#
+# The column names mean:
+#   'pk'     - The column is primary key
+#   'colidx' - The column is indexed
+#   'col'    - The column is not indexed
+#
+# The table names mean:
+#   tx_y     - table with x rows, y is simply used to get unique table names
+#
+# A comment explains each test. The notation used is
+#    (...,tx_col_next):(ty_col_prev,...)
+# which means that table x is joined with table y with join condition
+# "ON tx.col_next = ty.col_prev" like this:
+#    t1 JOIN t2 ON t1.col_next=t2.col_prev ...
+
+--echo #
+--echo # Chain test a:      colidx):(pk,colidx):(pk,colidx)
+--echo #
+
+let $query= SELECT * FROM t10_1;
+let $i= 1;
+while ($i < 8)
+{
+  let $query= $query JOIN t100_$i ON t10_$i.colidx = t100_$i.pk;
+  let $j=$i;
+  inc $j;
+  let $query= $query JOIN t10_$j ON t100_$i.colidx = t10_$j.pk;
+  inc $i;
+}
+--source include/print_greedy_search_count.inc
+
+--echo #
+--echo # Chain test b: (...,col):(colidx, col):(pk,col):(colidx,col):(pk,...)
+--echo #
+let $query= SELECT * FROM t10_1;
+let $i= 1;
+while ($i < 8)
+{
+  let $query= $query JOIN t100_$i ON t10_$i.col = t100_$i.colidx;
+  let $j=$i;
+  inc $j;
+  let $query= $query JOIN t10_$j ON t100_$i.col = t10_$j.pk;
+  inc $i;
+}
+--source include/print_greedy_search_count.inc
+
+--echo #
+--echo # Chain test c: (...,colidx):(col, pk):(col,colidx):(col,...)
+--echo #
+let $query= SELECT * FROM t10_1;
+let $i= 1;
+while ($i < 8)
+{
+  let $query= $query JOIN t100_$i ON t10_$i.colidx = t100_$i.col;
+  let $j=$i;
+  inc $j;
+  let $query= $query JOIN t10_$j ON t100_$i.pk = t10_$j.col;
+  inc $i;
+}
+--source include/print_greedy_search_count.inc
+
+--echo #
+--echo # Chain test d: (...,colidx):(pk, col):(pk,colidx):(pk,col):(pk,...)
+--echo #
+let $query= SELECT * FROM t10_1;
+let $i= 1;
+while ($i < 8)
+{
+  let $query= $query JOIN t100_$i ON t10_$i.colidx = t100_$i.pk;
+  let $j=$i;
+  inc $j;
+  let $query= $query JOIN t10_$j ON t100_$i.col = t10_$j.pk;
+  inc $i;
+}
+--source include/print_greedy_search_count.inc
+
+--echo #
+--echo # Cleanup after TEST 2
+--echo #
+
+--source include/greedy_search_drop_tables.inc

=== added file 'sql/merge_sort.h'
--- a/sql/merge_sort.h	1970-01-01 00:00:00 +0000
+++ b/sql/merge_sort.h	2012-02-23 11:22:34 +0000
@@ -0,0 +1,145 @@
+/* Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
+
+   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 St, Fifth Floor, Boston, MA 02110-1301  USA
+*/
+
+#ifndef MERGE_SORT_INCLUDED
+#define MERGE_SORT_INCLUDED
+
+/**
+  @file
+
+  @brief 
+  Merge sort and insert sort implementations. These sorting functions
+  are primarily intended for sorting of JOIN_TABs before the greedy
+  search algorithm is applied. Since the JOIN_TAB comparison functions
+  (Join_tab_compare*) are not transitive, the resulting order depends
+  on the sorting implementation to a certain degree.
+
+  Since the std::stable_sort and std::sort implementations differ
+  between platforms, the result of sorting JOIN_TABs may also differ.
+  In turn, the query execution plan would differ between platforms and
+  that is a problem with mtr tests (EXPLAIN output would vary).
+
+  If you intend to sort something transitive (which means almost
+  everything except JOIN_TABs) you should most likely use one of the
+  std sorting functions instead of this.
+*/
+
+#include "sql_select.h"
+#include <queue>
+
+/**
+ Sorts the elements in the range [first,last) into ascending order
+ using insertion sort.
+
+ @param first   First element in an array of pointers to be sorted
+ @param last    Element after the last element in an array of pointers 
+                to be sorted
+ @param comp    Comparison function object that, taking two pointers 
+                of the same type as those contained in the range, 
+                returns true if the first argument goes before the 
+                second argument in the specific strict weak ordering
+                it defines, and false otherwise.
+
+ In our case comp should be a function object with an operator:
+ 
+ bool operator()(Element_type*, Element_type*)
+*/
+
+template<typename Element_type, typename Comp_func>
+void insert_sort(Element_type **first, Element_type **last, Comp_func comp)
+{
+  for (Element_type **high_water_mark= first+1;
+       high_water_mark < last;
+       high_water_mark++)
+  {
+    for (Element_type **cur= high_water_mark; cur > first ; cur--)
+    {
+      if (comp(*(cur-1), *cur))
+        break;
+
+      Element_type *tmp= *(cur-1);
+      *(cur-1)= *cur;
+      *cur= tmp;
+    }
+  }
+}
+
+
+/**
+ Sorts the elements in the range [first,last) into ascending order
+ using merge sort.
+
+ @param first   First element in an array of pointers to be sorted
+ @param last    Element after the last element in an array of pointers 
+                to be sorted
+ @param comp    Comparison function object that, taking two pointers 
+                of the same type as those contained in the range, 
+                returns true if the first argument goes before the 
+                second argument in the specific strict weak ordering
+                it defines, and false otherwise.
+
+ In our case comp should be a function object with an operator:
+ 
+ bool operator()(Element_type*, Element_type*)
+*/
+
+template<typename Element_type, typename Comp_func>
+void merge_sort(Element_type **first, Element_type **last, Comp_func comp)
+{
+  const uint elements= last - first;
+
+  /*
+    Tests showed that the value 5 was a good number for JOIN_TAB
+    ordering, which is the primary use case for this function
+  */
+  if (elements < 5)
+  {
+    insert_sort(first, last, comp);
+    return;
+  }
+  Element_type **middle= first + (elements)/2;
+
+  merge_sort (first, middle, comp);
+  merge_sort (middle, last, comp);
+
+  std::queue<Element_type *> merged;
+
+  Element_type **cur1= first;
+  Element_type **cur2= middle;
+
+  for (uint i= 0; i < elements; i++)
+  {
+    DBUG_ASSERT (cur1 < middle || cur2 < last);
+
+    if (cur1 == middle)
+      merged.push(*cur2++);
+    else if (cur2 == last)
+      merged.push(*cur1++);
+    else if (comp(*cur1, *cur2))
+      merged.push(*cur1++);
+    else
+      merged.push(*cur2++);
+  }
+
+  Element_type **result= first;
+  while (!merged.empty())
+  {
+    *result++= merged.front();
+    merged.pop();
+  }
+}
+
+#endif /* MERGE_SORT_INCLUDED */

=== modified file 'sql/mysqld.cc'
--- a/sql/mysqld.cc	2012-02-21 14:51:02 +0000
+++ b/sql/mysqld.cc	2012-02-23 11:22:34 +0000
@@ -7070,6 +7070,7 @@ SHOW_VAR status_vars[]= {
   {"Opened_files",             (char*) &my_file_total_opened, SHOW_LONG_NOFLUSH},
   {"Opened_tables",            (char*) offsetof(STATUS_VAR, opened_tables), SHOW_LONGLONG_STATUS},
   {"Opened_table_definitions", (char*) offsetof(STATUS_VAR, opened_shares), SHOW_LONGLONG_STATUS},
+  {"Opt_partial_plans",        (char*) offsetof(STATUS_VAR, opt_partial_plans), SHOW_LONGLONG_STATUS},
   {"Prepared_stmt_count",      (char*) &show_prepared_stmt_count, SHOW_FUNC},
 #ifdef HAVE_QUERY_CACHE
   {"Qcache_free_blocks",       (char*) &query_cache.free_memory_blocks, SHOW_LONG_NOFLUSH},

=== modified file 'sql/sql_class.h'
--- a/sql/sql_class.h	2012-02-22 08:57:27 +0000
+++ b/sql/sql_class.h	2012-02-23 11:22:34 +0000
@@ -836,6 +836,7 @@ typedef struct system_status_var
 {
   ulonglong created_tmp_disk_tables;
   ulonglong created_tmp_tables;
+  ulonglong opt_partial_plans;
   ulonglong ha_commit_count;
   ulonglong ha_delete_count;
   ulonglong ha_read_first_count;

=== modified file 'sql/sql_planner.cc'
--- a/sql/sql_planner.cc	2012-01-16 12:51:06 +0000
+++ b/sql/sql_planner.cc	2012-02-23 11:22:34 +0000
@@ -1,4 +1,4 @@
-/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
+/* Copyright (c) 2000, 2012, Oracle and/or its affiliates. All rights reserved.
 
    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
@@ -29,6 +29,7 @@
 #include "opt_range.h"
 #include "opt_trace.h"
 #include "sql_executor.h"
+#include "merge_sort.h"
 #include <my_bit.h>
 
 #include <algorithm>
@@ -37,106 +38,6 @@ using std::min;
 
 static double prev_record_reads(JOIN *join, uint idx, table_map found_ref);
 
-/**
-  Compare two JOIN_TAB objects based on the number of accessed records.
-
-  @param ptr1 pointer to first JOIN_TAB object
-  @param ptr2 pointer to second JOIN_TAB object
-
-  NOTES
-    The order relation implemented by join_tab_cmp() is not transitive,
-    i.e. it is possible to choose such a, b and c that (a < b) && (b < c)
-    but (c < a). This implies that result of a sort using the relation
-    implemented by join_tab_cmp() depends on the order in which
-    elements are compared, i.e. the result is implementation-specific.
-    Example:
-      a: dependent = 0x0 table->map = 0x1 found_records = 3 ptr = 0x907e6b0
-      b: dependent = 0x0 table->map = 0x2 found_records = 3 ptr = 0x907e838
-      c: dependent = 0x6 table->map = 0x10 found_records = 2 ptr = 0x907ecd0
-     
-  @retval
-    1  if first is bigger
-  @retval
-    -1  if second is bigger
-  @retval
-    0  if equal
-*/
-
-static int
-join_tab_cmp(const void *, const void* ptr1, const void* ptr2)
-{
-  JOIN_TAB *jt1= *(JOIN_TAB**) ptr1;
-  JOIN_TAB *jt2= *(JOIN_TAB**) ptr2;
-
-  if (jt1->dependent & jt2->table->map)
-    return 1;
-  if (jt2->dependent & jt1->table->map)
-    return -1;  
-  if (jt1->found_records > jt2->found_records)
-    return 1;
-  if (jt1->found_records < jt2->found_records)
-    return -1; 
-  return jt1 > jt2 ? 1 : (jt1 < jt2 ? -1 : 0);
-}
-
-
-/**
-  Same as join_tab_cmp, but for use with SELECT_STRAIGHT_JOIN.
-*/
-
-static int
-join_tab_cmp_straight(const void *, const void* ptr1, const void* ptr2)
-{
-  JOIN_TAB *jt1= *(JOIN_TAB**) ptr1;
-  JOIN_TAB *jt2= *(JOIN_TAB**) ptr2;
- 
-  /*
-    We don't do subquery flattening if the parent or child select has
-    STRAIGHT_JOIN modifier. It is complicated to implement and the semantics
-    is hardly useful.
-  */
-  DBUG_ASSERT(!jt1->emb_sj_nest);
-  DBUG_ASSERT(!jt2->emb_sj_nest);
-
-  if (jt1->dependent & jt2->table->map)
-    return 1;
-  if (jt2->dependent & jt1->table->map)
-    return -1;
-  return jt1 > jt2 ? 1 : (jt1 < jt2 ? -1 : 0);
-}
-
-
-/*
-  Same as join_tab_cmp but tables from within the given semi-join nest go 
-  first. Used when optimizing semi-join materialization nests.
-*/
-
-static int
-join_tab_cmp_embedded_first(const void *emb, const void* ptr1, const void* ptr2)
-{
-  const TABLE_LIST *emb_nest= (TABLE_LIST*) emb;
-  JOIN_TAB *jt1= *(JOIN_TAB**) ptr1;
-  JOIN_TAB *jt2= *(JOIN_TAB**) ptr2;
-
-  if (jt1->emb_sj_nest == emb_nest && jt2->emb_sj_nest != emb_nest)
-    return -1;
-  if (jt1->emb_sj_nest != emb_nest && jt2->emb_sj_nest == emb_nest)
-    return 1;
-
-  if (jt1->dependent & jt2->table->map)
-    return 1;
-  if (jt2->dependent & jt1->table->map)
-    return -1;
-
-  if (jt1->found_records > jt2->found_records)
-    return 1;
-  if (jt1->found_records < jt2->found_records)
-    return -1; 
-  
-  return jt1 > jt2 ? 1 : (jt1 < jt2 ? -1 : 0);
-}
-
-
 /*
   This is a class for considering possible loose index scan optimizations.
   It's usage pattern is as follows:
@@ -1149,7 +1050,6 @@ bool Optimize_table_order::choose_table_
   }
 
   reset_nj_counters(join->join_list);
-  qsort2_cmp jtab_sort_func;
 
   const bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
   table_map join_tables;      ///< The tables involved in order selection
@@ -1159,7 +1059,9 @@ bool Optimize_table_order::choose_table_
     /* We're optimizing semi-join materialization nest, so put the 
        tables from this semi-join as first
     */
-    jtab_sort_func= join_tab_cmp_embedded_first;
+    merge_sort(join->best_ref + join->const_tables,
+               join->best_ref + join->tables,
+               Join_tab_compare_embedded_first(emb_sjm_nest));
     join_tables= emb_sjm_nest->sj_inner_tables;
   }
   else
@@ -1172,12 +1074,17 @@ bool Optimize_table_order::choose_table_
         Apply heuristic: pre-sort all access plans with respect to the number of
         records accessed.
     */
-    jtab_sort_func= straight_join ? join_tab_cmp_straight : join_tab_cmp;
+    if (straight_join)
+      merge_sort(join->best_ref + join->const_tables,
+                 join->best_ref + join->tables,
+                 Join_tab_compare_straight());
+    else 
+      merge_sort(join->best_ref + join->const_tables,
+                 join->best_ref + join->tables,
+                 Join_tab_compare_default());
+
     join_tables= join->all_table_map & ~join->const_table_map;
   }
-  my_qsort2(join->best_ref + join->const_tables,
-            join->tables - join->const_tables, sizeof(JOIN_TAB*),
-            jtab_sort_func, (void*)emb_sjm_nest);
 
   Opt_trace_object wrapper(&join->thd->opt_trace);
   Opt_trace_array
@@ -1882,6 +1789,7 @@ bool Optimize_table_order::best_extensio
 
   for (JOIN_TAB **pos= join->best_ref + idx; *pos; pos++)
   {
+    status_var_increment(thd->status_var.opt_partial_plans);
     JOIN_TAB *const s= *pos;
     const table_map real_table_bit= s->table->map;
 
@@ -2250,6 +2158,7 @@ table_map Optimize_table_order::eq_ref_e
                           added_to_eq_ref_extension);
       if (added_to_eq_ref_extension)
       {
+        status_var_increment(thd->status_var.opt_partial_plans);
         double current_record_count, current_read_time;
 
         /* Add the cost of extending the plan with 's' */

=== modified file 'sql/sql_planner.h'
--- a/sql/sql_planner.h	2011-12-14 12:32:55 +0000
+++ b/sql/sql_planner.h	2012-02-23 11:22:34 +0000
@@ -1,7 +1,7 @@
 #ifndef SQL_PLANNER_INCLUDED
 #define SQL_PLANNER_INCLUDED
 
-/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
+/* Copyright (c) 2000, 2012, Oracle and/or its affiliates. All rights reserved.
 
    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
@@ -140,12 +140,6 @@ private:
                 double *newcount, double *newcost);
 
   static uint determine_search_depth(uint search_depth, uint table_count);
-  /**
-    @todo: Add the static functions join_tab_cmp(), join_tab_cmp_straight() and
-    join_tab_cmp_embedded_first() as static private member functions here.
-    This is currently not possible because they are fed to my_qsort2(),
-    which requires C linkage.
-  */
 };
 
 void get_partial_join_cost(JOIN *join, uint n_tables, double *read_time_arg,

=== modified file 'sql/sql_select.h'
--- a/sql/sql_select.h	2012-01-16 12:51:06 +0000
+++ b/sql/sql_select.h	2012-02-23 11:22:34 +0000
@@ -1,7 +1,7 @@
 #ifndef SQL_SELECT_INCLUDED
 #define SQL_SELECT_INCLUDED
 
-/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
+/* Copyright (c) 2000, 2012, Oracle and/or its affiliates. All rights reserved.
 
    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
@@ -33,6 +33,7 @@
 #include "mem_root_array.h"
 #include "sql_executor.h"
 
+#include <functional>
 /**
    Returns a constant of type 'type' with the 'A' lowest-weight bits set.
    Example: LOWER_BITS(uint, 3) == 7.
@@ -654,6 +655,135 @@ st_join_table::st_join_table()
   memset(&read_record, 0, sizeof(read_record));
 }
 
+/**
+  "Less than" comparison function object used to compare two JOIN_TAB
+  objects based on a number of factors in this order:
+
+   - table before another table that depends on it (straight join, 
+     outer join etc), then
+   - table before another table that depends on it to use a key
+     as access method, then
+   - table with smallest number of records first, then
+   - the table with lowest-value pointer (i.e., the one located 
+     in the lowest memory address) first.
+
+  @param jt1  first JOIN_TAB object
+  @param jt2  second JOIN_TAB object
+
+  @note The order relation implemented by Join_tab_compare_default is not
+    transitive, i.e. it is possible to choose a, b and c such that 
+    (a < b) && (b < c) but (c < a). This is the case in the
+    following example: 
+
+      a: dependent = <none>   found_records = 3
+      b: dependent = <none>   found_records = 4
+      c: dependent = b        found_records = 2
+
+        a < b: because a has fewer records
+        b < c: because c depends on b (e.g outer join dependency)
+        c < a: because c has fewer records
+
+    This implies that the result of a sort using the relation
+    implemented by Join_tab_compare_default () depends on the order in
+    which elements are compared, i.e. the result is
+    implementation-specific.
+
+  @return
+    true if jt1 is smaller than jt2, false otherwise
+*/
+class Join_tab_compare_default :
+  public std::binary_function<const JOIN_TAB*, const JOIN_TAB*, bool>
+{
+public:
+  bool operator()(const JOIN_TAB *jt1, const JOIN_TAB *jt2)
+  {
+    // Sorting distinct tables, so a table should not be compared with itself
+    DBUG_ASSERT(jt1 != jt2);
+
+    if (jt1->dependent & jt2->table->map)
+      return false;
+    if (jt2->dependent & jt1->table->map)
+      return true;
+
+    const bool jt1_keydep_jt2= jt1->key_dependent & jt2->table->map;
+    const bool jt2_keydep_jt1= jt2->key_dependent & jt1->table->map;
+
+    if (jt1_keydep_jt2 && !jt2_keydep_jt1)
+      return false;
+    if (jt2_keydep_jt1 && !jt1_keydep_jt2)
+      return true;
+
+    if (jt1->found_records > jt2->found_records)
+      return false;
+    if (jt1->found_records < jt2->found_records)
+      return true;
+
+    return jt1 < jt2;
+  }
+};
+
+/**
+  "Less than" comparison function object used to compare two JOIN_TAB
+  objects that are joined using STRAIGHT JOIN. For STRAIGHT JOINs, 
+  the join order is dictated by the relative order of the tables in the
+  query which is reflected in JOIN_TAB::dependent. Table size and key
+  dependencies are ignored here.
+*/
+class Join_tab_compare_straight :
+  public std::binary_function<const JOIN_TAB*, const JOIN_TAB*, bool>
+{
+public:
+  bool operator()(const JOIN_TAB *jt1, const JOIN_TAB *jt2)
+  {
+    // Sorting distinct tables, so a table should not be compared with itself
+    DBUG_ASSERT(jt1 != jt2);
+
+    /*
+      We don't do subquery flattening if the parent or child select has
+      STRAIGHT_JOIN modifier. It is complicated to implement and the semantics
+      is hardly useful.
+    */
+    DBUG_ASSERT(!jt1->emb_sj_nest);
+    DBUG_ASSERT(!jt2->emb_sj_nest);
+
+    if (jt1->dependent & jt2->table->map)
+      return false;
+    if (jt2->dependent & jt1->table->map)
+      return true;
+
+    return jt1 < jt2;
+  }
+};
+
+/*
+  Same as Join_tab_compare_default but tables from within the given
+  semi-join nest go first. Used when optimizing semi-join
+  materialization nests.
+*/
+class Join_tab_compare_embedded_first :
+  public std::binary_function<const JOIN_TAB*, const JOIN_TAB*, bool>
+{
+private:
+  const TABLE_LIST *emb_nest;
+public:
+  
+  Join_tab_compare_embedded_first(const TABLE_LIST *nest) : emb_nest(nest){}
+
+  bool operator()(const JOIN_TAB *jt1, const JOIN_TAB *jt2)
+  {
+    // Sorting distinct tables, so a table should not be compared with itself
+    DBUG_ASSERT(jt1 != jt2);
+
+    if (jt1->emb_sj_nest == emb_nest && jt2->emb_sj_nest != emb_nest)
+      return true;
+    if (jt1->emb_sj_nest != emb_nest && jt2->emb_sj_nest == emb_nest)
+      return false;
+
+    Join_tab_compare_default cmp;
+    return cmp(jt1,jt2);
+  }
+};
+
 
 
 /**

=== modified file 'unittest/gunit/CMakeLists.txt'
--- a/unittest/gunit/CMakeLists.txt	2012-02-07 11:56:30 +0000
+++ b/unittest/gunit/CMakeLists.txt	2012-02-23 11:22:34 +0000
@@ -260,6 +260,7 @@ SET(SERVER_TESTS
   sql_table
   get_diagnostics
   segfault
+  join_tab_sort
 )
 
 FOREACH(test ${TESTS})

=== added file 'unittest/gunit/join_tab_sort-t.cc'
--- a/unittest/gunit/join_tab_sort-t.cc	1970-01-01 00:00:00 +0000
+++ b/unittest/gunit/join_tab_sort-t.cc	2012-02-23 11:22:34 +0000
@@ -0,0 +1,280 @@
+/* Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. 
+
+   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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+// First include (the generated) my_config.h, to get correct platform defines.
+#include "my_config.h"
+#include <gtest/gtest.h>
+
+#include "test_utils.h"
+
+#include "sql_select.h"
+#include "merge_sort.h"
+
+#include <vector>
+
+namespace {
+
+using my_testing::Server_initializer;
+using my_testing::Mock_error_handler;
+
+class JTSortTest : public ::testing::Test
+{
+protected:
+  static void SetUpTestCase()
+  {
+    Server_initializer::SetUpTestCase();
+  }
+
+  static void TearDownTestCase()
+  {
+    Server_initializer::TearDownTestCase();
+  }
+
+  virtual void SetUp()
+  {
+    initializer.SetUp();
+  }
+
+  virtual void TearDown()
+  {
+    initializer.TearDown();
+  }
+
+  Server_initializer initializer;
+};
+
+class MOCK_JOIN_TAB : public JOIN_TAB
+{
+public:
+  MOCK_JOIN_TAB(uint recs, uint table_no) : JOIN_TAB()
+  {
+    found_records= recs;
+    m_table.map= 1UL<<table_no;
+    this->table= &m_table;
+  }
+  
+  TABLE       m_table;
+};
+
+
+TEST_F(JTSortTest, SimpleSortTest)
+{
+  MOCK_JOIN_TAB jt1(UINT_MAX, 0);
+  MOCK_JOIN_TAB jt2(2, 0);
+  MOCK_JOIN_TAB jt3(1, 0);
+  MOCK_JOIN_TAB jt4(10, 0);
+  MOCK_JOIN_TAB jt5(5, 0);
+
+  MOCK_JOIN_TAB *arr[5];
+  arr[0]= &jt1;
+  arr[1]= &jt2;
+  arr[2]= &jt3;
+  arr[3]= &jt4;
+  arr[4]= &jt5;
+
+  insert_sort(arr, arr+5, Join_tab_compare_default());
+
+  EXPECT_EQ(1U, arr[0]->found_records);
+  EXPECT_EQ(2U, arr[1]->found_records);
+  EXPECT_EQ(5U, arr[2]->found_records);
+  EXPECT_EQ(10U, arr[3]->found_records);
+  EXPECT_EQ(UINT_MAX, arr[4]->found_records);
+
+}
+
+
+TEST_F(JTSortTest, SortFoundRecordsTest)
+{
+  const int num_tables= 50;
+  MOCK_JOIN_TAB *arr[num_tables];
+
+  for (int i= 0; i < num_tables; i++)
+    arr[i]= new MOCK_JOIN_TAB(i, 0);
+
+  // MERGE SORT
+  std::random_shuffle(arr, arr + 50);
+  merge_sort(arr, arr + num_tables, Join_tab_compare_default());
+  for (int i= 1; i < num_tables; i++)
+    EXPECT_TRUE(arr[i]->found_records > arr[i-1]->found_records);
+
+  // INSERT SORT
+  std::random_shuffle(arr, arr + 50);
+  insert_sort(arr, arr + num_tables, Join_tab_compare_default());
+  for (int i= 1; i < num_tables; i++)
+    EXPECT_TRUE(arr[i]->found_records > arr[i-1]->found_records);
+
+  for (int i= 0; i < num_tables; i++)
+  {
+    delete arr[i];
+  }
+}
+
+
+TEST_F(JTSortTest, SortDependsTest)
+{
+  const int num_tables= 50;
+  MOCK_JOIN_TAB *arr[num_tables];
+
+  /*
+    dependency has higher precedence than found_records, so the tables
+    shall be ordered with decreasing number of records in this test
+  */
+  for (int i= 0; i < num_tables; i++)
+  {
+    arr[i]= new MOCK_JOIN_TAB(i, i);
+    for (int j= i+1; j < num_tables; j++)
+      arr[i]->dependent|= 1UL << j;
+  }
+
+  // MERGE SORT
+  std::random_shuffle(arr, arr + num_tables);
+  merge_sort(arr, arr + num_tables, Join_tab_compare_default());
+  for (int i= 1; i < num_tables; i++)
+    EXPECT_TRUE(arr[i]->found_records < arr[i-1]->found_records);
+
+  // INSERT SORT
+  std::random_shuffle(arr, arr + num_tables);
+  insert_sort(arr, arr + num_tables, Join_tab_compare_default());
+  for (int i= 1; i < num_tables; i++)
+    EXPECT_TRUE(arr[i]->found_records < arr[i-1]->found_records);
+
+  for (int i= 0; i < num_tables; i++)
+  {
+    delete arr[i];
+  }
+}
+
+
+TEST_F(JTSortTest, SortKeyDependsTest)
+{
+  const int num_tables= 50;
+  MOCK_JOIN_TAB *arr[num_tables];
+
+  /*
+    key_dependency has higher precedence than found_records, so the
+    tables shall be ordered with decreasing number of records in this
+    test
+  */
+  for (int i= 0; i < num_tables; i++)
+  {
+    arr[i]= new MOCK_JOIN_TAB(i, i);
+    for (int j= i+1; j < num_tables; j++)
+      arr[i]->key_dependent|= 1UL << j;
+  }
+
+  // MERGE SORT
+  std::random_shuffle(arr, arr + num_tables);
+  merge_sort(arr, arr + num_tables, Join_tab_compare_default());
+  for (int i= 1; i < num_tables; i++)
+    EXPECT_TRUE(arr[i]->found_records < arr[i-1]->found_records);
+
+  // INSERT SORT
+  std::random_shuffle(arr, arr + num_tables);
+  insert_sort(arr, arr + num_tables, Join_tab_compare_default());
+  for (int i= 1; i < num_tables; i++)
+    EXPECT_TRUE(arr[i]->found_records < arr[i-1]->found_records);
+
+  for (int i= 0; i < num_tables; i++)
+    delete arr[i];
+}
+
+/*
+  Above, sorting for JOIN_TABs were tested. Below we check that the
+  sorting works for ints types as well. 
+*/
+
+class Int_compare_ptr :
+  public std::binary_function<const int*, const int*, bool>
+{
+public:
+  bool operator()(const int *i1, const int *i2) const
+  {
+    return *i1 < *i2;
+  }
+};
+
+
+TEST_F(JTSortTest, SortIntTest)
+{
+  const uint ints_to_sort= 1000;
+
+  std::vector<int> arr;
+  std::vector<int*> arr_ptr;
+
+  arr.reserve(ints_to_sort);
+  arr_ptr.reserve(ints_to_sort);
+
+  for (uint i= 0; i < ints_to_sort; i++)
+  {
+    arr.push_back(i);
+    arr_ptr.push_back(&arr[i]);
+  }
+
+  EXPECT_TRUE(arr.size() == ints_to_sort);
+  EXPECT_TRUE(arr_ptr.size() == ints_to_sort);
+
+  // MERGE SORT
+  std::random_shuffle(&arr_ptr.front(), &arr_ptr.back() + 1);
+  merge_sort(&arr_ptr.front(), &arr_ptr.back() + 1, Int_compare_ptr());
+  for (uint i= 0; i < arr_ptr.size(); i++)
+    EXPECT_TRUE(*arr_ptr[i] == (int)i);
+
+  // INSERT SORT
+  std::random_shuffle(&arr_ptr.front(), &arr_ptr.back() + 1);
+  insert_sort(&arr_ptr.front(), &arr_ptr.back() + 1, Int_compare_ptr());
+  for (uint i= 0; i < arr_ptr.size(); i++)
+    EXPECT_TRUE(*arr_ptr[i] == (int)i);
+}
+
+
+TEST_F(JTSortTest, SortInt2Test)
+{
+  const uint ints_to_sort= 1000;
+
+  std::vector<int> arr;
+  std::vector<int*> arr_ptr;
+
+  arr.reserve(ints_to_sort);
+  arr_ptr.reserve(ints_to_sort);
+
+  for (uint i= 0; i < (ints_to_sort - 2); i++)
+  {
+    arr.push_back((i % 2) ? i : (i * -1));
+    arr_ptr.push_back(&arr[i]);
+  }
+
+  arr.push_back(INT_MAX32);
+  arr_ptr.push_back(&arr.back());
+
+  arr.push_back(INT_MIN32);
+  arr_ptr.push_back(&arr.back());
+
+  EXPECT_TRUE(arr.size() == ints_to_sort);
+  EXPECT_TRUE(arr_ptr.size() == ints_to_sort);
+
+  // MERGE SORT
+  std::random_shuffle(&arr_ptr.front(), &arr_ptr.back() + 1);
+  merge_sort(&arr_ptr.front(), &arr_ptr.back() + 1, Int_compare_ptr());
+  for (uint i= 1; i < arr_ptr.size(); i++)
+    EXPECT_TRUE(*arr_ptr[i-1] < *arr_ptr[i]);
+
+  // INSERT SORT
+  std::random_shuffle(&arr_ptr.front(), &arr_ptr.back() + 1);
+  insert_sort(&arr_ptr.front(), &arr_ptr.back() + 1, Int_compare_ptr());
+  for (uint i= 1; i < arr_ptr.size(); i++)
+    EXPECT_TRUE(*arr_ptr[i-1] < *arr_ptr[i]);
+}
+
+}

No bundle (reason: useless for push emails).
Thread
bzr push into mysql-trunk branch (jorgen.loland:3947 to 3948) WL#6158Jorgen Loland24 Feb