Package org.apache.derby.impl.sql.compile

Class SubqueryNode

  • All Implemented Interfaces:
    Visitable
    class SubqueryNode
extends ValueNode
    A SubqueryNode represents a subquery. Subqueries return values to their outer queries. An quantified subquery is one that appears under a quantified operator (like IN or EXISTS) - quantified subqueries can return more than one value per invocation. An expression subquery is one that is not directly under a quantified operator - expression subqueries are allowed to return at most one value per invocation (returning no value is considered to be equivalent to returning NULL). There are a large number of subquery types. Because of the large number of types, and the large amount of shared code, we have decided to have 1 SubqueryNode without any subclasses. The subquery type (and operator) is encoded in the subqueryType field. The query optimizer is responsible for optimizing subqueries, and also for transforming them so that code can be generated for them. The optimizer may eliminate some subqueries by transforming them into joins, or it may change the internal form of a subquery (for example, transforming 'where x in (select y from z where ...)' into 'where (select true from z where x = y and ...)'). Note that aggregates present some additional issues. A transformation such as:
      where x in (SELECT expression FROM z)
    has to be treated specially if expression has an aggregate. We change it to:
      where x = (SELECT true FROM (SELECT MAX(x) FROM z) WHERE SQLCOL1 = y)

    • Constructor Detail

      • SubqueryNode

        SubqueryNode​(ResultSetNode resultSet,
             int subqueryType,
             ValueNode leftOperand,
             OrderByList orderCols,
             ValueNode offset,
             ValueNode fetchFirst,
             boolean hasJDBClimitClause,
             ContextManager cm)
        Constructor.
        Parameters:
        resultSet - The ResultSetNode for the subquery
        subqueryType - The type of the subquery
        leftOperand - The left operand, if any, of the subquery
        orderCols - ORDER BY list
        offset - OFFSET n ROWS
        fetchFirst - FETCH FIRST n ROWS ONLY
        hasJDBClimitClause - True if the offset/fetchFirst clauses come from JDBC limit/offset escape syntax
        cm - Context Manager

    • Method Detail

      • toString

        public java.lang.String toString()
        Convert this object to a String. See comments in QueryTreeNode.java for how this should be done for tree printing.
        Overrides:
        toString in class ValueNode
        Returns:
        This object as a String

      • printSubNodes

        void printSubNodes​(int depth)
        Prints the sub-nodes of this object. See QueryTreeNode.java for how tree printing is supposed to work.
        Overrides:
        printSubNodes in class QueryTreeNode
        Parameters:
        depth - The depth of this node in the tree

      • getResultSet

        ResultSetNode getResultSet()
        Return the resultSet for this SubqueryNode.
        Returns:
        ResultSetNode underlying this SubqueryNode.

      • getSubqueryType

        int getSubqueryType()
        Return the type of this subquery.
        Returns:
        int Type of this subquery.

      • setSubqueryType

        void setSubqueryType​(int subqueryType)
        Set the type of this subquery.
        Parameters:
        subqueryType - of this subquery.

      • setPointOfAttachment

        void setPointOfAttachment​(int pointOfAttachment)
                   throws StandardException
        Set the point of attachment of this subquery.
        Parameters:
        pointOfAttachment - The point of attachment of this subquery.
        Throws:
        StandardException - Thrown on error

      • getUnderTopAndNode

        boolean getUnderTopAndNode()
        Return whether or not this subquery is immediately under a top level AndNode.
        Returns:
        boolean Whether or not this subquery is immediately under a top level AndNode.

      • getPointOfAttachment

        int getPointOfAttachment()
        Get the ResultSet # for the point of attachment for this SubqueryNode.
        Returns:
        int The ResultSet # for the point of attachment

      • getPreprocessed

        boolean getPreprocessed()
        Get whether or not this SubqueryNode has already been preprocessed.
        Returns:
        Whether or not this SubqueryNode has already been preprocessed.

      • setParentComparisonOperator

        void setParentComparisonOperator​(BinaryComparisonOperatorNode parent)
        Set the parent BCON. Useful when considering flattening expression subqueries.
        Parameters:
        parent - The parent BCON.

      • bindExpression

        ValueNode bindExpression​(FromList fromList,
                         SubqueryList subqueryList,
                         java.util.List<AggregateNode> aggregates)
                  throws StandardException
        Bind this expression. This means binding the sub-expressions, as well as figuring out what the return type is for this expression.
        Overrides:
        bindExpression in class ValueNode
        Parameters:
        fromList - The FROM list for the query this expression is in, for binding columns. NOTE: fromList will be null if the subquery appears in a VALUES clause.
        subqueryList - The subquery list being built as we find SubqueryNodes
        aggregates - The aggregate list being built as we find AggregateNodes
        Returns:
        The new top of the expression tree.
        Throws:
        StandardException - Thrown on error

      • preprocess

        ValueNode preprocess​(int numTables,
                     FromList outerFromList,
                     SubqueryList outerSubqueryList,
                     PredicateList outerPredicateList)
              throws StandardException
        Preprocess an expression tree. We do a number of transformations here (including subqueries, IN lists, LIKE and BETWEEN) plus subquery flattening. NOTE: This is done before the outer ResultSetNode is preprocessed.
        Overrides:
        preprocess in class ValueNode
        Parameters:
        numTables - Number of tables in the DML Statement
        outerFromList - FromList from outer query block
        outerSubqueryList - SubqueryList from outer query block
        outerPredicateList - PredicateList from outer query block
        Returns:
        The modified expression
        Throws:
        StandardException - Thrown on error

      • singleFromBaseTable

        private FromBaseTable singleFromBaseTable​(FromList fromList)
        Does the from list from the subquery contain a single entry which is a FBT or a PRN/FBT.
        Parameters:
        fromList - The from list from the subquery
        Returns:
        the FromBaseTable if the from list from the subquery contains a single entry which is a FBT or a PRN/FBT, or null if the subquery does not contain a single FBT

      • rightOperandFlattenableToNotExists

        private boolean rightOperandFlattenableToNotExists​(int numTables,
                                                   FromBaseTable fbt)
                                            throws StandardException

        Check if the right operand is on a form that makes it possible to flatten this query to a NOT EXISTS join. We don't allow flattening if the right operand doesn't reference the base table of the subquery. (Requirement added as part of DERBY-4001.)

        The problem with the right operand not referencing the base table of the subquery, is that the join condition may then be used to filter rows from the right side (outer) table in the NOT EXISTS join. In a NOT EXISTS join, the join condition can only safely be applied to the left side (inner) table of the join. Otherwise, it will filter out all the interesting rows too early.

        Take the query below as an example:

        
 SELECT * FROM T1 WHERE X NOT IN (SELECT 1 FROM T2)

        Here, the right operand is 1, and the join condition is T1.X=1. If flattened, the join condition will be used directly on the outer table, and hide all rows with X<>1, although those are the only rows we're interested in. If the join condition had only been used on the inner table, the NOT EXISTS join logic would do the correct thing.

        If the join condition references the inner table, the condition cannot be used directly on the outer table, so it is safe to flatten the query.

        Parameters:
        numTables - the number of tables in this statement
        fbt - the only FromBaseTable in this subquery
        Returns:
        true if it is OK to flatten this query to a NOT EXISTS join, false otherwise
        Throws:
        StandardException

      • canAllBeFlattened

        private boolean canAllBeFlattened()
                           throws StandardException
        Can NOT IN, ALL be falttened to NOT EXISTS join? We can't or the flattening doesn't easily make sense if either side of the comparison is nullable. (beetle 5173)
        Returns:
        Whether or not the NOT IN or ALL subquery can be flattened.
        Throws:
        StandardException

      • flattenToNormalJoin

        private ValueNode flattenToNormalJoin​(int numTables,
                                      FromList outerFromList,
                                      SubqueryList outerSubqueryList,
                                      PredicateList outerPredicateList)
                               throws StandardException
        Flatten this subquery into the outer query block. At this point we are only flattening based on a uniqueness condition and only flattening non-aggregate subqueries. So, we promote the subquery's from list, as is, into the outer from list. For EXISTS subquerys, we return a TRUE. Otherwise we return a new comparison between the leftOperand and the expression in the subquery's SELECT list. RESOLVE - we will need to modify this logic to account for exists joins and aggregates as we support flattening for them. Anyway, here's what we do: o We remove ourself from the outer subquery list. o We decrement the nesting level for all tables in the subquery tree. o We append the subquery's from list to the outer from list. o We add the subquery's predicate list to the outer predicate list. (The subquery has already been preprocessed.) o We add the subquery's subquery list to the outer subquery list. o For EXISTS, we return a true. o Otherwise, we return a new comparison between the leftOperand and the expression in the inner select's RCL.
        Parameters:
        numTables - Number of tables in the DML Statement
        outerFromList - FromList from outer query block
        outerSubqueryList - SubqueryList from outer query block
        outerPredicateList - PredicateList from outer query block
        Returns:
        The modified expression
        Throws:
        StandardException - Thrown on error

      • flattenToExistsJoin

        private ValueNode flattenToExistsJoin​(int numTables,
                                      FromList outerFromList,
                                      SubqueryList outerSubqueryList,
                                      PredicateList outerPredicateList,
                                      boolean flattenableNotExists)
                               throws StandardException
        Flatten this subquery into the outer query block as an exists join. At this point we are only flattening non-aggregate subqueries with a single FBT in the from list. So, we transform all FBTs in the from list into ExistBaseTables, update the dependency lists for each of the tables and then flatten the subquery. RESOLVE - we will need to modify this logic to account for aggregates as we support flattening for them.
        Parameters:
        numTables - Number of tables in the DML Statement
        outerFromList - FromList from outer query block
        outerSubqueryList - SubqueryList from outer query block
        outerPredicateList - PredicateList from outer query block
        flattenableNotExists - Is it a flattening into a NOT EXISTS join
        Returns:
        The modified expression
        Throws:
        StandardException - Thrown on error

      • getRightOperand

        private ValueNode getRightOperand()
        Get the node that will be the right operand in the join condition if this ALL/ANY/SOME/(NOT) IN subquery is flattened to a join.
        Returns:
        the right operand

      • isInvariant

        private boolean isInvariant()
                     throws StandardException
        Check to see if we have a Variant value below us. If so, return true. Caches the result so multiple calls are ok.
        Returns:
        boolean whether we have
        Throws:
        StandardException - Thrown on error

      • hasCorrelatedCRs

        boolean hasCorrelatedCRs()
                  throws StandardException
        Check to see if this subquery has correlated column references. Only useful results if called AFTER binding (after CRs have been bound).
        Returns:
        whether the subquery has correlated column references.
        Throws:
        StandardException - Thrown on error

      • pushNewPredicate

        private UnaryComparisonOperatorNode pushNewPredicate​(int numTables)
                                              throws StandardException
        Transform: expression QuantifiedOperator (select x from ...) into (select true from .. where expression x ...) IS [NOT] NULL or, if we have an aggregate: (select true from (select AGG(x) from ...) where expression x ...) IS [NOT] NULL For ANY and IN subqueries: o We generate an IS NULL above the SubqueryNode and return the top of the new tree to the caller. o The operator in the new predicate that is added to the subquery will correspond to the operator that modifies the ANY. (eg, = for = ANY, with = for IN.) For ALL and NOT IN subqueries: o We generate an IS NOT NULL above the SubqueryNode and return the top of the new tree to the caller. o The operator in the new predicate that is added to the subquery will be a BinaryAllOperatorNode whose bcoNodeType corresponds to the negation of the operator that modifies the ALL. (eg, <> for = ALL, with <> for NOT IN.) NOTE: This method is called after the underlying subquery has been preprocessed, so we build a new Predicate, not just a new expression.
        Parameters:
        numTables - Number of tables in DML Statement
        Returns:
        UnaryComparisonOperatorNode An IS [NOT] NULL above the transformed subquery.
        Throws:
        StandardException - Thrown on error

      • getNewJoinCondition

        private BinaryComparisonOperatorNode getNewJoinCondition​(ValueNode leftOperand,
                                                         ValueNode rightOperand)
                                                  throws StandardException
        Build a new join condition between the leftOperand and the rightOperand. The comparison operator is dependent on the subquery type.
        Parameters:
        leftOperand - The left operand for the new condition.
        rightOperand - The right operand for the new condition.
        Throws:
        StandardException - Thrown on error

      • eliminateNots

        ValueNode eliminateNots​(boolean underNotNode)
                 throws StandardException
        Eliminate NotNodes in the current query block. We traverse the tree, inverting ANDs and ORs and eliminating NOTs as we go. We stop at ComparisonOperators and boolean expressions. We invert ComparisonOperators and replace boolean expressions with boolean expression = false. NOTE: Since we do not recurse under ComparisonOperators, there still could be NotNodes left in the tree.
        Overrides:
        eliminateNots in class ValueNode
        Parameters:
        underNotNode - Whether or not we are under a NotNode.
        Returns:
        The modified expression
        Throws:
        StandardException - Thrown on error

      • changeToCNF

        ValueNode changeToCNF​(boolean underTopAndNode)
               throws StandardException
        Finish putting an expression into conjunctive normal form. An expression tree in conjunctive normal form meets the following criteria: o If the expression tree is not null, the top level will be a chain of AndNodes terminating in a true BooleanConstantNode. o The left child of an AndNode will never be an AndNode. o Any right-linked chain that includes an AndNode will be entirely composed of AndNodes terminated by a true BooleanConstantNode. o The left child of an OrNode will never be an OrNode. o Any right-linked chain that includes an OrNode will be entirely composed of OrNodes terminated by a false BooleanConstantNode. o ValueNodes other than AndNodes and OrNodes are considered leaf nodes for purposes of expression normalization. In other words, we won't do any normalization under those nodes. In addition, we track whether or not we are under a top level AndNode. SubqueryNodes need to know this for subquery flattening.
        Overrides:
        changeToCNF in class ValueNode
        Parameters:
        underTopAndNode - Whether or not we are under a top level AndNode.
        Returns:
        The modified expression
        Throws:
        StandardException - Thrown on error

      • categorize

        boolean categorize​(JBitSet referencedTabs,
                   boolean simplePredsOnly)
            throws StandardException
        Categorize this predicate. Initially, this means building a bit map of the referenced tables for each predicate. If the source of this ColumnReference (at the next underlying level) is not a ColumnReference or a VirtualColumnNode then this predicate will not be pushed down. For example, in: select * from (select 1 from s) a (x) where x = 1 we will not push down x = 1. NOTE: It would be easy to handle the case of a constant, but if the inner SELECT returns an arbitrary expression, then we would have to copy that tree into the pushed predicate, and that tree could contain subqueries and method calls. RESOLVE - revisit this issue once we have views.
        Overrides:
        categorize in class ValueNode
        Parameters:
        referencedTabs - JBitSet with bit map of referenced FromTables
        simplePredsOnly - Whether or not to consider method calls, field references and conditional nodes when building bit map
        Returns:
        boolean Whether or not source.expression is a ColumnReference or a VirtualColumnNode.
        Throws:
        StandardException - Thrown on error

      • optimize

        void optimize​(DataDictionary dataDictionary,
              double outerRows)
       throws StandardException
        Optimize this SubqueryNode.
        Parameters:
        dataDictionary - The DataDictionary to use for optimization
        outerRows - The optimizer's estimate of the number of times this subquery will be executed.
        Throws:
        StandardException - Thrown on error

      • modifyAccessPaths

        void modifyAccessPaths()
                throws StandardException
        Make any changes to the access paths, as decided by the optimizer.
        Throws:
        StandardException - Thrown on error

      • getOrderableVariantType

        protected int getOrderableVariantType()
                               throws StandardException
        Return the variant type for the underlying expression. The variant type can be: VARIANT - variant within a scan (method calls and non-static field access) SCAN_INVARIANT - invariant within a scan (column references from outer tables) QUERY_INVARIANT - invariant within the life of a query (constant expressions)
        Overrides:
        getOrderableVariantType in class ValueNode
        Returns:
        The variant type for the underlying expression.
        Throws:
        StandardException - Thrown on error

      • isIN

        private boolean isIN()

      • isNOT_IN

        private boolean isNOT_IN()

      • isANY

        private boolean isANY()

      • isALL

        private boolean isALL()

      • isEXISTS

        private boolean isEXISTS()

      • isNOT_EXISTS

        private boolean isNOT_EXISTS()

      • changeToCorrespondingExpressionType

        private void changeToCorrespondingExpressionType()
                                          throws StandardException
        Convert this IN/ANY subquery, which is known to return at most 1 row, to an equivalent expression subquery.
        Throws:
        StandardException - Thrown on error

      • isEquivalent

        boolean isEquivalent​(ValueNode o)
        Tests if this node is equivalent to the specified ValueNode. Two ValueNodes are considered equivalent if they will evaluate to the same value during query execution.

        This method provides basic expression matching facility for the derived class of ValueNode and it is used by the language layer to compare the node structural form of the two expressions for equivalence at bind phase.

        Note that it is not comparing the actual row values at runtime to produce a result; hence, when comparing SQL NULLs, they are considered to be equivalent and not unknown.

        One usage case of this method in this context is to compare the select column expression against the group by expression to check if they are equivalent. e.g.:

        SELECT c1+c2 FROM t1 GROUP BY c1+c2

        In general, node equivalence is determined by the derived class of ValueNode. But they generally abide to the rules below:

        • The two ValueNodes must be of the same node type to be considered equivalent. e.g.: CastNode vs. CastNode - equivalent (if their args also match), ColumnReference vs CastNode - not equivalent.
        • If node P contains other ValueNode(s) and so on, those node(s) must also be of the same node type to be considered equivalent.
        • If node P takes a parameter list, then the number of arguments and its arguments for the two nodes must also match to be considered equivalent. e.g.: CAST(c1 as INTEGER) vs CAST(c1 as SMALLINT), they are not equivalent.
        • When comparing SQL NULLs in this context, they are considered to be equivalent.
        • If this does not apply or it is determined that the two nodes are not equivalent then the derived class of this method should return false; otherwise, return true.
        Specified by:
        isEquivalent in class ValueNode
        Parameters:
        o - the node to compare this ValueNode against.
        Returns:
        true if the two nodes are equivalent, false otherwise.

      • isHavingSubquery

        public boolean isHavingSubquery()
        Is this subquery part of a having clause?
        Returns:
        true if it is part of a having clause, otherwise false

      • setHavingSubquery

        public void setHavingSubquery​(boolean havingSubquery)
        Mark this subquery as being part of a having clause.
        Parameters:
        havingSubquery -

      • isWhereSubquery

        boolean isWhereSubquery()
        Is this subquery part of a whereclause?
        Returns:
        true if it is part of a where clause, otherwise false

      • setWhereSubquery

        void setWhereSubquery​(boolean whereSubquery)
        Mark this subquery as being part of a where clause.
        Parameters:
        whereSubquery -

      • isWhereExistsAnyInWithWhereSubquery

        boolean isWhereExistsAnyInWithWhereSubquery()
                                     throws StandardException
        Check whether this is a WHERE EXISTS | ANY | IN subquery with a subquery in its own WHERE clause. Used in flattening decision making. DERBY-3301 reported wrong results from a nested WHERE EXISTS, but according to the derby optimizer docs this applies to a broader range of WHERE clauses in a WHERE EXISTS subquery. No WHERE EXISTS subquery with anohter subquery in it own WHERE clause can be flattened.
        Returns:
        true if this subquery is a WHERE EXISTS | ANY | IN subquery with a subquery in its own WHERE clause
        Throws:
        StandardException

      • getOrderByList

        public OrderByList getOrderByList()
        Get ORDER BY list (used to construct FROM_SUBQUERY only), cf. FromSubquery, for which this node is transient.
        Returns:
        order by list if specified, else null.

      • getOffset

        public ValueNode getOffset()
        Get OFFSET (used to construct FROM_SUBQUERY only), cf. FromSubquery, for which this node is transient.
        Returns:
        offset if specified, else null.

      • getFetchFirst

        public ValueNode getFetchFirst()
        Get FETCH FIRST (used to construct FROM_SUBQUERY only), cf. FromSubquery, for which this node is transient.
        Returns:
        fetch first if specified, else null.

      • hasJDBClimitClause

        public boolean hasJDBClimitClause()
        Return true if the offset/fetchFirst clauses were added by JDBC LIMIT escape syntax. This method is used to construct a FROM_SUBQUERY only, cf. FromSubquery, for which this node is transient.
        Returns:
        true if the JDBC limit/offset semantics (rather than the SQL Standard OFFSET/FETCH NEXT) semantics apply