I committed this patch over the weekend on trunk. I would like this fix to be ported to 10.2 Beta as soon as possible, as I have a customer who is waiting for it. Anyone know how to get this ported to 10.2 Beta?
Satheesh Satheesh Bandaram (JIRA) wrote: > [ > http://issues.apache.org/jira/browse/DERBY-634?page=comments#action_12427671 > ] > >Satheesh Bandaram commented on DERBY-634: >----------------------------------------- > >Oops... my previous comment got little garbled. Here it is again. > >I propose to address this issue in phases. Here is my current thinking: > >Background information: >----------------------- > >A performance optimization was introduced in Cloudscape before open sourcing >as Apache Derby. >Before this optimization was introduced, a query like: > >Select a, b, c from Table1 where a> 5 and b in > (select x from Table2, Table3 where Table2.x=Table3.x and y > > 100) > >would take longer time time to execute than needed. This becomes worse as the >complexity of the >subquery increases. Basic problem was that for every qualified value of 'b', >the subquery was >getting executed, recreating the results multiple times. Cloudscape, at that >time, had the ability >to materialize results of a subquery only if a single row is returned from the >subquery. >(where subquery is of the form select max(i) from Table2) > >A performance optimization was introduced that allowed for some "small number" >of rows greater than >1 to be cached dynamically at runtime. As the subquery was executed first >time, results of the >subquery were cached until MAX_MEMORY_PER_TABLE is reached, which was 1MG by >default. If the results >of the subquery could be fit into memory less than this configurable size, a >nested union resultset >would be built to cache the results. > >Future invocations of the subquery would simply return results from this >subquery cache without >actually evaluating subquery. This resulted in performance boost for a >customer query from 10 minutes >to a few seconds. > >Side effect of this optimization: >--------------------------------- > >While the optimization worked well for the customer query, it is causing >issues for the query in >question here. If the subquery were returning just an integer, the >optimization could attempt to cache >1MG/4, about 250,000 rows in nested union resultsets. Nesting of this deep >would cause stack overflow. > >Jeff Lichman also identified several other issues mentioned in the description >of this entry. > >Proposed Fix: >------------- > >First, I think it is important to fix regression caused by this optimization. >The optimization was >intended to cache small number of subquery results. Instead of caching single >row result of a subquery, >this optimization could be adjusted to cache a small number of results. > >Second, caching results of subquery in nested union resultsets is not needed. >This can be rewritten to >generate a linear resultset, which would save runtime stack growth. > >Third, as Jeff pointed out, a global subquery optimization that is performed >during optimization is >the best approach. He pointed out subquery materialization based on hash joins >decided during >optimization phase is the ideal solution. Fortunately, Army's optimizer >enhancements introduced >recently builds a subquery materialization capability to Derby and this could >be extended to handle >this case as well. > >I propose to address the regression first by caching only small number of rows >dynamically. If number >of subquery results could cross 512, I think this optimization should be >dynamically disabled. > >I will also file another Improvement that would suggest reworking the original >optimization to be >built on Army's subquery materialization framework. My current impression is >that Army's subquery >work needs to be more generalized and stabilized before extending to cover >other cases. > >Let me know if anyone has any comments. > > > > >>Subquery materialization can cause stack overflow >>------------------------------------------------- >> >> Key: DERBY-634 >> URL: http://issues.apache.org/jira/browse/DERBY-634 >> Project: Derby >> Issue Type: Bug >> Components: SQL >> Affects Versions: 10.1.1.1 >> Reporter: Jeff Lichtman >> Fix For: 10.2.0.0 >> >> >>A performance optimization in subquery processing can cause a stack overflow. >>The optimization materializes a subquery ResultSet in memory where it thinks >>the rows will fit in memory. The materialization is done as a set of nested >>unions of constant rows (UnionResultSets and RowResultSets). If there are a >>lot of rows this can cause a stack overflow when fetching a row. >>The obvious fix is to make it use an iterative technique rather than a >>recursive one for storing and returning the rows. See the method >>BaseActivation.materializeResultSetIfPossible() in the language execution >>code. >>There are some other issues with this performance optimization that should be >>looked at: >>1) The optimization can backfire, making the query run much slower. For >>example, in the query: >> select * from one_row_table where column1 not in >> (select column2 from million_row_table) >>reading million_row_table into memory is an expensive operation. If there is >>an index on million_row_table.column2, the query should return a result very >>quickly despite the large size of million_row_table by doing a single probe >>into million_row_table via the index. >>Since in-memory materialization can be an expensive operation, the decision >>about whether to do it should be made based on query optimizer cost >>estimates. See SubqueryNode.generateExpression(). >>2) It may not be wise to cache partial query results in memory at all. >>Although this can help performance in some cases, it also chews up memory. >>This is different from a limited-size cache with a backing store (like what >>the store uses for page caching). The language has no way to limit the total >>amount of memory used in this type of processing. Note that hash joins >>originally used in-memory hash tables with no backing store, and that a >>backing store was added later. >>3) The implementation of this optimization has some problems. The decision to >>materialize the subquery results in memory is made during code generation - >>all such decisions should be made during the compilation phase. It's not >>clear to me why materializeResultSetIfPossible() is in BaseActivation - I >>would expect the of materialization to be done by a type of ResultSet, not by >>a method in BaseActivation. Also, this method calls getMaxMemoryPerTable() in >>the OptimizerFactory - nothing in the execution code should refer to anything >>in the compilation code (perhaps getMaxMemoryPerTable() should be moved >>somewhere else). >> >> > > >
