Package edu.caltech.nanodb.queryeval

Class CostBasedJoinPlanner

  • All Implemented Interfaces:
    Planner
    public class CostBasedJoinPlanner
extends java.lang.Object
implements Planner
    This planner implementation uses dynamic programming to devise an optimal join strategy for the query. As always, queries are optimized in units of SELECT-FROM-WHERE subqueries; optimizations don't currently span multiple subqueries.

    • Field Detail

      • logger

        private static org.apache.logging.log4j.Logger logger
        A logging object for reporting anything interesting that happens.

      • storageManager

        protected StorageManager storageManager
        The storage manager used during query planning.

    • Constructor Detail

      • CostBasedJoinPlanner

        public CostBasedJoinPlanner()

    • Method Detail

      • setStorageManager

        public void setStorageManager​(StorageManager storageManager)
        Sets the server to be used during query planning.
        Specified by:
        setStorageManager in interface Planner
        Parameters:
        storageManager - the storage manager instance for the planner implementation to use

      • makePlan

        public PlanNode makePlan​(SelectClause selClause,
                         java.util.List<SelectClause> enclosingSelects)
        Returns the root of a plan tree suitable for executing the specified query.
        Specified by:
        makePlan in interface Planner
        Parameters:
        selClause - an object describing the query to be performed
        enclosingSelects - a list of enclosing queries, if selClause is a nested subquery. This is allowed to be an empty list, or null, if the query is a top-level query. If selClause is a nested subquery, enclosingSelects[0] is the outermost enclosing query, then enclosingSelects[1] is enclosed by enclosingSelects[0], and so forth. The most tightly enclosing query is the last one in enclosingSelects.
        Returns:
        a plan tree for executing the specified query

      • makeJoinPlan

        private CostBasedJoinPlanner.JoinComponent makeJoinPlan​(FromClause fromClause,
                                                        java.util.Collection<Expression> extraConjuncts)
        Given the top-level FromClause for a SELECT-FROM-WHERE block, this helper generates an optimal join plan for the FromClause.
        Parameters:
        fromClause - the top-level FromClause of a SELECT-FROM-WHERE block.
        extraConjuncts - any extra conjuncts (e.g. from the WHERE clause, or HAVING clause)
        Returns:
        a JoinComponent object that represents the optimal plan corresponding to the FROM-clause

      • collectDetails

        private void collectDetails​(FromClause fromClause,
                            java.util.HashSet<Expression> conjuncts,
                            java.util.ArrayList<FromClause> leafFromClauses)
        This helper method pulls the essential details for join optimization out of a FROM clause. TODO: FILL IN DETAILS.
        Parameters:
        fromClause - the from-clause to collect details from
        conjuncts - the collection to add all conjuncts to
        leafFromClauses - the collection to add all leaf from-clauses to

      • generateLeafJoinComponents

        private java.util.ArrayList<CostBasedJoinPlanner.JoinComponent> generateLeafJoinComponents​(java.util.Collection<FromClause> leafFromClauses,
                                                                                           java.util.Collection<Expression> conjuncts)
        This helper method performs the first step of the dynamic programming process to generate an optimal join plan, by generating a plan for every leaf from-clause identified from analyzing the query. Leaf plans are usually very simple; they are built either from base-tables or SELECT subqueries. The most complex detail is that any conjuncts in the query that can be evaluated solely against a particular leaf plan-node will be associated with the plan node. This is a heuristic that usually produces good plans (and certainly will for the current state of the database), but could easily interfere with indexes or other plan optimizations.
        Parameters:
        leafFromClauses - the collection of from-clauses found in the query
        conjuncts - the collection of conjuncts that can be applied at this level
        Returns:
        a collection of CostBasedJoinPlanner.JoinComponent object containing the plans and other details for each leaf from-clause

      • makeLeafPlan

        private PlanNode makeLeafPlan​(FromClause fromClause,
                              java.util.Collection<Expression> conjuncts,
                              java.util.HashSet<Expression> leafConjuncts)
        Constructs a plan tree for evaluating the specified from-clause. TODO: COMPLETE THE DOCUMENTATION
        Parameters:
        fromClause - the select nodes that need to be joined.
        conjuncts - additional conjuncts that can be applied when constructing the from-clause plan.
        leafConjuncts - this is an output-parameter. Any conjuncts applied in this plan from the conjuncts collection should be added to this out-param.
        Returns:
        a plan tree for evaluating the specified from-clause
        Throws:
        java.lang.IllegalArgumentException - if the specified from-clause is a join expression that isn't an outer join, or has some other unrecognized type.

      • makeSimpleSelect

        public SelectNode makeSimpleSelect​(java.lang.String tableName,
                                   Expression predicate,
                                   java.util.List<SelectClause> enclosingSelects)
        Constructs a simple select plan that reads directly from a table, with an optional predicate for selecting rows.

        While this method can be used for building up larger SELECT queries, the returned plan is also suitable for use in UPDATE and DELETE command evaluation. In these cases, the plan must only generate tuples of type PageTuple, so that the command can modify or delete the actual tuple in the file's page data.

        Specified by:
        makeSimpleSelect in interface Planner
        Parameters:
        tableName - The name of the table that is being selected from.
        predicate - An optional selection predicate, or null if no filtering is desired.
        enclosingSelects - a list of enclosing queries, if selClause is a nested subquery. This is allowed to be an empty list, or null, if the query is a top-level query. If selClause is a nested subquery, enclosingSelects[0] is the outermost enclosing query, then enclosingSelects[1] is enclosed by enclosingSelects[0], and so forth. The most tightly enclosing query is the last one in enclosingSelects.
        Returns:
        A new plan-node for evaluating the select operation.