/*

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

   Licensed to the Apache Software Foundation (ASF) under one or more
   contributor license agreements.  See the NOTICE file distributed with
   this work for additional information regarding copyright ownership.
   The ASF licenses this file to you 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 java.util.HashSet;
import java.util.Set;
import org.apache.derby.iapi.error.StandardException;
import org.apache.derby.iapi.services.compiler.MethodBuilder;
import org.apache.derby.iapi.services.context.ContextManager;
import org.apache.derby.shared.common.sanity.SanityManager;
import org.apache.derby.iapi.sql.compile.Optimizable;
import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
import org.apache.derby.iapi.sql.compile.Visitor;
import org.apache.derby.iapi.store.access.ScanController;
import org.apache.derby.iapi.types.DataValueDescriptor;
import org.apache.derby.iapi.util.JBitSet;

/**
 * A Predicate represents a top level predicate.
 *
 */

public final class Predicate extends QueryTreeNode implements OptimizablePredicate,
                                                        Comparable<Predicate>
{
	/* Top of the predicate */
	AndNode		andNode;
	boolean		pushable;
	/* Bit map of referenced tables */
	JBitSet		referencedSet;
	/* Join clauses are placed into equivalence classes when applying transitive
	 * closure for join clauses.  This is useful for eliminating redundant predicates.
	 */
	int			equivalenceClass = -1;
	int			indexPosition;
	protected boolean startKey;
	protected boolean stopKey;
	protected boolean isQualifier;

	/* Hashtable used for tracking the search clause types that have been
	 * pushed through this predicate (if an equijoin) via transitive closure.
	 */
    private Set<Integer> searchClauses;

	// Whether or not this predicate has been scoped; see the
	// getPredScopedForResultSet() method of this class for more.
	private boolean scoped;

	/**
     * Constructor.
	 *
	 * @param andNode		The top of the predicate	 
	 * @param referencedSet	Bit map of referenced tables
     * @param cm            The context manager
	 */

    Predicate(AndNode andNode, JBitSet referencedSet, ContextManager cm)
	{
        super(cm);
        this.andNode = andNode;
		pushable = false;
        this.referencedSet = referencedSet;
		scoped = false;
	}

	/*
	 *  Optimizable interface
	 */

	/**
	 * @see org.apache.derby.iapi.sql.compile.OptimizablePredicate#getReferencedMap
	 */
	public JBitSet getReferencedMap()
	{
		return referencedSet;
	}

	/**
	 * @see org.apache.derby.iapi.sql.compile.OptimizablePredicate#hasSubquery
	 */
	public boolean hasSubquery()
	{
		/* RESOLVE - Currently, we record whether or not a predicate is pushable based
		 * on whether or not it contains a subquery or method call, but we do not
		 * record the underlying info.
		 */
		return ! pushable;
	}

	/**
	 * @see org.apache.derby.iapi.sql.compile.OptimizablePredicate#hasMethodCall
	 */
	public boolean hasMethodCall()
	{
		/* RESOLVE - Currently, we record whether or not a predicate is pushable based
		 * on whether or not it contains a subquery or method call, but we do not
		 * record the underlying info.
		 */
		return ! pushable;
	}

	/** @see OptimizablePredicate#markStartKey */
	public void markStartKey()
	{
		startKey = true;
	}

	/** @see OptimizablePredicate#isStartKey */
	public boolean isStartKey()
	{
		return startKey;
	}

	/** @see OptimizablePredicate#markStopKey */
	public void markStopKey()
	{
		stopKey = true;
	}

	/** @see OptimizablePredicate#isStopKey */
	public boolean isStopKey()
	{
		return stopKey;
	}

	/** @see OptimizablePredicate#markQualifier */
	public void markQualifier()
	{
		isQualifier = true;
	}

	/** @see OptimizablePredicate#isQualifier */
	public boolean isQualifier()
	{
		return isQualifier;
	}

	/** @see OptimizablePredicate#compareWithKnownConstant */
	public boolean compareWithKnownConstant(Optimizable optTable, boolean considerParameters)
	{
		boolean retval = false;
		RelationalOperator relop = getRelop();

		/* if this is for "in" operator node's dynamic start/stop key, relop is
		 * null, and it's not comparing with constant, beetle 3858
		 */
		if (!isRelationalOpPredicate())
			return false;

		if (relop.compareWithKnownConstant(optTable, considerParameters))
			retval = true;

		return retval;
	}

	public int hasEqualOnColumnList(int[] baseColumnPositions,
										Optimizable optTable)
		throws StandardException
	{
		RelationalOperator relop = getRelop();

		if (!isRelationalOpPredicate())
			return -1;
		
		if (!(relop.getOperator() == RelationalOperator.EQUALS_RELOP))
			return -1;
			
		for (int i = 0; i < baseColumnPositions.length; i++)
		{
			ColumnReference cr = relop.getColumnOperand(optTable, 
														baseColumnPositions[i]);
		
			if (cr == null)
				continue;
			
			if (relop.selfComparison(cr))
				continue;

			// If I made it thus far in the loop, we've found
			// something.
			return i;
		}
		
		return -1;
	}

	/**
	 * @see OptimizablePredicate#getCompareValue
	 *
	 * @exception StandardException		Thrown on error
	 */
	public DataValueDescriptor getCompareValue(Optimizable optTable)
		throws StandardException
	{
		if (SanityManager.DEBUG)
		{
			SanityManager.ASSERT(compareWithKnownConstant(optTable, true),
				"Cannot get the compare value if not comparing with a known constant.");
		}

		RelationalOperator relop = getRelop();

		return relop.getCompareValue(optTable);
	}

	/** @see OptimizablePredicate#equalsComparisonWithConstantExpression */
	public boolean equalsComparisonWithConstantExpression(Optimizable optTable)
	{
		boolean retval = false;

		if (isRelationalOpPredicate())
		{
			retval = getRelop().equalsComparisonWithConstantExpression(optTable);
		}

		return retval;
	}

	/** @see OptimizablePredicate#selectivity */
	public double selectivity(Optimizable optTable)
	throws StandardException
	{
		return andNode.getLeftOperand().selectivity(optTable);
	}

	/** @see OptimizablePredicate#getIndexPosition */
	public int getIndexPosition()
	{
		return indexPosition;
	}


	/* Comparable interface */

    public int compareTo(Predicate other)
	{
        Predicate otherPred = other;

		/* Not all operators are "equal". If the predicates are on the
		 * same key column, then a "=" opertor takes precedence over all
		 * other operators.  This ensures that the "=" will be both the start
		 * and stop predicates.  Otherwise, we could end up with it being one
		 * but not the other and get incorrect results.
		 *
		 * Also, we want "<>" to come after all the other operators.
		 * Other parts of the optimizer use the first predicate on an index
		 * column to determine the cost of using the index, so we want the
		 * "<>" to come last because it's not useful for limiting the scan.
		 *
		 * In other words, P1 is before() P2 if:
		 *		o  The P1.indexPosition < P2.indexPosition
		 *	or  o  P1.indexPosition == P2.indexPosition and
		 *		   P1's operator is ("=" or IS NULL) and
		 *		   P2's operator is not ("=" or IS NULL)
		 * or	o  P1.indexPosition == P2.indexPosition and
		 *		   P1's operator is not ("<>" or IS NOT NULL) and
		 *		   P2's operator is ("<>" or IS NOT NULL)
		 *
		 * (We have to impose an arbitrary, but reproducible ordering
		 * on the the "=" predicates on the same column, otherwise an
		 * ASSERTion, that after the predicates are order, Pn+1 is not
		 * before() Pn, will be violated.
		 */

		int otherIndexPosition = otherPred.getIndexPosition();

		if (indexPosition < otherIndexPosition)
			return -1;

		if (indexPosition > otherIndexPosition)
			return 1;

		// initialize these flags as if they are for "in" operator, then
		// change them if they are not
		//
		boolean thisIsEquals = false, otherIsEquals = false;
		boolean thisIsNotEquals = true, otherIsNotEquals = true;

		/* The call to "isRelationalOpPredicate()" will return false
		 * for a "probe predicate" because a probe predicate is really
		 * a disguised IN list. But when it comes to sorting, the probe
		 * predicate (which is of the form "<col> = ?") should be treated
		 * as an equality--i.e. it should have precedence over any non-
		 * equals predicate, per the comment at the start of this
		 * method.  So that's what we're checking here.
		 */
		if (this.isRelationalOpPredicate() || // this is not "in" or
			this.isInListProbePredicate())    // this is a probe predicate
		{
			int thisOperator = ((RelationalOperator)andNode.getLeftOperand()).getOperator();
			thisIsEquals = (thisOperator == RelationalOperator.EQUALS_RELOP ||
								thisOperator == RelationalOperator.IS_NULL_RELOP);
			thisIsNotEquals = (thisOperator == RelationalOperator.NOT_EQUALS_RELOP ||
								   thisOperator == RelationalOperator.IS_NOT_NULL_RELOP);
		}

		if (otherPred.isRelationalOpPredicate() || // other is not "in" or
			otherPred.isInListProbePredicate())    // other is a probe predicate
		{
			int	otherOperator = ((RelationalOperator)(otherPred.getAndNode().getLeftOperand())).getOperator();
			otherIsEquals = (otherOperator == RelationalOperator.EQUALS_RELOP ||
								 otherOperator == RelationalOperator.IS_NULL_RELOP);
			otherIsNotEquals = (otherOperator == RelationalOperator.NOT_EQUALS_RELOP ||
								 otherOperator == RelationalOperator.IS_NOT_NULL_RELOP);
		}

		boolean thisIsBefore = (thisIsEquals && ! otherIsEquals) || ( ! thisIsNotEquals && otherIsNotEquals);
		if (thisIsBefore)
			return -1;

		boolean otherIsBefore = (otherIsEquals && ! thisIsEquals) || ( ! otherIsNotEquals && thisIsNotEquals);
		if (otherIsBefore)
			return 1;
		return 0;
	}

	/**
	 * Return the andNode.
	 *
	 * @return AndNode	The andNode.
	 */
    AndNode getAndNode()
	{
		return andNode;
	}

	/**
	 * Set the andNode.
	 *
	 * @param andNode	The new andNode.
	 */
    void setAndNode(AndNode andNode)
	{
		this.andNode = andNode;
	}

	/**
	 * Return the pushable.
	 *
	 * @return boolean	Whether or not the predicate is pushable.
	 */
    boolean getPushable()
	{
		return pushable;
	}

	/**
	 * Set whether or not this predicate is pushable.  This method
	 * is intended for use when creating a copy of the predicate, ex
	 * for predicate pushdown.  We choose not to add this assignment
	 * to copyFields() because the comments for that method say that
	 * it should copy all fields _except_ the two specified at init
	 * time; "pushable" is one of the two specified at init time.
	 *
	 * @param pushable Whether or not the predicate is pushable.
	 */
    void setPushable(boolean pushable) {
		this.pushable = pushable;
	}

	/**
	 * Return the referencedSet.
	 *
	 * @return JBitSet	The referencedSet.
	 */
    JBitSet getReferencedSet()
	{
		return referencedSet;
	}

	/**
	 * Set the equivalence class, if any, for this predicate.
	 *
	 * @param equivalenceClass	The equivalence class for this predicate.
	 */
	void setEquivalenceClass(int equivalenceClass)
	{
		this.equivalenceClass = equivalenceClass;
	}

	/**
	 * Get the equivalenceClass for this predicate.
	 *
	 * @return The equivalenceClass for this predicate.
	 */
	int getEquivalenceClass()
	{
		return equivalenceClass;
	}

	/**
	 * Categorize this predicate.  Initially, this means
	 * building a bit map of the referenced tables for each predicate.
	 *
	 * @exception StandardException		Thrown on error
	 */
    void categorize() throws StandardException
	{
		pushable = andNode.categorize(referencedSet, false);
	}

	/**
	 * Get the RelationalOperator on the left side of the AND node, if
	 * there is one.  If the left side is not a RelationalOperator, return
	 * null.
	 *
	 * @return	The RelationalOperator on the left side of the AND node,
	 *			if any.
	 */
    RelationalOperator getRelop()
	{
		
		if (andNode.getLeftOperand() instanceof RelationalOperator)
		{
			return (RelationalOperator) andNode.getLeftOperand();
		}
		else
		{
			return null;
		}
	}

    final boolean isOrList()
    {
        return(andNode.getLeftOperand() instanceof OrNode);
    }

    /**
     * Is this predicate a possible Qualifier for store?
     * <p>
     * Current 2 types of predicates can be pushed to store: 
     *   1) RelationalOperator - 
     *      represented with by left operand as instance of RelationalOperator.
     *   2) A single And'd term of a list of OR terms
     *      represented by left operand as instance of OrNode.
     *
     * More checking specific operator's terms to see if they are finally
     * pushable to store.  In the final push at execution each term of the AND 
     * or OR must be a Relational operator with a column reference on one side 
     * and a constant on the other.
     *
     *
	 * @return true if term is wither a AND of a RelationalOperator, or an
     *              OR of one or more Relational Operators.
     *
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    final boolean isStoreQualifier()
    {
		if ((andNode.getLeftOperand() instanceof RelationalOperator) ||
		    (andNode.getLeftOperand() instanceof OrNode))
		{
            return(true);
		}
		else
		{
            return(false);
		}
    }

    /**
     * Is this predicate an pushable OR list?
     * <p>
     * Does the predicate represent a AND'd list of OR term's, all of which
     * are pushable.  To be pushable each of OR terms must be a legal 
     * qualifier, which is a column reference on one side of a Relational
     * operator and a constant on the other.
     *
	 * @return true if the predicate is a pushable set of OR clauses.
     *
     *
	 * @exception  StandardException  Standard exception policy.
     **/
    final boolean isPushableOrClause(Optimizable optTable)
        throws StandardException
	{
        boolean ret_val = true;

        if (andNode.getLeftOperand() instanceof OrNode)
        {
            QueryTreeNode node = andNode.getLeftOperand();

            while (node instanceof OrNode)
            {
                OrNode or_node = (OrNode) node;

                if (or_node.getLeftOperand() instanceof RelationalOperator)
                {
                    // if any term of the OR clause is not a qualifier, then
                    // reject the entire OR clause.
                    if (!((RelationalOperator) or_node.getLeftOperand()).
                        isQualifier(optTable, true))
                    {
                        // one of the terms is not a pushable Qualifier.
                        return(false);
                    }

                    node = or_node.getRightOperand();
                }
                else
                {
                    // one of the terms is not a RelationalOperator

                    return(false);
                }
            }

            return(true);
        }
        else
        {
            // Not an OR list
            return(false);
        }
	}

	/**
	 * Return whether or not this predicate has been used
	 * to add a new search clause of the specified type via transitive closure.
	 * NOTE: This can only be true if this is an equijoin
	 * between 2 column references.
	 *
	 * @param ro	The search clause that we are currently considering
	 *				as the source for transitive closure
	 *
	 * @return	Whether or not this predicate has been used
	 *			to add a new search clause of the specified type via transitive 
     *			closure.
	 */
	boolean transitiveSearchClauseAdded(RelationalOperator ro)
	{
        return searchClauses != null &&
            searchClauses.contains(ro.getOperator());
	}

	/**
	 * Mark this predicate as having been used to add a new predicate
	 * of the specified type via transitive closure on search clauses.
	 *
	 * @param ro	The search clause that we are currently considering
	 *				as the source for transitive closure
	 *
	 */
	void setTransitiveSearchClauseAdded(RelationalOperator ro)
	{
        if (searchClauses == null) {
            searchClauses = new HashSet<Integer>();
        }
		/* I have to remember that this ro has been added to this predicate as a
		 * transitive search clause.
		 */
        searchClauses.add(ro.getOperator());
	}

	/**
	 * Get the start operator for this predicate for a scan.
	 *
	 * @param optTable	The optimizable table, so we can tell which side of
	 *					the operator the search column is on.
	 *
	 * @return	The start operator for a start key on this column.
	 */
	int getStartOperator(Optimizable optTable)
	{
		if (SanityManager.DEBUG)
		{
			SanityManager.ASSERT(startKey, "Getting a start operator from a Predicate that's not a start key.");
		}

		/* if it's for "in" operator's dynamic start key, operator is GE,
		 * beetle 3858
		 */
		if (andNode.getLeftOperand() instanceof InListOperatorNode)
			return ScanController.GE;

		return getRelop().getStartOperator(optTable);
	}

	int getStopOperator(Optimizable optTable)
	{
		if (SanityManager.DEBUG)
		{
			SanityManager.ASSERT(stopKey, "Getting a stop operator from a Predicate that's not a stop key.");
		}

		 /* if it's for "in" operator's dynamic stop key, operator is GT,
		  * beetle 3858
		  */
		if (andNode.getLeftOperand() instanceof InListOperatorNode)
			return ScanController.GT;

		return getRelop().getStopOperator(optTable);
	}

	/**
	 * Set the position of the index column that this predicate restricts
	 *
	 * @param indexPosition	The position of the index column that this
	 *						predicate restricts.
	 */
	void setIndexPosition(int indexPosition)
	{
		this.indexPosition = indexPosition;
	}

	/**
	 * Clear the start/stop position and qualifier flags
	 */
	void clearScanFlags()
	{
		startKey = false;
		stopKey = false;
		isQualifier = false;
	}

	void generateExpressionOperand(Optimizable optTable,
										int columnPosition,
										ExpressionClassBuilder acb,
										MethodBuilder mb)
				throws StandardException
	{
		getRelop().generateExpressionOperand(optTable,
													columnPosition,
													acb,
													mb);
	}

	/**
	 * Convert this object to a String.  See comments in QueryTreeNode.java
	 * for how this should be done for tree printing.
	 *
	 * @return	This object as a String
	 */
    @Override
	public String toString()
	{
		if (SanityManager.DEBUG)
		{
			return binaryRelOpColRefsToString() + "\nreferencedSet: " +
				referencedSet  + "\n" + "pushable: " + pushable + "\n" +
				"isQualifier: " + isQualifier + "\n" +
				super.toString();
		}
		else
		{
			return "";
		}
	}

	/**
	 * Get a string version of the column references for this predicate
	 * IF it's a binary relational operator.  We only print out the
	 * names of the operands if they are column references; otherwise
	 * we just print a dummy value.  This is for debugging purposes
	 * only--it's a convenient way to see what columns the predicate
	 * is referencing, especially when tracing through code and printing
	 * assert failure.
	 */
    String binaryRelOpColRefsToString()
	{
		// We only consider binary relational operators here.
		if (!(getAndNode().getLeftOperand()
			instanceof BinaryRelationalOperatorNode))
		{
			return "";
		}

		final String DUMMY_VAL = "<expr>";
        java.lang.StringBuilder sBuf = new java.lang.StringBuilder();
		BinaryRelationalOperatorNode opNode =
			(BinaryRelationalOperatorNode)getAndNode().getLeftOperand();

		// Get left operand's name.
		if (opNode.getLeftOperand() instanceof ColumnReference)
		{
			sBuf.append(
                    ((ColumnReference)opNode.getLeftOperand()).getTableName());
            sBuf.append('.');
            sBuf.append(
                    ((ColumnReference)opNode.getLeftOperand()).getColumnName());
		}
		else
			sBuf.append(DUMMY_VAL);

		// Get the operator type.
        sBuf.append(' ');
        sBuf.append(opNode.operator);
        sBuf.append(' ');

		// Get right operand's name.
		if (opNode.getRightOperand() instanceof ColumnReference) {
			sBuf.append(
				((ColumnReference)opNode.getRightOperand()).getTableName() +
				"." +
				((ColumnReference)opNode.getRightOperand()).getColumnName()
			);
		}
		else
			sBuf.append(DUMMY_VAL);

		return sBuf.toString();
	}

	/**
	 * Prints the sub-nodes of this object.  See QueryTreeNode.java for
	 * how tree printing is supposed to work.
	 *
	 * @param depth		The depth of this node in the tree
	 */
    @Override
    void printSubNodes(int depth)
	{
		if (SanityManager.DEBUG)
		{
			printLabel(depth, "andNode: ");
			andNode.treePrint(depth + 1);
			super.printSubNodes(depth);
		}
	}

	/**
	 * Accept the visitor for all visitable children of this node.
	 * 
	 * @param v the visitor
	 *
	 * @exception StandardException on error
	 */
    @Override
	void acceptChildren(Visitor v)
		throws StandardException
	{
		super.acceptChildren(v);

		if (andNode != null)
		{
			andNode = (AndNode)andNode.accept(v);
		}
	}

	/**
	 * Copy all fields of this Predicate (except the two that
	 * are set from 'init').
	 *
	 */

    void copyFields(Predicate otherPred) {

		this.equivalenceClass = otherPred.getEquivalenceClass();
		this.indexPosition = otherPred.getIndexPosition();
		this.startKey = otherPred.isStartKey();
		this.stopKey = otherPred.isStopKey();
		this.isQualifier = otherPred.isQualifier();
        this.searchClauses = otherPred.searchClauses;

	}

	/**
	 * Determine whether or not this predicate is eligible for
	 * push-down into subqueries.  Right now the only predicates
	 * we consider to be eligible are those which 1) are Binary
	 * Relational operator nodes and 2) have a column reference
	 * on BOTH sides, each of which has a reference to a base
	 * table somewhere beneath it.
	 *
	 * @return Whether or not this predicate is eligible to be
	 *  pushed into subqueries.
	 */
	protected boolean pushableToSubqueries()
		throws StandardException
	{
		if (!isJoinPredicate())
			return false;

		// Make sure both column references ultimately point to base
		// tables.  If, for example, either column reference points to a
		// a literal or an aggregate, then we do not push the predicate.
		// This is because pushing involves remapping the references--
		// but if the reference doesn't have a base table beneath it,
		// the notion of "remapping" it doesn't (seem to) apply.  RESOLVE:
		// it might be okay to make the "remap" operation a no-op for
		// such column references, but it's not clear whether that's
		// always a safe option; further investigation required.

		BinaryRelationalOperatorNode opNode =
			(BinaryRelationalOperatorNode)getAndNode().getLeftOperand();

		JBitSet tNums = new JBitSet(getReferencedSet().size());
		BaseTableNumbersVisitor btnVis = new BaseTableNumbersVisitor(tNums);
		opNode.getLeftOperand().accept(btnVis);
		if (tNums.getFirstSetBit() == -1)
			return false;

		tNums.clearAll();
		opNode.getRightOperand().accept(btnVis);
		if (tNums.getFirstSetBit() == -1)
			return false;

		return true;
	}

	/**
	 * Is this predicate a join predicate?  In order to be so,
	 * it must be a binary relational operator node that has
	 * a column reference on both sides.
	 *
	 * @return Whether or not this is a join predicate.
	 */
	protected boolean isJoinPredicate()
	{
		// If the predicate isn't a binary relational operator,
		// then it's not a join predicate.
		if (!(getAndNode().getLeftOperand()
			instanceof BinaryRelationalOperatorNode))
		{
			return false;
		}

		BinaryRelationalOperatorNode opNode =
			(BinaryRelationalOperatorNode)getAndNode().getLeftOperand();

		// If both sides are column references AND they point to different
		// tables, then this is a join pred.
		return ((opNode.getLeftOperand() instanceof ColumnReference) &&
			(opNode.getRightOperand() instanceof ColumnReference) &&
			(((ColumnReference)opNode.getLeftOperand()).getTableNumber() !=
			((ColumnReference)opNode.getRightOperand()).getTableNumber()));
	}

	/**
	 * If this predicate's operator is a BinaryRelationalOperatorNode,
	 * then look at the operands and return a new, equivalent predicate
	 * that is "scoped" to the received ResultSetNode.  By "scoped" we
	 * mean that the operands, which shold be column references, have been
	 * mapped to the appropriate result columns in the received RSN.
	 * This is useful for pushing predicates from outer queries down
	 * into inner queries, in which case the column references need
	 * to be remapped.
	 *
	 * For example, let V1 represent
	 *
	 *    select i,j from t1 UNION select i,j from t2
	 * 
	 * and V2 represent
	 *
	 *    select a,b from t3 UNION select a,b from t4
	 * 
	 * Then assume we have the following query:
	 *
	 *    select * from V1, V2 where V1.j = V2.b
	 *
	 * Let's further assume that this Predicate object represents the
	 * "V1.j = V2.b" operator and that the childRSN we received
	 * as a parameter represents one of the subqueries to which we
	 * want to push the predicate; let's say it's:
	 *
	 *    select i,j from t1
	 *
	 * Then this method will return a new predicate whose binary
	 * operator represents the expression "T1.j = V2.b" (that is, V1.j
	 * will be mapped to the corresponding column in T1).  For more on
	 * how that mapping is made, see the "getScopedOperand()" method
	 * in BinaryRelationalOperatorNode.java.
	 *
	 * ASSUMPTION: We should only get to this method if we know that
	 * at least one operand in this predicate can and should be mapped
	 * to the received childRSN.  For an example of where that check is
	 * made, see the pushOptPredicate() method in SetOperatorNode.java.
	 *
	 * @param parentRSNsTables Set of all table numbers referenced by
	 *  the ResultSetNode that is _parent_ to the received childRSN.
	 *  We need this to make sure we don't scope the operands to a
	 *  ResultSetNode to which they don't apply.
	 * @param childRSN The result set node for which we want to create
	 *  a scoped predicate.
	 * @param whichRC If not -1 then this tells us which ResultColumn
	 *  in the received childRSN we need to use for the scoped predicate;
	 *  if -1 then the column position of the scoped column reference
	 *  will be stored in this array and passed back to the caller.
	 * @return A new predicate whose operands have been scoped to the
	 *  received childRSN.
	 */
	protected Predicate getPredScopedForResultSet(
		JBitSet parentRSNsTables, ResultSetNode childRSN,
		int [] whichRC) throws StandardException
	{
		// We only deal with binary relational operators here.
		if (!(getAndNode().getLeftOperand()
			instanceof BinaryRelationalOperatorNode))
		{
			return this;
		}

		// The predicate must have an AndNode in CNF, so we
		// need to create an AndNode representing:
		//    <scoped_bin_rel_op> AND TRUE
		// First create the boolean constant for TRUE.
        ValueNode trueNode = new BooleanConstantNode(true, getContextManager());

		BinaryRelationalOperatorNode opNode =
			(BinaryRelationalOperatorNode)getAndNode().getLeftOperand();

		// Create a new op node with left and right operands that point
		// to the received result set's columns as appropriate.
		BinaryRelationalOperatorNode newOpNode = 
            new BinaryRelationalOperatorNode(
                opNode.kind,
				opNode.getScopedOperand(
					BinaryRelationalOperatorNode.LEFT,
					parentRSNsTables,
					childRSN,
					whichRC),
				opNode.getScopedOperand(
					BinaryRelationalOperatorNode.RIGHT,
					parentRSNsTables,
					childRSN,
					whichRC),
                opNode.getForQueryRewrite(),
				getContextManager());

		// Bind the new op node.
		newOpNode.bindComparisonOperator();

		// Create and bind a new AND node in CNF form,
		// i.e. "<newOpNode> AND TRUE".
        AndNode newAnd = new AndNode(newOpNode, trueNode, getContextManager());
		newAnd.postBindFixup();

		// Categorize the new AND node; among other things, this
		// call sets up the new operators's referenced table map,
		// which is important for correct pushing of the new
		// predicate.
		JBitSet tableMap = new JBitSet(
			childRSN.getReferencedTableMap().size());
		newAnd.categorize(tableMap, false);

		// Now put the pieces together to get a new predicate.
        Predicate newPred =
                new Predicate(newAnd, tableMap, getContextManager());

		// Copy all of this predicates other fields into the new predicate.
		newPred.clearScanFlags();
		newPred.copyFields(this);
		newPred.setPushable(getPushable());

		// Take note of the fact that the new predicate is scoped for
		// the sake of pushing; we need this information during optimization
		// to figure out what we should and should not "pull" back up.
		newPred.markAsScopedForPush();
		return newPred;
	}

	/**
	 * Indicate that this predicate is a scoped copy of some other
	 * predicate (i.e. it was created as the result of a call to
	 * getPredScopedForResultSet() on some other predicate).
	 */
	protected void markAsScopedForPush() {
		this.scoped = true;
	}

	/**
	 * Return whether or not this predicate is a scoped copy of
	 * another predicate.
	 */
	protected boolean isScopedForPush() {
		return scoped;
	}

	/**
	 * When remapping a "normal" (i.e. non-scoped) predicate both
	 * of the predicate's operands are remapped and that's it.
	 * But when remapping a scoped predicate, things are slightly
	 * different.  This method handles remapping of scoped predicates.
	 *
	 * We know that, for a scoped predicate, exactly one operand has
	 * been scoped for a specific target result set; the other operand
	 * is pointing to some other instance of FromTable with which the
	 * target result set is to be joined (see getScopedOperand() in
	 * BinaryRelationalOperatorNode.java).  For every level of the
	 * query through which the scoped predicate is pushed, we have
	 * to perform a remap operation of the scoped operand.  We do
	 * *not*, however, remap the non-scoped operand.  The reason
	 * is that the non-scoped operand is already pointing to the
	 * result set against which it must be evaluated.  As the scoped
	 * predicate is pushed down the query tree, the non-scoped
	 * operand should not change where it's pointing and thus should
	 * not be remapped.  For example, assume we have a query whose
	 * tree has the following form:
	 *
	 *               SELECT[0] 
	 *                /     \ 
	 *              PRN      PRN 
	 *               |        |
	 *          SELECT[4]   UNION
	 *           |           /   \ 
	 *          PRN     SELECT[1]  SELECT[2] 
	 *           |         |          | 
	 *       [FBT:T1]     PRN        PRN 
	 *                     |          |
	 *                SELECT[3]  [FromBaseTable:T2]
	 *                     |
	 *                    PRN
	 *                     |
	 *             [FromBaseTable:T3]
	 *
	 * Assume also that we have some predicate "SELECT[4].i = <UNION>.j".
	 * If the optimizer decides to push the predicate to the UNION
	 * node, it (the predicate) will be scoped to the UNION's children,
	 * yielding something like "SELECT[4].i = SELECT[1].j" for the
	 * left child and "SELECT[4].i = SELECT[2].j" for the right child.
	 * These scoped predicates will then be pushed to the PRNs above
	 * SELECT[3] and T2, respectively.  As part of that pushing
	 * process a call to PRN.pushOptPredicate() will occur, which
	 * brings us to this method.  So let's assume we're here for
	 * the scoped predicate "SELECT[4].i = SELECT[1].j".  Then we want
	 * to remap the scoped operand, "SELECT[1].j", so that it will
	 * point to the correct column in "SELECT[3]".  We do NOT, however,
	 * want to remap the non-scoped operand "SELECT[4].i" because that
	 * operand is already pointing to the correct result set--namely,
	 * to a column in SELECT[4].  That non-scoped operand should not
	 * change regardless of how far down the UNION subtree the scoped
	 * predicate is pushed.
	 * 
	 * If we did try to remap the non-scoped operand, it would end up
	 * pointing to result sets too low in the tree, which could lead to
	 * execution-time errors.  So when we remap a scoped predicate, we
	 * have to make sure we only remap the scoped operand.  That's what
	 * this method does.
	 *
	 * @return True if this predicate is a scoped predicate, in which
	 *  case we performed a one-sided remap.  False if the predicate is
	 *  not scoped; the caller can then make the calls to perform a
	 *  "normal" remap on this predicate.
	 */
	protected boolean remapScopedPred()
	{
		if (!scoped)
			return false;

		/* Note: right now the only predicates we scope are those
		 * which are join predicates and all scoped predicates will
		 * have the same relational operator as the predicates from
		 * which they were scoped.  Thus if we get here, we know
		 * that andNode's leftOperand must be an instance of
		 * BinaryRelationalOperatorNode (and therefore the following
		 * cast is safe).
		 */
		BinaryRelationalOperatorNode binRelOp =
			(BinaryRelationalOperatorNode)andNode.getLeftOperand();

        ValueNode operand;

		if (SanityManager.DEBUG)
		{
			/* If this predicate is scoped then one (and only one) of
			 * its operands should be scoped.  Note that it's possible
			 * for an operand to be scoped to a non-ColumnReference
			 * value; if either operand is not a ColumnReference, then
			 * that operand must be the scoped operand.
			 */
			operand = binRelOp.getLeftOperand();
			boolean leftIsScoped =
				!(operand instanceof ColumnReference) ||
					((ColumnReference)operand).isScoped();

			operand = binRelOp.getRightOperand();
			boolean rightIsScoped =
				!(operand instanceof ColumnReference) ||
					((ColumnReference)operand).isScoped();

			SanityManager.ASSERT(leftIsScoped ^ rightIsScoped,
				"All scoped predicates should have exactly one scoped " +
				"operand, but '" + binaryRelOpColRefsToString() +
				"' has " + (leftIsScoped ? "TWO" : "NONE") + ".");
		}

		// Find the scoped operand and remap it.
		operand = binRelOp.getLeftOperand();
		if ((operand instanceof ColumnReference) &&
			((ColumnReference)operand).isScoped())
		{
			// Left operand is the scoped operand.
			((ColumnReference)operand).remapColumnReferences();
		}
		else
		{
			operand = binRelOp.getRightOperand();
			if ((operand instanceof ColumnReference) &&
				((ColumnReference)operand).isScoped())
			{
				// Right operand is the scoped operand.
				((ColumnReference)operand).remapColumnReferences();
			}

			// Else scoped operand is not a ColumnReference, which
			// means it can't (and doesn't need to) be remapped. So
			// just fall through and return.
		}

		return true;
	}

	/**
	 * Return true if this predicate is scoped AND the scoped
	 * operand is a ColumnReference that points to a source result
	 * set.  If the scoped operand is not a ColumnReference that
	 * points to a source result set then it must be pointing to
	 * some kind of expression, such as a literal (ex. 'strlit'),
	 * an aggregate value (ex. "count(*)"), or the result of a
	 * function (ex. "sin(i)") or operator (ex. "i+1").
	 *
	 * This method is used when pushing predicates to determine how
	 * far down the query tree a scoped predicate needs to be pushed
	 * to allow for successful evaluation of the scoped operand.  If
	 * the scoped operand is not pointing to a source result set
	 * then it should not be pushed any further down tree.  The reason
	 * is that evaluation of the expression to which the operand is
	 * pointing may depend on other values from the current level
	 * in the tree (ex. "sin(i)" depends on the value of "i", which
	 * could be a column at the predicate's current level).  If we
	 * pushed the predicate further down, those values could become
	 * inaccessible, leading to execution-time errors.
	 *
	 * If, on the other hand, the scoped operand *is* pointing to
	 * a source result set, then we want to push it further down
	 * the tree until it reaches that result set, which allows
	 * evaluation of this predicate to occur as close to store as
	 * possible.  This method doesn't actually do the push, it just
	 * returns "true" and then the caller can push as appropriate.
	 */
	protected boolean isScopedToSourceResultSet()
		throws StandardException
	{
		if (!scoped)
			return false;

		/* Note: right now the only predicates we scope are those
		 * which are join predicates and all scoped predicates will
		 * have the same relational operator as the predicates from
		 * which they were scoped.  Thus if we get here, we know
		 * that andNode's leftOperand must be an instance of
		 * BinaryRelationalOperatorNode (and therefore the following
		 * cast is safe).
		 */
		BinaryRelationalOperatorNode binRelOp =
			(BinaryRelationalOperatorNode)andNode.getLeftOperand();

		ValueNode operand = binRelOp.getLeftOperand();

		/* If operand isn't a ColumnReference then is must be the
		 * scoped operand.  This is because both operands have to
		 * be column references in order for scoping to occur (as
		 * per pushableToSubqueries()) and only the scoped operand
		 * can change (esp. can become a non-ColumnReference) as
		 * part of the scoping process.  And since it's not a
		 * ColumnReference it can't be "a ColumnReference that
		 * points to a source result set", so return false.
		 */
		if (!(operand instanceof ColumnReference))
			return false;

		/* If the operand is a ColumnReference and is scoped,
		 * then see if it is pointing to a ResultColumn whose
		 * expression is either another a CR or a Virtual
		 * ColumnNode.  If it is then that operand applies
		 * to a source result set further down the tree and
		 * thus we return true.
		 */
        ValueNode exp;
		ColumnReference cRef = (ColumnReference)operand;
		if (cRef.isScoped())
		{
			exp = cRef.getSource().getExpression();
			return ((exp instanceof VirtualColumnNode) ||
				(exp instanceof ColumnReference));
		}

		operand = binRelOp.getRightOperand();
		if (!(operand instanceof ColumnReference))
			return false;

		cRef = (ColumnReference)operand;
		if (SanityManager.DEBUG)
		{
			// If we got here then the left operand was NOT the scoped
			// operand; make sure the right one is scoped, then.
			SanityManager.ASSERT(cRef.isScoped(),
				"All scoped predicates should have exactly one scoped " +
				"operand, but '" + binaryRelOpColRefsToString() +
				"has NONE.");
		}

		exp = cRef.getSource().getExpression();
		return ((exp instanceof VirtualColumnNode) ||
			(exp instanceof ColumnReference));
	}

	/**
	 * Return whether or not this predicate corresponds to a legitimate
	 * relational operator.
	 *
	 * @return False if there is no relational operator for this predicate
	 *  OR if this predicate is an internal "probe predicate" (in which
	 *  case it "looks" like we have a relational operator but in truth
	 *  it's a disguised IN-list operator). True otherwise.
	 */
	protected boolean isRelationalOpPredicate()
	{
		/* The isRelationalOperator() method on the ValueNode
		 * interface tells us what we need to know, so all we have
		 * to do is call that method on the left child of our AND node.
		 * Note that BinaryRelationalOperatorNode.isRelationalOperator()
		 * includes logic to determine whether or not it (the BRON) is
		 * really a disguised IN-list operator--and if so, it will
		 * return false (which is what we want).
		 */
		return andNode.getLeftOperand().isRelationalOperator();
	}

	/**
	 * Return whether or not this predicate is an IN-list probe
	 * predicate.
	 */
	protected boolean isInListProbePredicate()
	{
		/* The isInListProbeNode() method on the ValueNode interface
		 * tells us what we need to know, so all we have to do is call
		 * that method on the left child of our AND node.
		 */
		return andNode.getLeftOperand().isInListProbeNode();
	}

	/**
	 * If this predicate corresponds to an IN-list, return the underlying
	 * InListOperatorNode from which it was built.  There are two forms
	 * to check for:
	 *
	 *  1. This predicate is an IN-list "probe predicate", in which case
	 *     the underlying InListOpNode is stored within the binary relational
	 *     operator that is the left operand of this predicate's AND node.
	 *
	 *  2. This predicate corresponds to an IN-list that could _not_ be
	 *     transformed into a "probe predicate" (i.e. the IN-list contains
	 *     one or more non-parameter, non-constant values). In that case
	 *     the underlying InListOpNode is simply the left operand of
	 *     this predicate's AND node.
	 *
	 * If this predicate does not correspond to an IN-list in any way,
	 * this method will return null.
	 */
	protected InListOperatorNode getSourceInList()
	{
		return getSourceInList(false);
	}

	/**
	 * Does the work of getSourceInList() above, but can also be called
	 * directly with an argument to indicate whether or not we should
	 * limit ourselves to probe predicates.
	 *
	 * @param probePredOnly If true, only get the source IN list for this
	 *   predicate *if* it is an IN-list probe predicate.  If false,
	 *   return the underlying InListOperatorNode (if it exists) regardless
	 *   of whether this is a probe predicate or an un-transformed IN-list
	 *   pred.
	 * 
	 * @return Underlying InListOp for this predicate (depending on
	 *   the value of probePredOnly), or null if this predicate does
	 *   not correspond to an IN-list in any way.
	 */
	protected InListOperatorNode getSourceInList(boolean probePredOnly)
	{
		ValueNode vn = andNode.getLeftOperand();
		if (isInListProbePredicate())
			return ((BinaryRelationalOperatorNode)vn).getInListOp();

		if (probePredOnly)
			return null;

		if (vn instanceof InListOperatorNode)
			return (InListOperatorNode)vn;

		return null;
	}
}
