predicatelist.java

derby database source code.good for you.

			return;
		}

		/* Create an array of numTables PredicateLists to hold the join clauses. */
		PredicateList[] joinClauses = new PredicateList[numTables];
		for (int index = 0; index < numTables; index++)
		{
			joinClauses[index] = new PredicateList();
		}

		/* Pull the equijoin clauses, putting each one in the list for
		 * each of the tables being joined.
		 */
		int size = size();
		for (int index = 0; index < size; index++)
		{
			Predicate predicate = (Predicate) elementAt(index);
			ValueNode vn = predicate.getAndNode().getLeftOperand();

			if (! (vn.isBinaryEqualsOperatorNode()))
			{
				continue;
			}

			/* Is this an equijoin clause between 2 ColumnReferences? */
			BinaryRelationalOperatorNode equals = 
                (BinaryRelationalOperatorNode) vn;
			ValueNode left = equals.getLeftOperand();
			ValueNode right = equals.getRightOperand();

			if ((left  instanceof ColumnReference && 
                 right instanceof ColumnReference))
			{
				ColumnReference leftCR = (ColumnReference) left;
				ColumnReference rightCR = (ColumnReference) right;
				if (leftCR.getSourceLevel() == rightCR.getSourceLevel() &&
					leftCR.getTableNumber() != rightCR.getTableNumber())
				{
					// Add the equijoin clause to each of the lists
					joinClauses[leftCR.getTableNumber()].addElement(predicate);
					joinClauses[rightCR.getTableNumber()].addElement(predicate);
				}
				continue;
			}
		}

		/* Walk each of the PredicateLists, using each 1 as the starting point 
         * of an equivalence class.
		 */
		for (int index = 0; index < numTables; index++)
		{
			PredicateList outerJCL = joinClauses[index];

			// Skip the empty lists
			if (outerJCL.size() == 0)
			{
				continue;
			}

			/* Put all of the join clauses that already have an equivalence 
             * class at the head of the outer list to optimize search.
			 */
			Vector movePreds = new Vector();
			for (int jcIndex = outerJCL.size() - 1; jcIndex >= 0; jcIndex--)
			{
				Predicate predicate = (Predicate) outerJCL.elementAt(jcIndex);
				if (predicate.getEquivalenceClass() != -1)
				{
					outerJCL.removeElementAt(jcIndex);
					movePreds.addElement(predicate);
				}
			}
			for (int mpIndex = 0; mpIndex < movePreds.size(); mpIndex++)
			{
				outerJCL.insertElementAt(
                    (Predicate) movePreds.elementAt(mpIndex), 0);
			}

			// Walk this list as the outer
			for (int outerIndex = 0; outerIndex < outerJCL.size(); outerIndex++)
			{
				ColumnReference innerCR = null;
				ColumnReference outerCR = null;
				int outerTableNumber = index;
				int middleTableNumber;
				int outerColumnNumber;
				int middleColumnNumber;
				int outerEC;

				/* Assign an equivalence class to those Predicates 
				 * that have not already been assigned an equivalence class.
				 */
				Predicate outerP = (Predicate) outerJCL.elementAt(outerIndex);
				if (outerP.getEquivalenceClass() == -1)
				{
					outerP.setEquivalenceClass(cc.getNextEquivalenceClass());
				}
				outerEC = outerP.getEquivalenceClass();

				// Get the table and column numbers
				BinaryRelationalOperatorNode equals = 
					(BinaryRelationalOperatorNode) outerP.getAndNode().getLeftOperand();
				ColumnReference leftCR = (ColumnReference) equals.getLeftOperand();
				ColumnReference rightCR = (ColumnReference) equals.getRightOperand();

				if (leftCR.getTableNumber() == outerTableNumber)
				{
					outerColumnNumber = leftCR.getColumnNumber();
					middleTableNumber = rightCR.getTableNumber();
					middleColumnNumber = rightCR.getColumnNumber();
					outerCR = leftCR;
				}
				else
				{
					outerColumnNumber = rightCR.getColumnNumber();
					middleTableNumber = leftCR.getTableNumber();
					middleColumnNumber = leftCR.getColumnNumber();
					outerCR = rightCR;
				}

				/* Walk the other list as the middle to find other join clauses
				 * in the chain/equivalence class
				 */
				PredicateList middleJCL = joinClauses[middleTableNumber];
				for (int middleIndex = 0; middleIndex < middleJCL.size(); middleIndex++)
				{
					/* Skip those Predicates that have already been
					 * assigned a different equivalence class.
					 */
					Predicate middleP = (Predicate) middleJCL.elementAt(middleIndex);
					if (middleP.getEquivalenceClass() != -1 &&
						middleP.getEquivalenceClass() != outerEC)
					{
						continue;
					}

					int innerTableNumber;
					int innerColumnNumber;

					// Get the table and column numbers
					BinaryRelationalOperatorNode middleEquals = 
						(BinaryRelationalOperatorNode) middleP.getAndNode().getLeftOperand();
					ColumnReference mLeftCR = (ColumnReference) middleEquals.getLeftOperand();
					ColumnReference mRightCR = (ColumnReference) middleEquals.getRightOperand();

					/* Find the other side of the equijoin, skipping this predicate if 
					 * not on middleColumnNumber.
					 */
					if (mLeftCR.getTableNumber() == middleTableNumber) 
					{
						if (mLeftCR.getColumnNumber() != middleColumnNumber)
						{
							continue;
						}
						innerTableNumber = mRightCR.getTableNumber();
						innerColumnNumber = mRightCR.getColumnNumber();
					}
					else
					{
						if (mRightCR.getColumnNumber() != middleColumnNumber)
						{
							continue;
						}
						innerTableNumber = mLeftCR.getTableNumber();
						innerColumnNumber = mLeftCR.getColumnNumber();
					}

					// Skip over outerTableNumber.outerColumnNumber = middleTableNumber.middleColumnNumber
  					if (outerTableNumber == innerTableNumber &&
  						outerColumnNumber == innerColumnNumber)
  					{
  						continue;
  					}

					// Put this predicate into the outer equivalence class
					middleP.setEquivalenceClass(outerEC);

					/* Now go to the inner list and see if there is an equijoin
					 * between inner and outer on innerColumnNumber and outerColumnNumber.
					 * If so, then we continue our walk across middle, otherwise we
					 * add a new equijoin to both the inner and outer lists before
					 * continuing to walk across middle.
					 */

					int newTableNumber;
					int newColumnNumber;
					Predicate innerP = null;
					PredicateList innerJCL = joinClauses[innerTableNumber];
					int innerIndex = 0;
					for ( ; innerIndex < innerJCL.size(); innerIndex++)
					{
						innerP = (Predicate) innerJCL.elementAt(innerIndex);

						// Skip over predicates with other equivalence classes
						if (innerP.getEquivalenceClass() != -1 &&
							innerP.getEquivalenceClass() != outerEC)
						{
							continue;
						}

						/* Now we see if the inner predicate completes the loop.
						 * If so, then add it to the outer equivalence class
						 * and stop.
						 */

						// Get the table and column numbers
						BinaryRelationalOperatorNode innerEquals = 
							(BinaryRelationalOperatorNode) innerP.getAndNode().getLeftOperand();
						ColumnReference iLeftCR = (ColumnReference) innerEquals.getLeftOperand();
						ColumnReference iRightCR = (ColumnReference) innerEquals.getRightOperand();

						if (iLeftCR.getTableNumber() == innerTableNumber)
						{
							if (iLeftCR.getColumnNumber() != innerColumnNumber)
							{
								continue;
							}
							newTableNumber = iRightCR.getTableNumber();
							newColumnNumber = iRightCR.getColumnNumber();
							innerCR = iLeftCR;
						}
						else
						{
							if (iRightCR.getColumnNumber() != innerColumnNumber)
							{
								continue;
							}
							newTableNumber = iLeftCR.getTableNumber();
							newColumnNumber = iLeftCR.getColumnNumber();
							innerCR = iRightCR;
						}

						// Did we find the equijoin between inner and outer
						if (newTableNumber == outerTableNumber &&
							newColumnNumber == outerColumnNumber)
						{
							break;
						}
					}

					// Did we find an equijoin on inner and outer
					if (innerIndex != innerJCL.size())
					{
						// match found
						// Put this predicate into the outer equivalence class
						innerP.setEquivalenceClass(outerEC);
						continue;
					}

					// No match, add new equijoin
					// Build a new predicate
					BinaryRelationalOperatorNode newEquals = (BinaryRelationalOperatorNode)
							getNodeFactory().getNode(
										C_NodeTypes.BINARY_EQUALS_OPERATOR_NODE,
										outerCR.getClone(),
										innerCR.getClone(),
										getContextManager());
					newEquals.bindComparisonOperator();
					/* Create the AND */
			        ValueNode trueNode = (ValueNode) getNodeFactory().getNode(
											C_NodeTypes.BOOLEAN_CONSTANT_NODE,
											Boolean.TRUE,
											getContextManager());
					AndNode newAnd = (AndNode) getNodeFactory().getNode(
														C_NodeTypes.AND_NODE,
														newEquals,
														trueNode,
														getContextManager());
					newAnd.postBindFixup();
					// Add a new predicate to both the equijoin clauses and this list
					JBitSet tableMap = new JBitSet(numTables);
					newAnd.categorize(tableMap, false);
					Predicate newPred = (Predicate) getNodeFactory().getNode(
													C_NodeTypes.PREDICATE,
													newAnd,
													tableMap,
													getContextManager());
					newPred.setEquivalenceClass(outerEC);
					addPredicate(newPred);
					/* Add the new predicate right after the outer position
					 * so that we can follow all of the predicates in equivalence
					 * classes before those that do not yet have equivalence classes.
					 */
					if (outerIndex != outerJCL.size() - 1)
					{
						outerJCL.insertElementAt(newPred, outerIndex + 1);
					}
					else
					{
						outerJCL.addElement(newPred);
					}
					innerJCL.addElement(newPred);
				}
			}
		}
	}

	 /**
	  * Perform transitive closure on search clauses.  We build a
	  * list of search clauses of the form:
	  *		<ColumnReference> <RelationalOperator> [<ConstantNode>]
	  * We also build a list of equijoin conditions of form:
	  *		<ColumnReference1> = <ColumnReference2>
	  * where both columns are from different tables in the same query block.
	  * For each search clause in the list, we search the equijoin list to see
	  * if there is an equijoin clause on the same column.  If so, then we 
      * search the search clause list for a search condition on the column 
      * being joined against with the same relation operator and constant.  If 
      * a match is found, then there is no need to add a new predicate.  
      * Otherwise, we add a new search condition on the column being joined 
      * with.  In either case, if the relational operator in the search
	  * clause is an "=" then we mark the equijoin clause as being redundant.
	  * Redundant equijoin clauses will be removed at the end of the search as 
      * they are * unnecessary.
	  *
	  * @param numTables			The number of tables in the query
	  * @param hashJoinSpecified	Whether or not user specified a hash join
	  *
	  * @return Nothing.
	  *
	  * @exception StandardException		Thrown on error
	  */
	 void searchClauseTransitiveClosure(int numTables, boolean hashJoinSpecified)
		 throws StandardException
	 {
		PredicateList	equijoinClauses = new PredicateList();
		PredicateList	searchClauses = new PredicateList();
		RelationalOperator	equalsNode = null;

		int size = size();
		for (int index = 0; index < size; index++)
		{
			Predicate		predicate = (Predicate) elementAt(index);
			AndNode			andNode = predicate.getAndNode();

			// Skip anything that's not a RelationalOperator
			if (! (andNode.getLeftOperand() instanceof RelationalOperator))
			{
				continue;
			}

			RelationalOperator operator = (RelationalOperator) andNode.getLeftOperand();
			// Is this an equijoin?
			if (((ValueNode)operator).isBinaryEqualsOperatorNode())
			{
				BinaryRelationalOperatorNode equals = (BinaryRelationalOperatorNode) operator;
				// Remember any equals node for redundancy check at end
				equalsNode = equals;
				ValueNode left = equals.getLeftOperand();
				ValueNode right = equals.getRightOperand();
				if ((left instanceof ColumnReference && right instanceof ColumnReference))
				{
					ColumnReference leftCR = (ColumnReference) left;
					ColumnReference rightCR = (ColumnReference) right;
					if (leftCR.getSourceLevel() == rightCR.getSourceLevel() &&
						leftCR.getTableNumber() != rightCR.getTableNumber())
					{
						equijoinClauses.addElement(predicate);
					}
					continue;
				}
			}

			// Is this a usable search clause?
			if (operator instanceof UnaryComparisonOperatorNode)
			{
				if (((UnaryComparisonOperatorNode) operator).getOperand() instanceof ColumnReference)
				{
					searchClauses.addElement(predicate);
				}
				continue;
			}
			else if (operator instanceof BinaryComparisonOperatorNode)
			{
				BinaryComparisonOperatorNode bcon = (BinaryComparisonOperatorNode) operator;
				ValueNode left = bcon.getLeftOperand();
				ValueNode right = bcon.getRightOperand();

				// Consider using variant type of the expression, instead of ConstantNode
				// or ParameterNode while porting this fix to trunk.
				if (left instanceof ColumnReference && 
					  (right instanceof ConstantNode || right instanceof ParameterNode))
				{
					searchClauses.addElement(predicate);
				}
				else if (right instanceof ConstantNode && left instanceof ColumnReference)
				{
					// put the ColumnReference on the left to simplify things
					bcon.swapOperands();
					searchClauses.addElement(predicate);
				}
				continue;
			}
		}

		// Nothing to do if no search clauses or equijoin clauses
		if (equijoinClauses.size() == 0 || searchClauses.size() == 0)
		{
			return;
		}

		/* Now we do the real work. 
		 * NOTE: We can append to the searchClauses while walking
		 * them, thus we cannot cache the value of size().
		 */
		for (int scIndex = 0; scIndex < searchClauses.size(); scIndex++)
		{
			ColumnReference searchCR;
			DataValueDescriptor searchODV = null;
			RelationalOperator ro = (RelationalOperator)
										((AndNode) 
											((Predicate) searchClauses.elementAt(scIndex)).getAndNode()).getLeftOperand();

			// Find the ColumnReference and constant value, if any, in the search clause
			if (ro instanceof UnaryComparisonOperatorNode)
			{
				searchCR = (ColumnReference) ((UnaryComparisonOperatorNode) ro).getOperand();
			}
			else
			{
				searchCR = (ColumnReference) ((BinaryComparisonOperatorNode) ro).getLeftOperand();

				// Don't get value for parameterNode since not known yet.
				if (((BinaryComparisonOperatorNode) ro).getRightOperand() instanceof ConstantNode)
				{
					ConstantNode currCN = (ConstantNode) ((BinaryComparisonOperatorNode) ro).getRightOperand();
					searchODV = (DataValueDescriptor) currCN.getValue();
				}
				else searchODV = null;
			}
			// Cache the table and column numbers of searchCR
			int tableNumber = searchCR.getTableNumber();
			int colNumber = searchCR.getColumnNumber();

			// Look for any equijoin clauses of interest
			int ejcSize = equijoinClauses.size();
			for (int ejcIndex = 0