Changing the Rules: Transformations for Rule-Based Optimizers
Mitch Cherniack (Brown University)
Stan Zdonik (Brown University)
Rule-based optimizers are extensible because they consist of
modifiable sets of rules. For modification to be straightforward, rules
must be easily reasoned about (i.e., understood and verified).
At the same time, rules must be expressive and efficient (to fire) for
rule-based optimizers to be
practical. Production-style rules (as in [PHH92])
are expressed with code and are hard to reason about. Pure rewrite rules
(as in [BG92]) lack code, but cannot atomically express complex transformations
(e.g., normalizations). Some systems allow rules to be grouped,
but sacrifice efficiency by providing limited control over their firing.
Therefore, none of these approaches succeeds in making rules expressive, efficient
and understandable.
We propose a language (COKO) for expressing an alternative form of input to
a rule-based optimizer. A COKO transformation consists of a set of declarative
(KOLA) rewrite rules and a
(firing) algorithm that specifies their firing. It is
straightforward to reason about COKO transformations because all query modification
is expressed with declarative rewrite rules. Firing
is specified algorithmically with an expressive language that provides
direct control over how query representations are
traversed, and under what conditions rules are fired.
Therefore, COKO achieves a delicate balance of
understandability, efficiency and expressivity.