Publish

53 files changed, 4847 insertions, 0 deletions

diff --git a/predicate-search-core/OWNERS b/predicate-search-core/OWNERS
new file mode 100644
index 00000000000..569bf1cc3a1
--- /dev/null
+++ b/predicate-search-core/OWNERS
@@ -0,0 +1 @@
+bjorncs
diff --git a/predicate-search-core/pom.xml b/predicate-search-core/pom.xml
new file mode 100644
index 00000000000..ad5d6002b66
--- /dev/null
+++ b/predicate-search-core/pom.xml
@@ -0,0 +1,57 @@
+<?xml version="1.0"?>
+<!-- Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -->
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+    <modelVersion>4.0.0</modelVersion>
+    <parent>
+        <groupId>com.yahoo.vespa</groupId>
+        <artifactId>parent</artifactId>
+        <version>6-SNAPSHOT</version>
+        <relativePath>../parent/pom.xml</relativePath>
+    </parent>
+    <artifactId>predicate-search-core</artifactId>
+    <version>6-SNAPSHOT</version>
+    <packaging>jar</packaging>
+    <name>${project.artifactId}</name>
+    <dependencies>
+        <dependency>
+            <groupId>junit</groupId>
+            <artifactId>junit</artifactId>
+            <scope>test</scope>
+        </dependency>
+        <dependency>
+            <groupId>org.antlr</groupId>
+            <artifactId>antlr-runtime</artifactId>
+        </dependency>
+        <dependency>
+            <groupId>com.yahoo.vespa</groupId>
+            <artifactId>vespajlib</artifactId>
+            <version>${project.version}</version>
+        </dependency>
+        <dependency>
+            <groupId>com.yahoo.vespa</groupId>
+            <artifactId>annotations</artifactId>
+            <version>${project.version}</version>
+        </dependency>
+        <dependency>
+            <groupId>com.fasterxml.jackson.core</groupId>
+            <artifactId>jackson-core</artifactId>
+            <scope>provided</scope>
+        </dependency>
+    </dependencies>
+    <build>
+        <plugins>
+            <plugin>
+                <groupId>org.antlr</groupId>
+                <artifactId>antlr3-maven-plugin</artifactId>
+                <executions>
+                    <execution>
+                        <goals>
+                            <goal>antlr</goal>
+                        </goals>
+                    </execution>
+                </executions>
+            </plugin>
+        </plugins>
+    </build>
+</project>
diff --git a/predicate-search-core/src/main/antlr3/com/yahoo/document/predicate/parser/Predicate.g b/predicate-search-core/src/main/antlr3/com/yahoo/document/predicate/parser/Predicate.g
new file mode 100644
index 00000000000..963d87c3218
--- /dev/null
+++ b/predicate-search-core/src/main/antlr3/com/yahoo/document/predicate/parser/Predicate.g
@@ -0,0 +1,118 @@
+grammar Predicate;
+
+@header {
+package com.yahoo.document.predicate.parser;
+
+import com.yahoo.document.predicate.Conjunction;
+import com.yahoo.document.predicate.Disjunction;
+import com.yahoo.document.predicate.FeatureRange;
+import com.yahoo.document.predicate.FeatureSet;
+import com.yahoo.document.predicate.Negation;
+import com.yahoo.document.predicate.Predicate;
+import com.yahoo.document.predicate.Predicates;
+}
+
+@lexer::header {
+package com.yahoo.document.predicate.parser;
+
+import com.yahoo.document.predicate.Predicate;
+}
+
+@members {
+    @Override
+    public void emitErrorMessage(String message) {
+        throw new IllegalArgumentException(message);
+    }
+}
+
+@lexer::members {
+    @Override
+    public void emitErrorMessage(String message) {
+        throw new IllegalArgumentException(message);
+    }
+}
+
+predicate returns [Predicate n]
+    : d=disjunction EOF { n = d; }
+    ;
+
+disjunction returns [Predicate n]
+    : c=conjunction { n = c; }
+      ( OR c2=conjunction { n = new Disjunction(n, c2); }
+        ( OR c3=conjunction { ((Disjunction)n).addOperand(c3); } )* )?
+    ;
+
+conjunction returns [Predicate n]
+    : u=unary_node { n = u; }
+      ( AND u2=unary_node { n = new Conjunction(n, u2); }
+        ( AND u3=unary_node { ((Conjunction)n).addOperand(u3); } )* )?
+    ;
+
+unary_node returns [Predicate n]
+    : l=leaf { n = l; }
+    | ( not=NOT )? '(' d=disjunction ')' { n = d; if (not != null) { n = new Negation(n); } }
+    ;
+
+leaf returns [Predicate n]
+    : k=value ( not=NOT )? IN
+        ( mv=multivalue[k] { n = mv; }
+        | r=range[k] { n = r; }
+        ) { if (not != null) { n = new Negation(n); } }
+    | TRUE { n = Predicates.value(true); }
+    | FALSE { n = Predicates.value(false); }
+    ;
+
+multivalue[String key] returns [FeatureSet n]
+    : '[' v1=value { n = new FeatureSet(key, v1); }
+          ( ',' v2=value { n.addValue(v2); })* ']'
+    ;
+
+value returns [String s]
+    : VALUE { s = $VALUE.text; }
+    | STRING { s = $STRING.text; }
+    | INTEGER { s = $INTEGER.text; }
+    | k=keyword { s = k; }
+    ;
+
+range[String key] returns [FeatureRange r]
+    : '[' { r = new FeatureRange(key); }
+          ( i1=INTEGER { r.setFromInclusive(Long.parseLong(i1.getText())); } )?
+          '..'
+          ( i2=INTEGER { r.setToInclusive(Long.parseLong(i2.getText())); } )?
+          ( '(' partition (',' partition)* ')' )?
+      ']'
+    ;
+
+partition
+    : value ('='|'=-') (INTEGER INTEGER /* second integer becomes negative */ | INTEGER '+[' INTEGER? '..' INTEGER? ']')
+    ;
+
+keyword returns [String s]
+    : OR  { s = $OR.text; }
+    | AND { s = $AND.text; }
+    | NOT { s = $NOT.text; }
+    | IN  { s = $IN.text; }
+    | TRUE { s = $TRUE.text; }
+    | FALSE { s = $FALSE.text; }
+    ;
+
+INTEGER : ( '-' | '+' )? ('1'..'9' ( '0'..'9' )* | '0') ;
+
+OR  : 'OR' | 'or' ;
+AND : 'AND' | 'and' ;
+NOT : 'NOT' | 'not' ;
+IN  : 'IN' | 'in' ;
+TRUE : 'TRUE' | 'true' ;
+FALSE : 'FALSE' | 'false' ;
+
+VALUE : ( 'a'..'z' | 'A'..'Z' | '0'..'9' | '_' )+ ;
+
+STRING
+    : ( '\'' ( ~('\'') | '\\\'' )* '\''
+      | '\"' ( ~('\"') | '\\\"' )* '\"' )
+      { setText(Predicate.asciiDecode(getText().substring(1, getText().length() - 1))); }
+    ;
+
+WS  : (' ' | '\t')+
+      {$channel = HIDDEN;}
+    ;
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/BinaryFormat.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/BinaryFormat.java
new file mode 100644
index 00000000000..89dcbc59d99
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/BinaryFormat.java
@@ -0,0 +1,167 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import com.yahoo.slime.Cursor;
+import com.yahoo.slime.Inspector;
+import com.yahoo.slime.Slime;
+
+import java.util.Objects;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class BinaryFormat {
+
+    final static String NODE_TYPE = "type";
+    final static String KEY = "key";
+    final static String SET = "feature_set";
+    final static String RANGE_MIN = "range_min";
+    final static String RANGE_MAX = "range_max";
+    final static String CHILDREN = "children";
+    final static String PARTITIONS = "partitions";
+    final static String EDGE_PARTITIONS = "edge_partitions";
+    final static String HASHED_PARTITIONS = "hashed_partitions";
+    final static String HASHED_EDGE_PARTITIONS = "hashed_edge_partitions";
+    final static String HASH = "hash";
+    final static String PAYLOAD = "payload";
+    final static String LABEL = "label";
+    final static String VALUE = "value";
+    final static String LOWER_BOUND = "lower_bound";
+    final static String UPPER_BOUND = "upper_bound";
+
+    final static int TYPE_CONJUNCTION = 1;
+    final static int TYPE_DISJUNCTION = 2;
+    final static int TYPE_NEGATION = 3;
+    final static int TYPE_FEATURE_SET = 4;
+    final static int TYPE_FEATURE_RANGE = 5;
+    final static int TYPE_TRUE = 6;
+    final static int TYPE_FALSE = 7;
+
+    public static byte[] encode(Predicate predicate) {
+        Objects.requireNonNull(predicate, "predicate");
+        Slime slime = new Slime();
+        encode(predicate, slime.setObject());
+        return com.yahoo.slime.BinaryFormat.encode(slime);
+    }
+
+    public static Predicate decode(byte[] buf) {
+        Objects.requireNonNull(buf, "buf");
+        Slime slime = com.yahoo.slime.BinaryFormat.decode(buf);
+        return decode(slime.get());
+    }
+
+    private static Predicate decode(Inspector in) {
+        switch ((int)in.field(NODE_TYPE).asLong()) {
+        case TYPE_CONJUNCTION:
+            Conjunction conjunction = new Conjunction();
+            in = in.field(CHILDREN);
+            for (int i = 0, len = in.children(); i < len; ++i) {
+                conjunction.addOperand(decode(in.entry(i)));
+            }
+            return conjunction;
+
+        case TYPE_DISJUNCTION:
+            Disjunction disjunction = new Disjunction();
+            in = in.field(CHILDREN);
+            for (int i = 0, len = in.children(); i < len; ++i) {
+                disjunction.addOperand(decode(in.entry(i)));
+            }
+            return disjunction;
+
+        case TYPE_NEGATION:
+            return new Negation(decode(in.field(CHILDREN).entry(0)));
+
+        case TYPE_FEATURE_RANGE:
+            FeatureRange featureRange = new FeatureRange(in.field(KEY).asString());
+            if (in.field(RANGE_MIN).valid()) {
+                featureRange.setFromInclusive(in.field(RANGE_MIN).asLong());
+            }
+            if (in.field(RANGE_MAX).valid()) {
+                featureRange.setToInclusive(in.field(RANGE_MAX).asLong());
+            }
+            Inspector p_in = in.field(PARTITIONS);
+            for (int i = 0, len = p_in.children(); i < len; ++i) {
+                featureRange.addPartition(new RangePartition(p_in.entry(i).asString()));
+            }
+            p_in = in.field(EDGE_PARTITIONS);
+            for (int i = 0, len = p_in.children(); i < len; ++i) {
+                Inspector obj = p_in.entry(i);
+                featureRange.addPartition(new RangeEdgePartition(
+                        obj.field(LABEL).asString(), obj.field(VALUE).asLong(),
+                        (int)obj.field(LOWER_BOUND).asLong(), (int)obj.field(UPPER_BOUND).asLong()));
+            }
+            return featureRange;
+
+        case TYPE_FEATURE_SET:
+            FeatureSet featureSet = new FeatureSet(in.field(KEY).asString());
+            in = in.field(SET);
+            for (int i = 0, len = in.children(); i < len; ++i) {
+                featureSet.addValue(in.entry(i).asString());
+            }
+            return featureSet;
+
+        case TYPE_TRUE:
+            return new BooleanPredicate(true);
+
+        case TYPE_FALSE:
+            return new BooleanPredicate(false);
+
+            default:
+            throw new UnsupportedOperationException(String.valueOf(in.field(NODE_TYPE).asLong()));
+        }
+    }
+
+    private static void encode(Predicate predicate, Cursor out) {
+        if (predicate instanceof Conjunction) {
+            out.setLong(NODE_TYPE, TYPE_CONJUNCTION);
+            out = out.setArray(CHILDREN);
+            for (Predicate operand : ((Conjunction)predicate).getOperands()) {
+                encode(operand, out.addObject());
+            }
+        } else if (predicate instanceof Disjunction) {
+            out.setLong(NODE_TYPE, TYPE_DISJUNCTION);
+            out = out.setArray(CHILDREN);
+            for (Predicate operand : ((Disjunction)predicate).getOperands()) {
+                encode(operand, out.addObject());
+            }
+        } else if (predicate instanceof FeatureRange) {
+            FeatureRange range = (FeatureRange) predicate;
+            out.setLong(NODE_TYPE, TYPE_FEATURE_RANGE);
+            out.setString(KEY, range.getKey());
+            Long from = range.getFromInclusive();
+            if (from != null) {
+                out.setLong(RANGE_MIN, from);
+            }
+            Long to = range.getToInclusive();
+            if (to != null) {
+                out.setLong(RANGE_MAX, to);
+            }
+            Cursor p_out = out.setArray(HASHED_PARTITIONS);
+            for (RangePartition p : range.getPartitions()) {
+                p_out.addLong(PredicateHash.hash64(p.getLabel()));
+            }
+            p_out = out.setArray(HASHED_EDGE_PARTITIONS);
+            for (RangeEdgePartition p : range.getEdgePartitions()) {
+                Cursor obj = p_out.addObject();
+                obj.setLong(HASH, PredicateHash.hash64(p.getLabel()));
+                obj.setLong(VALUE, p.getValue());
+                obj.setLong(PAYLOAD, p.encodeBounds());
+            }
+        } else if (predicate instanceof FeatureSet) {
+            out.setLong(NODE_TYPE, TYPE_FEATURE_SET);
+            out.setString(KEY, ((FeatureSet)predicate).getKey());
+            out = out.setArray(SET);
+            for (String value : ((FeatureSet)predicate).getValues()) {
+                out.addString(value);
+            }
+        } else if (predicate instanceof Negation) {
+            out.setLong(NODE_TYPE, TYPE_NEGATION);
+            out = out.setArray(CHILDREN);
+            encode(((Negation)predicate).getOperand(), out.addObject());
+        } else if (predicate instanceof BooleanPredicate) {
+            out.setLong(NODE_TYPE, ((BooleanPredicate)predicate).getValue() ? TYPE_TRUE : TYPE_FALSE);
+        } else {
+            throw new UnsupportedOperationException(predicate.getClass().getName());
+        }
+    }
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/BooleanPredicate.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/BooleanPredicate.java
new file mode 100644
index 00000000000..507d48bf241
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/BooleanPredicate.java
@@ -0,0 +1,54 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class BooleanPredicate extends PredicateValue {
+
+    private boolean value;
+
+    public BooleanPredicate(boolean value) {
+        this.value = value;
+    }
+
+    public boolean getValue() {
+        return value;
+    }
+
+    public BooleanPredicate setValue(boolean value) {
+        this.value = value;
+        return this;
+    }
+
+    @Override
+    public BooleanPredicate clone() throws CloneNotSupportedException {
+        return (BooleanPredicate)super.clone();
+    }
+
+    @Override
+    public int hashCode() {
+        return value ? Boolean.TRUE.hashCode() : Boolean.FALSE.hashCode();
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj == this) {
+            return true;
+        }
+        if (!(obj instanceof BooleanPredicate)) {
+            return false;
+        }
+        BooleanPredicate rhs = (BooleanPredicate)obj;
+        if (value != rhs.value) {
+            return false;
+        }
+        return true;
+    }
+
+    @Override
+    protected void appendTo(StringBuilder out) {
+        out.append(value ? "true" : "false");
+    }
+
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Conjunction.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Conjunction.java
new file mode 100644
index 00000000000..d917e374b69
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Conjunction.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.document.predicate;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class Conjunction extends PredicateOperator {
+
+    private List<Predicate> operands;
+
+    public Conjunction(Predicate... operands) {
+        this(Arrays.asList(operands));
+    }
+
+    public Conjunction(List<? extends Predicate> operands) {
+        this.operands = new ArrayList<>(operands);
+    }
+
+    public Conjunction addOperand(Predicate operand) {
+        operands.add(operand);
+        return this;
+    }
+
+    public Conjunction addOperands(Collection<? extends Predicate> operands) {
+        this.operands.addAll(operands);
+        return this;
+    }
+
+    public Conjunction setOperands(Collection<? extends Predicate> operands) {
+        this.operands.clear();
+        this.operands.addAll(operands);
+        return this;
+    }
+
+    @Override
+    public List<Predicate> getOperands() {
+        return operands;
+    }
+
+    @Override
+    public Conjunction clone() throws CloneNotSupportedException {
+        Conjunction obj = (Conjunction)super.clone();
+        obj.operands = new ArrayList<>(operands.size());
+        for (Predicate operand : operands) {
+            obj.operands.add(operand.clone());
+        }
+        return obj;
+    }
+
+    @Override
+    public int hashCode() {
+        return operands.hashCode();
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj == this) {
+            return true;
+        }
+        if (!(obj instanceof Conjunction)) {
+            return false;
+        }
+        Conjunction rhs = (Conjunction)obj;
+        if (!operands.equals(rhs.operands)) {
+            return false;
+        }
+        return true;
+    }
+
+    @Override
+    protected void appendTo(StringBuilder out) {
+        for (Iterator<Predicate> it = operands.iterator(); it.hasNext(); ) {
+            Predicate operand = it.next();
+            if (operand instanceof Disjunction || operand instanceof FeatureConjunction) {
+                out.append('(');
+                operand.appendTo(out);
+                out.append(')');
+            } else {
+                operand.appendTo(out);
+            }
+            if (it.hasNext()) {
+                out.append(" and ");
+            }
+        }
+    }
+
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Disjunction.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Disjunction.java
new file mode 100644
index 00000000000..c5fa6ba1f70
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Disjunction.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.document.predicate;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class Disjunction extends PredicateOperator {
+
+    private List<Predicate> operands;
+
+    public Disjunction(Predicate... operands) {
+        this(Arrays.asList(operands));
+    }
+
+    public Disjunction(List<? extends Predicate> operands) {
+        this.operands = new ArrayList<>(operands);
+    }
+
+    public Disjunction addOperand(Predicate operand) {
+        operands.add(operand);
+        return this;
+    }
+
+    public Disjunction addOperands(Collection<? extends Predicate> operands) {
+        this.operands.addAll(operands);
+        return this;
+    }
+
+    public Disjunction setOperands(Collection<? extends Predicate> operands) {
+        this.operands.clear();
+        this.operands.addAll(operands);
+        return this;
+    }
+
+    @Override
+    public List<Predicate> getOperands() {
+        return operands;
+    }
+
+    @Override
+    public Disjunction clone() throws CloneNotSupportedException {
+        Disjunction obj = (Disjunction)super.clone();
+        obj.operands = new ArrayList<>(operands.size());
+        for (Predicate operand : operands) {
+            obj.operands.add(operand.clone());
+        }
+        return obj;
+    }
+
+    @Override
+    public int hashCode() {
+        return operands.hashCode();
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj == this) {
+            return true;
+        }
+        if (!(obj instanceof Disjunction)) {
+            return false;
+        }
+        Disjunction rhs = (Disjunction)obj;
+        if (!operands.equals(rhs.operands)) {
+            return false;
+        }
+        return true;
+    }
+
+    @Override
+    protected void appendTo(StringBuilder out) {
+        for (Iterator<Predicate> it = operands.iterator(); it.hasNext(); ) {
+            Predicate operand = it.next();
+            if (operand instanceof Conjunction) {
+                out.append('(');
+                operand.appendTo(out);
+                out.append(')');
+            } else {
+                operand.appendTo(out);
+            }
+            if (it.hasNext()) {
+                out.append(" or ");
+            }
+        }
+    }
+
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureConjunction.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureConjunction.java
new file mode 100644
index 00000000000..ba6bb32e05f
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureConjunction.java
@@ -0,0 +1,104 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+/**
+ * A FeatureConjunction is a special type of Conjunction where
+ * all children are either a FeatureSet or a Negation (with an underlying FeatureSet).
+ * The underlying FeatureSets may only have one value.
+ *
+ * @author bjorncs
+ */
+public class FeatureConjunction extends PredicateOperator {
+    private final List<Predicate> operands;
+
+    public FeatureConjunction(List<Predicate> operands) {
+        validateOperands(operands);
+        this.operands = new ArrayList<>(operands);
+    }
+
+    private static void validateOperands(List<Predicate> operands) {
+        if (operands.size() <= 1) {
+            throw new IllegalArgumentException("Number of operands must 2 or more, was: " + operands.size());
+        }
+        if (!operands.stream()
+                .allMatch(FeatureConjunction::isValidFeatureConjunctionOperand)) {
+            throw new IllegalArgumentException(
+                    "A FeatureConjunction may only contain instances of Negation and FeatureSet, " +
+                            "and a FeatureSet may only have one value.");
+        }
+
+        long uniqueKeys = operands.stream().map(FeatureConjunction::getFeatureSetKey).distinct().count();
+        if (operands.size() > uniqueKeys) {
+            throw new IllegalArgumentException("Each FeatureSet key must have a unique key.");
+        }
+    }
+
+    private static String getFeatureSetKey(Predicate predicate) {
+        if (predicate instanceof FeatureSet) {
+            return ((FeatureSet) predicate).getKey();
+        } else {
+            Negation negation = (Negation) predicate;
+            return ((FeatureSet) negation.getOperand()).getKey();
+        }
+    }
+
+    public static boolean isValidFeatureConjunctionOperand(Predicate operand) {
+        return operand instanceof Negation
+                    && ((Negation) operand).getOperand() instanceof FeatureSet
+                    && isValidFeatureConjunctionOperand(((Negation) operand).getOperand())
+                || operand instanceof FeatureSet && ((FeatureSet) operand).getValues().size() == 1;
+    }
+
+    @Override
+    public List<Predicate> getOperands() {
+        return operands;
+    }
+
+    @Override
+    protected void appendTo(StringBuilder out) {
+        for (Iterator<Predicate> it = operands.iterator(); it.hasNext(); ) {
+            Predicate operand = it.next();
+            if (operand instanceof Disjunction) {
+                out.append('(');
+                operand.appendTo(out);
+                out.append(')');
+            } else {
+                operand.appendTo(out);
+            }
+            if (it.hasNext()) {
+                out.append(" conj ");
+            }
+        }
+    }
+
+    @Override
+    public FeatureConjunction clone() throws CloneNotSupportedException {
+        return new FeatureConjunction(operands);
+    }
+
+    @Override
+    public int hashCode() {
+        return operands.hashCode();
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj == this) {
+            return true;
+        }
+        if (!(obj instanceof FeatureConjunction)) {
+            return false;
+        }
+        FeatureConjunction rhs = (FeatureConjunction)obj;
+        if (!operands.equals(rhs.operands)) {
+            return false;
+        }
+        return true;
+    }
+
+
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureRange.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureRange.java
new file mode 100644
index 00000000000..2ca09ee98f0
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureRange.java
@@ -0,0 +1,190 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class FeatureRange extends PredicateValue {
+
+    private String key;
+    private Long from;
+    private Long to;
+    private List<RangePartition> partitions;
+    private List<RangeEdgePartition> edgePartitions;
+
+    public FeatureRange(String key) {
+        this(key, null, null);
+    }
+
+    public FeatureRange(String key, Long fromInclusive, Long toInclusive) {
+        setKey(key);
+        setFromInclusive(fromInclusive);
+        setToInclusive(toInclusive);
+        partitions = new ArrayList<>();
+        edgePartitions = new ArrayList<>();
+    }
+
+    public FeatureRange setKey(String key) {
+        Objects.requireNonNull(key, "key");
+        this.key = key;
+        return this;
+    }
+
+    public String getKey() {
+        return key;
+    }
+
+    public FeatureRange setFromInclusive(Long from) {
+        if (from != null && to != null && from > to) {
+            throw new IllegalArgumentException("Expected 'from' less than or equal to " + to + ", got " + from + ".");
+        }
+        this.from = from;
+        return this;
+    }
+
+    public Long getFromInclusive() {
+        return from;
+    }
+
+    public FeatureRange setToInclusive(Long to) {
+        if (from != null && to != null && from > to) {
+            throw new IllegalArgumentException("Expected 'to' greater than or equal to " + from + ", got " + to + ".");
+        }
+        this.to = to;
+        return this;
+    }
+
+    public Long getToInclusive() {
+        return to;
+    }
+
+    public void addPartition(RangePartition p) {
+        if (p instanceof RangeEdgePartition) {
+            edgePartitions.add((RangeEdgePartition)p);
+        } else {
+            partitions.add(p);
+        }
+    }
+
+    public List<RangeEdgePartition> getEdgePartitions() {
+        return edgePartitions;
+    }
+
+    public List<RangePartition> getPartitions() {
+        return partitions;
+    }
+
+    public void clearPartitions() {
+        partitions.clear();
+        edgePartitions.clear();
+    }
+
+    @Override
+    public FeatureRange clone() throws CloneNotSupportedException {
+        return (FeatureRange)super.clone();
+    }
+
+    @Override
+    public int hashCode() {
+        return ((key.hashCode() + (from != null ? from.hashCode() : 0)) * 31 + (to != null ? to.hashCode() : 0)) * 31;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj == this) {
+            return true;
+        }
+        if (!(obj instanceof FeatureRange)) {
+            return false;
+        }
+        FeatureRange rhs = (FeatureRange)obj;
+        if (!key.equals(rhs.key)) {
+            return false;
+        }
+        if (!Objects.equals(from, rhs.from)) {
+            return false;
+        }
+        if (!Objects.equals(to, rhs.to)) {
+            return false;
+        }
+        return partitions.equals(rhs.partitions) && edgePartitions.equals(rhs.edgePartitions);
+    }
+
+    @Override
+    protected void appendTo(StringBuilder out) {
+        appendQuotedTo(key, out);
+        out.append(" in [");
+        if (from != null) {
+            out.append(from);
+        }
+        out.append("..");
+        if (to != null) {
+            out.append(to);
+        }
+        if (!partitions.isEmpty() || !edgePartitions.isEmpty()) {
+            out.append(" (");
+            for (RangeEdgePartition p : edgePartitions) {
+                p.appendTo(out);
+                out.append(',');
+            }
+            for (RangePartition p : partitions) {
+                p.appendTo(out);
+                out.append(',');
+            }
+            out.deleteCharAt(out.length() - 1);  // Remove extra ','
+            out.append(")");
+        }
+        out.append("]");
+    }
+
+    public static FeatureRange buildFromMixedIn(String key, List<String> partitions, int arity) {
+        Long fromInclusive = null;
+        Long toInclusive = null;
+        long from = 0;
+        long to = 0;
+        for (String p : partitions) {
+            String[] parts = p.split(",");
+            if (parts.length == 1) {
+                String[] subparts = parts[0].split("=|-");
+                int offset = subparts.length == 3? 0 : 1;
+                if (subparts.length < 3 || subparts.length > 4) {
+                    throw new IllegalArgumentException("MIXED_IN range partition must be on the form label=val-val");
+                }
+                from = Long.parseLong(subparts[offset + 1]);
+                to = Long.parseLong(subparts[offset + 2]);
+                if (parts[0].contains("=-")) {
+                    long tmp = from;
+                    from = -to;
+                    to = -tmp;
+                }
+            } else {
+                if (parts.length != 3) {
+                    throw new IllegalArgumentException("MIXED_IN range edge partition must be on the form label=val,val,payload");
+                }
+                long value = Long.parseLong(parts[1]);
+                long payload = Long.parseLong(parts[2]);
+                if ((payload & 0xc0000000) == 0x80000000L) {
+                    from = value + (payload & 0xffff);
+                    to = value + arity - 1;
+                } else if ((payload & 0xc0000000) == 0x40000000L) {
+                    from = value;
+                    to = value + (payload & 0xffff);
+                } else {
+                    from = value + (payload >> 16);
+                    to = value + (payload & 0xffff);
+                }
+            }
+            if (fromInclusive == null || fromInclusive > from) {
+                fromInclusive = from;
+            }
+            if (toInclusive == null || toInclusive > to) {
+                toInclusive = to;
+            }
+        }
+        return new FeatureRange(key, fromInclusive, toInclusive);
+    }
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureSet.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureSet.java
new file mode 100644
index 00000000000..be560514995
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureSet.java
@@ -0,0 +1,119 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Objects;
+import java.util.Set;
+import java.util.TreeSet;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class FeatureSet extends PredicateValue {
+
+    private Set<String> values;
+    private String key;
+
+    public FeatureSet(String key, String... values) {
+        this(key, Arrays.asList(values));
+    }
+
+    public FeatureSet(String key, Collection<String> values) {
+        Objects.requireNonNull(key, "key");
+        if (values == null) {
+            throw new NullPointerException("values");
+        }
+        this.key = key;
+        this.values = new TreeSet<>(values);
+    }
+
+    public FeatureSet setKey(String key) {
+        Objects.requireNonNull(key, "key");
+        this.key = key;
+        return this;
+    }
+
+    public String getKey() {
+        return key;
+    }
+
+    public FeatureSet addValue(String value) {
+        Objects.requireNonNull(value, "value");
+        values.add(value);
+        return this;
+    }
+
+    public FeatureSet addValues(Collection<String> values) {
+        if (values == null) {
+            throw new NullPointerException("values");
+        }
+        this.values.addAll(values);
+        return this;
+    }
+
+    public FeatureSet setValues(Collection<String> values) {
+        if (values == null) {
+            throw new NullPointerException("values");
+        }
+        this.values.clear();
+        this.values.addAll(values);
+        return this;
+    }
+
+    public Set<String> getValues() {
+        return values;
+    }
+
+    @Override
+    public FeatureSet clone() throws CloneNotSupportedException {
+        FeatureSet obj = (FeatureSet)super.clone();
+        obj.values = new TreeSet<>(values);
+        return obj;
+    }
+
+    @Override
+    public int hashCode() {
+        return (key.hashCode() + values.hashCode()) * 31;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj == this) {
+            return true;
+        }
+        if (!(obj instanceof FeatureSet)) {
+            return false;
+        }
+        FeatureSet rhs = (FeatureSet)obj;
+        if (!key.equals(rhs.key)) {
+            return false;
+        }
+        if (!values.equals(rhs.values)) {
+            return false;
+        }
+        return true;
+    }
+
+    @Override
+    protected void appendTo(StringBuilder out) {
+        appendInAsTo("in", out);
+    }
+
+    protected void appendNegatedTo(StringBuilder out) {
+        appendInAsTo("not in", out);
+    }
+
+    private void appendInAsTo(String in, StringBuilder out) {
+        appendQuotedTo(key, out);
+        out.append(' ').append(in).append(" [");
+        for (Iterator<String> it = values.iterator(); it.hasNext(); ) {
+            appendQuotedTo(it.next(), out);
+            if (it.hasNext()) {
+                out.append(", ");
+            }
+        }
+        out.append("]");
+    }
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Negation.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Negation.java
new file mode 100644
index 00000000000..c5a4cb802ee
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Negation.java
@@ -0,0 +1,72 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import java.util.List;
+import java.util.Objects;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class Negation extends PredicateOperator {
+
+    private Predicate operand;
+
+    public Negation(Predicate operand) {
+        Objects.requireNonNull(operand, "operand");
+        this.operand = operand;
+    }
+
+    public Negation setOperand(Predicate operand) {
+        Objects.requireNonNull(operand, "operand");
+        this.operand = operand;
+        return this;
+    }
+
+    public Predicate getOperand() {
+        return operand;
+    }
+
+    @Override
+    public List<Predicate> getOperands() {
+        return java.util.Arrays.asList(operand);
+    }
+
+    @Override
+    public Negation clone() throws CloneNotSupportedException {
+        Negation obj = (Negation)super.clone();
+        obj.operand = operand.clone();
+        return obj;
+    }
+
+    @Override
+    public int hashCode() {
+        return operand.hashCode();
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj == this) {
+            return true;
+        }
+        if (!(obj instanceof Negation)) {
+            return false;
+        }
+        Negation rhs = (Negation)obj;
+        if (!operand.equals(rhs.operand)) {
+            return false;
+        }
+        return true;
+    }
+
+    @Override
+    protected void appendTo(StringBuilder out) {
+        if (operand instanceof FeatureSet) {
+            ((FeatureSet)operand).appendNegatedTo(out);
+        } else {
+            out.append("not (");
+            operand.appendTo(out);
+            out.append(')');
+        }
+    }
+
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicate.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicate.java
new file mode 100644
index 00000000000..2446d3e3524
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicate.java
@@ -0,0 +1,79 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import com.yahoo.document.predicate.parser.PredicateLexer;
+import com.yahoo.document.predicate.parser.PredicateParser;
+import com.yahoo.text.Ascii;
+import org.antlr.runtime.ANTLRStringStream;
+import org.antlr.runtime.CommonTokenStream;
+import org.antlr.runtime.RecognitionException;
+
+import java.nio.charset.StandardCharsets;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public abstract class Predicate implements Cloneable {
+
+    private final static char QUOTE_CHAR = '\'';
+    private final static Ascii.Encoder ASCII_ENCODER = Ascii.newEncoder(StandardCharsets.UTF_8, QUOTE_CHAR);
+    private final static Ascii.Decoder ASCII_DECODER = Ascii.newDecoder(StandardCharsets.UTF_8);
+
+    @Override
+    public Predicate clone() throws CloneNotSupportedException {
+        return (Predicate)super.clone();
+    }
+
+    @Override
+    public final String toString() {
+        StringBuilder out = new StringBuilder();
+        appendTo(out);
+        return out.toString();
+    }
+
+    protected abstract void appendTo(StringBuilder out);
+
+    protected static void appendQuotedTo(String str, StringBuilder out) {
+        String encoded = asciiEncode(str);
+        if (requiresQuote(encoded)) {
+            out.append(QUOTE_CHAR).append(encoded).append(QUOTE_CHAR);
+        } else {
+            out.append(str);
+        }
+    }
+
+    private static boolean requiresQuote(String str) {
+        for (int i = 0, len = str.length(); i < len; i = str.offsetByCodePoints(i, 1)) {
+            int c = str.codePointAt(i);
+            if (c == Ascii.ESCAPE_CHAR || !Character.isLetterOrDigit(c)) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    public static String asciiEncode(String str) {
+        return ASCII_ENCODER.encode(str);
+    }
+
+    public static String asciiDecode(String str) {
+        return ASCII_DECODER.decode(str);
+    }
+
+    public static Predicate fromBinary(byte[] buf) {
+        return BinaryFormat.decode(buf);
+    }
+
+    public static Predicate fromString(String str) {
+        ANTLRStringStream input = new ANTLRStringStream(str);
+        PredicateLexer lexer = new PredicateLexer(input);
+        CommonTokenStream tokens = new CommonTokenStream(lexer);
+        PredicateParser parser = new PredicateParser(tokens);
+        try {
+            return parser.predicate();
+        } catch (RecognitionException e) {
+            throw new IllegalArgumentException(e);
+        }
+    }
+
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateHash.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateHash.java
new file mode 100644
index 00000000000..8c0c9ee590e
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateHash.java
@@ -0,0 +1,111 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+
+import com.yahoo.text.Utf8;
+
+/**
+ * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a>
+ * This hash function must match the corresponding C++ hash function in 'ConvertClass',
+ * currently located at 'rise_platform/src/interface/cpp/api/ConvertClass.h'
+ */
+public class PredicateHash {
+    @SuppressWarnings("fallthrough")
+    public static long hash64(String s) {
+        byte[] bytes = Utf8.toBytes(s);
+        long a=0L, b=0L;
+        long c=0x9e3779b97f4a7c13L;
+        int len = bytes.length;
+        int offset = 0;
+        while (len >= 24) {
+            c += ((0xffL & (long)bytes[offset + 23]) << 56) +
+                    ((0xffL & (long)bytes[offset + 22]) << 48) +
+                    ((0xffL & (long)bytes[offset + 21]) << 40) +
+                    ((0xffL & (long)bytes[offset + 20]) << 32) +
+                    ((0xffL & (long)bytes[offset + 19]) << 24) +
+                    ((0xffL & (long)bytes[offset + 18]) << 16) +
+                    ((0xffL & (long)bytes[offset + 17]) << 8) +
+                    ((0xffL & (long)bytes[offset + 16]));
+
+            b += ((0xffL & (long)bytes[offset + 15]) << 56) +
+                    ((0xffL & (long)bytes[offset + 14]) << 48) +
+                    ((0xffL & (long)bytes[offset + 13]) << 40) +
+                    ((0xffL & (long)bytes[offset + 12]) << 32) +
+                    ((0xffL & (long)bytes[offset + 11]) << 24) +
+                    ((0xffL & (long)bytes[offset + 10]) << 16) +
+                    ((0xffL & (long)bytes[offset + 9]) << 8) +
+                    ((0xffL & (long)bytes[offset + 8]));
+
+            a += ((0xffL & (long)bytes[offset + 7]) << 56) +
+                    ((0xffL & (long)bytes[offset + 6]) << 48) +
+                    ((0xffL & (long)bytes[offset + 5]) << 40) +
+                    ((0xffL & (long)bytes[offset + 4]) << 32) +
+                    ((0xffL & (long)bytes[offset + 3]) << 24) +
+                    ((0xffL & (long)bytes[offset + 2]) << 16) +
+                    ((0xffL & (long)bytes[offset + 1]) << 8) +
+                    ((0xffL & (long)bytes[offset + 0]));
+
+            // Mix.  This arithmetic must match the mix below.
+            a -= b; a -= c; a ^= (c>>>43);
+            b -= c; b -= a; b ^= (a<<9);
+            c -= a; c -= b; c ^= (b>>>8);
+            a -= b; a -= c; a ^= (c>>>38);
+            b -= c; b -= a; b ^= (a<<23);
+            c -= a; c -= b; c ^= (b>>>5);
+            a -= b; a -= c; a ^= (c>>>35);
+            b -= c; b -= a; b ^= (a<<49);
+            c -= a; c -= b; c ^= (b>>>11);
+            a -= b; a -= c; a ^= (c>>>12);
+            b -= c; b -= a; b ^= (a<<18);
+            c -= a; c -= b; c ^= (b>>>22);
+            // End mix.
+
+            offset += 24;
+            len -= 24;
+        }
+
+        c += bytes.length;
+        switch (len) {
+            case 23: c+= (0xffL & (long)bytes[offset + 22]) << 56;
+            case 22: c+= (0xffL & (long)bytes[offset + 21]) << 48;
+            case 21: c+= (0xffL & (long)bytes[offset + 20]) << 40;
+            case 20: c+= (0xffL & (long)bytes[offset + 19]) << 32;
+            case 19: c+= (0xffL & (long)bytes[offset + 18]) << 24;
+            case 18: c+= (0xffL & (long)bytes[offset + 17]) << 16;
+            case 17: c+= (0xffL & (long)bytes[offset + 16]) << 8;
+                // The first byte of c is reserved for the length
+            case 16: b+= (0xffL & (long)bytes[offset + 15]) << 56;
+            case 15: b+= (0xffL & (long)bytes[offset + 14]) << 48;
+            case 14: b+= (0xffL & (long)bytes[offset + 13]) << 40;
+            case 13: b+= (0xffL & (long)bytes[offset + 12]) << 32;
+            case 12: b+= (0xffL & (long)bytes[offset + 11]) << 24;
+            case 11: b+= (0xffL & (long)bytes[offset + 10]) << 16;
+            case 10: b+= (0xffL & (long)bytes[offset + 9]) << 8;
+            case 9:  b+= (0xffL & (long)bytes[offset + 8]);
+            case 8:  a+= (0xffL & (long)bytes[offset + 7]) << 56;
+            case 7:  a+= (0xffL & (long)bytes[offset + 6]) << 48;
+            case 6:  a+= (0xffL & (long)bytes[offset + 5]) << 40;
+            case 5:  a+= (0xffL & (long)bytes[offset + 4]) << 32;
+            case 4:  a+= (0xffL & (long)bytes[offset + 3]) << 24;
+            case 3:  a+= (0xffL & (long)bytes[offset + 2]) << 16;
+            case 2:  a+= (0xffL & (long)bytes[offset + 1]) << 8;
+            case 1:  a+= (0xffL & (long)bytes[offset + 0]);
+        }
+        // Mix.  This arithmetic must match the mix above.
+        a -= b; a -= c; a ^= (c>>>43);
+        b -= c; b -= a; b ^= (a<<9);
+        c -= a; c -= b; c ^= (b>>>8);
+        a -= b; a -= c; a ^= (c>>>38);
+        b -= c; b -= a; b ^= (a<<23);
+        c -= a; c -= b; c ^= (b>>>5);
+        a -= b; a -= c; a ^= (c>>>35);
+        b -= c; b -= a; b ^= (a<<49);
+        c -= a; c -= b; c ^= (b>>>11);
+        a -= b; a -= c; a ^= (c>>>12);
+        b -= c; b -= a; b ^= (a<<18);
+        c -= a; c -= b; c ^= (b>>>22);
+        // End mix.
+
+        return c;
+    }
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateOperator.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateOperator.java
new file mode 100644
index 00000000000..0c0af37a791
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateOperator.java
@@ -0,0 +1,12 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import java.util.List;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+abstract public class PredicateOperator extends Predicate {
+
+    public abstract List<Predicate> getOperands();
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateValue.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateValue.java
new file mode 100644
index 00000000000..f34a8f4b268
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateValue.java
@@ -0,0 +1,9 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+abstract class PredicateValue extends Predicate {
+
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicates.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicates.java
new file mode 100644
index 00000000000..7362eb5ba6d
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicates.java
@@ -0,0 +1,69 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class Predicates {
+
+    public static Conjunction and(Predicate... operands) {
+        return new Conjunction(operands);
+    }
+
+    public static Disjunction or(Predicate... operands) {
+        return new Disjunction(operands);
+    }
+
+    public static Negation not(Predicate operand) {
+        return new Negation(operand);
+    }
+
+    public static BooleanPredicate value(boolean value) {
+        return new BooleanPredicate(value);
+    }
+
+    public static FeatureBuilder feature(String key) {
+        return new FeatureBuilder(key);
+    }
+
+    public static class FeatureBuilder {
+
+        private final String key;
+
+        public FeatureBuilder(String key) {
+            this.key = key;
+        }
+
+        public FeatureRange lessThan(long toExclusive) {
+            return new FeatureRange(key, null, toExclusive - 1);
+        }
+
+        public FeatureRange lessThanOrEqualTo(long toInclusive) {
+            return new FeatureRange(key, null, toInclusive);
+        }
+
+        public FeatureRange greaterThan(long fromExclusive) {
+            return new FeatureRange(key, fromExclusive + 1, null);
+        }
+
+        public FeatureRange greaterThanOrEqualTo(long fromInclusive) {
+            return new FeatureRange(key, fromInclusive, null);
+        }
+
+        public FeatureRange inRange(long fromInclusive, long toInclusive) {
+            return new FeatureRange(key, fromInclusive, toInclusive);
+        }
+
+        public Negation notInRange(long fromInclusive, long toInclusive) {
+            return new Negation(new FeatureRange(key, fromInclusive, toInclusive));
+        }
+
+        public FeatureSet inSet(String... values) {
+            return new FeatureSet(key, values);
+        }
+
+        public Negation notInSet(String... values) {
+            return new Negation(new FeatureSet(key, values));
+        }
+    }
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangeEdgePartition.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangeEdgePartition.java
new file mode 100644
index 00000000000..0771f0ec08e
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangeEdgePartition.java
@@ -0,0 +1,86 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+/**
+ * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a>
+ */
+public class RangeEdgePartition extends RangePartition {
+    private final long value;
+    private final int lowerBound;
+    private final int upperBound;
+
+    public RangeEdgePartition(String label, long value, int lower, int upper) {
+        super(label);
+        this.value = value;
+        this.lowerBound = lower;
+        this.upperBound = upper;
+    }
+
+    public long getValue() {
+        return value;
+    }
+
+    public int getLowerBound() {
+        return lowerBound;
+    }
+
+    public int getUpperBound() {
+        return upperBound;
+    }
+
+    @Override
+    public RangeEdgePartition clone() throws CloneNotSupportedException {
+        return (RangeEdgePartition)super.clone();
+    }
+
+    @Override
+    public int hashCode() {
+        return super.hashCode() + new Long(value).hashCode() +
+                new Integer(lowerBound).hashCode() + new Integer(upperBound).hashCode();
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj == this) {
+            return true;
+        }
+        if (!(obj instanceof RangeEdgePartition)) {
+            return false;
+        }
+        RangeEdgePartition other = (RangeEdgePartition)obj;
+        return super.equals(other) &&
+                value == other.value &&
+                lowerBound == other.lowerBound &&
+                upperBound == other.upperBound;
+    }
+
+    @Override
+    protected void appendTo(StringBuilder out) {
+        super.appendTo(out);
+
+        out.append("+[");
+        if (lowerBound > 0)
+            out.append(lowerBound);
+        out.append("..");
+        if (upperBound >= 0)
+            out.append(upperBound);
+        out.append(']');
+    }
+
+    public long encodeBounds() {
+        if (lowerBound > 0) {
+            if (upperBound >= 0) {
+                return lowerBound << 16 | (upperBound + 1);
+            } else {
+                return lowerBound | 0x80000000L;
+            }
+        } else {
+            if (upperBound >= 0) {
+                return (upperBound + 1) | 0x40000000;
+            } else {
+                return 0x80000000L;  // >0
+            }
+        }
+    }
+
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangePartition.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangePartition.java
new file mode 100644
index 00000000000..33cdd23c45c
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangePartition.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.document.predicate;
+
+/**
+ * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a>
+ */
+public class RangePartition extends PredicateValue {
+
+    private String label;
+
+    public RangePartition(String label) {
+        this.label = label;
+    }
+
+    public RangePartition(String key, long fromInclusive, long toInclusive, boolean isNeg) {
+        this(makeLabel(key, fromInclusive, toInclusive, isNeg));
+    }
+
+    private static String makeLabel(String key, long fromInclusive, long toInclusive, boolean isNeg) {
+        if (isNeg) {
+            // special case for toInclusive==long_min: It will print its own hyphen.
+            return key + "=" + (toInclusive==0x8000000000000000L? "" : "-") + toInclusive + "-" + fromInclusive;
+        } else {
+            // special case for toInclusive==long_min: It will print its own hyphen.
+            return key + "=" + fromInclusive + (toInclusive==0x8000000000000000L? "" : "-") + toInclusive;
+        }
+    }
+
+    public String getLabel() {
+        return label;
+    }
+
+    @Override
+    public RangePartition clone() throws CloneNotSupportedException {
+        return (RangePartition)super.clone();
+    }
+
+    @Override
+    public int hashCode() {
+        return label.hashCode();
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj == this) {
+            return true;
+        }
+        if (!(obj instanceof RangePartition)) {
+            return false;
+        }
+        return label.equals(((RangePartition)obj).getLabel());
+    }
+
+    @Override
+    protected void appendTo(StringBuilder out) {
+        int i = label.lastIndexOf('=');
+        appendQuotedTo(label.substring(0, i), out);
+        if (out.charAt(out.length() - 1) == '\'') {
+            out.deleteCharAt(out.length() - 1);
+            out.append(label.substring(i));
+            out.append('\'');
+        } else {
+            out.append(label.substring(i));
+        }
+    }
+
+}
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/SimplePredicates.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/SimplePredicates.java
new file mode 100644
index 00000000000..1b339767109
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/SimplePredicates.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.document.predicate;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class SimplePredicates {
+
+    public static Predicate newPredicate() {
+        return new Predicate() {
+
+            @Override
+            protected void appendTo(StringBuilder out) {
+                out.append("<anon>");
+            }
+
+        };
+    }
+
+    public static Predicate newString(String str) {
+        return new StringNode(str);
+    }
+
+    public static List<Predicate> newStrings(String... arr) {
+        List<Predicate> ret = new ArrayList<>(arr.length);
+        for (String str : arr) {
+            ret.add(newString(str));
+        }
+        return ret;
+    }
+
+    private static class StringNode extends Predicate {
+
+        final String str;
+
+        StringNode(String str) {
+            this.str = str;
+        }
+
+        @Override
+        public int hashCode() {
+            return str.hashCode();
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            if (obj == this) {
+                return true;
+            }
+            if (!(obj instanceof StringNode)) {
+                return false;
+            }
+            StringNode rhs = (StringNode)obj;
+            if (!str.equals(rhs.str)) {
+                return false;
+            }
+            return true;
+        }
+
+        @Override
+        protected void appendTo(StringBuilder out) {
+            out.append(str);
+        }
+
+    }
+}
+
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/package-info.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/package-info.java
new file mode 100644
index 00000000000..ef3b6954992
--- /dev/null
+++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/package-info.java
@@ -0,0 +1,8 @@
+// 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
+@com.yahoo.api.annotations.PublicApi
+/*
+    The predicate package is exported by the document module (OSGi).
+    Do not remove unless the intention is to modify the public API of document.
+ */
+package com.yahoo.document.predicate;
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;
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/BinaryFormatTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/BinaryFormatTest.java
new file mode 100644
index 00000000000..44477423fdb
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/BinaryFormatTest.java
@@ -0,0 +1,124 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import com.yahoo.slime.Inspector;
+import com.yahoo.slime.Slime;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class BinaryFormatTest {
+
+    @Test
+    public void requireThatEncodeNullThrows() {
+        try {
+            BinaryFormat.encode(null);
+            fail();
+        } catch (NullPointerException e) {
+            assertEquals("predicate", e.getMessage());
+        }
+    }
+
+    @Test
+    public void requireThatDecodeNullThrows() {
+        try {
+            BinaryFormat.decode(null);
+            fail();
+        } catch (NullPointerException e) {
+            assertEquals("buf", e.getMessage());
+        }
+    }
+
+    @Test
+    public void requireThatDecodeEmptyThrows() {
+        try {
+            BinaryFormat.decode(new byte[0]);
+            fail();
+        } catch (UnsupportedOperationException e) {
+            assertEquals("0", e.getMessage());
+        }
+    }
+
+    @Test
+    public void requireThatConjunctionCanBeSerialized() {
+        assertSerialize(new Conjunction(new FeatureSet("foo", "bar"), new FeatureSet("baz", "cox")));
+    }
+
+    @Test
+    public void requireThatDisjunctionCanBeSerialized() {
+        assertSerialize(new Disjunction(new FeatureSet("foo", "bar"), new FeatureSet("baz", "cox")));
+    }
+
+    @Test
+    public void requireThatFeatureRangeCanBeSerialized() {
+        assertSerialize(new FeatureRange("foo", null, null));
+        assertSerialize(new FeatureRange("foo", null, 9L));
+        assertSerialize(new FeatureRange("foo", 6L, null));
+        assertSerialize(new FeatureRange("foo", 6L, 9L));
+    }
+
+    @Test
+    public void requireThatPartitionedFeatureRangeCanBeSerialized() {
+        FeatureRange expected = new FeatureRange("foo", 8L, 20L);
+        FeatureRange f = new FeatureRange("foo", 8L, 20L);
+        f.addPartition(new RangeEdgePartition("foo=0", 0, 8, -1));
+        f.addPartition(new RangeEdgePartition("foo=20", 20, 0, 0));
+        f.addPartition(new RangePartition("foo", 10, 19, false));
+        assertSerializesTo(expected, f);
+        Slime slime = com.yahoo.slime.BinaryFormat.decode(BinaryFormat.encode(f));
+        assertEquals(BinaryFormat.TYPE_FEATURE_RANGE, slime.get().field(BinaryFormat.NODE_TYPE).asLong());
+        Inspector in1 = slime.get().field(BinaryFormat.HASHED_PARTITIONS);
+        assertEquals(1, in1.entries());
+        assertEquals(0xf2b6d1cc6322cb99L, in1.entry(0).asLong());
+        Inspector in2 = slime.get().field(BinaryFormat.HASHED_EDGE_PARTITIONS);
+        assertEquals(2, in2.entries());
+        Inspector obj1 = in2.entry(0);
+        assertEquals(0xb2b301e26efffdc2L, obj1.field(BinaryFormat.HASH).asLong());
+        assertEquals(0, obj1.field(BinaryFormat.VALUE).asLong());
+        assertEquals(0x80000008L, obj1.field(BinaryFormat.PAYLOAD).asLong());
+        Inspector obj2 = in2.entry(1);
+        assertEquals(0x22acb2ed72523c36L, obj2.field(BinaryFormat.HASH).asLong());
+        assertEquals(20, obj2.field(BinaryFormat.VALUE).asLong());
+        assertEquals(0x40000001L, obj2.field(BinaryFormat.PAYLOAD).asLong());
+    }
+
+    @Test
+    public void requireThatFeatureSetCanBeSerialized() {
+        assertSerialize(new FeatureSet("foo"));
+        assertSerialize(new FeatureSet("foo", "bar"));
+        assertSerialize(new FeatureSet("foo", "bar", "baz"));
+    }
+
+    @Test
+    public void requireThatNegationCanBeSerialized() {
+        assertSerialize(new Negation(new FeatureSet("foo", "bar")));
+    }
+
+    @Test
+    public void requireThatBooleanCanBeSerialized() {
+        assertSerialize(new BooleanPredicate(true));
+        assertSerialize(new BooleanPredicate(false));
+    }
+
+    @Test
+    public void requireThatUnknownNodeThrows() {
+        try {
+            BinaryFormat.encode(SimplePredicates.newString("foo"));
+            fail();
+        } catch (UnsupportedOperationException e) {
+
+        }
+    }
+
+    private static void assertSerializesTo(Predicate expected, Predicate predicate) {
+        assertEquals(expected, BinaryFormat.decode(BinaryFormat.encode(predicate)));
+    }
+
+    private static void assertSerialize(Predicate predicate) {
+        assertSerializesTo(predicate, predicate);
+    }
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/BooleanPredicateTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/BooleanPredicateTest.java
new file mode 100644
index 00000000000..7268b358889
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/BooleanPredicateTest.java
@@ -0,0 +1,47 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotSame;
+import static org.junit.Assert.assertTrue;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class BooleanPredicateTest {
+
+    @Test
+    public void requireThatFalseIsAValue() {
+        assertTrue(PredicateValue.class.isAssignableFrom(BooleanPredicate.class));
+    }
+
+    @Test
+    public void requireThatCloneIsImplemented() throws CloneNotSupportedException {
+        BooleanPredicate node1 = new BooleanPredicate(true);
+        BooleanPredicate node2 = node1.clone();
+        assertEquals(node1, node2);
+        assertNotSame(node1, node2);
+    }
+
+    @Test
+    public void requireThatHashCodeIsImplemented() {
+        assertEquals(new BooleanPredicate(true).hashCode(), new BooleanPredicate(true).hashCode());
+        assertEquals(new BooleanPredicate(false).hashCode(), new BooleanPredicate(false).hashCode());
+    }
+
+    @Test
+    public void requireThatEqualsIsImplemented() {
+        BooleanPredicate lhs = new BooleanPredicate(true);
+        assertTrue(lhs.equals(lhs));
+        assertFalse(lhs.equals(new Object()));
+
+        BooleanPredicate rhs = new BooleanPredicate(false);
+        assertFalse(lhs.equals(rhs));
+        rhs.setValue(true);
+        assertTrue(lhs.equals(rhs));
+    }
+
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/ConjunctionTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/ConjunctionTest.java
new file mode 100644
index 00000000000..6e12a00ba4d
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/ConjunctionTest.java
@@ -0,0 +1,113 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import java.util.Arrays;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotSame;
+import static org.junit.Assert.assertTrue;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class ConjunctionTest {
+
+    @Test
+    public void requireThatConjunctionIsAnOperator() {
+        assertTrue(PredicateOperator.class.isAssignableFrom(Conjunction.class));
+    }
+
+    @Test
+    public void requireThatAccessorsWork() {
+        Conjunction node = new Conjunction();
+        Predicate a = SimplePredicates.newString("a");
+        node.addOperand(a);
+        assertEquals(Arrays.asList(a), node.getOperands());
+        Predicate b = SimplePredicates.newString("b");
+        node.addOperand(b);
+        assertEquals(Arrays.asList(a, b), node.getOperands());
+        Predicate c = SimplePredicates.newString("c");
+        Predicate d = SimplePredicates.newString("d");
+        node.addOperands(Arrays.asList(c, d));
+        assertEquals(Arrays.asList(a, b, c, d), node.getOperands());
+        Predicate e = SimplePredicates.newString("e");
+        Predicate f = SimplePredicates.newString("f");
+        node.setOperands(Arrays.asList(e, f));
+        assertEquals(Arrays.asList(e, f), node.getOperands());
+    }
+
+    @Test
+    public void requireThatConstructorsWork() {
+        Predicate foo = SimplePredicates.newString("foo");
+        Predicate bar = SimplePredicates.newString("bar");
+        Conjunction node = new Conjunction(foo, bar);
+        assertEquals(Arrays.asList(foo, bar), node.getOperands());
+
+        node = new Conjunction(Arrays.asList(foo, bar));
+        assertEquals(Arrays.asList(foo, bar), node.getOperands());
+    }
+
+    @Test
+    public void requireThatCloneIsImplemented() throws CloneNotSupportedException {
+        Conjunction node1 = new Conjunction(SimplePredicates.newString("a"), SimplePredicates.newString("b"));
+        Conjunction node2 = node1.clone();
+        assertEquals(node1, node2);
+        assertNotSame(node1, node2);
+        assertNotSame(node1.getOperands(), node2.getOperands());
+    }
+
+    @Test
+    public void requireThatHashCodeIsImplemented() {
+        assertEquals(new Conjunction().hashCode(), new Conjunction().hashCode());
+    }
+
+    @Test
+    public void requireThatEqualsIsImplemented() {
+        Conjunction lhs = new Conjunction(SimplePredicates.newString("foo"),
+                                          SimplePredicates.newString("bar"));
+        assertTrue(lhs.equals(lhs));
+        assertFalse(lhs.equals(new Object()));
+
+        Conjunction rhs = new Conjunction();
+        assertFalse(lhs.equals(rhs));
+        rhs.addOperand(SimplePredicates.newString("foo"));
+        assertFalse(lhs.equals(rhs));
+        rhs.addOperand(SimplePredicates.newString("bar"));
+        assertTrue(lhs.equals(rhs));
+    }
+
+    @Test
+    public void requireThatNodeDelimiterIsAND() {
+        assertEquals("", newConjunction().toString());
+        assertEquals("foo", newConjunction("foo").toString());
+        assertEquals("foo and bar", newConjunction("foo", "bar").toString());
+        assertEquals("foo and bar and baz", newConjunction("foo", "bar", "baz").toString());
+    }
+
+    @Test
+    public void requireThatSimpleConjunctionsArePrettyPrinted() {
+        assertEquals("foo and bar",
+                     new Conjunction(SimplePredicates.newString("foo"),
+                                     SimplePredicates.newString("bar")).toString());
+    }
+
+    @Test
+    public void requireThatComplexConjunctionsArePrintedAsGroup() {
+        assertEquals("foo and bar and baz",
+                     new Conjunction(SimplePredicates.newString("foo"),
+                                     new Conjunction(SimplePredicates.newString("bar"),
+                                                     SimplePredicates.newString("baz"))).toString());
+        assertEquals("foo and (bar or baz)",
+                     new Conjunction(SimplePredicates.newString("foo"),
+                                     new Disjunction(SimplePredicates.newString("bar"),
+                                                     SimplePredicates.newString("baz"))).toString());
+    }
+
+    private static Conjunction newConjunction(String... operands) {
+        return new Conjunction(SimplePredicates.newStrings(operands));
+    }
+
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/DisjunctionTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/DisjunctionTest.java
new file mode 100644
index 00000000000..99dc46c4f5f
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/DisjunctionTest.java
@@ -0,0 +1,113 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import java.util.Arrays;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotSame;
+import static org.junit.Assert.assertTrue;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class DisjunctionTest {
+
+    @Test
+    public void requireThatDisjunctionIsAnOperator() {
+        assertTrue(PredicateOperator.class.isAssignableFrom(Disjunction.class));
+    }
+
+    @Test
+    public void requireThatAccessorsWork() {
+        Disjunction node = new Disjunction();
+        Predicate a = SimplePredicates.newString("a");
+        node.addOperand(a);
+        assertEquals(Arrays.asList(a), node.getOperands());
+        Predicate b = SimplePredicates.newString("b");
+        node.addOperand(b);
+        assertEquals(Arrays.asList(a, b), node.getOperands());
+        Predicate c = SimplePredicates.newString("c");
+        Predicate d = SimplePredicates.newString("d");
+        node.addOperands(Arrays.asList(c, d));
+        assertEquals(Arrays.asList(a, b, c, d), node.getOperands());
+        Predicate e = SimplePredicates.newString("e");
+        Predicate f = SimplePredicates.newString("f");
+        node.setOperands(Arrays.asList(e, f));
+        assertEquals(Arrays.asList(e, f), node.getOperands());
+    }
+
+    @Test
+    public void requireThatConstructorsWork() {
+        Predicate foo = SimplePredicates.newString("foo");
+        Predicate bar = SimplePredicates.newString("bar");
+        Disjunction node = new Disjunction(foo, bar);
+        assertEquals(Arrays.asList(foo, bar), node.getOperands());
+
+        node = new Disjunction(Arrays.asList(foo, bar));
+        assertEquals(Arrays.asList(foo, bar), node.getOperands());
+    }
+
+    @Test
+    public void requireThatCloneIsImplemented() throws CloneNotSupportedException {
+        Disjunction node1 = new Disjunction(SimplePredicates.newString("a"), SimplePredicates.newString("b"));
+        Disjunction node2 = node1.clone();
+        assertEquals(node1, node2);
+        assertNotSame(node1, node2);
+        assertNotSame(node1.getOperands(), node2.getOperands());
+    }
+
+    @Test
+    public void requireThatHashCodeIsImplemented() {
+        assertEquals(new Disjunction().hashCode(), new Disjunction().hashCode());
+    }
+
+    @Test
+    public void requireThatEqualsIsImplemented() {
+        Disjunction lhs = new Disjunction(SimplePredicates.newString("foo"),
+                                          SimplePredicates.newString("bar"));
+        assertTrue(lhs.equals(lhs));
+        assertFalse(lhs.equals(new Object()));
+
+        Disjunction rhs = new Disjunction();
+        assertFalse(lhs.equals(rhs));
+        rhs.addOperand(SimplePredicates.newString("foo"));
+        assertFalse(lhs.equals(rhs));
+        rhs.addOperand(SimplePredicates.newString("bar"));
+        assertTrue(lhs.equals(rhs));
+    }
+
+    @Test
+    public void requireThatNodeDelimiterIsOR() {
+        assertEquals("", newDisjunction().toString());
+        assertEquals("foo", newDisjunction("foo").toString());
+        assertEquals("foo or bar", newDisjunction("foo", "bar").toString());
+        assertEquals("foo or bar or baz", newDisjunction("foo", "bar", "baz").toString());
+    }
+
+    @Test
+    public void requireThatSimpleDisjunctionsArePrettyPrinted() {
+        assertEquals("foo or bar",
+                     new Disjunction(SimplePredicates.newString("foo"),
+                                     SimplePredicates.newString("bar")).toString());
+    }
+
+    @Test
+    public void requireThatComplexDisjunctionsArePrintedAsGroup() {
+        assertEquals("foo or bar or baz",
+                     new Disjunction(SimplePredicates.newString("foo"),
+                                     new Disjunction(SimplePredicates.newString("bar"),
+                                                     SimplePredicates.newString("baz"))).toString());
+        assertEquals("foo or (bar and baz)",
+                     new Disjunction(SimplePredicates.newString("foo"),
+                                     new Conjunction(SimplePredicates.newString("bar"),
+                                                     SimplePredicates.newString("baz"))).toString());
+    }
+
+    private static Disjunction newDisjunction(String... operands) {
+        return new Disjunction(SimplePredicates.newStrings(operands));
+    }
+
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureConjunctionTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureConjunctionTest.java
new file mode 100644
index 00000000000..e98400e86fa
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureConjunctionTest.java
@@ -0,0 +1,52 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import java.util.Arrays;
+import java.util.Collections;
+
+import static com.yahoo.document.predicate.Predicates.feature;
+import static com.yahoo.document.predicate.Predicates.not;
+
+/**
+ * @author bjorncs
+ */
+public class FeatureConjunctionTest {
+
+    @Test
+    public void require_that_featureconjunction_with_valid_operands_can_be_constructed() {
+        new FeatureConjunction(Arrays.asList(
+                not(feature("a").inSet("1")),
+                feature("b").inSet("1")));
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void require_that_constructor_throws_exception_if_all_operands_are_not_featuresets() {
+        new FeatureConjunction(Arrays.asList(
+                not(feature("a").inSet("1")),
+                feature("b").inRange(1, 2)));
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void require_that_constructor_throws_exception_if_single_operand() {
+        new FeatureConjunction(Arrays.asList(feature("a").inSet("1")));
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void require_that_constructor_throws_exception_if_no_operands() {
+        new FeatureConjunction(Collections.emptyList());
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void require_that_contructor_throws_exception_if_featuresets_contain_multiple_values() {
+        new FeatureConjunction(Arrays.asList(feature("a").inSet("1"), feature("b").inSet("2", "3")));
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void require_that_constructor_throws_exception_if_featureset_keys_are_not_unique() {
+        new FeatureConjunction(Arrays.asList(
+                not(feature("a").inSet("1")),
+                feature("a").inSet("2")));
+    }
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureRangeTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureRangeTest.java
new file mode 100644
index 00000000000..efcc0e5b64a
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureRangeTest.java
@@ -0,0 +1,263 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import java.util.Arrays;
+
+import static org.junit.Assert.*;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class FeatureRangeTest {
+
+    @Test
+    public void requireThatFeatureRangeIsAValue() {
+        assertTrue(PredicateValue.class.isAssignableFrom(FeatureRange.class));
+    }
+
+    @Test
+    public void requireThatAccessorsWork() {
+        FeatureRange node = new FeatureRange("foo");
+        assertEquals("foo", node.getKey());
+        node.setKey("bar");
+        assertEquals("bar", node.getKey());
+
+        node.setFromInclusive(69L);
+        assertEquals(69, node.getFromInclusive().intValue());
+        node.setFromInclusive(null);
+        assertNull(node.getFromInclusive());
+
+        node.setToInclusive(69L);
+        assertEquals(69, node.getToInclusive().intValue());
+        node.setToInclusive(null);
+        assertNull(node.getToInclusive());
+    }
+
+    @Test
+    public void requireThatConstructorsWork() {
+        FeatureRange node = new FeatureRange("foo");
+        assertEquals("foo", node.getKey());
+        assertNull(node.getFromInclusive());
+        assertNull(node.getToInclusive());
+
+        node = new FeatureRange("foo", null, null);
+        assertEquals("foo", node.getKey());
+        assertNull(node.getFromInclusive());
+        assertNull(node.getToInclusive());
+
+        node = new FeatureRange("foo", 69L, null);
+        assertEquals("foo", node.getKey());
+        assertEquals(69, node.getFromInclusive().intValue());
+        assertNull(node.getToInclusive());
+
+        node = new FeatureRange("foo", null, 69L);
+        assertEquals("foo", node.getKey());
+        assertNull(node.getFromInclusive());
+        assertEquals(69, node.getToInclusive().intValue());
+
+        node = new FeatureRange("foo", 6L, 9L);
+        assertEquals("foo", node.getKey());
+        assertEquals(6, node.getFromInclusive().intValue());
+        assertEquals(9, node.getToInclusive().intValue());
+    }
+
+    @Test
+    public void requireThatCloneIsImplemented() throws CloneNotSupportedException {
+        FeatureRange node1 = new FeatureRange("foo", 6L, 9L);
+        FeatureRange node2 = node1.clone();
+        assertEquals(node1, node2);
+        assertNotSame(node1, node2);
+    }
+
+    @Test
+    public void requireThatHashCodeIsImplemented() {
+        assertEquals(new FeatureRange("key").hashCode(), new FeatureRange("key").hashCode());
+    }
+
+    @Test
+    public void requireThatEqualsIsImplemented() {
+        FeatureRange lhs = new FeatureRange("foo", 6L, 9L);
+        assertTrue(lhs.equals(lhs));
+        assertFalse(lhs.equals(new Object()));
+
+        FeatureRange rhs = new FeatureRange("bar");
+        assertFalse(lhs.equals(rhs));
+        rhs.setKey("foo");
+        assertFalse(lhs.equals(rhs));
+        rhs.setFromInclusive(6L);
+        assertFalse(lhs.equals(rhs));
+        rhs.setToInclusive(9L);
+        assertTrue(lhs.equals(rhs));
+        rhs.addPartition(new RangePartition("foo"));
+        assertFalse(lhs.equals(rhs));
+        lhs.addPartition(new RangePartition("foo"));
+        assertTrue(lhs.equals(rhs));
+        rhs.addPartition(new RangeEdgePartition("foo", 10, 0, 2));
+        assertFalse(lhs.equals(rhs));
+        lhs.addPartition(new RangeEdgePartition("foo", 10, 0, 2));
+        assertTrue(lhs.equals(rhs));
+    }
+
+    @Test
+    public void requireThatFeatureKeyIsMandatoryInConstructor() {
+        try {
+            new FeatureRange(null);
+            fail();
+        } catch (NullPointerException e) {
+            assertEquals("key", e.getMessage());
+        }
+    }
+
+    @Test
+    public void requireThatFeatureKeyIsMandatoryInSetter() {
+        FeatureRange node = new FeatureRange("foo");
+        try {
+            node.setKey(null);
+            fail();
+        } catch (NullPointerException e) {
+            assertEquals("key", e.getMessage());
+        }
+        assertEquals("foo", node.getKey());
+    }
+
+    @Test
+    public void requireThatRangeCanBeSingleValue() {
+        FeatureRange node = new FeatureRange("key", 6L, 6L);
+        assertEquals(6, node.getFromInclusive().intValue());
+        assertEquals(6, node.getToInclusive().intValue());
+        node.setToInclusive(9L);
+        node.setFromInclusive(9L);
+        assertEquals(9, node.getFromInclusive().intValue());
+        assertEquals(9, node.getToInclusive().intValue());
+    }
+
+    @Test
+    public void requireThatFromCanNotBeConstructedGreaterThanTo() {
+        try {
+            new FeatureRange("key", 9L, 6L);
+            fail();
+        } catch (IllegalArgumentException e) {
+            assertEquals("Expected 'to' greater than or equal to 9, got 6.", e.getMessage());
+        }
+    }
+
+    @Test
+    public void requireThatFromCanNotBeSetGreaterThanTo() {
+        FeatureRange node = new FeatureRange("key", null, 6L);
+        try {
+            node.setFromInclusive(9L);
+            fail();
+        } catch (IllegalArgumentException e) {
+            assertEquals("Expected 'from' less than or equal to 6, got 9.", e.getMessage());
+        }
+        assertNull(node.getFromInclusive());
+
+        node = new FeatureRange("key", 6L, 9L);
+        try {
+            node.setFromInclusive(69L);
+            fail();
+        } catch (IllegalArgumentException e) {
+            assertEquals("Expected 'from' less than or equal to 9, got 69.", e.getMessage());
+        }
+        assertEquals(6, node.getFromInclusive().intValue());
+    }
+
+    @Test
+    public void requireThatToCanNotBeSetLessThanFrom() {
+        FeatureRange node = new FeatureRange("key", 9L, null);
+        try {
+            node.setToInclusive(6L);
+            fail();
+        } catch (IllegalArgumentException e) {
+            assertEquals("Expected 'to' greater than or equal to 9, got 6.", e.getMessage());
+        }
+        assertNull(node.getToInclusive());
+
+        node = new FeatureRange("key", 6L, 9L);
+        try {
+            node.setToInclusive(1L);
+            fail();
+        } catch (IllegalArgumentException e) {
+            assertEquals("Expected 'to' greater than or equal to 6, got 1.", e.getMessage());
+        }
+        assertEquals(9, node.getToInclusive().intValue());
+    }
+
+    @Test
+    public void requireThatKeyIsEscapedInToString() {
+        assertEquals("foo in [6..9]",
+                     new FeatureRange("foo", 6L, 9L).toString());
+        assertEquals("'\\foo' in [6..9]",
+                     new FeatureRange("\foo", 6L, 9L).toString());
+        assertEquals("'\\x27foo\\x27' in [6..9]",
+                     new FeatureRange("'foo'", 6L, 9L).toString());
+    }
+
+    @Test
+    public void requireThatToStringIncludesLimits() {
+        assertEquals("foo in [6..9]", new FeatureRange("foo", 6L, 9L).toString());
+    }
+
+    @Test
+    public void requireThatToStringAllowsNullLimits() {
+        assertEquals("foo in [..]", new FeatureRange("foo").toString());
+    }
+
+    @Test
+    public void requireThatToStringAllowsNullFromLimit() {
+        assertEquals("foo in [..69]", new FeatureRange("foo", null, 69L).toString());
+    }
+
+    @Test
+    public void requireThatToStringAllowsNullToLimit() {
+        assertEquals("foo in [69..]", new FeatureRange("foo", 69L, null).toString());
+    }
+
+    @Test
+    public void requireThatSimpleStringsArePrettyPrinted() {
+        assertEquals("foo in [6..9]",
+                     new FeatureRange("foo", 6L, 9L).toString());
+    }
+
+    @Test
+    public void requireThatComplexStringsAreEscaped() {
+        assertEquals("'\\foo' in [6..9]",
+                     new FeatureRange("\foo", 6L, 9L).toString());
+    }
+
+    @Test
+    public void requireThatRangePartitionsCanBeAdded() {
+        FeatureRange range = new FeatureRange("foo", 10L, 22L);
+        range.addPartition(new RangePartition("foo=10-19"));
+        range.addPartition(new RangePartition("foo", 0, 0x8000000000000000L, true));
+        range.addPartition(new RangeEdgePartition("foo=20", 20, 0, 2));
+        assertEquals("foo in [10..22 (foo=20+[..2],foo=10-19,foo=-9223372036854775808-0)]", range.toString());
+    }
+
+    @Test
+    public void requireThatRangePartitionsCanBeCleared() {
+        FeatureRange range = new FeatureRange("foo", 10L, 22L);
+        range.addPartition(new RangePartition("foo=10-19"));
+        range.addPartition(new RangeEdgePartition("foo=20", 20, 0, 2));
+        assertEquals("foo in [10..22 (foo=20+[..2],foo=10-19)]", range.toString());
+        range.clearPartitions();
+        assertEquals("foo in [10..22]", range.toString());
+    }
+
+    @Test
+    public void requireThatFeatureRangeCanBeBuiltFromMixedInNode() {
+        assertEquals(new FeatureRange("foo", 10L, 19L),
+                FeatureRange.buildFromMixedIn("foo", Arrays.asList("foo=10-19"), 10));
+        assertEquals(new FeatureRange("foo", -19L, -10L),
+                FeatureRange.buildFromMixedIn("foo", Arrays.asList("foo=-10-19"), 10));
+        assertEquals(new FeatureRange("foo", 10L, 19L),
+                FeatureRange.buildFromMixedIn("foo", Arrays.asList("foo=10,10,9"), 10));
+        assertEquals(new FeatureRange("foo", 10L, 19L),
+                FeatureRange.buildFromMixedIn("foo", Arrays.asList("foo=10,10,1073741833"), 10));
+        assertEquals(new FeatureRange("foo", 10L, 19L),
+                FeatureRange.buildFromMixedIn("foo", Arrays.asList("foo=10,10,2147483648"), 10));
+    }
+
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureSetTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureSetTest.java
new file mode 100644
index 00000000000..7bc9d5f2c04
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureSetTest.java
@@ -0,0 +1,180 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNotSame;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class FeatureSetTest {
+
+    @Test
+    public void requireThatFeatureSetIsAValue() {
+        assertTrue(PredicateValue.class.isAssignableFrom(FeatureSet.class));
+    }
+
+    @Test
+    public void requireThatAccessorsWork() {
+        FeatureSet node = new FeatureSet("key", "valueA", "valueB");
+        assertEquals("key", node.getKey());
+        assertValues(Arrays.asList("valueA", "valueB"), node);
+        node.addValue("valueC");
+        assertValues(Arrays.asList("valueA", "valueB", "valueC"), node);
+        node.addValues(Arrays.asList("valueD", "valueE"));
+        assertValues(Arrays.asList("valueA", "valueB", "valueC", "valueD", "valueE"), node);
+        node.setValues(Arrays.asList("valueF", "valueG"));
+        assertValues(Arrays.asList("valueF", "valueG"), node);
+    }
+
+    @Test
+    public void requireThatValueSetIsMutable() {
+        FeatureSet node = new FeatureSet("key");
+        node.getValues().add("valueA");
+        assertValues(Arrays.asList("valueA"), node);
+
+        node = new FeatureSet("key", "valueA");
+        node.getValues().add("valueB");
+        assertValues(Arrays.asList("valueA", "valueB"), node);
+    }
+
+    @Test
+    public void requireThatConstructorsWork() {
+        FeatureSet node = new FeatureSet("key", "valueA", "valueB");
+        assertEquals("key", node.getKey());
+        assertValues(Arrays.asList("valueA", "valueB"), node);
+
+        node = new FeatureSet("key", Arrays.asList("valueA", "valueB"));
+        assertEquals("key", node.getKey());
+        assertValues(Arrays.asList("valueA", "valueB"), node);
+    }
+
+    @Test
+    public void requireThatCloneIsImplemented() throws CloneNotSupportedException {
+        FeatureSet node1 = new FeatureSet("key", "valueA", "valueB");
+        FeatureSet node2 = node1.clone();
+        assertEquals(node1, node2);
+        assertNotSame(node1, node2);
+        assertNotSame(node1.getValues(), node2.getValues());
+    }
+
+    @Test
+    public void requireThatHashCodeIsImplemented() {
+        assertEquals(new FeatureSet("key").hashCode(), new FeatureSet("key").hashCode());
+    }
+
+    @Test
+    public void requireThatEqualsIsImplemented() {
+        FeatureSet lhs = new FeatureSet("keyA", "valueA", "valueB");
+        assertTrue(lhs.equals(lhs));
+        assertFalse(lhs.equals(new Object()));
+
+        FeatureSet rhs = new FeatureSet("keyB");
+        assertFalse(lhs.equals(rhs));
+        rhs.setKey("keyA");
+        assertFalse(lhs.equals(rhs));
+        rhs.addValue("valueA");
+        assertFalse(lhs.equals(rhs));
+        rhs.addValue("valueB");
+        assertTrue(lhs.equals(rhs));
+    }
+
+    @Test
+    public void requireThatkeyIsMandatoryInConstructor() {
+        try {
+            new FeatureSet(null);
+            fail();
+        } catch (NullPointerException e) {
+            assertEquals("key", e.getMessage());
+        }
+        try {
+            new FeatureSet(null, Collections.<String>emptyList());
+            fail();
+        } catch (NullPointerException e) {
+            assertEquals("key", e.getMessage());
+        }
+    }
+
+    @Test
+    public void requireThatkeyIsMandatoryInSetter() {
+        FeatureSet node = new FeatureSet("foo");
+        try {
+            node.setKey(null);
+            fail();
+        } catch (NullPointerException e) {
+            assertEquals("key", e.getMessage());
+        }
+        assertEquals("foo", node.getKey());
+    }
+
+    @Test
+    public void requireThatValueIsMandatoryInSetter() {
+        FeatureSet node = new FeatureSet("foo", "bar");
+        try {
+            node.addValue(null);
+            fail();
+        } catch (NullPointerException e) {
+            assertEquals("value", e.getMessage());
+        }
+        assertValues(Arrays.asList("bar"), node);
+    }
+
+    @Test
+    public void requireThatKeyIsEscapedInToString() {
+        assertEquals("foo in [val]",
+                     new FeatureSet("foo", "val").toString());
+        assertEquals("'\\foo' in [val]",
+                     new FeatureSet("\foo", "val").toString());
+        assertEquals("'\\x27foo\\x27' in [val]",
+                     new FeatureSet("'foo'", "val").toString());
+    }
+
+    @Test
+    public void requireThatValuesAreEscapedInToString() {
+        assertEquals("key in [bar, foo]",
+                     new FeatureSet("key", "foo", "bar").toString());
+        assertEquals("key in ['\\foo', 'ba\\r']",
+                     new FeatureSet("key", "\foo", "ba\r").toString());
+        assertEquals("key in ['\\x27bar\\x27', '\\x27foo\\x27']",
+                     new FeatureSet("key", "'foo'", "'bar'").toString());
+    }
+
+    @Test
+    public void requireThatSimpleStringsArePrettyPrinted() {
+        assertEquals("foo in [bar]",
+                     new FeatureSet("foo", "bar").toString());
+    }
+
+    @Test
+    public void requireThatComplexStringsAreEscaped() {
+        assertEquals("'\\foo' in ['ba\\r']",
+                     new FeatureSet("\foo", "ba\r").toString());
+    }
+
+    @Test
+    public void requireThatNegatedFeatureSetsArePrettyPrinted() {
+        assertEquals("country not in [no, se]",
+                     new Negation(new FeatureSet("country", "no", "se")).toString());
+    }
+
+    private static void assertValues(Collection<String> expected, FeatureSet actual) {
+        List<String> tmp = new ArrayList<>(expected);
+        for (String value : actual.getValues()) {
+            assertNotNull(value, tmp.remove(value));
+        }
+        assertTrue(tmp.toString(), tmp.isEmpty());
+    }
+
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/NegationTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/NegationTest.java
new file mode 100644
index 00000000000..95666342152
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/NegationTest.java
@@ -0,0 +1,89 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotSame;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class NegationTest {
+
+    @Test
+    public void requireThatNegationIsAnOperator() {
+        assertTrue(PredicateOperator.class.isAssignableFrom(Negation.class));
+    }
+
+    @Test
+    public void requireThatAccessorsWork() {
+        Predicate foo = SimplePredicates.newString("foo");
+        Negation node = new Negation(foo);
+        assertSame(foo, node.getOperand());
+
+        Predicate bar = SimplePredicates.newString("bar");
+        node.setOperand(bar);
+        assertSame(bar, node.getOperand());
+    }
+
+    @Test
+    public void requireThatCloneIsImplemented() throws CloneNotSupportedException {
+        Negation node1 = new Negation(SimplePredicates.newString("a"));
+        Negation node2 = node1.clone();
+        assertEquals(node1, node2);
+        assertNotSame(node1, node2);
+        assertNotSame(node1.getOperand(), node2.getOperand());
+    }
+
+    @Test
+    public void requireThatHashCodeIsImplemented() {
+        Predicate predicate = SimplePredicates.newPredicate();
+        assertEquals(new Negation(predicate).hashCode(), new Negation(predicate).hashCode());
+    }
+
+    @Test
+    public void requireThatEqualsIsImplemented() {
+        Negation lhs = new Negation(SimplePredicates.newString("foo"));
+        assertTrue(lhs.equals(lhs));
+        assertFalse(lhs.equals(new Object()));
+
+        Negation rhs = new Negation(SimplePredicates.newString("bar"));
+        assertFalse(lhs.equals(rhs));
+        rhs.setOperand(SimplePredicates.newString("foo"));
+        assertTrue(lhs.equals(rhs));
+    }
+
+    @Test
+    public void requireThatChildIsMandatoryInConstructor() {
+        try {
+            new Negation(null);
+            fail();
+        } catch (NullPointerException e) {
+            assertEquals("operand", e.getMessage());
+        }
+    }
+
+    @Test
+    public void requireThatChildIsMandatoryInSetter() {
+        Predicate operand = SimplePredicates.newPredicate();
+        Negation negation = new Negation(operand);
+        try {
+            negation.setOperand(null);
+            fail();
+        } catch (NullPointerException e) {
+            assertEquals("operand", e.getMessage());
+        }
+        assertSame(operand, negation.getOperand());
+    }
+
+    @Test
+    public void requireThatChildIsIncludedInToString() {
+        assertEquals("not (foo)", new Negation(SimplePredicates.newString("foo")).toString());
+    }
+
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateHashTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateHashTest.java
new file mode 100644
index 00000000000..759bfe9f48f
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateHashTest.java
@@ -0,0 +1,102 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a>
+ */
+public class PredicateHashTest{
+    @Test
+    public void requireThatShortStringsGetsHashes() {
+        assertHashesTo(0x82af3d1de65ec252L, "abcdefg");
+        assertHashesTo(0xdc50d922fb0e91d6L, "雅虎");
+        assertHashesTo(0x709bd6ff1a84dc14L, "country=日本");
+        assertHashesTo(0x28e8de732ab0e809L, "foo");
+
+        assertHashesTo(0x8db63936938575bfL, "");
+        assertHashesTo(0x1d48fd74d88633acL, "a");
+        assertHashesTo(0xd30019bef51f4a75L, "ab");
+        assertHashesTo(0x9cb12e2bfea87243L, "abc");
+        assertHashesTo(0x207e64432ec23f4bL, "abcd");
+        assertHashesTo(0xbb1277971caf7a56L, "abcde");
+        assertHashesTo(0xfde595baae539176L, "abcdef");
+        assertHashesTo(0x82af3d1de65ec252L, "abcdefg");
+        assertHashesTo(0x1cac1cd5db905a5fL, "abcdefgh");
+        assertHashesTo(0x1ce1c26a201525deL, "abcdefghi");
+        assertHashesTo(0x2237a417a20c1025L, "abcdefghij");
+        assertHashesTo(0xd98f47421abc3754L, "abcdefghijk");
+        assertHashesTo(0xb974917101764d3aL, "abcdefghijkl");
+        assertHashesTo(0xde3b7ffe3e6dd61fL, "abcdefghijklm");
+        assertHashesTo(0x31d95fa68634f482L, "abcdefghijklmn");
+        assertHashesTo(0xde99d87fdbeca8faL, "abcdefghijklmn1");
+        assertHashesTo(0x0afc8571f275c392L, "abcdefghijklmn12");
+        assertHashesTo(0xbd00379443b0606cL, "abcdefghijklmn123");
+        assertHashesTo(0x855c704c68e095c5L, "abcdefghijklmn1234");
+        assertHashesTo(0xe9233cb6e4fad097L, "abcdefghijklmn12345");
+        assertHashesTo(0x1103ca46bd6e8d2fL, "abcdefghijklmn123456");
+        assertHashesTo(0x0c7097be717354d1L, "abcdefghijklmn1234567");
+        assertHashesTo(0x3e75293210127583L, "abcdefghijklmn12345678");
+        assertHashesTo(0xa66286e1294d8197L, "abcdefghijklmn123456789");
+        assertHashesTo(0x79fac97d13f4cc84L, "abcdefghijklmn1234567890");
+    }
+
+    @Test
+    public void requireThatLongStringsGetsHashes() {
+        assertHashesTo(0x79fac97d13f4cc84L, "abcdefghijklmn1234567890");
+        assertHashesTo(0xd7af1798f1d5de44L, "abcdefghijklmn1234567890a");
+        assertHashesTo(0x5a259ad887478cccL, "abcdefghijklmn1234567890ab");
+        assertHashesTo(0x4e8d95bab8d64191L, "abcdefghijklmn1234567890abc");
+        assertHashesTo(0xf63b94d31db2fe1aL, "abcdefghijklmn1234567890abcd");
+        assertHashesTo(0x47a1977d65709aceL, "abcdefghijklmn1234567890abcde");
+        assertHashesTo(0x52e1fb6d6aff3aeeL, "abcdefghijklmn1234567890abcdef");
+        assertHashesTo(0xc16de639b6e69ad3L, "abcdefghijklmn1234567890abcdefg");
+        assertHashesTo(0x87c22dd1e285dd6fL, "abcdefghijklmn1234567890abcdefgh");
+        assertHashesTo(0x775a3542d88b4972L, "abcdefghijklmn1234567890abcdefghi");
+        assertHashesTo(0x7b0c82116edf338bL, "abcdefghijklmn1234567890abcdefghij");
+        assertHashesTo(0x0fe73b58f6b23cb6L, "abcdefghijklmn1234567890abcdefghijk");
+        assertHashesTo(0x27ab8d02387e64e0L, "abcdefghijklmn1234567890abcdefghijkl");
+        assertHashesTo(0xdd161af20b41be04L, "abcdefghijklmn1234567890abcdefghijklm");
+        assertHashesTo(0x67739554f61fffcbL, "abcdefghijklmn1234567890abcdefghijklmn");
+        assertHashesTo(0xa765cc6be247dfb2L, "abcdefghijklmn1234567890abcdefghijklmn1");
+        assertHashesTo(0x9e201896cc600501L, "abcdefghijklmn1234567890abcdefghijklmn12");
+        assertHashesTo(0xfc5077792bfed491L, "abcdefghijklmn1234567890abcdefghijklmn123");
+        assertHashesTo(0x96a7acb73fd13601L, "abcdefghijklmn1234567890abcdefghijklmn1234");
+        assertHashesTo(0x45de4237e48a0ba8L, "abcdefghijklmn1234567890abcdefghijklmn12345");
+        assertHashesTo(0x3b65da96300e107eL, "abcdefghijklmn1234567890abcdefghijklmn123456");
+        assertHashesTo(0xbd95c3591ee587bdL, "abcdefghijklmn1234567890abcdefghijklmn1234567");
+        assertHashesTo(0x2688cb2d10e8629bL, "abcdefghijklmn1234567890abcdefghijklmn12345678");
+        assertHashesTo(0xcd383d98f9483ef0L, "abcdefghijklmn1234567890abcdefghijklmn123456789");
+        assertHashesTo(0x220e374268970e84L, "abcdefghijklmn1234567890abcdefghijklmn1234567890");
+        assertHashesTo(0xd50ef002ed96bf0bL, "abcdefghijklmn1234567890abcdefghijklmn1234567890a");
+        assertHashesTo(0x5ec9b42099bb25c6L, "abcdefghijklmn1234567890abcdefghijklmn1234567890ab");
+        assertHashesTo(0x05c603997a19dbceL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abc");
+        assertHashesTo(0xcee3fce2a3e38762L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcd");
+        assertHashesTo(0xc0d9791b19897f0aL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcde");
+        assertHashesTo(0xde98d0f8250ec703L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdef");
+        assertHashesTo(0xa7688d5834fa7d2aL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefg");
+        assertHashesTo(0xad514e8250667cdeL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefgh");
+        assertHashesTo(0xf562662deca536c3L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghi");
+        assertHashesTo(0x9d1b8d2463cde877L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghij");
+        assertHashesTo(0x24840f21eeb30861L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijk");
+        assertHashesTo(0x40af2a3f14d31fdaL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijkl");
+        assertHashesTo(0x3514ad5e964b5c73L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklm");
+        assertHashesTo(0x7bd6243490571844L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn");
+        assertHashesTo(0x273de93a3bddd9e8L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn1");
+        assertHashesTo(0x18e6850c3e2f85beL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn12");
+        assertHashesTo(0x044968ddc534d822L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn123");
+        assertHashesTo(0x7430d9d503fe624dL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn1234");
+        assertHashesTo(0xf0bb1e5239c1d88cL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn12345");
+        assertHashesTo(0x2ee1ab348b7deaa0L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn123456");
+        assertHashesTo(0x18b6da5df76680dfL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn1234567");
+        assertHashesTo(0x06c95ee4ddc93743L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn12345678");
+        assertHashesTo(0x6406e477d8ca608dL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn123456789");
+        assertHashesTo(0x203397a04178d470L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn1234567890");
+    }
+
+    private void assertHashesTo(long hash, String key) {
+        assertEquals(hash, PredicateHash.hash64(key));
+    }
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateOperatorTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateOperatorTest.java
new file mode 100644
index 00000000000..b6de0bf3514
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateOperatorTest.java
@@ -0,0 +1,17 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertTrue;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class PredicateOperatorTest {
+
+    @Test
+    public void requireThatOperatorIsAPredicate() {
+        assertTrue(Predicate.class.isAssignableFrom(PredicateOperator.class));
+    }
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateParserTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateParserTest.java
new file mode 100644
index 00000000000..ee161c20feb
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateParserTest.java
@@ -0,0 +1,155 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+/**
+ * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a>
+ */
+
+public class PredicateParserTest {
+
+    @Test
+    public void requireThatParseErrorThrowsException() {
+        try {
+            Predicate.fromString("a in b");
+            fail("Expected an exception");
+        } catch (IllegalArgumentException e) {
+            assertEquals("line 1:5 no viable alternative at input 'b'", e.getMessage());
+        }
+    }
+
+    @Test
+    public void requireThatLexerErrorThrowsException() {
+        try {
+            Predicate.fromString("a-b in [b]");
+            fail("Expected an exception");
+        } catch (IllegalArgumentException e) {
+            assertEquals("line 1:2 no viable alternative at character 'b'", e.getMessage());
+        }
+    }
+
+    @Test
+    public void requireThatSingleValueLeafNodesParse() {
+        assertParsesTo("a in [b]", "a in [b]");
+        assertParsesTo("0 in [1]", "0 in [1]");
+        assertParsesTo("in in [in]", "in in [in]");
+        assertParsesTo("and in [or]", "and in [or]");
+        assertParsesTo("not in [not]", "not in [not]");
+        assertParsesTo("'-234' in ['+200']", "'-234' in ['+200']");
+        assertParsesTo("string in ['!@#$%^&*()[]']", "'string' in ['!@#$%^&*()[]']");
+        assertParsesTo("a in [b]", "a in [b]");
+        assertParsesTo("string in ['foo\\\\_\"\\t\\n\\f\\rbar']",
+                       "string in ['foo\\\\_\\x22\\t\\n\\f\\rbar']");
+        assertParsesTo("'\\xC3\\xB8' in [b]", "'ø' in [b]");
+        assertParsesTo("'\\xEF\\xBF\\xBD' in [b]", "'\\xf8' in [b]");
+        assertParsesTo("'\\xEF\\xBF\\xBD' in [b]", "'\\xef\\xbf\\xbd' in ['b']");
+        assertParsesTo("'\\xE4\\xB8\\x9C\\xE8\\xA5\\xBF' in ['\\xE8\\x87\\xAA\\xE8\\xA1\\x8C\\xE8\\xBD\\xA6']",
+                       "'东西' in ['自行车']");
+        assertParsesTo("true in [false]", "true in [false]");
+    }
+
+    @Test
+    public void requireThatMultiValueLeafNodesParse() {
+        assertParsesTo("a in [b]", "a in [b]");
+        assertParsesTo("0 in [1]", "0 in [1]");
+        assertParsesTo("in in [and, in]", "in in [in, and]");
+        assertParsesTo("a in [b, c, d, e, f]", "'a' in ['b', 'c', 'd', 'e', 'f']");
+    }
+
+    @Test
+    public void requireThatBothSingleAndDoubleQuotesWork() {
+        assertParsesTo("a in [b]", "'a' in ['b']");
+        assertParsesTo("a in [b]", "\"a\" in [\"b\"]");
+        assertParsesTo("'a\\x27' in [b]", "'a\\'' in ['b']");
+        assertParsesTo("'a\"' in [b]", "\"a\\\"\" in [\"b\"]");
+    }
+
+    @Test
+    public void requireThatRangeLeafNodesParse() {
+        assertParsesTo("a in [0..100]", "a in [0..100]");
+        assertParsesTo("0 in [..100]", "0 in [..100]");
+        assertParsesTo("0 in [0..]", "0 in [0..]");
+        assertParsesTo("0 in [..]", "0 in [..]");
+        assertParsesTo("a in [-100..100]", "a in [-100..+100]");
+        assertParsesTo("a in [-9223372036854775808..9223372036854775807]",
+                "a in [-9223372036854775808..+9223372036854775807]");
+    }
+
+    @Test
+    public void requireThatRangePartitionsAreIgnored() {
+        assertParsesTo("a in [0..100]", "a in [0..100 (a=0-99,a=100+[..0])]");
+        assertParsesTo("a in [-100..0]", "a in [-100..0 (a=-0-99,a=-100+[..0])]");
+        assertParsesTo("a in [-9223372036854775808..0]", "a in [-9223372036854775808..0 (a=-0-9223372036854775808)]");
+        assertParsesTo("a in [2..8]", "a in [2..8 (a=0+[2..8])]");
+        assertParsesTo("a in [0..8]", "a in [0..8 (a=0+[..8])]");
+        assertParsesTo("a in [2..9]", "a in [2..9 (a=0+[2..])]");
+    }
+
+    @Test
+    public void requireThatNotInSetWorks() {
+        assertParsesTo("a not in [b]", "a not in [b]");
+    }
+
+    @Test
+    public void requireThatConjunctionWorks() {
+        assertParsesTo("a in [b] and c in [d]", "a in [b] and c in [d]");
+        assertParsesTo("a in [b] and c in [d] and e in [f]", "a in [b] and c in [d] and e in [f]");
+    }
+
+    @Test
+    public void requireThatDisjunctionWorks() {
+        assertParsesTo("a in [b] or c in [d]", "a in [b] or c in [d]");
+        assertParsesTo("a in [b] or c in [d] or e in [f]", "a in [b] or c in [d] or e in [f]");
+    }
+
+    @Test
+    public void requireThatParenthesesWorks() {
+        assertParsesTo("a in [b] or c in [d]",
+                       "(a in [b]) or (c in [d])");
+        assertParsesTo("a in [b] or c in [d] or e in [f]",
+                       "(((a in [b]) or c in [d]) or e in [f])");
+        assertParsesTo("(a in [b] and c in [d]) or e in [f]",
+                       "a in [b] and c in [d] or e in [f]");
+        assertParsesTo("a in [b] and (c in [d] or e in [f])",
+                       "a in [b] and (c in [d] or e in [f])");
+        assertParsesTo("a in [b] and (c in [d] or e in [f]) and g in [h]",
+                       "a in [b] and (c in [d] or e in [f]) and g in [h]");
+    }
+
+    @Test
+    public void requireThatNotOutsideParenthesesWorks() {
+        assertParsesTo("a not in [b]", "not (a in [b])");
+    }
+
+    @Test
+    public void requireThatConjunctionsCanGetMoreThanTwoChildren() {
+        Predicate p = Predicate.fromString("a in [b] and c in [d] and e in [f] and g in [h]");
+        assertTrue(p instanceof Conjunction);
+        assertEquals(4, ((Conjunction)p).getOperands().size());
+    }
+
+    @Test
+    public void requireThatDisjunctionsCanGetMoreThanTwoChildren() {
+        Predicate p = Predicate.fromString("a in [b] or c in [d] or e in [f] or g in [h]");
+        assertTrue(p instanceof Disjunction);
+        assertEquals(4, ((Disjunction)p).getOperands().size());
+    }
+
+    @Test
+    public void requireThatBooleanCanBeParsed() {
+        assertParsesTo("true", "true");
+        assertParsesTo("false", "false");
+        assertParsesTo("true or false", "true or false");
+        assertParsesTo("false and true", "false and true");
+    }
+
+    private static void assertParsesTo(String expected, String predicate_str) {
+        assertEquals(expected, // TODO: Predicate.fromString(expected)
+                     Predicate.fromString(predicate_str).toString());
+    }
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateTest.java
new file mode 100644
index 00000000000..621378f394b
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateTest.java
@@ -0,0 +1,110 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import static com.yahoo.document.predicate.Predicates.and;
+import static com.yahoo.document.predicate.Predicates.feature;
+import static com.yahoo.document.predicate.Predicates.not;
+import static com.yahoo.document.predicate.Predicates.or;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class PredicateTest {
+
+    @Test
+    public void requireThatPredicateIsCloneable() {
+        assertTrue(Cloneable.class.isAssignableFrom(Predicate.class));
+    }
+
+    @Test
+    public void requireThatANDConstructsAConjunction() {
+        Predicate foo = SimplePredicates.newString("foo");
+        Predicate bar = SimplePredicates.newString("bar");
+        Predicate predicate = and(foo, bar);
+        assertEquals(Conjunction.class, predicate.getClass());
+        assertEquals(new Conjunction(foo, bar), predicate);
+    }
+
+    @Test
+    public void requireThatORConstructsADisjunction() {
+        Predicate foo = SimplePredicates.newString("foo");
+        Predicate bar = SimplePredicates.newString("bar");
+        Predicate predicate = or(foo, bar);
+        assertEquals(Disjunction.class, predicate.getClass());
+        assertEquals(new Disjunction(foo, bar), predicate);
+    }
+
+    @Test
+    public void requireThatNOTConstructsANegation() {
+        Predicate foo = SimplePredicates.newString("foo");
+        Predicate predicate = not(foo);
+        assertEquals(Negation.class, predicate.getClass());
+        assertEquals(new Negation(foo), predicate);
+    }
+
+    @Test
+    public void requireThatFeatureBuilderCanConstructFeatureRange() {
+        assertEquals(new FeatureRange("key", 6L, 9L),
+                     feature("key").inRange(6, 9));
+        assertEquals(new Negation(new FeatureRange("key", 6L, 9L)),
+                     feature("key").notInRange(6, 9));
+        assertEquals(new FeatureRange("key", 7L, null),
+                     feature("key").greaterThan(6));
+        assertEquals(new FeatureRange("key", 6L, null),
+                     feature("key").greaterThanOrEqualTo(6));
+        assertEquals(new FeatureRange("key", null, 5L),
+                     feature("key").lessThan(6));
+        assertEquals(new FeatureRange("key", null, 9L),
+                     feature("key").lessThanOrEqualTo(9));
+    }
+
+    @Test
+    public void requireThatFeatureBuilderCanConstructFeatureSet() {
+        assertEquals(new FeatureSet("key", "valueA", "valueB"),
+                     feature("key").inSet("valueA", "valueB"));
+        assertEquals(new Negation(new FeatureSet("key", "valueA", "valueB")),
+                     feature("key").notInSet("valueA", "valueB"));
+    }
+
+    @Test
+    public void requireThatPredicatesCanBeConstructedUsingConstructors() {
+        assertEquals("country in [no, se] and age in [20..30]",
+                     new Conjunction(new FeatureSet("country", "no", "se"),
+                                     new FeatureRange("age", 20L, 30L)).toString());
+        assertEquals("country not in [no, se] or age in [20..] or height in [..160]",
+                     new Disjunction(new Negation(new FeatureSet("country", "no", "se")),
+                                     new FeatureRange("age", 20L, null),
+                                     new FeatureRange("height", null, 160L)).toString());
+    }
+
+    @Test
+    public void requireThatPredicatesCanBeBuiltUsingChainedMethodCalls() {
+        assertEquals("country not in [no, se] or age in [20..] or height in [..160]",
+                     new Disjunction()
+                             .addOperand(new Negation(new FeatureSet("country").addValue("no").addValue("se")))
+                             .addOperand(new FeatureRange("age").setFromInclusive(20L))
+                             .addOperand(new FeatureRange("height").setToInclusive(160L))
+                             .toString());
+    }
+
+    @Test
+    public void requireThatPredicatesCanBeBuiltUsingSeparateMethodCalls() {
+        Conjunction conjunction = new Conjunction();
+        FeatureSet countrySet = new FeatureSet("country");
+        countrySet.addValue("no");
+        countrySet.addValue("se");
+        conjunction.addOperand(countrySet);
+        FeatureRange ageRange = new FeatureRange("age");
+        ageRange.setFromInclusive(20L);
+        conjunction.addOperand(ageRange);
+        FeatureRange heightRange = new FeatureRange("height");
+        heightRange.setToInclusive(160L);
+        conjunction.addOperand(heightRange);
+        assertEquals("country in [no, se] and age in [20..] and height in [..160]",
+                     conjunction.toString());
+    }
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateValueTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateValueTest.java
new file mode 100644
index 00000000000..810e9a8717c
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateValueTest.java
@@ -0,0 +1,17 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertTrue;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class PredicateValueTest {
+
+    @Test
+    public void requireThatValueIsAPredicate() {
+        assertTrue(Predicate.class.isAssignableFrom(PredicateValue.class));
+    }
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicatesTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicatesTest.java
new file mode 100644
index 00000000000..22832eedeff
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicatesTest.java
@@ -0,0 +1,38 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import static com.yahoo.document.predicate.Predicates.and;
+import static com.yahoo.document.predicate.Predicates.feature;
+import static com.yahoo.document.predicate.Predicates.not;
+import static com.yahoo.document.predicate.Predicates.or;
+import static com.yahoo.document.predicate.Predicates.value;
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a>
+ */
+public class PredicatesTest {
+
+    @Test
+    public void requireThatApiIsUsable() {
+        assertEquals(
+                new Disjunction(
+                        new Conjunction(new FeatureSet("country", "de", "no"),
+                                        new Negation(new FeatureSet("gender", "female")),
+                                        new FeatureRange("age", 6L, 9L)),
+                        new Conjunction(new Negation(new FeatureSet("country", "se")),
+                                        new FeatureSet("gender", "female"),
+                                        new FeatureRange("age", 69L, null))),
+                or(and(feature("country").inSet("de", "no"),
+                       feature("gender").notInSet("female"),
+                       feature("age").inRange(6, 9)),
+                   and(not(feature("country").inSet("se")),
+                       feature("gender").inSet("female"),
+                       feature("age").greaterThanOrEqualTo(69))));
+
+        assertEquals(new BooleanPredicate(true), value(true));
+        assertEquals(new BooleanPredicate(false), value(false));
+    }
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/RangeEdgePartitionTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/RangeEdgePartitionTest.java
new file mode 100644
index 00000000000..d9f6714d8c8
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/RangeEdgePartitionTest.java
@@ -0,0 +1,62 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import static org.junit.Assert.*;
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a>
+ */
+public class RangeEdgePartitionTest {
+
+    @Test
+    public void requireThatRangeEdgePartitionIsAValue() {
+        assertTrue(PredicateValue.class.isAssignableFrom(RangeEdgePartition.class));
+    }
+
+    @Test
+    public void requireThatConstructorsWork() {
+        RangeEdgePartition part = new RangeEdgePartition("foo=10", 10, 0, -1);
+        assertEquals("foo=10", part.getLabel());
+        assertEquals(0, part.getLowerBound());
+        assertEquals(-1, part.getUpperBound());
+    }
+
+    @Test
+    public void requireThatCloneIsImplemented() throws CloneNotSupportedException {
+        RangeEdgePartition node1 = new RangeEdgePartition("foo=10", 10, 0, 0);
+        RangeEdgePartition node2 = node1.clone();
+        assertEquals(node1, node2);
+        assertNotSame(node1, node2);
+    }
+
+    @Test
+    public void requireThatHashCodeIsImplemented() {
+        assertEquals(new RangeEdgePartition("foo=-10", 10, 2, 3).hashCode(),
+                new RangeEdgePartition("foo=-10", 10, 2, 3).hashCode());
+    }
+
+    @Test
+    public void requireThatEqualsIsImplemented() {
+        RangeEdgePartition lhs = new RangeEdgePartition("foo=10", 10, 5, 10);
+        assertTrue(lhs.equals(lhs));
+        assertFalse(lhs.equals(new Object()));
+
+        RangeEdgePartition rhs = new RangeEdgePartition("foo=20", 20, 0, 0);
+        assertFalse(lhs.equals(rhs));
+        rhs = new RangeEdgePartition("foo=10", 10, 5, 10);
+        assertTrue(lhs.equals(rhs));
+        assertFalse(lhs.equals(new RangeEdgePartition("foo=10", 10, 5, 11)));
+        assertFalse(lhs.equals(new RangeEdgePartition("foo=10", 10, 6, 10)));
+        assertFalse(lhs.equals(new RangeEdgePartition("foo=10", 11, 5, 10)));
+        assertFalse(lhs.equals(new RangeEdgePartition("foo=11", 10, 5, 10)));
+    }
+
+    @Test
+    public void requireThatKeyIsEscapedInToString() {
+        assertEquals("foo=10+[2..3]", new RangeEdgePartition("foo=10", 10, 2, 3).toString());
+        assertEquals("'\\foo=10'+[2..3]", new RangeEdgePartition("\foo=10", 10, 2, 3).toString());
+        assertEquals("'\\x27foo\\x27=10'+[2..3]", new RangeEdgePartition("'foo'=10", 10, 2, 3).toString());
+    }}
diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/RangePartitionTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/RangePartitionTest.java
new file mode 100644
index 00000000000..b9d2c865e9b
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/RangePartitionTest.java
@@ -0,0 +1,60 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.document.predicate;
+
+import org.junit.Test;
+
+import static org.junit.Assert.*;
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a>
+ */
+public class RangePartitionTest {
+
+    @Test
+    public void requireThatRangePartitionIsAValue() {
+        assertTrue(PredicateValue.class.isAssignableFrom(RangePartition.class));
+    }
+
+    @Test
+    public void requireThatConstructorsWork() {
+        RangePartition part = new RangePartition("foo=10-19");
+        assertEquals("foo=10-19", part.getLabel());
+        part = new RangePartition("foo", 10, 19, false);
+        assertEquals("foo=10-19", part.getLabel());
+        part = new RangePartition("foo", 10, 19, true);
+        assertEquals("foo=-19-10", part.getLabel());
+    }
+
+    @Test
+    public void requireThatCloneIsImplemented() throws CloneNotSupportedException {
+        RangePartition node1 = new RangePartition("foo=300-399");
+        RangePartition node2 = node1.clone();
+        assertEquals(node1, node2);
+        assertNotSame(node1, node2);
+    }
+
+    @Test
+    public void requireThatHashCodeIsImplemented() {
+        assertEquals(new RangePartition("foo=0-9").hashCode(), new RangePartition("foo=0-9").hashCode());
+    }
+
+    @Test
+    public void requireThatEqualsIsImplemented() {
+        RangePartition lhs = new RangePartition("foo=10-19");
+        assertTrue(lhs.equals(lhs));
+        assertFalse(lhs.equals(new Object()));
+
+        RangePartition rhs = new RangePartition("bar=1000-1999");
+        assertFalse(lhs.equals(rhs));
+        rhs = new RangePartition("foo=10-19");
+        assertTrue(lhs.equals(rhs));
+    }
+
+    @Test
+    public void requireThatKeyIsEscapedInToString() {
+        assertEquals("foo=10-19", new RangePartition("foo=10-19").toString());
+        assertEquals("'\\foo=10-19'", new RangePartition("\foo=10-19").toString());
+        assertEquals("'\\x27foo\\x27=10-19'", new RangePartition("'foo'=10-19").toString());
+    }
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/search/predicate/PredicateQueryParserTest.java b/predicate-search-core/src/test/java/com/yahoo/search/predicate/PredicateQueryParserTest.java
new file mode 100644
index 00000000000..dcee3a0c55d
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/search/predicate/PredicateQueryParserTest.java
@@ -0,0 +1,43 @@
+// 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 org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+import static org.hamcrest.CoreMatchers.is;
+import static org.junit.Assert.assertThat;
+
+/**
+ * @author bjorncs
+ */
+public class PredicateQueryParserTest {
+
+    @Test
+    public void require_that_json_is_correctly_parsed() {
+        String json =
+                "{" +
+                "   \"features\":[" +
+                "       {\"k\":\"k1\",\"v\":\"value1\",\"s\":\"0x1\"}," +
+                "       {\"k\":\"k2\",\"v\":\"value2\",\"s\":\"0x3\"}" +
+                "   ],\"rangeFeatures\":[" +
+                "       {\"k\":\"range1\",\"v\":123456789123,\"s\":\"0xffff\"}," +
+                "       {\"k\":\"range2\",\"v\":0,\"s\":\"0xffffffffffffffff\"}" +
+                "   ]" +
+                "}";
+
+        PredicateQueryParser parser = new PredicateQueryParser();
+        List<String> result = new ArrayList<>();
+        parser.parseJsonQuery(
+                json,
+                (k, v, s) -> result.add(String.format("%s:%s:%#x", k, v, s)),
+                (k, v, s) -> result.add(String.format("%s:%d:%#x", k, v, s)));
+
+        assertThat(result, is(Arrays.asList(
+                "k1:value1:0x1", "k2:value2:0x3",
+                "range1:123456789123:0xffff", "range2:0:0xffffffffffffffff")));
+    }
+
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/AndOrSimplifierTest.java b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/AndOrSimplifierTest.java
new file mode 100644
index 00000000000..4ec6c496e73
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/AndOrSimplifierTest.java
@@ -0,0 +1,134 @@
+// 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;
+import org.junit.Test;
+
+import static com.yahoo.document.predicate.Predicates.and;
+import static com.yahoo.document.predicate.Predicates.feature;
+import static com.yahoo.document.predicate.Predicates.not;
+import static com.yahoo.document.predicate.Predicates.or;
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a>
+ */
+public class AndOrSimplifierTest {
+
+    @Test
+    public void requireThatNestedConjunctionsAreCollapsed() {
+        assertSimplified(and(feature("a").inSet("b"),
+                             feature("c").inSet("d")),
+                         and(and(feature("a").inSet("b"),
+                                 feature("c").inSet("d"))));
+    }
+
+    @Test
+    public void requireThatNestedConjuctionsAreCollapsedInPlace() {
+        assertSimplified(and(feature("a").inSet("b"),
+                             feature("c").inSet("d"),
+                             feature("e").inSet("f")),
+                         and(feature("a").inSet("b"),
+                             and(feature("c").inSet("d")),
+                             feature("e").inSet("f")));
+    }
+
+    @Test
+    public void requireThatDeeplyNestedConjunctionsAreCollapsed() {
+        assertSimplified(and(feature("a").inSet("b"),
+                             feature("c").inSet("d"),
+                             feature("e").inSet("f"),
+                             feature("g").inSet("h"),
+                             feature("i").inSet("j")),
+                         and(feature("a").inSet("b"),
+                             and(feature("c").inSet("d")),
+                             feature("e").inSet("f"),
+                             and(and(feature("g").inSet("h"),
+                                     feature("i").inSet("j")))));
+    }
+
+    @Test
+    public void requireThatNestedDisjunctionsAreCollapsed() {
+        assertSimplified(or(feature("a").inSet("b"),
+                            feature("c").inSet("d")),
+                         or(or(feature("a").inSet("b"),
+                               feature("c").inSet("d"))));
+    }
+
+    @Test
+    public void requireThatNestedDisjuctionsAreCollapsedInPlace() {
+        assertSimplified(or(feature("a").inSet("b"),
+                            feature("c").inSet("d"),
+                            feature("e").inSet("f")),
+                         or(feature("a").inSet("b"),
+                            or(feature("c").inSet("d")),
+                            feature("e").inSet("f")));
+    }
+
+    @Test
+    public void requireThatDeeplyNestedDisjunctionsAreCollapsed() {
+        assertSimplified(or(feature("a").inSet("b"),
+                            feature("c").inSet("d"),
+                            feature("e").inSet("f"),
+                            feature("g").inSet("h"),
+                            feature("i").inSet("j")),
+                         or(feature("a").inSet("b"),
+                            or(feature("c").inSet("d")),
+                            feature("e").inSet("f"),
+                            or(or(feature("g").inSet("h"),
+                                  feature("i").inSet("j")))));
+    }
+
+    @Test
+    public void requireThatConjunctionsAndDisjunctionsAreNotCollapsed() {
+        assertSimplified(and(or(feature("a").inSet("b"),
+                                feature("c").inSet("d"))),
+                         and(or(feature("a").inSet("b"),
+                                feature("c").inSet("d"))));
+    }
+
+    @Test
+    public void requireThatNotOrIsTranslatedToAndNot() {
+        assertSimplified(
+                and(feature("a").notInSet("b"), feature("c").inSet("d")),
+                not(or(feature("a").inSet("b"), feature("c").notInSet("d"))));
+    }
+
+    @Test
+    public void requireThatNotAndIsTranslatedToOrNot() {
+        assertSimplified(
+                or(feature("a").notInSet("b"), feature("c").inSet("d")),
+                not(and(feature("a").inSet("b"), feature("c").notInSet("d"))));
+    }
+
+    @Test
+    public void requireThatTreeWithoutNotIsNotAffected() {
+        assertSimplified(
+                and(feature("a").inSet("b"), feature("c").notInSet("d")),
+                and(feature("a").inSet("b"), feature("c").notInSet("d")));
+        assertSimplified(
+                or(feature("a").inSet("b"), feature("c").notInSet("d")),
+                or(feature("a").inSet("b"), feature("c").notInSet("d")));
+        assertSimplified(feature("a").inSet("b"), feature("a").inSet("b"));
+    }
+
+    @Test
+    public void requireThatNotOfNotIsRemoved() {
+        assertSimplified(feature("a").inSet("b"), not(not(feature("a").inSet("b"))));
+        assertSimplified(feature("a").inSet("b"), not(feature("a").notInSet("b")));
+        assertSimplified(feature("a").notInSet("b"), not(not(feature("a").notInSet("b"))));
+    }
+
+    @Test
+    public void requireThatNotBeneathAndIsTranslated() {
+        assertSimplified(
+                and(feature("a").notInSet("b"), feature("c").inSet("d"), feature("b").inSet("c")),
+                and(not(or(feature("a").inSet("b"), feature("c").notInSet("d"))), feature("b").inSet("c")));
+    }
+
+    private static void assertSimplified(Predicate expected, Predicate input) {
+        AndOrSimplifier simplifier = new AndOrSimplifier();
+        Predicate actual = simplifier.process(input, new PredicateOptions(10));
+        assertEquals(expected, actual);
+    }
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/BooleanSimplifierTest.java b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/BooleanSimplifierTest.java
new file mode 100644
index 00000000000..37d2352df57
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/BooleanSimplifierTest.java
@@ -0,0 +1,60 @@
+// 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;
+import org.junit.Test;
+
+import static com.yahoo.document.predicate.Predicates.*;
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a>
+ */
+public class BooleanSimplifierTest {
+
+    @Test
+    public void requireThatOrOfTrueIsTrue() {
+        assertSimplifiedTo(value(true), or(feature("a").inSet("b"), value(true)));
+    }
+
+    @Test
+    public void requireThatFalseChildrenOfOrAreRemoved() {
+        assertSimplifiedTo(feature("a").inSet("b"), or(feature("a").inSet("b"), value(false)));
+    }
+
+    @Test
+    public void requireThatAndOfFalseIsFalse() {
+        assertSimplifiedTo(value(false), and(feature("a").inSet("b"), value(false)));
+    }
+
+    @Test
+    public void requireThatTrueChildrenOfAndAreRemoved() {
+        assertSimplifiedTo(feature("a").inSet("b"), and(feature("a").inSet("b"), value(true)));
+    }
+
+    @Test
+    public void requireThatSingleChildAndOrAreRemoved() {
+        assertSimplifiedTo(feature("a").inSet("b"), and(or(and(feature("a").inSet("b")))));
+    }
+
+    @Test
+    public void requireThatValueChildrenOfNotAreInverted() {
+        assertSimplifiedTo(value(true), not(value(false)));
+        assertSimplifiedTo(value(false), not(value(true)));
+        assertSimplifiedTo(value(true), not(not(not(value(false)))));
+        assertSimplifiedTo(value(true), not(not(not(and(feature("a").inSet("b"), value(false))))));
+    }
+
+    @Test
+    public void requireThatComplexExpressionIsSimplified() {
+        assertSimplifiedTo(
+                Predicate.fromString("'pub_entity' not in [301951]"),
+                Predicate.fromString("true and true and true and true and true and 'pub_entity' not in [301951] and ((true and true and true and true) or (true and true and true and true) or (true and true and true and true and 'pub_entity' in [86271]))"));
+    }
+
+    private void assertSimplifiedTo(Predicate expected, Predicate input) {
+        BooleanSimplifier simplifier = new BooleanSimplifier();
+        Predicate actual = simplifier.process(input, new PredicateOptions(10));
+        assertEquals(expected, actual);
+    }
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/ComplexNodeTransformerTest.java b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/ComplexNodeTransformerTest.java
new file mode 100644
index 00000000000..45cdabfb4f2
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/ComplexNodeTransformerTest.java
@@ -0,0 +1,604 @@
+// 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.RangePartition;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a>
+ */
+public class ComplexNodeTransformerTest {
+
+    private long lowerBound = 0x8000000000000000L;
+    private long upperBound = 0x7fffffffffffffffL;
+
+    private void testConvert(String predicate, String expected) {
+        int defaultArity = 10;
+        testConvert(predicate, expected, defaultArity);
+    }
+
+    private void testConvert(String predicate, String expected, int arity) {
+        Predicate p = Predicate.fromString(predicate);
+        ComplexNodeTransformer transformer = new ComplexNodeTransformer();
+        Predicate converted = transformer.process(p, new PredicateOptions(arity, lowerBound, upperBound));
+        assertEquals(expected, converted.toString());
+    }
+
+    @Test
+    public void requireThatSingleValueRangesAreConverted() {
+        testConvert("foo in [0..0]", "foo in [0..0 (foo=0+[..0])]");
+        testConvert("foo in [5..5]", "foo in [5..5 (foo=0+[5..5])]");
+        testConvert("foo in [9..9]", "foo in [9..9 (foo=0+[9..])]");
+        testConvert("foo in [10..10]", "foo in [10..10 (foo=10+[..0])]");
+        testConvert("foo in [-5..-5]", "foo in [-5..-5 (foo=-0+[5..5])]");
+        testConvert("foo in [-9..-9]", "foo in [-9..-9 (foo=-0+[9..])]");
+        testConvert("foo in [-10..-10]", "foo in [-10..-10 (foo=-10+[..0])]");
+    }
+
+    @Test
+    public void requireThatVeryShortRangesAreConverted() {
+        testConvert("foo in [10..17]", "foo in [10..17 (foo=10+[..7])]");
+        testConvert("foo in [12..19]", "foo in [12..19 (foo=10+[2..])]");
+        testConvert("foo in [11..18]", "foo in [11..18 (foo=10+[1..8])]");
+        testConvert("foo in [7..13]", "foo in [7..13 (foo=0+[7..],foo=10+[..3])]");
+        testConvert("foo in [-17..-10]", "foo in [-17..-10 (foo=-10+[..7])]");
+        testConvert("foo in [-19..-12]", "foo in [-19..-12 (foo=-10+[2..])]");
+        testConvert("foo in [-18..-11]", "foo in [-18..-11 (foo=-10+[1..8])]");
+        testConvert("foo in [-13..-7]", "foo in [-13..-7 (foo=-0+[7..],foo=-10+[..3])]");
+        testConvert("foo in [-5..4]", "foo in [-5..4 (foo=-0+[..5],foo=0+[..4])]");
+    }
+
+    @Test
+    public void requireThatShortRangeIsConverted() {
+        testConvert("foo in [9..19]", "foo in [9..19 (foo=0+[9..],foo=10-19)]");
+        testConvert("foo in [10..19]", "foo in [10..19 (foo=10-19)]");
+        testConvert("foo in [10..20]", "foo in [10..20 (foo=20+[..0],foo=10-19)]");
+        testConvert("foo in [12..21]", "foo in [12..21 (foo=10+[2..],foo=20+[..1])]");
+        testConvert("foo in [-19..-9]", "foo in [-19..-9 (foo=-0+[9..],foo=-19-10)]");
+        testConvert("foo in [-19..-10]", "foo in [-19..-10 (foo=-19-10)]");
+        testConvert("foo in [-20..-10]", "foo in [-20..-10 (foo=-20+[..0],foo=-19-10)]");
+        testConvert("foo in [-21..-12]", "foo in [-21..-12 (foo=-10+[2..],foo=-20+[..1])]");
+        testConvert("foo in [-9..9]", "foo in [-9..9 (foo=-9-0,foo=0-9)]");
+        testConvert("foo in [-10..10]", "foo in [-10..10 (foo=-10+[..0],foo=10+[..0],foo=-9-0,foo=0-9)]");
+    }
+
+    @Test
+    public void requireThatMediumRangeIsConverted() {
+        testConvert("foo in [10..39]", "foo in [10..39 (foo=10-19,foo=20-29,foo=30-39)]");
+        testConvert("foo in [10..38]", "foo in [10..38 (foo=30+[..8],foo=10-19,foo=20-29)]");
+        testConvert("foo in [18..39]", "foo in [18..39 (foo=10+[8..],foo=20-29,foo=30-39)]");
+        testConvert("foo in [8..38]", "foo in [8..38 (foo=0+[8..],foo=30+[..8],foo=10-19,foo=20-29)]");
+        testConvert("foo in [-39..-10]", "foo in [-39..-10 (foo=-19-10,foo=-29-20,foo=-39-30)]");
+        testConvert("foo in [-38..-10]", "foo in [-38..-10 (foo=-30+[..8],foo=-19-10,foo=-29-20)]");
+        testConvert("foo in [-39..-18]", "foo in [-39..-18 (foo=-10+[8..],foo=-29-20,foo=-39-30)]");
+        testConvert("foo in [-38..-8]", "foo in [-38..-8 (foo=-0+[8..],foo=-30+[..8],foo=-19-10,foo=-29-20)]");
+        testConvert("foo in [-19..19]", "foo in [-19..19 (foo=-9-0,foo=-19-10,foo=0-9,foo=10-19)]");
+    }
+
+    @Test
+    public void requireThatLargeRangeIsConverted() {
+        testConvert("foo in [10..199]", "foo in [10..199 (foo=10-19,foo=20-29,foo=30-39,foo=40-49,foo=50-59,foo=60-69,foo=70-79,foo=80-89,foo=90-99,foo=100-199)]");
+        testConvert("foo in [8..207]", "foo in [8..207 (foo=0+[8..],foo=200+[..7],foo=10-19,foo=20-29,foo=30-39,foo=40-49,foo=50-59,foo=60-69,foo=70-79,foo=80-89,foo=90-99,foo=100-199)]");
+        testConvert("foo in [999..2001]", "foo in [999..2001 (foo=990+[9..],foo=2000+[..1],foo=1000-1999)]");
+        testConvert("foo in [999..2009]", "foo in [999..2009 (foo=990+[9..],foo=2000-2009,foo=1000-1999)]");
+        testConvert("foo in [999..2099]", "foo in [999..2099 (foo=990+[9..],foo=2000-2099,foo=1000-1999)]");
+        testConvert("foo in [999..2999]", "foo in [999..2999 (foo=990+[9..],foo=1000-1999,foo=2000-2999)]");
+        testConvert("foo in [-199..-10]", "foo in [-199..-10 (foo=-19-10,foo=-29-20,foo=-39-30,foo=-49-40,foo=-59-50,foo=-69-60,foo=-79-70,foo=-89-80,foo=-99-90,foo=-199-100)]");
+        testConvert("foo in [-207..-8]", "foo in [-207..-8 (foo=-0+[8..],foo=-200+[..7],foo=-19-10,foo=-29-20,foo=-39-30,foo=-49-40,foo=-59-50,foo=-69-60,foo=-79-70,foo=-89-80,foo=-99-90,foo=-199-100)]");
+        testConvert("foo in [-2001..-999]", "foo in [-2001..-999 (foo=-990+[9..],foo=-2000+[..1],foo=-1999-1000)]");
+        testConvert("foo in [-999..999]", "foo in [-999..999 (foo=-999-0,foo=0-999)]");
+    }
+
+    @Test
+    public void requireThatLongMaxIsConverted() {
+        testConvert("foo in [0..9223372036854775807]",
+                "foo in [0..9223372036854775807 (" +
+                        "foo=9223372036854775800+[..7]," +
+                        "foo=9223372036854775000-9223372036854775099," +
+                        "foo=9223372036854775100-9223372036854775199," +
+                        "foo=9223372036854775200-9223372036854775299," +
+                        "foo=9223372036854775300-9223372036854775399," +
+                        "foo=9223372036854775400-9223372036854775499," +
+                        "foo=9223372036854775500-9223372036854775599," +
+                        "foo=9223372036854775600-9223372036854775699," +
+                        "foo=9223372036854775700-9223372036854775799," +
+                        "foo=9223372036854770000-9223372036854770999," +
+                        "foo=9223372036854771000-9223372036854771999," +
+                        "foo=9223372036854772000-9223372036854772999," +
+                        "foo=9223372036854773000-9223372036854773999," +
+                        "foo=9223372036854774000-9223372036854774999," +
+                        "foo=9223372036854700000-9223372036854709999," +
+                        "foo=9223372036854710000-9223372036854719999," +
+                        "foo=9223372036854720000-9223372036854729999," +
+                        "foo=9223372036854730000-9223372036854739999," +
+                        "foo=9223372036854740000-9223372036854749999," +
+                        "foo=9223372036854750000-9223372036854759999," +
+                        "foo=9223372036854760000-9223372036854769999," +
+                        "foo=9223372036854000000-9223372036854099999," +
+                        "foo=9223372036854100000-9223372036854199999," +
+                        "foo=9223372036854200000-9223372036854299999," +
+                        "foo=9223372036854300000-9223372036854399999," +
+                        "foo=9223372036854400000-9223372036854499999," +
+                        "foo=9223372036854500000-9223372036854599999," +
+                        "foo=9223372036854600000-9223372036854699999," +
+                        "foo=9223372036850000000-9223372036850999999," +
+                        "foo=9223372036851000000-9223372036851999999," +
+                        "foo=9223372036852000000-9223372036852999999," +
+                        "foo=9223372036853000000-9223372036853999999," +
+                        "foo=9223372036800000000-9223372036809999999," +
+                        "foo=9223372036810000000-9223372036819999999," +
+                        "foo=9223372036820000000-9223372036829999999," +
+                        "foo=9223372036830000000-9223372036839999999," +
+                        "foo=9223372036840000000-9223372036849999999," +
+                        "foo=9223372036000000000-9223372036099999999," +
+                        "foo=9223372036100000000-9223372036199999999," +
+                        "foo=9223372036200000000-9223372036299999999," +
+                        "foo=9223372036300000000-9223372036399999999," +
+                        "foo=9223372036400000000-9223372036499999999," +
+                        "foo=9223372036500000000-9223372036599999999," +
+                        "foo=9223372036600000000-9223372036699999999," +
+                        "foo=9223372036700000000-9223372036799999999," +
+                        "foo=9223372030000000000-9223372030999999999," +
+                        "foo=9223372031000000000-9223372031999999999," +
+                        "foo=9223372032000000000-9223372032999999999," +
+                        "foo=9223372033000000000-9223372033999999999," +
+                        "foo=9223372034000000000-9223372034999999999," +
+                        "foo=9223372035000000000-9223372035999999999," +
+                        "foo=9223372000000000000-9223372009999999999," +
+                        "foo=9223372010000000000-9223372019999999999," +
+                        "foo=9223372020000000000-9223372029999999999," +
+                        "foo=9223370000000000000-9223370999999999999," +
+                        "foo=9223371000000000000-9223371999999999999," +
+                        "foo=9223300000000000000-9223309999999999999," +
+                        "foo=9223310000000000000-9223319999999999999," +
+                        "foo=9223320000000000000-9223329999999999999," +
+                        "foo=9223330000000000000-9223339999999999999," +
+                        "foo=9223340000000000000-9223349999999999999," +
+                        "foo=9223350000000000000-9223359999999999999," +
+                        "foo=9223360000000000000-9223369999999999999," +
+                        "foo=9223000000000000000-9223099999999999999," +
+                        "foo=9223100000000000000-9223199999999999999," +
+                        "foo=9223200000000000000-9223299999999999999," +
+                        "foo=9220000000000000000-9220999999999999999," +
+                        "foo=9221000000000000000-9221999999999999999," +
+                        "foo=9222000000000000000-9222999999999999999," +
+                        "foo=9200000000000000000-9209999999999999999," +
+                        "foo=9210000000000000000-9219999999999999999," +
+                        "foo=9000000000000000000-9099999999999999999," +
+                        "foo=9100000000000000000-9199999999999999999," +
+                        "foo=0-999999999999999999," +
+                        "foo=1000000000000000000-1999999999999999999," +
+                        "foo=2000000000000000000-2999999999999999999," +
+                        "foo=3000000000000000000-3999999999999999999," +
+                        "foo=4000000000000000000-4999999999999999999," +
+                        "foo=5000000000000000000-5999999999999999999," +
+                        "foo=6000000000000000000-6999999999999999999," +
+                        "foo=7000000000000000000-7999999999999999999," +
+                        "foo=8000000000000000000-8999999999999999999)]");
+
+        testConvert("foo in [9223372036854775807..9223372036854775807]", "foo in [9223372036854775807..9223372036854775807 (foo=9223372036854775800+[7..7])]");
+    }
+
+    @Test
+    public void requireThatLongMinIsConverted() {
+        testConvert("foo in [-9223372036854775808..-1]",
+                "foo in [-9223372036854775808..-1 (" +
+                        "foo=-9223372036854775800+[..8]," +
+                        "foo=-9223372036854775099-9223372036854775000," +
+                        "foo=-9223372036854775199-9223372036854775100," +
+                        "foo=-9223372036854775299-9223372036854775200," +
+                        "foo=-9223372036854775399-9223372036854775300," +
+                        "foo=-9223372036854775499-9223372036854775400," +
+                        "foo=-9223372036854775599-9223372036854775500," +
+                        "foo=-9223372036854775699-9223372036854775600," +
+                        "foo=-9223372036854775799-9223372036854775700," +
+                        "foo=-9223372036854770999-9223372036854770000," +
+                        "foo=-9223372036854771999-9223372036854771000," +
+                        "foo=-9223372036854772999-9223372036854772000," +
+                        "foo=-9223372036854773999-9223372036854773000," +
+                        "foo=-9223372036854774999-9223372036854774000," +
+                        "foo=-9223372036854709999-9223372036854700000," +
+                        "foo=-9223372036854719999-9223372036854710000," +
+                        "foo=-9223372036854729999-9223372036854720000," +
+                        "foo=-9223372036854739999-9223372036854730000," +
+                        "foo=-9223372036854749999-9223372036854740000," +
+                        "foo=-9223372036854759999-9223372036854750000," +
+                        "foo=-9223372036854769999-9223372036854760000," +
+                        "foo=-9223372036854099999-9223372036854000000," +
+                        "foo=-9223372036854199999-9223372036854100000," +
+                        "foo=-9223372036854299999-9223372036854200000," +
+                        "foo=-9223372036854399999-9223372036854300000," +
+                        "foo=-9223372036854499999-9223372036854400000," +
+                        "foo=-9223372036854599999-9223372036854500000," +
+                        "foo=-9223372036854699999-9223372036854600000," +
+                        "foo=-9223372036850999999-9223372036850000000," +
+                        "foo=-9223372036851999999-9223372036851000000," +
+                        "foo=-9223372036852999999-9223372036852000000," +
+                        "foo=-9223372036853999999-9223372036853000000," +
+                        "foo=-9223372036809999999-9223372036800000000," +
+                        "foo=-9223372036819999999-9223372036810000000," +
+                        "foo=-9223372036829999999-9223372036820000000," +
+                        "foo=-9223372036839999999-9223372036830000000," +
+                        "foo=-9223372036849999999-9223372036840000000," +
+                        "foo=-9223372036099999999-9223372036000000000," +
+                        "foo=-9223372036199999999-9223372036100000000," +
+                        "foo=-9223372036299999999-9223372036200000000," +
+                        "foo=-9223372036399999999-9223372036300000000," +
+                        "foo=-9223372036499999999-9223372036400000000," +
+                        "foo=-9223372036599999999-9223372036500000000," +
+                        "foo=-9223372036699999999-9223372036600000000," +
+                        "foo=-9223372036799999999-9223372036700000000," +
+                        "foo=-9223372030999999999-9223372030000000000," +
+                        "foo=-9223372031999999999-9223372031000000000," +
+                        "foo=-9223372032999999999-9223372032000000000," +
+                        "foo=-9223372033999999999-9223372033000000000," +
+                        "foo=-9223372034999999999-9223372034000000000," +
+                        "foo=-9223372035999999999-9223372035000000000," +
+                        "foo=-9223372009999999999-9223372000000000000," +
+                        "foo=-9223372019999999999-9223372010000000000," +
+                        "foo=-9223372029999999999-9223372020000000000," +
+                        "foo=-9223370999999999999-9223370000000000000," +
+                        "foo=-9223371999999999999-9223371000000000000," +
+                        "foo=-9223309999999999999-9223300000000000000," +
+                        "foo=-9223319999999999999-9223310000000000000," +
+                        "foo=-9223329999999999999-9223320000000000000," +
+                        "foo=-9223339999999999999-9223330000000000000," +
+                        "foo=-9223349999999999999-9223340000000000000," +
+                        "foo=-9223359999999999999-9223350000000000000," +
+                        "foo=-9223369999999999999-9223360000000000000," +
+                        "foo=-9223099999999999999-9223000000000000000," +
+                        "foo=-9223199999999999999-9223100000000000000," +
+                        "foo=-9223299999999999999-9223200000000000000," +
+                        "foo=-9220999999999999999-9220000000000000000," +
+                        "foo=-9221999999999999999-9221000000000000000," +
+                        "foo=-9222999999999999999-9222000000000000000," +
+                        "foo=-9209999999999999999-9200000000000000000," +
+                        "foo=-9219999999999999999-9210000000000000000," +
+                        "foo=-9099999999999999999-9000000000000000000," +
+                        "foo=-9199999999999999999-9100000000000000000," +
+                        "foo=-999999999999999999-0," +
+                        "foo=-1999999999999999999-1000000000000000000," +
+                        "foo=-2999999999999999999-2000000000000000000," +
+                        "foo=-3999999999999999999-3000000000000000000," +
+                        "foo=-4999999999999999999-4000000000000000000," +
+                        "foo=-5999999999999999999-5000000000000000000," +
+                        "foo=-6999999999999999999-6000000000000000000," +
+                        "foo=-7999999999999999999-7000000000000000000," +
+                        "foo=-8999999999999999999-8000000000000000000)]");
+        testConvert("foo in [-9223372036854775808..-9223372036854775808]", "foo in [-9223372036854775808..-9223372036854775808 (foo=-9223372036854775800+[8..8])]");
+    }
+
+    @Test
+    public void requireThatLowAritiesWork() {
+        testConvert("foo in [10..39]", "foo in [10..39 (foo=10-11,foo=12-15,foo=32-39,foo=16-31)]", 2);
+        testConvert("foo in [2..32]", "foo in [2..32 (foo=32+[..0],foo=2-3,foo=4-7,foo=8-15,foo=16-31)]", 2);
+        testConvert("foo in [-31..63]", "foo in [-31..63 (foo=-31-0,foo=0-63)]", 2);
+        testConvert("foo in [0..9223372036854775807]", "foo in [0..9223372036854775807 (foo=0-9223372036854775807)]", 2);
+        testConvert("foo in [9223372036854775807..9223372036854775807]", "foo in [9223372036854775807..9223372036854775807 (foo=9223372036854775806+[1..])]", 2);
+        testConvert("foo in [-9223372036854775808..-1]", "foo in [-9223372036854775808..-1 (foo=-9223372036854775808+[..0],foo=-9223372036854775807-0)]", 2);
+        testConvert("foo in [-9223372036854775808..-9223372036854775808]", "foo in [-9223372036854775808..-9223372036854775808 (foo=-9223372036854775808+[..0])]", 2);
+        testConvert("foo in [-9223372036854775808..9223372036854775807]", "foo in [-9223372036854775808..9223372036854775807 (foo=-9223372036854775808+[..0],foo=-9223372036854775807-0,foo=0-9223372036854775807)]", 2);
+
+        testConvert("foo in [9223372036854775807..9223372036854775807]", "foo in [9223372036854775807..9223372036854775807 (foo=9223372036854775806+[1..1])]", 3);
+        testConvert("foo in [-9223372036854775808..-9223372036854775808]", "foo in [-9223372036854775808..-9223372036854775808 (foo=-9223372036854775806+[2..])]", 3);
+        testConvert("foo in [-9223372036854775808..-1]",
+                "foo in [-9223372036854775808..-1 (" +
+                        "foo=-9223372036854775808-9223372036854775782," +
+                        "foo=-9223372036854775700-9223372036854775620," +
+                        "foo=-9223372036854775781-9223372036854775701," +
+                        "foo=-9223372036854775376-9223372036854775134," +
+                        "foo=-9223372036854775619-9223372036854775377," +
+                        "foo=-9223372036854775133-9223372036854774405," +
+                        "foo=-9223372036854774404-9223372036854767844," +
+                        "foo=-9223372036854708794-9223372036854649746," +
+                        "foo=-9223372036854767843-9223372036854708795," +
+                        "foo=-9223372036854472598-9223372036854295452," +
+                        "foo=-9223372036854649745-9223372036854472599," +
+                        "foo=-9223372036854295451-9223372036853764011," +
+                        "foo=-9223372036852169687-9223372036850575365," +
+                        "foo=-9223372036853764010-9223372036852169688," +
+                        "foo=-9223372036850575364-9223372036807528644," +
+                        "foo=-9223372036420108154-9223372036032687666," +
+                        "foo=-9223372036807528643-9223372036420108155," +
+                        "foo=-9223372036032687665-9223372032545903265," +
+                        "foo=-9223372022085550061-9223372011625196859," +
+                        "foo=-9223372032545903264-9223372022085550062," +
+                        "foo=-9223372011625196858-9223371980244137250," +
+                        "foo=-9223371980244137249-9223371132955527807," +
+                        "foo=-9223368591089699477-9223366049223871149," +
+                        "foo=-9223371132955527806-9223368591089699478," +
+                        "foo=-9223358423626386161-9223350798028901175," +
+                        "foo=-9223366049223871148-9223358423626386162," +
+                        "foo=-9223327921236446213-9223305044443991253," +
+                        "foo=-9223350798028901174-9223327921236446214," +
+                        "foo=-9223305044443991252-9223099153311896604," +
+                        "foo=-9223099153311896603-9222481479915612657," +
+                        "foo=-9222481479915612656-9205804298215946088," +
+                        "foo=-9205804298215946087-9155772753116946381," +
+                        "foo=-9155772753116946380-9005678117819947260," +
+                        "foo=-8555394211928949896-8105110306037952534," +
+                        "foo=-9005678117819947259-8555394211928949897," +
+                        "foo=-4052555153018976266-0," +
+                        "foo=-8105110306037952533-4052555153018976267)]", 3);
+    }
+
+    @Test
+    public void requireThatHighAritiesWork() {
+        testConvert("foo in [10..39]", "foo in [10..39 (foo=0+[10..39])]", 1000);
+        testConvert("foo in [9000..11000]", "foo in [9000..11000 (foo=0+[9000..],foo=10000+[..1000])]", 10000);
+        testConvert("foo in [10..39]", "foo in [10..39 (foo=0+[10..39])]", 16384);
+        testConvert("foo in [10..32768]", "foo in [10..32768 (foo=0+[10..],foo=32768+[..0],foo=16384-32767)]", 16384);
+
+        testConvert("foo in [9223372036854775807..9223372036854775807]", "foo in [9223372036854775807..9223372036854775807 (foo=9223372036854759424+[16383..])]", 16384);
+        testConvert("foo in [-9223372036854775808..-9223372036854775808]", "foo in [-9223372036854775808..-9223372036854775808 (foo=-9223372036854775808+[..0])]", 16384);
+    }
+
+    @Test
+    public void requireThatOpenRangesWork() {
+        testConvert("foo in [-7..]", "foo in [-7.. (foo=-7-0,foo=0-9223372036854775807)]", 2);
+        testConvert("foo in [..7]", "foo in [..7 (foo=-9223372036854775808+[..0],foo=-9223372036854775807-0,foo=0-7)]", 2);
+    }
+
+    @Test
+    public void requireThatUpperAndLowerBoundsWork() {
+        lowerBound = -999;
+        upperBound = 999;
+        testConvert("foo in [-9..]", "foo in [-9.. (foo=-9-0,foo=0-999)]", 10);
+        testConvert("foo in [..9]", "foo in [..9 (foo=-999-0,foo=0-9)]", 10);
+        testConvert("foo in [..]", "foo in [.. (foo=-999-0,foo=0-999)]", 10);
+    }
+
+    @Test
+    public void requireThatUpperAndLowerBoundsPruneClosedRanges() {
+        lowerBound = -999;
+        upperBound = 999;
+        testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-999)]", 10);
+        lowerBound = 888;
+        testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-999)]", 10);
+        lowerBound = 900;
+        testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-999)]", 10);
+    }
+
+    @Test
+    public void requireThatRangesOutsideBoundsAreSimplifiedToOneImpossibleRange() {
+        lowerBound = 900;
+        upperBound = 999;
+        testConvert("foo in [0..100]", "foo in [0..100 (foo=-9223372036854775799-9223372036854775790)]", 10);
+        testConvert("foo in [1000..1100]", "foo in [1000..1100 (foo=9223372036854775790-9223372036854775799)]", 10);
+        lowerBound = -999;
+        upperBound = -900;
+        testConvert("foo in [-2000..-1000]", "foo in [-2000..-1000 (foo=-9223372036854775799-9223372036854775790)]", 10);
+        testConvert("foo in [0..100]", "foo in [0..100 (foo=9223372036854775790-9223372036854775799)]", 10);
+        lowerBound = -9223372036854775790L;
+        upperBound = 9223372036854775790L;
+        testConvert("foo in [9223372036854775791..9223372036854775792]", "foo in [9223372036854775791..9223372036854775792 (foo=9223372036854775790+[1..1])]", 10);
+        testConvert("foo in [-9223372036854775792..-9223372036854775791]", "foo in [-9223372036854775792..-9223372036854775791 (foo=-9223372036854775790+[1..1])]", 10);
+    }
+
+    @Test
+    public void requireThatUpperAndLowerBoundsAreAdjustedWithArity() {
+        lowerBound = -999;
+        upperBound = 999;
+        testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-999)]", 10);
+        testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-1023)]", 2);
+        testConvert("foo in [-10000..10000]", "foo in [-10000..10000 (foo=-999-0,foo=0-999)]", 10);
+        testConvert("foo in [-10000..10000]", "foo in [-10000..10000 (foo=-1023-0,foo=0-1023)]", 2);
+
+        upperBound = 1000;
+        testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-9999)]", 10);
+
+        lowerBound = 100;
+        upperBound = 999;
+        testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-999)]", 10);
+        testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-1023)]", 2);
+
+        lowerBound = -999;
+        upperBound = -100;
+        testConvert("foo in [-10000..10000]", "foo in [-10000..10000 (foo=-999-0)]", 10);
+        testConvert("foo in [-10000..10000]", "foo in [-10000..10000 (foo=-1023-0)]", 2);
+
+        lowerBound = -9223372036854775790L;
+        upperBound = 9223372036854775790L;
+        testConvert("foo in [-9223372036854775791..9223372036854775792]",
+                "foo in [-9223372036854775791..9223372036854775792 (" +
+                        "foo=-9223372036854775790+[..0],foo=9223372036854775790+[..0]," +
+                        "foo=-9223372036854775709-9223372036854775700," +
+                        "foo=-9223372036854775719-9223372036854775710," +
+                        "foo=-9223372036854775729-9223372036854775720," +
+                        "foo=-9223372036854775739-9223372036854775730," +
+                        "foo=-9223372036854775749-9223372036854775740," +
+                        "foo=-9223372036854775759-9223372036854775750," +
+                        "foo=-9223372036854775769-9223372036854775760," +
+                        "foo=-9223372036854775779-9223372036854775770," +
+                        "foo=-9223372036854775789-9223372036854775780," +
+                        "foo=-9223372036854775099-9223372036854775000," +
+                        "foo=-9223372036854775199-9223372036854775100," +
+                        "foo=-9223372036854775299-9223372036854775200," +
+                        "foo=-9223372036854775399-9223372036854775300," +
+                        "foo=-9223372036854775499-9223372036854775400," +
+                        "foo=-9223372036854775599-9223372036854775500," +
+                        "foo=-9223372036854775699-9223372036854775600," +
+                        "foo=-9223372036854770999-9223372036854770000," +
+                        "foo=-9223372036854771999-9223372036854771000," +
+                        "foo=-9223372036854772999-9223372036854772000," +
+                        "foo=-9223372036854773999-9223372036854773000," +
+                        "foo=-9223372036854774999-9223372036854774000," +
+                        "foo=-9223372036854709999-9223372036854700000," +
+                        "foo=-9223372036854719999-9223372036854710000," +
+                        "foo=-9223372036854729999-9223372036854720000," +
+                        "foo=-9223372036854739999-9223372036854730000," +
+                        "foo=-9223372036854749999-9223372036854740000," +
+                        "foo=-9223372036854759999-9223372036854750000," +
+                        "foo=-9223372036854769999-9223372036854760000," +
+                        "foo=-9223372036854099999-9223372036854000000," +
+                        "foo=-9223372036854199999-9223372036854100000," +
+                        "foo=-9223372036854299999-9223372036854200000," +
+                        "foo=-9223372036854399999-9223372036854300000," +
+                        "foo=-9223372036854499999-9223372036854400000," +
+                        "foo=-9223372036854599999-9223372036854500000," +
+                        "foo=-9223372036854699999-9223372036854600000," +
+                        "foo=-9223372036850999999-9223372036850000000," +
+                        "foo=-9223372036851999999-9223372036851000000," +
+                        "foo=-9223372036852999999-9223372036852000000," +
+                        "foo=-9223372036853999999-9223372036853000000," +
+                        "foo=-9223372036809999999-9223372036800000000," +
+                        "foo=-9223372036819999999-9223372036810000000," +
+                        "foo=-9223372036829999999-9223372036820000000," +
+                        "foo=-9223372036839999999-9223372036830000000," +
+                        "foo=-9223372036849999999-9223372036840000000," +
+                        "foo=-9223372036099999999-9223372036000000000," +
+                        "foo=-9223372036199999999-9223372036100000000," +
+                        "foo=-9223372036299999999-9223372036200000000," +
+                        "foo=-9223372036399999999-9223372036300000000," +
+                        "foo=-9223372036499999999-9223372036400000000," +
+                        "foo=-9223372036599999999-9223372036500000000," +
+                        "foo=-9223372036699999999-9223372036600000000," +
+                        "foo=-9223372036799999999-9223372036700000000," +
+                        "foo=-9223372030999999999-9223372030000000000," +
+                        "foo=-9223372031999999999-9223372031000000000," +
+                        "foo=-9223372032999999999-9223372032000000000," +
+                        "foo=-9223372033999999999-9223372033000000000," +
+                        "foo=-9223372034999999999-9223372034000000000," +
+                        "foo=-9223372035999999999-9223372035000000000," +
+                        "foo=-9223372009999999999-9223372000000000000," +
+                        "foo=-9223372019999999999-9223372010000000000," +
+                        "foo=-9223372029999999999-9223372020000000000," +
+                        "foo=-9223370999999999999-9223370000000000000," +
+                        "foo=-9223371999999999999-9223371000000000000," +
+                        "foo=-9223309999999999999-9223300000000000000," +
+                        "foo=-9223319999999999999-9223310000000000000," +
+                        "foo=-9223329999999999999-9223320000000000000," +
+                        "foo=-9223339999999999999-9223330000000000000," +
+                        "foo=-9223349999999999999-9223340000000000000," +
+                        "foo=-9223359999999999999-9223350000000000000," +
+                        "foo=-9223369999999999999-9223360000000000000," +
+                        "foo=-9223099999999999999-9223000000000000000," +
+                        "foo=-9223199999999999999-9223100000000000000," +
+                        "foo=-9223299999999999999-9223200000000000000," +
+                        "foo=-9220999999999999999-9220000000000000000," +
+                        "foo=-9221999999999999999-9221000000000000000," +
+                        "foo=-9222999999999999999-9222000000000000000," +
+                        "foo=-9209999999999999999-9200000000000000000," +
+                        "foo=-9219999999999999999-9210000000000000000," +
+                        "foo=-9099999999999999999-9000000000000000000," +
+                        "foo=-9199999999999999999-9100000000000000000," +
+                        "foo=-999999999999999999-0," +
+                        "foo=-1999999999999999999-1000000000000000000," +
+                        "foo=-2999999999999999999-2000000000000000000," +
+                        "foo=-3999999999999999999-3000000000000000000," +
+                        "foo=-4999999999999999999-4000000000000000000," +
+                        "foo=-5999999999999999999-5000000000000000000," +
+                        "foo=-6999999999999999999-6000000000000000000," +
+                        "foo=-7999999999999999999-7000000000000000000," +
+                        "foo=-8999999999999999999-8000000000000000000," +
+                        "foo=9223372036854775700-9223372036854775709," +
+                        "foo=9223372036854775710-9223372036854775719," +
+                        "foo=9223372036854775720-9223372036854775729," +
+                        "foo=9223372036854775730-9223372036854775739," +
+                        "foo=9223372036854775740-9223372036854775749," +
+                        "foo=9223372036854775750-9223372036854775759," +
+                        "foo=9223372036854775760-9223372036854775769," +
+                        "foo=9223372036854775770-9223372036854775779," +
+                        "foo=9223372036854775780-9223372036854775789," +
+                        "foo=9223372036854775000-9223372036854775099," +
+                        "foo=9223372036854775100-9223372036854775199," +
+                        "foo=9223372036854775200-9223372036854775299," +
+                        "foo=9223372036854775300-9223372036854775399," +
+                        "foo=9223372036854775400-9223372036854775499," +
+                        "foo=9223372036854775500-9223372036854775599," +
+                        "foo=9223372036854775600-9223372036854775699," +
+                        "foo=9223372036854770000-9223372036854770999," +
+                        "foo=9223372036854771000-9223372036854771999," +
+                        "foo=9223372036854772000-9223372036854772999," +
+                        "foo=9223372036854773000-9223372036854773999," +
+                        "foo=9223372036854774000-9223372036854774999," +
+                        "foo=9223372036854700000-9223372036854709999," +
+                        "foo=9223372036854710000-9223372036854719999," +
+                        "foo=9223372036854720000-9223372036854729999," +
+                        "foo=9223372036854730000-9223372036854739999," +
+                        "foo=9223372036854740000-9223372036854749999," +
+                        "foo=9223372036854750000-9223372036854759999," +
+                        "foo=9223372036854760000-9223372036854769999," +
+                        "foo=9223372036854000000-9223372036854099999," +
+                        "foo=9223372036854100000-9223372036854199999," +
+                        "foo=9223372036854200000-9223372036854299999," +
+                        "foo=9223372036854300000-9223372036854399999," +
+                        "foo=9223372036854400000-9223372036854499999," +
+                        "foo=9223372036854500000-9223372036854599999," +
+                        "foo=9223372036854600000-9223372036854699999," +
+                        "foo=9223372036850000000-9223372036850999999," +
+                        "foo=9223372036851000000-9223372036851999999," +
+                        "foo=9223372036852000000-9223372036852999999," +
+                        "foo=9223372036853000000-9223372036853999999," +
+                        "foo=9223372036800000000-9223372036809999999," +
+                        "foo=9223372036810000000-9223372036819999999," +
+                        "foo=9223372036820000000-9223372036829999999," +
+                        "foo=9223372036830000000-9223372036839999999," +
+                        "foo=9223372036840000000-9223372036849999999," +
+                        "foo=9223372036000000000-9223372036099999999," +
+                        "foo=9223372036100000000-9223372036199999999," +
+                        "foo=9223372036200000000-9223372036299999999," +
+                        "foo=9223372036300000000-9223372036399999999," +
+                        "foo=9223372036400000000-9223372036499999999," +
+                        "foo=9223372036500000000-9223372036599999999," +
+                        "foo=9223372036600000000-9223372036699999999," +
+                        "foo=9223372036700000000-9223372036799999999," +
+                        "foo=9223372030000000000-9223372030999999999," +
+                        "foo=9223372031000000000-9223372031999999999," +
+                        "foo=9223372032000000000-9223372032999999999," +
+                        "foo=9223372033000000000-9223372033999999999," +
+                        "foo=9223372034000000000-9223372034999999999," +
+                        "foo=9223372035000000000-9223372035999999999," +
+                        "foo=9223372000000000000-9223372009999999999," +
+                        "foo=9223372010000000000-9223372019999999999," +
+                        "foo=9223372020000000000-9223372029999999999," +
+                        "foo=9223370000000000000-9223370999999999999," +
+                        "foo=9223371000000000000-9223371999999999999," +
+                        "foo=9223300000000000000-9223309999999999999," +
+                        "foo=9223310000000000000-9223319999999999999," +
+                        "foo=9223320000000000000-9223329999999999999," +
+                        "foo=9223330000000000000-9223339999999999999," +
+                        "foo=9223340000000000000-9223349999999999999," +
+                        "foo=9223350000000000000-9223359999999999999," +
+                        "foo=9223360000000000000-9223369999999999999," +
+                        "foo=9223000000000000000-9223099999999999999," +
+                        "foo=9223100000000000000-9223199999999999999," +
+                        "foo=9223200000000000000-9223299999999999999," +
+                        "foo=9220000000000000000-9220999999999999999," +
+                        "foo=9221000000000000000-9221999999999999999," +
+                        "foo=9222000000000000000-9222999999999999999," +
+                        "foo=9200000000000000000-9209999999999999999," +
+                        "foo=9210000000000000000-9219999999999999999," +
+                        "foo=9000000000000000000-9099999999999999999," +
+                        "foo=9100000000000000000-9199999999999999999," +
+                        "foo=0-999999999999999999," +
+                        "foo=1000000000000000000-1999999999999999999," +
+                        "foo=2000000000000000000-2999999999999999999," +
+                        "foo=3000000000000000000-3999999999999999999," +
+                        "foo=4000000000000000000-4999999999999999999," +
+                        "foo=5000000000000000000-5999999999999999999," +
+                        "foo=6000000000000000000-6999999999999999999," +
+                        "foo=7000000000000000000-7999999999999999999," +
+                        "foo=8000000000000000000-8999999999999999999)]");
+
+        lowerBound = -922337203685477579L;
+        upperBound = 922337203685477579L;
+        testConvert("foo in [-9223372036854775791..9223372036854775792]",
+                "foo in [-9223372036854775791..9223372036854775792 (foo=-999999999999999999-0,foo=0-999999999999999999)]");
+    }
+
+    @Test
+    public void requireThatExistingPartitionsAreCleared() {
+        testConvert("foo in [10..19]", "foo in [10..19 (foo=10-19)]");
+        Predicate p = Predicate.fromString("foo in [10..19]");
+        ((FeatureRange)p).addPartition(new RangePartition("foo", 10000L, 20000L, false));
+        ComplexNodeTransformer tranformer = new ComplexNodeTransformer();
+        Predicate converted = tranformer.process(p, new PredicateOptions(10, lowerBound, upperBound));
+        assertEquals("foo in [10..19 (foo=10-19)]", converted.toString());
+
+    }
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/NotNodeReordererTest.java b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/NotNodeReordererTest.java
new file mode 100644
index 00000000000..de61c3e04c6
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/NotNodeReordererTest.java
@@ -0,0 +1,55 @@
+// 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;
+import org.junit.Test;
+
+import static com.yahoo.document.predicate.Predicates.and;
+import static com.yahoo.document.predicate.Predicates.feature;
+import static com.yahoo.document.predicate.Predicates.or;
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a>
+ */
+public class NotNodeReordererTest {
+    @Test
+    public void requireThatNotChildrenAreMovedAwayFromLastAndChild() {
+        checkReorder(
+                and(feature("a").inSet("b"), feature("c").notInSet("d")),
+                and(feature("c").notInSet("d"), feature("a").inSet("b")));
+
+        checkReorder(
+                and(feature("a").inSet("b"), feature("c").notInSet("d"), feature("e").notInSet("f")),
+                and(feature("c").notInSet("d"), feature("e").notInSet("f"), feature("a").inSet("b")));
+    }
+
+    @Test
+    public void requireThatNotChildrenAreMovedToLastOrChild() {
+        checkReorder(
+                or(feature("c").notInSet("d"), feature("a").inSet("b")),
+                or(feature("a").inSet("b"), feature("c").notInSet("d")));
+
+        checkReorder(
+                or(feature("c").notInSet("d"), feature("e").notInSet("f"), feature("a").inSet("b")),
+                or(feature("a").inSet("b"), feature("c").notInSet("d"), feature("e").notInSet("f")));
+    }
+
+    @Test
+    public void requireThatComplexReorderingWork() {
+        checkReorder(and(feature("g").inSet("h"),
+                         or(and(feature("a").notInSet("b"),
+                                feature("c").notInSet("d")),
+                            feature("e").inSet("f"))),
+                and(or(feature("e").inSet("f"),
+                       and(feature("a").notInSet("b"),
+                           feature("c").notInSet("d"))),
+                    feature("g").inSet("h")));
+    }
+
+    private static void checkReorder(Predicate input, Predicate expected) {
+        NotNodeReorderer reorderer = new NotNodeReorderer();
+        Predicate actual = reorderer.process(input, new PredicateOptions(10));
+        assertEquals(expected, actual);
+    }
+}
diff --git a/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/OrSimplifierTest.java b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/OrSimplifierTest.java
new file mode 100644
index 00000000000..6db02c5be57
--- /dev/null
+++ b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/OrSimplifierTest.java
@@ -0,0 +1,98 @@
+// 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;
+import org.junit.Test;
+
+import static com.yahoo.document.predicate.Predicates.and;
+import static com.yahoo.document.predicate.Predicates.feature;
+import static com.yahoo.document.predicate.Predicates.not;
+import static com.yahoo.document.predicate.Predicates.or;
+import static org.junit.Assert.assertEquals;
+
+public class OrSimplifierTest {
+
+    @Test
+    public void require_that_or_with_feature_sets_of_same_key_is_simplified_to_single_feature_set() {
+        Predicate p =
+                or(
+                        feature("key1").inSet("value1", "value4"),
+                        feature("key1").inSet("value2", "value3"),
+                        feature("key1").inSet("value1", "value4"));
+        Predicate expected = feature("key1").inSet("value1", "value2", "value3", "value4");
+        assertConvertedPredicateEquals(expected, p);
+    }
+
+    @Test
+    public void require_that_or_with_feature_sets_of_different_keys_is_simplified() {
+        Predicate p =
+                or(
+                        feature("key1").inSet("value1", "value3"),
+                        feature("key1").inSet("value2"),
+                        feature("key2").inSet("value1"),
+                        feature("key2").inSet("value2", "value3"));
+        Predicate expected =
+                or(
+                        feature("key1").inSet("value1", "value2", "value3"),
+                        feature("key2").inSet("value1", "value2", "value3"));
+        assertConvertedPredicateEquals(expected, p);
+    }
+
+    @Test
+    public void require_that_conversion_is_recursive_and_cascades() {
+        Predicate p =
+                or(
+                        feature("key1").inSet("value1", "value4"),
+                        feature("key1").inSet("value2", "value3"),
+                        or(
+                                feature("key1").inSet("value1"),
+                                feature("key1").inSet("value4")));
+        Predicate expected = feature("key1").inSet("value1", "value2", "value3", "value4");
+        assertConvertedPredicateEquals(expected, p);
+    }
+
+    @Test
+    public void require_that_or_below_and_is_converted() {
+        Predicate p =
+                and(
+                        or(
+                                feature("key1").inSet("value1"),
+                                feature("key1").inSet("value2")),
+                        feature("key2").inSet("value2"));
+        Predicate expected =
+                and(
+                        feature("key1").inSet("value1", "value2"),
+                        feature("key2").inSet("value2"));
+        assertConvertedPredicateEquals(expected, p);
+    }
+
+    @Test
+    public void require_that_or_below_not_is_converted() {
+        Predicate p =
+                not(
+                        or(
+                                feature("key1").inSet("value1"),
+                                feature("key1").inSet("value2")));
+        Predicate expected = not(feature("key1").inSet("value1", "value2"));
+        assertConvertedPredicateEquals(expected, p);
+    }
+
+    @Test
+    public void require_that_non_feature_set_nodes_are_left_untouched() {
+        Predicate p =
+                or(
+                        feature("key1").inSet("value1"),
+                        feature("key1").inSet("value2"),
+                        not(feature("key1").inSet("value3")));
+        Predicate expected =
+                or(
+                        not(feature("key1").inSet("value3")),
+                        feature("key1").inSet("value1", "value2"));
+        assertConvertedPredicateEquals(expected, p);
+    }
+
+    private static void assertConvertedPredicateEquals(Predicate expected, Predicate predicate) {
+        OrSimplifier simplifier = new OrSimplifier();
+        assertEquals(expected, simplifier.simplifyTree(predicate));
+    }
+}