simpledb

Class JoinOptimizer

java.lang.Object

simpledb.JoinOptimizer

public class JoinOptimizer
extends java.lang.Object

The JoinOptimizer class is responsible for ordering a series of joins optimally, and for selecting the best instantiation of a join for a given logical plan.

Field Summary

Fields

Modifier and Type	Field and Description
(package private) java.util.Vector<LogicalJoinNode>	joins
(package private) LogicalPlan	p

Constructor Summary

Constructors

Constructor and Description
JoinOptimizer(LogicalPlan p, java.util.Vector<LogicalJoinNode> joins) Constructor

Method Summary

Modifier and Type	Method and Description
private CostCard	computeCostAndCardOfSubplan(java.util.HashMap<java.lang.String,TableStats> stats, java.util.HashMap<java.lang.String,java.lang.Double> filterSelectivities, LogicalJoinNode joinToRemove, java.util.Set<LogicalJoinNode> joinSet, double bestCostSoFar, PlanCache pc) This is a helper method that computes the cost and cardinality of joining joinToRemove to joinSet (joinSet should contain joinToRemove), given that all of the subsets of size joinSet.size() - 1 have already been computed and stored in PlanCache pc.
private boolean	doesJoin(java.util.Vector<LogicalJoinNode> joinlist, java.lang.String table) Return true if the specified table is in the list of joins, false otherwise
<T> java.util.Set<java.util.Set<T>>	enumerateSubsets(java.util.Vector<T> v, int size) Helper method to enumerate all of the subsets of a given size of a specified vector.
int	estimateJoinCardinality(LogicalJoinNode j, int card1, int card2, boolean t1pkey, boolean t2pkey, java.util.Map<java.lang.String,TableStats> stats) Estimate the cardinality of a join.
double	estimateJoinCost(LogicalJoinNode j, int card1, int card2, double cost1, double cost2) Estimate the cost of a join.
static int	estimateTableJoinCardinality(Predicate.Op joinOp, java.lang.String table1Alias, java.lang.String table2Alias, java.lang.String field1PureName, java.lang.String field2PureName, int card1, int card2, boolean t1pkey, boolean t2pkey, java.util.Map<java.lang.String,TableStats> stats, java.util.Map<java.lang.String,java.lang.Integer> tableAliasToId) Estimate join cardinality
private boolean	hasPkey(java.util.Vector<LogicalJoinNode> joinlist) Return true if a primary key field is joined by one of the joins in joinlist
static DbIterator	instantiateJoin(LogicalJoinNode lj, DbIterator plan1, DbIterator plan2) Return best iterator for computing a given logical join, given the specified statistics, and the provided left and right subplans.
private boolean	isPkey(java.lang.String tableAlias, java.lang.String field) Return true if field is a primary key of the specified table, false otherwise
java.util.Vector<LogicalJoinNode>	orderJoins(java.util.HashMap<java.lang.String,TableStats> stats, java.util.HashMap<java.lang.String,java.lang.Double> filterSelectivities, boolean explain) Compute a logical, reasonably efficient join on the specified tables.
private void	printJoins(java.util.Vector<LogicalJoinNode> js, PlanCache pc, java.util.HashMap<java.lang.String,TableStats> stats, java.util.HashMap<java.lang.String,java.lang.Double> selectivities) Helper function to display a Swing window with a tree representation of the specified list of joins.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

p

LogicalPlan p

joins

java.util.Vector<LogicalJoinNode> joins

Constructor Detail

JoinOptimizer

public JoinOptimizer(LogicalPlan p,
                     java.util.Vector<LogicalJoinNode> joins)

Constructor

Parameters:

p - the logical plan being optimized

joins - the list of joins being performed

Method Detail

instantiateJoin

public static DbIterator instantiateJoin(LogicalJoinNode lj,
                                         DbIterator plan1,
                                         DbIterator plan2)
                                  throws ParsingException

Return best iterator for computing a given logical join, given the specified statistics, and the provided left and right subplans. Note that there is insufficient information to determine which plan should be the inner/outer here -- because DbIterator's don't provide any cardinality estimates, and stats only has information about the base tables. For this reason, the plan1

Parameters:

lj - The join being considered

plan1 - The left join node's child

plan2 - The right join node's child

Throws:

ParsingException

estimateJoinCost

public double estimateJoinCost(LogicalJoinNode j,
                               int card1,
                               int card2,
                               double cost1,
                               double cost2)

Estimate the cost of a join. The cost of the join should be calculated based on the join algorithm (or algorithms) that you implemented for Project 2. It should be a function of the amount of data that must be read over the course of the query, as well as the number of CPU opertions performed by your join. Assume that the cost of a single predicate application is roughly 1.

Parameters:

j - A LogicalJoinNode representing the join operation being performed.

card1 - Estimated cardinality of the left-hand side of the query

card2 - Estimated cardinality of the right-hand side of the query

cost1 - Estimated cost of one full scan of the table on the left-hand side of the query

cost2 - Estimated cost of one full scan of the table on the right-hand side of the query

Returns:

An estimate of the cost of this query, in terms of cost1 and cost2

estimateJoinCardinality

public int estimateJoinCardinality(LogicalJoinNode j,
                                   int card1,
                                   int card2,
                                   boolean t1pkey,
                                   boolean t2pkey,
                                   java.util.Map<java.lang.String,TableStats> stats)

Estimate the cardinality of a join. The cardinality of a join is the number of tuples produced by the join.

Parameters:

j - A LogicalJoinNode representing the join operation being performed.

card1 - Cardinality of the left-hand table in the join

card2 - Cardinality of the right-hand table in the join

t1pkey - Is the left-hand table a primary-key table?

t2pkey - Is the right-hand table a primary-key table?

stats - The table stats, referenced by table names, not alias

Returns:

The cardinality of the join

estimateTableJoinCardinality

public static int estimateTableJoinCardinality(Predicate.Op joinOp,
                                               java.lang.String table1Alias,
                                               java.lang.String table2Alias,
                                               java.lang.String field1PureName,
                                               java.lang.String field2PureName,
                                               int card1,
                                               int card2,
                                               boolean t1pkey,
                                               boolean t2pkey,
                                               java.util.Map<java.lang.String,TableStats> stats,
                                               java.util.Map<java.lang.String,java.lang.Integer> tableAliasToId)

Estimate join cardinality

Parameters:

joinOp -

table1Alias -

table2Alias -

field1PureName -

field2PureName -

card1 -

card2 -

t1pkey -

t2pkey -

stats -

tableAliasToId -

Returns:

enumerateSubsets

public <T> java.util.Set<java.util.Set<T>> enumerateSubsets(java.util.Vector<T> v,
                                                            int size)

Helper method to enumerate all of the subsets of a given size of a specified vector.

Parameters:

v - The vector whose subsets are desired

size - The size of the subsets of interest

Returns:

a set of all subsets of the specified size

orderJoins

public java.util.Vector<LogicalJoinNode> orderJoins(java.util.HashMap<java.lang.String,TableStats> stats,
                                                    java.util.HashMap<java.lang.String,java.lang.Double> filterSelectivities,
                                                    boolean explain)
                                             throws ParsingException

Compute a logical, reasonably efficient join on the specified tables. See project description for hints on how this should be implemented.

Parameters:

stats - Statistics for each table involved in the join, referenced by base table names, not alias

filterSelectivities - Selectivities of the filter predicates on each table in the join, referenced by table alias (if no alias, the base table name)

explain - Indicates whether your code should explain its query plan or simply execute it

Returns:

A Vector < LogicalJoinNode > that stores joins in the left-deep order in which they should be executed.

Throws:

ParsingException - when stats or filter selectivities is missing a table in the join, or or when another internal error occurs

computeCostAndCardOfSubplan

private CostCard computeCostAndCardOfSubplan(java.util.HashMap<java.lang.String,TableStats> stats,
                                             java.util.HashMap<java.lang.String,java.lang.Double> filterSelectivities,
                                             LogicalJoinNode joinToRemove,
                                             java.util.Set<LogicalJoinNode> joinSet,
                                             double bestCostSoFar,
                                             PlanCache pc)
                                      throws ParsingException

This is a helper method that computes the cost and cardinality of joining joinToRemove to joinSet (joinSet should contain joinToRemove), given that all of the subsets of size joinSet.size() - 1 have already been computed and stored in PlanCache pc.

Parameters:

stats - table stats for all of the tables, referenced by table names rather than alias (see orderJoins(java.util.HashMap<java.lang.String, simpledb.TableStats>, java.util.HashMap<java.lang.String, java.lang.Double>, boolean))

filterSelectivities - the selectivities of the filters over each of the tables (where tables are indentified by their alias or name if no alias is given)

joinToRemove - the join to remove from joinSet

joinSet - the set of joins being considered

bestCostSoFar - the best way to join joinSet so far (minimum of previous invocations of computeCostAndCardOfSubplan for this joinSet, from returned CostCard)

pc - the PlanCache for this join; should have subplans for all plans of size joinSet.size()-1

Returns:

A CostCard objects desribing the cost, cardinality, optimal subplan

Throws:

ParsingException - when stats, filterSelectivities, or pc object is missing tables involved in join

doesJoin

private boolean doesJoin(java.util.Vector<LogicalJoinNode> joinlist,
                         java.lang.String table)

Return true if the specified table is in the list of joins, false otherwise

isPkey

private boolean isPkey(java.lang.String tableAlias,
                       java.lang.String field)

Return true if field is a primary key of the specified table, false otherwise

Parameters:

tableAlias - The alias of the table in the query

field - The pure name of the field

hasPkey

private boolean hasPkey(java.util.Vector<LogicalJoinNode> joinlist)

Return true if a primary key field is joined by one of the joins in joinlist

printJoins

private void printJoins(java.util.Vector<LogicalJoinNode> js,
                        PlanCache pc,
                        java.util.HashMap<java.lang.String,TableStats> stats,
                        java.util.HashMap<java.lang.String,java.lang.Double> selectivities)

Helper function to display a Swing window with a tree representation of the specified list of joins. See orderJoins(java.util.HashMap<java.lang.String, simpledb.TableStats>, java.util.HashMap<java.lang.String, java.lang.Double>, boolean), which may want to call this when the analyze flag is true.

Parameters:

js - the join plan to visualize

pc - the PlanCache accumulated whild building the optimal plan

stats - table statistics for base tables

selectivities - the selectivities of the filters over each of the tables (where tables are indentified by their alias or name if no alias is given)