Package se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple

Class CardinalityBasedGreedyJoinPlanOptimizerImpl.GreedyConstructionAlgorithm

java.lang.Object
se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.GreedyConstructionAlgorithm
All Implemented Interfaces:
JoinPlanOptimizerBase.EnumerationAlgorithm
Enclosing class:
CardinalityBasedGreedyJoinPlanOptimizerImpl
protected class CardinalityBasedGreedyJoinPlanOptimizerImpl.GreedyConstructionAlgorithm extends Object implements JoinPlanOptimizerBase.EnumerationAlgorithm

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected final List<PhysicalPlan>
    subplans
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    GreedyConstructionAlgorithm(List<PhysicalPlan> subplans)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    protected int
    accessNumForReq(int cardinality, FederationMember fm)
    The number of requests depends on the page size of response.
    protected List<se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics>
    associateCardWithSubPlans(List<LogicalOpRequest<?,?>> reqOpsOfAllSubPlans, CardinalityResponse[] resps)
     
    protected se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics
    chooseFirstSubPlan(List<se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics> subPlansWithStatistics)
    Compares all available subplans (see subplans) in terms of their respective cardinality returns the one with the lowest cardinality.
    protected se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics
    decidePhysicalAlgorithm(se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics currentPlan, se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics nextPlan)
    The physical algorithm (symmetric hash join and bind join) is determined based on the estimated number of requests to execute the join (see formulas on page 1052 of the paper[1]) - SHJ: Card(T1)/PageSize + Card(T2)/PageSize - BJ: Card(T1)/PageSize + Card(T1)/blockSize [1] Heling, Lars, and Maribel Acosta.
    protected double
    determineBlockSize(FederationMember fm)
    The block size (number of bindings can be attached) depends on the type of interface
    protected List<LogicalOpRequest<?,?>>
    extractAllRequestOpsFromSourceAssignment(PhysicalPlan plan)
    Extracts all request operators from the given plan, assuming that this plan is a sub-plan of a source assignment (hence, assuming that this plan can only be either a single request, a filter over a request, or a union with requests).
    PhysicalPlan
    getResultingPlan()
     
    protected List<se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics>
    getSubPlansContainVars(ExpectedVariables vars, List<se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics> subPlansWithStatistics)
    Iterate through the remaining subplans and selected those that contain any of the variables in the given set of variables.

    Methods inherited from class java.lang.Object

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

  • Field Details

  • Constructor Details

    • GreedyConstructionAlgorithm

      public GreedyConstructionAlgorithm(List<PhysicalPlan> subplans)

  • Method Details

    • getResultingPlan

      public PhysicalPlan getResultingPlan() throws PhysicalOptimizationException
      Specified by:
      getResultingPlan in interface JoinPlanOptimizerBase.EnumerationAlgorithm
      Throws:
      PhysicalOptimizationException

    • extractAllRequestOpsFromSourceAssignment

      protected List<LogicalOpRequest<?,?>> extractAllRequestOpsFromSourceAssignment(PhysicalPlan plan)
      Extracts all request operators from the given plan, assuming that this plan is a sub-plan of a source assignment (hence, assuming that this plan can only be either a single request, a filter over a request, or a union with requests). The extracted request operators will be order in the order in which they are discovered by a depth-first traversal of the given plan.

    • associateCardWithSubPlans

      protected List<se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics> associateCardWithSubPlans(List<LogicalOpRequest<?,?>> reqOpsOfAllSubPlans, CardinalityResponse[] resps)
      Parameters:
      reqOpsOfAllSubPlans - A list of request operators, which is ordered in the order in which the request operators can be found by a depth-first traversal of the subplans.
      resps - A list of cardinality in the same order of 'reqOpsOfAllSubPlans'
      Returns:
      A list of PhysicalPlanWithStatistics, with each object corresponding to a subplan in the 'subplans' list. Each PhysicalPlanWithStatistics object contains the physical plan for the subplan, along with its cardinality, a list of relevant federations members, and estimated number of access to federation members. During a depth-first traversal of the subplans, increase the index by 1 when visiting a request operator: If the root operator of the subplan is a Request operator, get the corresponding cardinality from resps with the same index; If the subPlan with a Union of requests, calculate the total cardinality by summing up the cardinality of individual requests. (See page 1052 in the paper[1])

    • chooseFirstSubPlan

      protected se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics chooseFirstSubPlan(List<se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics> subPlansWithStatistics)
      Compares all available subplans (see subplans) in terms of their respective cardinality returns the one with the lowest cardinality.

    • getSubPlansContainVars

      protected List<se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics> getSubPlansContainVars(ExpectedVariables vars, List<se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics> subPlansWithStatistics)
      Iterate through the remaining subplans and selected those that contain any of the variables in the given set of variables.

    • decidePhysicalAlgorithm

      protected se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics decidePhysicalAlgorithm(se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics currentPlan, se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.CardinalityBasedGreedyJoinPlanOptimizerImpl.PhysicalPlanWithStatistics nextPlan)
      The physical algorithm (symmetric hash join and bind join) is determined based on the estimated number of requests to execute the join (see formulas on page 1052 of the paper[1]) - SHJ: Card(T1)/PageSize + Card(T2)/PageSize - BJ: Card(T1)/PageSize + Card(T1)/blockSize [1] Heling, Lars, and Maribel Acosta. "Federated SPARQL query processing over heterogeneous linked data fragments." Proceedings of the ACM Web Conference 2022. For the comparison, only keeping the second element is enough.

    • accessNumForReq

      protected int accessNumForReq(int cardinality, FederationMember fm)
      The number of requests depends on the page size of response.

    • determineBlockSize

      protected double determineBlockSize(FederationMember fm)
      The block size (number of bindings can be attached) depends on the type of interface