MySQL Lists are EOL. Please join:

List:Internals« Previous MessageNext Message »
From:Sergey Petrunia Date:October 7 2005 1:06pm
Subject:bk commit into 5.0 tree (sergefp:1.2005) BUG#13126
View as plain text  
Below is the list of changes that have just been committed into a local
5.0 repository of psergey. When psergey does a push these changes will
be propagated to the main repository and, within 24 hours after the
push, to the public repository.
For information on how to access the public repository
see http://dev.mysql.com/doc/mysql/en/installing-source-tree.html

ChangeSet
  1.2005 05/10/07 17:06:27 sergefp@stripped +6 -0
  BUG#13126: (Invalid join orders produced for nested joins, wrong query results) 
  Before join execution: 
    Assign each non simplified away or confluent nested join a bit number;
    For each JOIN_TAB, remember the which nested joins it is a part of.
  On execution:
    Before attempting to add a JOIN_TAB to partial join order, check that we're 
    not "leaving" any nested join before we've put all of its tables into the 
    join order.

  sql/table.h
    1.116 05/10/07 17:06:17 sergefp@stripped +2 -0
    BUG#13126: Added NESTED_JOIN::nj_map - now each nested join that has not been
    simplified away, and is not a container for a single table has a bit number 
    in nested_join_map. 

  sql/sql_select.h
    1.100 05/10/07 17:06:17 sergefp@stripped +9 -0
    BUG#13126: 
    * Added JOIN_TAB::embedding_map - bitmap of nested joins this table is part of
    * Added JOIN::nested_joins: mapping from bit numbers to NESTED_JOIN*

  sql/sql_select.cc
    1.377 05/10/07 17:06:17 sergefp@stripped +162 -3
    BUG#13126: (Invalid join orders produced for nested joins, wrong query results) 
    Before join execution: 
      Assign each non simplified away or confluent nested join a bit number;
      For each JOIN_TAB, remember the which nested joins it is a part of.
    On execution:
      Before attempting to add a JOIN_TAB to partial join order, check that we're 
      not "leaving" any nested join before we've put all of its tables into the 
      join order.

  sql/mysql_priv.h
    1.356 05/10/07 17:06:17 sergefp@stripped +1 -0
    BUG#13126: Added nested_join_map bitmap type

  mysql-test/t/join_nested.test
    1.12 05/10/07 17:06:17 sergefp@stripped +68 -0
    Testcase for BUG#13126

  mysql-test/r/join_nested.result
    1.16 05/10/07 17:06:17 sergefp@stripped +64 -0
    Testcase for BUG#13126

# This is a BitKeeper patch.  What follows are the unified diffs for the
# set of deltas contained in the patch.  The rest of the patch, the part
# that BitKeeper cares about, is below these diffs.
# User:	sergefp
# Host:	newbox.mylan
# Root:	/home/psergey/mysql-5.0-bug13126-r3

--- 1.355/sql/mysql_priv.h	2005-09-23 17:47:01 +04:00
+++ 1.356/sql/mysql_priv.h	2005-10-07 17:06:17 +04:00
@@ -42,6 +42,7 @@
 
 /* TODO convert all these three maps to Bitmap classes */
 typedef ulonglong table_map;          /* Used for table bits in join */
+typedef ulonglong nested_join_map;
 typedef Bitmap<64> key_map;           /* Used for finding keys */
 typedef ulong key_part_map;           /* Used for finding key parts */
 

--- 1.376/sql/sql_select.cc	2005-09-30 01:34:15 +04:00
+++ 1.377/sql/sql_select.cc	2005-10-07 17:06:17 +04:00
@@ -98,6 +98,11 @@
                                              void *table_join_idx);
 static COND *simplify_joins(JOIN *join, List<TABLE_LIST> *join_list,
                             COND *conds, bool top);
+static uint number_nested_joins(JOIN *join, List<TABLE_LIST> *join_list,
+                                uint first_unused);
+static bool can_extend_join_order(JOIN *join, table_map remaining, 
+                                  JOIN_TAB *prev_tab, JOIN_TAB *next_tab);
+
 static COND *optimize_cond(JOIN *join, COND *conds,
                            List<TABLE_LIST> *join_list,
 			   Item::cond_result *cond_value);
@@ -585,8 +590,14 @@
 
     sel->first_cond_optimization= 0;
 
+    if (!(nested_joins= (NESTED_JOIN**)thd->alloc(sizeof(NESTED_JOIN*)*
+                                                  tables)))
+    {
+      DBUG_RETURN(1);
+    }
     /* Convert all outer joins to inner joins if possible */
     conds= simplify_joins(this, join_list, conds, TRUE);
+    number_nested_joins(this, join_list, 0);
 
     sel->prep_where= conds ? conds->copy_andor_structure(thd) : 0;
 
@@ -1961,14 +1972,19 @@
 	continue;
       }
       outer_join|= table->map;
+      s->embedding_map= 0;
+      for (;embedding; embedding= embedding->embedding)
+        s->embedding_map|= embedding->nested_join->nj_map;
       continue;
     }
     if (embedding)
     {
       /* s belongs to a nested join, maybe to several embedded joins */
+      s->embedding_map= 0;
       do
       {
         NESTED_JOIN *nested_join= embedding->nested_join;
+        s->embedding_map|=nested_join->nj_map;
         s->dependent|= embedding->dep_tables;
         embedding= embedding->embedding;
         outer_join|= nested_join->used_tables;
@@ -4022,7 +4038,10 @@
   for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
   {
     table_map real_table_bit= s->table->map;
-    if ((remaining_tables & real_table_bit) && !(remaining_tables & s->dependent))
+    if ((remaining_tables & real_table_bit) && 
+        !(remaining_tables & s->dependent) && 
+        (!idx || can_extend_join_order(join, remaining_tables, 
+                                       join->positions[idx-1].table, s)))
     {
       double current_record_count, current_read_time;
 
@@ -7195,7 +7214,20 @@
     The new condition, if success
     0, otherwise  
 */
+//{remove
+static void print_table_list(List<TABLE_LIST> *list)
+{
+  List_iterator<TABLE_LIST> it(*list);
+  TABLE_LIST *l;
+  fprintf(stderr, "list{");
+  while ((l=it++))
+  {
+    fprintf(stderr, "%s,", l->alias);
+  }
+  fprintf(stderr, "}\n");
+}
 
+//}
 static COND *
 simplify_joins(JOIN *join, List<TABLE_LIST> *join_list, COND *conds, bool top)
 {
@@ -7340,13 +7372,140 @@
       {
         tbl->embedding= table->embedding;
         tbl->join_list= table->join_list;
-      }      
+      }
       li.replace(nested_join->join_list);
     }
   }
   DBUG_RETURN(conds); 
 }
-        
+
+
+/*
+  Assign each nested join structure a bit in nested_join_map, and setup
+  bit number -> NESTED_JOIN* mapping in JOIN::nested_joins.
+  
+  SYNOPSIS
+    number_nested_joins()
+      join          Join being processed
+      join_list     List of tables 
+      first_unused  Number of first unused bit in nested_join_map before the
+                    call
+
+  RETURN
+    First unused bit in nested_join_map after the call.
+*/
+
+static 
+uint number_nested_joins(JOIN *join, List<TABLE_LIST> *join_list, 
+                         uint first_unused)
+{
+  TABLE_LIST *table;
+  List_iterator<TABLE_LIST> li(*join_list);
+  DBUG_ENTER("number_nested_joins");
+  
+  //print_table_list(join_list);
+  
+  while ((table= li++))
+  {
+    NESTED_JOIN *nested_join;
+    if ((nested_join= table->nested_join))
+    {
+      if (join_list->elements != 1) 
+      {
+        nested_join->nj_map= 1 << first_unused;
+        join->nested_joins[first_unused++]= nested_join;
+      }
+      first_unused= number_nested_joins(join, &nested_join->join_list, 
+                                        first_unused);
+    }
+  }
+  DBUG_RETURN(first_unused);
+}
+
+
+/*
+  Check if nested join processing rules allow that partial join order with
+  last table last_tab is extended with table next_tab.
+  
+  SYNOPSIS
+   can_extend_join_order()
+     join       Join being processed
+     remaining  Bitmap of tables that remain to be included in join order
+                (including next_tab->table).
+     last_tab   Last table in current partial join order (this function is
+                not called for 'empty' partial join orders)
+     next_tab   Table we're going to extend the current partial join with
+
+  NOTE
+    It is assumed that current partial join order, and its extension with
+    next_tab are valid wrt table dependencies
+
+  DECRIPTION
+    This function is used to prevent construction of join orders that
+    executioner cannot handle. Current executioner algorithm imposes the 
+    following limitations on join order:
+    1) an "outer" table must be before any corresponding "inner" table.
+       This is guaranteed by table dependencies.
+    2) "Non interleaving" Tables inside a nested join must form a continous 
+       sequence in join order (i.e. their sequence must not be interrupted 
+       by tables outside of the nested join). This is guaranteed by this 
+       function.
+
+    WHY NEED NON-INTERLEAVING
+    Consider an example: 
+     
+     select * from t0 join t1 left join (t2 join t3) on cond1
+    
+    The join order "t1 t2 t0 t3" is invalid:
+
+    table t0 is outside of the nested join, so WHERE condition for t0 is
+    attached directly to t0 (without triggers, and it may be used to access
+    t0). Applying WHERE(t0) to (t2,t0,t3) record is invalid as we may miss
+    combinations of (t1, t2, t3) that satisfy condition cond1, and produce a
+    null-complemented (t1, t2.NULLs, t3.NULLs) row, which should not have
+    been produced.
+    
+    If table t0 is not between t2 and t3, the problem doesn't exits:
+    * If t0 is located after (t2,t3), WHERE(t0) is applied after nested join
+      processing has finished.
+    * If t0 is located before (t2,t3), predicates like WHERE_cond(t0, t2) are
+      wrapped into condition triggers, which takes care of correct nested
+      join processing.
+    
+  IMPLEMENTATION
+    We get this info from pre-processing:
+    * JOIN_TAB::embedding_map is a bitmap of nested joins a table is a part of.
+    * NESTED_JOIN::used_tables is a bitmap of tables contained within a
+      nested join.
+    In transition from current join table to next, we get a list of nested 
+    joins we will exit and disable the transition if we exist a nested join
+    without adding all of its tables to the partial join order.
+
+  RETURN
+    TRUE   Plan extension allowed
+    FALSE  Plan extension not allowed
+*/
+
+static bool can_extend_join_order(JOIN *join, table_map remaining, 
+                                  JOIN_TAB *last_tab, JOIN_TAB *next_tab)
+{
+  nested_join_map leaving;
+  uint pos= 0;
+  /* Get bitmap of nested joins we're 'leaving' */
+  leaving= last_tab->embedding_map & ~ next_tab->embedding_map;
+  while (leaving)
+  {
+    if (leaving & 1)
+    {
+      if (join->nested_joins[pos]->used_tables & remaining)
+        return FALSE;
+    }
+    leaving = leaving >> 1;
+    pos++;
+  }
+  return TRUE;
+}
+
 
 static COND *
 optimize_cond(JOIN *join, COND *conds, List<TABLE_LIST> *join_list,

--- 1.99/sql/sql_select.h	2005-09-22 02:10:59 +04:00
+++ 1.100/sql/sql_select.h	2005-10-07 17:06:17 +04:00
@@ -136,6 +136,8 @@
   TABLE_REF	ref;
   JOIN_CACHE	cache;
   JOIN		*join;
+  /* Bitmap of nested joins this table is part of */
+  nested_join_map embedding_map;
 
   void cleanup();
 } JOIN_TAB;
@@ -263,6 +265,12 @@
   bool union_part; // this subselect is part of union 
   bool optimized; // flag to avoid double optimization in EXPLAIN
 
+  /* 
+    For nested joins left after simplification: mapping from bit numbers in 
+    nested_join_map to nested join structs (nested_joins[k].nj_map == 1<<k).
+  */
+  NESTED_JOIN **nested_joins;
+
   JOIN(THD *thd_arg, List<Item> &fields_arg, ulonglong select_options_arg,
        select_result *result_arg)
     :fields_list(fields_arg)
@@ -312,6 +320,7 @@
     zero_result_cause= 0;
     optimized= 0;
     cond_equal= 0;
+    nested_joins= NULL;
 
     all_fields= fields_arg;
     fields_list= fields_arg;

--- 1.115/sql/table.h	2005-09-22 02:10:59 +04:00
+++ 1.116/sql/table.h	2005-10-07 17:06:17 +04:00
@@ -760,6 +760,8 @@
   table_map         not_null_tables; /* tables that rejects nulls           */
   struct st_join_table *first_nested;/* the first nested table in the plan  */
   uint              counter;         /* to count tables in the nested join  */
+  /* bit used to identify this nested join (see JOIN::nested_joins) */
+  nested_join_map   nj_map;        
 } NESTED_JOIN;
 
 

--- 1.15/mysql-test/r/join_nested.result	2005-09-29 18:34:14 +04:00
+++ 1.16/mysql-test/r/join_nested.result	2005-10-07 17:06:17 +04:00
@@ -1403,3 +1403,67 @@
 ERROR 42S22: Unknown column 'v2.x' in 'field list'
 DROP VIEW v1, v2;
 DROP TABLE t1, t2, t3, t4, t5, t6;
+create table t1 (id1 int(11) not null);
+insert into t1 values (1),(2);
+create table t2 (id2 int(11) not null);
+insert into t2 values (1),(2),(3),(4);
+create table t3 (id3 char(16) not null);
+insert into t3 values ('100');
+create table t4 (id2 int(11) not null, id3 char(16));
+create table t5 (id1 int(11) not null, key (id1));
+insert into t5 values (1),(2),(1);
+create view v1 as
+select t4.id3 from t4 join t2 on t4.id2 = t2.id2;
+select t1.id1 from t1 inner join (t3 left join v1 on t3.id3 = v1.id3);
+id1
+1
+2
+drop view v1;
+drop table t1, t2, t3, t4, t5;
+create table t0 (a int);
+insert into t0 values (0),(1),(2),(3);
+create table t1(a int);
+insert into t1 select A.a + 10*(B.a) from t0 A, t0 B;
+create table t2 (a int, b int);
+insert into t2 values (1,1), (2,2), (3,3);
+create table t3(a int, b int, filler char(200), key(a));
+insert into t3 select a,a,'filler' from t1;
+insert into t3 select a,a,'filler' from t1;
+create table t4 like t3;
+insert into t4 select * from t3;
+insert into t4 select * from t3;
+create table t5 like t4;
+insert into t5 select * from t4;
+insert into t5 select * from t4;
+create table t6 like t5;
+insert into t6 select * from t5;
+insert into t6 select * from t5;
+create table t7 like t6;
+insert into t7 select * from t6;
+insert into t7 select * from t6;
+explain select * from t4 join 
+t2 left join (t3 join t5 on t5.a=t3.b) on t3.a=t2.b where t4.a<=>t3.b;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	X	
+1	SIMPLE	t3	ref	a	a	5	test.t2.b	X	
+1	SIMPLE	t5	ref	a	a	5	test.t3.b	X	
+1	SIMPLE	t4	ref	a	a	5	test.t3.b	X	Using where
+explain select * from (t4 join t6 on t6.a=t4.b) right join t3 on t4.a=t3.b
+join t2 left join (t5 join t7 on t7.a=t5.b) on t5.a=t2.b where t3.a<=>t2.b;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	X	
+1	SIMPLE	t3	ref	a	a	5	test.t2.b	X	Using where
+1	SIMPLE	t4	ref	a	a	5	test.t3.b	X	
+1	SIMPLE	t6	ref	a	a	5	test.t4.b	X	
+1	SIMPLE	t5	ref	a	a	5	test.t2.b	X	
+1	SIMPLE	t7	ref	a	a	5	test.t5.b	X	
+explain select * from t2 left join
+(t3 left join (t4 join t6 on t6.a=t4.b) on t4.a=t3.b 
+join t5 on t5.a=t3.b) on t3.a=t2.b;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	X	
+1	SIMPLE	t3	ref	a	a	5	test.t2.b	X	
+1	SIMPLE	t4	ref	a	a	5	test.t3.b	X	
+1	SIMPLE	t6	ref	a	a	5	test.t4.b	X	
+1	SIMPLE	t5	ref	a	a	5	test.t3.b	X	
+drop table t0, t1, t2, t4, t5, t6;

--- 1.11/mysql-test/t/join_nested.test	2005-09-29 18:34:14 +04:00
+++ 1.12/mysql-test/t/join_nested.test	2005-10-07 17:06:17 +04:00
@@ -832,3 +832,71 @@
 
 DROP VIEW v1, v2;
 DROP TABLE t1, t2, t3, t4, t5, t6;
+
+#
+# BUG#13126 -test case from bug report
+#
+create table t1 (id1 int(11) not null); 
+insert into t1 values (1),(2);
+
+create table t2 (id2 int(11) not null);
+insert into t2 values (1),(2),(3),(4);
+
+create table t3 (id3 char(16) not null);
+insert into t3 values ('100');
+
+create table t4 (id2 int(11) not null, id3 char(16));
+
+create table t5 (id1 int(11) not null, key (id1));
+insert into t5 values (1),(2),(1);
+
+create view v1 as
+  select t4.id3 from t4 join t2 on t4.id2 = t2.id2;
+
+select t1.id1 from t1 inner join (t3 left join v1 on t3.id3 = v1.id3);
+
+drop view v1;
+drop table t1, t2, t3, t4, t5;
+
+create table t0 (a int);
+insert into t0 values (0),(1),(2),(3);
+create table t1(a int);
+insert into t1 select A.a + 10*(B.a) from t0 A, t0 B;
+
+create table t2 (a int, b int);
+insert into t2 values (1,1), (2,2), (3,3);
+
+create table t3(a int, b int, filler char(200), key(a));
+insert into t3 select a,a,'filler' from t1;
+insert into t3 select a,a,'filler' from t1;
+
+create table t4 like t3;
+insert into t4 select * from t3;
+insert into t4 select * from t3;
+
+create table t5 like t4;
+insert into t5 select * from t4;
+insert into t5 select * from t4;
+
+create table t6 like t5;
+insert into t6 select * from t5;
+insert into t6 select * from t5;
+
+create table t7 like t6;
+insert into t7 select * from t6;
+insert into t7 select * from t6;
+
+--replace_column 9 X
+explain select * from t4 join 
+  t2 left join (t3 join t5 on t5.a=t3.b) on t3.a=t2.b where t4.a<=>t3.b;
+
+--replace_column 9 X
+explain select * from (t4 join t6 on t6.a=t4.b) right join t3 on t4.a=t3.b
+  join t2 left join (t5 join t7 on t7.a=t5.b) on t5.a=t2.b where t3.a<=>t2.b;
+
+--replace_column 9 X
+explain select * from t2 left join
+  (t3 left join (t4 join t6 on t6.a=t4.b) on t4.a=t3.b 
+   join t5 on t5.a=t3.b) on t3.a=t2.b;
+
+drop table t0, t1, t2, t4, t5, t6;
Thread
bk commit into 5.0 tree (sergefp:1.2005) BUG#13126Sergey Petrunia7 Oct