From: Frazer Clement
Date: September 30 2010 2:50pm
Subject: Re: bzr commit into mysql-5.1-telco-7.0-spj-scan-vs-scan branch (ole.john.aske:3304)
List-Archive: http://lists.mysql.com/commits/119561
Message-Id: <4CA4A39A.40400@oracle.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Must confess to difficulty visualising a scan child being "'indirectly' 
outer joined with an ascending scan parent if there exists outer joined 
lookup operations between the scan child and its closest scan ancestor"


Ole John Aske wrote:
> #At file:///net/fimafeng09/export/home/tmp/oleja/mysql/mysql-5.1-telco-7.0-spj-scan-scan/ based on revid:jan.wedvik@stripped
> 
>  3304 Ole John Aske	2010-09-30
>       sps-svs: Addition to previous 'sledgehammer fix' where an outer joined scan child is *not* allowed to be pushed:
>       
>       The scan child may be 'indirectly' outer joined with an ascending scan parent if there exists outer joined
>       lookup operations between the scan child and its closest scan ancestor.
> 
>     modified:
>       mysql-test/suite/ndb/r/ndb_join_pushdown.result
>       mysql-test/suite/ndb/t/ndb_join_pushdown.test
>       sql/ha_ndbcluster.cc
> === modified file 'mysql-test/suite/ndb/r/ndb_join_pushdown.result'
> --- a/mysql-test/suite/ndb/r/ndb_join_pushdown.result	2010-09-29 11:53:33 +0000
> +++ b/mysql-test/suite/ndb/r/ndb_join_pushdown.result	2010-09-30 14:20:12 +0000
> @@ -3524,6 +3524,37 @@ pk	u	a	b	pk	u	a	b	pk	u	a	b
>  7	7	10	10	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL
>  8	8	10	10	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL
>  9	9	10	10	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL
> +explain select straight_join * from t1 as x1 
> +inner join t1 as x2 on x2.b = x1.a;
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	SIMPLE	x1	ALL	NULL	NULL	NULL	NULL	13	Parent of 2 pushed join@1
> +1	SIMPLE	x2	ref	ix1	ix1	5	test.x1.a	1	Child of pushed join@1; Using where
> +explain select straight_join * from t1 as x1 
> +left join t1 as x2 on x2.b = x1.a;
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	SIMPLE	x1	ALL	NULL	NULL	NULL	NULL	13	
> +1	SIMPLE	x2	ref	ix1	ix1	5	test.x1.a	1	
> +explain select straight_join * from t1 as x1 
> +right join t1 as x2 on x2.b = x1.a;
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	SIMPLE	x2	ALL	NULL	NULL	NULL	NULL	13	
> +1	SIMPLE	x1	ALL	NULL	NULL	NULL	NULL	13	
> +explain select straight_join * from 
> +t1 as x1 inner join
> +(t1 as x2 inner join t1 as x3 on x3.b = x2.a)
> +on x2.pk = x1.a;
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	SIMPLE	x1	ALL	NULL	NULL	NULL	NULL	13	Parent of 3 pushed join@1
> +1	SIMPLE	x2	eq_ref	PRIMARY	PRIMARY	4	test.x1.a	1	Child of pushed join@1
> +1	SIMPLE	x3	ref	ix1	ix1	5	test.x2.a	1	Child of pushed join@1; Using where
> +explain select straight_join * from 
> +t1 as x1 left join
> +(t1 as x2 inner join t1 as x3 on x3.b = x2.a)
> +on x2.pk = x1.a;
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	SIMPLE	x1	ALL	NULL	NULL	NULL	NULL	13	Parent of 2 pushed join@1
> +1	SIMPLE	x2	eq_ref	PRIMARY	PRIMARY	4	test.x1.a	1	Child of pushed join@1
> +1	SIMPLE	x3	ref	ix1	ix1	5	test.x2.a	1	
>  explain select straight_join count(*) from t1 as x1 
>  join t1 as x2 on x2.b = x1.a
>  join t1 as x3 on x3.b = x1.b;
> @@ -3983,13 +4014,13 @@ LOCAL+REMOTE READS_SENT
>  drop table spj_counts_at_startup;
>  drop table spj_counts_at_end;
>  scan_count
> -1969
> +1975
>  pruned_scan_count
>  7
>  sorted_scan_count
>  44
>  pushed_queries_defined
> -330
> +333
>  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	2010-09-29 11:53:33 +0000
> +++ b/mysql-test/suite/ndb/t/ndb_join_pushdown.test	2010-09-30 14:20:12 +0000
> @@ -2529,6 +2529,37 @@ select straight_join * from t1 as table1
>     (t1 as table2  join t1 as table3 on table2.pk = table3.b)
>   on table1.pk = table2.b;
>  
> +#############
> +# Testcase for 'sledgehammer' fix for scan -> outer join scan:
> +# Pushing of outer joined has to be dissabled as incomplete child batches
> +# may cause the parent row to be returned multiple times:
> +
> +# Push scan-scan when inner joined
> +explain select straight_join * from t1 as x1 
> +  inner join t1 as x2 on x2.b = x1.a;
> +
> +# Outer joined scans are not pushed.
> +explain select straight_join * from t1 as x1 
> +  left join t1 as x2 on x2.b = x1.a;
> +explain select straight_join * from t1 as x1 
> +  right join t1 as x2 on x2.b = x1.a;
> +
> +# If there is a lookup operation(s) inbetween the scans
> +# pushing is disabled if any of these are outer joined
> +
> +# inner joined lookups, push allowed
> +explain select straight_join * from 
> +  t1 as x1 inner join
> +    (t1 as x2 inner join t1 as x3 on x3.b = x2.a)
> +  on x2.pk = x1.a;
> +
> +# Even if x3 is inner joined with x2 (lookup)
> +# push is dissabled as x2 is outer joined with embedding scan operation
> +# which makes join relation between the scans on x1 & x3 an 'indirect' outer join
> +explain select straight_join * from 
> +  t1 as x1 left join
> +    (t1 as x2 inner join t1 as x3 on x3.b = x2.a)
> +  on x2.pk = x1.a;
>  
>  #############
>  # Test bushy-scans:
> @@ -2583,7 +2614,7 @@ select straight_join count(*) from t1 as
>  # If we have a bushy lookup, with scandescendants depending on these lookups,
>  # we dont serialize the scan by insertion of artificial dependencies.
>  #
> -# (Actually we could have serialized these also be forcing an artificial dependency
> +# (Actually we could have serialized these also by forcing an artificial dependency
>  #  between the referred lookup parent, and one of the other scan child. However, we
>  #  don't believe this to be an efficient way of executing the pushed query, and would
>  #  instead break these queries up into several smaller queries) 
> 
> === modified file 'sql/ha_ndbcluster.cc'
> --- a/sql/ha_ndbcluster.cc	2010-09-29 13:14:52 +0000
> +++ b/sql/ha_ndbcluster.cc	2010-09-30 14:20:12 +0000
> @@ -1019,19 +1019,31 @@ ndb_pushed_builder_ctx::field_ref_is_joi
>  
>        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_INNER_JOIN)
> +      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"));
>          DBUG_RETURN(false);
>        }
>        parent_no= descendant_no;
>  //    parent= scan_descendant;
> -      DBUG_PRINT("info", ("  Force artificial grandparent dependency through scan-child %s", parent->get_table()->alias));
> +      DBUG_PRINT("info", ("  Force artificial grandparent dependency through scan-child %s", scan_descendant->get_table()->alias));
> +
> +      if (scan_descendant && 
> +         table->get_join_type(scan_descendant) == AQP::JT_OUTER_JOIN)
> +      {
> +        DBUG_PRINT("info", ("  Table scan %d is outer joined with scan-descendant %d, not pushable (yet)",
> +                    tab_no, descendant_no));
> +        DBUG_RETURN(false);
> +      }
>      }
>      else
>      {
> -      // Verify that there are no ancestors with scan descendants.
> +      // 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)
>        {
> @@ -1041,13 +1053,24 @@ ndb_pushed_builder_ctx::field_ref_is_joi
>            DBUG_RETURN(false);
>          }
>  
> -        const AQP::Table_access* const ancestor= m_plan.get_table_access(ancestor_no);
> -        if (!is_lookup_operation(ancestor->get_access_type()))
> +        scan_ancestor= m_plan.get_table_access(ancestor_no);
> +        if (!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
> +
> +      // Outer joining scan-scan is not supported due to possible parent-NULL-row duplicates
> +      // being created in the NdbResultStream when incomplete child batches are received.
> +      // (Outer joining with scan may be indirect through lookup operations inbetween)
> +      if (scan_ancestor && 
> +         table->get_join_type(scan_ancestor) == AQP::JT_OUTER_JOIN)
> +      {
> +        DBUG_PRINT("info", ("  Table scan %d is outer joined with scan-ancestor %d, not pushable (yet)",
> +                    tab_no, ancestor_no));
> +        DBUG_RETURN(false);
> +      }
>      }
>    } // scan operation
>  
> @@ -1291,12 +1314,6 @@ ha_ndbcluster::make_pushed_join(AQP::Joi
>        DBUG_PRINT("info", ("Table %d not REF-joined, not pushable", join_cnt));
>        continue;
>      }
> -    if (!is_lookup_operation(child_type) && !is_lookup_operation(access_type) && 
> -         join_tab->get_join_type(join_parent) == AQP::JT_OUTER_JOIN )
> -    {
> -      DBUG_PRINT("info", ("Table %d is outer joined Scan-scan, not pushable (yet)", join_cnt));
> -      continue;
> -    }
>      /**
>       * If this is the first child in pushed join we need to define the 
>       * parent operation first.
> @@ -1396,6 +1413,7 @@ ha_ndbcluster::make_pushed_join(AQP::Joi
>        }
>      }
>  
> +    DBUG_ASSERT (join_parent!=NULL);
>      bool need_explicit_parent= true;
>      ndb_table_access_map parent_map(join_parent);
>      KEY_PART_INFO *key_part= key->key_part;
> @@ -1474,7 +1492,6 @@ ha_ndbcluster::make_pushed_join(AQP::Joi
>      const NdbDictionary::Table* const table= handler->m_table;
>   
>      NdbQueryOptions options;
> -    DBUG_ASSERT(join_parent!=NULL);
>      if (join_tab->get_join_type(join_parent) == AQP::JT_INNER_JOIN)
>      {
>        options.setMatchType(NdbQueryOptions::MatchNonNull);
> 
> 
> 
> ------------------------------------------------------------------------
> 
> 


-- 
Frazer Clement, Senior Software Engineer,
MySQL Cluster / Oracle - www.mysql.com
Office: Edinburgh, UK

Are you MySQL certified?  www.mysql.com/certification