[OPTIMIZER] Proposal for pushing join predicates into Unions posted to DERBY-805.

[Army <qo...@sbcglobal.net>]

I have attached a description of the changes I plan to submit for DERBY-805 to 
that Jira issue.  This is a rather complicated enhancement so the description of 
the changes is pretty long.  In short, though, I outline a 6-step approach to 
pushing join predicates down into Unions:

1 - Add the ability to take a predicate and scope it to a target result set so 
that it can be pushed to that result set.

2 - Implement the "pushOptPredicate()" and "optimizeIt()" methods for 
UnionNodes.  The former method should take predicates that are passed into the 
UnionNode from outer queries, scope them (per step 1) for the left and right 
children of the UnionNode, and store them locally.  The latter method should 
then pass the scoped predicates down to both children so that they can use the 
predicates in their own optimize()/optimizeIt() calls.

3 - Take scoped predicates (created in step 1) that are pushed into the children 
result sets of a UnionNode (per step 2) and allow the the children to push the 
scoped predicates even further down the tree, until we eventually get them to a 
base table.

4 - Make sure predicates that are pushed down into subqueries of a UnionNode are 
correctly "pulled" back up (if they are unscoped) or discarded (if they are 
scoped) for every permutation seen during optimization.

5 - Ensure that the best access path for a UnionNode that pushes predicates is 
correctly saved during optimization and correctly retrieved when it comes time 
to finalize the query's overall access path.

6 - And finally, when optimization is complete, make sure all relevant 
predicates are pushed down the tree one last time and left there, in preparation 
for code generation.

See DERBY-805.html for all the gory details.

I have made the changes described in this document locally and they all seem to 
work, with a couple of exceptions as noted at the end of the document.  I plan 
to break the changes down into separate patches where it's possible to do so, 
and will be posting those patches in the coming days.  In the meantime, if 
anyone has time to review this document and provide feedback, direction, or 
suggestions, I would be grateful.  As I myself am still trying to learn all the 
subtleties of Derby optimization, the more feedback I get, the better...

Thanks,
Army

Re: [OPTIMIZER] Proposal for pushing join predicates into Unions posted to DERBY-805.

[Army <qo...@sbcglobal.net>]

Jeffrey Lichtman wrote:
> 
>> 4 - Make sure predicates that are pushed down into subqueries of a 
>> UnionNode are correctly "pulled" back up (if they are unscoped) or 
>> discarded (if they are scoped) for every permutation seen during 
>> optimization.
> 
> Predicates may have to be copied when pushed into the children of a 
> UnionNode. When the predicates are pulled back up out of the UnionNode, 
> all but one copy of each will have to be discarded. 

Yes.  The way I do this now to keep a pointer to the original, unscoped 
predicate and push newly created, "scoped" predicates (one for each child) down 
to the children.  When it comes time to pull, I pull the unscoped predicate 
(which serves as the "all but one copy" that you mentioned) and discard the 
scoped ones.

> Please watch out for whether this causes performance problems due to 
> object creation and garbage collection. If such problems exist, it may 
> be possible to cache copies of predicates for re-use.

Good point, thanks for mentioning this.  The code right will rescope the 
predicate for each child for every permutation, which as you said could cause 
performance problems with object creation.  I will look at this to see if I can 
cache the scoped predicates for re-use, so that we don't end up re-scoping the 
same predicate for the same children for every permutation.

Army

Re: [OPTIMIZER] Proposal for pushing join predicates into Unions posted to DERBY-805.

[Jeffrey Lichtman <sw...@rcn.com>]

>4 - Make sure predicates that are pushed down into subqueries of a 
>UnionNode are correctly "pulled" back up (if they are unscoped) or 
>discarded (if they are scoped) for every permutation seen during optimization.

Predicates may have to be copied when pushed into the children of a 
UnionNode. When the predicates are pulled back up out of the 
UnionNode, all but one copy of each will have to be discarded. Please 
watch out for whether this causes performance problems due to object 
creation and garbage collection. If such problems exist, it may be 
possible to cache copies of predicates for re-use.


                        -        Jeff Lichtman
                                 swazoo@rcn.com
                                 Check out Swazoo Koolak's Web Jukebox at
                                 http://swazoo.com/ 

Re: [OPTIMIZER] Proposal for pushing join predicates into Unions posted to DERBY-805.

[Rick Hillegas <Ri...@Sun.COM>]

Hi Satheesh and Army,

I will try to get to this later this week. I'm a bit busy for the next 
few days.

Regards,
-Rick

Satheesh Bandaram wrote:

> This is a great improvement to Derby providing good performance 
> improvement. Thanks Army for the writeup... It does look impressive. I 
> will take this home for some "light" reading. :-)  I would like to 
> invite other optimizer experts to review the doc and code patch when 
> ready. Jeff Lichtman and Rick, do you have some time to review the doc?
>
> I have added an entry to DerbyDevActivities 
> <http://wiki.apache.org/db-derby/DerbyDevActivities>under improvements 
> for this. Hopefully this work will lead to further improvements to 
> Derby Optimizer in this area.
>
> Satheesh
>
> Army wrote:
>
>> I have attached a description of the changes I plan to submit for 
>> DERBY-805 to that Jira issue.  This is a rather complicated 
>> enhancement so the description of the changes is pretty long.  In 
>> short, though, I outline a 6-step approach to pushing join predicates 
>> down into Unions:
>>
>> 1 - Add the ability to take a predicate and scope it to a target 
>> result set so that it can be pushed to that result set.
>>
>> 2 - Implement the "pushOptPredicate()" and "optimizeIt()" methods for 
>> UnionNodes.  The former method should take predicates that are passed 
>> into the UnionNode from outer queries, scope them (per step 1) for 
>> the left and right children of the UnionNode, and store them 
>> locally.  The latter method should then pass the scoped predicates 
>> down to both children so that they can use the predicates in their 
>> own optimize()/optimizeIt() calls.
>>
>> 3 - Take scoped predicates (created in step 1) that are pushed into 
>> the children result sets of a UnionNode (per step 2) and allow the 
>> the children to push the scoped predicates even further down the 
>> tree, until we eventually get them to a base table.
>>
>> 4 - Make sure predicates that are pushed down into subqueries of a 
>> UnionNode are correctly "pulled" back up (if they are unscoped) or 
>> discarded (if they are scoped) for every permutation seen during 
>> optimization.
>>
>> 5 - Ensure that the best access path for a UnionNode that pushes 
>> predicates is correctly saved during optimization and correctly 
>> retrieved when it comes time to finalize the query's overall access 
>> path.
>>
>> 6 - And finally, when optimization is complete, make sure all 
>> relevant predicates are pushed down the tree one last time and left 
>> there, in preparation for code generation.
>>
>> See DERBY-805.html for all the gory details.
>>
>> I have made the changes described in this document locally and they 
>> all seem to work, with a couple of exceptions as noted at the end of 
>> the document.  I plan to break the changes down into separate patches 
>> where it's possible to do so, and will be posting those patches in 
>> the coming days.  In the meantime, if anyone has time to review this 
>> document and provide feedback, direction, or suggestions, I would be 
>> grateful.  As I myself am still trying to learn all the subtleties of 
>> Derby optimization, the more feedback I get, the better...
>>
>> Thanks,
>> Army
>>
>>