Bug #52005 'JOIN_TAB->dependent' may be incorrectly propageted for multilevel outer joins
Submitted: 12 Mar 2010 15:47 Modified: 14 Oct 2010 14:19
Reporter: Ole John Aske Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:5.1 OS:Any
Assigned to: Sergei Glukhov CPU Architecture:Any
Triage: Triaged: D1 (Critical)

[12 Mar 2010 15:47] Ole John Aske
Description:
make_join_statistics() calculate the transitive closure for relations a particular JOIN_TAB is 'dependent on'.

We aggregate the dependent table_map of of a JOIN_TAB by adding dependencies from other tables which we depend on. However, this may also cause new pedendencies to be available after we have completed processing a certain JOIN_TAB. With the current algorithm these dependencies will be unnoticed.

What we need as an algorithm where we reiterate until there are no more changes in the total set of dependencies.

I have included a suggested fix.

How to repeat:
Run Random Query Generator with the outer_join grammar with only the '#ifndef DBUG_OFF' part of my fix - It will hit the DBUG_ASSERT after a short while and expose the incomplete depencency map.

Suggested fix:
=== modified file 'sql/sql_select.cc'
--- sql/sql_select.cc   2010-03-10 09:36:44 +0000
+++ sql/sql_select.cc   2010-03-12 15:19:01 +0000
@@ -1488,6 +1488,24 @@ JOIN::optimize()
     DBUG_PRINT("info", ("need_tmp= %d, at:%d", need_tmp, __LINE__));
   }

@@ -2751,23 +2769,64 @@ make_join_statistics(JOIN *join, TABLE_L
        This will speed up the plan search for many cases with outer joins,
        as well as allow us to catch illegal cross references/
        Warshall's algorithm is used to build the transitive closure.
-       As we use bitmaps to represent the relation the complexity
-       of the algorithm is O((number of tables)^2).
+       As we may restart the outer loop upto 'table_count' times, the
+       complexity of the algorithm is O((number of tables)^3).
+       However, most if the iterations will be shortcircuted when
+       there are no pedendencies to propogate.
     */
+    for (i= 0 ; i < table_count ; i++)
+    {
+      uint j;
+      table= stat[i].table;
+
+      if (!table->reginfo.join_tab->dependent)
+        continue;
+
+      /* Add my dependencies to other tables depending on me */
+      for (j= 0, s= stat ; j < table_count ; j++, s++)
+      {
+        if (s->dependent & table->map)
+        {
+          table_map was_dependent= s->dependent;
+          s->dependent |= table->reginfo.join_tab->dependent;
+
+          /**
+           * If we change dependencies for a table we already have
+           * processed: Redo dependency propagation from this table.
+           */
+          if (i > j && s->dependent != was_dependent)
+          {
+            i = j-1;
+            break;
+          }
+        }
+      }
+    }
+
+#ifndef DBUG_OFF
+    /* Verify that all dependencies has been propagated.
+     * Mostly a codestub to verify that the above fix is required when running
+     * RQG with outer_join grammer - Which else will assert below after a
+     * few 1.000 queries.
+     */
     for (i= 0, s= stat ; i < table_count ; i++, s++)
     {
       for (uint j= 0 ; j < table_count ; j++)
       {
         table= stat[j].table;
         if (s->dependent & table->map)
-          s->dependent |= table->reginfo.join_tab->dependent;
+          /* There should be no more pending dependencies */
+          DBUG_ASSERT(!(table->reginfo.join_tab->dependent & ~(s->dependent)));
       }
-      if (outer_join & s->table->map)
-        s->table->maybe_null= 1;
     }
+#endif
+
     /* Catch illegal cross references for outer joins */
     for (i= 0, s= stat ; i < table_count ; i++, s++)
     {
+      if (outer_join & s->table->map)
+        s->table->maybe_null= 1;
+
       if (s->dependent & s->table->map)
       {
         join->tables=0;                        // Don't use join->table
[14 Mar 2010 9:51] Sveta Smirnova
Thank you for the report.

Verified as described.
[17 May 2010 13:53] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/108450

3386 Sergey Glukhov	2010-05-17
      Bug#52005 'JOIN_TAB->dependent' may be incorrectly propageted for multilevel outer joins
      There are two problems:
      1. In simplify_joins function we calculate table dependences. If STRAIGHT_JOIN hint
      is used for whole SELECT we do not count it and as result some dependendeces
      might be lost. It leads to incorrect table order which is retruned by
      join_tab_cmp_straight() function.
      2. make_join_statistics() calculate the transitive closure for relations a particular
      JOIN_TAB is 'dependent on'.
      We aggregate the dependent table_map of of a JOIN_TAB by adding dependencies from other
      tables which we depend on. However, this may also cause new pedendencies to be available
      after we have completed processing a certain JOIN_TAB.
      Both these problems affect condition pushdown and as result condition might be pushed
      into wrong table which leads to crash or even ommited which leads to wrong result.
      The fix:
      1. Use modified 'transitive closure' algorithm provided by Ole John Aske
      2. Update table dependences in simplify_joins according to 
         global STRAIGHT_JOIN hint.
      Note: the patch also fixes bugs 46091 & 51492
     @ mysql-test/r/join_outer.result
        test case
     @ mysql-test/t/join_outer.test
        test case
     @ sql/sql_select.cc
        There are two problems:
        1. In simplify_joins function we calculate table dependences. If STRAIGHT_JOIN hint
        is used for whole SELECT we do not count it and as result some dependendeces
        might be lost. It leads to incorrect table order which is retruned by
        join_tab_cmp_straight() function.
        2. make_join_statistics() calculate the transitive closure for relations a particular
        JOIN_TAB is 'dependent on'.
        We aggregate the dependent table_map of of a JOIN_TAB by adding dependencies from other
        tables which we depend on. However, this may also cause new pedendencies to be available
        after we have completed processing a certain JOIN_TAB.
        Both these problems affect condition pushdown and as result condition might be pushed
        into wrong table which leads to crash or even ommited which leads to wrong result.
        The fix:
        1. Use modified 'transitive closure' algorithm provided by Ole John Aske
        2. Update table dependences in simplify_joins according to 
           global STRAIGHT_JOIN hint.
[20 May 2010 13:27] Ole John Aske
Patch approved with a minor comment: (Which you are free to ignore)

You should consider to remove the '#ifndef DBUG_OFF... #endif' section from the patch. I originally added this to my proposed patch mainly to convince the verifier & developers that the dependency propagation was broken. With the  modified algorithm in place it should be obsolete.

Has also done extensive RQG testing with this patch (+ fix for #52357 which was required due to bug #48971) - I was not able to provoke any further problems related to these issues :-)
[27 May 2010 15:13] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/109387

3398 Sergey Glukhov	2010-05-27
      Bug#52005 'JOIN_TAB->dependent' may be incorrectly propageted for multilevel outer joins
      There are two problems:
      1. In simplify_joins function we calculate table dependencies. If STRAIGHT_JOIN hint
      is used for whole SELECT we do not count it and as result some dependendecies
      might be lost. It leads to incorrect table order which is returned by
      join_tab_cmp_straight() function.
      2. make_join_statistics() calculate the transitive closure for relations a particular
      JOIN_TAB is 'dependent on'.
      We aggregate the dependent table_map of a JOIN_TAB by adding dependencies from other
      tables which we depend on. However, this may also cause new dependencies to be
      available after we have completed processing a certain JOIN_TAB.
      Both these problems affect condition pushdown and as result condition might be pushed
      into wrong table which leads to crash or even omitted which leads to wrong result.
      The fix:
      1. Use modified 'transitive closure' algorithm provided by Ole John Aske
      2. Update table dependences in simplify_joins according to 
         global STRAIGHT_JOIN hint.
      Note: the patch also fixes bugs 46091 & 51492
     @ mysql-test/r/join_outer.result
        test case
     @ mysql-test/t/join_outer.test
        test case
     @ sql/sql_select.cc
        1. Use modified 'transitive closure' algorithm provided by Ole John Aske
        2. Update table dependences in simplify_joins according to 
           global STRAIGHT_JOIN hint.
[2 Jun 2010 8:49] Bugs System
Pushed into 5.1.48 (revid:georgi.kodinov@oracle.com-20100602084411-2yu607bslbmgufl3) (version source revid:sergey.glukhov@sun.com-20100527151353-7wgqj73d16lkzt57) (merge vers: 5.1.47) (pib:16)
[17 Jun 2010 6:12] Bugs System
Pushed into 5.5.5-m3 (revid:alexey.kopytov@sun.com-20100615145247-8bj0vmuqlotbqsn9) (version source revid:sergey.glukhov@sun.com-20100527152010-mvxqqnhjlmllpn4v) (merge vers: 5.5.5-m3) (pib:16)
[17 Jun 2010 6:15] Bugs System
Pushed into mysql-next-mr (revid:alik@sun.com-20100615150216-cubqoyn1fj9b6a2p) (version source revid:vasil.dimov@oracle.com-20100513074652-0cvlhgkesgbb2bfh) (pib:16)
[19 Jul 2010 19:48] Paul Dubois
Noted in 5.1.48, 5.5.5 changelogs.

For outer joins, the optimizer could fail to properly calculate table
dependencies.
[14 Oct 2010 8:30] Bugs System
Pushed into mysql-5.1-telco-7.0 5.1.51-ndb-7.0.20 (revid:martin.skold@mysql.com-20101014082627-jrmy9xbfbtrebw3c) (version source revid:vasil.dimov@oracle.com-20100513074652-0cvlhgkesgbb2bfh) (merge vers: 5.5.5-m3) (pib:21)
[14 Oct 2010 8:45] Bugs System
Pushed into mysql-5.1-telco-6.3 5.1.51-ndb-6.3.39 (revid:martin.skold@mysql.com-20101014083757-5qo48b86d69zjvzj) (version source revid:vasil.dimov@oracle.com-20100513074652-0cvlhgkesgbb2bfh) (merge vers: 5.5.5-m3) (pib:21)
[14 Oct 2010 8:59] Bugs System
Pushed into mysql-5.1-telco-6.2 5.1.51-ndb-6.2.19 (revid:martin.skold@mysql.com-20101014084420-y54ecj85j5we27oa) (version source revid:vasil.dimov@oracle.com-20100513074652-0cvlhgkesgbb2bfh) (merge vers: 5.5.5-m3) (pib:21)
[14 Oct 2010 14:19] Jon Stephens
Already documented in the 5.1.48 changelog; no additional changelog entries required. Set back to Closed state.
[21 Oct 2010 15:46] Guilhem Bichot
A small follow-up (just an assertion) has been added in tree next-mr-opt-backporting:
http://lists.mysql.com/commits/121554