joinnode.java

derby database source code.good for you.

/*

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

   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.context.ContextManager;

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.Visitable;
import org.apache.derby.iapi.sql.compile.Visitor;
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.DataDictionary;
import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;

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

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

import org.apache.derby.iapi.sql.Activation;
import org.apache.derby.iapi.sql.ResultSet;

import org.apache.derby.iapi.store.access.TransactionController;

import org.apache.derby.iapi.services.loader.GeneratedMethod;

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

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

import java.util.Properties;
import java.util.Vector;

/**
 * A JoinNode represents a join result set for either of the basic DML
 * operations: SELECT and INSERT.  For INSERT - SELECT, any of the
 * fields in a JoinNode can be used (the JoinNode represents
 * the (join) SELECT statement in the INSERT - SELECT).  For INSERT,
 * the resultColumns in the selectList will contain the names of the columns
 * being inserted into or updated.
 *
 * @author Jeff Lichtman
 */

public class JoinNode extends TableOperatorNode
{
	/* Join semantics */
	public static final int INNERJOIN = 1;
	public static final int CROSSJOIN = 2;
	public static final int LEFTOUTERJOIN = 3;
	public static final int RIGHTOUTERJOIN = 4;
	public static final int FULLOUTERJOIN = 5;
	public static final int UNIONJOIN = 6;

	private boolean optimized;

	private PredicateList leftPredicateList;
	private PredicateList rightPredicateList;

	protected boolean flattenableJoin = true;
	Vector				aggregateVector;
	SubqueryList		subqueryList;
	ValueNode			joinClause;
	boolean	            joinClauseNormalized;
	PredicateList		joinPredicates;
	ResultColumnList	usingClause;


	/**
	 * Initializer for a JoinNode.
	 *
	 * @param leftResult	The ResultSetNode on the left side of this join
	 * @param rightResult	The ResultSetNode on the right side of this join
	 * @param onClause		The ON clause
	 * @param usingClause	The USING clause
	 * @param selectList	The result column list for the join
	 * @param tableProperties	Properties list associated with the table
	 *
	 * @exception StandardException		Thrown on error
	 */
	public void init(
					Object leftResult,
					Object rightResult,
					Object onClause,
					Object usingClause,
					Object selectList,
					Object tableProperties)
			throws StandardException
	{
		super.init(leftResult, rightResult, tableProperties);
		resultColumns = (ResultColumnList) selectList;
		joinClause = (ValueNode) onClause;
		joinClauseNormalized = false;
		this.usingClause = (ResultColumnList) usingClause;

		/* JoinNodes can be generated in the parser or at the end of optimization.
		 * Those generated in the parser do not have resultColumns yet.
		 */
		if (resultColumns != null)
		{
			/* A longer term assertion */
			if (SanityManager.DEBUG)
			{
				SanityManager.ASSERT((leftResultSet.getReferencedTableMap() != null &&
									  rightResultSet.getReferencedTableMap() != null) ||
									 (leftResultSet.getReferencedTableMap() == null &&
	 								  rightResultSet.getReferencedTableMap() == null),
					"left and right referencedTableMaps are expected to either both be non-null or both be null");
			}

			/* Build the referenced table map (left || right) */
			if (leftResultSet.getReferencedTableMap() != null)
			{
				referencedTableMap = (JBitSet) leftResultSet.getReferencedTableMap().clone();
				referencedTableMap.or((JBitSet) rightResultSet.getReferencedTableMap());
			}
		}
		joinPredicates = (PredicateList) getNodeFactory().getNode(
											C_NodeTypes.PREDICATE_LIST,
											getContextManager());
	}

	/*
	 *  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
	{
		optimizer.trace(Optimizer.CALLING_ON_JOIN_NODE, 0, 0, 0.0, null);

		// 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);

		/*
		** 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 joins, though, we want to figure out
		** the best plan for the join knowing how many outer rows there are -
		** it could affect the join strategy significantly.  So we implement
		** optimizeIt() here, which overrides the optimizeIt() in FromTable.
		** This assumes that the join strategy for which this join 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).
		*/

		/* RESOLVE - Need to figure out how to really optimize this node. */

		// RESOLVE: NEED TO SET ROW ORDERING OF SOURCES IN THE ROW ORDERING
		// THAT WAS PASSED IN.
		leftResultSet = optimizeSource(
							optimizer,
							leftResultSet,
							getLeftPredicateList(),
							outerCost);

		/* Move all joinPredicates down to the right.
		 * RESOLVE - When we consider the reverse join order then
		 * we will have to pull them back up and then push them
		 * down to the other side when considering the reverse
		 * join order.
		 * RESOLVE - This logic needs to be looked at when we
		 * implement full outer join.
		 */
		// Walk joinPredicates backwards due to possible deletes
		for (int index = joinPredicates.size() - 1; index >= 0; index --)
		{
			JBitSet	  curBitSet;
			Predicate predicate;

			predicate = (Predicate) joinPredicates.elementAt(index);
			if (! predicate.getPushable())
			{
				continue;
			}
			joinPredicates.removeElementAt(index);
			getRightPredicateList().addElement(predicate);
		}

		rightResultSet = optimizeSource(
							optimizer,
							rightResultSet,
							getRightPredicateList(),
							leftResultSet.getCostEstimate());

		costEstimate = getCostEstimate(optimizer);

		/*
		** We add the costs for the inner and outer table, but the number
		** of rows is that for the inner table only.
		*/
		costEstimate.setCost(
			leftResultSet.getCostEstimate().getEstimatedCost() +
			rightResultSet.getCostEstimate().getEstimatedCost(),
			rightResultSet.getCostEstimate().rowCount(),
			rightResultSet.getCostEstimate().rowCount());

		/*
		** Some types of joins (e.g. outer joins) will return a different
		** number of rows than is predicted by optimizeIt() in JoinNode.
		** So, adjust this value now. This method does nothing for most
		** join types.
		*/
		adjustNumberOfRowsReturned(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);

		/* Optimize subqueries only once, no matter how many times we're called */
		if ( (! optimized) && (subqueryList != null))
		{
			/* RESOLVE - Need to figure out how to really optimize this node.
		 	* Also need to figure out the pushing of the joinClause.
		 	*/
			subqueryList.optimize(optimizer.getDataDictionary(),
									costEstimate.rowCount());
			subqueryList.modifyAccessPaths();
		}

		optimized = true;

		return costEstimate;
	}

	/**
	 * @see Optimizable#pushOptPredicate
	 *
	 * @exception StandardException		Thrown on error
	 */

	public boolean pushOptPredicate(OptimizablePredicate optimizablePredicate)
			throws StandardException
	{
		if (SanityManager.DEBUG)
		{
			SanityManager.ASSERT(optimizablePredicate instanceof Predicate,
				"optimizablePredicate expected to be instanceof Predicate");
			SanityManager.ASSERT(! optimizablePredicate.hasSubquery() &&
								 ! optimizablePredicate.hasMethodCall(),
				"optimizablePredicate either has a subquery or a method call");
		}

		/* Add the matching predicate to the joinPredicates */
		joinPredicates.addPredicate((Predicate) optimizablePredicate);

		/* Remap all of the ColumnReferences to point to the
		 * source of the values.
		 */
		RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
		((Predicate) optimizablePredicate).getAndNode().accept(rcrv);

		return true;
	}

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

		/* By the time we're done here, both the left and right
		 * predicate lists should be empty because we pushed everything
		 * down.
		 */
		if (SanityManager.DEBUG)
		{
			if (getLeftPredicateList().size() != 0)
			{
				SanityManager.THROWASSERT(
					"getLeftPredicateList().size() expected to be 0, not " +
					getLeftPredicateList().size());
			}
			if (getRightPredicateList().size() != 0)
			{
				SanityManager.THROWASSERT(
					"getRightPredicateList().size() expected to be 0, not " +
					getRightPredicateList().size());
			}
		}

		return this;
	}


	/**
	 *  Some types of joins (e.g. outer joins) will return a different
	 *  number of rows than is predicted by optimizeIt() in JoinNode.
	 *  So, adjust this value now. This method does nothing for most
	 *  join types.
	 */
	protected void adjustNumberOfRowsReturned(CostEstimate costEstimate)
	{
	}

	/**
	 * Return a ResultColumnList with all of the columns in this table.
	 * (Used in expanding '*'s.)
	 * NOTE: Since this method is for expanding a "*" in the SELECT list,
	 * ResultColumn.expression will be a ColumnReference.
	 *
	 * @param allTableName		The qualifier on the "*"
	 *
	 * @return ResultColumnList	List of result columns from this table.
	 *
	 * @exception StandardException		Thrown on error
	 */
	public ResultColumnList getAllResultColumns(TableName allTableName)
			throws StandardException
	{
		/* We need special processing when there is a USING clause.
	 	 * The resulting table will be the join columns from
		 * the outer table followed by the non-join columns from 
		 * left side plus the non-join columns from the right side.
		 */
		if (usingClause == null)
		{
			return getAllResultColumnsNoUsing(allTableName);
		}

		/* Get the logical left side of the join.
		 * This is where the join columns come from.
		 * (For RIGHT OUTER JOIN, the left is the right
		 * and the right is the left and the JOIN is the NIOJ).
		 */
		ResultSetNode	logicalLeftRS = getLogicalLeftResultSet();

		// Get the join columns
		ResultColumnList joinRCL = logicalLeftRS.getAllResultColumns(
										null).
											getJoinColumns(usingClause);

		// Get the left and right RCLs
		ResultColumnList leftRCL = leftResultSet.getAllResultColumns(allTableName); 
		ResultColumnList rightRCL = rightResultSet.getAllResultColumns(allTableName); 

		/* Chop the join columns out of the both left and right.
		 * Thanks to the ANSI committee, the join columns 
		 * do not belong to either table.
		 */
		if (leftRCL != null)
		{
			leftRCL.removeJoinColumns(usingClause);
		}
		if (rightRCL != null)
		{
			rightRCL.removeJoinColumns(usingClause);
		}

		/* If allTableName is null, then we want to return the splicing
		 * of the join columns followed by the non-join columns from
		 * the left followed by the non-join columns from the right.
		 * If not, then at most 1 side should match.
		 * NOTE: We need to make sure that the RC's VirtualColumnIds
		 * are correct (1 .. size).
		 */
		if (leftRCL == null)
		{
			rightRCL.resetVirtualColumnIds();
			return rightRCL;
		}
		else if (rightRCL == null)
		{
			leftRCL.resetVirtualColumnIds();
			return leftRCL;
		}
		else
		{
			/* Both sides are non-null.  This should only happen
			 * if allTableName is null.
			 */
			if (SanityManager.DEBUG)
			{
				if (allTableName != null)
				{
					SanityManager.THROWASSERT(
						"allTableName (" + allTableName + 
						") expected to be null");
				}
			}
			joinRCL.destructiveAppend(leftRCL);
			joinRCL.destructiveAppend(rightRCL);
			joinRCL.resetVirtualColumnIds();
			return joinRCL;
		}
	}

	/**
	 * Return a ResultColumnList with all of the columns in this table.
	 * (Used in expanding '*'s.)
	 * NOTE: Since this method is for expanding a "*" in the SELECT list,
	 * ResultColumn.expression will be a ColumnReference.
	 * NOTE: This method is handles the case when there is no USING clause.
	 * The caller handles the case when there is a USING clause.
	 *
	 * @param allTableName		The qualifier on the "*"
	 *
	 * @return ResultColumnList	List of result columns from this table.
	 *
	 * @exception StandardException		Thrown on error
	 */
	private ResultColumnList getAllResultColumnsNoUsing(TableName allTableName)
			throws StandardException
	{
		ResultColumnList leftRCL = leftResultSet.getAllResultColumns(allTableName); 
		ResultColumnList rightRCL = rightResultSet.getAllResultColumns(allTableName); 
		/* If allTableName is null, then we want to return the spliced
		 * left and right RCLs.  If not, then at most 1 side should match.
		 */
		if (leftRCL == null)
		{
			return rightRCL;
		}
		else if (rightRCL == null)
		{
			return leftRCL;
		}
		else
		{
			/* Both sides are non-null.  This should only happen
			 * if allTableName is null.
			 */
			if (SanityManager.DEBUG)
			{
				if (allTableName != null)
				{