Mailing-List: contact derby-dev-help@db.apache.org; run by ezmlm
Precedence: bulk
Reply-To: <derby-dev@db.apache.org>
Message-ID: <1440569331.1140138386132.JavaMail.jira@ajax.apache.org>
Date: Fri, 17 Feb 2006 02:06:26 +0100 (CET)
From: "A B (JIRA)" <derby-dev@db.apache.org>
To: derby-dev@db.apache.org
Subject: [jira] Commented: (DERBY-805) Push join predicates into union and
 other set operations. DERBY-649 implemented scalar (single table) predicate
 pushdown. Adding join predicate push down could improve performance
 significantly.
In-Reply-To: <688763290.1136837782912.JavaMail.jira@ajax.apache.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit

    [ http://issues.apache.org/jira/browse/DERBY-805?page=comments#action_12366729 ] 

A B commented on DERBY-805:
---------------------------

Pasting my reply to Jeff's question here (Jira was down this morning, so I just sent the reply to derby-dev):

Jeff Lichtman (JIRA) wrote:

>     [ http://issues.apache.org/jira/browse/DERBY-805?page=comments#action_12366598 ]
> Jeff Lichtman commented on DERBY-805:
> -------------------------------------
>
> I have been reading Army's (A B''s) document, and I have some questions.


Thank you very much for taking the time to read it.  I really appreciate it.

> How could a predicate be pushable to only one side of a union? Can you provide an example of a predicate that can be pushed only to one side?

If we take something along the lines of:

select ... from
  t2,
  (select * from t1 union values (1,2), (3,4), (5,6)) X1 (a,b)
where X1.a = t2.i;

In this case the predicate X1.a = t2.i could be pushed to the left ("select * from t1") and used when reading T1, but couldn't be pushed to the VALUES clause  because there's no underlying table.  If we pushed to the left but not to the right, then removed it from the UnionNode's predList--which is the restrictionList of the ProjectRestrictNode above the UnionNode--the rows from the right would remain unqualified and thus we'd return incorrect results (more rows that intended).

> Why are you only dealing with join predicates? It would also be useful to push simple search arguments (i.e. a column compared to a constant), and this case might  be more common than join predicates:

Actually, when I first made the changes described in the document, I pushed any predicate that was a binary relational operator with a column reference on at least one side and a query-invariant value (i.e. constant or parameter) on whichever side was not a column reference (if either).  This covered the case of a column compared to a constant.  All of my changes worked, so from a logical/coding perspective we could indeed do just that.  However, I then put in the join predicate limitation because it seemed to me (based on very brief inspection) that the case of a comparison with a constant was covered by Satheesh's fix for DERBY-649, so I thought it might be extra unnecessary work to continually push/pull those predicates throughout the optimization process.  The following comments re: DERBY-649 made me think I didn't need to worry about one-sided predicates:

<Jeff Lichtman>
> BTW, the business of pushing and pulling predicates during optimization can be
> hard to understand and debug, so maybe it's best to only handle the simple
> cases and do it during preprocessing.

<Satheesh>
The pushing is done before optimization... during preprocessing. [ ... ] You bring up a *great *point about pushing join predicates. I am not implementing this for UnionNode.

And of the course, the "summary" of DERBY-805 itself says "Push join predicates into union and other set operations. DERBY-649 implemented scalar (single table) predicate pushdown. Adding join predicate push down could improve performance significantly."

So given that, I figured the goal for DERBY-805 was to focus on pushing join predicates--and that's what I've done.  One final comment from OptimizerImpl further prompted me lean toward this limitation:

    /*
    ** Pull the predicates at from the optimizable and put
    ** them back in the predicate list.
    **
    ** NOTE: This is a little inefficient because it pulls the
    ** single-table predicates, which are guaranteed to always
    ** be pushed to the same optimizable.  We could make this
    ** leave the single-table predicates where they are.
    */
    pullMe.pullOptPredicates(predicateList);

So it seemed like pushing more single-sided predicates would be adding to the "inefficiency" mentioned here, and since the predicates are (as I understand it) already handled in preprocessing for DERBY-649, I didn't think we'd benefit from pushing them during optimization.  Perhaps I'm missing something somewhere or drawing the wrong conclusion?

> I would prefer to see any type of predicate pushed into a union - even those containing complex expressions. This might be hard to implement, though, as I don't know whether the cloning methods are implemented for the entire ValueNode hierarchy.

Sounds like an "itch" to me :) While it might indeed be nice to push predicates containing complex expressions, that's another enhancement of its own.  I won't be doing that with my DERBY-805 changes.

Thanks again--I can't say that enough--for reading the document.  It's a huge one and I'm grateful for your time and feedback.

> Push join predicates into union and other set operations. DERBY-649 implemented scalar (single table) predicate pushdown. Adding join predicate push down could improve performance significantly.
> --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
>          Key: DERBY-805
>          URL: http://issues.apache.org/jira/browse/DERBY-805
>      Project: Derby
>         Type: Sub-task
>   Components: SQL
>     Versions: 10.1.2.0, 10.2.0.0
>  Environment: generic
>     Reporter: Satheesh Bandaram
>     Assignee: A B
>      Fix For: 10.2.0.0
>  Attachments: DERBY-805.html
>
> Fix for DERBY-649 implemented scalar (single table) predicate push down into UNIONs. While this improves performance for one set of queries, ability to push join-predicates further improves Derby performance by enabling use of indices where possible.
> For example,
> create view V1 as select i, j from T1 union all select i,j from T2; 
> create view V2 as select a,b from T3 union all select a,b from T4; 
> insert into T1 values (1,1), (2,2), (3,3), (4,4), (5,5); 
> For a query like
> select * from V1, V2 where V1.j = V2.b and V1.i =1;
> If the join order choosen is V1,V2, V1 can use index on V1.i (if present) following fix for DERBY-649. But if there is a index on V2.b also, Derby currently can't use that index. By pushing join predicate, Derby would be able to use the index and improve performance. Some of the queries I have seen (not the one shown here...) could improve from 70-120 seconds to about one second.
> Note there is a good comment by Jeff Lichtman about join-predicate push down. I am copying parts of it here for completeness of this report: (Modified)
> If predicate push down is done during optimization, it would be possible to push joins into the union as long as it's in the right place in the join order.
> For example:
> create view v as select * from t1 union all select * from t2;
> select * from v, t3 where v.c1 = t3.c2;
> In this select, if t3 is the outer table then the qualification could be pushed into the union and optimized there, but if t3 is the inner table the qualification can't be pushed into the union.
> If the pushing is done at preprocess time (i.e. before optimization) it is impossible to know whether a join qualification like this can be safely pushed.
> There's a comment in UnionNode.optimizeIt() saying:
> /* RESOLVE - don't try to push predicated through for now */
> This is where I'd expect to see something for pushing predicates into the union during optimization.
> BTW, the business of pushing and pulling predicates during optimization can be hard to understand and debug, so maybe it's best to only handle the simple cases and do it during preprocessing.

-- 
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
   http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
   http://www.atlassian.com/software/jira