diff options
Diffstat (limited to 'predicate-search-core/src/main/java/com/yahoo/search')
11 files changed, 732 insertions, 0 deletions
diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/PredicateQueryParser.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/PredicateQueryParser.java new file mode 100644 index 00000000000..6f5fac54354 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/PredicateQueryParser.java @@ -0,0 +1,132 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate; + +import com.fasterxml.jackson.core.JsonFactory; +import com.fasterxml.jackson.core.JsonParser; +import com.fasterxml.jackson.core.JsonToken; +import org.apache.commons.lang.ArrayUtils; + +import java.io.IOException; +import java.util.Arrays; + +/** + * Parses predicate queries from JSON. + * + * Input JSON is assumed to have the following format: + * { + * "features": [ + * {"k": "key-name", "v":"value", "s":"0xDEADBEEFDEADBEEF"} + * ], + * "rangeFeatures": [ + * {"k": "key-name", "v":42, "s":"0xDEADBEEFDEADBEEF"} + * ] + * } + * + * @author bjorncs + */ +public class PredicateQueryParser { + private final JsonFactory factory = new JsonFactory(); + + @FunctionalInterface + public interface FeatureHandler<V> { + void accept(String key, V value, long subqueryBitmap); + } + + /** + * Parses predicate query from JSON. + * @param json JSON input. + * @param featureHandler The handler is invoked when a feature is parsed. + * @param rangeFeatureHandler The handler is invoked when a range feature is parsed. + * @throws IllegalArgumentException If JSON is invalid. + */ + public void parseJsonQuery( + String json, FeatureHandler<String> featureHandler, FeatureHandler<Long> rangeFeatureHandler) + throws IllegalArgumentException { + + try (JsonParser parser = factory.createParser(json)) { + skipToken(parser, JsonToken.START_OBJECT); + while (parser.nextToken() != JsonToken.END_OBJECT) { + String fieldName = parser.getCurrentName(); + switch (fieldName) { + case "features": + parseFeatures(parser, JsonParser::getText, featureHandler); + break; + case "rangeFeatures": + parseFeatures(parser, JsonParser::getLongValue, rangeFeatureHandler); + break; + default: + throw new IllegalArgumentException("Invalid field name: " + fieldName); + } + } + } catch (IllegalArgumentException e) { + throw e; + } catch (IOException e) { + throw new AssertionError("This should never happen when parsing from a String", e); + } catch (Exception e) { + throw new IllegalArgumentException(String.format("Parsing query from JSON failed: '%s'", json), e); + } + } + + private static <V> void parseFeatures( + JsonParser parser, ValueParser<V> valueParser, FeatureHandler<V> featureHandler) throws IOException { + skipToken(parser, JsonToken.START_ARRAY); + while (parser.nextToken() != JsonToken.END_ARRAY) { + parseFeature(parser, valueParser, featureHandler); + } + } + + private static <V> void parseFeature( + JsonParser parser, ValueParser<V> valueParser, FeatureHandler<V> featureHandler) throws IOException { + String key = null; + V value = null; + long subqueryBitmap = SubqueryBitmap.DEFAULT_VALUE; // Specifying subquery bitmap is optional. + + while (parser.nextToken() != JsonToken.END_OBJECT) { + String fieldName = parser.getCurrentName(); + skipToken(parser, JsonToken.VALUE_STRING, JsonToken.VALUE_NUMBER_INT); + switch (fieldName) { + case "k": + key = parser.getText(); + break; + case "v": + value = valueParser.parse(parser); + break; + case "s": + subqueryBitmap = fromHexString(parser.getText()); + break; + default: + throw new IllegalArgumentException("Invalid field name: " + fieldName); + } + } + if (key == null) { + throw new IllegalArgumentException( + String.format("Feature key is missing! (%s)", parser.getCurrentLocation())); + } + if (value == null) { + throw new IllegalArgumentException( + String.format("Feature value is missing! (%s)", parser.getCurrentLocation())); + } + featureHandler.accept(key, value, subqueryBitmap); + } + + private static void skipToken(JsonParser parser, JsonToken... expected) throws IOException { + JsonToken actual = parser.nextToken(); + if (!ArrayUtils.contains(expected, actual)) { + throw new IllegalArgumentException( + String.format("Expected a token in %s, got %s (%s).", + Arrays.toString(expected), actual, parser.getTokenLocation())); + } + } + + private static long fromHexString(String subqueryBitmap) { + if (!subqueryBitmap.startsWith("0x")) { + throw new IllegalArgumentException("Not a valid subquery bitmap ('0x' prefix missing): " + subqueryBitmap); + } + return Long.parseUnsignedLong(subqueryBitmap.substring(2), 16); + } + + @FunctionalInterface + private interface ValueParser<V> { + V parse(JsonParser parser) throws IOException; + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/SubqueryBitmap.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/SubqueryBitmap.java new file mode 100644 index 00000000000..84b342f930a --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/SubqueryBitmap.java @@ -0,0 +1,21 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate; + +/** + * Constants related to the subquery bitmap in predicate/boolean search. + * @author bjorncs + */ +public interface SubqueryBitmap { + + /** + * A feature annotated with the following bitmap will be added to all (64) subqueries. + */ + long ALL_SUBQUERIES = 0xFFFF_FFFF_FFFF_FFFFl; + + /** + * Default subquery bitmap. + */ + long DEFAULT_VALUE = ALL_SUBQUERIES; + + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/AndOrSimplifier.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/AndOrSimplifier.java new file mode 100644 index 00000000000..b281f98a94a --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/AndOrSimplifier.java @@ -0,0 +1,70 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.Conjunction; +import com.yahoo.document.predicate.Disjunction; +import com.yahoo.document.predicate.Negation; +import com.yahoo.document.predicate.Predicate; + +import java.util.ArrayList; +import java.util.List; + +/** + * Simplifies a predicate by: + * - Combining child-AND/OR nodes with direct parents of the same type + * - Pushing negations down to leaf nodes by using De Morgan's law. + * + * @author magnarn + * @author bjorncs + */ +public class AndOrSimplifier implements PredicateProcessor { + + public Predicate simplifySubTree(Predicate predicate, boolean negated) { + if (predicate == null) { + return null; + } + if (predicate instanceof Negation) { + return simplifySubTree(((Negation) predicate).getOperand(), !negated); + } else if (predicate instanceof Conjunction) { + List<Predicate> in = ((Conjunction)predicate).getOperands(); + List<Predicate> out = new ArrayList<>(in.size()); + for (Predicate operand : in) { + operand = simplifySubTree(operand, negated); + if (operand instanceof Conjunction) { + out.addAll(((Conjunction)operand).getOperands()); + } else { + out.add(operand); + } + } + if (negated) { + return new Disjunction(out); + } + ((Conjunction)predicate).setOperands(out); + } else if (predicate instanceof Disjunction) { + List<Predicate> in = ((Disjunction)predicate).getOperands(); + List<Predicate> out = new ArrayList<>(in.size()); + for (Predicate operand : in) { + operand = simplifySubTree(operand, negated); + if (operand instanceof Disjunction) { + out.addAll(((Disjunction)operand).getOperands()); + } else { + out.add(operand); + } + } + if (negated) { + return new Conjunction(out); + } + ((Disjunction)predicate).setOperands(out); + } else { + if (negated) { + return new Negation(predicate); + } + } + return predicate; + } + + @Override + public Predicate process(Predicate predicate, PredicateOptions options) { + return simplifySubTree(predicate, false); + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/BooleanSimplifier.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/BooleanSimplifier.java new file mode 100644 index 00000000000..fd1fed8ae15 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/BooleanSimplifier.java @@ -0,0 +1,93 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.BooleanPredicate; +import com.yahoo.document.predicate.Conjunction; +import com.yahoo.document.predicate.Disjunction; +import com.yahoo.document.predicate.Negation; +import com.yahoo.document.predicate.Predicate; +import com.yahoo.document.predicate.PredicateOperator; + +import java.util.ArrayList; +import java.util.List; + +/** + * Simplifies a predicate by collapsing TRUE/FALSE-children into their parents. + * E.g. if an AND node has a FALSE child, the entire node is replaced by FALSE. + * Replaces single-child AND/OR-nodes with the child. + * + * @author magnarn + * @author bjorncs + */ +public class BooleanSimplifier implements PredicateProcessor { + + public Predicate simplifySubTree(Predicate predicate) { + if (predicate == null) { + return null; + } + if (predicate instanceof Conjunction) { + List<Predicate> in = ((PredicateOperator)predicate).getOperands(); + List<Predicate> out = new ArrayList<>(in.size()); + for (Predicate operand : in) { + operand = simplifySubTree(operand); + if (isFalse(operand)) { + return new BooleanPredicate(false); + } else if (!isTrue(operand)) { + out.add(operand); + } + } + if (out.size() == 1) { + return out.get(0); + } else if (out.size() == 0) { + return new BooleanPredicate(true); + } + ((Conjunction)predicate).setOperands(out); + } else if (predicate instanceof Disjunction) { + List<Predicate> in = ((PredicateOperator)predicate).getOperands(); + List<Predicate> out = new ArrayList<>(in.size()); + for (Predicate operand : in) { + operand = simplifySubTree(operand); + if (isTrue(operand)) { + return new BooleanPredicate(true); + } else if (!isFalse(operand)) { + out.add(operand); + } + } + if (out.size() == 1) { + return out.get(0); + } else if (out.size() == 0) { + return new BooleanPredicate(false); + } + ((Disjunction)predicate).setOperands(out); + } else if (predicate instanceof Negation) { + Predicate operand = ((Negation)predicate).getOperand(); + operand = simplifySubTree(operand); + if (isTrue(operand)) { + return new BooleanPredicate(false); + } else if (isFalse(operand)) { + return new BooleanPredicate(true); + } + ((Negation) predicate).setOperand(operand); + } + return predicate; + } + + private boolean isFalse(Predicate predicate) { + if (predicate instanceof BooleanPredicate) { + return !((BooleanPredicate)predicate).getValue(); + } + return false; + } + + private boolean isTrue(Predicate predicate) { + if (predicate instanceof BooleanPredicate) { + return ((BooleanPredicate)predicate).getValue(); + } + return false; + } + + @Override + public Predicate process(Predicate predicate, PredicateOptions options) { + return simplifySubTree(predicate); + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/ComplexNodeTransformer.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/ComplexNodeTransformer.java new file mode 100644 index 00000000000..4ff5d37f842 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/ComplexNodeTransformer.java @@ -0,0 +1,159 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.FeatureRange; +import com.yahoo.document.predicate.Predicate; +import com.yahoo.document.predicate.PredicateOperator; +import com.yahoo.document.predicate.RangeEdgePartition; +import com.yahoo.document.predicate.RangePartition; + +import static java.lang.Math.abs; + +/** + * Partitions all the feature ranges according to the arity and bounds + * set in the PredicateOptions, and updates the ranges with a set of + * partitions and edge partitions. + * This is required to be able to store a range in the PredicateIndex. + * + * @author magnarn + * @author bjorncs + */ +public class ComplexNodeTransformer implements PredicateProcessor { + + public void processPredicate(Predicate predicate, PredicateOptions options) { + if (predicate instanceof PredicateOperator) { + for (Predicate p : ((PredicateOperator) predicate).getOperands()) { + processPredicate(p, options); + } + } else if (predicate instanceof FeatureRange) { + processFeatureRange((FeatureRange) predicate, options); + } + } + + private void processFeatureRange(FeatureRange range, PredicateOptions options) { + range.clearPartitions(); + int arity = options.getArity(); + RangePruner rangePruner = new RangePruner(range, options, arity); + long from = rangePruner.getFrom(); + long to = rangePruner.getTo(); + + if (from < 0) { + if (to < 0) { + // Special case for to==-1. -X-0 means the same as -X-1, but is more efficient. + partitionRange(range, (to == -1 ? 0 : -to), -from, arity, true); + } else { + partitionRange(range, 0, -from, arity, true); + partitionRange(range, 0, to, arity, false); + } + } else { + partitionRange(range, from, to, arity, false); + } + } + + private void partitionRange(FeatureRange range, long from, long to, int arity, boolean isNeg) { + int fromRemainder = abs((int) (from % arity)); // from is only negative when using LLONG_MIN. + // operate on exclusive upper bound. + int toRemainder = ((int) ((to - arity + 1) % arity) + arity) % arity; // avoid overflow of (to + 1) + long fromVal = from - fromRemainder; + long toVal = to - toRemainder; // use inclusive upper bound here to avoid overflow problems. + long fromValDividedByArity = abs(fromVal / arity); + if (fromVal - 1 == toVal) { // (toVal + 1) might cause overflow + addEdgePartition(range, fromVal, fromRemainder, toRemainder - 1, isNeg); + return; + } else { + if (fromRemainder != 0) { + addEdgePartition(range, fromVal, fromRemainder, -1, isNeg); + fromValDividedByArity += 1; + } + if (toRemainder != 0) { + addEdgePartition(range, toVal + 1, -1, toRemainder - 1, isNeg); + } + } + makePartitions(range, fromValDividedByArity, abs((toVal - (arity - 1)) / arity) + 1, arity, arity, isNeg); + } + + private void addEdgePartition(FeatureRange range, long value, int from, int to, boolean isNeg) { + String label; + if (value == 0x8000000000000000L) // special case long_min. + label = range.getKey() + "=-9223372036854775808"; + else + label = range.getKey() + (isNeg ? "=-" : "=") + Long.toString(value); + range.addPartition(new RangeEdgePartition(label, value, from, to)); + } + + private void makePartitions(FeatureRange range, long fromVal, long toVal, long stepSize, int arity, boolean isNeg) { + int fromRemainder = (int) (fromVal % arity); + int toRemainder = (int) (toVal % arity); + long nextFromVal = fromVal - fromRemainder; + long nextToVal = toVal - toRemainder; + if (nextFromVal == nextToVal) { + addPartitions(range, nextFromVal, stepSize, fromRemainder, toRemainder, isNeg); + } else { + if (fromRemainder > 0) { + addPartitions(range, nextFromVal, stepSize, fromRemainder, arity, isNeg); + fromVal = nextFromVal + arity; + } + addPartitions(range, nextToVal, stepSize, 0, toRemainder, isNeg); + makePartitions(range, fromVal / arity, toVal / arity, stepSize * arity, arity, isNeg); + } + } + + private void addPartitions(FeatureRange range, long part, long partSize, int first, int last, boolean isNeg) { + for (int i = first; i < last; ++i) { + range.addPartition(new RangePartition( + range.getKey(), (part + i) * partSize, (part + i + 1) * partSize - 1, isNeg)); + } + } + + @Override + public Predicate process(Predicate predicate, PredicateOptions options) { + processPredicate(predicate, options); + return predicate; + } + + /** + * Prunes ranges that lie partially or completely outside the configured upper/lower bounds. + */ + private static class RangePruner { + private long from; + private long to; + + public RangePruner(FeatureRange range, PredicateOptions options, int arity) { + from = range.getFromInclusive() != null ? range.getFromInclusive() : options.getAdjustedLowerBound(); + to = range.getToInclusive() != null ? range.getToInclusive() : options.getAdjustedUpperBound(); + + if (from > options.getUpperBound()) { // Range completely beyond bounds + long upperRangeStart = Long.MAX_VALUE - (Long.MAX_VALUE % arity) - arity; + if (options.getUpperBound() < upperRangeStart) { + from = upperRangeStart; + to = upperRangeStart + arity - 1; + } else { + to = from; + } + } else if (to < options.getLowerBound()) { // Range completely before bounds + long lowerRangeEnd = Long.MIN_VALUE + (arity - (Long.MIN_VALUE % arity)); + if (options.getLowerBound() > lowerRangeEnd) { + from = lowerRangeEnd - arity + 1; + to = lowerRangeEnd; + } else { + from = to; + } + } else { // Modify if range overlaps bounds + if (from < options.getLowerBound()) { + from = options.getAdjustedLowerBound(); + } + if (to > options.getUpperBound()) { + to = options.getAdjustedUpperBound(); + } + } + } + + public long getFrom() { + return from; + } + + public long getTo() { + return to; + } + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/NotNodeReorderer.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/NotNodeReorderer.java new file mode 100644 index 00000000000..bd7339581f4 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/NotNodeReorderer.java @@ -0,0 +1,67 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.Conjunction; +import com.yahoo.document.predicate.Disjunction; +import com.yahoo.document.predicate.Negation; +import com.yahoo.document.predicate.Predicate; + +import java.util.ArrayList; +import java.util.List; + +/** + * Reorders not nodes to improve the efficiency of the z-star posting list compression. + * It puts negative children first in AND-nodes, and last in OR-nodes. + * + * @author magnarn + * @author bjorncs + */ +public class NotNodeReorderer implements PredicateProcessor { + /** + * @return true if the predicate ends in a negation. + */ + public boolean processSubTree(Predicate predicate) { + if (predicate == null) { + return false; + } + if (predicate instanceof Negation) { + // All negations are for leaf-nodes after AndOrSimplifier has run. + return true; + } else if (predicate instanceof Conjunction) { + List<Predicate> in = ((Conjunction)predicate).getOperands(); + List<Predicate> out = new ArrayList<>(in.size()); + List<Predicate> positiveChildren = new ArrayList<>(in.size()); + for (Predicate operand : in) { + if (processSubTree(operand)) { + out.add(operand); + } else { + positiveChildren.add(operand); + } + } + out.addAll(positiveChildren); + ((Conjunction)predicate).setOperands(out); + return positiveChildren.isEmpty(); + } else if (predicate instanceof Disjunction) { + List<Predicate> in = ((Disjunction)predicate).getOperands(); + List<Predicate> out = new ArrayList<>(in.size()); + List<Predicate> negativeChildren = new ArrayList<>(in.size()); + for (Predicate operand : in) { + if (processSubTree(operand)) { + negativeChildren.add(operand); + } else { + out.add(operand); + } + } + out.addAll(negativeChildren); + ((Disjunction)predicate).setOperands(out); + return !negativeChildren.isEmpty(); + } + return false; + } + + @Override + public Predicate process(Predicate predicate, PredicateOptions options) { + processSubTree(predicate); + return predicate; + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/OrSimplifier.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/OrSimplifier.java new file mode 100644 index 00000000000..768534b0068 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/OrSimplifier.java @@ -0,0 +1,71 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.Conjunction; +import com.yahoo.document.predicate.Disjunction; +import com.yahoo.document.predicate.FeatureSet; +import com.yahoo.document.predicate.Negation; +import com.yahoo.document.predicate.Predicate; + +import java.util.List; +import java.util.Optional; + +import static java.util.stream.Collectors.groupingBy; +import static java.util.stream.Collectors.reducing; +import static java.util.stream.Collectors.toList; + +/** + * Simplifies Disjunction nodes where all children are of type FeatureSet. All FeatureSet that share the same key + * are merged into a single FeatureSet. The Disjunction is removed if all children merges into a single feature set. + * @author bjorncs + */ +public class OrSimplifier implements PredicateProcessor { + + @Override + public Predicate process(Predicate predicate, PredicateOptions options) { + return simplifyTree(predicate); + } + + public Predicate simplifyTree(Predicate predicate) { + if (predicate instanceof Disjunction) { + Disjunction disjunction = (Disjunction) predicate; + List<Predicate> newChildren = + disjunction.getOperands().stream().map(this::simplifyTree).collect(toList()); + return compressFeatureSets(newChildren); + } else if (predicate instanceof Negation) { + Negation negation = (Negation) predicate; + negation.setOperand(simplifyTree(negation.getOperand())); + return negation; + } else if (predicate instanceof Conjunction) { + Conjunction conjunction = (Conjunction) predicate; + List<Predicate> newChildren = + conjunction.getOperands().stream().map(this::simplifyTree).collect(toList()); + conjunction.setOperands(newChildren); + return conjunction; + } else { + return predicate; + } + } + + // Groups and merges the feature sets based on key. + private static Predicate compressFeatureSets(List<Predicate> children) { + List<Predicate> newChildren = children.stream().filter(p -> !(p instanceof FeatureSet)).collect(toList()); + children.stream() + .filter(FeatureSet.class::isInstance) + .map(FeatureSet.class::cast) + .collect(groupingBy(FeatureSet::getKey, + reducing((f1, f2) -> { + f1.addValues(f2.getValues()); + return f1; + }))) + .values() + .stream() + .map(Optional::get) + .forEach(newChildren::add); + if (newChildren.size() == 1) { + return newChildren.get(0); + } else { + return new Disjunction(newChildren); + } + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/PredicateOptions.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/PredicateOptions.java new file mode 100644 index 00000000000..134d52dd3ab --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/PredicateOptions.java @@ -0,0 +1,87 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import java.util.OptionalLong; + +/** + * This class contains the configured options for predicate indexes. + * The adjusted bounds are extended to the nearest power of the arity (-1) + * and are used to generate more efficient indexes. + * + * @author magnarn + * @author bjorncs + */ +public class PredicateOptions { + public static final long DEFAULT_LOWER_BOUND = 0x8000000000000000L; + public static final long DEFAULT_UPPER_BOUND = 0x7fffffffffffffffL; + + private final int arity; + private final long lowerBound; + private final long upperBound; + private OptionalLong adjustedLowerBound; + private OptionalLong adjustedUpperBound; + + public PredicateOptions(int arity, Long lowerBound, Long upperBound) { + this.arity = arity; + this.lowerBound = lowerBound == null? DEFAULT_LOWER_BOUND : lowerBound; + this.upperBound = upperBound == null? DEFAULT_UPPER_BOUND : upperBound; + this.adjustedLowerBound = OptionalLong.empty(); + this.adjustedUpperBound = OptionalLong.empty(); + } + + public PredicateOptions(int arity) { + this(arity, DEFAULT_LOWER_BOUND, DEFAULT_UPPER_BOUND); + } + + public int getArity() { + return arity; + } + + public long getLowerBound() { + return lowerBound; + } + + public long getUpperBound() { + return upperBound; + } + + public long getAdjustedLowerBound() { + if (!adjustedLowerBound.isPresent()) { + if (lowerBound == DEFAULT_LOWER_BOUND) { + adjustedLowerBound = OptionalLong.of(lowerBound); + } else if (lowerBound > 0) { + adjustedLowerBound = OptionalLong.of(0L); + } else { + adjustedLowerBound = OptionalLong.of(-adjustBound(arity, -lowerBound)); + } + } + return adjustedLowerBound.getAsLong(); + } + + public long getAdjustedUpperBound() { + if (!adjustedUpperBound.isPresent()) { + if (upperBound == DEFAULT_UPPER_BOUND) { + adjustedUpperBound = OptionalLong.of(DEFAULT_UPPER_BOUND); + } else if (upperBound < 0) { + adjustedUpperBound = OptionalLong.of(-1L); // 0 belongs to the positive range. + } else { + adjustedUpperBound = OptionalLong.of(adjustBound(arity, upperBound)); + } + } + return adjustedUpperBound.getAsLong(); + } + + private static long adjustBound(int arity, long bound) { + long adjusted = arity; + long value = bound; + long max = Long.MAX_VALUE / arity; + while ((value/=arity) > 0) { + if (adjusted > max) { + return bound; + } + adjusted *= arity; + } + return adjusted - 1; + } +} + diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/PredicateProcessor.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/PredicateProcessor.java new file mode 100644 index 00000000000..f6559bb4044 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/PredicateProcessor.java @@ -0,0 +1,24 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.Predicate; + +/** + * A predicate processor takes a predicate, processes it and returns the result. + * Predicate optimisers typically implement this interface. + * Note that the interface does not give any guarantees if the processor will + * modify the predicate in-place or return a new instance. + * + * @author bjorncs + */ +@FunctionalInterface +public interface PredicateProcessor { + + /** + * Processes a predicate. + * + * @return the processed predicate. + */ + Predicate process(Predicate predicate, PredicateOptions options); + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/package-info.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/package-info.java new file mode 100644 index 00000000000..77d8143d137 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/package-info.java @@ -0,0 +1,4 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +@com.yahoo.osgi.annotation.ExportPackage + +package com.yahoo.search.predicate.optimization; diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/package-info.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/package-info.java new file mode 100644 index 00000000000..8f2d929efcd --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/package-info.java @@ -0,0 +1,4 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +@com.yahoo.osgi.annotation.ExportPackage + +package com.yahoo.search.predicate; |