uwescience / raco

Compilation and rule-based optimization framework for relational algebra. Raco is the language, optimization, and query translation layer for the Myria project.
Other
72 stars 19 forks source link

Operator.preorder() seems broken #547

Closed senderista closed 7 years ago

senderista commented 7 years ago

The definition of Operator.preorder() at https://github.com/uwescience/raco/blob/master/raco/algebra.py#L92 seems wrong, since the recursion uses postorder():

    def preorder(self, f):
        """Preorder traversal, applying a function to each operator.  The
        function returns an iterator"""
        for x in f(self):
            yield x
        for c in self.children():
            for x in c.postorder(f):
                yield x

Changing postorder() to preorder() in the above code breaks an existing test though (https://github.com/uwescience/raco/blob/cf26abec675cbdc62008bd075bacb5e0d177247d/c_test_environment/grappalang_myrial_tests.py#L200). The problem seems to be that the NumTuplesPropagation rule (https://github.com/uwescience/raco/blob/cf26abec675cbdc62008bd075bacb5e0d177247d/raco/rules.py#L65) is making invalid assumptions, but I don't have time to investigate this further.

senderista commented 7 years ago

I changed preorder() to postorder() in the NumTuplesPropagation rule and that fixed tests, so I'm assuming that this fix is correct and the rule should have been using postorder() to begin with (that seems reasonable since StoreTemp needs to be visited before its corresponding ScanTemp and the StoreTemp is lower in the tree).

fixed by dec7afb