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())

Last modified: 7/21/97 by Leonidas Fegaras