diff options
Diffstat (limited to 'predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/NotNodeReorderer.java')
-rw-r--r-- | predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/NotNodeReorderer.java | 67 |
1 files changed, 67 insertions, 0 deletions
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; + } +} |