# Examples of OQL Query Optimization

The OQL query:

    select struct( E: e.name, D: e.dept.name )
    from e in Employees;

is translated into the following algebraic form:

    reduce(bag,
           join(bag,
                get(bag,Employees,e,and()),
                get(bag,Departments,x,and()),
                and(eq(OID(project(e,dept)),OID(x))),
                none),
           y,
           struct(bind(E,project(e,name)),bind(D,project(x,name))),
           and())

i.e., the path expression `e.dept.name` becomes a pointer join.

The OQL query:

    sum( select e.age
         from e in Employees );

is translated into the following algebraic form:

    reduce(sum,get(sum,Employees,e,and()),x,project(e,age),and())

i.e., aggregates and quantification are done using reductions.

The OQL query:

    flatten(select e.children from e in Employees);

is translated into the following algebraic form:

    reduce(set,
           unnest(set,
                  get(set,Employees,e,and()),
                  x,
                  project(e,children),
                  and(),
                  false),
           y,
           x,
           and())

This is an example of program fusion (`flatten` was fused with the select statement).

The OQL query:

    select distinct struct( D: d.name,
    			E: ( select e.name
    			     from e in Employees
    			    where e.dept = d ) )
    from d in Departments;

is translated into the following algebraic form:

    reduce(set,
           nest(bag,
                join(bag,
                     get(bag,Employees,e,and()),
                     get(set,Departments,d,and()),
                     and(eq(project(e,dept),d)),
                     right),
                x,
                project(e,name),
                vars(d),
                vars(),
                and()),
           y,
           struct(bind(D,project(d,name)),bind(E,x)),
           and())

i.e., the nested query was unnested into a right-outer join followed by a nesting.

The OQL query:

    select struct( E: e.name, D: e.dept.name, N: e.dept.address )
    from e in Employees
    where e.age>60 and e.dept.name="CSE";

is translated into the following algebraic form:

    reduce(bag,
           join(bag,
                get(bag,Employees,e,and(gt(project(e,age),60))),
                get(bag,Departments,x,and(eq(project(x,name),"CSE"))),
                and(eq(OID(project(e,dept)),OID(x))),
                none),
           y,
           struct(bind(E,project(e,name)),
                  bind(D,project(x,name)),
                  bind(N,project(x,address))),
           and())

Here we avoided materializing `e.dept` three times.

The OQL query:

    select distinct struct( E: e.name,
    			C: e.manager.name,
    			M: ( select c.name
    			       from c in e.children
    			      where for all d in e.manager.children: c.age > d.age ) )
    from e in Employees;

is translated into the following algebraic form:

    reduce(set,
           nest(bag,
                nest(all,
                     unnest(all,
                            unnest(bag,
                                   get(set,Employees,e,and()),
                                   c,
                                   project(e,children),
                                   and(),
                                   true),
                            d,
                            project(project(e,manager),children),
                            and(),
                            true),
                     x,
                     gt(project(c,age),project(d,age)),
                     vars(c,e),
                     vars(),
                     and()),
                y,
                project(c,name),
                vars(e),
                vars(x),
                and(x)),
           z,
           struct(bind(E,project(e,name)),
                  bind(C,project(project(e,manager),name)),
                  bind(M,y)),
           and())

A double nested query; the unnestings keep their inputs (possibly padded with nulls). Here, for the sake of simplicity, we didn't materialize path expressions.

The OQL query:

    group e in Employees by ( dname: e.dept.name );

is translated into the following algebraic form:

    reduce(set,
           nest(set,
                map(set,
                    join(bag,
                         get(set,Employees,e,and()),
                         get(bag,Departments,x,and()),
                         and(eq(OID(project(e,dept)),OID(x))),
                         left),
                    y,
                    project(x,name)),
                z,
                e,
                vars(x,y),
                vars(),
                and()),
           w,
           struct(bind(dname,project(x,name)),bind(partition,z)),
           and())