predicatelist.java

derby database source code.good for you.

			andNode = (AndNode) predicate.getAndNode();

			// skip non-equality predicates
			ValueNode opNode = andNode.getLeftOperand();

			if (!opNode.optimizableEqualityNode(optTable, columnNumber, false))
				continue;

			// We found a match - make this entry first in the list
			if (index != 0)
			{
				removeElementAt(index);
				insertElementAt(predicate, 0);
			}
			
			return;
		}

		/* We should never get here since this method only called when we
		 * know that the desired equality predicate exists.
		 */
		if (SanityManager.DEBUG)
		{
			SanityManager.THROWASSERT(
				"Could  not find the expected equality predicate on column #" +
				columnNumber);
		}
	}

	private void orderUsefulPredicates(Optimizable optTable,
										ConglomerateDescriptor cd,
										boolean pushPreds,
										boolean nonMatchingIndexScan,
										boolean coveringIndexScan)
						throws StandardException
	{
		boolean[]	deletes;
		int[]		baseColumnPositions;
		boolean[]	isAscending;
		int			size = size();
		Predicate[]	usefulPredicates = new Predicate[size];
		int			usefulCount = 0;
		Predicate	predicate;


		/*
		** Clear all the scan flags for this predicate list, so that the
		** flags that get set are only for the given conglomerate.
		*/
		for (int index = 0; index < size; index++)
		{
			predicate = (Predicate) elementAt(index);

			predicate.clearScanFlags();
		}

		/*
		** RESOLVE: For now, not pushing any predicates for heaps.  When this
		** changes, we also need to make the scan in
		** TableScanResultSet.getCurrentRow() check the qualifiers to see
		** if the row still qualifies (there is a new method in ScanController
		** for this.
		*/

		/* Is a heap scan or a non-matching index scan on a covering index? */
		if ((cd == null) ||  (! cd.isIndex()) || 
			 (nonMatchingIndexScan && coveringIndexScan))
		{
			/*
			** For the heap, the useful predicates are the relational
			** operators that have a column from the table on one side,
			** and an expression that doesn't have a column from that
			** table on the other side.
			**
			** For the heap, all useful predicates become Qualifiers, so
			** they don't have to be in any order.
			**
			** NOTE: We can logically delete the current element when
			** traversing the Vector in the next loop,
			** so we must build an array of elements to
			** delete while looping and then delete them
			** in reverse order after completing the loop.
			*/
			Predicate[] preds = new Predicate[size];

			for (int index = 0; index < size; index++)
			{
				Predicate	pred = (Predicate) elementAt(index);

				/*
				** Skip over it if it's not a relational operator (this includes
				** BinaryComparisonOperators and IsNullNodes.
				*/
				RelationalOperator relop = pred.getRelop();

				if (relop == null)
                {
                    // possible OR clause, check for it.

                    if (!pred.isPushableOrClause(optTable))
                    {
                        // NOT an OR or AND, so go on to next predicate.
                        continue;
                    }
                }
                else
                {
                    if ( ! relop.isQualifier(optTable))
                    {
                        // NOT a qualifier, go on to next predicate.
                        continue;
                    }
                }

				pred.markQualifier();

				if (pushPreds)
				{
					/* Push the predicate down.
					 * (Just record for now.)
					 */
					if (optTable.pushOptPredicate(pred))
					{
						preds[index] = pred;
					}
				}
			}

			/* Now we actually push the predicates down */
			for (int inner = size - 1; inner >= 0; inner--)
			{
				if (preds[inner] != null)
				{
					removeOptPredicate(preds[inner]);
				}
			}

			return;
		}

		baseColumnPositions = cd.getIndexDescriptor().baseColumnPositions();
		isAscending = cd.getIndexDescriptor().isAscending();

		/*
		** Create an array of useful predicates.  Also, count how many
		** useful predicates there are.
		*/
		for (int index = 0; index < size; index++)
		{
			Predicate pred = (Predicate) elementAt(index);
			ColumnReference indexCol = null;
			int			indexPosition;

			/*
			** Skip over it if it's not a relational operator (this includes
			** BinaryComparisonOperators and IsNullNodes.
			*/
			RelationalOperator relop = pred.getRelop();

			/* if it's "in" operator, we generate dynamic start and stop key
			 * to improve index scan performance, beetle 3858.
			 */
			boolean isIn = false;
			InListOperatorNode inNode = null;

			if (relop == null)
			{
				if (pred.getAndNode().getLeftOperand() instanceof InListOperatorNode &&
					! ((InListOperatorNode)pred.getAndNode().getLeftOperand()).getTransformed())
				{
					isIn = true;
					inNode = (InListOperatorNode) pred.getAndNode().getLeftOperand();
				}
				else
					continue;
			}

			if ( !isIn && ! relop.isQualifier(optTable))
				continue;

			/* Look for an index column on one side of the relop */
			for (indexPosition = 0;
				indexPosition < baseColumnPositions.length;
				indexPosition++)
			{
				if (isIn)
				{
					if (inNode.getLeftOperand() instanceof ColumnReference)
					{
						indexCol = (ColumnReference) inNode.getLeftOperand();
						if ((optTable.getTableNumber() != indexCol.getTableNumber()) ||
								(indexCol.getColumnNumber() != baseColumnPositions[indexPosition]) ||
								inNode.selfReference(indexCol))
							indexCol = null;
					}
				}
				else
				{
					indexCol =
						relop.getColumnOperand(
							optTable,
							baseColumnPositions[indexPosition]);
				}
				if (indexCol != null)
					break;
			}
				
			/*
			** Skip over it if there is no index column on one side of the
			** operand.
			*/
			if (indexCol == null)
				continue;

			pred.setIndexPosition(indexPosition);

			/* Remember the useful predicate */
			usefulPredicates[usefulCount++] = pred;
		}

		/* We can end up with no useful
		 * predicates with a force index override -
		 * Each predicate is on a non-key column or both
		 * sides of the operator are columns from the same table.
		 * There's no predicates to push down, so return and we'll
		 * evaluate them in a PRN.
		 */
		if (usefulCount == 0)
			return;

		/* The array of useful predicates may have unused slots.  Shrink it */
		if (usefulPredicates.length > usefulCount)
		{
			Predicate[]	shrink = new Predicate[usefulCount];

			System.arraycopy(usefulPredicates, 0, shrink, 0, usefulCount);

			usefulPredicates = shrink;
		}

		/* Sort the array of useful predicates in index position order */
		java.util.Arrays.sort(usefulPredicates);

		/* Push the sorted predicates down to the Optimizable table */
		int		currentStartPosition = -1;
		boolean	gapInStartPositions = false;
		int		currentStopPosition = -1;
		boolean	gapInStopPositions = false;
		boolean seenNonEquals = false;
		int		firstNonEqualsPosition = -1;
		int		lastStartEqualsPosition = -1;

		/* beetle 4572. We need to truncate if necessary potential multi-column 
         * start key up to the first one whose start operator is GT, and make 
         * start operator GT;
		 * or start operator is GE if there's no such column.  We need to 
         * truncate if necessary potential multi-column stop key up to the 
         * first one whose stop operator is GE, and make stop operator GE; or 
         * stop operator is GT if no such column.
		 * eg., start key (a,b,c,d,e,f), potential start operators 
         * (GE,GE,GE,GT,GE,GT)
		 * then start key should really be (a,b,c,d) with start operator GT.
		 */
		boolean seenGE = false, seenGT = false;

		for (int i = 0; i < usefulCount; i++)
		{
			Predicate	        thisPred          = usefulPredicates[i];
			int			        thisIndexPosition = thisPred.getIndexPosition();
			boolean		        thisPredMarked    = false;
			RelationalOperator	relop             = thisPred.getRelop();
			int                 thisOperator      = -1;

			boolean             isIn              = false;
			InListOperatorNode  inNode            = null;

			if (relop == null)
			{
				isIn = true;
				inNode = (InListOperatorNode) 
                    thisPred.getAndNode().getLeftOperand();
			}
			else
            {
				thisOperator = relop.getOperator();
            }

			/* Allow only one start and stop position per index column */
			if (currentStartPosition != thisIndexPosition)
			{
				/*
				** We're working on a new index column for the start position.
				** Is it just one more than the previous position?
				*/
				if ((thisIndexPosition - currentStartPosition) > 1)
				{
					/*
					** There's a gap in the start positions.  Don't mark any
					** more predicates as start predicates.
					*/
					gapInStartPositions = true;
				}
				else if ((thisOperator == RelationalOperator.EQUALS_RELOP) ||
						 (thisOperator == RelationalOperator.IS_NULL_RELOP))
				{
					/* Remember the last "=" or IS NULL predicate in the start
					 * position.  (The sort on the predicates above has ensured
					 * that these predicates appear 1st within the predicates on
					 * a specific column.)
					 */
					lastStartEqualsPosition = thisIndexPosition;
				}

				if ( ! gapInStartPositions)
				{
					/*
					** There is no gap in start positions.  Is this predicate
					** useful as a start position?  This depends on the
					** operator - for example, indexCol = <expr> is useful,
					** while indexCol < <expr> is not useful with asc index
					** we simply need to reverse the logic for desc indexes
					**
					** The relop has to figure out whether the index column
					** is on the left or the right, so pass the Optimizable
					** table to help it.
					*/
					if (! seenGT &&
						(isIn || ((relop.usefulStartKey(optTable) && isAscending[thisIndexPosition]) ||
						(relop.usefulStopKey(optTable) && ! isAscending[thisIndexPosition]))))
					{
						thisPred.markStartKey();
						currentStartPosition = thisIndexPosition;
						thisPredMarked = true;
						seenGT = (thisPred.getStartOperator(optTable) == ScanController.GT);
					}
				}
			}

			/* Same as above, except for stop keys */
			if (currentStopPosition != thisIndexPosition)
			{
				if ((thisIndexPosition - currentStopPosition) > 1)
				{
					gapInStopPositions = true;
				}

				if ( ! gapInStopPositions)
				{
					if (! seenGE &&
						(isIn || ((relop.usefulStopKey(optTable) && isAscending[thisIndexPosition]) ||
						(relop.usefulStartKey(optTable) && ! isAscending[thisIndexPosition]))))
					{
						thisPred.markStopKey();
						currentStopPosition = thisIndexPosition;
						thisPredMarked = true;
						seenGE = (thisPred.getStopOperator(optTable) == ScanController.GE);
					}
				}
			}

			/* Mark this predicate as a qualifier if it is not a start/stop 
             * position or if we have already seen a previous column whose 
             * RELOPS do not include "=" or IS NULL.  For example, if
			 * the index is on (a, b, c) and the predicates are a > 1 and b = 1
             * and c = 1, then b = 1 and c = 1 also need to be a qualifications,
             * otherwise we may match on (2, 0, 3).
			 */
			if ( (! isIn) &&	// store can never treat "in" as qualifier
				 ((! thisPredMarked ) ||
				  (seenNonEquals && thisIndexPosition != firstNonEqualsPosition)
				 ) )
			{
				thisPred.markQualifier();
			}

			/* Remember if we have seen a column without an "=" */
			if (lastStartEqualsPosition != thisIndexPosition &&
				firstNonEqualsPosition == -1 &&
				(thisOperator != RelationalOperator.EQUALS_RELOP) &&
				(thisOperator != RelationalOperator.IS_NULL_RELOP))
			{
				seenNonEquals = true;
				/* Remember the column */
				firstNonEqualsPosition = thisIndexPosition;
			}

			if (pushPreds)
			{
				/* we only roughly detected that the predicate may be useful 
                 * earlier, it may turn out that it's not actually start/stop 
                 * key because another better predicate on the column is chosen.
                 * We don't want to push "in" in this case, since it's not a 
                 * qualifier.  Beetle 4316.
				 */
				if (isIn && ! thisPredMarked)
					continue;

				/*
				** Push the predicate down.  They get pushed down in the
				** order of the index.
				*/

				/* If this is an InListOperator predicate, make a copy of the
				 * the predicate (including the AND node contained within it)
				 * and then push the _copy_ (instead of the original) into
				 * optTable.  We need to do this to avoid having the exact
				 * same Predicate object (and in particular, the exact same
				 * AndNode object) be referenced in both optTable and this.v,
				 * which can lead to an infinite recursion loop when we get to
				 * restorePredicates(), and thus to stack overflow
				 * (beetle 4974).
				 */
				Predicate predToPush;
				if (isIn) 
                {
					AndNode andCopy = (AndNode) getNodeFactory().getNode(
										C_NodeTypes.AND_NODE,
										thisPred.getAndNode().getLeftOperand(),
										thisPred.getAndNode().getRightOperand(),
										getContextManager());
					andCopy.copyFields(thisPred.getAndNode());
					Predicate predCopy = (Predicate) getNodeFactory().getNode(
										C_NodeTypes.PREDICATE,
										andCopy,
										thisPred.getReferencedSet(),
										getContextManager());
					predCopy.copyFields(thisPred);
					predToPush = predCopy;
				}
				else
                {
					predToPush = thisPred;
                }

				if (optTable.pushOptPredicate(predToPush))
				{
					/* although we generated dynamic start and stop key for "in"
					 * , we still need this predicate for further restriction
					 */
					if (! isIn)