QueryPlanEstimator.java

  1. /*
  2.  * Copyright © 2014 - 2021 Leipzig University (Database Research Group)
  3.  *
  4.  * Licensed under the Apache License, Version 2.0 (the "License");
  5.  * you may not use this file except in compliance with the License.
  6.  * You may obtain a copy of the License at
  7.  *
  8.  *     http://www.apache.org/licenses/LICENSE-2.0
  9.  *
  10.  * Unless required by applicable law or agreed to in writing, software
  11.  * distributed under the License is distributed on an "AS IS" BASIS,
  12.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13.  * See the License for the specific language governing permissions and
  14.  * limitations under the License.
  15.  */
  16. package org.gradoop.flink.model.impl.operators.matching.single.cypher.planning.estimation;

  17. import org.gradoop.flink.model.impl.operators.matching.common.query.QueryHandler;
  18. import org.gradoop.flink.model.impl.operators.matching.common.statistics.GraphStatistics;
  19. import org.gradoop.flink.model.impl.operators.matching.single.cypher.planning.queryplan.BinaryNode;
  20. import org.gradoop.flink.model.impl.operators.matching.single.cypher.planning.queryplan.FilterNode;
  21. import org.gradoop.flink.model.impl.operators.matching.single.cypher.planning.queryplan.JoinNode;
  22. import org.gradoop.flink.model.impl.operators.matching.single.cypher.planning.queryplan.PlanNode;
  23. import org.gradoop.flink.model.impl.operators.matching.single.cypher.planning.queryplan.QueryPlan;
  24. import org.gradoop.flink.model.impl.operators.matching.single.cypher.planning.queryplan.UnaryNode;

  25. /**
  26.  * Estimates a given query plan by traversing its nodes and updating the state of specific
  27.  * estimator implementations (e.g. for join, filter, project).
  28.  */
  29. public class QueryPlanEstimator {
  30.   /**
  31.    * The query plan to estimate
  32.    */
  33.   private final QueryPlan queryPlan;
  34.   /**
  35.    * Estimates the cardinality of the joins in the given query plan.
  36.    */
  37.   private final JoinEstimator joinEstimator;
  38.   /**
  39.    * Estimates the cardinality and selectivity of the leaf nodes.
  40.    */
  41.   private final FilterEstimator filterEstimator;

  42.   /**
  43.    * Creates a new plan estimator.
  44.    *
  45.    * @param queryPlan query plan
  46.    * @param queryHandler query handler
  47.    * @param graphStatistics graph statistics
  48.    */
  49.   public QueryPlanEstimator(QueryPlan queryPlan, QueryHandler queryHandler,
  50.     GraphStatistics graphStatistics) {
  51.     this.queryPlan = queryPlan;
  52.     this.joinEstimator = new JoinEstimator(queryHandler, graphStatistics);
  53.     this.filterEstimator = new FilterEstimator(queryHandler, graphStatistics);
  54.   }

  55.   /**
  56.    * Returns the estimated query plan.
  57.    *
  58.    * @return query plan
  59.    */
  60.   public QueryPlan getQueryPlan() {
  61.     return queryPlan;
  62.   }

  63.   /**
  64.    * Traverses the query plan and computes the estimated cardinality according to the nodes.
  65.    *
  66.    * @return estimated cardinality of the specified plan
  67.    */
  68.   public long getCardinality() {
  69.     traversePlan(queryPlan.getRoot());

  70.     long cardinality = joinEstimator.getCardinality();
  71.     if (cardinality == 0) {
  72.       // plan contains only a leaf node
  73.       cardinality = filterEstimator.getCardinality();
  74.     }
  75.     double selectivity = filterEstimator.getSelectivity();

  76.     return Math.round(cardinality * selectivity);
  77.   }

  78.   /**
  79.    * Visits the node if necessary and traverses the plan further if possible.
  80.    *
  81.    * @param node plan node
  82.    */
  83.   private void traversePlan(PlanNode node) {
  84.     if (node instanceof JoinNode) {
  85.       this.joinEstimator.visit((JoinNode) node);
  86.     }
  87.     if (node instanceof FilterNode) {
  88.       this.filterEstimator.visit((FilterNode) node);
  89.     }

  90.     if (node instanceof BinaryNode) {
  91.       traversePlan(((BinaryNode) node).getLeftChild());
  92.       traversePlan(((BinaryNode) node).getRightChild());
  93.     }
  94.     if (node instanceof UnaryNode) {
  95.       traversePlan(((UnaryNode) node).getChildNode());
  96.     }
  97.   }
  98. }