List:Commits« Previous MessageNext Message »
From:Ole John Aske Date:April 27 2011 7:42am
Subject:bzr commit into mysql-5.1-telco-7.0-spj-scan-vs-scan branch
(ole.john.aske:3480)
View as plain text  
#At file:///net/fimafeng09/export/home/tmp/oleja/mysql/mysql-5.1-telco-7.0-spj-scan-scan/ based on revid:jonas@stripped

 3480 Ole John Aske	2011-04-27
      SPJ: Mayor refactoring of ha_ndbcluster_push.cc and the logic which build 
      the pushed query (or: NdbQueryDef).
      
      Previously the NdbQueryDef was build incremenataly as we analyzed the query 
      plan for pushable operations. This had the disadvantage that we could take 
      descission about parent - child relations at this stage which later prevented
      other child candidates to be appended to the pushed query.
      
      This refactoring extends 'class ndb_pushed_builder_ctx' such that it
      collects intermediate information about pushable operation, and possible
      parent candidates for each child operation. Furthermore, it 
      breaks the pushability logic into multiple passes:
      
      1 ANALYZE:
          Analyze each child candidate and add it to 
          'ndb_pushed_builder_ctx::m_join_scope' as 
          'pushable' if it qualifies as such. In addition possible parent
          candidates, and required (forced) parent dependencies are collected
          for each table. All non pushable operations should be identified 
          during this pass such that only known pushable operations remains.
      
      2 OPTIMIZE:
          Determine the parent to be used among the set of possible
          parents. This is decided based on simple heuristic where
          the goal is to employ conditional filters as soon as possible,  
          reduce the fanout of intermediate results, and utilize
          the parallelism of the SPJ block whenever considdered optimal.
      
      3 BUILD:
          Build the NdbQueryDef.
      
      The primary goal of this refactoring has been to provide a better platform 
      for later improving the efficiency of the pushed queries being produced.
       
      It has not been the goal of this refactoring to change the pushability
      of any query in the existing MTR testsuite. However a few queries has improved
      its pushability as the 'analyze' phase now are able to force an artificial 
      sequential dependency between tables which enables more child operations to be 
      appended to the pushed query.

    modified:
      mysql-test/suite/ndb/r/ndb_gis.result
      mysql-test/suite/ndb/r/ndb_join_pushdown.result
      mysql-test/suite/ndb/t/ndb_join_pushdown.test
      sql/ha_ndbcluster.cc
      sql/ha_ndbcluster.h
      sql/ha_ndbcluster_push.cc
      sql/ha_ndbcluster_push.h
=== modified file 'mysql-test/suite/ndb/r/ndb_gis.result'
--- a/mysql-test/suite/ndb/r/ndb_gis.result	2010-10-29 20:06:44 +0000
+++ b/mysql-test/suite/ndb/r/ndb_gis.result	2011-04-27 07:42:18 +0000
@@ -406,8 +406,8 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	g1	ALL	NULL	NULL	NULL	NULL	2	100.00	Using temporary; Using filesort
 1	SIMPLE	g2	ALL	NULL	NULL	NULL	NULL	2	100.00	Using join buffer
 Warnings:
-Note	1644	Table 'g1' not pushable, select list can't contain BLOB columns
-Note	1644	Table 'g2' not pushable, select list can't contain BLOB columns
+Note	1644	Table 'g1' is not pushable: select list can't contain BLOB columns
+Note	1644	Table 'g2' is not pushable: select list can't contain BLOB columns
 Note	1003	select `test`.`g1`.`fid` AS `first`,`test`.`g2`.`fid` AS `second`,within(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `w`,contains(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `c`,overlaps(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `o`,equals(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `e`,disjoint(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `d`,touches(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `t`,intersects(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `i`,crosses(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `r` from `test`.`gis_geometrycollection` `g1` join `test`.`gis_geometrycollection` `g2` order by `test`.`g1`.`fid`,`test`.`g2`.`fid`
 DROP TABLE gis_point, gis_line, gis_polygon, gis_multi_point, gis_multi_line, gis_multi_polygon, gis_geometrycollection, gis_geometry;
 CREATE TABLE t1 (
@@ -960,8 +960,8 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	g1	ALL	NULL	NULL	NULL	NULL	2	100.00	Using temporary; Using filesort
 1	SIMPLE	g2	ALL	NULL	NULL	NULL	NULL	2	100.00	Using join buffer
 Warnings:
-Note	1644	Table 'g1' not pushable, select list can't contain BLOB columns
-Note	1644	Table 'g2' not pushable, select list can't contain BLOB columns
+Note	1644	Table 'g1' is not pushable: select list can't contain BLOB columns
+Note	1644	Table 'g2' is not pushable: select list can't contain BLOB columns
 Note	1003	select `test`.`g1`.`fid` AS `first`,`test`.`g2`.`fid` AS `second`,within(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `w`,contains(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `c`,overlaps(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `o`,equals(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `e`,disjoint(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `d`,touches(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `t`,intersects(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `i`,crosses(`test`.`g1`.`g`,`test`.`g2`.`g`) AS `r` from `test`.`gis_geometrycollection` `g1` join `test`.`gis_geometrycollection` `g2` order by `test`.`g1`.`fid`,`test`.`g2`.`fid`
 DROP TABLE gis_point, gis_line, gis_polygon, gis_multi_point, gis_multi_line, gis_multi_polygon, gis_geometrycollection, gis_geometry;
 CREATE TABLE t1 (

=== modified file 'mysql-test/suite/ndb/r/ndb_join_pushdown.result'
--- a/mysql-test/suite/ndb/r/ndb_join_pushdown.result	2011-03-17 13:54:30 +0000
+++ b/mysql-test/suite/ndb/r/ndb_join_pushdown.result	2011-04-27 07:42:18 +0000
@@ -1106,12 +1106,11 @@ join t1 as t2 on t2.a = t1.a and t2.b = 
 join t1 as t3 on t3.a = t1.c and t3.b = t1.d
 join t1 as t4 on t4.a = t3.c and t4.b = t2.c;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	SIMPLE	t1	ALL	PRIMARY	NULL	NULL	NULL	16	100.00	Parent of 3 pushed join@1
+1	SIMPLE	t1	ALL	PRIMARY	NULL	NULL	NULL	16	100.00	Parent of 4 pushed join@1
 1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	8	test.t1.a,test.t1.b	1	100.00	Child of 't1' in pushed join@1
-1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	8	test.t1.c,test.t1.d	1	100.00	Child of 't1' in pushed join@1
-1	SIMPLE	t4	eq_ref	PRIMARY	PRIMARY	8	test.t3.c,test.t2.c	1	100.00	
+1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	8	test.t1.c,test.t1.d	1	100.00	Child of 't2' in pushed join@1
+1	SIMPLE	t4	eq_ref	PRIMARY	PRIMARY	8	test.t3.c,test.t2.c	1	100.00	Child of 't3' in pushed join@1
 Warnings:
-Note	1644	Can't push table 't4' as child of 't1', no parents found within scope
 Note	1003	select straight_join `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t1`.`c` AS `c`,`test`.`t1`.`d` AS `d`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b`,`test`.`t2`.`c` AS `c`,`test`.`t2`.`d` AS `d`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS `b`,`test`.`t3`.`c` AS `c`,`test`.`t3`.`d` AS `d`,`test`.`t4`.`a` AS `a`,`test`.`t4`.`b` AS `b`,`test`.`t4`.`c` AS `c`,`test`.`t4`.`d` AS `d` from `test`.`t1` join `test`.`t1` `t2` join `test`.`t1` `t3` join `test`.`t1` `t4` where ((`test`.`t2`.`b` = `test`.`t1`.`b`) and (`test`.`t2`.`a` = `test`.`t1`.`a`) and (`test`.`t3`.`b` = `test`.`t1`.`d`) and (`test`.`t3`.`a` = `test`.`t1`.`c`) and (`test`.`t4`.`b` = `test`.`t2`.`c`) and (`test`.`t4`.`a` = `test`.`t3`.`c`))
 select straight_join *
 from t1
@@ -1352,6 +1351,89 @@ a	b	c	d	a	b	c	d	a	b	c	d	a	b	c	d
 3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3
 3	4	3	4	3	4	3	4	3	4	3	4	3	4	3	4
 4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4
+explain extended
+select straight_join *
+from t1
+join t1 as t2  on t2.a = t1.a and t2.b = t1.b
+join t1 as t2x on t2x.a = t2.c and t2x.b = t2.d
+join t1 as t3x on t3x.a = t1.c and t3x.b = t1.d
+join t1 as t4  on t4.a = t3x.c and t4.b = t2x.c;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	t1	ALL	PRIMARY	NULL	NULL	NULL	16	100.00	Parent of 5 pushed join@1
+1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	8	test.t1.a,test.t1.b	1	100.00	Child of 't1' in pushed join@1
+1	SIMPLE	t2x	eq_ref	PRIMARY	PRIMARY	8	test.t2.c,test.t2.d	1	100.00	Child of 't2' in pushed join@1
+1	SIMPLE	t3x	eq_ref	PRIMARY	PRIMARY	8	test.t1.c,test.t1.d	1	100.00	Child of 't2x' in pushed join@1
+1	SIMPLE	t4	eq_ref	PRIMARY	PRIMARY	8	test.t3x.c,test.t2x.c	1	100.00	Child of 't3x' in pushed join@1
+Warnings:
+Note	1003	select straight_join `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t1`.`c` AS `c`,`test`.`t1`.`d` AS `d`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b`,`test`.`t2`.`c` AS `c`,`test`.`t2`.`d` AS `d`,`test`.`t2x`.`a` AS `a`,`test`.`t2x`.`b` AS `b`,`test`.`t2x`.`c` AS `c`,`test`.`t2x`.`d` AS `d`,`test`.`t3x`.`a` AS `a`,`test`.`t3x`.`b` AS `b`,`test`.`t3x`.`c` AS `c`,`test`.`t3x`.`d` AS `d`,`test`.`t4`.`a` AS `a`,`test`.`t4`.`b` AS `b`,`test`.`t4`.`c` AS `c`,`test`.`t4`.`d` AS `d` from `test`.`t1` join `test`.`t1` `t2` join `test`.`t1` `t2x` join `test`.`t1` `t3x` join `test`.`t1` `t4` where ((`test`.`t2`.`b` = `test`.`t1`.`b`) and (`test`.`t2`.`a` = `test`.`t1`.`a`) and (`test`.`t2x`.`b` = `test`.`t2`.`d`) and (`test`.`t2x`.`a` = `test`.`t2`.`c`) and (`test`.`t3x`.`b` = `test`.`t1`.`d`) and (`test`.`t3x`.`a` = `test`.`t1`.`c`) and (`test`.`t4`.`b` = `test`.`t2x`.`c`) and (`test`.`t4`.`a` = `test`.`t3x`.`c`))
+explain extended
+select straight_join *
+from t1
+join t1 as t2  on t2.a = t1.a and t2.b = t1.b
+join t1 as t2x on t2x.a = t2.c and t2x.b = t2.d
+join t1 as t3  on t3.a = t1.c and t3.b = t1.d
+join t1 as t3x on t3x.a = t3.c and t3x.b = t3.d
+join t1 as t4  on t4.a = t3x.c and t4.b = t2x.c;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	t1	ALL	PRIMARY	NULL	NULL	NULL	16	100.00	Parent of 6 pushed join@1
+1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	8	test.t1.a,test.t1.b	1	100.00	Child of 't1' in pushed join@1
+1	SIMPLE	t2x	eq_ref	PRIMARY	PRIMARY	8	test.t2.c,test.t2.d	1	100.00	Child of 't2' in pushed join@1
+1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	8	test.t1.c,test.t1.d	1	100.00	Child of 't2x' in pushed join@1
+1	SIMPLE	t3x	eq_ref	PRIMARY	PRIMARY	8	test.t3.c,test.t3.d	1	100.00	Child of 't3' in pushed join@1
+1	SIMPLE	t4	eq_ref	PRIMARY	PRIMARY	8	test.t3x.c,test.t2x.c	1	100.00	Child of 't3x' in pushed join@1
+Warnings:
+Note	1003	select straight_join `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t1`.`c` AS `c`,`test`.`t1`.`d` AS `d`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b`,`test`.`t2`.`c` AS `c`,`test`.`t2`.`d` AS `d`,`test`.`t2x`.`a` AS `a`,`test`.`t2x`.`b` AS `b`,`test`.`t2x`.`c` AS `c`,`test`.`t2x`.`d` AS `d`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS `b`,`test`.`t3`.`c` AS `c`,`test`.`t3`.`d` AS `d`,`test`.`t3x`.`a` AS `a`,`test`.`t3x`.`b` AS `b`,`test`.`t3x`.`c` AS `c`,`test`.`t3x`.`d` AS `d`,`test`.`t4`.`a` AS `a`,`test`.`t4`.`b` AS `b`,`test`.`t4`.`c` AS `c`,`test`.`t4`.`d` AS `d` from `test`.`t1` join `test`.`t1` `t2` join `test`.`t1` `t2x` join `test`.`t1` `t3` join `test`.`t1` `t3x` join `test`.`t1` `t4` where ((`test`.`t2`.`b` = `test`.`t1`.`b`) and (`test`.`t2`.`a` = `test`.`t1`.`a`) and (`test`.`t2x`.`b` = `test`.`t2`.`d`) and (`test`.`t2x`.`a` = `test`.`t2`.`c`) and (`test`.`t3`.`b` = `test`.`t1`.`d`) and (`test`.`t3`.`a` = `test`.`t1`.`c`) and (`test`.`t3x`.`b` = 
 `test`.`t3`.`d`) and (`test`.`t3x`.`a` = `test`.`t3`.`c`) and (`test`.`t4`.`b` = `test`.`t2x`.`c`) and (`test`.`t4`.`a` = `test`.`t3x`.`c`))
+explain extended
+select straight_join *
+from t1
+join t1 as t2  on t2.a = t1.a and t2.b = t1.b
+join t1 as t3  on t3.a = t1.c and t3.b = t1.d
+join t1 as t2x on t2x.a = t2.c and t2x.b = t2.d
+join t1 as t3x on t3x.a = t3.c and t3x.b = t3.d
+join t1 as t4  on t4.a = t3x.c and t4.b = t2x.c;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	t1	ALL	PRIMARY	NULL	NULL	NULL	16	100.00	Parent of 6 pushed join@1
+1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	8	test.t1.a,test.t1.b	1	100.00	Child of 't1' in pushed join@1
+1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	8	test.t1.c,test.t1.d	1	100.00	Child of 't2' in pushed join@1
+1	SIMPLE	t2x	eq_ref	PRIMARY	PRIMARY	8	test.t2.c,test.t2.d	1	100.00	Child of 't3' in pushed join@1
+1	SIMPLE	t3x	eq_ref	PRIMARY	PRIMARY	8	test.t3.c,test.t3.d	1	100.00	Child of 't2x' in pushed join@1
+1	SIMPLE	t4	eq_ref	PRIMARY	PRIMARY	8	test.t3x.c,test.t2x.c	1	100.00	Child of 't3x' in pushed join@1
+Warnings:
+Note	1003	select straight_join `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t1`.`c` AS `c`,`test`.`t1`.`d` AS `d`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b`,`test`.`t2`.`c` AS `c`,`test`.`t2`.`d` AS `d`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS `b`,`test`.`t3`.`c` AS `c`,`test`.`t3`.`d` AS `d`,`test`.`t2x`.`a` AS `a`,`test`.`t2x`.`b` AS `b`,`test`.`t2x`.`c` AS `c`,`test`.`t2x`.`d` AS `d`,`test`.`t3x`.`a` AS `a`,`test`.`t3x`.`b` AS `b`,`test`.`t3x`.`c` AS `c`,`test`.`t3x`.`d` AS `d`,`test`.`t4`.`a` AS `a`,`test`.`t4`.`b` AS `b`,`test`.`t4`.`c` AS `c`,`test`.`t4`.`d` AS `d` from `test`.`t1` join `test`.`t1` `t2` join `test`.`t1` `t3` join `test`.`t1` `t2x` join `test`.`t1` `t3x` join `test`.`t1` `t4` where ((`test`.`t2`.`b` = `test`.`t1`.`b`) and (`test`.`t2`.`a` = `test`.`t1`.`a`) and (`test`.`t3`.`b` = `test`.`t1`.`d`) and (`test`.`t3`.`a` = `test`.`t1`.`c`) and (`test`.`t2x`.`b` = `test`.`t2`.`d`) and (`test`.`t2x`.`a` = `test`.`t2`.`c`) and (`test`.`t3x`.`b` = 
 `test`.`t3`.`d`) and (`test`.`t3x`.`a` = `test`.`t3`.`c`) and (`test`.`t4`.`b` = `test`.`t2x`.`c`) and (`test`.`t4`.`a` = `test`.`t3x`.`c`))
+explain extended
+select straight_join *
+from t1
+join t1 as t2  on t2.a = t1.a and t2.b = t1.b
+join t1 as t2x on t2x.a = t2.c and t2x.b = t2.d
+join t1 as t3  on t3.a = t1.c and t3.b = t1.d
+join t1 as t3x on t3x.a = t1.c and t3x.b = t1.d
+join t1 as t4  on t4.a = t3x.c and t4.b = t2x.c;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	t1	ALL	PRIMARY	NULL	NULL	NULL	16	100.00	Parent of 6 pushed join@1
+1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	8	test.t1.a,test.t1.b	1	100.00	Child of 't1' in pushed join@1
+1	SIMPLE	t2x	eq_ref	PRIMARY	PRIMARY	8	test.t2.c,test.t2.d	1	100.00	Child of 't2' in pushed join@1
+1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	8	test.t1.c,test.t1.d	1	100.00	Child of 't1' in pushed join@1
+1	SIMPLE	t3x	eq_ref	PRIMARY	PRIMARY	8	test.t3.a,test.t3.b	1	100.00	Child of 't2x' in pushed join@1; Using where
+1	SIMPLE	t4	eq_ref	PRIMARY	PRIMARY	8	test.t3x.c,test.t2x.c	1	100.00	Child of 't3x' in pushed join@1
+Warnings:
+Note	1003	select straight_join `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t1`.`c` AS `c`,`test`.`t1`.`d` AS `d`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b`,`test`.`t2`.`c` AS `c`,`test`.`t2`.`d` AS `d`,`test`.`t2x`.`a` AS `a`,`test`.`t2x`.`b` AS `b`,`test`.`t2x`.`c` AS `c`,`test`.`t2x`.`d` AS `d`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS `b`,`test`.`t3`.`c` AS `c`,`test`.`t3`.`d` AS `d`,`test`.`t3x`.`a` AS `a`,`test`.`t3x`.`b` AS `b`,`test`.`t3x`.`c` AS `c`,`test`.`t3x`.`d` AS `d`,`test`.`t4`.`a` AS `a`,`test`.`t4`.`b` AS `b`,`test`.`t4`.`c` AS `c`,`test`.`t4`.`d` AS `d` from `test`.`t1` join `test`.`t1` `t2` join `test`.`t1` `t2x` join `test`.`t1` `t3` join `test`.`t1` `t3x` join `test`.`t1` `t4` where ((`test`.`t2`.`b` = `test`.`t1`.`b`) and (`test`.`t2`.`a` = `test`.`t1`.`a`) and (`test`.`t2x`.`b` = `test`.`t2`.`d`) and (`test`.`t2x`.`a` = `test`.`t2`.`c`) and (`test`.`t3`.`b` = `test`.`t1`.`d`) and (`test`.`t3x`.`b` = `test`.`t1`.`d`) and (`test`.`t3`.`a` = 
 `test`.`t1`.`c`) and (`test`.`t3x`.`a` = `test`.`t1`.`c`) and (`test`.`t4`.`b` = `test`.`t2x`.`c`) and (`test`.`t4`.`a` = `test`.`t3x`.`c`))
+explain extended
+select straight_join *
+from t1
+join t1 as t2  on t2.a = t1.a and t2.b = t1.b
+join t1 as t2x on t2x.a = t2.c and t2x.b = t2.d
+join t1 as t3  on t3.a = t1.c and t3.b = t1.b
+join t1 as t3x on t3x.a = t1.c and t3x.b = t1.d
+join t1 as t4  on t4.a = t3x.c and t4.b = t2x.c;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	t1	ALL	PRIMARY	NULL	NULL	NULL	16	100.00	Parent of 6 pushed join@1
+1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	8	test.t1.a,test.t1.b	1	100.00	Child of 't1' in pushed join@1
+1	SIMPLE	t2x	eq_ref	PRIMARY	PRIMARY	8	test.t2.c,test.t2.d	1	100.00	Child of 't2' in pushed join@1
+1	SIMPLE	t3	eq_ref	PRIMARY	PRIMARY	8	test.t1.c,test.t2.b	1	100.00	Child of 't1' in pushed join@1; Using where
+1	SIMPLE	t3x	eq_ref	PRIMARY	PRIMARY	8	test.t3.a,test.t1.d	1	100.00	Child of 't2x' in pushed join@1; Using where
+1	SIMPLE	t4	eq_ref	PRIMARY	PRIMARY	8	test.t3x.c,test.t2x.c	1	100.00	Child of 't3x' in pushed join@1
+Warnings:
+Note	1003	select straight_join `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t1`.`c` AS `c`,`test`.`t1`.`d` AS `d`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b`,`test`.`t2`.`c` AS `c`,`test`.`t2`.`d` AS `d`,`test`.`t2x`.`a` AS `a`,`test`.`t2x`.`b` AS `b`,`test`.`t2x`.`c` AS `c`,`test`.`t2x`.`d` AS `d`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS `b`,`test`.`t3`.`c` AS `c`,`test`.`t3`.`d` AS `d`,`test`.`t3x`.`a` AS `a`,`test`.`t3x`.`b` AS `b`,`test`.`t3x`.`c` AS `c`,`test`.`t3x`.`d` AS `d`,`test`.`t4`.`a` AS `a`,`test`.`t4`.`b` AS `b`,`test`.`t4`.`c` AS `c`,`test`.`t4`.`d` AS `d` from `test`.`t1` join `test`.`t1` `t2` join `test`.`t1` `t2x` join `test`.`t1` `t3` join `test`.`t1` `t3x` join `test`.`t1` `t4` where ((`test`.`t2`.`a` = `test`.`t1`.`a`) and (`test`.`t2x`.`b` = `test`.`t2`.`d`) and (`test`.`t2x`.`a` = `test`.`t2`.`c`) and (`test`.`t2`.`b` = `test`.`t1`.`b`) and (`test`.`t3`.`b` = `test`.`t1`.`b`) and (`test`.`t3x`.`b` = `test`.`t1`.`d`) and (`test`.`t3`.`a` = 
 `test`.`t1`.`c`) and (`test`.`t3x`.`a` = `test`.`t1`.`c`) and (`test`.`t4`.`b` = `test`.`t2x`.`c`) and (`test`.`t4`.`a` = `test`.`t3x`.`c`))
 set ndb_join_pushdown=true;
 explain extended 
 select * from t1 x, t1 y, t1 z, t1 where 
@@ -2495,7 +2577,7 @@ join t3 as y2 on y2.b3 = x2.c3 and y2.d3
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	SIMPLE	x1	ALL	b3,c3,c3_2	NULL	NULL	NULL	7	100.00	Parent of 4 pushed join@1
 1	SIMPLE	y1	ref	b3	b3	9	test.x1.b3,test.x1.d3	1	100.00	Child of 'x1' in pushed join@1; Using where
-1	SIMPLE	x2	ref	b3,c3,c3_2	b3	4	test.x1.b3	1	100.00	Child of 'y1' in pushed join@1
+1	SIMPLE	x2	ref	b3,c3,c3_2	b3	4	test.x1.b3	1	100.00	Child of 'x1' in pushed join@1
 1	SIMPLE	y2	ref	b3	b3	9	test.x2.c3,test.x1.c3	1	100.00	Child of 'x2' in pushed join@1; Using where
 Warnings:
 Note	1003	select straight_join `test`.`x1`.`a3` AS `a3`,`test`.`x1`.`b3` AS `b3`,`test`.`x1`.`c3` AS `c3`,`test`.`x1`.`d3` AS `d3`,`test`.`y1`.`a3` AS `a3`,`test`.`y1`.`b3` AS `b3`,`test`.`y1`.`c3` AS `c3`,`test`.`y1`.`d3` AS `d3`,`test`.`x2`.`a3` AS `a3`,`test`.`x2`.`b3` AS `b3`,`test`.`x2`.`c3` AS `c3`,`test`.`x2`.`d3` AS `d3`,`test`.`y2`.`a3` AS `a3`,`test`.`y2`.`b3` AS `b3`,`test`.`y2`.`c3` AS `c3`,`test`.`y2`.`d3` AS `d3` from `test`.`t3` `x1` join `test`.`t3` `y1` join `test`.`t3` `x2` join `test`.`t3` `y2` where ((`test`.`y1`.`d3` = `test`.`x1`.`d3`) and (`test`.`y1`.`b3` = `test`.`x1`.`b3`) and (`test`.`x2`.`b3` = `test`.`x1`.`b3`) and (`test`.`y2`.`d3` = `test`.`x1`.`c3`) and (`test`.`y2`.`b3` = `test`.`x2`.`c3`))
@@ -2639,8 +2721,7 @@ select *
 from t1
 join t1 as t2 on (t2.b = t1.b or t2.b = t1.a)
 join t1 as t3 on t3.a = t2.a
-join t1 as t4 on t4.a = t3.b
-;
+join t1 as t4 on t4.a = t3.b;
 a	b	c	a	b	c	a	b	c	a	b	c
 1	NULL	2	2	1	NULL	2	1	NULL	1	NULL	2
 1	NULL	2	5	1	NULL	5	1	NULL	1	NULL	2
@@ -2655,12 +2736,25 @@ a	b	c	a	b	c	a	b	c	a	b	c
 6	2	2	3	2	2	3	2	2	2	1	NULL
 6	2	2	6	2	2	6	2	2	2	1	NULL
 set ndb_join_pushdown=true;
+explain extended
+select *
+from t1
+join t1 as t2 on (t2.b = t1.b or t2.b = t1.a)
+join t1 as t3 on t3.a = t2.a
+join t1 as t4 on t4.a = t3.b;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	t2	ALL	PRIMARY,b	NULL	NULL	NULL	6	100.00	Parent of 3 pushed join@1
+1	SIMPLE	t3	eq_ref	PRIMARY,b	PRIMARY	4	test.t2.a	1	100.00	Child of 't2' in pushed join@1
+1	SIMPLE	t4	eq_ref	PRIMARY	PRIMARY	4	test.t3.b	1	100.00	Child of 't3' in pushed join@1
+1	SIMPLE	t1	ALL	PRIMARY,b	NULL	NULL	NULL	6	100.00	Range checked for each record (index map: 0x3)
+Warnings:
+Note	1644	Table 't1' is not pushable: Access type was not chosen at 'prepare' time
+Note	1003	select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t1`.`c` AS `c`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b`,`test`.`t2`.`c` AS `c`,`test`.`t3`.`a` AS `a`,`test`.`t3`.`b` AS `b`,`test`.`t3`.`c` AS `c`,`test`.`t4`.`a` AS `a`,`test`.`t4`.`b` AS `b`,`test`.`t4`.`c` AS `c` from `test`.`t1` join `test`.`t1` `t2` join `test`.`t1` `t3` join `test`.`t1` `t4` where ((`test`.`t3`.`a` = `test`.`t2`.`a`) and (`test`.`t4`.`a` = `test`.`t3`.`b`) and ((`test`.`t1`.`b` = `test`.`t2`.`b`) or (`test`.`t1`.`a` = `test`.`t2`.`b`)))
 select *
 from t1
 join t1 as t2 on (t2.b = t1.b or t2.b = t1.a)
 join t1 as t3 on t3.a = t2.a
-join t1 as t4 on t4.a = t3.b
-;
+join t1 as t4 on t4.a = t3.b;
 a	b	c	a	b	c	a	b	c	a	b	c
 1	NULL	2	2	1	NULL	2	1	NULL	1	NULL	2
 1	NULL	2	5	1	NULL	5	1	NULL	1	NULL	2
@@ -2821,7 +2915,7 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	4	100.00	
 1	SIMPLE	t2	eq_ref	PRIMARY	PRIMARY	4	test.t1.b	1	100.00	
 Warnings:
-Note	1644	Table 't1' not pushable, select list can't contain BLOB columns
+Note	1644	Table 't1' is not pushable: select list can't contain BLOB columns
 Note	1003	select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t1`.`c` AS `c`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b` from `test`.`t1` join `test`.`t2` where (`test`.`t2`.`a` = `test`.`t1`.`b`)
 select *
 from t1, t2
@@ -2856,7 +2950,7 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	4	100.00	
 1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	4	test.t2.b	1	100.00	
 Warnings:
-Note	1644	Table 't1' not pushable, select list can't contain BLOB columns
+Note	1644	Table 't1' is not pushable: select list can't contain BLOB columns
 Note	1003	select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t1`.`c` AS `c`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b` from `test`.`t1` join `test`.`t2` where (`test`.`t1`.`a` = `test`.`t2`.`b`)
 select *
 from t1, t2
@@ -2875,7 +2969,7 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	t2	const	PRIMARY	PRIMARY	4	const	1	100.00	
 1	SIMPLE	t1	eq_ref	PRIMARY	PRIMARY	4	test.t2.b	1	100.00	
 Warnings:
-Note	1644	Table 't1' not pushable, select list can't contain BLOB columns
+Note	1644	Table 't1' is not pushable: select list can't contain BLOB columns
 Note	1003	select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t1`.`c` AS `c`,`test`.`t2`.`a` AS `a`,`test`.`t2`.`b` AS `b` from `test`.`t1` join `test`.`t2` where ((`test`.`t2`.`a` = 3) and (`test`.`t1`.`a` = `test`.`t2`.`b`))
 select *
 from t1, t2
@@ -4171,7 +4265,7 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	x2	ref	ix1	ix1	5	test.x1.a	2	100.00	Child of 'x1' in pushed join@1; Using where
 1	SIMPLE	x3	ref	ix1	ix1	5	test.x1.b	2	100.00	
 Warnings:
-Note	1644	Can't push table 'x3' as child of 'x1', outer join with scan-descendant 'x2' not implemented
+Note	1644	Can't push table 'x3' as child of 'x1', outer join with scan-ancestor 'x2' not implemented
 Note	1003	select straight_join count(0) AS `count(*)` from `test`.`t1` `x1` join `test`.`t1` `x2` left join `test`.`t1` `x3` on((`test`.`x3`.`b` = `test`.`x1`.`b`)) where (`test`.`x2`.`b` = `test`.`x1`.`a`)
 set ndb_join_pushdown=off;
 select straight_join count(*) from t1 as x1 
@@ -4190,12 +4284,11 @@ select straight_join count(*) from t1 as
 join t1 as x2 on x2.b = x1.a
 join t1 as x3 on x3.pk = x1.a join t1 as x4 on x4.b = x3.a;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	SIMPLE	x1	ALL	NULL	NULL	NULL	NULL	13	100.00	Parent of 3 pushed join@1
+1	SIMPLE	x1	ALL	NULL	NULL	NULL	NULL	13	100.00	Parent of 4 pushed join@1
 1	SIMPLE	x2	ref	ix1	ix1	5	test.x1.a	2	100.00	Child of 'x1' in pushed join@1; Using where
-1	SIMPLE	x3	eq_ref	PRIMARY	PRIMARY	4	test.x1.a	1	100.00	Child of 'x1' in pushed join@1
-1	SIMPLE	x4	ref	ix1	ix1	5	test.x3.a	2	100.00	Using where
+1	SIMPLE	x3	eq_ref	PRIMARY	PRIMARY	4	test.x1.a	1	100.00	Child of 'x2' in pushed join@1
+1	SIMPLE	x4	ref	ix1	ix1	5	test.x3.a	2	100.00	Child of 'x3' in pushed join@1; Using where
 Warnings:
-Note	1644	Can't push table 'x4' as child of 'x1', implementation limitations due to bushy scan with 'x2' indirect through 'x1'
 Note	1003	select straight_join count(0) AS `count(*)` from `test`.`t1` `x1` join `test`.`t1` `x2` join `test`.`t1` `x3` join `test`.`t1` `x4` where ((`test`.`x2`.`b` = `test`.`x1`.`a`) and (`test`.`x3`.`pk` = `test`.`x1`.`a`) and (`test`.`x4`.`b` = `test`.`x3`.`a`))
 set ndb_join_pushdown=off;
 select straight_join count(*) from t1 as x1
@@ -4749,8 +4842,8 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	x1	ALL	uk1	NULL	NULL	NULL	3	100.00	
 1	SIMPLE	x2	eq_ref	PRIMARY	PRIMARY	12	test.x1.b	1	100.00	
 Warnings:
-Note	1644	Table 'x1' is not pushable, lock modes other than 'read committed' not implemented
-Note	1644	Table 'x2' is not pushable, lock modes other than 'read committed' not implemented
+Note	1644	Table 'x1' is not pushable: lock modes other than 'read committed' not implemented
+Note	1644	Table 'x2' is not pushable: lock modes other than 'read committed' not implemented
 Note	1003	select `test`.`x1`.`a` AS `a`,`test`.`x1`.`b` AS `b`,`test`.`x1`.`c` AS `c`,`test`.`x2`.`a` AS `a`,`test`.`x2`.`b` AS `b`,`test`.`x2`.`c` AS `c` from `test`.`tc` `x1` join `test`.`tc` `x2` where (`test`.`x2`.`a` = `test`.`x1`.`b`)
 explain extended select * from tc as x1, tc as x2 where x1.b=x2.a;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
@@ -4891,9 +4984,9 @@ CONST_PRUNED_RANGE_SCANS_RECEIVED	6
 LOCAL_TABLE_SCANS_SENT	228
 PRUNED_RANGE_SCANS_RECEIVED	17
 RANGE_SCANS_RECEIVED	718
-READS_NOT_FOUND	404
+READS_NOT_FOUND	407
 READS_RECEIVED	52
-SCAN_ROWS_RETURNED	78728
+SCAN_ROWS_RETURNED	80920
 TABLE_SCANS_RECEIVED	228
 select sum(spj_counts_at_end.val - spj_counts_at_startup.val) as 'LOCAL+REMOTE READS_SENT'
        from spj_counts_at_end, spj_counts_at_startup 
@@ -4901,17 +4994,17 @@ where spj_counts_at_end.counter_name = s
 and (spj_counts_at_end.counter_name = 'LOCAL_READS_SENT'
        or spj_counts_at_end.counter_name = 'REMOTE_READS_SENT');
 LOCAL+REMOTE READS_SENT
-28871
+29026
 drop table spj_counts_at_startup;
 drop table spj_counts_at_end;
 scan_count
-2677
+2530
 pruned_scan_count
 8
 sorted_scan_count
 9
 pushed_queries_defined
-360
+366
 pushed_queries_dropped
 11
 pushed_queries_executed

=== modified file 'mysql-test/suite/ndb/t/ndb_join_pushdown.test'
--- a/mysql-test/suite/ndb/t/ndb_join_pushdown.test	2011-03-17 08:02:01 +0000
+++ b/mysql-test/suite/ndb/t/ndb_join_pushdown.test	2011-04-27 07:42:18 +0000
@@ -477,8 +477,7 @@ from t1
  join t1 as t2 on t2.a = t1.a and t2.b = t1.b
  join t1 as t3 on t3.a = t2.c and t3.b = t1.c;
 
-# t4 is NOT pushable as t2 & t3 does not have 
-# a parent / grandparent relationship
+# t4 is pushable iff we force an artificial parental dependency between t2 & t3.
 explain extended
 select straight_join *
 from t1
@@ -526,10 +525,10 @@ from t1
 # may be made pushable by equality set replacement.
 #
 # BEWARE: mysqld optimizer may do its own replacement
-#    before ha_ndbcluster analyze the AQP. We therefore 
+#    before ha_ndbcluster_push analyze the AQP. We therefore 
 #    provide multiple similar testcases and hope that
 #    some of them will trigger the replacement code in 
-#    ha_ndbcluster :-o
+#    ha_ndbcluster_push :-o
 explain extended
 select straight_join *
 from t1
@@ -608,6 +607,58 @@ from t1
  join t1 as t3 on t3.a = t1.c and t3.b = t1.d
  join t1 as t4 on t4.a = t3.c and t4.b = t1.b;
 
+# Added more multidependency tests;
+#
+
+explain extended
+select straight_join *
+from t1
+ join t1 as t2  on t2.a = t1.a and t2.b = t1.b
+ join t1 as t2x on t2x.a = t2.c and t2x.b = t2.d
+ join t1 as t3x on t3x.a = t1.c and t3x.b = t1.d
+ join t1 as t4  on t4.a = t3x.c and t4.b = t2x.c;
+
+explain extended
+select straight_join *
+from t1
+ join t1 as t2  on t2.a = t1.a and t2.b = t1.b
+ join t1 as t2x on t2x.a = t2.c and t2x.b = t2.d
+ join t1 as t3  on t3.a = t1.c and t3.b = t1.d
+ join t1 as t3x on t3x.a = t3.c and t3x.b = t3.d
+ join t1 as t4  on t4.a = t3x.c and t4.b = t2x.c; 
+
+explain extended
+select straight_join *
+from t1
+ join t1 as t2  on t2.a = t1.a and t2.b = t1.b
+ join t1 as t3  on t3.a = t1.c and t3.b = t1.d
+ join t1 as t2x on t2x.a = t2.c and t2x.b = t2.d
+ join t1 as t3x on t3x.a = t3.c and t3x.b = t3.d
+ join t1 as t4  on t4.a = t3x.c and t4.b = t2x.c; 
+
+# 't3' is not referred as ancestor and should not be
+# included in the forced dependencies
+# (Depends directly on 't1' and can be bushy wrt. to
+#  the other tables)
+explain extended
+select straight_join *
+from t1
+ join t1 as t2  on t2.a = t1.a and t2.b = t1.b
+ join t1 as t2x on t2x.a = t2.c and t2x.b = t2.d
+ join t1 as t3  on t3.a = t1.c and t3.b = t1.d
+ join t1 as t3x on t3x.a = t1.c and t3x.b = t1.d
+ join t1 as t4  on t4.a = t3x.c and t4.b = t2x.c;
+
+# 't3' is still independent - see comment above.
+explain extended
+select straight_join *
+from t1
+ join t1 as t2  on t2.a = t1.a and t2.b = t1.b
+ join t1 as t2x on t2x.a = t2.c and t2x.b = t2.d
+ join t1 as t3  on t3.a = t1.c and t3.b = t1.b
+ join t1 as t3x on t3x.a = t1.c and t3x.b = t1.d
+ join t1 as t4  on t4.a = t3x.c and t4.b = t2x.c;
+
 
 # Test a combination of pushed table scan (x, y)
 #  & pushed EQ-bound (indexScan) (z, t1)
@@ -1459,18 +1510,22 @@ select *
 from t1
 join t1 as t2 on (t2.b = t1.b or t2.b = t1.a)
 join t1 as t3 on t3.a = t2.a
-join t1 as t4 on t4.a = t3.b
-;
+join t1 as t4 on t4.a = t3.b;
 
 set ndb_join_pushdown=true;
 
+explain extended
+select *
+from t1
+join t1 as t2 on (t2.b = t1.b or t2.b = t1.a)
+join t1 as t3 on t3.a = t2.a
+join t1 as t4 on t4.a = t3.b;
 --sorted_result
 select *
 from t1
 join t1 as t2 on (t2.b = t1.b or t2.b = t1.a)
 join t1 as t3 on t3.a = t2.a
-join t1 as t4 on t4.a = t3.b
-;
+join t1 as t4 on t4.a = t3.b;
 
 ## Test subquery execution where 'Full scan on null key' strategy requires
 ## table scan execution in addition to the key lookup which was prepared

=== modified file 'sql/ha_ndbcluster.cc'
--- a/sql/ha_ndbcluster.cc	2011-04-14 08:59:45 +0000
+++ b/sql/ha_ndbcluster.cc	2011-04-27 07:42:18 +0000
@@ -46,9 +46,9 @@
 #include "ha_ndbcluster_cond.h"
 #include "ha_ndbcluster_tables.h"
 #include "ha_ndbcluster_connection.h"
+#include "abstract_query_plan.h"
 
 #include <mysql/plugin.h>
-#include <abstract_query_plan.h>
 #include <ndb_version.h>
 
 #ifdef ndb_dynamite
@@ -440,380 +440,128 @@ struct st_ndb_status {
   long long api_client_stats[Ndb::NumClientStatistics];
 };
 
-bool ndbcluster_join_pushdown_enabled(THD* thd)
+/**
+ * This is a list of NdbQueryDef objects that have been created within a 
+ * transaction. This list is kept to make sure that they are all released 
+ * when the transaction ends.
+ * An NdbQueryDef object is required to live longer than any NdbQuery object
+ * instantiated from it. Since NdbQueryObjects may be kept until the 
+ * transaction ends, this list is necessary.
+ */
+class ndb_query_def_list
 {
-  return THDVAR(thd, join_pushdown);
-}
+public:
+  ndb_query_def_list(const NdbQueryDef* def, const ndb_query_def_list* next):
+    m_def(def), m_next(next){}
 
-int
-ha_ndbcluster::make_pushed_join(ndb_pushed_builder_ctx& context,
-                                const AQP::Table_access* join_root)
-{
-  DBUG_ENTER("make_pushed_join");
+  const NdbQueryDef* get_def() const
+  { return m_def; }
 
-  DBUG_ASSERT (context.is_pushable_as_parent(join_root));
-  context.set_root(join_root);
-  const AQP::Join_plan& plan= context.plan();
+  const ndb_query_def_list* get_next() const
+  { return m_next; }
 
-  DBUG_PRINT("enter", ("Table %d as root is pushable", join_root->get_access_no()));
-  DBUG_EXECUTE("info", join_root->dbug_print(););
+private:
+  const NdbQueryDef* const m_def;
+  const ndb_query_def_list* const m_next;
+};
 
-  const AQP::enum_access_type access_type= join_root->get_access_type();
 
-  /**
-   * Past this point we know at least join_root to be join pushable 
-   * as parent operation. Search for tables to be appendable as child 
-   * operation.
-   * Parent operation is not defined before we have found the first 
-   * appendable child.
-   */
-  NdbQueryBuilder* const builder= NdbQueryBuilder::create();
-  if (unlikely (builder==NULL))
-  {
-    DBUG_RETURN(HA_ERR_OUT_OF_MEM);
-  }
-
-  uint push_cnt= 0;
-  uint fld_refs= 0;
-  Field* referred_fields[ndb_pushed_join::MAX_REFERRED_FIELDS];
+/**
+ * Try to find pushable subsets of a join plan.
+ * @param hton unused (maybe useful for other engines).
+ * @param thd Thread.
+ * @param plan The join plan to examine.
+ * @return Possible error code.
+ */
+static
+int ndbcluster_make_pushed_join(handlerton *hton,
+                                THD* thd,
+                                AQP::Join_plan* plan)
+{
+  DBUG_ENTER("ndbcluster_make_pushed_join");
+  (void)ha_ndb_ext; // prevents compiler warning.
 
-  for (uint join_cnt= join_root->get_access_no()+1; join_cnt<plan.get_access_count(); join_cnt++)
+  if (THDVAR(thd, join_pushdown))
   {
-    const Item* join_items[ndb_pushed_join::MAX_LINKED_KEYS+1];
-    const AQP::Table_access* join_parent;
-
-    const AQP::Table_access* const join_tab= plan.get_table_access(join_cnt);
-    const NdbQueryOperationDef* query_op= NULL;
+    ndb_pushed_builder_ctx pushed_builder(*plan);
 
-    if (!context.is_pushable_as_child(join_tab, join_items, join_parent))
+    for (uint i= 0; i < plan->get_access_count()-1; i++)
     {
-      DBUG_PRINT("info", ("Table %d not pushable as child", join_cnt));
-      continue;
-    }
-    /**
-     * If this is the first child in pushed join we need to define the 
-     * parent operation first.
-     */
-    if (push_cnt == 0)
-    {
-      NdbQueryOptions options;
-      if (m_cond)
-      {
-        NdbInterpretedCode code(m_table);
-        if (m_cond->generate_scan_filter(&code, NULL) != 0)
-          ERR_RETURN(code.getNdbError());
-
-        options.setInterpretedCode(code);
-      }
+      const AQP::Table_access* const join_root= plan->get_table_access(i);
+      const ndb_pushed_join* pushed_join= NULL;
 
-      if (ndbcluster_is_lookup_operation(access_type))
+      // Try to build a ndb_pushed_join starting from 'join_root'
+      int error= pushed_builder.make_pushed_join(join_root, pushed_join);
+      if (unlikely(error))
       {
-        const KEY* const key= 
-          &table->key_info[join_root->get_index_no()];
-        const NdbQueryOperand* root_key[ndb_pushed_join::MAX_KEY_PART+1]= {NULL};
-
-        for (uint i= 0; i < key->key_parts; i++)
-        {
-          root_key[i]= builder->paramValue();
-          if (unlikely(!root_key[i]))
-          {
-            const NdbError error = builder->getNdbError();
-            builder->destroy();
-            ERR_RETURN(error);
-          }
-        }
-        root_key[key->key_parts]= NULL;
-
-        // Primary key access assumed
-       if (access_type == AQP::AT_PRIMARY_KEY || 
-           access_type == AQP::AT_MULTI_PRIMARY_KEY)
-       {
-          DBUG_PRINT("info", ("Root operation is 'primary-key-lookup'"));
-          DBUG_ASSERT(join_root->get_index_no() == 
-                      static_cast<int>(table->s->primary_key));
-          query_op= builder->readTuple(m_table, root_key, &options);
-        }
-        else
+        if (error < 0)  // getNdbError() gives us the error code
         {
-          DBUG_PRINT("info", ("Root operation is 'unique-index-lookup'"));
-          const NdbDictionary::Index* const index 
-            = m_index[join_root->get_index_no()].unique_index;
-          DBUG_ASSERT(index);
-          query_op= builder->readTuple(index, m_table, root_key, &options);
+          ERR_SET(pushed_builder.getNdbError(),error);
         }
-      }
-      /**
-       *  AT_MULTI_MIXED may have 'ranges' which are pure single key lookups also.
-       *  In our current implementation these are converted into range access in the
-       *  pushed MRR implementation. However, the future plan is to build both 
-       *  RANGE and KEY pushable joins for these.
-       */
-      else if (access_type == AQP::AT_ORDERED_INDEX_SCAN  ||
-               access_type == AQP::AT_MULTI_MIXED)
-      {
-        DBUG_ASSERT(join_root->get_index_no() >= 0);
-        DBUG_ASSERT(m_index[join_root->get_index_no()].index != NULL);
-
-        DBUG_PRINT("info", ("Root operation is 'equal-range-lookup'"));
-        DBUG_PRINT("info", ("Creating scanIndex on index id:%d, name:%s",
-                            join_root->get_index_no(), 
-                            m_index[join_root->get_index_no()]
-                            .index->getName()));
-
-        // Bounds will be generated and supplied during execute
-        query_op= 
-          builder->scanIndex(m_index[join_root->get_index_no()].index, m_table, 0, &options);
-      }
-      else if (access_type == AQP::AT_TABLE_SCAN) 
-      {
-        DBUG_PRINT("info", ("Root operation is 'table scan'"));
-        query_op= builder->scanTable(m_table, &options);
-      }
-      else
-      {
-        DBUG_ASSERT(false);
+        join_root->get_table()->file->print_error(error, MYF(0));
+        DBUG_RETURN(error);
       }
 
-      if (unlikely(!query_op))
+      // Assign any produced pushed_join definitions to 
+      // the ha_ndbcluster instance representing its root.
+      if (pushed_join != NULL)
       {
-        const NdbError error = builder->getNdbError();
-        builder->destroy();
-        ERR_RETURN(error);
-      }
-
-      context.add_pushed(join_root, NULL, query_op);
-      push_cnt= 1;
-    } // End: 'define root'
-
-    DBUG_PRINT("info", ("Appending child, join_cnt:%d, key_parts:%d", push_cnt, 
-                        join_tab->get_no_of_key_fields()));
-
-    DBUG_ASSERT(join_tab->get_table()->file->ht == ht);
-    const ha_ndbcluster* const handler=
-      static_cast<ha_ndbcluster*>(join_tab->get_table()->file);
+        ha_ndbcluster* const handler=
+          static_cast<ha_ndbcluster*>(join_root->get_table()->file);
 
-    const KEY* const key= &handler->table->key_info[join_tab->get_index_no()];
-
-    const NdbQueryOperand* linked_key[ndb_pushed_join::MAX_LINKED_KEYS]= {NULL};
-    uint map[ndb_pushed_join::MAX_LINKED_KEYS+1];
-
-    const uint key_fields= join_tab->get_no_of_key_fields();
-    DBUG_ASSERT(key_fields > 0 && key_fields <= key->key_parts);
-
-    if (ndbcluster_is_lookup_operation(join_tab->get_access_type()))
-    {
-      ndbcluster_build_key_map(handler->m_table, 
-                               handler->m_index[join_tab->get_index_no()],
-                               key, map);
-    }
-    else
-    {
-      for (uint ix = 0; ix < key_fields; ix++)
-      {
-        map[ix]= ix;
-      }
-    }
-
-    DBUG_ASSERT (join_parent!=NULL);
-    bool need_explicit_parent= true;
-    const ndb_table_access_map parent_map(join_parent);
-    const KEY_PART_INFO *key_part= key->key_part;
-    for (uint i= 0; i < key_fields; i++, key_part++)
-    {
-      const Item* const item= join_items[i];
-      linked_key[map[i]]= NULL;
-      DBUG_ASSERT(item->const_item() == item->const_during_execution());
-      if (item->const_item())
-      {
-        /** 
-         * Propagate Items constant value to Field containing the value of this 
-         * key_part:
-         */
-        Field* const field= key_part->field;
-        const int error= 
-          const_cast<Item*>(item)->save_in_field_no_warnings(field, true);
+        error= handler->assign_pushed_join(pushed_join);
         if (unlikely(error))
         {
-          DBUG_PRINT("info", ("Failed to store constant Item into Field -> not"
-                              " pushable"));
-          builder->destroy();
-          DBUG_RETURN(0);
-        }
-        if (field->is_real_null())
-        {
-          DBUG_PRINT("info", ("NULL constValues in key -> not pushable"));
-          builder->destroy();
-          DBUG_RETURN(0);  // TODO, handle gracefull -> continue?
-        }
-        const uchar* const ptr= (field->real_type() == MYSQL_TYPE_VARCHAR)
-                ? field->ptr + ((Field_varstring*)field)->length_bytes
-                : field->ptr;
-
-        linked_key[map[i]]= builder->constValue(ptr, field->data_length());
-      }
-      else
-      {
-        DBUG_ASSERT(item->type() == Item::FIELD_ITEM);
-        const Item_field* const field_item= static_cast<const Item_field*>(item);
-        const ndb_table_access_map used_table(field_item->used_tables());
-
-        if (context.join_scope().contain(used_table))
-        {
-          const AQP::Table_access* referred_table;
-          if (likely(parent_map == used_table))
-          {
-            referred_table= join_parent;
-            need_explicit_parent= false;
-          }
-          else
-          {
-            referred_table= context.get_referred_table_access(used_table);
-          }
-
-          // Locate the parent operation for this 'join_items[]'.
-          // May refer any of the preceeding parent tables
-          const NdbQueryOperationDef* const parent_op= 
-            context.get_query_operation(referred_table);
-          DBUG_ASSERT(parent_op != NULL);
-
-          DBUG_ASSERT(field_item->type() == Item::FIELD_ITEM);
-          // TODO use field_index ??
-          linked_key[map[i]]= 
-            builder->linkedValue(parent_op, 
-                                 field_item->field_name);
-        }
-        else
-        {
-          DBUG_ASSERT(context.const_scope().contain(used_table));
-          // Outside scope of join plan, Handle as parameter as its value
-          // will be known when we are ready to execute this query.
-          if (unlikely(fld_refs >= ndb_pushed_join::MAX_REFERRED_FIELDS))
-          {
-            DBUG_PRINT("info", ("Too many Field refs ( >= MAX_REFERRED_FIELDS) "
-                                "encountered"));
-            builder->destroy();
-            DBUG_RETURN(0);  // TODO, handle gracefull -> continue?
-          }
-          referred_fields[fld_refs++]= field_item->field;
-          linked_key[map[i]]= builder->paramValue();
+          delete pushed_join;
+          handler->print_error(error, MYF(0));
+          DBUG_RETURN(error);
         }
       }
-      if (unlikely(!linked_key[map[i]]))
-      {
-        const NdbError error = builder->getNdbError();
-        builder->destroy();
-        ERR_RETURN(error);
-      }
-    } // for (uint i= 0; i < key->key_parts; i++, key_part++)
-
-    const NdbDictionary::Table* const table= handler->m_table;
- 
-    NdbQueryOptions options;
-    if (join_tab->get_join_type(join_parent) == AQP::JT_INNER_JOIN)
-    {
-      options.setMatchType(NdbQueryOptions::MatchNonNull);
     }
-    if (need_explicit_parent)
-    {
-      const NdbQueryOperationDef* parent_op= 
-        context.get_query_operation(join_parent);
-      DBUG_ASSERT(parent_op != NULL);
-      options.setParent(parent_op);
-    }
-    if (handler->m_cond)
-    {
-      NdbInterpretedCode code(table);
-      if (handler->m_cond->generate_scan_filter(&code, NULL) != 0)
-        ERR_RETURN(code.getNdbError());
-
-      options.setInterpretedCode(code);
-    }
-
-    if (join_tab->get_access_type() == AQP::AT_ORDERED_INDEX_SCAN)
-    {
-      const NdbQueryIndexBound bounds(linked_key);
-      query_op= builder->scanIndex(handler->m_index[join_tab->get_index_no()]
-                                   .index, table, &bounds, &options);
-    }
-    // Link on primary key or an unique index
-    else if (join_tab->get_access_type() == AQP::AT_PRIMARY_KEY)
-    {
-      query_op= builder->readTuple(table, linked_key, &options);
-    }
-    else
-    {
-      DBUG_ASSERT(join_tab->get_access_type() == AQP::AT_UNIQUE_KEY);
-      const NdbDictionary::Index* const index
-        = handler->m_index[join_tab->get_index_no()].unique_index;
-      DBUG_ASSERT(index != NULL);
-      query_op= builder->readTuple(index, table, linked_key, &options);
-    }
-
-    if (unlikely(!query_op))
-    {
-      const NdbError error = builder->getNdbError();
-      builder->destroy();
-      ERR_RETURN(error);
-    }
-
-    context.add_pushed(join_tab, join_parent, query_op);
-    push_cnt++;
-  } // for (uint join_cnt= 1; join_cnt<plan.get_access_count(); join_cnt++)
-
-  if (push_cnt < 2)
-  {
-    builder->destroy();
-    DBUG_RETURN(0);
-  }
-
-  const NdbQueryDef* const query_def= builder->prepare();
-  if (unlikely(!query_def))
-  {
-    const NdbError error = builder->getNdbError();
-    builder->destroy();
-    ERR_RETURN(error);
   }
+  DBUG_RETURN(0);
+} // ndbcluster_make_pushed_join
+  
+/**
+ * In case a pushed join having the table for this handler as its root
+ * has been produced. ::assign_pushed_join() is responsible for setting
+ * up this ha_ndbcluster instance such that the prepared NdbQuery 
+ * might be instantiated at execution time.
+ */
+int
+ha_ndbcluster::assign_pushed_join(const ndb_pushed_join* pushed_join)
+{
+  DBUG_ENTER("assign_pushed_join");
+  const NdbQueryDef* const query_def= &pushed_join->get_query_def();
 
   m_thd_ndb->m_pushed_queries_defined++;
   /* 
    * Append query definition to transaction specific list, so that it can be
    * released when the transaction ends.  
    */
-  const ndb_query_def_list* const list_item = 
+  const ndb_query_def_list* const list_item= 
     new ndb_query_def_list(query_def, m_thd_ndb->m_query_defs);
   if (unlikely(list_item == NULL))
   {
-    builder->destroy();
     DBUG_RETURN(HA_ERR_OUT_OF_MEM);
   }
   m_thd_ndb->m_query_defs = list_item;
-  
-  DBUG_PRINT("info", ("Created pushed join with %d child operations", 
-                      push_cnt-1));
-  m_pushed_join_member= new ndb_pushed_join(
-                                     context.plan(), 
-                                     context.join_scope(), 
-                                     fld_refs, 
-                                     referred_fields, 
-                                     query_def);
-  if (unlikely (m_pushed_join_member == NULL))
-  {
-    builder->destroy();
-    DBUG_RETURN(HA_ERR_OUT_OF_MEM);
-  }
 
-  for (uint i = 0; i < push_cnt; i++)
+  for (uint i = 0; i < pushed_join->get_operation_count(); i++)
   {
-    const TABLE* const tab= m_pushed_join_member->get_table(i);
+    const TABLE* const tab= pushed_join->get_table(i);
     DBUG_ASSERT(tab->file->ht == ht);
     ha_ndbcluster* child= static_cast<ha_ndbcluster*>(tab->file);
-    child->m_pushed_join_member= m_pushed_join_member;
+    child->m_pushed_join_member= pushed_join;
     child->m_pushed_join_operation= i;
   }
 
-  builder->destroy();
+  DBUG_PRINT("info", ("Assigned pushed join with %d child operations", 
+                      pushed_join->get_operation_count()-1));
+
   DBUG_RETURN(0);
-} // ha_ndbcluster::make_pushed_join()
+} // ha_ndbcluster::assign_pushed_join()
+
 
 /*
   Map from thr_lock_type to NdbOperation::LockMode
@@ -828,47 +576,47 @@ NdbOperation::LockMode get_ndb_lock_mode
   return NdbOperation::LM_CommittedRead;
 }
 
-//ndb_pushed_builder_ctx::enum_pushability
-int
-ha_ndbcluster::get_pushability() const
+/**
+ * First level of filtering tables which *maybe* may be part of
+ * a pushed query: Returning 'false' will eliminate this table
+ * from being a part of a pushed join.
+ * A 'reason' for rejecting this table is required if 'false'
+ * is returned.
+ */
+bool
+ha_ndbcluster::maybe_pushable_join(const char*& reason) const
 {
+  reason= "";
   if (uses_blob_value(table->read_set))
   {
-    EXPLAIN_NO_PUSH("Table '%s' not pushable, "
-                    "select list can't contain BLOB columns",
-                     table->alias);
-    return 0;
+    reason= "select list can't contain BLOB columns";
+    return false;
   }
   if (m_user_defined_partitioning)
   {
-    EXPLAIN_NO_PUSH("Table '%s' not pushable, "
-                    "has user defined partioning",
-                     table->alias);
-    return 0;
+    reason= "has user defined partioning";
+    return false;
   }
 
   // Pushed operations may not set locks.
   const NdbOperation::LockMode lockMode= get_ndb_lock_mode(m_lock.type);
   switch (lockMode)
   {
+  case NdbOperation::LM_CommittedRead:
+    return true;
+
   case NdbOperation::LM_Read:
   case NdbOperation::LM_Exclusive:
-    EXPLAIN_NO_PUSH("Table '%s' is not pushable, "
-                    "lock modes other than 'read committed' not implemented",
-                    table->alias);
-    return 0;
+    reason= "lock modes other than 'read committed' not implemented";
+    return false;
         
-  case NdbOperation::LM_CommittedRead:
-    break;
-      
   default: // Other lock modes not used by handler.
     assert(false);
-    return 0;
+    return false;
   }
 
-  return (ndb_pushed_builder_ctx::PUSHABLE_AS_CHILD | 
-          ndb_pushed_builder_ctx::PUSHABLE_AS_PARENT);
-} // ha_ndbcluster::get_pushability()
+  return true;
+} // ha_ndbcluster::is_pushable()
 
 
 /**
@@ -1054,7 +802,7 @@ ha_ndbcluster::create_pushed_join(NdbQue
     const TABLE* const tab= m_pushed_join_member->get_table(i);
     ha_ndbcluster* handler= static_cast<ha_ndbcluster*>(tab->file);
 
-    DBUG_ASSERT(handler->m_pushed_join_operation==i);
+    DBUG_ASSERT(handler->m_pushed_join_operation==(int)i);
     NdbQueryOperation* const op= query->getQueryOperation(i);
     handler->m_pushed_operation= op;
 

=== modified file 'sql/ha_ndbcluster.h'
--- a/sql/ha_ndbcluster.h	2011-03-24 13:34:51 +0000
+++ b/sql/ha_ndbcluster.h	2011-04-27 07:42:18 +0000
@@ -52,13 +52,9 @@ class NdbQuery;
 class NdbQueryOperation;
 class NdbQueryOperationTypeWrapper;
 class NdbQueryParamValue;
+class ndb_pushed_join;
 class ndb_query_def_list;
 
-namespace AQP{
-  class Join_plan;
-  class Table_access;
-};
-
 typedef enum ndb_index_type {
   UNDEFINED_INDEX = 0,
   PRIMARY_KEY_INDEX = 1,
@@ -410,12 +406,12 @@ class Thd_ndb 
 int ndbcluster_commit(handlerton *hton, THD *thd, bool all);
 class ha_ndbcluster: public handler
 {
+  friend class ndb_pushed_builder_ctx;
+
  public:
   ha_ndbcluster(handlerton *hton, TABLE_SHARE *table);
   ~ha_ndbcluster();
 
-  int get_pushability() const;
-
 #ifndef NDB_WITHOUT_READ_BEFORE_WRITE_REMOVAL
   void column_bitmaps_signal(uint sig_type);
 #endif
@@ -593,8 +589,8 @@ static void set_tabname(const char *path
  */
   void cond_pop();
 
-  int make_pushed_join(class ndb_pushed_builder_ctx& context,
-		       const AQP::Table_access* join_root);
+  bool maybe_pushable_join(const char*& reason) const;
+  int assign_pushed_join(const ndb_pushed_join* pushed_join);
 
   bool test_push_flag(enum ha_push_flag flag) const;
 
@@ -938,7 +934,7 @@ private:
   ha_rows m_autoincrement_prefetch;
 
   // Joins pushed to NDB.
-  const class ndb_pushed_join
+  const ndb_pushed_join
        *m_pushed_join_member;            // Pushed join def. I am member of
   int m_pushed_join_operation;           // Op. id. in above pushed join
   static const int PUSHED_ROOT= 0;       // Op. id. if I'm root
@@ -972,13 +968,6 @@ int ndbcluster_table_exists_in_engine(TH
                                       const char *db, const char *name);
 void ndbcluster_print_error(int error, const NdbOperation *error_op);
 
-/**
- * Calling THDVAR(thd, join_pushdown) from another source file would not work,
- * since MYSQL_THDVAR_BOOL is static to ha_ndbcluster.cc and cannot be made
- * extern in any clean way.
- */
-bool ndbcluster_join_pushdown_enabled(THD* thd);
-
 static const char ndbcluster_hton_name[]= "ndbcluster";
 static const int ndbcluster_hton_name_length=sizeof(ndbcluster_hton_name)-1;
 extern int ndbcluster_terminating;

=== modified file 'sql/ha_ndbcluster_push.cc'
--- a/sql/ha_ndbcluster_push.cc	2011-03-31 07:44:04 +0000
+++ b/sql/ha_ndbcluster_push.cc	2011-04-27 07:42:18 +0000
@@ -34,20 +34,14 @@
 
 #include "ha_ndbcluster.h"
 #include "ha_ndbcluster_push.h"
-#include <ndbapi/NdbApi.hpp>
+#include "ha_ndbcluster_binlog.h"
 #include "ha_ndbcluster_cond.h"
-#include <util/Bitmask.hpp>
-#include <ndbapi/NdbIndexStat.hpp>
+#include "abstract_query_plan.h"
+
+#include <ndbapi/NdbApi.hpp>
 #include <ndbapi/NdbInterpretedCode.hpp>
 #include "../storage/ndb/src/ndbapi/NdbQueryBuilder.hpp"
-#include "../storage/ndb/src/ndbapi/NdbQueryOperation.hpp"
 
-#include "ha_ndbcluster_binlog.h"
-#include "ha_ndbcluster_tables.h"
-#include "ha_ndbcluster_connection.h"
-
-#include <mysql/plugin.h>
-#include <abstract_query_plan.h>
 #include <ndb_version.h>
 
 
@@ -56,72 +50,16 @@
 #define assert(x) do { if(x) break; ::printf("%s %d: assert failed: %s\n", __FILE__, __LINE__, #x); ::fflush(stdout); ::signal(SIGABRT,SIG_DFL); ::abort(); ::kill(::getpid(),6); ::kill(::getpid(),9); } while (0)
 #endif
 
-ndb_pushed_join
-::ndb_pushed_join(const AQP::Join_plan& plan, 
-                  const ndb_table_access_map& pushed_operations,
-                  uint field_refs, Field* const fields[],
-                  const NdbQueryDef* query_def)
-:
-  m_query_def(query_def),
-  m_operation_count(0),
-  m_field_count(field_refs)
-{
-  DBUG_ASSERT(query_def != NULL);
-  DBUG_ASSERT(field_refs <= MAX_REFERRED_FIELDS);
-  ndb_table_access_map searched;
-  for (uint i= 0; !(searched==pushed_operations); i++)
-  {
-    const AQP::Table_access* const join_tab= plan.get_table_access(i);
-    ndb_table_access_map table_map(join_tab);
-    if (pushed_operations.contain(table_map))
-    {
-      DBUG_ASSERT(m_operation_count < MAX_PUSHED_OPERATIONS);
-      m_tables[m_operation_count++] = join_tab->get_table();
-      searched.add(table_map);
-    }
-  }
-  for (uint i= 0; i < field_refs; i++)
-  {
-    m_referred_fields[i] = fields[i];
-  }
-}
-
-/**
- * Try to find pushable subsets of a join plan.
- * @param hton unused (maybe useful for other engines).
- * @param thd Thread.
- * @param plan The join plan to examine.
- * @return Possible error code.
- */
-int ndbcluster_make_pushed_join(handlerton *hton, THD* thd,
-                                AQP::Join_plan* plan)
-{
-  DBUG_ENTER("ndbcluster_make_pushed_join");
-  (void)ha_ndb_ext; // prevents compiler warning.
-
-  if (!ndbcluster_join_pushdown_enabled(thd))
-    DBUG_RETURN(0);
-
-  ndb_pushed_builder_ctx context(*plan);
-  for (uint i= 0; i < plan->get_access_count()-1; i++)
-  {
-    const AQP::Table_access* const join_root=  plan->get_table_access(i);
-    if (context.is_pushable_as_parent(join_root))
-    {
-      ha_ndbcluster* const handler=
-        static_cast<ha_ndbcluster*>(join_root->get_table()->file);
-
-      int error= handler->make_pushed_join(context,join_root);
-      if (unlikely(error))
-      {
-        handler->print_error(error, MYF(0));
-        DBUG_RETURN(error);
-      }
-    }
-  }
+#define EXPLAIN_NO_PUSH(msgfmt, ...)                              \
+do                                                                \
+{                                                                 \
+  if (unlikely(current_thd->lex->describe & DESCRIBE_EXTENDED))   \
+  {                                                               \
+    ndbcluster_explain_no_push ((msgfmt), __VA_ARGS__);           \
+  }                                                               \
+}                                                                 \
+while(0)
 
-  DBUG_RETURN(0);
-} // ndbcluster_make_pushed_join
 
 static inline const char* get_referred_field_name(const Item_field* field_item)
 {
@@ -135,11 +73,18 @@ static const char* get_referred_table_ac
   return field_item->field->table->alias;
 }
 
+static bool ndbcluster_is_lookup_operation(AQP::enum_access_type accessType)
+{
+  return accessType == AQP::AT_PRIMARY_KEY ||
+    accessType == AQP::AT_MULTI_PRIMARY_KEY ||
+    accessType == AQP::AT_UNIQUE_KEY;
+}
+
 /**
  * Used by 'explain extended' to explain why an operation could not be pushed.
  * @param[in] msgfmt printf style format string.
  */
-void ndbcluster_explain_no_push(const char* msgfmt, ...)
+static void ndbcluster_explain_no_push(const char* msgfmt, ...)
 {
   va_list args;
   char wbuff[1024];
@@ -150,333 +95,286 @@ void ndbcluster_explain_no_push(const ch
                wbuff);
 } // ndbcluster_explain_no_push();
 
-void ndb_pushed_builder_ctx::set_root(const AQP::Table_access* join_root)
+
+uint
+ndb_table_access_map::first_table(uint start) const
 {
-  DBUG_ASSERT(join_root->get_join_plan() == &m_plan);
-  m_join_root= join_root;
-  m_join_scope.clear_all();
-  m_const_scope.clear_all();
-
-  m_join_scope.add(join_root);
-  for (uint i= 0; i<join_root->get_access_no(); i++)
-    m_const_scope.add(m_plan.get_table_access(i));
+  for (uint table_no= start; table_no<length(); table_no++)
+  {
+    if (contain(table_no))
+      return table_no;
+  }
+  return length();
 }
 
-void
-ndb_pushed_builder_ctx::add_pushed(
-                  const AQP::Table_access* table,
-                  const AQP::Table_access* parent,
-                  const NdbQueryOperationDef* query_op)
-{
-  uint table_no= table->get_access_no();
-  DBUG_ASSERT(table_no < MAX_TABLES);
-  m_join_scope.add(table);
-  m_tables[table_no].op= query_op;
-  m_tables[table_no].m_maybe_pushable= 0; // Exclude from further pushing
-  if (likely(parent))
-  {
-    uint parent_no= parent->get_access_no();
-
-    // Aggregated set of parent and grand...grand...parents to this table
-    ndb_table_access_map parent_map(parent);
-    DBUG_ASSERT(m_join_scope.contain(parent_map));
-    m_tables[table_no].m_parent= parent_no;
-    m_tables[table_no].m_ancestors= m_tables[parent_no].m_ancestors;
-    m_tables[table_no].m_ancestors.add(parent_map);
-
-    // Maintain which scan operation is the last in a possible
-    // linear list of scan operations. 
-    if (!ndbcluster_is_lookup_operation(table->get_access_type()))
-    {
-      while (parent_no != MAX_TABLES)
-      {
-        m_tables[parent_no].m_last_scan_descendant= table_no;
-        parent_no = m_tables[parent_no].m_parent;
-      }
-    }
-  }
-  else
+uint
+ndb_table_access_map::last_table(uint start) const
+{
+  uint table_no= start;
+  while(true)
   {
-    m_tables[table_no].m_ancestors.clear_all();
+    if (contain(table_no))
+      return table_no;
+    else if (table_no == 0)
+      return length();
+    table_no--;
   }
-} // ndb_pushed_builder_ctx::add_pushed
+}
 
-/**
- *  get_referred_table_access()
- *
- * Locate the 'Table_access' object for table with the specified bitmap id
- */
-const AQP::Table_access*
-ndb_pushed_builder_ctx::get_referred_table_access(const ndb_table_access_map& find_table) const
+ndb_pushed_join::ndb_pushed_join(
+                  const ndb_pushed_builder_ctx& builder,
+                  const NdbQueryDef* query_def)
+:
+  m_query_def(query_def),
+  m_operation_count(0),
+  m_field_count(builder.m_fld_refs)
 {
+  DBUG_ASSERT(query_def != NULL);
+  DBUG_ASSERT(builder.m_fld_refs <= MAX_REFERRED_FIELDS);
   ndb_table_access_map searched;
-  for (uint i= join_root()->get_access_no(); !(searched==m_join_scope); i++)
+  for (uint tab_no= 0; !(searched==builder.m_join_scope); tab_no++)
   {
-    const AQP::Table_access* const table= m_plan.get_table_access(i);
-    ndb_table_access_map table_map(table);
-    if (m_join_scope.contain(table_map))
-    { if (find_table==table_map)
-        return table;
-      searched.add(table_map);
+    const AQP::Table_access* const join_tab= builder.m_plan.get_table_access(tab_no);
+    if (builder.m_join_scope.contain(tab_no))
+    {
+      DBUG_ASSERT(m_operation_count < MAX_PUSHED_OPERATIONS);
+      m_tables[m_operation_count++] = join_tab->get_table();
+      searched.add(tab_no);
     }
   }
-  return NULL;
-} // ndb_pushed_builder_ctx::get_referred_table_access
-
-/**
- * Set up the 'm_maybe_pushable' property of each table from the 'Abstract Query Plan' associated
- * with this ndb_pushed_builder_ctx. A table may be possibly pushable as both:
- * PUSHABLE_AS_CHILD and/or PUSHABLE_AS_PARENT.
- * When a table is annotated as not PUSHABLE_AS_... it will be excluded from further
- * pushability investigation for this specific table.
- */
-void
-ndb_pushed_builder_ctx::init_pushability()
-{
-  for (uint i= 0; i< m_plan.get_access_count(); i++)
+  for (uint i= 0; i < builder.m_fld_refs; i++)
   {
-    m_tables[i].m_maybe_pushable= 0;
+    m_referred_fields[i] = builder.m_referred_fields[i];
+  }
+}
 
-    const AQP::Table_access* const table_access = m_plan.get_table_access(i);
-    if (table_access->get_table()->file->ht != ndbcluster_hton)
-    {
-      EXPLAIN_NO_PUSH("Table '%s' not in ndb engine, not pushable", 
-                      table_access->get_table()->alias);
-      continue;
-    }
+ndb_pushed_builder_ctx::ndb_pushed_builder_ctx(const AQP::Join_plan& plan)
+:
+  m_plan(plan),
+  m_join_root(),
+  m_join_scope(),
+  m_const_scope(),
+  m_fld_refs(0),
+  m_builder(NULL)
+{ 
+  const uint count= m_plan.get_access_count();
+  (void)ha_ndb_ext; // Prevents compiler warning.
 
-    switch (table_access->get_access_type())
+  DBUG_ASSERT(count <= MAX_TABLES);
+  if (count > 1)
+  {
+    for (uint i= 0; i < count; i++)
     {
-    case AQP::AT_VOID:
-      DBUG_ASSERT(false);
-      break;
+      m_tables[i].m_maybe_pushable= 0;
+
+      const AQP::Table_access* const table = m_plan.get_table_access(i);
+      if (table->get_table()->file->ht != ndbcluster_hton)
+      {
+        EXPLAIN_NO_PUSH("Table '%s' not in ndb engine, not pushable", 
+                        table->get_table()->alias);
+        continue;
+      }
 
-    case AQP::AT_FIXED:
-      EXPLAIN_NO_PUSH("Table '%s' was optimized away, or const'ified by optimizer",
-                      table_access->get_table()->alias);
-      break;
-
-    case AQP::AT_OTHER:
-      EXPLAIN_NO_PUSH("Table '%s' is not pushable: %s",
-                      table_access->get_table()->alias, 
-                      table_access->get_other_access_reason());
-      break;
-
-    case AQP::AT_UNDECIDED:
-      EXPLAIN_NO_PUSH("Access type for table '%s' will not be chosen before"
-                      " execution time and '%s' is therefore not pushable.",
-                      table_access->get_table()->alias,
-                      table_access->get_table()->alias);
-      break;
+      switch (table->get_access_type())
+      {
+      case AQP::AT_VOID:
+        DBUG_ASSERT(false);
+        break;
+
+      case AQP::AT_FIXED:
+        EXPLAIN_NO_PUSH("Table '%s' was optimized away, or const'ified by optimizer",
+                        table->get_table()->alias);
+        break;
+
+      case AQP::AT_OTHER:
+        EXPLAIN_NO_PUSH("Table '%s' is not pushable: %s",
+                        table->get_table()->alias, 
+                        table->get_other_access_reason());
+        break;
+
+      case AQP::AT_UNDECIDED:
+        EXPLAIN_NO_PUSH("Table '%s' is not pushable: "
+                        "Access type was not chosen at 'prepare' time",
+                        table->get_table()->alias);
+        break;
   
-    default:
-      m_tables[i].m_maybe_pushable= 
-        static_cast<ha_ndbcluster*>(table_access->get_table()->file)
-        ->get_pushability();
-      break;
+      default:
+        const char* reason= NULL;
+        const ha_ndbcluster* handler=
+          static_cast<ha_ndbcluster*>(table->get_table()->file);
+
+        if (handler->maybe_pushable_join(reason))
+        {
+          m_tables[i].m_maybe_pushable= PUSHABLE_AS_CHILD | PUSHABLE_AS_PARENT;
+        }
+        else
+        {
+          EXPLAIN_NO_PUSH("Table '%s' is not pushable: %s",
+                          table->get_table()->alias, reason);
+        }
+        break;
+      }
     }
-  }
 
-  m_tables[0].m_maybe_pushable &= ~PUSHABLE_AS_CHILD;
-  m_tables[m_plan.get_access_count()-1].m_maybe_pushable &= ~PUSHABLE_AS_PARENT;
-} // ndb_pushed_builder_ctx::init_pushability()
+    m_tables[0].m_maybe_pushable &= ~PUSHABLE_AS_CHILD;
+    m_tables[count-1].m_maybe_pushable &= ~PUSHABLE_AS_PARENT;
 
+    // Fill in table for maping internal <-> external table enumeration
+    for (uint i= 0; i < count; i++)
+    {
+      const AQP::Table_access* const table = m_plan.get_table_access(i);
+      uint external= table->get_table()->tablenr;
+      DBUG_ASSERT(external <= MAX_TABLES);
 
-bool
-ndb_pushed_builder_ctx::is_pushable_as_parent(const AQP::Table_access* table)
+      m_remap[i].to_external= external;
+      m_remap[external].to_internal= i;
+    }
+  }
+} // ndb_pushed_builder_ctx::ndb_pushed_builder_ctx()
+
+ndb_pushed_builder_ctx::~ndb_pushed_builder_ctx()
 {
-  DBUG_ENTER("is_pushable_as_parent");
-  uint table_no = table->get_access_no();
-  if ((m_tables[table_no].m_maybe_pushable & PUSHABLE_AS_PARENT) != PUSHABLE_AS_PARENT)
+  if (m_builder)
   {
-    DBUG_PRINT("info", ("Table %d already reported 'not pushable_as_parent'", table_no));
-    DBUG_RETURN(false);
+    m_builder->destroy();
   }
+}
 
-  const AQP::enum_access_type access_type= table->get_access_type();
-  DBUG_ASSERT(access_type != AQP::AT_VOID);
+const NdbError& ndb_pushed_builder_ctx::getNdbError() const
+{
+  DBUG_ASSERT(m_builder);
+  return m_builder->getNdbError();
+}
 
-  if (access_type == AQP::AT_MULTI_UNIQUE_KEY)
+/**
+ * Get *internal* table_no of table referred by 'key_item'
+ */
+uint
+ndb_pushed_builder_ctx::get_table_no(const Item* key_item) const
+{
+  DBUG_ASSERT(key_item->type() == Item::FIELD_ITEM);
+  table_map bitmap= key_item->used_tables();
+
+  for (uint i= 0; i<MAX_TABLES && bitmap!=0; i++, bitmap>>=1)
   {
-    EXPLAIN_NO_PUSH("Table '%s' is not pushable, "
-                    "access type 'MULTI_UNIQUE_KEY' not implemented",
-                     table->get_table()->alias);
-    m_tables[table_no].m_maybe_pushable &= ~PUSHABLE_AS_PARENT;
-    DBUG_RETURN(false);
+    if (bitmap & 1)
+    {
+      DBUG_ASSERT(bitmap == 0x01);  // Only a single table in 'bitmap'
+      return m_remap[i].to_internal;
+    }
   }
+  return MAX_TABLES;
+}
 
-  DBUG_RETURN(true);
-} // ndb_pushed_builder_ctx::is_pushable_as_parent()
-
-/*********************
- * This method examines a key item (could be part of a lookup key or a scan 
- * bound) for a table access operation and calculates the set of possible
- * parents. (These are possible parent table access operations in the query 
- * tree that will be pushed to the ndb.)
+/**
+ * Main entry point to build a pushed join having 'join_root'
+ * as it first operation.
+ *
+ * If the root operation is pushable, we append as many 'child' 
+ * operations as possible to the pushed join.
+ *
+ * This currently is implemented as a 3 pass algorithm:
+ *
+ *  1) Analyze each child and add it to 'm_join_scope' as 
+ *    'pushable' if it qualifies as such. Part of this phase
+ *     is also calculations of possible parents for each table.
+ *
+ *  2) Determine the parent to be used among the set of possible
+ *     parents. This is decided based on simple heuristic where
+ *     the goal is to employ filters as soon as possible,  
+ *     reduce the fanout of intermediate results, and utilize
+ *     the parallelism of the SPJ block whenever considdered optimal.
+ *
+ *  3) Build the pushed query.
  *
- * @param[in] table The table access operation to which the key item belongs.
- * @param[in] key_item The key_item to examine
- * @param[in] key_part_info Metatdata about the key item.
- * @param[out] field_parents The set of possible parents for 'key_item' 
- * ('join_root' if keys are constant).
- * @return True if at least one possible parent was found. (False means that 
- * operation cannot be pushed).
  */
-bool ndb_pushed_builder_ctx
-::find_field_parents(const AQP::Table_access* table,
-                     const Item* key_item, 
-                     const KEY_PART_INFO* key_part_info,
-                     ndb_table_access_map& field_parents)
+int 
+ndb_pushed_builder_ctx::make_pushed_join(
+                            const AQP::Table_access* join_root,
+                            const ndb_pushed_join* &pushed_join)
 {
-  DBUG_ENTER("find_field_parents()");
-  const uint tab_no = table->get_access_no();
+  DBUG_ENTER("make_pushed_join");
+  pushed_join= NULL;
 
-  // TODO: extend to also handle ->const_during_execution() which includes 
-  // mysql parameters in addition to contant values/expressions
-  if (key_item->const_item())  // ...->const_during_execution() ?
+  if (is_pushable_with_root(join_root))
   {
-    field_parents= ndb_table_access_map(join_root());
-    DBUG_PRINT("info", (" Item type:%d is 'const_item'", key_item->type()));
-    DBUG_RETURN(true);
+    int error;
+    error= optimize_query_plan();
+    if (unlikely(error))
+      DBUG_RETURN(error);
+    
+    error= build_query();
+    if (unlikely(error))
+      DBUG_RETURN(error);
+
+    const NdbQueryDef* const query_def= m_builder->prepare();
+    if (unlikely(query_def == NULL))
+      DBUG_RETURN(-1);  // Get error with ::getNdbError()
+
+    pushed_join= new ndb_pushed_join(*this, query_def);
+    if (unlikely (pushed_join == NULL))
+      DBUG_RETURN(HA_ERR_OUT_OF_MEM);
+
+    DBUG_PRINT("info", ("Created pushed join with %d child operations", 
+                        pushed_join->get_operation_count()-1));
   }
-  else if (key_item->type() != Item::FIELD_ITEM)
+  DBUG_RETURN(0);
+} // ndb_pushed_builder_ctx::make_pushed_join()
+
+
+/**
+ * If there is a pushable query starting with 'root'; add as many
+ * child operations as possible to this 'ndb_pushed_builder_ctx' starting
+ * with that join_root.
+ */
+bool
+ndb_pushed_builder_ctx::is_pushable_with_root(const AQP::Table_access* root)
+{
+  DBUG_ENTER("is_pushable_with_root");
+
+  const uint root_no= root->get_access_no();
+  if ((m_tables[root_no].m_maybe_pushable & PUSHABLE_AS_PARENT) != PUSHABLE_AS_PARENT)
   {
-    EXPLAIN_NO_PUSH("Can't push table '%s' as child, "
-                    "column '%s' does neither 'ref' a column nor a constant",
-                    table->get_table()->alias,
-                    key_part_info->field->field_name);
-    m_tables[tab_no].m_maybe_pushable &= ~PUSHABLE_AS_CHILD; // Permanently disable as child
+    DBUG_PRINT("info", ("Table %d already reported 'not pushable_as_parent'", root_no));
     DBUG_RETURN(false);
   }
 
-  const Item_field* const key_item_field 
-    = static_cast<const Item_field*>(key_item);
-
-  const int key_part_no = key_item - table->get_key_field(0);
-  (void)key_part_no; // kill warning
-
-  DBUG_PRINT("info", ("keyPart:%d, field:%s.%s",
-              key_part_no, key_item_field->field->table->alias, 
-                      key_item_field->field->field_name));
+  const AQP::enum_access_type access_type= root->get_access_type();
+  DBUG_ASSERT(access_type != AQP::AT_VOID);
 
-  if (!key_item_field->field
-      ->eq_def(key_part_info->field))
+  if (access_type == AQP::AT_MULTI_UNIQUE_KEY)
   {
-    EXPLAIN_NO_PUSH("Can't push table '%s' as child, "
-                    "column '%s' does not have same datatype as ref'ed "
-                    "column '%s.%s'",
-                    table->get_table()->alias,
-                    key_part_info->field->field_name,
-                    key_item_field->field->table->alias, 
-                    key_item_field->field->field_name);
-    m_tables[tab_no].m_maybe_pushable &= ~PUSHABLE_AS_CHILD; // Permanently disable as child
+    EXPLAIN_NO_PUSH("Table '%s' is not pushable, "
+                    "access type 'MULTI_UNIQUE_KEY' not implemented",
+                     root->get_table()->alias);
+    m_tables[root_no].m_maybe_pushable &= ~PUSHABLE_AS_PARENT;
     DBUG_RETURN(false);
   }
 
   /**
-   * Below this point 'key_item_field' is a candidate for refering a parent table
-   * in a pushed join. It should either directly refer a parent common to all
-   * FIELD_ITEMs, or refer a grandparent of this common parent.
-   * There are different cases which should be handled:
-   *
-   *  1) 'key_item_field' may already refer one of the parent available within our
-   *      pushed scope.
-   *  2)  By using the equality set, we may find alternative parent references which
-   *      may make this a pushed join.
+   * Past this point we know at least root to be pushable as parent
+   * operation. Search remaining tables appendable if '::is_pushable_as_child()'
    */
+  DBUG_PRINT("info", ("Table %d is pushable as root", root->get_access_no()));
+  DBUG_EXECUTE("info", root->dbug_print(););
+  m_fld_refs= 0;
+  m_join_root= root;
+  m_const_scope.set_prefix(root_no);
+  m_join_scope= ndb_table_access_map(root_no);
 
-  ///////////////////////////////////////////////////////////////////
-  // 0) Prepare for calculating parent candidates for this FIELD_ITEM
-  //
-  field_parents.clear_all();
-
-  ////////////////////////////////////////////////////////////////////
-  // 1) Add our existing parent reference to the set of parent candidates
-  //
-  const ndb_table_access_map parent_map(key_item_field->used_tables());
-
-  if (m_join_scope.contain(parent_map))
-  {
-    field_parents.add(parent_map);
-  }
-
-  //////////////////////////////////////////////////////////////////
-  // 2) Use the equality set to possibly find more parent candidates
-  //    usable by substituting existing 'key_item_field'
-  //
-  AQP::Equal_set_iterator equal_iter(&m_plan, key_item_field);
-  const Item_field* substitute_field= equal_iter.next();
-  while (substitute_field != NULL)
+  uint push_cnt= 0;
+  for (uint tab_no= root->get_access_no()+1; tab_no<m_plan.get_access_count(); tab_no++)
   {
-    if (substitute_field != key_item_field)
+    const AQP::Table_access* const table= m_plan.get_table_access(tab_no);
+    if (is_pushable_as_child(table))
     {
-      ndb_table_access_map substitute_table(substitute_field->used_tables());
-      if (m_join_scope.contain(substitute_table))
-      {
-        DBUG_PRINT("info", 
-                   (" join_items[%d] %s.%s can be replaced with %s.%s",
-                    key_part_no,
-                    get_referred_table_access_name(key_item_field),
-                    get_referred_field_name(key_item_field),
-                    get_referred_table_access_name(substitute_field),
-                    get_referred_field_name(substitute_field)));
-
-        field_parents.add(substitute_table);
-      }
+      push_cnt++;
     }
-    substitute_field= equal_iter.next();
-  } // while(substitute_field != NULL)
-
-  if (!field_parents.is_clear_all())
-  {
-    DBUG_RETURN(true);
   }
+  DBUG_RETURN(push_cnt>0);
 
-  if (m_const_scope.contain(parent_map))
-  {
-    // This key item is const. and did not cause the set of possible parents
-    // to be recalculated. Reuse what we had before this key item.
-    DBUG_ASSERT(field_parents.is_clear_all());
-    /** 
-     * Scan queries cannot be pushed if the pushed query may refer column 
-     * values (paramValues) from rows stored in a join cache.  
-     */
-    if (!ndbcluster_is_lookup_operation(join_root()->get_access_type()))
-    {
-      const st_table* const referred_tab = key_item_field->field->table;
-      uint access_no = tab_no;
-      do
-      {
-        DBUG_ASSERT(access_no > 0);
-        access_no--;
-        if (m_plan.get_table_access(access_no)->uses_join_cache())
-        {
-          EXPLAIN_NO_PUSH("Cannot push table '%s' as child of '%s', since "
-                          "it referes to column '%s.%s' which will be stored "
-                          "in a join buffer.",
-                          table->get_table()->alias, 
-                          join_root()->get_table()->alias,
-                          get_referred_table_access_name(key_item_field),
-                          get_referred_field_name(key_item_field));
-          DBUG_RETURN(false);
-        }
-      } while (m_plan.get_table_access(access_no)->get_table() 
-               != referred_tab);
+} // ndb_pushed_builder_ctx::is_pushable_with_root()
 
-    } // if (!ndbcluster_is_lookup_operation(root_type)
-    field_parents= ndb_table_access_map(join_root());
-    DBUG_RETURN(true);
-  }
-  else
-  {
-    EXPLAIN_NO_PUSH("Can't push table '%s' as child of '%s', "
-                    "column '%s.%s' is outside scope of pushable join",
-                     table->get_table()->alias, join_root()->get_table()->alias,
-                     get_referred_table_access_name(key_item_field),
-                     get_referred_field_name(key_item_field));
-    DBUG_RETURN(false);
-  }
-} // ndb_pushed_builder_ctx::find_field_parents()
 
 /***************************************************************
  *  is_pushable_as_child()
@@ -494,29 +392,26 @@ bool ndb_pushed_builder_ctx
  * to resolve cases (2) above) where multiple parents are refered.
  * If needed too make a child pushable, we replace parent 
  * references with another from the COND_EQUAL sets which make
- * it pushable . The modified join condition is returned in 
- * join_items[] .
+ * it pushable .
  ****************************************************************/
 bool
 ndb_pushed_builder_ctx::is_pushable_as_child(
-                           const AQP::Table_access* table,
-                           const Item* join_items[ndb_pushed_join::MAX_LINKED_KEYS+1],
-                           const AQP::Table_access*& parent)
+                           const AQP::Table_access* table)
 {
   DBUG_ENTER("is_pushable_as_child");
-  const uint tab_no = table->get_access_no();
-  parent= NULL;
-
-  DBUG_ASSERT (join_root() < table);
+  const uint root_no= m_join_root->get_access_no();
+  const uint tab_no= table->get_access_no();
 
+  DBUG_ASSERT(tab_no > root_no);
+  
   if ((m_tables[tab_no].m_maybe_pushable & PUSHABLE_AS_CHILD) != PUSHABLE_AS_CHILD)
   {
     DBUG_PRINT("info", ("Table %s already known 'not is_pushable_as_child'", table->get_table()->alias));
     DBUG_RETURN(false);
   }
 
+  const AQP::enum_access_type root_type= m_join_root->get_access_type();
   const AQP::enum_access_type access_type= table->get_access_type();
-  const AQP::enum_access_type root_type= join_root()->get_access_type();
 
   if (!(ndbcluster_is_lookup_operation(access_type) || 
         access_type==AQP::AT_ORDERED_INDEX_SCAN))
@@ -533,17 +428,19 @@ ndb_pushed_builder_ctx::is_pushable_as_c
   {
     EXPLAIN_NO_PUSH("Push of table '%s' as scan-child "
                     "with lookup-root '%s' not implemented",
-                     table->get_table()->alias, join_root()->get_table()->alias);
+                     table->get_table()->alias,
+                     m_join_root->get_table()->alias);
     // 'table' may still be PUSHABLE_AS_CHILD with another parent
     DBUG_RETURN(false);
   }
 
-  if (access_type==AQP::AT_ORDERED_INDEX_SCAN && join_root()->is_fixed_ordered_index())  
+  if (access_type==AQP::AT_ORDERED_INDEX_SCAN && m_join_root->is_fixed_ordered_index())  
   {
     // root must be an ordered index scan - Thus it cannot have other scan descendant.
     EXPLAIN_NO_PUSH("Push of table '%s' as scan-child "
                     "with ordered indexscan-root '%s' not implemented",
-                     table->get_table()->alias, join_root()->get_table()->alias);
+                     table->get_table()->alias,
+                     m_join_root->get_table()->alias);
     DBUG_RETURN(false);
   }
 
@@ -556,7 +453,7 @@ ndb_pushed_builder_ctx::is_pushable_as_c
     DBUG_RETURN(false);
   }
 
-  for (uint i = tab_no - 1; i >= join_root()->get_access_no() && i < ~uint(0); 
+  for (uint i = tab_no - 1; i >= root_no && i < ~uint(0); 
        i--)
   {
     if (m_plan.get_table_access(i)->uses_join_cache())
@@ -564,7 +461,7 @@ ndb_pushed_builder_ctx::is_pushable_as_c
       EXPLAIN_NO_PUSH("Cannot push table '%s' as child of table '%s'. Doing so "
                       "would prevent using join buffer for table '%s'.",
                       table->get_table()->alias,
-                      join_root()->get_table()->alias,
+                      m_join_root->get_table()->alias,
                       m_plan.get_table_access(i+1)->get_table()->alias);
       DBUG_RETURN(false);
     }
@@ -573,64 +470,91 @@ ndb_pushed_builder_ctx::is_pushable_as_c
   DBUG_PRINT("info", ("Table:%d, Checking %d REF keys", tab_no, 
                       table->get_no_of_key_fields()));
 
+  /*****
+   * Calculate the set of possible parents for table, where:
+   *  - 'current' are those currently being referred by the 
+   *     FIELD_ITEMs as set up by the MySQL optimizer.
+   *  - 'common' are those we may refer (possibly through the EQ-sets)
+   *     such that all FIELD_ITEMs are from the same parent.
+   *  - 'extended' are those parents refered from some of the 
+   *     FIELD_ITEMs, and having the rest of the referred FIELD_ITEM 
+   *     tables available as 'grandparent refs'
+   *     (The SPJ block can handle field references to any ancestor
+   *      operation, not just the (direct) parent).
+   *
+   * In addition there are firm dependencies between some parents
+   * such that all 'depend_parents' must be referred as an ancestors
+   * of the table. By default 'depend_parents' will at least contain
+   * the most 'grandparent' of the extended parents.
+   *
+   ****/
   ndb_table_access_map current_parents;
-  ndb_table_access_map parents(join_root());
+  ndb_table_access_map common_parents(m_join_scope);
+  ndb_table_access_map extend_parents;
+  ndb_table_access_map depend_parents;
 
   for (uint key_part_no= 0; 
        key_part_no < table->get_no_of_key_fields(); 
        key_part_no++)
   {
     const Item* const key_item= table->get_key_field(key_part_no);
-    join_items[key_part_no]= key_item;
-    current_parents.add(ndb_table_access_map(key_item->used_tables()));
+    const KEY_PART_INFO* key_part= table->get_key_part_info(key_part_no);
 
-    /* All parts of the key must be fields in some of the preceeding 
-     * tables 
-     */
-    ndb_table_access_map field_parents;
-    if (!find_field_parents(table,
-                            key_item,
-                            table->get_key_part_info(key_part_no), 
-                            field_parents))
+    if (key_item->const_item()) // REF is a litteral or field from const-table
     {
-      DBUG_RETURN(false);
+      DBUG_PRINT("info", (" Item type:%d is 'const_item'", key_item->type()));
+      if (!is_const_item_pushable(key_item, key_part))
+      {
+        DBUG_RETURN(false);
+      }
     }
-    /* Now we must merge the set of possible parents for this key with the set
-     * of possible parents for all preceding keys.
-     */
-    ndb_table_access_map new_parents(parents);
-    // First find the operations present in both sets.
-    new_parents.intersect(field_parents);
-
-    /* Secondly, add each operation which is only in one of the sets, but
-     * which is a descendant of some operation in the other set.
-     * The SPJ block can handle field references to any ancestor operation,
-     * not just the (direct) parent. 
-     */
-    for (uint parent_no= join_root()->get_access_no(); parent_no < tab_no;
-         parent_no++)
+    else if (key_item->type() == Item::FIELD_ITEM)
     {
-      const AQP::Table_access* const parent_candidate= 
-        m_plan.get_table_access(parent_no);
-
-      if (parents.contain_table(parent_candidate) && 
-          !field_parents.contain_table(parent_candidate) &&
-          is_child_of(parent_candidate, field_parents))
+      /**
+       * Calculate all parents FIELD_ITEM may refer - Including those 
+       * available through usage of equality sets.
+       */
+      ndb_table_access_map field_parents;
+      if (!is_field_item_pushable(table, key_item, key_part, field_parents))
       {
-        new_parents.add(parent_candidate);
+        DBUG_RETURN(false);
       }
-      else if (!parents.contain_table(parent_candidate) && 
-          field_parents.contain_table(parent_candidate) &&
-          is_child_of(parent_candidate, parents))
+
+      if (key_item->type() == Item::FIELD_ITEM)
       {
-        new_parents.add(parent_candidate);
+        uint referred_table_no= get_table_no(key_item);
+        current_parents.add(referred_table_no);
       }
-    }
-    parents= new_parents;
 
-  } // for (uint key_part_no= 0 ...
+      /**
+       * Calculate 'common_parents' as the set of possible 'field_parents'
+       * available from all 'key_part'.
+       */
+      common_parents.intersect(field_parents);
 
-  join_items[table->get_no_of_key_fields()]= NULL;
+      /**
+       * 'Extended' parents are refered from some 'FIELD_ITEM', and contain
+       * all parents directly referred, or available as 'depend_parents'. 
+       * The later excludes those before the first (grand-)parent
+       * available from all 'field_parents' (first_grandparent).
+       * However, it also introduce a dependency of those
+       * tables to really be available as grand parents.
+       */
+      extend_parents.add(field_parents);
+
+      const uint first= field_parents.first_table(root_no);
+      depend_parents.add(first);
+    }
+    else
+    {
+      EXPLAIN_NO_PUSH("Can't push table '%s' as child, "
+                      "column '%s' does neither 'ref' a column nor a constant",
+                      table->get_table()->alias,
+                      key_part->field->field_name);
+      m_tables[tab_no].m_maybe_pushable &= ~PUSHABLE_AS_CHILD; // Permanently disable as child
+      DBUG_RETURN(false);
+    }
+  } // for (uint key_part_no= 0 ...
 
   if (m_const_scope.contain(current_parents))
   {
@@ -639,232 +563,714 @@ ndb_pushed_builder_ctx::is_pushable_as_c
     //       allow such tables to be included in the pushed join.
     EXPLAIN_NO_PUSH("Can't push table '%s' as child of '%s', "
                     "their dependency is 'const'",
-                     table->get_table()->alias, join_root()->get_table()->alias);
+                     table->get_table()->alias,
+                     m_join_root->get_table()->alias);
     DBUG_RETURN(false);
   }
-  else if (parents.is_clear_all())
+  else if (extend_parents.is_clear_all())
   {
     EXPLAIN_NO_PUSH("Can't push table '%s' as child of '%s', "
                     "no parents found within scope",
-                     table->get_table()->alias, join_root()->get_table()->alias);
+                     table->get_table()->alias,
+                     m_join_root->get_table()->alias);
     DBUG_RETURN(false);
   }
 
-  DBUG_ASSERT(m_join_scope.contain(parents));
-
-  /**
-   * Parent is selected among the set of 'parents'. To improve
-   * fanout for lookup operations (bushy joins!) we prefer the most grandparent of the anchestors.
-   * As scans can't be bushy currently, we try to serialize these by moving them 'down'.
-   */
-  uint parent_no;
-  if (ndbcluster_is_lookup_operation(table->get_access_type()))
-  {
-    for (parent_no= join_root()->get_access_no();
-         parent_no < tab_no && !parents.contain_table(m_plan.get_table_access(parent_no));
-         parent_no++)
-    {}
-  }
-  else // scan operation
+  if (!ndbcluster_is_lookup_operation(table->get_access_type()))
   {
-    parent_no= tab_no-1;
-    while (!parents.contain_table(m_plan.get_table_access(parent_no)))
+    /**
+     * Currently we do not support 'bushy' (or star joined) scans): 
+     * If there are preceding scan operations, add a (artificial) dependency
+     * to this (scan-)table which makes it non-bushy!
+     * Terminate search at first scan ancester, as the presence if this
+     * scan guarante that the tree is non scan-bushy above.
+     *
+     *  NOTE: This will also force the cross product between rows from these
+     *        artificial parent to be materialized in the SPJ block - Which adds
+     *        extra (huge) communication overhead.
+     *        As a longer term solution bushy scans should be nativily
+     *        supported by SPJ.
+     */
+    const AQP::Table_access* scan_ancestor= NULL;
+    for (uint ancestor_no= tab_no-1; ancestor_no >= root_no; ancestor_no--)
     {
-      DBUG_ASSERT(parent_no > join_root()->get_access_no());
-      parent_no--;
+      if (!m_join_scope.contain(ancestor_no))
+        continue;
+
+      scan_ancestor= m_plan.get_table_access(ancestor_no);
+      if (!ndbcluster_is_lookup_operation(scan_ancestor->get_access_type()))
+      {
+        depend_parents.add(ancestor_no);
+        break; // As adding this scanop was prev. allowed: Above ancestor can't be scan bushy
+      }
     }
+    DBUG_ASSERT(scan_ancestor != NULL);
+
     /**
-     * If parent already has a scan descendant:
-     *   appending 'table' will make this a 'bushy scan' which we don't yet nativily support as a pushed operation.
-     *   We can solve this by appending this table after the last existing scan operation in the query.
-     *   This cause an artificial grandparent dependency to be created to the actuall parent.
+     * Outer joining scan-scan is not supported, due to the following problem:
+     * Consider the query:
+     *
+     * select * from t1 left join t2 
+     *   where t1.attr=t2.ordered_index and predicate(t1.row, t2. row);
      *
-     *  NOTE: This will also force the cross product between rows from these artificial parent to be
-     *        created in the SPJ block - Which adds extra (huge) communication overhead.
-     *        As a longer term solution bushy scans should be nativily supported by SPJ.
+     * Where 'predicate' cannot be pushed to the ndb. The ndb api may then
+     * return:
+     * +---------+---------+
+     * | t1.row1 | t2.row1 | 
+     * | t1.row2 | t2.row1 | 
+     * | t1.row1 | t2.row2 |
+     * +---------+---------+
+     * Now assume that all rows but [t1.row1, t2.row1] satisfies 'predicate'.
+     * mysqld would be confused since the rows are not grouped on t1 values.
+     * It would therefor generate a NULL row such that it returns:
+     * +---------+---------+
+     * | t1.row1 | NULL    | -> Error! 
+     * | t1.row2 | t2.row1 | 
+     * | t1.row1 | t2.row2 |
+     * +---------+---------+
+     * 
+     * (Outer joining with scan may be indirect through lookup operations 
+     * inbetween)
      */
-
-    // 'm_last_scan_descendant' is the candidate to be added as an artificial grandparent.
-    if (m_tables[parent_no].m_last_scan_descendant < MAX_TABLES)
+    if (scan_ancestor && 
+       table->get_join_type(scan_ancestor) == AQP::JT_OUTER_JOIN)
     {
-      uint descendant_no= m_tables[parent_no].m_last_scan_descendant;
+      EXPLAIN_NO_PUSH("Can't push table '%s' as child of '%s', "
+                      "outer join with scan-ancestor '%s' not implemented",
+                       table->get_table()->alias,
+                       m_join_root->get_table()->alias,
+                       scan_ancestor->get_table()->alias);
+      DBUG_RETURN(false);
+    }
+  } // scan operation
 
-      const AQP::Table_access* const scan_descendant = m_plan.get_table_access(descendant_no);
-      parent= m_plan.get_table_access(parent_no);
-      if (scan_descendant->get_join_type(parent) == AQP::JT_OUTER_JOIN)
-      {
-        DBUG_PRINT("info", ("  There are outer joins between parent and artificial parent -> can't append"));
-        EXPLAIN_NO_PUSH("Can't push table '%s' as child of '%s', "
-                        "implementation limitations for outer joins",
-                        table->get_table()->alias, join_root()->get_table()->alias);
-        DBUG_RETURN(false);
-      }
-      parent_no= descendant_no;
-//    parent= scan_descendant;
-      DBUG_PRINT("info", ("  Force artificial grandparent dependency through scan-child %s",
-                         scan_descendant->get_table()->alias));
+  DBUG_ASSERT(m_join_scope.contain(common_parents));
+  DBUG_ASSERT(m_join_scope.contain(extend_parents));
+  DBUG_ASSERT(extend_parents.is_clear_all() ||
+              extend_parents.contain(common_parents));
+  /**
+   * Register calculated parent sets - ::optimize() choose from these.
+   */
+  m_tables[tab_no].m_common_parents= common_parents;
+  m_tables[tab_no].m_extend_parents= extend_parents;
+  m_tables[tab_no].m_depend_parents= depend_parents;
+  m_tables[tab_no].m_parent= MAX_TABLES;
 
-      /**
-       * Outer joining scan-scan is not supported, due to the following problem:
-       * Consider the query:
-       *
-       * select * from t1 left join t2 
-       *   where t1.attr=t2.ordered_index and predicate(t1.row, t2. row);
-       *
-       * Where 'predicate' cannot be pushed to the ndb. The ndb api may then
-       * return:
-       * +---------+---------+
-       * | t1.row1 | t2.row1 | 
-       * | t1.row2 | t2.row1 | 
-       * | t1.row1 | t2.row2 |
-       * +---------+---------+
-       * Now assume that all rows but [t1.row1, t2.row1] satisfies 'predicate'.
-       * mysqld would be confused since the rows are not grouped on t1 values.
-       * It would therefor generate a NULL row such that it returns:
-       * +---------+---------+
-       * | t1.row1 | NULL    | -> Error! 
-       * | t1.row2 | t2.row1 | 
-       * | t1.row1 | t2.row2 |
-       * +---------+---------+
-       * 
-       * (Outer joining with scan may be indirect through lookup operations 
-       * inbetween)
-       */
-      if (scan_descendant && 
-         table->get_join_type(scan_descendant) == AQP::JT_OUTER_JOIN)
+  m_tables[tab_no].m_maybe_pushable= 0; // Exclude from further pushing
+  m_join_scope.add(tab_no);
+
+  DBUG_RETURN(true);
+} // ndb_pushed_builder_ctx::is_pushable_as_child
+
+
+/*********************
+ * This method examines a key item (could be part of a lookup key or a scan 
+ * bound) for a table access operation and calculates the set of possible
+ * parents. (These are possible parent table access operations in the query 
+ * tree that will be pushed to the ndb.)
+ *
+ * @param[in] table The table access operation to which the key item belongs.
+ * @param[in] key_item The key_item to examine
+ * @param[in] key_part Metatdata about the key item.
+ * @param[out] field_parents The set of possible parents for 'key_item' 
+ * ('join_root' if keys are constant).
+ * @return True if at least one possible parent was found. (False means that 
+ * operation cannot be pushed).
+ */
+bool ndb_pushed_builder_ctx::is_field_item_pushable(
+                     const AQP::Table_access* table,
+                     const Item* key_item, 
+                     const KEY_PART_INFO* key_part,
+                     ndb_table_access_map& field_parents)
+{
+  DBUG_ENTER("is_field_item_pushable()");
+  const uint tab_no = table->get_access_no();
+  DBUG_ASSERT(key_item->type() == Item::FIELD_ITEM);
+
+  const Item_field* const key_item_field 
+    = static_cast<const Item_field*>(key_item);
+
+  DBUG_PRINT("info", ("keyPart:%d, field:%s.%s",
+              (int)(key_item - table->get_key_field(0)),
+              key_item_field->field->table->alias, 
+              key_item_field->field->field_name));
+
+  if (!key_item_field->field->eq_def(key_part->field))
+  {
+    EXPLAIN_NO_PUSH("Can't push table '%s' as child, "
+                    "column '%s' does not have same datatype as ref'ed "
+                    "column '%s.%s'",
+                    table->get_table()->alias,
+                    key_part->field->field_name,
+                    key_item_field->field->table->alias, 
+                    key_item_field->field->field_name);
+    m_tables[tab_no].m_maybe_pushable &= ~PUSHABLE_AS_CHILD; // Permanently disable as child
+    DBUG_RETURN(false);
+  }
+
+  /**
+   * Below this point 'key_item_field' is a candidate for refering a parent table
+   * in a pushed join. It should either directly refer a parent common to all
+   * FIELD_ITEMs, or refer a grandparent of this common parent.
+   * There are different cases which should be handled:
+   *
+   *  1) 'key_item_field' may already refer one of the parent available within our
+   *      pushed scope.
+   *  2)  By using the equality set, we may find alternative parent references which
+   *      may make this a pushed join.
+   */
+
+  ///////////////////////////////////////////////////////////////////
+  // 0) Prepare for calculating parent candidates for this FIELD_ITEM
+  //
+  field_parents.clear_all();
+
+  ////////////////////////////////////////////////////////////////////
+  // 1) Add our existing parent reference to the set of parent candidates
+  //
+  uint referred_table_no= get_table_no(key_item_field);
+  if (m_join_scope.contain(referred_table_no))
+  {
+    field_parents.add(referred_table_no);
+  }
+
+  //////////////////////////////////////////////////////////////////
+  // 2) Use the equality set to possibly find more parent candidates
+  //    usable by substituting existing 'key_item_field'
+  //
+  AQP::Equal_set_iterator equal_iter(&m_plan, key_item_field);
+  const Item_field* substitute_field= equal_iter.next();
+  while (substitute_field != NULL)
+  {
+    if (substitute_field != key_item_field)
+    {
+      const uint substitute_table_no= get_table_no(substitute_field);
+      if (m_join_scope.contain(substitute_table_no))
       {
-        EXPLAIN_NO_PUSH("Can't push table '%s' as child of '%s', "
-                        "outer join with scan-descendant '%s' not implemented",
-                         table->get_table()->alias,
-                         join_root()->get_table()->alias,
-                         scan_descendant->get_table()->alias);
-        DBUG_RETURN(false);
+        DBUG_PRINT("info", 
+                   (" join_items[%d] %s.%s can be replaced with %s.%s",
+                    (int)(key_item - table->get_key_field(0)),
+                    get_referred_table_access_name(key_item_field),
+                    get_referred_field_name(key_item_field),
+                    get_referred_table_access_name(substitute_field),
+                    get_referred_field_name(substitute_field)));
+
+        field_parents.add(substitute_table_no);
       }
     }
-    else
+    substitute_field= equal_iter.next();
+  } // while(substitute_field != NULL)
+
+  if (!field_parents.is_clear_all())
+  {
+    DBUG_RETURN(true);
+  }
+
+  if (m_const_scope.contain(referred_table_no))
+  {
+    // This key item is const. and did not cause the set of possible parents
+    // to be recalculated. Reuse what we had before this key item.
+    DBUG_ASSERT(field_parents.is_clear_all());
+    /** 
+     * Scan queries cannot be pushed if the pushed query may refer column 
+     * values (paramValues) from rows stored in a join cache.  
+     */
+    if (!ndbcluster_is_lookup_operation(m_join_root->get_access_type()))
     {
-      // Verify that there are no ancestors with scan descendants. (possibly through lookup operations)
-      // (Which would cause an indirect bushy scan to be defined.)
-      // Terminate search at first scan ancester, as the presence if this scan guarante that 
-      // the tree is non scan-bush above.
-      //
-      const AQP::Table_access* scan_ancestor= NULL;
-      uint ancestor_no= parent_no;
-      while (ancestor_no != MAX_TABLES)
+      const st_table* const referred_tab = key_item_field->field->table;
+      uint access_no = tab_no;
+      do
       {
-        scan_ancestor= m_plan.get_table_access(ancestor_no);
-        if (m_tables[ancestor_no].m_last_scan_descendant < MAX_TABLES)
+        DBUG_ASSERT(access_no > 0);
+        access_no--;
+        if (m_plan.get_table_access(access_no)->uses_join_cache())
         {
-          EXPLAIN_NO_PUSH("Can't push table '%s' as child of '%s', "
-                          "implementation limitations due to bushy scan "
-                          "with '%s' indirect through '%s'",
-                           table->get_table()->alias,
-                           join_root()->get_table()->alias,
-                           m_plan.get_table_access(m_tables[ancestor_no].m_last_scan_descendant)->get_table()->alias,
-                           scan_ancestor->get_table()->alias);
+          EXPLAIN_NO_PUSH("Cannot push table '%s' as child of '%s', since "
+                          "it referes to column '%s.%s' which will be stored "
+                          "in a join buffer.",
+                          table->get_table()->alias, 
+                          m_join_root->get_table()->alias,
+                          get_referred_table_access_name(key_item_field),
+                          get_referred_field_name(key_item_field));
           DBUG_RETURN(false);
         }
+      } while (m_plan.get_table_access(access_no)->get_table() 
+               != referred_tab);
 
-        if (!ndbcluster_is_lookup_operation(scan_ancestor->get_access_type()))
-        {
-          break; // As adding this scanop was prev. allowed, above ancestor can't be scan bushy
-        }
-        ancestor_no= m_tables[ancestor_no].m_parent;
-      } // while
+    } // if (!ndbcluster_is_lookup_operation(root_type)
+    field_parents= ndb_table_access_map(m_join_root->get_access_no());
+    DBUG_RETURN(true);
+  }
+  else
+  {
+    EXPLAIN_NO_PUSH("Can't push table '%s' as child of '%s', "
+                    "column '%s.%s' is outside scope of pushable join",
+                     table->get_table()->alias, m_join_root->get_table()->alias,
+                     get_referred_table_access_name(key_item_field),
+                     get_referred_field_name(key_item_field));
+    DBUG_RETURN(false);
+  }
+} // ndb_pushed_builder_ctx::is_field_item_pushable()
 
-      // Outer joining scan-scan is not supported, see comments above.
-      if (scan_ancestor && 
-         table->get_join_type(scan_ancestor) == AQP::JT_OUTER_JOIN)
-      {
-        EXPLAIN_NO_PUSH("Can't push table '%s' as child of '%s', "
-                        "outer join with scan-ancestor '%s' not implemented",
-                         table->get_table()->alias,
-                         join_root()->get_table()->alias,
-                         scan_ancestor->get_table()->alias);
-        DBUG_RETURN(false);
+
+bool ndb_pushed_builder_ctx::is_const_item_pushable(
+                     const Item* key_item, 
+                     const KEY_PART_INFO* key_part)
+{
+  DBUG_ENTER("is_const_item_pushable()");
+  DBUG_ASSERT(key_item->const_item());
+
+  /** 
+   * Propagate Items constant value to Field containing the value of this 
+   * key_part:
+   */
+  Field* const field= key_part->field;
+  const int error= 
+    const_cast<Item*>(key_item)->save_in_field_no_warnings(field, true);
+  if (unlikely(error))
+  {
+    DBUG_PRINT("info", ("Failed to store constant Item into Field -> not"
+                        " pushable"));
+    DBUG_RETURN(false);
+  }
+  if (field->is_real_null())
+  {
+    DBUG_PRINT("info", ("NULL constValues in key -> not pushable"));
+    DBUG_RETURN(false);   // TODO, handle gracefull -> continue?
+  }
+  DBUG_RETURN(true);
+} // ndb_pushed_builder_ctx::is_const_item_pushable()
+
+
+int
+ndb_pushed_builder_ctx::optimize_query_plan()
+{
+  DBUG_ENTER("optimize_query_plan");
+  const uint root_no= m_join_root->get_access_no();
+
+  // Find an optimal order for joining the tables
+  for (uint tab_no= m_plan.get_access_count()-1;
+       tab_no > root_no;
+       tab_no--)
+  {
+    struct pushed_tables &table= m_tables[tab_no];
+    if (!m_join_scope.contain(tab_no))
+      continue;
+
+    /**
+     * Enforce the parent dependencies on the available
+     * 'common' and 'extended' parents set such that we
+     * don't skip any dependent parents from our ancestors
+     * when selecting the actuall 'm_parent' to be used.
+     */
+    if (!table.m_depend_parents.is_clear_all())
+    {
+      ndb_table_access_map const &dependency
+        = table.m_depend_parents;
+      DBUG_ASSERT(!dependency.contain(tab_no)); // Circular dependency!
+
+      uint depends_on_parent= dependency.last_table(tab_no-1);
+      ndb_table_access_map dependency_mask;
+      dependency_mask.set_prefix(depends_on_parent);
+
+      if (table.m_extend_parents.is_overlapping(dependency_mask))
+      {
+        table.m_extend_parents.subtract(dependency_mask);
+        table.m_extend_parents.add(depends_on_parent);
+      }
+      if (table.m_common_parents.is_overlapping(dependency_mask))
+      {
+        table.m_common_parents.clear_all();
       }
     }
-  } // scan operation
 
-     // get_referred_table_access ??
-  parent= m_plan.get_table_access(parent_no);
-  const ndb_table_access_map parent_map(parent);
-//DBUG_ASSERT(parents.contain(parent_map));
+    /**
+     * Select set to choose parent from, prefer a 'common'
+     * parent of available.
+     */
+    uint parent_no;
+    ndb_table_access_map const &parents=
+       table.m_common_parents.is_clear_all()
+       ? table.m_extend_parents
+       : table.m_common_parents;
+
+    DBUG_ASSERT(!parents.is_clear_all());
+    DBUG_ASSERT(!parents.contain(tab_no)); // No circular dependency!
+
+    /**
+     * In order to take advantage of the parallelism in the SPJ block; 
+     * Choose the first possible parent candidate. Will result in the
+     * most 'bushy' query plan (aka: star-join)
+     */
+    parent_no= parents.first_table(root_no);
+    DBUG_ASSERT(parent_no < tab_no);
+    table.m_parent= parent_no;
+
+    ndb_table_access_map dependency(table.m_depend_parents);
+    dependency.clear_bit(parent_no);
+    m_tables[parent_no].m_depend_parents.add(dependency);
+  }
+
+  /* Build the set of ancestors available through the selected 'm_parent' */
+  for (uint tab_no= root_no+1;
+       tab_no < m_plan.get_access_count();
+       tab_no++)
+  {
+    if (m_join_scope.contain(tab_no))
+    {
+      struct pushed_tables &table= m_tables[tab_no];
+      const uint parent_no= table.m_parent;
+      table.m_ancestors= m_tables[parent_no].m_ancestors;
+      table.m_ancestors.add(parent_no);
+      DBUG_ASSERT(table.m_ancestors.contain(table.m_depend_parents));
+    }
+  }
+  DBUG_RETURN(0);
+} // ndb_pushed_builder_ctx::optimize_query_plan
+
+
+void
+ndb_pushed_builder_ctx::collect_key_refs(
+                                  const AQP::Table_access* table,
+                                  const Item* key_refs[]) const
+{
+  DBUG_ENTER("collect_key_refs");
+
+  const uint tab_no= table->get_access_no();
+  const uint parent_no= m_tables[tab_no].m_parent;
+  const ndb_table_access_map& ancestors= m_tables[tab_no].m_ancestors;
+
+  DBUG_ASSERT(m_join_scope.contain(ancestors));
+  DBUG_ASSERT(ancestors.contain(parent_no));
 
   /**
    * If there are any key_fields with 'current_parents' different from
    * our selected 'parent', we have to find substitutes for
    * those key_fields within the equality set.
    **/
-  if (!(parent_map==current_parents))
+  for (uint key_part_no= 0; 
+       key_part_no < table->get_no_of_key_fields(); 
+       key_part_no++)
   {
-    ndb_table_access_map grandparent_map= m_tables[parent_no].m_ancestors;
-    DBUG_ASSERT (!grandparent_map.contain(parent_map));
+    const Item* const key_item= table->get_key_field(key_part_no);
+    key_refs[key_part_no]= key_item;
 
-    for (uint key_part_no= 0; 
-         key_part_no < table->get_no_of_key_fields(); 
-         key_part_no++)
+    DBUG_ASSERT(key_item->const_item() || key_item->type()==Item::FIELD_ITEM);
+
+    if (key_item->type() == Item::FIELD_ITEM)
     {
-      DBUG_ASSERT(join_items[key_part_no]->const_item() || 
-                  join_items[key_part_no]->type()==Item::FIELD_ITEM);
+      const Item_field* join_item= static_cast<const Item_field*>(key_item);
+      uint referred_table_no= get_table_no(join_item);
 
-      if (join_items[key_part_no]->type() == Item::FIELD_ITEM)
+      if (referred_table_no != parent_no)
       {
-        const Item_field* join_item 
-          = static_cast<const Item_field*>(join_items[key_part_no]);
-        
-        ndb_table_access_map used_table(join_item->used_tables());
-        if (!(used_table == parent_map))
+        AQP::Equal_set_iterator iter(&m_plan, join_item);
+        const Item_field* substitute_field= iter.next();
+        while (substitute_field != NULL)
         {
-          AQP::Equal_set_iterator iter(&m_plan, join_item);
-          const Item_field* substitute_field= iter.next();
-          while (substitute_field != NULL)
+          ///////////////////////////////////////////////////////////
+          // Prefer to replace join_item with ref. to selected parent.
+          //
+          const uint substitute_table_no= get_table_no(substitute_field);
+          if (substitute_table_no == parent_no)
+          {
+            DBUG_PRINT("info", 
+                       (" Replacing key_refs[%d] %s.%s with %s.%s (parent)",
+                        key_part_no,
+                        get_referred_table_access_name(join_item),
+                        get_referred_field_name(join_item),
+                        get_referred_table_access_name(substitute_field),
+                        get_referred_field_name(substitute_field)));
+
+            referred_table_no= substitute_table_no;
+            key_refs[key_part_no]= join_item= substitute_field;
+            break;
+          }
+          else if (ancestors.contain(substitute_table_no))
           {
-            ///////////////////////////////////////////////////////////
-            // Prefer to replace join_item with ref. to selected parent.
+            DBUG_ASSERT(substitute_table_no <= parent_no);
+
+            //////////////////////////////////////////////////////////////////////
+            // Second best is to replace join_item with closest grandparent ref.
+            // In this case we will continue to search for the common parent match:
+            // Updates key_refs[] if:
+            //   1): Replace incorrect refs of tables not being an 'ancestor'. 
+            //   2): Found a better substitute closer to selected parent 
             //
-            ndb_table_access_map substitute_table(substitute_field->used_tables());
-            if (substitute_table == parent_map)
+            if (!ancestors.contain(referred_table_no) ||   // 1
+                referred_table_no < substitute_table_no)   // 2)
             {
               DBUG_PRINT("info", 
-                         (" Replacing join_items[%d] %s.%s with %s.%s (parent)",
+                         (" Replacing key_refs[%d] %s.%s with %s.%s (grandparent)",
                           key_part_no,
-                          //join_item->field->table->alias,
                           get_referred_table_access_name(join_item),
                           get_referred_field_name(join_item),
                           get_referred_table_access_name(substitute_field),
                           get_referred_field_name(substitute_field)));
 
-              join_items[key_part_no]= join_item= substitute_field;
-              break;
+              referred_table_no= substitute_table_no;
+              key_refs[key_part_no]= join_item= substitute_field;
             }
+          }
+          substitute_field= iter.next();
+        } // while (substitute...
 
-            ////////////////////////////////////////////////////////////
-            // Second best is to replace join_item with grandparent ref.
-            // In this case we will continue to search for a common parent match
-            //
-            else if (!grandparent_map.contain(used_table) && grandparent_map.contain(substitute_table))
-            {
-              DBUG_PRINT("info", 
-                         (" Replacing join_items[%d] %s.%s with %s.%s (grandparent)",
-                          key_part_no,
-                          //join_item->field->table->alias,
-                          get_referred_table_access_name(join_item),
-                          get_referred_field_name(join_item),
-                          get_referred_table_access_name(substitute_field),
-                          get_referred_field_name(substitute_field)));
+        DBUG_ASSERT (referred_table_no == parent_no ||
+                     !m_join_scope.contain(referred_table_no)  || // Is a 'const' paramValue
+                     !m_tables[tab_no].m_common_parents.contain(parent_no));
+      }
+    } // Item::FIELD_ITEM
+  }
 
-              join_items[key_part_no]= join_item= substitute_field;
-            }
-            substitute_field= iter.next();
+  key_refs[table->get_no_of_key_fields()]= NULL;
+  DBUG_VOID_RETURN;
+} // ndb_pushed_builder_ctx::collect_key_refs()
+
+
+int
+ndb_pushed_builder_ctx::build_key(const AQP::Table_access* table,
+                                  const NdbQueryOperand *op_key[])
+{
+  DBUG_ENTER("build_key");
+  const uint tab_no= table->get_access_no();
+  DBUG_ASSERT(m_join_scope.contain(tab_no));
+
+  const KEY* const key= &table->get_table()->key_info[table->get_index_no()];
+  op_key[0]= NULL;
+
+  if (table == m_join_root)
+  {
+    if (ndbcluster_is_lookup_operation(table->get_access_type()))
+    {
+      for (uint i= 0; i < key->key_parts; i++)
+      {
+        op_key[i]= m_builder->paramValue();
+        if (unlikely(op_key[i] == NULL))
+        {
+          DBUG_RETURN(-1);
+        }
+      }
+      op_key[key->key_parts]= NULL;
+    }
+  }
+  else
+  {
+    const uint key_fields= table->get_no_of_key_fields();
+    DBUG_ASSERT(key_fields > 0 && key_fields <= key->key_parts);
+    uint map[ndb_pushed_join::MAX_LINKED_KEYS+1];
+
+    if (ndbcluster_is_lookup_operation(table->get_access_type()))
+    {
+      const ha_ndbcluster* handler=
+        static_cast<ha_ndbcluster*>(table->get_table()->file);
+      ndbcluster_build_key_map(handler->m_table, 
+                               handler->m_index[table->get_index_no()],
+                               key, map);
+    }
+    else
+    {
+      for (uint ix = 0; ix < key_fields; ix++)
+      {
+        map[ix]= ix;
+      }
+    }
+
+    const uint parent_no= m_tables[tab_no].m_parent;
+    DBUG_ASSERT(parent_no!=MAX_TABLES);
+
+    const Item* join_items[ndb_pushed_join::MAX_LINKED_KEYS+1];
+    collect_key_refs(table,join_items);
+
+    const KEY_PART_INFO *key_part= key->key_part;
+    for (uint i= 0; i < key_fields; i++, key_part++)
+    {
+      const Item* const item= join_items[i];
+      op_key[map[i]]= NULL;
+
+      DBUG_ASSERT(item->const_item() == item->const_during_execution());
+      if (item->const_item())
+      {
+        /** 
+         * Propagate Items constant value to Field containing the value of this 
+         * key_part:
+         */
+        Field* const field= key_part->field;
+        DBUG_ASSERT(!field->is_real_null());
+        const uchar* const ptr= (field->real_type() == MYSQL_TYPE_VARCHAR)
+                ? field->ptr + ((Field_varstring*)field)->length_bytes
+                : field->ptr;
+
+        op_key[map[i]]= m_builder->constValue(ptr, field->data_length());
+      }
+      else
+      {
+        DBUG_ASSERT(item->type() == Item::FIELD_ITEM);
+        const Item_field* const field_item= static_cast<const Item_field*>(item);
+        const uint referred_table_no= get_table_no(field_item);
+
+        if (m_join_scope.contain(referred_table_no))
+        {
+          // Locate the parent operation for this 'join_items[]'.
+          // May refer any of the preceeding parent tables
+          const NdbQueryOperationDef* const parent_op= m_tables[referred_table_no].m_op;
+          DBUG_ASSERT(parent_op != NULL);
+
+          // TODO use field_index ??
+          op_key[map[i]]= m_builder->linkedValue(parent_op, 
+                                               field_item->field_name);
+        }
+        else
+        {
+          DBUG_ASSERT(m_const_scope.contain(referred_table_no));
+          // Outside scope of join plan, Handle as parameter as its value
+          // will be known when we are ready to execute this query.
+          if (unlikely(m_fld_refs >= ndb_pushed_join::MAX_REFERRED_FIELDS))
+          {
+            DBUG_PRINT("info", ("Too many Field refs ( >= MAX_REFERRED_FIELDS) "
+                                "encountered"));
+            DBUG_RETURN(-1);  // TODO, handle gracefull -> continue?
           }
+          m_referred_fields[m_fld_refs++]= field_item->field;
+          op_key[map[i]]= m_builder->paramValue();
         }
-      } // Item::FIELD_ITEM
-    } // for all 'key_parts'
-  } // substitute
+      }
 
-  DBUG_RETURN(true);
-} // ndb_pushed_builder_ctx::is_pushable_as_child
+      if (unlikely(op_key[map[i]] == NULL))
+      {
+        DBUG_RETURN(-1);
+      }
+    }
+    op_key[key_fields]= NULL;
+  }
+  DBUG_RETURN(0);
+} // ndb_pushed_builder_ctx::build_key()
+
+
+int
+ndb_pushed_builder_ctx::build_query()
+{
+  DBUG_ENTER("build_query");
+
+  DBUG_PRINT("enter", ("Table %d as root is pushable", m_join_root->get_access_no()));
+  DBUG_EXECUTE("info", m_join_root->dbug_print(););
+
+  uint root_no= m_join_root->get_access_no();
+  DBUG_ASSERT(m_join_scope.contain(root_no));
+
+  if (m_builder == NULL)
+  {
+    m_builder= NdbQueryBuilder::create();
+    if (unlikely (m_builder==NULL))
+    {
+      DBUG_RETURN(HA_ERR_OUT_OF_MEM);
+    }
+  }
+
+  for (uint tab_no= root_no; tab_no<m_plan.get_access_count(); tab_no++)
+  {
+    if (!m_join_scope.contain(tab_no))
+      continue;
+
+    const AQP::Table_access* const table= m_plan.get_table_access(tab_no);
+    const AQP::enum_access_type access_type= table->get_access_type();
+    const ha_ndbcluster* handler=
+      static_cast<ha_ndbcluster*>(table->get_table()->file);
+
+    const NdbQueryOperand* op_key[ndb_pushed_join::MAX_KEY_PART+1];
+    if (table->get_index_no() >= 0)
+    {
+      const int error= build_key(table, op_key);
+      if (unlikely(error))
+        DBUG_RETURN(error);
+    }
+
+    NdbQueryOptions options;
+    if (handler->m_cond)
+    {
+      NdbInterpretedCode code(handler->m_table);
+      if (handler->m_cond->generate_scan_filter(&code, NULL) != 0)
+      {
+//      ERR_RETURN(code.getNdbError());  // FIXME
+      }
+      options.setInterpretedCode(code);
+    } 
+    if (table != m_join_root)
+    {
+      const uint parent_no= m_tables[tab_no].m_parent;
+      const AQP::Table_access* parent= m_plan.get_table_access(parent_no);
+
+      if (!m_tables[tab_no].m_common_parents.contain(parent_no))
+      {
+        DBUG_ASSERT(m_tables[parent_no].m_op != NULL);
+        options.setParent(m_tables[parent_no].m_op);
+      }
+      if (table->get_join_type(parent) == AQP::JT_INNER_JOIN)
+      {
+        options.setMatchType(NdbQueryOptions::MatchNonNull);
+      } 
+    }
+
+    const NdbQueryOperationDef* query_op= NULL;
+    if (ndbcluster_is_lookup_operation(access_type))
+    {
+      // Primary key access assumed
+      if (access_type == AQP::AT_PRIMARY_KEY || 
+          access_type == AQP::AT_MULTI_PRIMARY_KEY)
+      {
+        DBUG_PRINT("info", ("Operation is 'primary-key-lookup'"));
+        query_op= m_builder->readTuple(handler->m_table, op_key, &options);
+      }
+      else
+      {
+        DBUG_ASSERT(access_type == AQP::AT_UNIQUE_KEY);
+        DBUG_PRINT("info", ("Operation is 'unique-index-lookup'"));
+        const NdbDictionary::Index* const index 
+          = handler->m_index[table->get_index_no()].unique_index;
+        DBUG_ASSERT(index);
+        query_op= m_builder->readTuple(index, handler->m_table, op_key, &options);
+      }
+    } // ndbcluster_is_lookup_operation()
+
+    /**
+     *  AT_MULTI_MIXED may have 'ranges' which are pure single key lookups also.
+     *  In our current implementation these are converted into range access in the
+     *  pushed MRR implementation. However, the future plan is to build both 
+     *  RANGE and KEY pushable joins for these.
+     */
+    else if (access_type == AQP::AT_ORDERED_INDEX_SCAN  ||
+             access_type == AQP::AT_MULTI_MIXED)
+    {
+      DBUG_ASSERT(table->get_index_no() >= 0);
+      DBUG_ASSERT(handler->m_index[table->get_index_no()].index != NULL);
+
+      DBUG_PRINT("info", ("Operation is 'equal-range-lookup'"));
+      DBUG_PRINT("info", ("Creating scanIndex on index id:%d, name:%s",
+                          table->get_index_no(), 
+                          handler->m_index[table->get_index_no()]
+                           .index->getName()));
+
+      const NdbQueryIndexBound bounds(op_key);
+      query_op= m_builder->scanIndex(handler->m_index[table->get_index_no()].index,
+                                   handler->m_table, &bounds, &options);
+    }
+    else if (access_type == AQP::AT_TABLE_SCAN) 
+    {
+      DBUG_PRINT("info", ("Operation is 'table scan'"));
+      query_op= m_builder->scanTable(handler->m_table, &options);
+    }
+    else
+    {
+      DBUG_ASSERT(false);
+    }
+
+    if (unlikely(!query_op))
+      DBUG_RETURN(-1);
+
+    m_tables[tab_no].m_op= query_op;
+  } // for (join_cnt= m_join_root->get_access_no(); join_cnt<plan.get_access_count(); join_cnt++)
+
+  DBUG_RETURN(0);
+} // ndb_pushed_builder_ctx::build_query()
 
 
 /**
@@ -919,6 +1325,6 @@ ndbcluster_build_key_map(const NDBTAB* t
       key_pos++;
     }
   }
-} // build_key_map
+} // ndbcluster_build_key_map
 
 #endif // WITH_NDBCLUSTER_STORAGE_ENGINE

=== modified file 'sql/ha_ndbcluster_push.h'
--- a/sql/ha_ndbcluster_push.h	2011-03-31 07:44:04 +0000
+++ b/sql/ha_ndbcluster_push.h	2011-04-27 07:42:18 +0000
@@ -19,59 +19,24 @@
 #pragma interface                       /* gcc class implementation */
 #endif
 
-#include <abstract_query_plan.h>
+#include "sql_bitmap.h"
 
-#define EXPLAIN_NO_PUSH(msgfmt, ...)                              \
-do                                                                \
-{                                                                 \
-  if (unlikely(current_thd->lex->describe & DESCRIBE_EXTENDED))   \
-  {                                                               \
-    ndbcluster_explain_no_push ((msgfmt), __VA_ARGS__);           \
-  }                                                               \
-}                                                                 \
-while(0)
-
-int ndbcluster_make_pushed_join(handlerton *hton, THD* thd,
-				AQP::Join_plan* plan);
-
-inline bool ndbcluster_is_lookup_operation(AQP::enum_access_type accessType)
-{
-  return accessType == AQP::AT_PRIMARY_KEY ||
-    accessType == AQP::AT_MULTI_PRIMARY_KEY ||
-    accessType == AQP::AT_UNIQUE_KEY;
-}
-
-void ndbcluster_explain_no_push(const char* msgfmt, ...);
+class NdbQueryBuilder;
+class NdbQueryOperand;
+class NdbQueryOperationDef;
+class NdbError;
+class ndb_pushed_builder_ctx;
+
+namespace AQP{
+  class Join_plan;
+  class Table_access;
+};
 
 void ndbcluster_build_key_map(const NdbDictionary::Table* table, 
 			      const NDB_INDEX_DATA& index,
 			      const KEY *key_def,
 			      uint ix_map[]);
 
-/**
- * This is a list of NdbQueryDef objects that have been created within a 
- * transaction. This list is kept to make sure that they are all released 
- * when the transaction ends.
- * An NdbQueryDef object is required to live longer than any NdbQuery object
- * instantiated from it. Since NdbQueryObjects may be kept until the 
- * transaction ends, this list is necessary.
- */
-class ndb_query_def_list
-{
-public:
-  ndb_query_def_list(const NdbQueryDef* def, const ndb_query_def_list* next):
-    m_def(def), m_next(next){}
-
-  const NdbQueryDef* get_def() const
-  { return m_def; }
-
-  const ndb_query_def_list* get_next() const
-  { return m_next; }
-
-private:
-  const NdbQueryDef* const m_def;
-  const ndb_query_def_list* const m_next;
-};
 
 /** 
  * This type is used in conjunction with AQP::Join_plan and represents a set 
@@ -87,152 +52,33 @@ public:
   explicit ndb_table_access_map()
    : table_bitmap(0)
   {}
-
-  explicit ndb_table_access_map(table_map bitmap)
+  explicit ndb_table_access_map(uint table_no)
    : table_bitmap(0)
-//{ set_map(table); } .. Bitmap<>::set_map() is expected to be available in the near future
-  {
-    for (uint i= 0; bitmap!=0; i++, bitmap>>=1)
-    {
-      if (bitmap & 1)
-        set_bit(i);
-    }
+  { set_bit(table_no);
   }
 
-  explicit ndb_table_access_map(const AQP::Table_access* const table)
-   : table_bitmap(0)
-  { set_bit(table->get_table()->tablenr); }
-
   void add(const ndb_table_access_map& table_map)
   { // Require const_cast as signature of class Bitmap::merge is not const correct
     merge(const_cast<ndb_table_access_map&>(table_map));
   }
-  void add(const AQP::Table_access* const table)
+  void add(uint table_no)
   {
-    ndb_table_access_map table_map(table);
-    add(table_map);
+    set_bit(table_no);
   }
 
   bool contain(const ndb_table_access_map& table_map) const
   {
     return table_map.is_subset(*this);
   }
-  bool contain_table(const AQP::Table_access* const table) const
+  bool contain(uint table_no) const
   {
-    ndb_table_access_map table_map(table);
-    return contain(table_map);
+    return is_set(table_no);
   }
-}; // class ndb_table_access_map
-
-
-/**
- * Contains the context and helper methods used during ::make_pushed_join().
- *
- * Interacts with the AQP which provides interface to the query prepared by
- * the mysqld optimizer.
- *
- * Execution plans built for pushed joins are stored inside this builder context.
- */
-class ndb_pushed_builder_ctx
-{
-public:
-
-  ndb_pushed_builder_ctx(AQP::Join_plan& plan)
-   : m_plan(plan), m_join_root(), m_join_scope(), m_const_scope()
-  { 
-    if (plan.get_access_count() > 1)
-      init_pushability();
-  }
-
-  /** Define root of pushable tree.*/
-  void set_root(const AQP::Table_access* join_root);
-
-  const AQP::Join_plan& plan() const
-  { return m_plan; }
-
-  const AQP::Table_access* join_root() const
-  { return m_join_root; }
-
-  const ndb_table_access_map& join_scope() const
-  { return m_join_scope; }
-
-  const ndb_table_access_map& const_scope() const
-  { return m_const_scope; }
-
-  const class NdbQueryOperationDef* 
-    get_query_operation(const AQP::Table_access* table) const
-  {
-    DBUG_ASSERT(m_join_scope.contain_table(table));
-    return m_tables[table->get_access_no()].op;
-  }
-
-  const AQP::Table_access* get_referred_table_access(
-                  const ndb_table_access_map& used_tables) const;
-
-  bool is_pushable_as_parent(
-                  const AQP::Table_access* table);
-
-  bool is_pushable_as_child(
-                  const AQP::Table_access* table,
-                  const Item* join_items[],
-                  const AQP::Table_access*& parent);
-
-  void add_pushed(const AQP::Table_access* table,
-                  const AQP::Table_access* parent,
-                  const NdbQueryOperationDef* query_op);
-
-  // Check if 'table' is child of some of the specified 'parents'
-  bool is_child_of(const AQP::Table_access* table,
-                   const ndb_table_access_map& parents) const
-  {
-    DBUG_ASSERT(m_join_scope.contain_table(table));
-    DBUG_ASSERT(parents.is_subset(m_join_scope));
-    return parents.is_overlapping(m_tables[table->get_access_no()].m_ancestors);
-  }
-
-  enum pushability
-  {
-    PUSHABLE_AS_PARENT= 0x01,
-    PUSHABLE_AS_CHILD= 0x02
-  } enum_pushability;
-
-private:
-  void init_pushability();
-
-  bool find_field_parents(const AQP::Table_access* table,
-                          const Item* key_item, 
-                          const KEY_PART_INFO* key_part_info,
-                          ndb_table_access_map& parents);
-private:
-  const AQP::Join_plan& m_plan;
-  const AQP::Table_access* m_join_root;
-
-  // Scope of tables covered by this pushed join
-  ndb_table_access_map m_join_scope;
-
-  // Scope of tables evaluated prior to 'm_join_root'
-  // These are effectively const or params wrt. the pushed join
-  ndb_table_access_map m_const_scope;
-
-  struct pushed_tables
-  {
-    pushed_tables() : 
-      m_maybe_pushable(0),
-      m_parent(MAX_TABLES), 
-      m_ancestors(), 
-      m_last_scan_descendant(MAX_TABLES), 
-      op(NULL) 
-    {}
-
-    int  m_maybe_pushable;
-    uint m_parent;
-    ndb_table_access_map m_ancestors;
-    uint m_last_scan_descendant;
 
-    const NdbQueryOperationDef* op;
-  } m_tables[MAX_TABLES];
+  uint first_table(uint start= 0) const;
+  uint last_table(uint start= MAX_TABLES) const;
 
-}; // class ndb_pushed_builder_ctx
+}; // class ndb_table_access_map
 
 
 /** This class represents a prepared pushed (N-way) join operation.
@@ -245,10 +91,8 @@ private:
 class ndb_pushed_join
 {
 public:
-  explicit ndb_pushed_join(const AQP::Join_plan& plan, 
-			  const ndb_table_access_map& pushed_operations,
-			  uint field_refs, Field* const fields[],
-			  const NdbQueryDef* query_def);
+  explicit ndb_pushed_join(const ndb_pushed_builder_ctx& builder_ctx,
+                           const NdbQueryDef* query_def);
   
   /** Get the number of pushed table access operations.*/
   uint get_operation_count() const
@@ -325,3 +169,154 @@ private:
   Field* m_referred_fields[MAX_REFERRED_FIELDS];
 }; // class ndb_pushed_join
 
+
+
+/**
+ * Contains the context and helper methods used during ::make_pushed_join().
+ *
+ * Interacts with the AQP which provides interface to the query prepared by
+ * the mysqld optimizer.
+ *
+ * Execution plans built for pushed joins are stored inside this builder context.
+ */
+class ndb_pushed_builder_ctx
+{
+  friend ndb_pushed_join::ndb_pushed_join(
+                           const ndb_pushed_builder_ctx& builder_ctx,
+                           const NdbQueryDef* query_def);
+
+public:
+  ndb_pushed_builder_ctx(const AQP::Join_plan& plan);
+  ~ndb_pushed_builder_ctx();
+
+  /**
+   * Build the pushed query identified with 'is_pushable_with_root()'.
+   * Returns:
+   *   = 0: A NdbQueryDef has successfully been prepared for execution.
+   *   > 0: Returned value is the error code.
+   *   < 0: There is a pending NdbError to be retrieved with getNdbError()
+   */
+  int make_pushed_join(const AQP::Table_access* join_root,
+                       const ndb_pushed_join* &pushed_join);
+
+  const NdbError& getNdbError() const;
+
+private:
+  /**
+   * Collect all tables which may be pushed together with 'root'.
+   * Returns 'true' if anything is pushable.
+   */
+  bool is_pushable_with_root(
+                  const AQP::Table_access* root);
+
+  bool is_pushable_as_child(
+                  const AQP::Table_access* table);
+
+  bool is_const_item_pushable(
+                  const Item* key_item, 
+                  const KEY_PART_INFO* key_part);
+
+  bool is_field_item_pushable(
+                  const AQP::Table_access* table,
+                  const Item* key_item, 
+                  const KEY_PART_INFO* key_part,
+                  ndb_table_access_map& parents);
+
+  int optimize_query_plan();
+
+  int build_query();
+
+  void collect_key_refs(
+                  const AQP::Table_access* table,
+                  const Item* key_refs[]) const;
+
+  int build_key(const AQP::Table_access* table,
+                const NdbQueryOperand* op_key[]);
+
+  uint get_table_no(const Item* key_item) const;
+
+private:
+  const AQP::Join_plan& m_plan;
+  const AQP::Table_access* m_join_root;
+
+  // Scope of tables covered by this pushed join
+  ndb_table_access_map m_join_scope;
+
+  // Scope of tables evaluated prior to 'm_join_root'
+  // These are effectively const or params wrt. the pushed join
+  ndb_table_access_map m_const_scope;
+
+  // Set of tables required to have strict sequential dependency
+  ndb_table_access_map m_forced_sequence;
+
+  uint m_fld_refs;
+  Field* m_referred_fields[ndb_pushed_join::MAX_REFERRED_FIELDS];
+
+  // Handle to the NdbQuery factory.
+  // Possibly reused if multiple NdbQuery's are pushed.
+  NdbQueryBuilder* m_builder;
+
+  enum pushability
+  {
+    PUSHABLE_AS_PARENT= 0x01,
+    PUSHABLE_AS_CHILD= 0x02
+  } enum_pushability;
+
+  struct pushed_tables
+  {
+    pushed_tables() : 
+      m_maybe_pushable(0),
+      m_common_parents(), 
+      m_extend_parents(), 
+      m_depend_parents(), 
+      m_parent(MAX_TABLES), 
+      m_ancestors(), 
+      m_op(NULL) 
+    {}
+
+    int m_maybe_pushable;  // OR'ed bits from 'enum_pushability'
+
+    /**
+     * We maintain two sets of parent candidates for each table: 
+     *  - 'common' are those parents for which ::collect_key_refs()
+     *     will find key_refs[] (possibly through the EQ-sets) such that all
+     *     linkedValues() refer fields from the same parent.
+     *  - 'extendeded' are those parents refered from some of the 
+     *     key_refs[], and having the rest of the key_refs[] available as
+     *     'grandparent refs'.
+     */
+    ndb_table_access_map m_common_parents;
+    ndb_table_access_map m_extend_parents;
+
+    /**
+     * (sub)Set of a parents which *must* be available as ancestors
+     * due to dependencies on these parents tables.
+     */
+    ndb_table_access_map m_depend_parents;
+
+    /**
+     * The actual parent is choosen among (m_common_parents | m_extend_parents)
+     * by ::optimize_query_plan()
+     */
+    uint m_parent;
+
+    /**
+     * All ancestors available throught the 'm_parent' chain
+     */
+    ndb_table_access_map m_ancestors;
+
+    const NdbQueryOperationDef* m_op;
+  } m_tables[MAX_TABLES];
+
+  /**
+   * There are two different table enumerations used:
+   */
+  struct table_remap
+  {
+    Uint16 to_external;  // m_remap[] is indexed with internal table_no
+    Uint16 to_internal;  // m_remap[] is indexed with external tablenr
+  } m_remap[MAX_TABLES];
+
+}; // class ndb_pushed_builder_ctx
+
+


Attachment: [text/bzr-bundle] bzr/ole.john.aske@oracle.com-20110427074218-a9xc8s4lio516ayz.bundle
Thread
bzr commit into mysql-5.1-telco-7.0-spj-scan-vs-scan branch(ole.john.aske:3480) Ole John Aske27 Apr