Package com.bigdata.bop.joinGraph

This package provides support for join graphs, query optimization, and generating full query plans from a join graph and the evaluation order identified by a query optimizer.

See: Description

Interface Summary

Interface	Description
IEvaluationPlan	Interface for evaluation orders.
IEvaluationPlanFactory	A factory for evaluation plans.
IRangeCountFactory	An interface used by an IEvaluationPlan to obtain range counts for the IPredicates in an IRule.

Class Summary

Class	Description
DefaultRangeCountFactory	Default implementation.
FixedEvaluationPlanFactory	A factory for IEvaluationPlans that uses a caller specified evaluation order.
NOPEvaluationPlanFactory	A factory for IEvaluationPlans that do not reorder the predicates in the tail.
NoReorderEvaluationPlan	Useful for testing - will not reorder the join predicates.
PartitionedJoinGroup	Deprecated by StaticAnalysis_CanJoin which is a port of this code to the AST mode.
TestAll	Aggregates test suites into increasing dependency order.
TestPartitionedJoinGroup	Unit tests for PartitionedJoinGroup.
TestPartitionedJoinGroup_canJoin	Unit tests for PartitionedJoinGroup.canJoin(IPredicate, IPredicate)
TestPartitionedJoinGroup_canJoinUsingConstraints	This test suite is built around around BSBM Q5.

Exception Summary

Exception	Description
NoSolutionsException	Exception thrown when the join graph does not have any solutions in the data (running the cutoff joins to explore the join graph does not produce any solutions such that we can not complete a path through the join graph without a zero cardinality).

Package com.bigdata.bop.joinGraph Description

This package provides support for join graphs, query optimization, and generating full query plans from a join graph and the evaluation order identified by a query optimizer.

Support is provided for both static query optimization, based on an analysis of variable bindings and the cardinality of the various access paths, and adaptive query optimization.

The adaptive query optimization technique is based on breadth first cutoff sampling of join paths and dynamically selects a join path providing efficient execution plan for the query. Fast and accurate cardinality estimates are available based on range counts are used to decide which joins to execute first. Without accurate knowledge of detailed correlation in joins, estimation error rapidly sets in as variable bindings are propagated. Adaptive query optimization iteratively explores the join path identified as having lowest cost for a common set of vertices. Join paths whose costs are dominated by a better solution are eliminated. Sampling of longer and longer join paths continues until one join path is found to have the lowest cost, at which point it is executed. This approach bears some similarity to the one described in ROX : Run-time Optimization of XQueries , by Kader and Boncz (2009) (presentation ), but there are numerous differences as well.