Class QueryJoinOptimizer.JoinVisitor

java.lang.Object

org.eclipse.rdf4j.query.algebra.helpers.AbstractSimpleQueryModelVisitor<RuntimeException>

org.eclipse.rdf4j.query.algebra.evaluation.optimizer.QueryJoinOptimizer.JoinVisitor

All Implemented Interfaces:

QueryModelVisitor<RuntimeException>

Enclosing class:

QueryJoinOptimizer

protected class QueryJoinOptimizer.JoinVisitor
extends AbstractSimpleQueryModelVisitor<RuntimeException>

This can be extended by subclasses to allow for adjustments to the optimization process.

Author:

Arjohn Kampman, James Leigh

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	JoinVisitor()

Method Summary

Modifier and Type	Method	Description
protected <M extends Map<Var,Integer>> void	fillVarFreqMap(List<Var> varList, M varFreqMap)
protected int	getForeignVarFreq(List<Var> ownUnboundVars, Map<Var,Integer> varFreqMap)
protected <L extends List<TupleExpr>> L	getJoinArgs(TupleExpr tupleExpr, L joinArgs)
protected List<Var>	getStatementPatternVars(TupleExpr tupleExpr)
protected List<TupleExpr>	getSubSelects(List<TupleExpr> expressions)	This method returns all direct sub-selects in the given list of expressions.
protected double	getTupleExprCost(TupleExpr tupleExpr, Map<TupleExpr, Double> cardinalityMap, Map<TupleExpr, List<Var>> varsMap, Map<Var,Integer> varFreqMap)
protected List<Var>	getUnboundVars(List<Var> vars)
void	meet(Join node)
void	meet(LeftJoin leftJoin)
void	meet(StatementPattern node)
protected List<TupleExpr>	reorderSubselects(List<TupleExpr> subSelects)	Determines an optimal ordering of subselect join arguments, based on variable bindings.
protected TupleExpr	selectNextTupleExpr(List<TupleExpr> expressions, Map<TupleExpr, Double> cardinalityMap, Map<TupleExpr, List<Var>> varsMap, Map<Var,Integer> varFreqMap)	Selects from a list of tuple expressions the next tuple expression that should be evaluated.

Methods inherited from class AbstractSimpleQueryModelVisitor

meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meet, meetBinaryTupleOperator, meetBinaryValueOperator, meetCompareSubQueryValueOperator, meetNAryValueOperator, meetOther, meetSubQueryValueOperator, meetUnaryTupleOperator, meetUnaryValueOperator, meetUnsupported, meetUpdateExpr

Modifier and Type	Method	Description
void	meet(Add node)
void	meet(AggregateFunctionCall node)
void	meet(And node)
void	meet(ArbitraryLengthPath node)
void	meet(Avg node)
void	meet(BindingSetAssignment node)
void	meet(BNodeGenerator node)
void	meet(Bound node)
void	meet(Clear node)
void	meet(Coalesce node)
void	meet(Compare node)
void	meet(CompareAll node)
void	meet(CompareAny node)
void	meet(Copy node)
void	meet(Count node)
void	meet(Create node)
void	meet(Datatype node)
void	meet(DeleteData node)
void	meet(DescribeOperator node)
void	meet(Difference node)
void	meet(Distinct node)
void	meet(EmptySet node)
void	meet(Exists node)
void	meet(Extension node)
void	meet(ExtensionElem node)
void	meet(Filter node)
void	meet(FunctionCall node)
void	meet(Group node)
void	meet(GroupConcat node)
void	meet(GroupElem node)
void	meet(If node)
void	meet(In node)
void	meet(InsertData node)
void	meet(Intersection node)
void	meet(IRIFunction node)
void	meet(IsBNode node)
void	meet(IsLiteral node)
void	meet(IsNumeric node)
void	meet(IsResource node)
void	meet(IsURI node)
void	meet(Label node)
void	meet(Lang node)
void	meet(LangMatches node)
void	meet(ListMemberOperator node)
void	meet(Load node)
void	meet(LocalName node)
void	meet(MathExpr node)
void	meet(Max node)
void	meet(Min node)
void	meet(Modify node)
void	meet(Move node)
void	meet(MultiProjection node)
void	meet(Namespace node)
void	meet(Not node)
void	meet(Or node)
void	meet(Order node)
void	meet(OrderElem node)
void	meet(Projection node)
void	meet(ProjectionElem node)
void	meet(ProjectionElemList node)
void	meet(QueryRoot node)
void	meet(Reduced node)
void	meet(Regex node)
void	meet(SameTerm node)
void	meet(Sample node)
void	meet(Service node)
void	meet(SingletonSet node)
void	meet(Slice node)
void	meet(Str node)
void	meet(Sum node)
void	meet(TripleRef node)
void	meet(Union node)
void	meet(ValueConstant node)
void	meet(ValueExprTripleRef node)
void	meet(Var node)
void	meet(ZeroLengthPath node)
protected void	meetBinaryTupleOperator(BinaryTupleOperator node)	Method called by all meet methods with a BinaryTupleOperator node as argument.
protected void	meetBinaryValueOperator(BinaryValueOperator node)	Method called by all meet methods with a BinaryValueOperator node as argument.
protected void	meetCompareSubQueryValueOperator(CompareSubQueryValueOperator node)	Method called by all meet methods with a CompareSubQueryValueOperator node as argument.
protected void	meetNAryValueOperator(NAryValueOperator node)	Method called by all meet methods with a NAryValueOperator node as argument.
void	meetOther(QueryModelNode node)
protected void	meetSubQueryValueOperator(SubQueryValueOperator node)	Method called by all meet methods with a SubQueryValueOperator node as argument.
protected void	meetUnaryTupleOperator(UnaryTupleOperator node)	Method called by all meet methods with a UnaryTupleOperator node as argument.
protected void	meetUnaryValueOperator(UnaryValueOperator node)	Method called by all meet methods with a UnaryValueOperator node as argument.
void	meetUnsupported(QueryModelNode node)
protected void	meetUpdateExpr(UpdateExpr node)	Method called by all meet methods with a UpdateExpr node as argument.

Methods inherited from class Object

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

Constructor Details

JoinVisitor

protected JoinVisitor()

Method Details

meet

public void meet(LeftJoin leftJoin)

Specified by:

meet in interface QueryModelVisitor<RuntimeException>

Overrides:

meet in class AbstractSimpleQueryModelVisitor<RuntimeException>

meet

public void meet(StatementPattern node)
          throws RuntimeException

Specified by:

meet in interface QueryModelVisitor<RuntimeException>

Overrides:

meet in class AbstractSimpleQueryModelVisitor<RuntimeException>

Throws:

RuntimeException

meet

public void meet(Join node)

Specified by:

meet in interface QueryModelVisitor<RuntimeException>

Overrides:

meet in class AbstractSimpleQueryModelVisitor<RuntimeException>

getJoinArgs

protected <L extends List<TupleExpr>> L getJoinArgs(TupleExpr tupleExpr,
 L joinArgs)

getStatementPatternVars

protected List<Var> getStatementPatternVars(TupleExpr tupleExpr)

fillVarFreqMap

protected <M extends Map<Var,Integer>> void fillVarFreqMap(List<Var> varList,
 M varFreqMap)

getSubSelects

protected List<TupleExpr> getSubSelects(List<TupleExpr> expressions)

This method returns all direct sub-selects in the given list of expressions.

This method is meant to be possible to override by subclasses.

Parameters:

expressions -

Returns:

reorderSubselects

protected List<TupleExpr> reorderSubselects(List<TupleExpr> subSelects)

Determines an optimal ordering of subselect join arguments, based on variable bindings. An ordering is considered optimal if for each consecutive element it holds that first of all its shared variables with all previous elements is maximized, and second, the union of all its variables with all previous elements is maximized.

Example: reordering

  [f] [a b c] [e f] [a d] [b e]

should result in:

  [a b c] [a d] [b e] [e f] [f]

Parameters:

subSelects - the original ordering of expressions

Returns:

the optimized ordering of expressions

selectNextTupleExpr

protected TupleExpr selectNextTupleExpr(List<TupleExpr> expressions,
 Map<TupleExpr, Double> cardinalityMap,
 Map<TupleExpr, List<Var>> varsMap,
 Map<Var,Integer> varFreqMap)

Selects from a list of tuple expressions the next tuple expression that should be evaluated. This method selects the tuple expression with highest number of bound variables, preferring variables that have been bound in other tuple expressions over variables with a fixed value.

getTupleExprCost

protected double getTupleExprCost(TupleExpr tupleExpr,
 Map<TupleExpr, Double> cardinalityMap,
 Map<TupleExpr, List<Var>> varsMap,
 Map<Var,Integer> varFreqMap)

getUnboundVars

protected List<Var> getUnboundVars(List<Var> vars)

getForeignVarFreq

protected int getForeignVarFreq(List<Var> ownUnboundVars,
 Map<Var,Integer> varFreqMap)