db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Knut Anders Hatlen (JIRA)" <j...@apache.org>
Subject [jira] Updated: (DERBY-4421) Allow Visitors to process the nodes bottom-up
Date Mon, 26 Oct 2009 13:46:59 GMT

     [ https://issues.apache.org/jira/browse/DERBY-4421?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Knut Anders Hatlen updated DERBY-4421:
--------------------------------------

    Attachment: d4421-1a.stat
                d4421-1a.diff

Attached is a patch with the following code changes:

1) Adds a method visitChildrenFirst() to the Visitor interface and implements it as "return
false" for all existing visitor classes.

2) QueryTreeNode.accept() checks visitChildrenFirst() to see if visit() should be called on
the parent or the children first.

3) Makes QueryTreeNode.accept() final to prevent sub-classes from overriding it, as classes
that override it would need to duplicate the logic. Duplicated code tends to be more difficult
to maintain and more error-prone and should be avoided.

4) Adds an empty acceptChildren() method to QueryTreeNode. This method is called by QueryTreeNode.accept(),
and sub-classes should now override this method instead of accept().

5) Replaces all accept() overrides in sub-classes of QueryTreeNode with acceptChildren().

Most of these steps were just mechanical transformations. There's one exception from the rule:
FromList.accept() was removed instead of replaced with an acceptChildren() method. That's
because the old accept() method did the exact same thing as the parent's (QueryTreeNodeVector)
accept() method did. This worked, and didn't cause nodes to be visited twice, because FromList.accept()
didn't follow the established pattern and call super.accept(). There's however no reason to
implement accept() or acceptChildren() in FromList, so I found it more consistent to remove
it.

The patch removes more code than it adds (215 lines added, 359 lines removed), so I think
it's a good clean-up. Since the checking of Visitor.stopTraversal() has been centralized to
QueryTreeNode.accept(), we could also remove the now redundant calls to stopTraversal() in
all the acceptChildren() methods. But I'd prefer to do that in a follow-up patch in order
to keep this patch smaller and easier to understand.

The regression tests ran cleanly with an earlier version of the patch. The patch had to be
refreshed because DERBY-3634 has added one new visitor and two new accept() methods after
that. Rerunning regression tests now.

I also tested the patch together with the patch from DERBY-4416. If the visitor is told to
traverse the tree bottom-up, the patch is now able to optimize away an WHERE clause that contains
(1=1)=(1=1), so that no project-restrict result set is generated for this statement:

  SELECT * FROM T WHERE (1=1)=(1=1)

Without this patch, there would be a project-restrict result set on top of the table scan
with a (TRUE=TRUE) restriction.

> Allow Visitors to process the nodes bottom-up
> ---------------------------------------------
>
>                 Key: DERBY-4421
>                 URL: https://issues.apache.org/jira/browse/DERBY-4421
>             Project: Derby
>          Issue Type: Improvement
>          Components: SQL
>    Affects Versions: 10.6.0.0
>            Reporter: Knut Anders Hatlen
>            Assignee: Knut Anders Hatlen
>            Priority: Minor
>         Attachments: d4421-1a.diff, d4421-1a.stat
>
>
> Currently, QueryTreeNode.accept() walks the tree top-down, always calling
> visit() on the parent before it calls visit() on the children. Although this
> is fine in most cases, there are use cases where visiting the nodes
> bottom-up would be better. One example is mentioned in DERBY-4416. The
> visitor posted there looks for binary comparison operators and checks
> whether both operands are constants. If they are, the operator is replaced
> with a boolean constant.
> Take this expression as an example: (1<2)=(2>1)
> The query tree looks like this:
>        =
>      /   \
>     /     \
>    <       >
>   / \     / \
>  /   \   /   \
> 1     2 2     1
> If we walk the tree top-down with the said visitor, the = node doesn't have
> constant operands when it's visited. The < and > operators do have constant
> operands, and they're both replaced with constant TRUE. This means the
> expression (1<2)=(2>1) is rewritten to TRUE=TRUE, and that's how far the
> transformation goes.
> If the tree had been processed bottom-up, we would start with the < and >
> operators, and again replace them with TRUE. The query tree would therefore
> have been transformed to this intermediate form when the = operator was
> visited:
>        =
>      /   \
>     /     \
>   TRUE   TRUE
> This is the same as the end result when visiting top-down, but now the =
> operator hasn't been visited yet. Since both the operands of the = operator
> are constants, the visitor will perform yet another transformation so the
> tree is simplified further and ends up as:
>     TRUE

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


Mime
View raw message