Switch to topological sorting for MATCH patterns in new query planner

luigidellaquila · luigidellaquila · commit 3ea6e48e9a58 · 2017-04-20T11:30:05.000+02:00
diff --git a/core/src/main/java/com/orientechnologies/orient/core/sql/executor/OMatchExecutionPlanner.java b/core/src/main/java/com/orientechnologies/orient/core/sql/executor/OMatchExecutionPlanner.java
@@ -75,7 +75,8 @@ public OInternalExecutionPlan createExecutionPlan(OCommandContext context, boole
       }
       result.chain(step);
     } else {
-      OInternalExecutionPlan plan = createPlanForPattern(pattern, context, estimatedRootEntries, aliasesToPrefetch, enableProfiling);
+      OInternalExecutionPlan plan = createPlanForPattern(pattern, context, estimatedRootEntries, aliasesToPrefetch,
+          enableProfiling);
       for (OExecutionStep step : plan.getSteps()) {
         result.chain((OExecutionStepInternal) step);
       }
@@ -126,7 +127,7 @@ private void addReturnStep(OSelectExecutionPlan result, OCommandContext context,
   private OInternalExecutionPlan createPlanForPattern(Pattern pattern, OCommandContext context,
       Map<String, Long> estimatedRootEntries, Set<String> prefetchedAliases, boolean profilingEnabled) {
     OSelectExecutionPlan plan = new OSelectExecutionPlan(context);
-    List<EdgeTraversal> sortedEdges = sortEdges(estimatedRootEntries, pattern, context);
+    List<EdgeTraversal> sortedEdges = getTopologicalSortedSchedule(estimatedRootEntries, pattern);
 
     boolean first = true;
     if (sortedEdges.size() > 0) {
@@ -154,6 +155,200 @@ private OInternalExecutionPlan createPlanForPattern(Pattern pattern, OCommandCon
     return plan;
   }
 
+  /**
+   * sort edges in the order they will be matched
+   */
+  private List<EdgeTraversal> getTopologicalSortedSchedule(Map<String, Long> estimatedRootEntries,
+      Pattern pattern) {
+    List<EdgeTraversal> resultingSchedule = new ArrayList<>();
+    Map<String, Set<String>> remainingDependencies = getDependencies(pattern);
+    Set<PatternNode> visitedNodes = new HashSet<>();
+    Set<PatternEdge> visitedEdges = new HashSet<>();
+
+    // Sort the possible root vertices in order of estimated size, since we want to start with a small vertex set.
+    List<OPair<Long, String>> rootWeights = new ArrayList<>();
+    for (Map.Entry<String, Long> root : estimatedRootEntries.entrySet()) {
+      rootWeights.add(new OPair<>(root.getValue(), root.getKey()));
+    }
+    Collections.sort(rootWeights);
+
+    // Add the starting vertices, in the correct order, to an ordered set.
+    Set<String> remainingStarts = new LinkedHashSet<String>();
+    for (OPair<Long, String> item : rootWeights) {
+      remainingStarts.add(item.getValue());
+    }
+    // Add all the remaining aliases after all the suggested start points.
+    for (String alias : pattern.aliasToNode.keySet()) {
+      if (!remainingStarts.contains(alias)) {
+        remainingStarts.add(alias);
+      }
+    }
+
+    while (resultingSchedule.size() < pattern.numOfEdges) {
+      // Start a new depth-first pass, adding all nodes with satisfied dependencies.
+      // 1. Find a starting vertex for the depth-first pass.
+      PatternNode startingNode = null;
+      List<String> startsToRemove = new ArrayList<String>();
+      for (String currentAlias : remainingStarts) {
+        PatternNode currentNode = pattern.aliasToNode.get(currentAlias);
+
+        if (visitedNodes.contains(currentNode)) {
+          // If a previous traversal already visited this alias, remove it from further consideration.
+          startsToRemove.add(currentAlias);
+        } else if (remainingDependencies.get(currentAlias).isEmpty()) {
+          // If it hasn't been visited, and has all dependencies satisfied, visit it.
+          startsToRemove.add(currentAlias);
+          startingNode = currentNode;
+          break;
+        }
+      }
+      remainingStarts.removeAll(startsToRemove);
+
+      if (startingNode == null) {
+        // We didn't manage to find a valid root, and yet we haven't constructed a complete schedule.
+        // This means there must be a cycle in our dependency graph, or all dependency-free nodes are optional.
+        // Therefore, the query is invalid.
+        throw new OCommandExecutionException("This query contains MATCH conditions that cannot be evaluated, "
+            + "like an undefined alias or a circular dependency on a $matched condition.");
+      }
+
+      // 2. Having found a starting vertex, traverse its neighbors depth-first,
+      //    adding any non-visited ones with satisfied dependencies to our schedule.
+      updateScheduleStartingAt(startingNode, visitedNodes, visitedEdges, remainingDependencies, resultingSchedule);
+    }
+
+    if (resultingSchedule.size() != pattern.numOfEdges) {
+      throw new AssertionError("Incorrect number of edges: " + resultingSchedule.size() + " vs " + pattern.numOfEdges);
+    }
+
+    return resultingSchedule;
+  }
+
+  /**
+   * Start a depth-first traversal from the starting node, adding all viable unscheduled edges and vertices.
+   *
+   * @param startNode             the node from which to start the depth-first traversal
+   * @param visitedNodes          set of nodes that are already visited (mutated in this function)
+   * @param visitedEdges          set of edges that are already visited and therefore don't need to be scheduled (mutated in this
+   *                              function)
+   * @param remainingDependencies dependency map including only the dependencies that haven't yet been satisfied (mutated in this
+   *                              function)
+   * @param resultingSchedule     the schedule being computed i.e. appended to (mutated in this function)
+   */
+  private void updateScheduleStartingAt(PatternNode startNode, Set<PatternNode> visitedNodes, Set<PatternEdge> visitedEdges,
+      Map<String, Set<String>> remainingDependencies, List<EdgeTraversal> resultingSchedule) {
+    // OrientDB requires the schedule to contain all edges present in the query, which is a stronger condition
+    // than simply visiting all nodes in the query. Consider the following example query:
+    //     MATCH {
+    //         class: A,
+    //         as: foo
+    //     }.in() {
+    //         as: bar
+    //     }, {
+    //         class: B,
+    //         as: bar
+    //     }.out() {
+    //         as: foo
+    //     } RETURN $matches
+    // The schedule for the above query must have two edges, even though there are only two nodes and they can both
+    // be visited with the traversal of a single edge.
+    //
+    // To satisfy it, we obey the following for each non-optional node:
+    // - ignore edges to neighboring nodes which have unsatisfied dependencies;
+    // - for visited neighboring nodes, add their edge if it wasn't already present in the schedule, but do not
+    //   recurse into the neighboring node;
+    // - for unvisited neighboring nodes with satisfied dependencies, add their edge and recurse into them.
+    visitedNodes.add(startNode);
+    for (Set<String> dependencies : remainingDependencies.values()) {
+      dependencies.remove(startNode.alias);
+    }
+
+    Map<PatternEdge, Boolean> edges = new LinkedHashMap<PatternEdge, Boolean>();
+    for (PatternEdge outEdge : startNode.out) {
+      edges.put(outEdge, true);
+    }
+    for (PatternEdge inEdge : startNode.in) {
+      edges.put(inEdge, false);
+    }
+
+    for (Map.Entry<PatternEdge, Boolean> edgeData : edges.entrySet()) {
+      PatternEdge edge = edgeData.getKey();
+      boolean isOutbound = edgeData.getValue();
+      PatternNode neighboringNode = isOutbound ? edge.in : edge.out;
+
+      if (!remainingDependencies.get(neighboringNode.alias).isEmpty()) {
+        // Unsatisfied dependencies, ignore this neighboring node.
+        continue;
+      }
+
+      if (visitedNodes.contains(neighboringNode)) {
+        if (!visitedEdges.contains(edge)) {
+          // If we are executing in this block, we are in the following situation:
+          // - the startNode has not been visited yet;
+          // - it has a neighboringNode that has already been visited;
+          // - the edge between the startNode and the neighboringNode has not been scheduled yet.
+          //
+          // The isOutbound value shows us whether the edge is outbound from the point of view of the startNode.
+          // However, if there are edges to the startNode, we must visit the startNode from an already-visited
+          // neighbor, to preserve the validity of the traversal. Therefore, we negate the value of isOutbound
+          // to ensure that the edge is always scheduled in the direction from the already-visited neighbor
+          // toward the startNode. Notably, this is also the case when evaluating "optional" nodes -- we always
+          // visit the optional node from its non-optional and already-visited neighbor.
+          //
+          // The only exception to the above is when we have edges with "while" conditions. We are not allowed
+          // to flip their directionality, so we leave them as-is.
+          boolean traversalDirection;
+          if (startNode.optional || edge.item.isBidirectional()) {
+            traversalDirection = !isOutbound;
+          } else {
+            traversalDirection = isOutbound;
+          }
+
+          visitedEdges.add(edge);
+          resultingSchedule.add(new EdgeTraversal(edge, traversalDirection));
+        }
+      } else if (!startNode.optional) {
+        // If the neighboring node wasn't visited, we don't expand the optional node into it, hence the above check.
+        // Instead, we'll allow the neighboring node to add the edge we failed to visit, via the above block.
+        if (visitedEdges.contains(edge)) {
+          // Should never happen.
+          throw new AssertionError("The edge was visited, but the neighboring vertex was not: " + edge + " " + neighboringNode);
+        }
+
+        visitedEdges.add(edge);
+        resultingSchedule.add(new EdgeTraversal(edge, isOutbound));
+        updateScheduleStartingAt(neighboringNode, visitedNodes, visitedEdges, remainingDependencies, resultingSchedule);
+      }
+    }
+  }
+
+  /**
+   * Calculate the set of dependency aliases for each alias in the pattern.
+   *
+   * @param pattern
+   *
+   * @return map of alias to the set of aliases it depends on
+   */
+  private Map<String, Set<String>> getDependencies(Pattern pattern) {
+    Map<String, Set<String>> result = new HashMap<String, Set<String>>();
+
+    for (PatternNode node : pattern.aliasToNode.values()) {
+      Set<String> currentDependencies = new HashSet<String>();
+
+      OWhereClause filter = aliasFilters.get(node.alias);
+      if (filter != null && filter.getBaseExpression() != null) {
+        List<String> involvedAliases = filter.getBaseExpression().getMatchPatternInvolvedAliases();
+        if (involvedAliases != null) {
+          currentDependencies.addAll(involvedAliases);
+        }
+      }
+
+      result.put(node.alias, currentDependencies);
+    }
+
+    return result;
+  }
+
   private void splitDisjointPatterns(OCommandContext context) {
     if (this.subPatterns != null) {
       return;
@@ -162,7 +357,8 @@ private void splitDisjointPatterns(OCommandContext context) {
     this.subPatterns = pattern.getDisjointPatterns();
   }
 
-  private void addStepsFor(OSelectExecutionPlan plan, EdgeTraversal edge, OCommandContext context, boolean first, boolean profilingEnabled) {
+  private void addStepsFor(OSelectExecutionPlan plan, EdgeTraversal edge, OCommandContext context, boolean first,
+      boolean profilingEnabled) {
     if (first) {
       PatternNode patternNode = edge.out ? edge.edge.out : edge.edge.in;
       String clazz = this.aliasClasses.get(patternNode.alias);
@@ -174,7 +370,8 @@ private void addStepsFor(OSelectExecutionPlan plan, EdgeTraversal edge, OCommand
       select.setWhereClause(where == null ? null : where.copy());
       OBasicCommandContext subContxt = new OBasicCommandContext();
       subContxt.setParentWithoutOverridingChild(context);
-      plan.chain(new MatchFirstStep(context, patternNode, select.createExecutionPlan(subContxt, profilingEnabled), profilingEnabled));
+      plan.chain(
+          new MatchFirstStep(context, patternNode, select.createExecutionPlan(subContxt, profilingEnabled), profilingEnabled));
     }
     if (edge.edge.in.isOptionalNode()) {
       foundOptional = true;
@@ -184,13 +381,15 @@ private void addStepsFor(OSelectExecutionPlan plan, EdgeTraversal edge, OCommand
     }
   }
 
-  private void addPrefetchSteps(OSelectExecutionPlan result, Set<String> aliasesToPrefetch, OCommandContext context, boolean profilingEnabled) {
+  private void addPrefetchSteps(OSelectExecutionPlan result, Set<String> aliasesToPrefetch, OCommandContext context,
+      boolean profilingEnabled) {
     for (String alias : aliasesToPrefetch) {
       String targetClass = aliasClasses.get(alias);
       OWhereClause filter = aliasFilters.get(alias);
       OSelectStatement prefetchStm = createSelectStatement(targetClass, filter);
 
-      MatchPrefetchStep step = new MatchPrefetchStep(context, prefetchStm.createExecutionPlan(context, profilingEnabled), alias, profilingEnabled);
+      MatchPrefetchStep step = new MatchPrefetchStep(context, prefetchStm.createExecutionPlan(context, profilingEnabled), alias,
+          profilingEnabled);
       result.chain(step);
     }
   }
diff --git a/core/src/main/java/com/orientechnologies/orient/core/sql/parser/Pattern.java b/core/src/main/java/com/orientechnologies/orient/core/sql/parser/Pattern.java
@@ -11,8 +11,8 @@
  * Created by luigidellaquila on 28/07/15.
  */
 public class Pattern {
-  Map<String, PatternNode> aliasToNode = new LinkedHashMap<String, PatternNode>();
-  int                      numOfEdges  = 0;
+  public Map<String, PatternNode> aliasToNode = new LinkedHashMap<String, PatternNode>();
+  public int                      numOfEdges  = 0;
 
   public void addExpression(OMatchExpression expression) {
     PatternNode originNode = getOrCreateNode(expression.origin);
