diff options
author | Jon Bratseth <bratseth@oath.com> | 2020-08-05 10:03:10 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2020-08-05 10:03:10 +0200 |
commit | 75b7675c38fddf27daf17bcb46fc575d8dc8049e (patch) | |
tree | 3ab2e62f2cb75b7f655dd11577650cac5725ccd1 /container-search | |
parent | 78d1d7c83099639947edb423c67df4961a2cf5e4 (diff) | |
parent | 356d86da69178183e27ddb30907c810e228ad8c2 (diff) |
Merge pull request #13981 from vespa-engine/bratseth/compact
Bratseth/compact
Diffstat (limited to 'container-search')
8 files changed, 106 insertions, 51 deletions
diff --git a/container-search/abi-spec.json b/container-search/abi-spec.json index a338bb5d8e7..37a75f39e87 100644 --- a/container-search/abi-spec.json +++ b/container-search/abi-spec.json @@ -6037,6 +6037,7 @@ ], "methods": [ "public static com.yahoo.search.query.profile.compiled.Binding createFrom(com.yahoo.search.query.profile.DimensionBinding)", + "public boolean generalizes(com.yahoo.search.query.profile.compiled.Binding)", "public boolean isNull()", "public java.lang.String toString()", "public boolean equals(java.lang.Object)", @@ -6108,7 +6109,7 @@ ], "methods": [ "public void <init>()", - "public void put(java.lang.Object, com.yahoo.search.query.profile.DimensionBinding, java.lang.Object)", + "public void put(com.yahoo.processing.request.CompoundName, com.yahoo.search.query.profile.DimensionBinding, java.lang.Object)", "public com.yahoo.search.query.profile.compiled.DimensionalMap build()" ], "fields": [] @@ -6120,7 +6121,7 @@ "public" ], "methods": [ - "public java.lang.Object get(java.lang.Object, java.util.Map)", + "public java.lang.Object get(com.yahoo.processing.request.CompoundName, java.util.Map)", "public java.util.Set entrySet()", "public boolean isEmpty()" ], @@ -6134,7 +6135,7 @@ ], "methods": [ "public void <init>()", - "public java.lang.Object valueFor(com.yahoo.search.query.profile.DimensionBinding)", + "public java.lang.Object valueFor(com.yahoo.search.query.profile.compiled.Binding)", "public void add(java.lang.Object, com.yahoo.search.query.profile.DimensionBinding)", "public com.yahoo.search.query.profile.compiled.DimensionalValue build(java.util.Map)" ], 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 5dacd347c2c..3010c6a9d09 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 @@ -32,10 +32,10 @@ public class QueryProfileCompiler { public static CompiledQueryProfile compile(QueryProfile in, CompiledQueryProfileRegistry registry) { try { - DimensionalMap.Builder<CompoundName, ValueWithSource> values = new DimensionalMap.Builder<>(); - DimensionalMap.Builder<CompoundName, QueryProfileType> types = new DimensionalMap.Builder<>(); - DimensionalMap.Builder<CompoundName, Object> references = new DimensionalMap.Builder<>(); - DimensionalMap.Builder<CompoundName, Object> unoverridables = new DimensionalMap.Builder<>(); + DimensionalMap.Builder<ValueWithSource> values = new DimensionalMap.Builder<>(); + DimensionalMap.Builder<QueryProfileType> types = new DimensionalMap.Builder<>(); + DimensionalMap.Builder<Object> references = new DimensionalMap.Builder<>(); + DimensionalMap.Builder<Object> unoverridables = new DimensionalMap.Builder<>(); // Resolve values for each existing variant and combine into a single data structure Set<DimensionBindingForPath> variants = collectVariants(CompoundName.empty, in, DimensionBinding.nullBinding); 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 27f600f9ad6..3812cdaac3c 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 @@ -86,6 +86,27 @@ public class Binding implements Comparable<Binding> { this.hashCode = Arrays.hashCode(dimensions) + 11 * Arrays.hashCode(dimensionValues); } + /** + * Returns whether this binding is a proper generalization of the given binding: + * Meaning it contains a proper subset of the given bindings. + */ + public boolean generalizes(Binding binding) { + if ( dimensions.length >= binding.dimensions.length) return false; + for (int i = 0; i < dimensions.length; i++) { + int indexOfDimension = indexOf(dimensions[i], binding.dimensions); + if (indexOfDimension < 0) return false; + if ( ! binding.dimensionValues[i].equals(binding.dimensionValues[indexOfDimension])) return false; + } + return true; + } + + private int indexOf(String value, String[] array) { + for (int i = 0; i < array.length; i++) { + if (array[i].equals(value)) + return i; + } + return -1; + } /** Returns true only if this binding is null (contains no values for its dimensions (if any) */ public boolean isNull() { return dimensions.length == 0; } diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/CompiledQueryProfile.java b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/CompiledQueryProfile.java index 9be459ceeab..c6b0f4a533b 100644 --- a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/CompiledQueryProfile.java +++ b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/CompiledQueryProfile.java @@ -30,26 +30,26 @@ public class CompiledQueryProfile extends AbstractComponent implements Cloneable private final QueryProfileType type; /** The values of this */ - private final DimensionalMap<CompoundName, ValueWithSource> entries; + private final DimensionalMap<ValueWithSource> entries; /** Keys which have a type in this */ - private final DimensionalMap<CompoundName, QueryProfileType> types; + private final DimensionalMap<QueryProfileType> types; /** Keys which are (typed or untyped) references to other query profiles in this. Used as a set. */ - private final DimensionalMap<CompoundName, Object> references; + private final DimensionalMap<Object> references; /** Values which are not overridable in this. Used as a set. */ - private final DimensionalMap<CompoundName, Object> unoverridables; + private final DimensionalMap<Object> unoverridables; /** * Creates a new query profile from an id. */ public CompiledQueryProfile(ComponentId id, QueryProfileType type, - DimensionalMap<CompoundName, ValueWithSource> entries, - DimensionalMap<CompoundName, QueryProfileType> types, - DimensionalMap<CompoundName, Object> references, - DimensionalMap<CompoundName, Object> unoverridables, + DimensionalMap<ValueWithSource> entries, + DimensionalMap<QueryProfileType> types, + DimensionalMap<Object> references, + DimensionalMap<Object> unoverridables, CompiledQueryProfileRegistry registry) { super(id); this.registry = registry; @@ -91,10 +91,10 @@ public class CompiledQueryProfile extends AbstractComponent implements Cloneable } /** Returns the types reachable from this, or an empty map (never null) if none */ - public DimensionalMap<CompoundName, QueryProfileType> getTypes() { return types; } + public DimensionalMap<QueryProfileType> getTypes() { return types; } /** Returns the references reachable from this, or an empty map (never null) if none */ - public DimensionalMap<CompoundName, Object> getReferences() { return references; } + public DimensionalMap<Object> getReferences() { return references; } /** * Return all objects that start with the given prefix path using no context. Use "" to list all. diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalMap.java b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalMap.java index 2e8f5dcf91c..b6bd6dc5a6a 100644 --- a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalMap.java +++ b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalMap.java @@ -2,6 +2,7 @@ package com.yahoo.search.query.profile.compiled; import com.google.common.collect.ImmutableMap; +import com.yahoo.processing.request.CompoundName; import com.yahoo.search.query.profile.DimensionBinding; import java.util.HashMap; @@ -16,23 +17,23 @@ import java.util.Set; * * @author bratseth */ -public class DimensionalMap<KEY, VALUE> { +public class DimensionalMap<VALUE> { - private final Map<KEY, DimensionalValue<VALUE>> values; + private final Map<CompoundName, DimensionalValue<VALUE>> values; - private DimensionalMap(Map<KEY, DimensionalValue<VALUE>> values) { + private DimensionalMap(Map<CompoundName, DimensionalValue<VALUE>> values) { this.values = ImmutableMap.copyOf(values); } /** Returns the value for this key matching a context, or null if none */ - public VALUE get(KEY key, Map<String, String> context) { + public VALUE get(CompoundName key, Map<String, String> context) { DimensionalValue<VALUE> variants = values.get(key); if (variants == null) return null; return variants.get(context); } /** Returns the set of dimensional entries across all contexts. */ - public Set<Map.Entry<KEY, DimensionalValue<VALUE>>> entrySet() { + public Set<Map.Entry<CompoundName, DimensionalValue<VALUE>>> entrySet() { return values.entrySet(); } @@ -41,12 +42,12 @@ public class DimensionalMap<KEY, VALUE> { return values.isEmpty(); } - public static class Builder<KEY, VALUE> { + public static class Builder<VALUE> { - private Map<KEY, DimensionalValue.Builder<VALUE>> entries = new HashMap<>(); + private final Map<CompoundName, DimensionalValue.Builder<VALUE>> entries = new HashMap<>(); // TODO: DimensionBinding -> Binding? - public void put(KEY key, DimensionBinding binding, VALUE value) { + public void put(CompoundName key, DimensionBinding binding, VALUE value) { DimensionalValue.Builder<VALUE> entry = entries.get(key); if (entry == null) { entry = new DimensionalValue.Builder<>(); @@ -55,9 +56,9 @@ public class DimensionalMap<KEY, VALUE> { entry.add(value, binding); } - public DimensionalMap<KEY, VALUE> build() { - Map<KEY, DimensionalValue<VALUE>> map = new HashMap<>(); - for (Map.Entry<KEY, DimensionalValue.Builder<VALUE>> entry : entries.entrySet()) { + public DimensionalMap<VALUE> build() { + Map<CompoundName, DimensionalValue<VALUE>> map = new HashMap<>(); + for (Map.Entry<CompoundName, DimensionalValue.Builder<VALUE>> entry : entries.entrySet()) { map.put(entry.getKey(), entry.getValue().build(entries)); } return new DimensionalMap<>(map); 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 c1ee49913fe..cd1eabc2e32 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 @@ -63,11 +63,11 @@ public class DimensionalValue<VALUE> { public static class Builder<VALUE> { - /** The minimal set of variants needed to capture all values at this key */ - private Map<VALUE, Value.Builder<VALUE>> buildableVariants = new HashMap<>(); + /** The variants of the value of this key */ + private final Map<VALUE, Value.Builder<VALUE>> buildableVariants = new HashMap<>(); /** Returns the value for the given binding, or null if none */ - public VALUE valueFor(DimensionBinding variantBinding) { + public VALUE valueFor(Binding variantBinding) { for (var entry : buildableVariants.entrySet()) { if (entry.getValue().variants.contains(variantBinding)) return entry.getKey(); @@ -77,8 +77,8 @@ public class DimensionalValue<VALUE> { public void add(VALUE value, DimensionBinding variantBinding) { // Note: We know we can index by the value because its possible types are constrained - // to what query profiles allow: String, primitives and query profiles - Value.Builder variant = buildableVariants.get(value); + // to what query profiles allow: String, primitives and query profiles (wrapped as a ValueWithSource) + Value.Builder<VALUE> variant = buildableVariants.get(value); if (variant == null) { variant = new Value.Builder<>(value); buildableVariants.put(value, variant); @@ -86,23 +86,29 @@ public class DimensionalValue<VALUE> { variant.addVariant(variantBinding); } - public DimensionalValue<VALUE> build(Map<?, DimensionalValue.Builder<VALUE>> entries) { - List<Value> variants = new ArrayList<>(); - for (Value.Builder buildableVariant : buildableVariants.values()) { + public DimensionalValue<VALUE> build(Map<CompoundName, DimensionalValue.Builder<VALUE>> entries) { + List<Value<VALUE>> variants = new ArrayList<>(); + if (buildableVariants.size() == 1) { + // Compact size 1 as it is common and easy to do. To compact size > 1 we would need to + // compact within generic intervals having the same value + for (Value.Builder<VALUE> buildableVariant : buildableVariants.values()) + buildableVariant.compact(); + } + for (Value.Builder<VALUE> buildableVariant : buildableVariants.values()) { variants.addAll(buildableVariant.build(entries)); } - return new DimensionalValue(variants); + return new DimensionalValue<>(variants); } } /** A value for a particular binding */ - private static class Value<VALUE> implements Comparable<Value> { + private static class Value<VALUE> implements Comparable<Value<VALUE>> { - private VALUE value; + private final VALUE value; /** The minimal binding this holds for */ - private Binding binding; + private final Binding binding; public Value(VALUE value, Binding binding) { this.value = value; @@ -141,7 +147,7 @@ public class DimensionalValue<VALUE> { * Some of these are more general versions of others. * We need to keep both to allow interleaving a different value with medium generality. */ - private Set<DimensionBinding> variants = new HashSet<>(); + private List<Binding> variants = new ArrayList<>(); public Builder(VALUE value) { this.value = value; @@ -149,20 +155,44 @@ public class DimensionalValue<VALUE> { /** Add a binding this holds for */ public void addVariant(DimensionBinding binding) { - variants.add(binding); + variants.add(Binding.createFrom(binding)); + } + + /** Remove variants that are specializations of other variants in this */ + void compact() { + Collections.sort(variants); + List<Binding> compacted = new ArrayList<>(); + if (variants.get(variants.size() - 1).dimensions().length == 0) { // Shortcut + variants = List.of(variants.get(variants.size() - 1)); + } + else { + for (int i = variants.size() - 1; i >= 0; i--) { + if (!containsGeneralizationOf(variants.get(i), compacted)) + compacted.add(variants.get(i)); + } + Collections.reverse(compacted); + variants = compacted; + } + } + + private boolean containsGeneralizationOf(Binding binding, List<Binding> bindings) { + for (Binding candidate : bindings) { + if (candidate.generalizes(binding)) + return true; + } + return false; } /** Build a separate value object for each dimension combination which has this value */ public List<Value<VALUE>> build(Map<CompoundName, DimensionalValue.Builder<VALUE>> entries) { - // Shortcut for efficiency of the normal case - if (variants.size() == 1) { - return Collections.singletonList(new Value<>(substituteIfRelative(value, variants.iterator().next(), entries), - Binding.createFrom(variants.iterator().next()))); + if (variants.size() == 1) { // Shortcut + return List.of(new Value<>(substituteIfRelative(value, variants.iterator().next(), entries), + variants.iterator().next())); } List<Value<VALUE>> values = new ArrayList<>(variants.size()); - for (DimensionBinding variant : variants) { - values.add(new Value<>(substituteIfRelative(value, variant, entries), Binding.createFrom(variant))); + for (Binding variant : variants) { + values.add(new Value<>(substituteIfRelative(value, variant, entries), variant)); } return values; } @@ -174,7 +204,7 @@ public class DimensionalValue<VALUE> { // TODO: Move this @SuppressWarnings("unchecked") private VALUE substituteIfRelative(VALUE value, - DimensionBinding variant, + Binding variant, Map<CompoundName, DimensionalValue.Builder<VALUE>> entries) { if (value instanceof ValueWithSource && ((ValueWithSource)value).value() instanceof SubstituteString) { ValueWithSource valueWithSource = (ValueWithSource)value; @@ -188,7 +218,7 @@ public class DimensionalValue<VALUE> { if (substituteValues == null) throw new IllegalArgumentException("Could not resolve local substitution '" + relativeComponent.fieldName() + "' in variant " + - variant); + Arrays.toString(variant.dimensionValues())); ValueWithSource resolved = (ValueWithSource)substituteValues.valueFor(variant); resolvedComponents.add(new SubstituteString.StringComponent(resolved.value().toString())); } 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 445073ced3a..a6acde87e30 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 @@ -4,6 +4,7 @@ package com.yahoo.search.query.profile.config.test; import com.yahoo.jdisc.http.HttpRequest.Method; import com.yahoo.container.jdisc.HttpRequest; import com.yahoo.processing.request.CompoundName; +import com.yahoo.search.query.profile.compiled.DimensionalValue; import com.yahoo.yolean.Exceptions; import com.yahoo.search.Query; import com.yahoo.search.query.Properties; @@ -14,6 +15,7 @@ import com.yahoo.search.query.profile.compiled.CompiledQueryProfileRegistry; import com.yahoo.search.query.profile.config.QueryProfileXMLReader; import com.yahoo.search.query.profile.types.FieldDescription; import com.yahoo.search.query.profile.types.QueryProfileType; +import org.junit.Ignore; import org.junit.Test; import java.util.HashMap; diff --git a/container-search/src/test/java/com/yahoo/search/query/profile/test/QueryProfileSubstitutionTestCase.java b/container-search/src/test/java/com/yahoo/search/query/profile/test/QueryProfileSubstitutionTestCase.java index b3b83b9c07e..4720b92848a 100644 --- a/container-search/src/test/java/com/yahoo/search/query/profile/test/QueryProfileSubstitutionTestCase.java +++ b/container-search/src/test/java/com/yahoo/search/query/profile/test/QueryProfileSubstitutionTestCase.java @@ -54,7 +54,7 @@ public class QueryProfileSubstitutionTestCase { fail("Expected exception"); } catch (IllegalArgumentException e) { - assertEquals("Invalid query profile 'test': Could not resolve local substitution 'world' in variant DimensionBinding []", + assertEquals("Invalid query profile 'test': Could not resolve local substitution 'world' in variant []", Exceptions.toMessageString(e)); } } |