QueryInfo.java #5

/*
// $Id: //guest/julian_hyde/saffron/src/main/saffron/rel/QueryInfo.java#5 $
// Saffron preprocessor and data engine
// Copyright (C) 2002 Julian Hyde <julian.hyde@mail.com>
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Library General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
// Library General Public License for more details.
//
// You should have received a copy of the GNU Library General Public
// License along with this library; if not, write to the
// Free Software Foundation, Inc., 59 Temple Place - Suite 330,
// Boston, MA  02111-1307, USA.
//
// See the COPYING file located in the top-level-directory of
// the archive of this library for complete text of license.
*/

package saffron.rel;

import openjava.mop.Environment;
import openjava.mop.OJClass;
import openjava.mop.QueryEnvironment;
import openjava.mop.Toolbox;
import openjava.ptree.*;
import openjava.ptree.util.SyntheticClass;
import openjava.tools.DebugOut;
import saffron.opt.Cluster;
import saffron.opt.Query;
import saffron.opt.VolcanoPlanner;
import saffron.util.RelEnvironment;
import saffron.util.Util;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Vector;
import java.util.ArrayList;

/**
 * A <code>QueryInfo</code> holds all the information about a {@link
 * QueryExpression} while it is being translated into a collection of
 * {@link saffron.rel.Rel}s.
 *
 * <p>Those <code>Rel</code>s will all belong to the same {@link Cluster},
 * but <code>Cluster</code> is much simpler.  Please put the stuff which is
 * only needed at translation time into <code>QueryInfo</code>, and keep
 * <code>Cluster</code> simple.</p>
 **/

class QueryInfo
{
	QueryInfo parent;
	QueryEnvironment env;
	SaffronQueryExpander expander;
	HashSet leaves = new HashSet();
	Cluster cluster;
	private Rel root;

	/**
	 * Creates a <code>QueryInfo</code>
	 *
	 * @param env environment of the query that this expression was
	 *			  contained in - gives us access to the from list of that
	 *			  query
	 **/
	QueryInfo(
		QueryInfo parent, QueryEnvironment env,
		SaffronQueryExpander expander, Expression exp)
	{
		this.parent = parent;
		this.env = env;
		this.expander = expander;
		this.cluster = createCluster(parent, env.getParent(), exp);
	}

	static Cluster createCluster(
			QueryInfo queryInfo, Environment env, Expression exp) {
		Query query;
		VolcanoPlanner planner;
		if (queryInfo == null) {
			query = new Query();
			planner = null;
		} else {
			query = queryInfo.cluster.query;
			planner = queryInfo.cluster.planner;
		}
		return new Cluster(query, env, planner, exp);
	}

	Rel getRoot() {
		return root;
	}

	void setRoot(Rel root) {
		this.root = root;
	}

	/**
	 * Translates an expression into one which references only internal
	 * variables.  Clones the expression first.
	 *
	 * @param exp expression to translate
	 * @param rel relational expression in whose environment the returned
	 *			  expression will be interpreted
	 * @returns converted expression
	 **/
	public Expression convertExpToInternal(Expression exp)
	{
		return convertExpToInternal(exp, new Rel[] {getRoot()});
	}

	public Expression convertExpToInternal(Expression exp, Rel[] inputs)
	{
		Expression clone = (Expression) exp.makeRecursiveCopy();
		InternalTranslator translator = new InternalTranslator(
			this, inputs);
		return Util.go(translator, clone);
	}

	/**
	 * Translates an aggregate expression into one which references only
	 * variables. Expressions inside aggregate functions are added to
	 * <code>aggList</code>, if they are not already present.
	 *
	 * @param exp expression to translate
	 * @param groups expressions from the <code>group by</code> clause
	 * @param aggInputList expressions inside aggregations; expressions are
	 *	 added to this list if an aggregate needs one and it is not present
	 * @param aggCallList calls to aggregates; {@link
	 *	 saffron.rel.Aggregate.Call}s are added to this list if they are needed
	 *	 but are not present
	 **/
	public Expression convertGroupExpToInternal(
		Expression exp, Expression[] groups, ExpressionList aggInputList,
		Vector aggCallVector)
	{
		Expression clone = (Expression) exp.makeRecursiveCopy();
		AggInternalTranslator translator = new AggInternalTranslator(
			this, new Rel[] {getRoot()}, groups, aggInputList,
			aggCallVector);
		Expression translated;
		try {
			translated = Util.go(translator, clone);
		} catch (NotAGroupException e) {
			Util.discard(e);
			throw Util.newInternal(
				"Not a group-by expression: " + exp);
		}
		AggUnpickler unpickler = new AggUnpickler(this, groups.length);
		return Util.go(unpickler, translated);
	}

	/**
	 * Returns the <code>count</code>th leaf ({@link saffron.rel.Rel} which implements
	 * a from-list item) below this one.
	 *
	 * @param rel relation to start from
	 * @param count leaf number we want
	 * @param seen <code>seen[0]</code> contains the number of leaves we
	 *		  have seen so far
	 * @param path list containing the rel at each depth
	 * @param current depth
	 **/
	private Rel findLeaf(
			Rel rel, int count, int[] seen, ArrayList path, int depth)
	{
		if (leaves.contains(rel)) {
			if (seen[0] == count) {
				path.add(rel);
				return rel;
			} else {
				seen[0]++;
				return null;
			}
		} else {
			Rel[] inputs = rel.getInputs();
			path.add(rel);
			for (int i = 0; i < inputs.length; i++) {
				Rel result = findLeaf(inputs[i], count, seen, path, depth + 1);
				if (result != null) {
					return result;
				}
			}
			path.remove(path.size() - 1);
			return null;
		}
	}

	/**
	 * Returns the number of {@link saffron.rel.Rel}s below this one which
	 * implement a from-list item.
	 **/
	int countLeaves(Rel rel)
	{
		if (leaves.contains(rel)) {
			return 1;
		}
		Rel[] inputs = rel.getInputs();
		int width = 0;
		for (int i = 0; i < inputs.length; i++) {
			width += countLeaves(inputs[i]);
		}
		Util.assert(width > 0);
		return width;
	}

	/**
	 * Returns the number of columns in this input.
	 **/
	int countColumns(Rel rel)
	{
		OJClass clazz = rel.getRowType();
		if (clazz instanceof SyntheticClass) {
			SyntheticClass syntheticClass = (SyntheticClass) clazz;
			return syntheticClass.getWidth();
		} else {
			return 1;
		}
	}

	/**
	 * Creates an expression with which to reference <code>expression<code>,
	 * whose offset in its from-list is <code>offset</code>.
	 */
	Expression lookup(int offset, Rel[] inputs, boolean foo, String varName)
	{
		int[] seen = new int[] {0};
		for (int i = 0; i < inputs.length; i++) {
			Rel input = inputs[i];
			int oldSeen = seen[0];
			ArrayList path = new ArrayList();
			Rel leaf = findLeaf(input, offset, seen, path, 0);
			if (leaf == null) {
				continue;
			}
			Util.assert(path.get(0) == input);
			Util.assert(path.get(path.size() - 1) == leaf);
			int leafCount = countLeaves(input);
			Expression v;
			if (foo) {
				Util.assert(varName == null);
				v = null;
				int childOffset = 0;
				boolean inJoin = false;
			loop:
				for (int j = 0, count = path.size(); j < count; j++) {
					Rel parent = (Rel) path.get(j),
							child = null;
					if (j < path.size() - 1) {
						child = (Rel) path.get(j + 1);
					}
					if (parent instanceof Join) {
						Join join = (Join) parent;
						inJoin = true;
						if (child == join.left) {
							// nothing
						} else if (child == join.right) {
							childOffset += SyntheticClass.getWidth(
									join.left.getRowType());
						} else {
							throw Util.newInternal();
						}
					}
					if (j == 0) {
						v = RelEnvironment.makeReference(i);
						continue;
					}
					if (inJoin &&
							(child == null || parent instanceof Project)) {
						v = new FieldAccess(
								v,
								SyntheticClass.makeField(childOffset));
						inJoin = false;
					}
					if (child == null) {
						break;
					}
					if (parent instanceof Project) {
						if (inJoin) {
							v = new FieldAccess(
									v,
									SyntheticClass.makeField(childOffset));
							inJoin = false;
						}
						Project project = (Project) parent;
						Variable inputRef = RelEnvironment.makeReference(childOffset);
						for (int k = 0; k < project.exps.length; k++) {
							Expression exp = project.exps[k];
							if (exp.equals(inputRef)) {
								v = new FieldAccess(
										v,
										project.fieldNames[k]);
								continue loop;
							}
							throw Util.newInternal(
									"input#" + childOffset + " (" +
									child.toStringShort() +
									") is not referenced in select list of " +
									parent.toStringShort());
						}
					}
				}
			} else {
				if (varName == null) {
					varName = leaf.getOrCreateCorelVariable();
				} else {
					// we are resolving a forward reference
					leaf.registerCorelVariable(varName);
				}
				v = new Variable(varName);
			}
			if (leafCount == 1 || true /* todo: obsolete leafCount*/) {
				return v;
			} else {
				int field = seen[0] - oldSeen;
				Util.assert(0 <= field);
				Util.assert(field < leafCount);
				FieldAccess fieldAccess = new FieldAccess(
					v, SyntheticClass.makeField(field));
				return fieldAccess;
			}
		}
		throw Util.newInternal("could not find input");
	}

	Expression lookup(int offset, Rel input, boolean foo, String varName) {
		if (input == null) {
			// We're referencing a relational expression which has not
			// been translated yet. This occurs when from items are
			// correlated, e.g. select from emp as emp join emp.getDepts()
			// as dept. Create a temporary expression.
			Util.assert(!foo);
			Util.assert(
					varName == null,
					"when lookup is called to fixup forward references " +
					"(varName!=null), the input must not be null");
			DeferredLookup lookup = new DeferredLookup(this, offset, foo);
			String corelName = cluster.query.createCorelUnresolved(
				lookup);
			return new Variable(corelName);
		} else {
			return lookup(offset, new Rel[] {input}, foo, varName);
		}
	}

	/**
	 * Converts a {@link QueryExpression} into a {@link saffron.rel.Rel}.
	 *
	 * Capture occurs when a query is converted into relational
	 * expressions. The scalar expressions in the query reference (a) rows
	 * from their own query, (b) rows from an enclosing query, (c)
	 * variables from the enclosing environment.
	 *
	 * We have already dealt with (a), and we can leave environmental
	 * references (c) as they are.	So, we deal with references to rows in
	 * this query now.	References to queries inside or outside this query
	 * will happen in due course.
	 **/
	Rel convertQueryToRel(QueryExpression queryExp)
	{
		DebugOut.println(
			"convertQueryToRel: queryExp=[" + queryExp + "] recurse [");

		Expression fromList = queryExp.getFrom();
		setRoot(convertFromExpToRel(fromList));

		// Examples in the following refer to the query
		//	 select 1 + sum(x + 2)
		//	 group by y
		//	 from t
		//	 where min(z) > 4
		ExpressionList groupList = queryExp.getGroupList();
		if (groupList != null) {
			// "aggInputList" is the input expressions to the aggregation:
			// group expressions first, then expressions within aggregate
			// functions, for example {y, x + 2, z}.  "preGroups" and
			// "postGroups" are the group expressions before and after
			// translation.
			ExpressionList aggInputList = new ExpressionList();
			Expression[] preGroups = Util.toArray(groupList),
				postGroups = new Expression[preGroups.length];
			for (int i = 0; i < preGroups.length; i++) {
				Expression preGroup = preGroups[i];
				Expression postGroup = convertExpToInternal(preGroup);
				aggInputList.add(postGroup);
				postGroups[i] = postGroup;
			}
			Expression whereClause = queryExp.getWhere();
			// "aggCallVector" is the aggregate expressions, for example
			// {sum(#1), min(#2)}.
			Vector aggCallVector = new Vector();
			if (whereClause != null) {
				whereClause = convertGroupExpToInternal(
					whereClause, preGroups, aggInputList, aggCallVector);
				whereClause = removeSubqueries(whereClause);
			}
			Expression[] selects = Util.toArray(queryExp.getSelectList());
			String[] aliases = new String[selects.length];
			for (int i = 0; i < selects.length; i++) {
				aliases[i] = Util.getAlias(selects[i]);
				selects[i] = convertGroupExpToInternal(
					selects[i], preGroups, aggInputList, aggCallVector);
			}
			Aggregate.Call[] aggCalls = (Aggregate.Call[]) Util.toArray(
				aggCallVector, new Aggregate.Call[0]);
			Expression[] aggInputs = Util.toArray(aggInputList);
			setRoot(new Project(
					cluster, getRoot(), aggInputs, null, Project.flagBoxed));
			setRoot(new Aggregate(
				cluster, getRoot(), preGroups.length, aggCalls));
			if (whereClause != null) {
				setRoot(new Filter(cluster, getRoot(), whereClause));
			}
			setRoot(new Project(
					cluster, getRoot(), selects, aliases,
					queryExp.isBoxed() ? Project.flagBoxed : 0));

			ExpressionList sortList = queryExp.getSort();
			Expression[] sorts = Util.toArray(sortList);
			if (sorts != null && sorts.length > 0) {
				throw Toolbox.newInternal("sort not implemented");
			}
			OJClass relRowType = getRoot().getRowType(),
				queryRowType = queryExp.getRowType(env);
			DebugOut.println(
				"] return [" + getRoot() + "] rowType=[" + relRowType +
				"]");
			Util.assert(relRowType == queryRowType);
			return getRoot();
		}

		Expression whereClause = queryExp.getWhere();
		if (whereClause != null) {
			whereClause = convertExpToInternal(whereClause);
			whereClause = removeSubqueries(whereClause);
			setRoot(new Filter(cluster, getRoot(), whereClause));
		}

		Expression[] selects = Util.toArray(queryExp.getSelectList());
		String[] aliases = new String[selects.length];
		for (int i = 0; i < selects.length; i++) {
			aliases[i] = Util.getAlias(selects[i]);
			selects[i] = convertExpToInternal(selects[i]);
		}
		setRoot(new Project(
				cluster, getRoot(), selects, aliases,
				queryExp.isBoxed() ? Project.flagBoxed : 0));

		ExpressionList sortList = queryExp.getSort();
		Expression[] sorts = Util.toArray(sortList);
		if (sorts != null && sorts.length > 0) {
			throw Toolbox.newInternal("sort not implemented");

//			Parameter parameter = new Parameter("p", rel.getRowType(), null);
//				ExpReplacer replacer = new OrdinalRef.Replacer(0, parameter);
//				Sort[] compiledSorts = new Sort[sorts.length];
//				for (int i = 0; i < sorts.length; i++) {
//					compiledSorts[i] = new Sort(
//						(Exp) replacer.go(sorts[i].safeClone()),
//						sorts[i].ascending);
//				}
//				rel = new Sort(env, rel, sorts, parameter);
		}
		OJClass relRowType = getRoot().getRowType(),
			queryRowType = queryExp.getRowType(env);
		DebugOut.println(
			"] return [" + getRoot() + "] rowType=[" + relRowType +
			"]");
		if (relRowType != queryRowType) {
			throw Util.newInternal(
					"rel row type (" + relRowType + ") should equal the " +
					"row type (" + queryRowType + ") of the query it was " +
					"translated from");
		}
		return getRoot();
	}

	/**
	 * Converts an expression into a relational expression.	 For example,
	 * an array becomes an {@link ExpressionReader}.  Leaf nodes are
	 * registered in {@link #leaves}.
	 *
	 * @param exp the expression to convert
	 * @return the equivalent relational expression
	 **/
	Rel convertFromExpToRel(Expression exp)
	{
		if (exp == null) {
			Rel rel = new OneRow(cluster);
			leaves.add(rel);
			return rel;

		} else if (exp instanceof JoinExpression) {
			JoinExpression joinExp = (JoinExpression) exp;
			Expression leftExp = joinExp.getLeft(),
				rightExp = joinExp.getRight(),
				conditionExp = joinExp.getCondition();
			int joinType = joinExp.getJoinType();
			Rel left = convertFromExpToRel(leftExp),
				right = convertFromExpToRel(rightExp);
			// Deal with any forward-references.
			if (!cluster.query.mapDeferredToCorel.isEmpty()) {
				Iterator lookups = cluster.query.mapDeferredToCorel.keySet().iterator();
				while (lookups.hasNext()) {
					DeferredLookup lookup = (DeferredLookup) lookups.next();
					String corelName = (String)
							cluster.query.mapDeferredToCorel.get(lookup);
					// as a side-effect, this associates corelName with rel
					Expression expression = lookup.lookup(
							new Rel[] {left, right}, corelName);
					Util.assert(expression != null);
				}
				cluster.query.mapDeferredToCorel.clear();
			}
			// Make sure that left does not depend upon a correlating variable
			// coming from right. We'll swap them before we create a
			// JavaNestedLoopJoin.
			boolean swapped = false;
			String[] variables = Util.getVariablesSetAndUsed(right, left);
			if (variables.length > 0) {
				variables = Util.getVariablesSetAndUsed(left, right);
				if (variables.length > 0) {
					throw Util.newInternal(
						"joined expressions must not be mutually dependent: " +
						exp);
				}
			}
			conditionExp = convertExpToInternal(
				conditionExp, new Rel[] {left,right});
			return new Join(
				cluster, left, right, conditionExp, joinType);
		} else if (exp instanceof AliasedExpression) {
			AliasedExpression aliasedExp = (AliasedExpression) exp;
			return convertFromExpToRel(aliasedExp.getExpression());

		} else if (exp instanceof QueryExpression) {
			QueryExpression queryExp = (QueryExpression) exp;
			QueryEnvironment qenv = new QueryEnvironment(env, queryExp);
			QueryInfo newQueryInfo = new QueryInfo(
				this, qenv, expander, exp);
			Rel rel = newQueryInfo.convertQueryToRel(queryExp);
			leaves.add(rel);
			return rel;

		} else {
			// finally, look for relational expressions which can occur
			// anywhere, and fail if we're not looking at one
			return expander.convertExpToRel(exp, true, this, null);
		}
	}

	/**
	 * Goes through an expression looking for sub-queries (<code>in</code>
	 * or <code>exists</code>). If it finds one, it joins the query to the
	 * from clause, replaces the condition, and returns true.
	 *
	 * Examples:<ul>
	 *
	 * <li><code>exists</code> becomes a reference to a indicator
	 * query:
	 *
	 * <blockquote>
	 * <pre>select from dept
	 * where dept.location.equals("SF") && exists (
	 *	 select from emp
	 *	 where emp.deptno == dept.deptno && emp.gender.equals("F"))</pre>
	 * </blockquote>
	 *
	 * becomes
	 *
	 * <blockquote>
	 * <pre>select from dept cross join (
	 *	 select distinct from emp
	 *	 where emp.deptno == dept.deptno && emp.gender.equals("F"))
	 * where dept.location.equals("SF") && indicator != null</pre>
	 * </blockquote>
	 *
	 * <p>The reference to 'dept' from within a join query is illegal --
	 * but we haven't de-correlated yet.</li>
	 *
	 * <li><code>in</code> becomes a test to see whether an outer-joined
	 * query met the join condition:
	 *
	 * <blockquote>
	 * <pre>select from emp
	 * where emp.deptno in (
	 *	 select dept.deptno from dept where dept.location.equals("SF"))
	 * && emp.gender.equals("F")</pre>
	 * </blockquote>
	 *
	 * becomes
	 *
	 * <blockquote>
	 * <pre>select from emp <i>left</i> join (
	 *	 select dept.deptno from dept where dept.location.equals("SF")) q1
	 * on emp.deptno == q1.deptno
	 * where <i>q1 is not null &&</i> emp.gender.equals("F")</pre>
	 * </blockquote>
	 *
	 * Optimization #1: If the <code>in</code> condition is
	 * <code>&amp;&amp;</code>ed into the where clause, then make the join
	 * into a full join, and omit the condition.  Hence,
	 *
	 * <blockquote>
	 * <pre>select from emp join (
	 *	 select dept.deptno from dept where dept.location.equals("SF")) q1
	 * on emp.deptno == q1.deptno
	 * where emp.gender.equals("F")</pre>
	 * </blockquote>
	 *
	 * </li></ul>
	 *
	 * @param exps holds the expressions, passed
	 *	   in/out. <code>exps[0]</code> is the expression, and
	 *	   <code>exps[1]</code> is the from clause
	 * @return whether an subqueries where found and replaced
	 **/
	Expression removeSubqueries(Expression exp)
	{
		while (true) {
			Rel oldFrom = getRoot();
			SubqueryFinder subqueryFinder = new SubqueryFinder(this);
			Expression oldExp = exp;
			exp = Util.go(subqueryFinder, oldExp);
			if (oldFrom == getRoot()) {
				return exp;
			}
		}
	}
}

/**
 * Contains the information necessary to repeat a call to
 * {@link QueryInfo#lookup(int,Rel[],boolean,String)}.
 */
class DeferredLookup
{
	QueryInfo queryInfo;
	int offset;
	boolean foo;
	DeferredLookup(
			QueryInfo queryInfo, int offset, boolean foo) {
		this.queryInfo = queryInfo;
		this.offset = offset;
		this.foo = foo;
	}
	Expression lookup(Rel[] inputs, String varName) {
		return queryInfo.lookup(offset, inputs, foo, varName);
	}
}

// End QueryInfo.java