Class PushJoinUnderUnionWithRequests
java.lang.Object
se.liu.ida.hefquin.engine.queryproc.impl.loptimizer.heuristics.PushJoinUnderUnionWithRequests
- All Implemented Interfaces:
HeuristicForLogicalOptimization
public class PushJoinUnderUnionWithRequests
extends Object
implements HeuristicForLogicalOptimization
In cases in which there are unions with requests under joins (which may
happen only if we do not use
In this case, the joins can be implemented only by using a local join algorithm (e.g., hash join), which also means that the requests inside the unions are executed by physical request operators and, thus, may end up retrieving a lot of unnecessary triples from fm2 and from fm3 (i.e., triples that do not participate in the joins). In contrast, when applying this heuristic to that plan, the resulting plan is:
where the subplan under the second tpAdd operator is the same as the subplan under the first tpAdd operator. Now, the tpAdd operators can be implemented using bind joins or index nested loops joins, which may reduce the number of unnecessary triples retrieved from fm2 and fm3. The heuristic assumes that we have already applied a join ordering heuristics beforehand; i.e., the subplans under the multiway joins already have a reasonable order before this heuristics turns such a multiway join into stages of xxAdd operators (with the union operators in between the stages). Based on this assumption, the heuristics always processes the subplans of multiway joins from left to right; i.e., the left-most union subplan becomes the first stage and the right-most union subplan becomes the last stage at the top of the resulting (sub)plan. If there are multiple subplans under a join that are not union subplans, then these are kept together under a join. For instance, if the previous example plan would contain a second request before the multiway unions, then that request would be kept together with the first request as a join under the tpAdd operators created for the first multiway union. In addition to requests under unions (that are under joins), this heuristic even considers combinations of a filter operator with a request operator, in which case the request would also be turned into an xxAdd operator, but with the filter on top of it. Moreover, any other subplan under such unions (that are under joins) is joined with the previous join arguments. To illustrate these cases, consider the following example plan.
The resulting plan would then be as follows.
UnionPullUp, this heuristics turns
the requests into xxAdd operators with the previous join arguments as
subplans. The rationale of this heuristics is that it allows us to use
bind joins and index nested loops joins in cases in which otherwise only
local join algorithms (e.g., hash join) could be used. In this sense, the
effect of this heuristics is similar to that of UnionPullUp, but
without pulling out unions completely and, thus, without producing a great
number of join subplans.
For instance, consider the following plan.
mj(
req_fm1^(s,p,?x),
mu(
req_fm2^(?x,p2,?y),
req_fm3^(?x,p2,?y)
),
mu(
req_fm2^(?y,p3,?z),
req_fm3^(?y,p3,?z)
)
)
In this case, the joins can be implemented only by using a local join algorithm (e.g., hash join), which also means that the requests inside the unions are executed by physical request operators and, thus, may end up retrieving a lot of unnecessary triples from fm2 and from fm3 (i.e., triples that do not participate in the joins). In contrast, when applying this heuristic to that plan, the resulting plan is:
mu(
tpAdd_fm2^(?y,p3,?z) (
mu(
tpAdd__fm2^(?x,p2,?y) (
req_fm1^(s,p,?x)
),
tpAdd__fm3^(?x,p2,?y) (
req_fm1^(s,p,?x)
)
)
),
tpAdd_fm3^(?y,p3,?z) (
mu(
...
)
)
),
where the subplan under the second tpAdd operator is the same as the subplan under the first tpAdd operator. Now, the tpAdd operators can be implemented using bind joins or index nested loops joins, which may reduce the number of unnecessary triples retrieved from fm2 and fm3. The heuristic assumes that we have already applied a join ordering heuristics beforehand; i.e., the subplans under the multiway joins already have a reasonable order before this heuristics turns such a multiway join into stages of xxAdd operators (with the union operators in between the stages). Based on this assumption, the heuristics always processes the subplans of multiway joins from left to right; i.e., the left-most union subplan becomes the first stage and the right-most union subplan becomes the last stage at the top of the resulting (sub)plan. If there are multiple subplans under a join that are not union subplans, then these are kept together under a join. For instance, if the previous example plan would contain a second request before the multiway unions, then that request would be kept together with the first request as a join under the tpAdd operators created for the first multiway union. In addition to requests under unions (that are under joins), this heuristic even considers combinations of a filter operator with a request operator, in which case the request would also be turned into an xxAdd operator, but with the filter on top of it. Moreover, any other subplan under such unions (that are under joins) is joined with the previous join arguments. To illustrate these cases, consider the following example plan.
mj(
req_fm1^(s,p,?x),
mu(
filter^condition(
req_fm2^(?x,p2,?y)
),
leftjoin( ... )
)
)
The resulting plan would then be as follows.
mu(
filter^condition(
tpAdd_fm2^(?x,p2,?y) (
req_fm1^(s,p,?x)
)
),
mj(
req_fm1^(s,p,?x),
leftjoin( ... )
)
)
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionapply(LogicalPlan inputPlan) Applies this heuristics to the given plan and returns the resulting, potentially rewritten plan.protected LogicalPlanrewrite(LogicalPlan unionPlan, List<LogicalPlan> subPlansAsInput)
-
Constructor Details
-
PushJoinUnderUnionWithRequests
public PushJoinUnderUnionWithRequests()
-
-
Method Details
-
apply
Description copied from interface:HeuristicForLogicalOptimizationApplies this heuristics to the given plan and returns the resulting, potentially rewritten plan.- Specified by:
applyin interfaceHeuristicForLogicalOptimization
-
rewrite
-