Package edu.caltech.nanodb.plannodes

Class PlanNode

  • All Implemented Interfaces:
    java.lang.Cloneable
    Direct Known Subclasses:
    GroupAggregateNode, ProjectNode, RenameNode, SelectNode, SortNode, TableFunctionScanNode, ThetaJoinNode, TupleBagNode
    public abstract class PlanNode
extends java.lang.Object
implements java.lang.Cloneable
    The base class of all query execution plan nodes. All plan nodes have similar implementation characteristics provided by this class. They may have zero, one or two child plan nodes.

    Marking

    Plan nodes may or may not support marking positions within the tuple-stream produced by the node. Some algorithms require marking positions within a node's tuple stream, so that processing can return to that point later on.

    Implementations are encouraged to only support marking if it is easy to support in the implementation. The MaterializeNode can be used to add marking to any tuple stream.

    If a plan node supports marking, its behavior must be as follows:

    • Marking should be inexpensive, and there should be no penalty for not resetting to a given mark.
    • When resetToLastMark() is called, the next call to getNextTuple() should return the first tuple that would be returned after the most recent call to markCurrentPosition().
    • It must be possible to mark before the first tuple. Resetting to this mark should cause the next call to getNextTuple() to again return the first tuple. (Note that this is similar to the case when initialize() is called on a plan node, but the difference here is that marking/resetting uses cached results, and initialize() causes the results to be regenerated from scratch.)
    • It must be possible to mark after the last tuple. Resetting to this mark should cause the next call to getNextTuple() to return null.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected PlanCost cost
      The estimated cost of executing this plan and its subplans.
      protected Environment environment
      The environment used to evaluate expressions against tuples being processed.
      protected PlanNode leftChild
      The left child of this plan node.
      protected PlanNode rightChild
      If the plan node has two children, this field is set to the right child node.
      protected Schema schema
      The schema of the results produced by this plan-node.
      protected java.util.ArrayList<ColumnStats> stats
      Statistics (possibly estimated) describing the results produced by this plan node.

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected PlanNode()
      Constructs a PlanNode with no child nodes.
      protected PlanNode​(PlanNode leftChild)
      Constructs a PlanNode with a given operation type, and the specified left child-plan.
      protected PlanNode​(PlanNode leftChild, PlanNode rightChild)
      Constructs a PlanNode with a given operation type, and the specified left child-plan.

    • Method Summary

      All Methods Static Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      void addParentEnvironmentToPlanTree​(Environment parentEnv)
      This method adds a parent environment to the entire plan tree rooted at this plan node.
      abstract void cleanUp()
      Perform any necessary clean up tasks.
      protected PlanNode clone()
      Creates a copy of this plan node and its subtree.
      PlanNode duplicate()
      Returns a deep copy of this plan tree.
      abstract boolean equals​(java.lang.Object obj)
      Checks if the argument is a plan node tree with the same structure, but not necesarily the same references.
      PlanCost getCost()
      Returns the estimated cost of this plan node's operation.
      Environment getEnvironment()
      Returns the environment that this plan node uses during query evaluation.
      abstract Tuple getNextTuple()
      Gets the next tuple that fulfills the conditions for this plan node.
      Schema getSchema()
      Returns the schema of the results that this node produces.
      java.util.ArrayList<ColumnStats> getStats()
      Returns statistics (possibly estimated) describing the results that this plan node will produce.
      abstract int hashCode()
      Computes the hash-code of a plan-node, including any sub-plans of this plan.
      void initialize()
      Does any initialization the node might need, including setting up the node's execution environment.
      void markCurrentPosition()
      Marks the current tuple in the tuple-stream produced by this node.
      abstract void prepare()
      This method is responsible for computing critical details about the plan node, such as the schema of the results that are produced, the estimated cost of evaluating the plan node (and its children), and statistics describing the results produced by the plan node.
      void printNodeTree​(java.io.PrintStream out)
      Prints the entire node tree with indentation to the specified output stream starting from indentation level 0.
      void printNodeTree​(java.io.PrintStream out, boolean includeCosts)
      Prints the entire node tree with indentation to the specified output stream starting from indentation level 0.
      void printNodeTree​(java.io.PrintStream out, boolean includeCosts, java.lang.String indent)
      Prints the entire plan subtree starting at this node.
      static java.lang.String printNodeTreeToString​(PlanNode plan)
      Generates the same result as printNodeTree(PrintStream), but into a string instead of to an output stream.
      static java.lang.String printNodeTreeToString​(PlanNode plan, boolean includeCosts)
      Generates the same result as printNodeTree(PrintStream), but into a string instead of to an output stream.
      boolean requiresLeftMarking()
      This method reports whether this plan node requires the left child to support marking for proper evaluation.
      boolean requiresRightMarking()
      This method reports whether this plan node requires the right child to support marking for proper evaluation.
      void resetToLastMark()
      Resets the node's tuple-stream to the most recently marked position.
      abstract java.util.List<OrderByExpression> resultsOrderedBy()
      If the results are ordered in some way, this method returns a collection of expressions specifying what columns or expressions the results are ordered by.
      void setEnvironment​(Environment env)
      Sets the plan node's environment to the specified environment object.
      private void setNodeParents()
      Iterates through the tree and sets node parents to correct references.
      boolean supportsMarking()
      This method reports whether this plan node supports marking a certain point in the tuple-stream so that processing can return to that point as needed.
      abstract java.lang.String toString()
      Reports this node and its vital parameters as a string.

      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, wait, wait, wait

    • Field Detail

      • leftChild

        protected PlanNode leftChild
        The left child of this plan node. If the plan node only has one child, use this field.

      • rightChild

        protected PlanNode rightChild
        If the plan node has two children, this field is set to the right child node. If the plan has only one child, this field will be null.

      • schema

        protected Schema schema
        The schema of the results produced by this plan-node. The schema is initialized by the prepare() method; before that method has been called, this will be null.

      • cost

        protected PlanCost cost
        The estimated cost of executing this plan and its subplans. This cost is computed by the prepare() method; before that method has been called, this will be null.

      • stats

        protected java.util.ArrayList<ColumnStats> stats
        Statistics (possibly estimated) describing the results produced by this plan node. These statistics are produced when the prepare() method is called; before that method has been called, this will be null.

        This collection corresponds to the schema object; it will contain the same number of columns, and the individual columns will correspond with the specific columns in the schema object.

      • environment

        protected Environment environment
        The environment used to evaluate expressions against tuples being processed.

    • Constructor Detail

      • PlanNode

        protected PlanNode()
        Constructs a PlanNode with no child nodes.

      • PlanNode

        protected PlanNode​(PlanNode leftChild)
        Constructs a PlanNode with a given operation type, and the specified left child-plan. This method will be called by subclass constructors.
        Parameters:
        leftChild - the left subplan of this node.
        Throws:
        java.lang.IllegalArgumentException - if leftChild is null

      • PlanNode

        protected PlanNode​(PlanNode leftChild,
                   PlanNode rightChild)
        Constructs a PlanNode with a given operation type, and the specified left child-plan. This method will be called by subclass constructors.
        Parameters:
        leftChild - the left subplan of this node.
        rightChild - the right subplan of this node.
        Throws:
        java.lang.IllegalArgumentException - if op, leftChild, or rightChild is null

    • Method Detail

      • resultsOrderedBy

        public abstract java.util.List<OrderByExpression> resultsOrderedBy()
        If the results are ordered in some way, this method returns a collection of expressions specifying what columns or expressions the results are ordered by. If the results are not ordered then this method may return either an empty list or a null value.

        When this method returns a list of ordering expressions, the order of the expressions themselves also matters. The entire set of results will be ordered by the first expression; rows with the same value for the first expression will be ordered by the second expression; etc.

        Returns:
        If the plan node produces ordered results, this will be a list of objects specifying the ordering. If the node doesn't produce ordered results then the return-value will either be an empty list or it will be null.

      • supportsMarking

        public boolean supportsMarking()
        This method reports whether this plan node supports marking a certain point in the tuple-stream so that processing can return to that point as needed.
        Returns:
        true if the node supports position marking, false otherwise.

      • requiresLeftMarking

        public boolean requiresLeftMarking()
        This method reports whether this plan node requires the left child to support marking for proper evaluation.
        Returns:
        true if the node requires that its left child supports marking, false otherwise.

      • requiresRightMarking

        public boolean requiresRightMarking()
        This method reports whether this plan node requires the right child to support marking for proper evaluation.
        Returns:
        true if the node requires that its right child supports marking, false otherwise.

      • prepare

        public abstract void prepare()
        This method is responsible for computing critical details about the plan node, such as the schema of the results that are produced, the estimated cost of evaluating the plan node (and its children), and statistics describing the results produced by the plan node.

      • getSchema

        public final Schema getSchema()
        Returns the schema of the results that this node produces. Some nodes such as Select will not change the input schema but others, such as Project, Rename, and ThetaJoin, must change it.

        The schema is not computed until the prepare() method is called; until that point, this method will return null.

        Returns:
        the schema produced by this plan-node.

      • getCost

        public final PlanCost getCost()
        Returns the estimated cost of this plan node's operation. The estimate depends on which algorithm the node uses and the data it is working with.

        The cost is not computed until the prepare() method is called; until that point, this method will return null.

        Returns:
        an object containing various cost measures such as the worst-case number of disk accesses, the number of tuples produced, etc.

      • getStats

        public final java.util.ArrayList<ColumnStats> getStats()
        Returns statistics (possibly estimated) describing the results that this plan node will produce. Estimating statistics for output results is a very imprecise task, to say the least.

        These statistics are not computed until the prepare() method is called; until that point, this method will return null.

        Returns:
        statistics describing the results that will be produced by this plan-node.

      • getEnvironment

        public Environment getEnvironment()
        Returns the environment that this plan node uses during query evaluation.
        Returns:
        the environment this plan node uses during evaluation.

      • setEnvironment

        public void setEnvironment​(Environment env)
        Sets the plan node's environment to the specified environment object. This can be used to connect subqueries to their parent environment, among other things.
        Parameters:
        env - the environment for this plan node to use during evaluation.

      • addParentEnvironmentToPlanTree

        public void addParentEnvironmentToPlanTree​(Environment parentEnv)
        This method adds a parent environment to the entire plan tree rooted at this plan node. This allows an execution plan to be used as a subquery that references an outer plan's tuples during evaluation.
        Parameters:
        parentEnv - the parent environment to add to this plan tree.

      • initialize

        public void initialize()
        Does any initialization the node might need, including setting up the node's execution environment. Subclasses of PlanNode can extend this method to perform other kinds of initialization, but they must be sure to call their parent class' implementation as well.

      • getNextTuple

        public abstract Tuple getNextTuple()
                            throws java.lang.IllegalStateException
        Gets the next tuple that fulfills the conditions for this plan node. If the node has a child, it should call getNextTuple() on the child. If the node is a leaf, the tuple comes from some external source such as a table file, the network, etc.
        Returns:
        the next tuple to be generated by this plan, or null if the plan has finished generating plan nodes.
        Throws:
        java.lang.IllegalStateException - if a plan node is not properly initialized

      • markCurrentPosition

        public void markCurrentPosition()
        Marks the current tuple in the tuple-stream produced by this node. The resetToLastMark() method can be used to return to this tuple. Note that only one marker can be set in the tuple-stream at a time.
        Throws:
        java.lang.UnsupportedOperationException - if the node does not support marking.
        java.lang.IllegalStateException - if there is no "current tuple" to mark. This will occur if getNextTuple() hasn't yet been called (i.e. we are before the first tuple in the tuple-stream), or if we have already reached the end of the tuple-stream (i.e. we are after the last tuple in the stream).

      • resetToLastMark

        public void resetToLastMark()
        Resets the node's tuple-stream to the most recently marked position. Note that only one marker can be set in the tuple-stream at a time.
        Throws:
        java.lang.UnsupportedOperationException - if the node does not support marking.
        java.lang.IllegalStateException - if markCurrentPosition() hasn't yet been called on this plan-node

      • cleanUp

        public abstract void cleanUp()
        Perform any necessary clean up tasks. This should probably be called when we are done with this plan node.

      • toString

        public abstract java.lang.String toString()
        Reports this node and its vital parameters as a string.
        Overrides:
        toString in class java.lang.Object
        Returns:
        the node in string format.
        Design Note:
        We re-declare this here to force its implementation in subclasses.

      • printNodeTree

        public void printNodeTree​(java.io.PrintStream out,
                          boolean includeCosts,
                          java.lang.String indent)
        Prints the entire plan subtree starting at this node.
        Parameters:
        out - PrintStream to be used for output.
        includeCosts - a flag controlling whether the cost estimates will be included in the plan output
        indent - the indentation level.

      • printNodeTree

        public void printNodeTree​(java.io.PrintStream out,
                          boolean includeCosts)
        Prints the entire node tree with indentation to the specified output stream starting from indentation level 0.
        Parameters:
        out - the output stream.
        includeCosts - a flag controlling whether costs are included in the output

      • printNodeTree

        public void printNodeTree​(java.io.PrintStream out)
        Prints the entire node tree with indentation to the specified output stream starting from indentation level 0. Costs are not included in the output.
        Parameters:
        out - the output stream.

      • printNodeTreeToString

        public static java.lang.String printNodeTreeToString​(PlanNode plan,
                                                     boolean includeCosts)
        Generates the same result as printNodeTree(PrintStream), but into a string instead of to an output stream.
        Parameters:
        plan - The plan tree to print to a string.
        includeCosts - a flag controlling whether costs are included in the output
        Returns:
        A string containing the indented printout of the plan.

      • printNodeTreeToString

        public static java.lang.String printNodeTreeToString​(PlanNode plan)
        Generates the same result as printNodeTree(PrintStream), but into a string instead of to an output stream.
        Parameters:
        plan - The plan tree to print to a string.
        Returns:
        A string containing the indented printout of the plan.

      • equals

        public abstract boolean equals​(java.lang.Object obj)
        Checks if the argument is a plan node tree with the same structure, but not necesarily the same references.
        Overrides:
        equals in class java.lang.Object
        Parameters:
        obj - the object to which we are comparing
        Design Note:
        We re-declare this here to force its implementation in subclasses.

      • hashCode

        public abstract int hashCode()
        Computes the hash-code of a plan-node, including any sub-plans of this plan. This method is used to see if two plan nodes (or subtrees) might be equal.
        Overrides:
        hashCode in class java.lang.Object
        Returns:
        the hash code for the plan node and any subnodes it may contain.

      • clone

        protected PlanNode clone()
                  throws java.lang.CloneNotSupportedException
        Creates a copy of this plan node and its subtree. Note that this method is only used internally, because plan nodes also reference their parent node, and it is not possible for this method to set that parent-reference properly. To create a deep copy of an entire plan tree, the duplicate() method should be used.
        Overrides:
        clone in class java.lang.Object
        Throws:
        java.lang.CloneNotSupportedException

      • setNodeParents

        private void setNodeParents()
        Iterates through the tree and sets node parents to correct references. This method should be called after cloning an entire tree because cloning cannot correctly clone parent references.

      • duplicate

        public PlanNode duplicate()
        Returns a deep copy of this plan tree.
        Returns:
        a root to the duplicated plan tree.