|
Thanks Jeff for your analysis. I was just getting ready to file another improvement request to make this optimization more generic. (not specific to unions) I have seen huge improvements in two different customer situations. For the situation I filed the defect, each of the views (V1 and V2) had 36 tables each and by materializing the inner view into a temp. table, I noticed speed up from 70-150 seconds to under 3 seconds. (including the cost of creating temp. table)
I also saw another situation later without unions where materializing some table subqueries improved performance by couple of orders of magnitude. So you are right... this optimization can be applied to other cases too. I think materialization with or without hash joins should be useful. In both situations, creating temp. table that materialized derived tables improved so much. You are right that the optimization should be done inside the optimizer. Attaching a patch (d781_v1.patch) to address this issue by allowing the optimizer to consider and choose hash joins with subqueries, which is a more general case of the specific union example mentioned in the description for this issue. In brief, the patch does this by following up on the suggestions given by Jeff Lichtman in comments above and also in the following thread:
http://article.gmane.org/gmane.comp.apache.db.derby.devel/12208 Since result set materialization comes for "free" with hash joins, that fact we now allow hash joins with subqueries (as of this patch) means that we implicitly have a way to materialize the subquery result sets. The details of the patch are included as Note that I did not add the sample union query shown in the description for this issue to the tests because when I run it against the current codeline, the optimizer will already choose to do materialization of the UnionNode (via hash join) even without the patch for this issue, and thus it didn't seem like that particular test case was useful. The new test in subqery.sql is more relevant because the optimizer will choose to do a nested loop join with the subquery before my changes and will do a hash join after my changes, which seems to more accurately reflect what this issue is about. I ran derbyall using sane jars on Red Hat Linux with ibm142 and saw no new failures, and the overall execution time does not change despite the extra work the optimizer is doing. I would greatly appreciate any review/feedback people might have on these changes. Thanks. Attaching an updated patch, d781_v2.patch, that is synced with the latest codeline and that also has a small fix to the lang/subquery test (there was a typo in the first patch). Other than the minor test fix, this patch is identical to the _v1 patch.
Still awaiting review, if anyone has the time... Hi Army,
Thanks again for the great writeup, and for putting the energy into clear comments and careful changes to the code. It really makes a huge difference when trying to read the code. I've read through the writeup carefully, and checked it against the patch, and I have no comments or suggestions to make. The patch applied cleanly for me, built without problems, and lang/subquery.sql and lang/predicatesIntoviews.sql both passed in my environment. It looks like an excellent patch to me; I am +1 for commit. Thank you so much for volunteering to do this review, Bryan--and for taking the time to read the write-up in its rather wordy entirety. I really appreciate your time and effort here.
I'll work on putting together a release note as you described on derby-dev: http://article.gmane.org/gmane.comp.apache.db.derby.devel/23875 and will post that to this issue and/or to Thanks again for all of your time, Bryan! Possible RELEASE NOTE for this fix is as follows, based on suggestions from Bryan in the above-referenced thread:
<begin_release_note> The Derby optimizer has been enhanced so that it now considers the cost of performing a hash join with subqueries when it is safe to do so. If the cost of the hash join is better than a nested loop join, Derby will choose to do the hash join and will thereby materialize the subquery. WHAT CHANGED When optimizing a query that has one or more non-flattenable subqueries in the FROM clause, Derby will now check to see if it is possible to perform a hash join with that subquery as the inner table. Prior to Derby 10.2, the optimizer would never consider a hash join with a subquery; it only did nested loop joins. SYMPTOM Execution performance of queries containing non-flattenable subqueries may change. The expectation is that the new (10.2) query plans will show improved performance over the old ones. Another potential symptom is that the compilation time for such queries may increase. If this happens, the increase should only occur at compilation time; execution time should either improve or, at the very least, remain the same as in earlier versions of Derby. CAUSE If the optimizer chooses to do a hash join with a subquery, Derby only has to execute the subquery a single time per statement, after which Derby can just perform the desired join against the materialized result set. Depending on how many rows are in the outer table of the join, this once-per-statement execution of the subquery can lead to major performance improvements over the once-per-outer-row execution employed by earlier versions of Derby. As for the extra compilation time, this is due to the simple fact that the optimizer is now doing more work--i.e. in addition to considering nested loop joins with subqueries, it is now _also_ considering hash joins with those subqueries, and that means that it could potentially take longer for the optimizer to finish its work. Note again that, if it occurs, the increased time should only occur at compilation time; execution time should either improve or, at the very least, remain the same as in earlier versions of Derby. SOLUTION This was an intentional change to improve the execution plans chosen by the optimizer for queries having large and/or complex subqueries. The expectation is that the new behavior--and the subsequent query plans--will lead to improved performance over the old ones, so no further solution is required. WORKAROUND There is no way to disable/workaround this new behavior since the symptom as described above is a good one for Derby. That said, any user who notices a negative performance change after moving to Derby 10.2, and who believes that the difference in performance is related to this optimizer enhancement, is encouraged to visit the following "performance diagnosis" page and to follow up with his/her findings on the Derby mailing lists: http://wiki.apache.org/db-derby/PerformanceDiagnosisTips <end_release_note> There may be existing application impact as applications may see increased compilation times but should see improved execution time performance. Applications may want to adjust to use PreparedStatements instead of Statements (always a good practice with Derby).
Resolving issue as the patch was committed by Satheesh with svn #423989. I'll wait a couple of days to see if anything comes up and then will close this next week if all is well.
Thanks again to Bryan for the review and to Satheesh for the commit. I think it would be good to modify this improvement description, as it will likely be picked up by release notes and/or other documentation. The fix is more generic than 'UNION' subqueries as the original description says.
Also the example in the description doesn't apply anymore, I think. When the entry was made, join-predicate push down work wasn't completed, so the example in the description would have shown the problem, I think. But now, (post join-predicate pushdown work) the example may not apply. > I think it would be good to modify this improvement description
Seems like this could be a simple as removing the word "union" from the description--does that sound reasonable to you? Or do you want an entirely new description? Something like "Subquery materialization via hash join" or "Support subquery materialization by allowing the optimizer to cost and generate hash joins with subqueries". Any preference? Removed the word "union" from the summary since the changes affect subqueries in general, not just UNION subqueries (as Satheesh pointed out). I decided to leave the actual description as it is, though, since I think it's useful as background to the follow-up comments which eventually led to the final changes. Also, if we change the description many of the comments will no longer make sense. For the sake of clarity I prefer to leave the description as it is. The more generic "summary" will be what's picked up in release notes, so I think that's good enough...
Of course, people should feel free to speak up if they disagree. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|
Improvement
Closed
Major
Materialize subqueries in select list where possible to avoid creating invariant resultsets many times.
The report identifies a real problem (performance with a union as the inner table of a join) and proposes a solution that would work (materialization). I think, though, that the proposed solution focuses in the wrong place. The materialization should happen as a result of a join strategy, not as part of the logic associated with unions.
There are cases where materializing a union would cause a query to run slower. Materialization requires the creation of a temporary conglomerate and the inserting of rows into the conglomerate, so it should be done only if the savings are greater than the costs. Since materialization can make things either faster or slower depending on circumstances, the decision as to whether to materialize should be done in the optimizer.
Also, there are other types of result sets that could benefit from materialization - for example, INTERSECT, joins, aggregates, etc. Any of these could end up on the right side of a join through the use of table subqueries (i.e. SELECT statements in the FROM list of the outer query). I don't think we want to re-implement the materialization logic in all of these cases. I suppose the logic could be pushed into a parent class, but I think even that would be putting it in the wrong place.
If you think about it, we already have a join strategy that materializes the inner result set, i.e. hash join. I would expect the optimizer to at least consider this strategy for the example given in this enhancement request. We should check whether the optimizer is making the correct decision about hash join in this case before implementing materialization logic specific to unions.