List:Commits« Previous MessageNext Message »
From:Jan Wedvik Date:December 7 2010 1:58pm
Subject:bzr commit into mysql-5.1-telco-7.0-spj-scan-vs-scan branch
(jan.wedvik:3390)
View as plain text  
#At file:///net/atum17/export/home2/tmp/jw159207/mysql/repo/push-scan-scan/ based on revid:ole.john.aske@stripped

 3390 Jan Wedvik	2010-12-07
      This commit fixes an error in Table_access::get_join_type(). This method
      checks if the relationship between a Table_access and one of its 
      predecessors in the join plan is an inner join or a (left) outer join.
      
      For some queries, this method would make an assert failure, because it was
      unable to decide the type of join. This error has now been fixed, and more
      regression test cases have also been added.

    modified:
      mysql-test/suite/ndb/r/ndb_join_pushdown.result
      mysql-test/suite/ndb/t/ndb_join_pushdown.test
      sql/abstract_query_plan.cc
=== modified file 'mysql-test/suite/ndb/r/ndb_join_pushdown.result'
--- a/mysql-test/suite/ndb/r/ndb_join_pushdown.result	2010-11-17 11:59:32 +0000
+++ b/mysql-test/suite/ndb/r/ndb_join_pushdown.result	2010-12-07 13:58:30 +0000
@@ -4598,6 +4598,101 @@ select * from t1 as q1, t1 as q2 where q
 a	b	c	d	a	b	c	d
 aaa	1	aaa	1	aaa	1	aaa	1
 drop table t1;
+CREATE TABLE t1 (
+a int NOT NULL,
+b int NOT NULL,
+c int NOT NULL,
+d int,
+PRIMARY KEY (`a`,`b`),
+unique key(c)
+) ENGINE=ndbcluster;
+insert into t1 values
+(1,1,1,1), 
+(1,2,2,1), 
+(1,3,3,1), 
+(1,4,4,1), 
+(1,5,5,2), 
+(1,6,6,2), 
+(1,7,7,2), 
+(1,8,8,2);
+explain extended select count(*) from t1 as x1 
+join (t1 as x2 
+left join (t1 as x3 
+cross join t1 as x4) 
+on x2.d=x3.a) 
+on x2.c is null or x1.a=x4.d;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	x2	ALL	NULL	NULL	NULL	NULL	8	100.00	
+1	SIMPLE	x3	ref	PRIMARY	PRIMARY	4	test.x2.d	1	100.00	
+1	SIMPLE	x4	ALL	NULL	NULL	NULL	NULL	8	100.00	Parent of 2 pushed join@1
+1	SIMPLE	x1	ref	PRIMARY	PRIMARY	4	test.x4.d	1	100.00	Child of pushed join@1
+Warnings:
+Note	1644	Can't push table 'x3' as child of 'x2', outer join with scan-ancestor 'x2' not implemented
+Note	1644	Can't push table 'x4' as child, 'type' must be a 'ref' access
+Note	1644	Can't push table 'x1' as child of 'x2', column 'x4.d' is outside scope of pushable join
+Note	1644	Can't push table 'x1' as child of 'x3', column 'x4.d' is outside scope of pushable join
+Note	1003	select count(0) AS `count(*)` from `test`.`t1` `x1` join `test`.`t1` `x2` left join (`test`.`t1` `x3` join `test`.`t1` `x4`) on((`test`.`x3`.`a` = `test`.`x2`.`d`)) where (`test`.`x1`.`a` = `test`.`x4`.`d`)
+select count(*) from t1 as x1 
+join (t1 as x2 
+left join (t1 as x3 
+cross join t1 as x4) 
+on x2.d=x3.a) 
+on x2.c is null or x1.a=x4.d;
+count(*)
+1024
+explain extended select count(*) from t1 as x1 
+left join (t1 as x2 
+cross join t1 as x3) 
+on x1.d=x2.a;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	x1	ALL	NULL	NULL	NULL	NULL	8	100.00	
+1	SIMPLE	x2	ref	PRIMARY	PRIMARY	4	test.x1.d	1	100.00	
+1	SIMPLE	x3	ALL	NULL	NULL	NULL	NULL	8	100.00	
+Warnings:
+Note	1644	Can't push table 'x2' as child of 'x1', outer join with scan-ancestor 'x1' not implemented
+Note	1644	Can't push table 'x3' as child, 'type' must be a 'ref' access
+Note	1003	select count(0) AS `count(*)` from `test`.`t1` `x1` left join (`test`.`t1` `x2` join `test`.`t1` `x3`) on((`test`.`x1`.`d` = `test`.`x2`.`a`)) where 1
+select count(*) from t1 as x1 
+left join (t1 as x2 
+cross join t1 as x3) 
+on x1.d=x2.a;
+count(*)
+260
+explain extended select count(*) from t1 as x0 
+left join (t1 as x1 
+join (t1 as x2 
+left join (t1 as x3 
+join t1 as x4 on x3.d=x4.a) 
+on x2.d=x3.a) 
+on x2.c is null or x1.a=x4.d) 
+on x0.d=x1.a;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	x0	ALL	NULL	NULL	NULL	NULL	8	100.00	
+1	SIMPLE	x1	ref	PRIMARY	PRIMARY	4	test.x0.d	1	100.00	
+1	SIMPLE	x2	ALL	c	NULL	NULL	NULL	8	100.00	
+1	SIMPLE	x3	ref	PRIMARY	PRIMARY	4	test.x2.d	1	100.00	Parent of 2 pushed join@1
+1	SIMPLE	x4	ref	PRIMARY	PRIMARY	4	test.x3.d	1	100.00	Child of pushed join@1
+Warnings:
+Note	1644	Can't push table 'x1' as child of 'x0', outer join with scan-ancestor 'x0' not implemented
+Note	1644	Can't push table 'x2' as child, 'type' must be a 'ref' access
+Note	1644	Can't push table 'x3' as child of 'x0', column 'x2.d' is outside scope of pushable join
+Note	1644	Can't push table 'x4' as child of 'x0', column 'x3.d' is outside scope of pushable join
+Note	1644	Can't push table 'x3' as child of 'x1', column 'x2.d' is outside scope of pushable join
+Note	1644	Can't push table 'x4' as child of 'x1', column 'x3.d' is outside scope of pushable join
+Note	1644	Can't push table 'x3' as child of 'x2', outer join with scan-ancestor 'x2' not implemented
+Note	1644	Can't push table 'x4' as child of 'x2', column 'x3.d' is outside scope of pushable join
+Note	1003	select count(0) AS `count(*)` from `test`.`t1` `x0` left join (`test`.`t1` `x1` join `test`.`t1` `x2` left join (`test`.`t1` `x3` join `test`.`t1` `x4`) on(((`test`.`x2`.`d` = `test`.`x3`.`a`) and (`test`.`x3`.`d` = `test`.`x4`.`a`)))) on(((`test`.`x0`.`d` = `test`.`x1`.`a`) and (isnull(`test`.`x2`.`c`) or (`test`.`x1`.`a` = `test`.`x4`.`d`)))) where 1
+select count(*) from t1 as x0 
+left join (t1 as x1 
+join (t1 as x2 
+left join (t1 as x3 
+join t1 as x4 on x3.d=x4.a) 
+on x2.d=x3.a) 
+on x2.c is null or x1.a=x4.d) 
+on x0.d=x1.a;
+count(*)
+2052
+drop table t1;
 create temporary table spj_counts_at_end
 select counter_name, sum(val) as val 
 from ndbinfo.counters 
@@ -4613,13 +4708,13 @@ and spj_counts_at_end.counter_name <> 'L
        and spj_counts_at_end.counter_name <> 'SCAN_BATCHES_RETURNED';
 counter_name	spj_counts_at_end.val - spj_counts_at_startup.val
 CONST_PRUNED_RANGE_SCANS_RECEIVED	6
-LOCAL_TABLE_SCANS_SENT	196
+LOCAL_TABLE_SCANS_SENT	260
 PRUNED_RANGE_SCANS_RECEIVED	17
-RANGE_SCANS_RECEIVED	210
+RANGE_SCANS_RECEIVED	722
 READS_NOT_FOUND	405
 READS_RECEIVED	61
-SCAN_ROWS_RETURNED	63869
-TABLE_SCANS_RECEIVED	196
+SCAN_ROWS_RETURNED	70269
+TABLE_SCANS_RECEIVED	260
 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 
 where spj_counts_at_end.counter_name = spj_counts_at_startup.counter_name
@@ -4630,15 +4725,15 @@ LOCAL+REMOTE READS_SENT
 drop table spj_counts_at_startup;
 drop table spj_counts_at_end;
 scan_count
-2035
+2425
 pruned_scan_count
 8
 sorted_scan_count
 9
 pushed_queries_defined
-348
+352
 pushed_queries_dropped
 11
 pushed_queries_executed
-268
+556
 set ndb_join_pushdown = @save_ndb_join_pushdown;

=== modified file 'mysql-test/suite/ndb/t/ndb_join_pushdown.test'
--- a/mysql-test/suite/ndb/t/ndb_join_pushdown.test	2010-11-16 13:26:19 +0000
+++ b/mysql-test/suite/ndb/t/ndb_join_pushdown.test	2010-12-07 13:58:30 +0000
@@ -2983,6 +2983,70 @@ select * from t1 as q1, t1 as q2 where q
 select * from t1 as q1, t1 as q2 where q1.a = 'aaa' and q1.c=q2.a;
 drop table t1;
 
+#######################################
+# Some tests for nested left joins.
+
+CREATE TABLE t1 (
+  a int NOT NULL,
+  b int NOT NULL,
+  c int NOT NULL,
+  d int,
+  PRIMARY KEY (`a`,`b`),
+  unique key(c)
+) ENGINE=ndbcluster;
+
+insert into t1 values
+(1,1,1,1), 
+(1,2,2,1), 
+(1,3,3,1), 
+(1,4,4,1), 
+(1,5,5,2), 
+(1,6,6,2), 
+(1,7,7,2), 
+(1,8,8,2);
+
+explain extended select count(*) from t1 as x1 
+   join (t1 as x2 
+      left join (t1 as x3 
+         cross join t1 as x4) 
+      on x2.d=x3.a) 
+   on x2.c is null or x1.a=x4.d;
+select count(*) from t1 as x1 
+   join (t1 as x2 
+      left join (t1 as x3 
+         cross join t1 as x4) 
+      on x2.d=x3.a) 
+   on x2.c is null or x1.a=x4.d;
+
+explain extended select count(*) from t1 as x1 
+   left join (t1 as x2 
+      cross join t1 as x3) 
+   on x1.d=x2.a;
+select count(*) from t1 as x1 
+   left join (t1 as x2 
+      cross join t1 as x3) 
+   on x1.d=x2.a;
+
+
+explain extended select count(*) from t1 as x0 
+   left join (t1 as x1 
+      join (t1 as x2 
+         left join (t1 as x3 
+            join t1 as x4 on x3.d=x4.a) 
+         on x2.d=x3.a) 
+      on x2.c is null or x1.a=x4.d) 
+   on x0.d=x1.a;
+select count(*) from t1 as x0 
+   left join (t1 as x1 
+      join (t1 as x2 
+         left join (t1 as x3 
+            join t1 as x4 on x3.d=x4.a) 
+         on x2.d=x3.a) 
+      on x2.c is null or x1.a=x4.d) 
+   on x0.d=x1.a;
+
+drop table t1;
+
 ########################################
 # Verify DBSPJ counters for entire test:
 

=== modified file 'sql/abstract_query_plan.cc'
--- a/sql/abstract_query_plan.cc	2010-11-17 11:59:32 +0000
+++ b/sql/abstract_query_plan.cc	2010-12-07 13:58:30 +0000
@@ -145,37 +145,78 @@ namespace AQP
   }
 
   /**
-   Determine join type between this table and its parent table.
+    Determine join type between this table access and some other table
+    access that preceeds it in the join plan..
   */
-  enum_join_type Table_access::get_join_type(const Table_access* parent) const
+  enum_join_type 
+  Table_access::get_join_type(const Table_access* predecessor) const
   {
-    const TABLE_LIST *this_table=   this->get_join_tab()->table->pos_in_table_list;
-    const TABLE_LIST *parent_table= parent->get_join_tab()->table->pos_in_table_list;
+    DBUG_ENTER("get_join_type");
+    DBUG_ASSERT(get_access_no() > predecessor->get_access_no());
 
-    /**
-     Itterate the join-nest until we reach the same join level as the parent.
-     If we find 'outer_join' inbetween, the join of this table wrt. parent
-     is reported as JT_OUTER_JOIN.
-    */
-    const TABLE_LIST *join_item = this_table;
-    for (join_item = this_table; join_item!=NULL; join_item = join_item->embedding)
+    if (get_join_tab()->table->pos_in_table_list->outer_join != 0)
+    {
+      /*
+        This cover unnested outer joins such as 
+        'select * from t1 left join t2 on t1.attr=t1.pk'.
+       */
+      DBUG_PRINT("info", ("JT_OUTER_JOIN between %s and %s",
+                          predecessor->get_join_tab()->table->alias,
+                          get_join_tab()->table->alias));
+      DBUG_RETURN(JT_OUTER_JOIN);
+    }
+
+    const TABLE_LIST* const child_embedding= 
+      get_join_tab()->table->pos_in_table_list->embedding;;
+
+    if (child_embedding == NULL)
+    {
+      // 'this' is not on the inner side of any left join.
+      DBUG_PRINT("info", ("JT_INNER_JOIN between %s and %s",
+                          predecessor->get_join_tab()->table->alias,
+                          get_join_tab()->table->alias));
+      DBUG_RETURN(JT_INNER_JOIN);
+    }
+
+    DBUG_ASSERT(child_embedding->outer_join != 0);
+
+    const TABLE_LIST *predecessor_embedding= 
+      predecessor->get_join_tab()->table->pos_in_table_list->embedding;
+
+    /*
+      This covers the nested join case, i.e:
+      <table reference> LEFT JOIN (<joined table>).
+      
+      TABLE_LIST objects form a tree where TABLE_LIST::emebedding points to
+      the parent object. Now if child_embedding is non null and not an 
+      ancestor of predecessor_embedding in the embedding tree, then 'this'
+      must be on the inner side of some left join where 'predecessor' is on 
+      the outer side.
+     */
+    while (true)
     {
-      if (join_item->outer_join)
+      if (predecessor_embedding == child_embedding)
       {
-        DBUG_PRINT("info", ("JT_OUTER_JOIN"));
-        return JT_OUTER_JOIN;
+        DBUG_PRINT("info", ("JT_INNER_JOIN between %s and %s",
+                            predecessor->get_join_tab()->table->alias,
+                            get_join_tab()->table->alias));
+        DBUG_RETURN(JT_INNER_JOIN);
       }
-      else if (join_item->embedding == parent_table->embedding)
+      else if (predecessor_embedding == NULL)
       {
-        DBUG_PRINT("info", ("at parent -> JT_INNER_JOIN"));
-        return JT_INNER_JOIN;
+        /*
+           We reached the root of the tree without finding child_embedding,
+           so it must be in another branch and hence on the inner side of some
+           left join where 'predecessor' is on the outer side.
+         */
+        DBUG_PRINT("info", ("JT_OUTER_JOIN between %s and %s",
+                            predecessor->get_join_tab()->table->alias,
+                            get_join_tab()->table->alias));
+        DBUG_RETURN(JT_OUTER_JOIN);
       }
+      // Iterate through ancestors of predecessor_embedding.
+      predecessor_embedding = predecessor_embedding->embedding;
     }
-
-    /* Unable to determine jointype, default to OUTER which is the 'most covering' */
-    DBUG_PRINT("info", ("fall through -> JT_OUTER_JOIN"));
-    DBUG_ASSERT(false);
-    return JT_OUTER_JOIN;
   }
 
   /**


Attachment: [text/bzr-bundle] bzr/jan.wedvik@sun.com-20101207135830-1p2yw7la6g8zcfql.bundle
Thread
bzr commit into mysql-5.1-telco-7.0-spj-scan-vs-scan branch(jan.wedvik:3390) Jan Wedvik7 Dec