db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jeffrey Lichtman <swa...@rcn.com>
Subject Re: [OPTIMIZER] OptimizerImpl "best plans" for subqueries?
Date Sat, 18 Feb 2006 07:51:15 GMT

>>I believe the optimizer currently keeps track of only two "best 
>>plans" - the best access path for each table in a query (or 
>>subquery) as it's currently being considered in a join order, and 
>>the best overall join order and path for each table for the best 
>>plan it's found so far.
>Am I right in thinking that the first of these two "best plans" is 
>stored in "bestAccessPath", and the second is stored in 
>"trulyTheBestAccessPath"?  That's how I read it, but I'd just like 
>to make sure.

Yes, that's right.

. . .
<a bunch of stuff deleted>
. . .

>Does that sound right, or am I being too optimistic?

I think it's right as far as it goes, but still doesn't fix the other 
issues discussed below:

>I've been struggling to wrap my head around this question, as well 
>(at least, I *think* this is the question with which I've been 
>struggling ;)  And ultimately, I think this ties back to what I was 
>trying to do with the Phase 1 patch for DERBY-805--namely, keep 
>track of "the plan to use with the best plan found for the outer 
>query".  But based on this discussion, I wonder if the patch I 
>posted goes far enough--if there are subqueries beneath subqueries, 
>such as can happen if we have unions beneath unions beneath unions, 
>how do we get each of those subqueries to remember its best plan 
>with respect to _every_ level of outer query (there could be 
>several) that sits above it?

I think it may be necessary when remembering "truly the best" access 
path at any level of subquery to tell each table subquery to remember 
its best access path as "truly the best" also, and to recurse through 
all the nested subqueries to do this. I don't think this would be 
very hard to implement. I only worry about what would happen with 
deeply-nested subqueries - this could create an order 2**n algorithm 
(that is, one whose time would grow exponentially with the number of 
levels of nesting).

>That's the question I've been pondering for the past two days; is 
>that also what you are referring to by the above "I'll have to think 
>about" statement?  Or am I taking this in a different direction?

Yes, I believe we're thinking about the same thing.

                        -        Jeff Lichtman
                                 Check out Swazoo Koolak's Web Jukebox at

View raw message