unionnode.java

derby database source code.good for you.

/*

   Derby - Class org.apache.derby.impl.sql.compile.UnionNode

   Copyright 1997, 2004 The Apache Software Foundation or its licensors, as applicable.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.

 */

package	org.apache.derby.impl.sql.compile;

import org.apache.derby.iapi.services.compiler.MethodBuilder;

import org.apache.derby.iapi.services.sanity.SanityManager;

import org.apache.derby.iapi.error.StandardException;

import org.apache.derby.iapi.sql.compile.Optimizable;
import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
import org.apache.derby.iapi.sql.compile.Optimizer;
import org.apache.derby.iapi.sql.compile.CostEstimate;
import org.apache.derby.iapi.sql.compile.RowOrdering;
import org.apache.derby.iapi.sql.compile.C_NodeTypes;

import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;

import org.apache.derby.iapi.reference.SQLState;
import org.apache.derby.iapi.reference.ClassName;

import org.apache.derby.impl.sql.compile.ActivationClassBuilder;

import org.apache.derby.iapi.types.DataTypeDescriptor;

import org.apache.derby.iapi.util.JBitSet;
import org.apache.derby.iapi.services.classfile.VMOpcode;

/**
 * A UnionNode represents a UNION in a DML statement.  It contains a boolean
 * telling whether the union operation should eliminate duplicate rows.
 *
 * @author Jeff Lichtman
 */

public class UnionNode extends SetOperatorNode
{
	/* Only optimize it once */
	/* Only call addNewNodes() once */
	private boolean addNewNodesCalled;

	/* Is this a UNION ALL generated for a table constructor -- a VALUES expression with multiple rows. */
	boolean			tableConstructor;

	/* True if this is the top node of a table constructor */
	boolean			topTableConstructor;


	/**
	 * Initializer for a UnionNode.
	 *
	 * @param leftResult		The ResultSetNode on the left side of this union
	 * @param rightResult		The ResultSetNode on the right side of this union
	 * @param all				Whether or not this is a UNION ALL.
	 * @param tableConstructor	Whether or not this is from a table constructor.
	 * @param tableProperties	Properties list associated with the table
	 *
	 * @exception StandardException		Thrown on error
	 */

	public void init(
					Object leftResult,
					Object rightResult,
					Object all,
					Object tableConstructor,
					Object tableProperties)
			throws StandardException
	{
		super.init(leftResult, rightResult, all, tableProperties);

		/* Is this a UNION ALL for a table constructor? */
		this.tableConstructor = ((Boolean) tableConstructor).booleanValue();
    } // end of init

	/**
	 * Mark this as the top node of a table constructor.
	 */
	public void markTopTableConstructor()
	{
		topTableConstructor = true;
	}

	/**
	 * Tell whether this is a UNION for a table constructor.
	 */
	boolean tableConstructor()
	{
		return tableConstructor;
	}

	/**
	 * Check for (and reject) ? parameters directly under the ResultColumns.
	 * This is done for SELECT statements.  Don't reject parameters that
	 * are in a table constructor - these are allowed, as long as the
	 * table constructor is in an INSERT statement or each column of the
	 * table constructor has at least one non-? column.  The latter case
	 * is checked below, in bindExpressions().
	 *
	 * @return	Nothing
	 *
	 * @exception StandardException		Thrown if a ? parameter found
	 *									directly under a ResultColumn
	 */
	public void rejectParameters() throws StandardException
	{
		if ( ! tableConstructor())
			super.rejectParameters();
	}

	/**
	 * Set the type of column in the result column lists of each
	 * source of this union tree to the type in the given result column list
	 * (which represents the result columns for an insert).
	 * This is only for table constructors that appear in insert statements.
	 *
	 * @param typeColumns	The ResultColumnList containing the desired result
	 *						types.
	 *
	 * @exception StandardException		Thrown on error
	 */
	void setTableConstructorTypes(ResultColumnList typeColumns)
			throws StandardException
	{
		if (SanityManager.DEBUG)
		{
			SanityManager.ASSERT(resultColumns.size() <= typeColumns.size(),
				"More columns in ResultColumnList than in base table.");
		}

		ResultSetNode	rsn;

		/*
		** Should only set types of ? parameters to types of result columns
		** if it's a table constructor.
		*/
		if (tableConstructor())
		{
			/* By looping through the union nodes, we avoid recursion */
			for (rsn = this; rsn instanceof UnionNode; )
			{
				UnionNode union = (UnionNode) rsn;

				/*
				** Assume that table constructors are left-deep trees of UnionNodes
				** with RowResultSet nodes on the right.
				*/
				if (SanityManager.DEBUG)
					SanityManager.ASSERT(
						union.rightResultSet instanceof RowResultSetNode,
						"A " + union.rightResultSet.getClass().getName() +
						" is on the right of a union in a table constructor");

				((RowResultSetNode) union.rightResultSet).setTableConstructorTypes(
																typeColumns);

				rsn = union.leftResultSet;
			}

			/* The last node on the left should be a result set node */
			if (SanityManager.DEBUG)
				SanityManager.ASSERT(rsn instanceof RowResultSetNode,
					"A " + rsn.getClass().getName() +
					" is at the left end of a table constructor");

			((RowResultSetNode) rsn).setTableConstructorTypes(typeColumns);
		}
	}

	/*
	 *  Optimizable interface
	 */

	/**
	 * @see org.apache.derby.iapi.sql.compile.Optimizable#optimizeIt
	 *
	 * @exception StandardException		Thrown on error
	 */
	public CostEstimate optimizeIt(Optimizer optimizer,
							OptimizablePredicateList predList,
							CostEstimate outerCost,
							RowOrdering rowOrdering)
			throws StandardException
	{
		/*
		** RESOLVE: Most types of Optimizables only implement estimateCost(),
		** and leave it up to optimizeIt() in FromTable to figure out the
		** total cost of the join.  For unions, though, we want to figure out
		** the best plan for the sources knowing how many outer rows there are -
		** it could affect their strategies significantly.  So we implement
		** optimizeIt() here, which overrides the optimizeIt() in FromTable.
		** This assumes that the join strategy for which this union node is
		** the inner table is a nested loop join, which will not be a valid
		** assumption when we implement other strategies like materialization
		** (hash join can work only on base tables).
		*/

		/* optimize() both resultSets */

		// If we have predicates from an outer block, we want to try
		// to push them down to this node's children.  However, we can't
		// just push the predicates down as they are; instead, we
		// need to scope them for the child result sets first, and
		// then push the scoped versions.  This is all done in the
		// call to pushOptPredicate() here; for more, see that method's
		// definition in SetOperatorNode.  NOTE: If we're considering a
		// hash join then we do not push the predicates because we'll
		// need the predicates to be at this level in order to find
		// out if one of them is an equijoin predicate that can be used
		// for the hash join.
		if ((predList != null) &&
			!getCurrentAccessPath().getJoinStrategy().isHashJoin())
		{
			for (int i = predList.size() - 1; i >= 0; i--) {
				if (pushOptPredicate(predList.getOptPredicate(i)))
					predList.removeOptPredicate(i);
			}
		}

		// It's possible that a call to optimize the left/right will cause
		// a new "truly the best" plan to be stored in the underlying base
		// tables.  If that happens and then we decide to skip that plan
		// (which we might do if the call to "considerCost()" below decides
		// the current path is infeasible or not the best) we need to be
		// able to revert back to the "truly the best" plans that we had
		// saved before we got here.  So with this next call we save the
		// current plans using "this" node as the key.  If needed, we'll
		// then make the call to revert the plans in OptimizerImpl's
		// getNextDecoratedPermutation() method.
		addOrLoadBestPlanMapping(true, this);

		leftResultSet = optimizeSource(
							optimizer,
							leftResultSet,
							getLeftOptPredicateList(),
							outerCost);

		rightResultSet = optimizeSource(
							optimizer,
							rightResultSet,
							getRightOptPredicateList(),
							outerCost);

		CostEstimate costEstimate = getCostEstimate(optimizer);

		/* The cost is the sum of the two child costs */
		costEstimate.setCost(leftResultSet.getCostEstimate().getEstimatedCost(),
							 leftResultSet.getCostEstimate().rowCount(),
							 leftResultSet.getCostEstimate().singleScanRowCount() +
							 rightResultSet.getCostEstimate().singleScanRowCount());

		costEstimate.add(rightResultSet.costEstimate, costEstimate);

		/*
		** Get the cost of this result set in the context of the whole plan.
		*/
		getCurrentAccessPath().
			getJoinStrategy().
				estimateCost(
							this,
							predList,
							(ConglomerateDescriptor) null,
							outerCost,
							optimizer,
							costEstimate
							);

		optimizer.considerCost(this, predList, costEstimate, outerCost);

		return costEstimate;
	}

	/**
	 * DERBY-649: Handle pushing predicates into UnionNodes. It is possible to push
	 * single table predicates that are binaryOperations or inListOperations. 
	 *
	 * Predicates of the form <columnReference> <RELOP> <constant> or <columnReference>
	 * IN <constantList> are currently handled. Since these predicates would allow
	 * optimizer to pick available indices, pushing them provides maximum benifit.
	 *
	 * It should be possible to expand this logic to cover more cases. Even pushing
	 * expressions (like a+b = 10) into SELECTs would improve performance, even if
	 * they don't allow use of index. It would mean evaluating expressions closer to
	 * data and hence could avoid sorting or other overheads that UNION may require.
	 *
	 * Note that the predicates are not removed after pushing. This is to ensure if
	 * pushing is not possible or only partially feasible.
	 *
	 * @param 	predicateList		List of single table predicates to push
	 *
	 * @return	Nothing
	 *
	 * @exception	StandardException		Thrown on error
	 */
	public void pushExpressions(PredicateList predicateList)
					throws StandardException
	{
		// If left or right side is a UnionNode, further push the predicate list
		// Note, it is OK not to push these predicates since they are also evaluated
		// in the ProjectRestrictNode. There are other types of operations possible
		// here in addition to UnionNode or SelectNode, like RowResultSetNode.
		if (leftResultSet instanceof UnionNode)
			((UnionNode)leftResultSet).pushExpressions(predicateList);
		else if (leftResultSet instanceof SelectNode)
			predicateList.pushExpressionsIntoSelect((SelectNode)leftResultSet, true);

		if (rightResultSet instanceof UnionNode)
			((UnionNode)rightResultSet).pushExpressions(predicateList);
		else if (rightResultSet instanceof SelectNode)
			predicateList.pushExpressionsIntoSelect((SelectNode)rightResultSet, true);
	}

	/**
	 * @see Optimizable#modifyAccessPath
	 *
	 * @exception StandardException		Thrown on error
	 */
	public Optimizable modifyAccessPath(JBitSet outerTables) throws StandardException