diff options
author | Jon Bratseth <bratseth@gmail.com> | 2020-07-17 11:45:27 +0200 |
---|---|---|
committer | Jon Bratseth <bratseth@gmail.com> | 2020-07-17 11:45:27 +0200 |
commit | 667eedc92b4c9c81c3872e000a8f26779b9bf131 (patch) | |
tree | d1ff7e4115c70877104c1f0e803417e50399f925 /container-search | |
parent | 8dad7e25c8d1bd022880327a0c7f57e48efc302f (diff) |
Faster lookup given many variants
Diffstat (limited to 'container-search')
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®ion=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®ion=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"); |