Class ProjectPushDown

java.lang.Object
se.liu.ida.hefquin.engine.queryproc.impl.loptimizer.heuristics.ProjectPushDown
All Implemented Interfaces:
HeuristicForLogicalOptimization
public class ProjectPushDown extends Object implements HeuristicForLogicalOptimization
Pushes project operators as much as possible towards the leaf nodes of a given logical plan. This implementation works recursively in a top-down manner such that, after pushing a project operator under some other operator, the pushed project is considered again for further pushing. Whether and how a particular project operator can be pushed depends on the variables that are required and produced by the operators in the plan. For unary operators such as bind and unfold, the projection is adjusted before being pushed: - Variables produced by the operator are removed from the pushed projection, as they are not required as input. - Variables required to evaluate expressions of the operator are added, to ensure that the operator can still be evaluated correctly. If this adjusted projection is identical to the original projection, the project operator is pushed entirely below the respective operator. Otherwise, the project operator is split: an adjusted projection is pushed below the operator, while the original projection remains on top to preserve the final output schema. For operators with multiple subplans (e.g., joins), projections may be pushed into individual subplans based on the variables required in each branch, while ensuring that all necessary join variables are preserved. In cases where pushing is not possible without violating correctness, the project operator remains in its original position.

  • Constructor Details

    • ProjectPushDown

      public ProjectPushDown()

  • Method Details

    • apply

      public LogicalPlan apply(LogicalPlan inputPlan)
      Description copied from interface: HeuristicForLogicalOptimization
      Applies this heuristics to the given plan and returns the resulting, potentially rewritten plan.
      Specified by:
      apply in interface HeuristicForLogicalOptimization

    • applyToPlanWithProjectAsRootOperator

      protected LogicalPlan applyToPlanWithProjectAsRootOperator(LogicalOpProject projectOp, LogicalPlan subPlanUnderProject, LogicalPlan inputPlan)

    • createPlanForRequestUnderProject

      protected LogicalPlan createPlanForRequestUnderProject(LogicalOpProject projectOp, LogicalOpRequest<?,?> reqOp, LogicalPlan inputPlan)
      Pushing a project operator into request operator is not possible yet TODO #570

    • createPlanForFixedSolMapUnderProject

      protected LogicalPlan createPlanForFixedSolMapUnderProject(LogicalOpProject projectOp, LogicalOpFixedSolMap fixedSolMapOp, LogicalPlan inputPlan)
      Applies a project operator to a fixed solution mapping operator. If all variables in the solution mapping are retained by the projection, the project operator is redundant and is removed. Otherwise, a new fixed solution mapping is created that contains only the projected variables.

    • createPlanForUnionUnderProject

      protected LogicalPlan createPlanForUnionUnderProject(LogicalOpProject projectOp, LogicalPlan subPlanUnderProject)
      Pushes the project operator into each subplan under the union operator. The heuristic is then applied recursively to each subplan. Finally, all rewritten subplans are collected under a multiway union as the new root operator.

    • createPlanForBindUnderProject

      protected LogicalPlan createPlanForBindUnderProject(LogicalOpProject projectOp, LogicalOpBind bindOp, LogicalPlan subPlanUnderBind, LogicalPlan inputPlan)
      Attempts to push a project operator below a bind operator. The pushed projection is adjusted to ensure correctness:
      • Variables assigned by the bind operator are removed, since they are produced by the bind and not needed as input.
      • Variables required to evaluate the bind expressions are added, to ensure the bind can still be evaluated after pushdown.
      If this adjustment does not change the projection, the whole project can be pushed below the bind. If the adjusted projection contains all the variables of the subplan under the bind (including both the certain and the possible variables), then there is no need to push the adjusted projection at all and the plan can remain as is. Otherwise, the project is split: the adjusted projection is pushed below the bind, while the original projection remains on top.

    • createPlanForUnfoldUnderProject

      protected LogicalPlan createPlanForUnfoldUnderProject(LogicalOpProject projectOp, LogicalOpUnfold unfoldOp, LogicalPlan subPlanUnderUnfold, LogicalPlan inputPlan)
      Attempts to push a project operator below an unfold operator. The pushed projection is adjusted similarly to the bind case:
      • Variables assigned by the unfold operator are removed, since they are produced by the unfold.
      • Variables required to evaluate the unfold expression are added, to ensure the unfold can still be evaluated after pushdown.
      If this adjustment does not change the projection, the whole project can be pushed below the unfold. If the adjusted projection contains all the variables of the subplan under the unfold (including both the certain and the possible variables), then there is no need to push the adjusted projection at all and the plan can remain as is. Otherwise, the project is split: the adjusted projection is pushed below the unfold, while the original projection remains on top.

    • createPlanForL2GOrG2LUnderProject

      protected LogicalPlan createPlanForL2GOrG2LUnderProject(LogicalOpProject projectOp, UnaryLogicalOp childOp, LogicalPlan subPlanUnderChildOp)
      Assumes that the given child operator is either a LogicalOpLocalToGlobal or a LogicalOpGlobalToLocal. While pushing the project operator under an l2g or a g2l operator is safe in some cases, it is not generally safe. Both operators may:
      • map one input solution mapping to multiple output solution mappings
      • drop solution mappings entirely in some cases
      Pushing projection can therefore:
      • change duplication behaviour of results
      • incorrectly prevent solution mappings from being dropped
      TODO: think more about cases in which pushing a project operator is safe.

    • createPlanForAddOpUnderProject

      protected LogicalPlan createPlanForAddOpUnderProject(LogicalOpProject parentProjectOp, UnaryLogicalOp childOp, LogicalPlan subPlanUnderChildOp, LogicalPlan inputPlan)
      Pushes a project operator below a gpAdd or gpOptAdd operator. The pushdown must preserve:
      • variables required by the parent projection
      • variables required by the operator (e.g., parameter variables or optional bindings)
      • join variables between the subplan and the operator pattern
      If all projected variables are guaranteed by the subplan and include all required variables, the projection is fully pushed below the operator. Otherwise, a reduced projection is pushed down while the original projection is retained above. If no beneficial pushdown is possible, the operator is left unchanged, but the heuristic is still applied recursively to the subplan.

    • createPlanForJoinLikeOpUnderProject

      protected LogicalPlan createPlanForJoinLikeOpUnderProject(LogicalOpProject projectOp, LogicalPlan subPlanUnderProject, LogicalPlan inputPlan)
      Pushes a projection below a n-ary operator by splitting required variables per branch. Each branch must retain:
      • its subset of the variables of the parent projection
      • its subset of the join variables

    • createPlanForProjectUnderProject

      protected LogicalPlan createPlanForProjectUnderProject(LogicalOpProject parentProjectOp, LogicalOpProject childProjectOp, LogicalPlan subPlanUnderChildProjectOp)
      Merges a parent and child project operator into a single project operator. The resulting projection contains the intersection of the variables from both operators and is applied to the subplan under the child project.

    • createPlanForUnaryOpUnderProject

      protected LogicalPlan createPlanForUnaryOpUnderProject(LogicalOpProject projectOp, UnaryLogicalOp op, LogicalPlan subPlanUnderOp)
      Returns a plan in which the given project operator is pushed under the given unary operator, with the subplan underneath being a version of the given subplan in which the project push down heuristic has been applied recursively.

    • computeJoinVars

      protected Set<org.apache.jena.sparql.core.Var> computeJoinVars(LogicalPlan joinPlan)
      Determines the set of all join variables between the subplans of the given plan, where a join variable is a variable (certain or possible) that occurs in at least two subplan.

    • operatorDoesNotRequireExtraVars

      protected boolean operatorDoesNotRequireExtraVars(UnaryLogicalOp childOp, LogicalOpProject projectOp)