OPTL Rule Syntax

A program in OPTL has the following structure in BNF:

C++code
[ "%{"
  C++code
  "%inherited" name { "," name }
  "%synthesized" "{" { name "=" C++type ";" } "}" "=" C++code
  { "%logical" { lrule } }
  "%physical" { prule }
"%}"
C++code ]

1. The specification of the inherited attributes: this is the line starting with %inherited and followed by the list of synthesized attributes separated by comma. In the SQL optimizer we have only one inherited attribute, namely the expected order:

   %inherited order
   

2. The specification of the synthesized attributes: this is the line starting with %synthesized and followed by a C++ tuple type that defines the synthesized attributes along with an initialization value for the attributes. For the SQL optimizer we have three synthesized attributes: the size in blocks of the output relation, the plan cost, and the plan order:

   %synthesized { int size; float cost; Expr order; }
              = { 0, 10000.0, #<order()> }
   

3. We may have zero or more modules with logical rules (started with the keyword %logical) and only one module for physical rules (started with the keyword %physical). The optimizer tries the logical rules first in the order they are specified, and then it tries the physical rules.

lrule ::=   [ inherited ] pattern [ guard ] "=>" body
          | [ inherited ] pattern [ guard ] "=" body
guard ::= ":" C++code
inherited ::= "{" { name "=" pattern ";" } "}"
body ::=    expr ";"
          | "let" name "=" C++code { "," name "=" C++code } "in" body
          | "#case" C++code { "|" pattern "=>" body } "#end" ";"
          | "#forall" name "in" C++code "do" body "#end" ";"

There are two types of rules: reductions (indicated by => in the rule) and rewrites (indicated by = in the rule). If there are many rules applicable to a term, then the first reduction rule is applied and the rest rules are ignored; if there is no applicable reduction rule, then all applicable rewrite rules are applied to this term and the results of all rules are accumulated. This process repeats for a term and its subterms until no rule is applicable. The rewrite rule type must be selected with caution, as it may yield an inefficient search. In addition, there is a danger of falling into an infinite loop, even though no rule can be applied twice to the same term. One example of such a case is the rule `x = f(`x), which generates the infinite sequence f(a), f(f(a)), f(f(f(a))), ... for some term a. For example, the following reduction combines two selects into one select. The predicate of the new select is the conjunction of the two selection predicates (derived by the support function combine_predicates):

select(select(`e,`p1),`p2)
  => let pred = combine_predicates(p1,p2)
     in select(`e,`pred);

prule ::=   [ inherited ] pattern [ guard ] "=" body
body ::=    expr [ synthesized ] ";"
          | "let" name "=" C++code { "," name "=" C++code } "in" body
          | "#case" C++code { "|" pattern "=>" body } "#end" ";"
          | "#forall" name "in" C++code "do" body "#end" ";"
synthesized ::= ":"  "{" { name "=" C++code ";" } "}"

There is also support for memoization. When a term x, associated with inherited attributes IA, is transformed into a list of expressions [x1,...,xn] (these are physical plans because the rewrite is complete) with their synthesized attributes [SA1,...,SAn], then the tuple (x,IA,[(x1,SA1),...,(xn,SAn)]) is stored in a system-provided memoization table (a hash table). Therefore, rewriting a term x with IA involves searching this table to test if x and IA are already memoized. If they are, the resulting rewrite is retrieved from the table; if not, the result is calculated by applying the rewrite rules.

As an example of a physical rule, consider the following:

{ order=order(); }
select(rename(scan(`table),`name),`pred)
  = #forall r in all_table_indexes(table,name) do
       #case r
       |  index(`idx,order(...io))
	     => INDEX_SCAN(`table,`name,`pred,`idx,order(...io))
	        : { size = int(table_cardinality(table)*selectivity(pred));
	            cost = index_access_cost(table,pred,io);
		    order = #<order(...io)>; };
       #end;
    #end;

For each OPTL specification file, OPTGEN generates an optimizer. The interface of this optimizer is the function rewrite:

list<plan*>* rewrite ( Expr e, inherited ia, plan* (best_plan)(list<plan*>*), bool generate_plans );

class plan {
public:
  Expr expression;
  synthesized attributes;
};