/********************************************************************************
*
* File: optimizer.gen
* Title: The optimizer for the relational database system SDB.
* Programmer: Leonidas Fegaras, UTA
* Date: 2/21/97
*
* For more information, read the web page:
*   http://www-cse.uta.edu/~fegaras/cse6331/optgen.html
* 
* The following are the relational algebraic operators
* (indicated as terms) used by SDB:
*
* 1. scan( table_name )
* 2. projection( term, ... list_of_projections )
* 3. select( term, predicate )
* 4. join( term, term, predicate )
* 5. rename( term, range_variable )
*    the relational rename operator (rho)
* 6. union( term, term )
* 
* list_of_projections is a list of named projections of the form
* as(projection,name),... where each projection has the form
* project(table_name,attribute).  Each predicate has either the form
* comparison or the form and(...list_of_comparisons), where each
* comparison has the form cmp(projection,projection) or
* cmp(projection,value), for some comparison operator cmp.
* 
* The query forms produced by sql.y take one of the two forms:
*
* 1. union( query, query )
* 2. sql_select( project( ...list_of_projections ),
*                from( ...list_of_bindings ), 
*                where_predicate, group_by, having_predicate, order_by )
*
* where each binding in the list_of_bindings has the form 
* as(query,range_variable). The mjoin algebraic operator is
* used as an intermediate operator. It represents a multi-join.
*
* The following are the physical plan operators
* (indicated as plans) used by SDB:
* 
* 1. TABLE_SCAN( table_name, range_variable, predicate )
*    implements the SQL query:
*    select * from table_name range_variable where predicate
* 2. INDEX_SCAN( table_name, range_variable, predicate, index_name, sort_order )
*    like TABLE_SCAN, but it uses the index index_name to
*    deliver the tuples order in sort_order
* 3. PROJECTION( plan, ... list_of_projections )
*    implements relational projection
* 4. FILTER( plan, predicate )
*    implements relational selection
* 5. SORT( plan, sort_order )
*    sorts a plan into the sort_order (a list of projections)
* 6. GROUP_BY( plan, ... list_of_projections )
*    groups a plan by the list_of_projections; plan should be
*    ordered by the list_of_projections
* 7. NESTED_LOOP( plan, plan, predicate )
* 8. MERGE_JOIN( plan, plan, predicate, left_sort_order, right_sort_order )
*    merge join requires the left input be sorted by left_sort_order
*    and the right by right_sort_order
* 9. UNION( plan, plan )
* 
* For example, the following SQL query against the COMPANY database:
* 
* select e.fname, e.lname, s.fname, s.lname
*   from employee e, employee s
*  where e.superssn = s.ssn;
* 
* is compiled by sql.y into the following algebraic expression:
* 
* sql_select(project(as(project(e,fname),NONE),
*                    as(project(e,lname),NONE),
*                    as(project(s,fname),NONE),
*                    as(project(s,lname),NONE)),
*            from(as(employee,e),as(employee,s)),
*            eq(project(e,superssn),project(s,ssn)),
*            NONE,
*            true,
*            NONE)
* 
* One algebraic form that you get after the logical rewrite phase is:
* 
* projection(join(rename(scan(employee),e),
*                 rename(scan(employee),s),
*                 eq(project(e,superssn),project(s,ssn))),
*            as(project(e,fname),NONE),
*            as(project(e,lname),NONE),
*            as(project(s,fname),NONE),
*            as(project(s,lname),NONE))
* 
* The best plan found after the physical rewrite phase is:
* 
* PROJECTION(MERGE_JOIN(SORT(TABLE_SCAN(employee,e,true),
*                            order(project(e,superssn))),
*                       INDEX_SCAN(employee,s,true,Primary_idx,
*                                  order(project(s,ssn))),
*                       eq(project(e,superssn),project(s,ssn)),
*                       order(project(e,superssn)),
*                       order(project(s,ssn))),
*            as(project(e,fname),NONE),
*            as(project(e,lname),NONE),
*            as(project(s,fname),NONE),
*            as(project(s,lname),NONE))
* 
* That is, the e employee table was scanned using TABLE_SCAN and then
* sorted over superssn, while the s employee table didn't have to be
* sorted since the output of the INDEX_SCAN is already sorted by ssn.
* As another example, the query:
* 
*   select pnumber, pname, count(*)
*     from project, works_on
*    where pnumber = pno
* group by pnumber, pname
*   having count(*) > 2;
* 
* is compiled by sql.y into:
* 
* sql_select(project(as(project(project,pnumber),NONE),
*                    as(project(project,pname),NONE),
*                    as(count(ALL),NONE)),
*            from(as(project,project),as(works_on,works_on)),
*            eq(project(project,pnumber),project(works_on,pno)),
*            columns(project(project,pnumber),project(project,pname)),
*            gt(count(ALL),2),
*            NONE)
* 
* where the 6th line is the GROUP BY and the 7th line is the HAVING part
* of the query. The best plan is:
* 
* PROJECTION(
*    FILTER(
*       GROUP_BY(
*          NESTED_LOOP(
*             INDEX_SCAN(project,project,true,Primary_idx,
*                        order(project(project,pnumber))),
*             TABLE_SCAN(works_on,works_on,true),
*             eq(project(project,pnumber),project(works_on,pno))),
*          project(project,pnumber),
*          project(project,pname)),
*       gt(count(ALL),2)),
*    as(project(project,pnumber),NONE),
*    as(project(project,pname),NONE),
*    as(count(ALL),NONE))
*
* The GROUP_BY operator requires that its input be sorted by both pnumber
* and pno. This order can be delivered by using an index scan.
* Recall that the order of the nested loop output is the order of the
* outer table (its left input).
*
*
*********************************************************************************/

#include <math.h>
#include "typecheck.h"
#include "evaluation.h"


/* DATABASE holds both the database schema and the database state */
extern database* DATABASE;


/* negated_comparisons binds boolean comparisons into their negated forms */
string ngv[][2] = {{"eq","neq"},{"neq","eq"},{"lt","geq"},
		   {"leq","gt"},{"gt","leq"},{"geq","lt"}};

binding<String>* make_negated ( string v[][2] ) {
  binding<String>* res = new binding<String>;
  for(short i = sizeof(v); i>=0; i--) res = res->extend(&v[i][0],&v[i][1]);
  return res;
};

static binding<String>* negated_comparisons = make_negated(ngv);


/* all_algebraic holds the names of all algebraic operators */
static list<Expr>* all_algebraic
   = Nil->cons(#<mjoin>)->cons(#<select>)->cons(#<join>)->cons(#<projection>)
	->cons(#<union>)->cons(#<rename>)->cons(#<sort>)->cons(#<group_by>);

/* all_plans holds the names of all physical plans */
static list<Expr>* all_plans
   = Nil->cons(#<TABLE_SCAN>)->cons(#<INDEX_SCAN>)->cons(#<SORT>)->cons(#<NESTED_LOOP>)
        ->cons(#<MERGE_JOIN>)->cons(#<PROJECTION>)->cons(#<FILTER>)
	->cons(#<UNION>)->cons(#<rename>)->cons(#<GROUP_BY>);


/* retrieves the projection names from the list_of_projections tl */
list<Expr>* tables (list<Expr>* tl) {
  list<Expr>* res = Nil;
  for(list<Expr>* r = tl; r->consp(); r=r->tl)
     #case r->hd
     |  as(`e,`table) => res = res->cons(table);
     #end;
  return res;
};


/* for each plan or algebraic expression e, all_tables(e) collects
*  all table names that appear in the leaves of e */
list<Expr>* all_tables (Expr e) {
  list<Expr>* res = Nil;
  #case e
  |  rename(`u,`table) => res = res->cons(table);
  |  TABLE_SCAN(_,`table,...a) => res = res->cons(table);
  |  INDEX_SCAN(_,`table,...a) => res = res->cons(table);
  |  `f(...r) => if (member(f,all_plans) || member(f,all_algebraic))
		    for(list<Expr>* s = r; s->consp(); s=s->tl)
		       res = res->append(all_tables(s->hd));
  #end;
  return res;
};


/*  returns true if pred refers to a range variable in tables */
bool refers_to ( Expr pred, list<Expr>* tables ) {
  #case pred
  |  project(`x,`a) => return refers_to(x,tables);
  |  `f(...r) => for(; r->consp(); r=r->tl)
		    if (refers_to(r->hd,tables))
		       return true;
  |  `v => if (member(v,tables)) return true;
  #end;
  return false;
};


/* true if x is a plan */
bool is_plan ( Expr x ) {
  #case x
  |  `f(...r) => return member(f,all_plans);
  |  _ => return false;
  #end;
};


/* negates a boolean predicate e using De Morgan Laws */
Expr negate (Expr e) {
  #case e
  | or(`x,`y) => { Expr nx = negate(x);
		   Expr ny = negate(y);
		   return #<and(`nx,`ny)>;
		 };
  | and(`x,`y) => { Expr nx = negate(x);
		    Expr ny = negate(y);
		    return #<or(`nx,`ny)>;
		  };
  | not(`x) => return x;
  | `f(`x,`y) => { Expr nf = variable(negated_comparisons->find(f->name()));
		   return #<`nf(`x,`y)>;
		 };
  | `x => return #<not(`x)>;
  #end;
};


/* puts the boolean predicate e into a disjunctive normal form;
*  the result is a disjunction of conjunctions represented by a list of lists   */
list<list<Expr>*>* disjunctive_form (Expr e) {
  #case e
  | or(`x,`y)
	=> return disjunctive_form(x)->append(disjunctive_form(y));
  | and(`x,`y)
	=> { list<list<Expr>*>* res = new list<list<Expr>*>;
	     for(list<list<Expr>*>* r = disjunctive_form(x); r->consp(); r=r->tl)
		for(list<list<Expr>*>* s = disjunctive_form(y); s->consp(); s=s->tl)
		   res = res->cons(r->hd->append(s->hd));
	     return res;
	   };
  | not(`x) => if (x->variablep())
		  return (new list<list<Expr>*>)->cons(Nil->cons(e));
		  else return disjunctive_form(negate(x));
  | `x => return (new list<list<Expr>*>)->cons(Nil->cons(x));
  #end;
};


/* constructs the disjunctive normal form of the predicate e */
Expr normalize_predicate (Expr e) {
  list<Expr>* res = Nil;
  for(list<list<Expr>*>* r = disjunctive_form(e); r->consp(); r=r->tl)
  { list<Expr>* params = r->hd;
    if (params->nullp()) ;
       else if (params->tl->nullp()) res = res->cons(params->hd);
            else res = res->cons(#<and(...params)>);
  };
  if (res->nullp()) return #<true>;
     else if (res->tl->nullp()) return res->hd;
          else return #<or(...res)>;
};


/* constructs the conjunction and(x,y) for predicates x and y and simplify */
Expr combine_predicates ( Expr x, Expr y ) {
  #case x
  |  true => #case y 
	     |  true => return #<true>;
	     |  and(...ys) => return #<and(...ys)>;
	     |  _ => return y;
	     #end;
  |  and(...xs) => #case y
		   |  and(...ys) => return #<and(...(xs->append(ys)))>;
		   |  _ => return #<and(...(xs->cons(y)))>;
		   #end;
  |  _ => #case y
	  |  and(...ys) => return #<and(...(ys->cons(x)))>;
	  |  _ => return #<and(`x,`y)>;
	  #end;
  #end;
};


/* constructs the conjunction of the list of predicates preds */
Expr make_conjunction ( list<Expr>* preds ) {
  if (preds->nullp()) return #<true>;
     else if (preds->tl->nullp()) return preds->hd;
          else return #<and(...preds)>;
};


/* the inverse of make_conjunction */
list<Expr>* decompose_conjunction ( Expr pred ) {
  #case pred
  |  true => return Nil;
  |  and(...ps) => return ps;
  |  `x => return Nil->cons(x);
  #end;
};


/* true if there is an equality predicate that binds an attribute of a table
*  in left_tables with an attribute of a table in right_tables.
*  This will imply that the join between these tables will be an equijoin */
bool equijoinp ( Expr pred, list<Expr>* left_tables, list<Expr>* right_tables ) {
  for(list<Expr>* r = decompose_conjunction(pred); r->consp(); r=r->tl)
     #case r->hd
     |  eq(project(`x,`a),project(`y,`b))
	   => if (member(x,left_tables) && member(y,right_tables)) return true;
	      if (member(y,left_tables) && member(x,right_tables)) return true;
     #end;
  return false;
};


/* splitls the predicate pred into three parts: one part bound to left will
*  hold all predicates that refer to the left_tables exclusively; another
*  part bound to right will hold all predicates that refer to the right_tables
*  exclusively; the result of the function will hold all predicates that refer
*  to both left and right tables */
Expr split_predicate ( Expr pred, list<Expr>* left_tables, list<Expr>* right_tables,
		       Expr &left, Expr &right ) {
  list<Expr>* lefts = Nil;
  list<Expr>* rights = Nil;
  list<Expr>* rests = Nil;
  for(list<Expr>* r = decompose_conjunction(pred); r->consp(); r=r->tl)
     #case r->hd
     |  `f(project(`t1,`a1),project(`t2,`a2))
		=> if (member(t1,left_tables) && member(t2,left_tables))
		      lefts = lefts->cons(r->hd);
		   else if (member(t1,right_tables) && member(t2,right_tables))
		      rights = rights->cons(r->hd);
		   else rests = rests->cons(r->hd);
     |  `f(project(`t,`a),`cnst)
		=> if (member(t,left_tables)) lefts = lefts->cons(r->hd);
		   else if (member(t,right_tables)) rights = rights->cons(r->hd);
		   else rests = rests->cons(r->hd);
     |  `f(`cnst,project(`t,`a))
		=> if (member(t,left_tables)) lefts = lefts->cons(r->hd);
		   else if (member(t,right_tables)) rights = rights->cons(r->hd);
		   else rests = rests->cons(r->hd);
     |  `x => rests = rests->cons(x);
     #end;
     left = make_conjunction(lefts);
     right = make_conjunction(rights);
     return make_conjunction(rests);
};


/* chooses an equality predicate from pred that binds an attribute of a table
*  in left_tables with an attribute of a table in right_tables (if there is one).
*  The left part of this equality determines the order in which the left input
*  of a merge join be sorted while the right part determines the order of the right input */
Expr required_order ( Expr pred, list<Expr>* left_tables, list<Expr>* right_tables ) {
  list<Expr>* ords = Nil;
  for(list<Expr>* r=decompose_conjunction(pred); r->consp(); r=r->tl)
     #case r->hd
     |  eq(project(`x,`a),project(`y,`b))
	   => if (member(x,left_tables) && member(y,right_tables))
	         ords=ords->cons(#<project(`x,`a)>);
	      if (member(y,left_tables) && member(x,right_tables))
		 ords=ords->cons(#<project(`y,`b)>);
     #end;
  return #<order(...ords)>;
};


/* true if the expected order is at least as strong as the computed order
*  expected_order = computed_order plus sometrhing */
bool subsumes ( Expr computed_order, Expr expected_order ) {
  #case computed_order
  |  order(...co) => #case expected_order
		     |  order(...eo)
			 => list<Expr>* s = eo;
			    for(list<Expr>* r = co; r->consp(); r=r->tl, s=s->tl)
			       if (s->nullp()) return false;
			       else if (!r->hd->eq(s->hd)) return false;
			    return true;
		     |  _ => return false;
		     #end;
  |  _ => return false;
  #end;
};


/* Retrieves statistics and indexes from the meta-database */
int table_cardinality ( Expr table ) {
  return DATABASE->find_relation(table->name())->cardinality;
};

int table_size ( Expr table ) {
  return DATABASE->find_relation(table->name())->size;
};

Expr find_index ( Expr table, Expr order ) {
  return DATABASE->find_relation(table->name())->find_index(order);
};


/* selectivity estimation; needs lots of work */
float selectivity ( Expr pred ) {
  float sel = 1.0;
  for(list<Expr>* r = decompose_conjunction(pred); r->consp(); r=r->tl)
     #case r->hd
     |  eq(project(`x,`a),`v) => sel = sel/10.0;
     |  eq(`v,project(`x,`a)) => sel = sel/10.0;
     |  _ => sel = sel/100.0;
     #end;
  return sel;
};


/* the cost of accessing an index (B-tree) */
float B_tree_cost ( int data_blocks ) {
  if (data_blocks <= 1) return 1.0;
  return ceil(log(data_blocks));
};


/* the cost of accessing an index to satisfy a required order io and a predicate pred */
float index_access_cost ( Expr table, Expr pred, list<Expr>* io ) {
  float size = table_size(table);
  for(list<Expr>* r = decompose_conjunction(pred); r->consp(); r=r->tl)
     #case r->hd
     |  eq(project(`x,`a),`v) => if (member(#<project(`x,`a)>,io)) size = size/10.0;
     |  eq(`v,project(`x,`a)) => if (member(#<project(`x,`a)>,io)) size = size/10.0;
     |  `f(project(`x,`a),`v) => if (member(#<project(`x,`a)>,io)) size = size/2.0;
     |  `f(`v,project(`x,`a)) => if (member(#<project(`x,`a)>,io)) size = size/2.0;
     #end;
  return size + B_tree_cost(table_size(table));
};


/* returns all indexes attached to table ranged by the range variable name */
list<Expr>* all_table_indexes ( Expr table, Expr name ) {
  binding<Expr>* indexes = DATABASE->find_relation(table->name())->indexes;
  list<Expr>* res = Nil;
  for(Names n = indexes->names(); n->consp(); n=n->tl)
  {  list<Expr>* idx = Nil;
     for(list<Expr>* r = indexes->find(n->hd)->arguments()->reverse();
	 r->consp(); r=r->tl)
       idx = idx->cons(#<project(`name,`(r->hd))>);
     res = res->cons(#<index(`(variable(n->hd)),order(...idx))>);
  };
  return res;
};


%{

/* set this to true if you want to get a tracing of the rule system; lots of output */
#define trace_rules false

/* set this to true if you want to print the results of every optimization module */
#define trace_stages true


%trace { 0 }


/* the only inherited attribute is the expected order */
%inherited order

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


/******************** LOGICAL RULES ***********************************/
%logical

/* Rule 1: translate the sql projection first ...	*/
sql_select(project(...ps),`from,`where,`group,`having,`order)
  => projection(sql_select(ALL,`from,`where,`group,`having,`order),
		...ps);

/* Rule 2: ... then translate the ORDER BY ...		*/
sql_select(ALL,`from,`where,`group,`having,`columns(...clist))
  => sort(sql_select(ALL,`from,`where,`group,`having,NONE),
	  order(...clist));

/* Rule 3: ... then translate GROUP BY and HAVING;		*/
/* put the HAVING predicate in disjunctive normal form ...	*/
sql_select(ALL,`from,`where,columns(...glist),`having,NONE)
  => let Expr new_having_predicate = normalize_predicate(having)
     in select(group_by(sql_select(ALL,`from,`where,NONE,true,NONE),
			groups(...glist)),
	       `new_having_predicate);

/* Rule 4: ... finally make the sql_select a multi-join;	*/
/* put the predicate in disjunctive normal form ...		*/
sql_select(ALL,from(...ts),`where,NONE,true,NONE)
  => let Expr new_predicate = normalize_predicate(where)
     in mjoin(from(...ts),`new_predicate);

/* Rule 5: bottom case of Rule 6	*/
mjoin(`from,or(`pred))
  => mjoin(`from,`pred);

/* Rule 6: disjunction is captured by relational union */
mjoin(`from,or(`pred,...ps))
  => union(mjoin(`from,`pred),
           mjoin(`from,or(...ps)));

/* Rule 7: bottom case: if the mjoin is a join of one table, and the	*/
/* predicate is true, make it a table scan				*/
mjoin(from(as(`e,`table)),true)
  => let Expr ne = (e->variablep()) ? #<scan(`e)> : e
     in rename(`ne,`table);

/* Rule 8: bottom case: if the mjoin is a join of one table, make it a selection */
mjoin(from(as(`e,`table)),`pred)
  => let Expr ne = (e->variablep()) ? #<scan(`e)> : e
     in select(rename(`ne,`table),`pred);

/* Rule 9: ... otherwise create a binary join between the first table and	*/
/* the mjoin of the rest of the tables (to be rewritten latter); 		*/
/* split the predicate and promote the pieces to the join inputs		*/
mjoin(from(as(`e,`table),...ts),`pred)
  => let Expr left = #<true>,
	 Expr right = #<true>,
	 Expr rest = split_predicate(pred,Nil->cons(table),tables(ts),left,right),
	 Expr ne = (e->variablep()) ? #<scan(`e)> : e,
	 Expr inner = (left->eq(#<true>)) ? #<rename(`ne,`table)>
                                          : #<select(rename(`ne,`table),`left)>
     in join(`inner,mjoin(from(...ts),`right),`rest);


/* -------------------- PERMUTATION RULES ---------------------------------- */
%logical

/* Rule 10: eliminate trivial selections */
select(`e,true)
  => `e;

/* Rule 11: fuse cascaded selections */
select(select(`e,`p1),`p2)
  => let Expr pred = combine_predicates(p1,p2)
     in select(`e,`pred);

select(join(`x,`y,`p1),`p2)
  => let Expr pred = combine_predicates(p1,p2)
     in join(`x,`y,`pred);

/* Rule 13: associativity rule */
dontdoityet(join(`x,`y,`pxy),`z,`pxyz)
  => let Expr pred = combine_predicates(pxy,pxyz),
	Expr px = #<true>,
	Expr pyz = #<true>,
	Expr new_pxyz = split_predicate(pred,all_tables(x),
			    all_tables(y)->append(all_tables(z)),px,pyz),
	Expr new_x = (px->eq(#<true>)) ? x : #<select(`px,`x)>
    in join(`new_x,join(`y,`z,`pyz),`new_pxyz);

/* Rule 12: commutativity rule */
join(`x,`y,`pred)
  = join(`y,`x, `pred);


/* -------------------- PHYSICAL RULES -------------------------------- */

%physical

/* Rule 14: convert scan into TABLE_SCAN */
{ order=order(); }
rename(scan(`table),`name)
  = TABLE_SCAN(`table,`name,true)
    : { size = table_cardinality(table);
	cost = table_size(table);
	order = #<order()>; };

/* Rule 15: if an index delivers the requested order, use this index */
{ order=order(`o,...os); }
rename(scan(`table),`name)
  = #case find_index(table,#<order(`o,...os)>)
    |  index(`idx,order(...io))
	=> INDEX_SCAN(`table,`name,true,`idx,order(...io))
	   : { size = table_cardinality(table);
	       cost = table_size(table);
	       order = #<order(...io)>; };
    #end;

/* Rule 16: selection can be done during TABLE_SCAN */
{ order=order(); }
select(rename(scan(`table),`name),`pred)
  = TABLE_SCAN(`table,`name,`pred)
     : { size = int(table_cardinality(table)*selectivity(pred));
	 cost = table_size(table);
	 order = #<order()>; };

/* Rule 17: selection can be done during INDEX_SCAN */
{ order=order(`o,...os); }
select(rename(scan(`table),`name),`pred)
  = #case find_index(table,#<order(`o,...os)>)
    |  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;

/* Rule 18: if requested order is empty then use any index; so here we use ALL indexes */
{ 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;

/* Rule 19: all selections left out from rules 16 & 17 become FILTERs */
{ order=order(); }
select(`e,`pred)
   : is_plan(e)
   = FILTER(`e,`pred)
     : { size = int(^e.size*selectivity(pred));
	 cost = ^e.cost+^e.size;
	 order = ^e.order; };

/* Rule 20: rename should remain rename */
{ order=order(); }
rename(`e,`name)
   : is_plan(e)
   = rename(`e,`name)
     : { size = ^e.size;
	 cost = ^e.cost;
	 order = ^e.order; };

/* Rule 21: if a non-empty order is requested then SORT the plan x; of course now	*/
/* the required order for x should be empty so this rule is applied only once		*/
{ order=order(`o,...os); }
(`x<-{ order=order(); })
  : is_plan(x) && !subsumes(#<order(`o,...os)>,^x.order)
  = SORT(`x,order(`o,...os))
    : { size = ^x.size;
	cost = ^x.cost+(^x.size*B_tree_cost(^x.size));
	order =  #<order(`o,...os)>; };

/* Rule 22: join to nested loop; the required order propagates to the left input only */
{ order=`ord; }
join( `x<-{ order=`ord; },
      `y<-{ order=order(); },
      `pred )
   : !refers_to(ord,all_tables(y))
   = NESTED_LOOP(`x,`y,`pred)
     : { size = int(^x.size*^y.size*selectivity(pred));
	 cost = ^x.cost+^y.cost+(^x.size*^y.size);
	 order = ^x.order; };

/* Rule 23: convert join into merge join; both inputs are required to be ordered */
{ order=`l; }
join( `x<-{ order=`(required_order(pred,all_tables(x),all_tables(y))); },
      `y<-{ order=`(required_order(pred,all_tables(y),all_tables(x))); },
      `pred )
   : equijoinp(pred,all_tables(x),all_tables(y))
     && subsumes(l,^x.order)
   = MERGE_JOIN(`x,`y,`pred,
		`(required_order(pred,all_tables(x),all_tables(y))),
		`(required_order(pred,all_tables(y),all_tables(x))))
        : { size = int((^x.size+^y.size)*selectivity(pred));
	    cost = ^x.cost+^y.cost+(^x.size+^y.size);
	    order = ^x.order; };

/* Rule 24: eliminate duplicate sorts */
{ order=order(); }
sort( `e<-{ order=`ord; }, `ord )
   = `e
     : { size = ^e.size;
	 cost = ^e.cost;
	 order = ^e.order; };

/* Rule 25: GROUP BY needs its input ordered */
{ order=order(); }
group_by( `e<-{ order=order(...glist); },
          groups(...glist) )
   = GROUP_BY(`e,...glist)
     : { size = ^e.size;
	 cost = ^e.cost+^e.size;
	 order = ^e.order; };

/* Rule 26 */
{ order=order(); }
projection(`e,...ps)
   = PROJECTION(`e,...ps)
     : { size = ^e.size;
	 cost = ^e.cost+^e.size;
	 order = ^e.order; };

/* Rule 27 */
{ order=order(); }
union(`x,`y)
  = UNION(`x,`y)
    : { size = ^x.size+^y.size;
	cost = ^x.cost+^y.cost+^x.size+^y.size;
	order = #<order()>; };

%}

/*--------------------------------------------------------------------------------*/


bool better_plan ( plan* x, plan* y ) {
  return x->attributes.cost < y->attributes.cost;
};


/* returns the 10 best plans from a list of plans */
list<plan*>* ten_best_plans ( list<plan*>* plans ) {
  list<plan*>* res = new list<plan*>;
  short i = 0;
  for(list<plan*>* r = plans->sort(better_plan); i<10 && r->consp(); r=r->tl, i++)
     res = res->cons(r->hd);
  return res;
};


/* optimize an SQL query */
Expr optimize_query (Expr query) {
  optimizer_init();
  /* initial inherited attribute */
  inherited init;
  init.order = #<order()>;
  /* set this to false if you want to generate algebraic expressions only */
  bool generate_physical_plans = true;
  /* best_plans is a pointer to a function that filters out plans during the beam search */
  best_plans = &ten_best_plans;
  list<plan*>* plans = rewrite(query,init,generate_physical_plans);
  return ten_best_plans(plans)->hd->expression;
};
