db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Satheesh Bandaram <banda...@gmail.com>
Subject Re: [jira] Commented: (DERBY-634) Subquery materialization can cause stack overflow
Date Tue, 15 Aug 2006 01:44:11 GMT
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).
>>    
>>
>
>  
>



Mime
View raw message