uwescience/raco — pull request #317 by dhalperi (2014-09-06 15:38:32+00:00)
Title: Speedup handling of very long queries

As we have seen, some queries take quite a while to parse. I made a trivial example (see examples/chained.myl) which, on `master`, takes about 1 second to get the physical plan: ~0.58 seconds to get the parsed plan, the rest to optimize.

I found three major attributions of time:

* time spent in `copy.deepcopy` in the cfg
* time spent in repeated calls to compute_liveness
* time spent in `op.scheme()`, which in retrospect is obvious -- it essentially walks the entire graph to construct the plan!

Some ways to improve the parser/optimizer performance on this query:
- expand deepcopy with a simple literal impl (see a109628). Turns out copying a dict/set explicitly is somehow much faster than calling deepcopy directly.
- reduce the number of rounds in the inlining code by parsing back to front instead of front to back. I have some basic reasoning in the commit message, but I'm sure there are some places it fails. Maybe when we have a LOT of branching early back-to-front will increase the # of calls, and there is probably a better rewrite I should think about.
- when inlining, only deepcopy the subplan we're inlining the second+ time we inline it. When we inline it once, we can just reuse it.
- make it easier to avoid unnecessary scheme computations in optimization rules, and do so. It turns out we compute scheme whenever we convert expressions to unnamed, but in practice they are likely to have already been unnamed by our own previous work.

The upshot of this work is that for the sample query the parse + optimize time on my laptop (`time scripts/myrial examples/chained.myl`) goes from about 1s to about 0.37s.

(I know that performance optimization is not a goal and simpler is better. But this makes some programs that we did not use to be able to submit, e.g. appengine might time out parsing + issuing them, work much better on the website.)