joinnode.java

derby database source code.good for you.

	{
		ResultSetNode newTreeTop;
		
		newTreeTop = super.preprocess(numTables, gbl, fromList);

		/* Put the expression trees in conjunctive normal form.
		 * NOTE - This needs to occur before we preprocess the subqueries
		 * because the subquery transformations assume that any subquery operator 
		 * negation has already occurred.
		 */
		if (joinClause != null)
		{
			normExpressions();

			/* Preprocess any subqueries in the join clause */
			if (subqueryList != null)
			{
				/* RESOLVE - In order to flatten a subquery in
				 * the ON clause of an inner join we'd have to pass
				 * the various lists from the outer select through to
				 * ResultSetNode.preprocess() and overload
				 * normExpressions in HalfOuterJoinNode.  That's not
				 * worth the effort, so we say that the ON clause
				 * is not under a top level AND in normExpressions()
				 * to ensure that subqueries in the ON clause do not
				 * get flattened.  That allows us to pass empty lists
				 * to joinClause.preprocess() because we know that no
				 * flattening will take place. (Bug #1206)
				 */
				joinClause.preprocess(
								numTables,
								(FromList) getNodeFactory().getNode(
									C_NodeTypes.FROM_LIST,
									getNodeFactory().doJoinOrderOptimization(),
									getContextManager()),
								(SubqueryList) getNodeFactory().getNode(
													C_NodeTypes.SUBQUERY_LIST,
													getContextManager()),
								(PredicateList) getNodeFactory().getNode(
													C_NodeTypes.PREDICATE_LIST,
													getContextManager()));
			}

			/* Pull apart the expression trees */
			joinPredicates.pullExpressions(numTables, joinClause);
			joinPredicates.categorize();
			joinClause = null;
		}

		return newTreeTop;
	}

    /**
     * Find the unreferenced result columns and project them out. This is used in pre-processing joins
     * that are not flattened into the where clause.
     */
    void projectResultColumns() throws StandardException
    {
        leftResultSet.projectResultColumns();
        rightResultSet.projectResultColumns();
        resultColumns.pullVirtualIsReferenced();
        super.projectResultColumns();
    }
    
	/** Put the expression trees in conjunctive normal form 
	 *
	 * @return None.
	 *
	 * @exception StandardException		Thrown on error
	 */
	public void normExpressions()
				throws StandardException
	{
		if (joinClauseNormalized == true) return;

		/* For each expression tree:
		 *	o Eliminate NOTs (eliminateNots())
		 *	o Ensure that there is an AndNode on top of every
		 *	  top level expression. (putAndsOnTop())
		 *	o Finish the job (changeToCNF())
		 */
		joinClause = joinClause.eliminateNots(false);
		if (SanityManager.DEBUG)
		{
			if (!(joinClause.verifyEliminateNots()) )
			{
				joinClause.treePrint();
				SanityManager.THROWASSERT(
					"joinClause in invalid form: " + joinClause); 
			}
		}
		joinClause = joinClause.putAndsOnTop();
		if (SanityManager.DEBUG)
		{
			if (! ((joinClause instanceof AndNode) &&
				   (joinClause.verifyPutAndsOnTop())) )
			{
				joinClause.treePrint();
				SanityManager.THROWASSERT(
					"joinClause in invalid form: " + joinClause); 
			}
		}
		/* RESOLVE - ON clause is temporarily "not under a top
		 * top level AND" until we figure out how to deal with
		 * subqueries in the ON clause. (Bug 1206)
		 */
		joinClause = joinClause.changeToCNF(false);
		if (SanityManager.DEBUG)
		{
			if (! ((joinClause instanceof AndNode) &&
				   (joinClause.verifyChangeToCNF())) )
			{
				joinClause.treePrint();
				SanityManager.THROWASSERT(
					"joinClause in invalid form: " + joinClause); 
			}
		}

		joinClauseNormalized = true;
	}

	/**
	 * Push expressions down to the first ResultSetNode which can do expression
	 * evaluation and has the same referenced table map.
	 * RESOLVE - This means only pushing down single table expressions to
	 * DistinctNodes today.  Once we have a better understanding of how
	 * the optimizer will work, we can push down join clauses.
	 *
	 * @param outerPredicateList	The PredicateList from the outer RS.
	 *
	 * @exception StandardException		Thrown on error
	 */
	public void pushExpressions(PredicateList outerPredicateList)
					throws StandardException
	{
		FromTable		leftFromTable = (FromTable) leftResultSet;
		FromTable		rightFromTable = (FromTable) rightResultSet;

		/* OuterJoinNodes are responsible for overriding this
		 * method since they have different rules about where predicates
		 * can be applied.
		 */
		if (SanityManager.DEBUG)
		{
			if (this instanceof HalfOuterJoinNode)
			{
				SanityManager.THROWASSERT(
					"JN.pushExpressions() not expected to be called for " +
					getClass().getName());
			}
		}

		/* We try to push "pushable" 
		 * predicates to 1 of 3 places:
		 *	o Predicates that only reference tables
		 *	  on the left are pushed to the leftPredicateList.
		 *	o Predicates that only reference tables
		 *	  on the right are pushed to the rightPredicateList.
		 *	o Predicates which reference tables on both
		 *	  sides (and no others) are pushed to 
		 *	  the joinPredicates and may be pushed down
		 *	  further during optimization.
		 */
		// Left only
		pushExpressionsToLeft(outerPredicateList);
		leftFromTable.pushExpressions(getLeftPredicateList());
		// Right only
		pushExpressionsToRight(outerPredicateList);
		rightFromTable.pushExpressions(getRightPredicateList());
		// Join predicates
		grabJoinPredicates(outerPredicateList);

		/* 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());
			}
		}
	}

	protected void pushExpressionsToLeft(PredicateList outerPredicateList)
		throws StandardException
	{
		FromTable		leftFromTable = (FromTable) leftResultSet;

		JBitSet		leftReferencedTableMap = leftFromTable.getReferencedTableMap();

		/* Build a list of the single table predicates on left result set
		 * that we can push down 
		 */
		// Walk outerPredicateList backwards due to possible deletes
		for (int index = outerPredicateList.size() - 1; index >= 0; index --)
		{
			JBitSet	  curBitSet;
			Predicate predicate;

			predicate = (Predicate) outerPredicateList.elementAt(index);
			if (! predicate.getPushable())
			{
				continue;
			}

			curBitSet = predicate.getReferencedSet();
			
			/* Do we have a match? */
			if (leftReferencedTableMap.contains(curBitSet))
			{
				/* Add the matching predicate to the push list */
				getLeftPredicateList().addPredicate(predicate);

				/* Remap all of the ColumnReferences to point to the
				 * source of the values.
				 * The tree is something like:
				 *			PRN1
				 *			  |
				 *			 JN (this)
				 *		   /    \
				 *		PRN2	PRN3
				 *        |       |
				 *		FBT1	FBT2
				 *
				 * The ColumnReferences start off pointing to the RCL off of
				 * PRN1.  For optimization, we want them to point to the
				 * RCL off of PRN2.  In order to do that, we remap them
				 * twice here.  If optimization pushes them down to the
				 * base table, it will remap them again.
				 */
				RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
				predicate.getAndNode().accept(rcrv);
				predicate.getAndNode().accept(rcrv);

				/* Remove the matching predicate from the outer list */
				outerPredicateList.removeElementAt(index);
			}
		}
	}

	private void pushExpressionsToRight(PredicateList outerPredicateList)
		throws StandardException
	{
		FromTable		rightFromTable = (FromTable) rightResultSet;

		JBitSet		rightReferencedTableMap = rightFromTable.getReferencedTableMap();

		/* Build a list of the single table predicates on right result set
		 * that we can push down 
		 */
		// Walk outerPredicateList backwards due to possible deletes
		for (int index = outerPredicateList.size() - 1; index >= 0; index --)
		{
			JBitSet	  curBitSet;
			Predicate predicate;

			predicate = (Predicate) outerPredicateList.elementAt(index);
			if (! predicate.getPushable())
			{
				continue;
			}

			curBitSet = predicate.getReferencedSet();
			
			/* Do we have a match? */
			if (rightReferencedTableMap.contains(curBitSet))
			{
				/* Add the matching predicate to the push list */
				getRightPredicateList().addPredicate(predicate);

				/* Remap all of the ColumnReferences to point to the
				 * source of the values.
				 * The tree is something like:
				 *			PRN1
				 *			  |
				 *			 JN (this)
				 *		   /    \
				 *		PRN2	PRN3
				 *        |       |
				 *		FBT1	FBT2
				 *
				 * The ColumnReferences start off pointing to the RCL off of
				 * PRN1.  For optimization, we want them to point to the
				 * RCL off of PRN3.  In order to do that, we remap them
				 * twice here.  If optimization pushes them down to the
				 * base table, it will remap them again.
				 */
				RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
				predicate.getAndNode().accept(rcrv);
				predicate.getAndNode().accept(rcrv);

				/* Remove the matching predicate from the outer list */
				outerPredicateList.removeElementAt(index);
			}
		}
	}

	private void grabJoinPredicates(PredicateList outerPredicateList)
		throws StandardException
	{
		FromTable		leftFromTable = (FromTable) leftResultSet;
		FromTable		rightFromTable = (FromTable) rightResultSet;

		JBitSet		leftReferencedTableMap = leftFromTable.getReferencedTableMap();
		JBitSet		rightReferencedTableMap = rightFromTable.getReferencedTableMap();

		/* Build a list of the join predicates that we can push down */
		// Walk outerPredicateList backwards due to possible deletes
		for (int index = outerPredicateList.size() - 1; index >= 0; index --)
		{
			JBitSet	  curBitSet;
			Predicate predicate;

			predicate = (Predicate) outerPredicateList.elementAt(index);
			if (! predicate.getPushable())
			{
				continue;
			}

			curBitSet = predicate.getReferencedSet();
			
			/* Do we have a match? */
			JBitSet innerBitSet = (JBitSet) rightReferencedTableMap.clone();
			innerBitSet.or(leftReferencedTableMap);
			if (innerBitSet.contains(curBitSet))
			{
				/* Add the matching predicate to the push list */
				joinPredicates.addPredicate(predicate);

				/* Remap all of the ColumnReferences to point to the
				 * source of the values.
				 * The tree is something like:
				 *			PRN1
				 *			  |
				 *			 JN (this)
				 *		   /    \
				 *		PRN2	PRN3
				 *        |       |
				 *		FBT1	FBT2
				 *
				 * The ColumnReferences start off pointing to the RCL off of
				 * PRN1.  For optimization, we want them to point to the
				 * RCL off of PRN2 or PRN3.  In order to do that, we remap them
				 * twice here.  If optimization pushes them down to the
				 * base table, it will remap them again.
				 */
				RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
				predicate.getAndNode().accept(rcrv);
				predicate.getAndNode().accept(rcrv);

				/* Remove the matching predicate from the outer list */
				outerPredicateList.removeElementAt(index);
			}
		}
	}

	/**
	 * Flatten this JoinNode into the outer query block. The steps in
	 * flattening are:
	 *	o  Mark all ResultColumns as redundant, so that they are "skipped over"
	 *	   at generate().
	 *	o  Append the joinPredicates to the outer list.
	 *	o  Create a FromList from the tables being joined and return 
	 *	   that list so that the caller will merge the 2 lists 
	 *
	 * @param rcl				The RCL from the outer query
	 * @param outerPList		PredicateList to append wherePredicates to.
	 * @param sql				The SubqueryList from the outer query
	 * @param gbl				The group by list, if any
	 *
	 * @return FromList		The fromList from the underlying SelectNode.
	 *
	 * @exception StandardException		Thrown on error
	 */
	public FromList flatten(ResultColumnList rcl,
							PredicateList outerPList,
							SubqueryList sql,
							GroupByList gbl)

			throws StandardException
	{
		/* OuterJoinNodes should never get here.
		 * (They can be transformed, but never
		 * flattened directly.)
		 */
		if (SanityManager.DEBUG)
		{
			if (this instanceof HalfOuterJoinNode)
			{
				SanityManager.THROWASSERT(
					"JN.flatten() not expected to be called for " +
					getClass().getName());
			}
		}

		/* Build a new FromList composed of left and right children 
		 * NOTE: We must call FL.addElement() instead of FL.addFromTable()
		 * since there is no exposed name. (And even if there was,
		 * we could care less about unique exposed name checking here.)
		 */
		FromList	fromList = (FromList) getNodeFactory().getNode(
									C_NodeTypes.FROM_LIST,
									getNodeFactory().doJoinOrderOptimization(),
									getContextManager());
		fromList.addElement((FromTable) leftResultSet);
		fromList.addElement((FromTable) rightResultSet);

		/* Mark our RCL as redundant */
		resultColumns.setRedundant();

		/* Remap all ColumnReferences from the outer query to this node.
		 * (We replace those ColumnReferences with clones of the matching
		 * expression in the left and right's RCL.
		 */
		rcl.remapColumnReferencesToExpressions();
		outerPList.remapColumnReferencesToExpressions();
		if (gbl != null)
		{
			gbl.remapColumnReferencesToExpressions();
		}

		if (joinPredicates.size() > 0)
		{
			outerPList.destructiveAppend(joinPredicates);
		}

		if (subqueryList != null && subqueryList.size() > 0)
		{
			sql.destructiveAppend(subqueryList);
		}

		return fromList;
	}

	/**
	 * Currently we don't reordering any outer join w/ inner joins.
	 */
	public boolean LOJ_reorderable(int numTables)
				throws StandardException
	{
		return false;
	}

	/**
	 * Transform any Outer Join into an Inner Join where applicable.
	 * (Based on the existence of a null intolerant
	 * predicate on the inner table.)
	 *
	 * @param predicateTree	The predicate tree for the query block
	 *
	 * @return The new tree top (OuterJoin or InnerJoin).
	 *
	 * @exception StandardException		Thrown on error
	 */
	public FromTable transformOuterJoins(ValueNode predicateTree, int numTables)
		throws StandardException
	{
		/* Can't flatten if no predicates in where clause. */
		if (predicateTree == null)
		{
			return this;
		}

		/* See if left or right sides can be transformed */
		leftResultSet = ((FromTable) leftResultSet).transformOuterJoins(predicateTree, numTables);
		rightResultSet = ((FromTable) rightResultSet).transformOuterJoins(predicateTree, numTables);

		return this;
	}

    /**
     * For joins, the tree will be (nodes are left out if the clauses
     * are empty):
     *
     *      ProjectRestrictResultSet -- for the having and the select list
     *      SortResultSet -- for the group by list
     *      ProjectRestrictResultSet -- for the where and the select list (if no group or having)
     *      the result set for the fromList
     *
	 *
	 * @exception StandardException		Thrown on error
     */