Faster lookup given many variants

4 files changed, 133 insertions, 30 deletions

diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/Binding.java b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/Binding.java
index 88014eef46d..27f600f9ad6 100644
--- a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/Binding.java
+++ b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/Binding.java
@@ -57,27 +57,44 @@ public class Binding implements Comparable<Binding> {
         return new Binding(generality, context);
     }
 
-    private Binding(int generality, Map<String, String> binding) {
+    /** Creates a binding from a map containing the exact bindings this will have */
+    private Binding(int generality, Map<String, String> bindings) {
         this.generality = generality;
 
         // Map -> arrays to limit memory consumption and speed up evaluation
-        dimensions = new String[binding.size()];
-        dimensionValues = new String[binding.size()];
+        dimensions = new String[bindings.size()];
+        dimensionValues = new String[bindings.size()];
 
         int i = 0;
-        int bindingHash = 0;
-        for (Map.Entry<String,String> entry : binding.entrySet()) {
+        for (Map.Entry<String,String> entry : bindings.entrySet()) {
             dimensions[i] = entry.getKey();
             dimensionValues[i] = entry.getValue();
-            bindingHash += i * entry.getKey().hashCode() +  11 * i * entry.getValue().hashCode();
             i++;
         }
-        this.hashCode = bindingHash;
+        this.hashCode = Arrays.hashCode(dimensions) + 11 * Arrays.hashCode(dimensionValues);
     }
 
+    Binding(DimensionalValue.BindingSpec spec, Map<String, String> bindings) {
+        this.generality = 0; // Not used here
+
+        // Map -> arrays to limit memory consumption and speed up evaluation
+        dimensions = spec.dimensions();
+        dimensionValues = new String[spec.dimensions().length];
+        for (int i = 0; i < dimensions.length; i++) {
+            dimensionValues[i] = bindings.get(dimensions[i]);
+        }
+        this.hashCode = Arrays.hashCode(dimensions) + 11 * Arrays.hashCode(dimensionValues);
+    }
+
+
     /** Returns true only if this binding is null (contains no values for its dimensions (if any) */
     public boolean isNull() { return dimensions.length == 0; }
 
+    /** Do not change the returtned array */
+    String[] dimensions() { return dimensions; }
+
+    String[] dimensionValues() { return dimensionValues; }
+
     @Override
     public String toString() {
         StringBuilder b = new StringBuilder("Binding[");
@@ -116,7 +133,7 @@ public class Binding implements Comparable<Binding> {
     /**
      * Implements a partial ordering where more specific bindings come before less specific ones,
      * taking both the number of bindings and their positions into account (earlier dimensions
-     * take precedence over later ones.
+     * take precedence over later ones).
      * <p>
      * The order is not well defined for bindings in different dimensional spaces.
      */
diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalValue.java b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalValue.java
index 0137b848dac..c1ee49913fe 100644
--- a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalValue.java
+++ b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalValue.java
@@ -6,6 +6,7 @@ import com.yahoo.search.query.profile.DimensionBinding;
 import com.yahoo.search.query.profile.SubstituteString;
 
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
@@ -20,20 +21,22 @@ import java.util.Set;
  */
 public class DimensionalValue<VALUE> {
 
-    private final List<Value<VALUE>> values;
+    private final Map<Binding, VALUE> indexedVariants;
+    private final List<BindingSpec> bindingSpecs;
 
-    /** Create a set of variants which is a single value regardless of dimensions */
-    public DimensionalValue(Value<VALUE> value) {
-        this.values = Collections.singletonList(value);
-    }
+    private DimensionalValue(List<Value<VALUE>> variants) {
+        Collections.sort(variants);
 
-    public DimensionalValue(List<Value<VALUE>> valueVariants) {
-        if (valueVariants.size() == 1) { // special cased for efficiency
-            this.values = Collections.singletonList(valueVariants.get(0));
-        }
-        else {
-            this.values = new ArrayList<>(valueVariants);
-            Collections.sort(this.values);
+        // If there are inconsistent definitions of the same property, we should pick the first in the sort order
+        this.indexedVariants = new HashMap<>();
+        for (Value<VALUE> variant : variants)
+            indexedVariants.putIfAbsent(variant.binding(), variant.value());
+
+        this.bindingSpecs = new ArrayList<>();
+        for (Value<VALUE> variant : variants) {
+            BindingSpec spec = new BindingSpec(variant.binding());
+            if ( ! bindingSpecs.contains(spec))
+                bindingSpecs.add(spec);
         }
     }
 
@@ -41,18 +44,21 @@ public class DimensionalValue<VALUE> {
     public VALUE get(Map<String, String> context) {
         if (context == null)
             context = Collections.emptyMap();
-        for (Value<VALUE> value : values) {
-            if (value.matches(context))
-                return value.value();
+
+        for (BindingSpec spec : bindingSpecs) {
+            if ( ! spec.matches(context)) continue;
+            VALUE value = indexedVariants.get(new Binding(spec, context));
+            if (value != null)
+                return value;
         }
         return null;
     }
 
-    public boolean isEmpty() { return values.isEmpty(); }
+    public boolean isEmpty() { return indexedVariants.isEmpty(); }
 
     @Override
     public String toString() {
-        return values.toString();
+        return indexedVariants.toString();
     }
 
     public static class Builder<VALUE> {
@@ -93,7 +99,7 @@ public class DimensionalValue<VALUE> {
     /** A value for a particular binding */
     private static class Value<VALUE> implements Comparable<Value> {
 
-        private VALUE value = null;
+        private VALUE value;
 
         /** The minimal binding this holds for */
         private Binding binding;
@@ -126,9 +132,6 @@ public class DimensionalValue<VALUE> {
             return " value '" + value + "' for " + binding;
         }
 
-        /**
-         * A single value with the minimal set of dimension combinations it holds for.
-         */
         private static class Builder<VALUE> {
 
             private final VALUE value;
@@ -212,4 +215,38 @@ public class DimensionalValue<VALUE> {
 
     }
 
+    /** A list of dimensions for which there exist one or more bindings in this */
+    static class BindingSpec {
+
+        /** The dimensions of this. Unenforced invariant: Content never changes. */
+        private final String[] dimensions;
+
+        public BindingSpec(Binding binding) {
+            this.dimensions = binding.dimensions();
+        }
+
+        /** Do not change the returned array */
+        String[] dimensions() { return dimensions; }
+
+        /** Returns whether this context contains all the keys of this */
+        public boolean matches(Map<String, String> context) {
+            for (int i = 0; i < dimensions.length; i++)
+                if ( ! context.containsKey(dimensions[i])) return false;
+            return true;
+        }
+
+        @Override
+        public int hashCode() {
+            return Arrays.hashCode(dimensions);
+        }
+
+        @Override
+        public boolean equals(Object other) {
+            if (other == this) return true;
+            if ( ! (other instanceof BindingSpec)) return false;
+            return Arrays.equals(((BindingSpec)other).dimensions, this.dimensions);
+        }
+
+    }
+
 }
diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/ValueWithSource.java b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/ValueWithSource.java
index bc49e116c6e..d2c4eaaec9b 100644
--- a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/ValueWithSource.java
+++ b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/ValueWithSource.java
@@ -2,9 +2,9 @@
 package com.yahoo.search.query.profile.compiled;
 
 import com.yahoo.search.query.profile.DimensionValues;
-import com.yahoo.search.query.profile.QueryProfile;
 import com.yahoo.search.query.profile.types.QueryProfileType;
 
+import java.util.Objects;
 import java.util.Optional;
 
 /**
@@ -68,6 +68,24 @@ public class ValueWithSource {
     public Optional<DimensionValues> variant() { return Optional.ofNullable(variant); }
 
     @Override
+    public int hashCode() {
+        // Value is always a value object. Don't include source in identity.
+        return Objects.hash(value, isUnoverridable, type);
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (o == this) return true;
+        if ( ! (o instanceof ValueWithSource)) return false;
+
+        ValueWithSource other = (ValueWithSource)o;
+        if ( ! Objects.equals(this.value, other.value)) return false;
+        if ( ! Objects.equals(this.isUnoverridable, other.isUnoverridable)) return false;
+        if ( ! Objects.equals(this.type, other.type)) return false;
+        return true;
+    }
+
+    @Override
     public String toString() {
         return value +
                " (from query profile '" + source + "'" +
diff --git a/container-search/src/test/java/com/yahoo/search/query/profile/config/test/XmlReadingTestCase.java b/container-search/src/test/java/com/yahoo/search/query/profile/config/test/XmlReadingTestCase.java
index e85940278e3..bd14efb4dfa 100644
--- a/container-search/src/test/java/com/yahoo/search/query/profile/config/test/XmlReadingTestCase.java
+++ b/container-search/src/test/java/com/yahoo/search/query/profile/config/test/XmlReadingTestCase.java
@@ -32,6 +32,37 @@ import static org.junit.Assert.fail;
 public class XmlReadingTestCase {
 
     @Test
+    @Ignore
+    public void testTmp() {
+        QueryProfileRegistry registry =
+                new QueryProfileXMLReader().read("/Users/bratseth/development/slingstone/massmedia_serving/homerun/src/main/application/search/flattened");
+        long startTime = System.currentTimeMillis();
+        System.out.println("Compiling ...");
+        CompiledQueryProfileRegistry cRegistry = registry.compile();
+        System.out.println("Done in " + (( System.currentTimeMillis() - startTime) / 1000) + " seconds");
+        System.out.println("");
+        CompiledQueryProfile cProfile = cRegistry.getComponent("megastream_unified");
+
+        Query q = new Query("?debug=true&clientId=default&langReg=en-US&format=xml&tracelevel=4&" +
+                            "trace.timestamps=true&site=frontpage&streamBucketId=ga&configId=default&" +
+                            "queryProfile=megastream_unified&lang=ENGLISH&region=US&", cProfile);
+        q.properties().listProperties();
+
+        // About 60 ms with tracelevel=4, a few ms with tracelevel=0
+        startTime = System.currentTimeMillis();
+        System.out.println("Creating query ...");
+        new Query("?debug=true&clientId=default&langReg=en-US&format=xml&tracelevel=0&" +
+                  "trace.timestamps=true&site=frontpage&streamBucketId=ga&configId=default&" +
+                  "queryProfile=megastream_unified&lang=ENGLISH&region=US&", cProfile);
+        System.out.println("Done in " + (System.currentTimeMillis() - startTime) + " ms");
+
+        startTime = System.currentTimeMillis();
+        System.out.println("listProperties() ...");
+        q.properties().listProperties().forEach((k, v) -> System.out.println("  " + k + "=" + v));
+        System.out.println("Done in " + (System.currentTimeMillis() - startTime) + " ms");
+    }
+
+    @Test
     public void testInheritance() {
         QueryProfileRegistry registry =
                 new QueryProfileXMLReader().read("src/test/java/com/yahoo/search/query/profile/config/test/inheritance");