| 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: | |
| Category: | MySQL Server: Optimizer | Severity: | S3 (Non-critical) |
| Version: | 5.1 | OS: | Any |
| Assigned to: | Sergei Glukhov | CPU Architecture: | Any |
[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
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