From 22f2fda9aaea0e132e46b01f62fbd85c87a2a07c Mon Sep 17 00:00:00 2001
From: Jon Marius Venstad <venstad@gmail.com>
Date: Thu, 7 Jan 2021 22:58:38 +0100
Subject: Use a trie for variants, keyed on path, to look up prefix paths

This eliminates 40% of the total run time, which was spent on path prefix considerations
---
 .../search/query/profile/QueryProfileCompiler.java | 80 +++++++++++++++++-----
 1 file changed, 63 insertions(+), 17 deletions(-)

(limited to 'container-search/src')

diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/QueryProfileCompiler.java b/container-search/src/main/java/com/yahoo/search/query/profile/QueryProfileCompiler.java
index b7103fff8fe..e3cadd7b795 100644
--- a/container-search/src/main/java/com/yahoo/search/query/profile/QueryProfileCompiler.java
+++ b/container-search/src/main/java/com/yahoo/search/query/profile/QueryProfileCompiler.java
@@ -8,11 +8,15 @@ import com.yahoo.search.query.profile.compiled.DimensionalMap;
 import com.yahoo.search.query.profile.compiled.ValueWithSource;
 import com.yahoo.search.query.profile.types.QueryProfileType;
 
+import java.util.ArrayList;
 import java.util.HashSet;
+import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.SortedMap;
+import java.util.TreeMap;
+import java.util.function.Consumer;
 import java.util.logging.Logger;
-import java.util.stream.Collectors;
 
 /**
  * Compile a set of query profiles into compiled profiles.
@@ -103,9 +107,18 @@ public class QueryProfileCompiler {
     private static Set<DimensionBindingForPath> wildcardExpanded(Set<DimensionBindingForPath> variants) {
         Set<DimensionBindingForPath> expanded = new HashSet<>();
 
+        PathTree trie = new PathTree();
+        for (var variant : variants)
+            trie.add(variant);
+
         for (var variant : variants) {
-            if (hasWildcardBeforeEnd(variant.binding()))
-                expanded.addAll(wildcardExpanded(variant, variants));
+            if ( ! variant.binding.isNull())
+                trie.forEachPrefix(variant, prefixVariant -> {
+                    if ( ! hasWildcardBeforeEnd(prefixVariant.binding)) return;
+                    DimensionBinding combined = prefixVariant.binding().combineWith(variant.binding());
+                    if ( ! combined.isInvalid() )
+                        expanded.add(new DimensionBindingForPath(combined, prefixVariant.path()));
+                });
         }
         return expanded;
     }
@@ -118,20 +131,6 @@ public class QueryProfileCompiler {
         return false;
     }
 
-    private static Set<DimensionBindingForPath> wildcardExpanded(DimensionBindingForPath variantToExpand,
-                                                                 Set<DimensionBindingForPath> variants) {
-        Set<DimensionBindingForPath> expanded = new HashSet<>();
-        for (var variant : variants) {
-            if (variant.binding().isNull()) continue;
-            if ( ! variant.path().hasPrefix(variantToExpand.path())) continue;
-            DimensionBinding combined = variantToExpand.binding().combineWith(variant.binding());
-            if ( ! combined.isInvalid() )
-                expanded.add(new DimensionBindingForPath(combined, variantToExpand.path()));
-        }
-        return expanded;
-    }
-
-
     /** Generates a set of all the (legal) combinations of the variants in the given sets */
     private static Set<DimensionBindingForPath> combined(Set<DimensionBindingForPath> v1s,
                                                          Set<DimensionBindingForPath> v2s) {
@@ -214,4 +213,51 @@ public class QueryProfileCompiler {
 
     }
 
+
+    /**
+     * Simple trie for CompoundName paths.
+     *
+     * @author jonmv
+     */
+    static class PathTree {
+
+        private final Node root = new Node(0);
+
+        void add(DimensionBindingForPath entry) {
+            root.add(entry);
+        }
+
+         void forEachPrefix(DimensionBindingForPath entry, Consumer<DimensionBindingForPath> action) {
+            root.visit(entry, action);
+         }
+
+        private static class Node {
+
+            private final int depth;
+            private final SortedMap<String, Node> children = new TreeMap<>();
+            private final List<DimensionBindingForPath> elements = new ArrayList<>();
+
+            private Node(int depth) {
+                this.depth = depth;
+            }
+
+            void visit(DimensionBindingForPath entry, Consumer<DimensionBindingForPath> action) {
+                elements.forEach(action);
+                if (depth < entry.path().size() && children.containsKey(entry.path().get(depth)))
+                    children.get(entry.path().get(depth)).visit(entry, action);
+            }
+
+            void add(DimensionBindingForPath entry) {
+                if (depth == entry.path().size())
+                    elements.add(entry);
+                else
+                    children.computeIfAbsent(entry.path().get(depth),
+                                             __ -> new Node(depth + 1)).add(entry);
+            }
+
+        }
+
+    }
+
+
 }
-- 
cgit v1.2.3