diff options
Diffstat (limited to 'predicate-search/src/main/java/com/yahoo/search/predicate/index')
20 files changed, 49 insertions, 15 deletions
diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/BoundsPostingList.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/BoundsPostingList.java index 65da0c8bd76..25d34f752b8 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/BoundsPostingList.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/BoundsPostingList.java @@ -5,7 +5,7 @@ package com.yahoo.search.predicate.index; * Wraps a posting stream of IntervalWithBounds objects (for collapsed * fixed tree leaf nodes) into a PostingList. * - * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + * @author Magnar Nedland * @author bjorncs */ public class BoundsPostingList extends MultiIntervalPostingList { diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/CachedPostingListCounter.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/CachedPostingListCounter.java index 97292d1bc82..91599da5483 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/CachedPostingListCounter.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/CachedPostingListCounter.java @@ -17,6 +17,7 @@ import java.util.List; * @author bjorncs */ public class CachedPostingListCounter { + // Only use bit vector for counting if the documents covered is more than the threshold (relative to nDocuments) private static final double THRESHOLD_USE_BIT_VECTOR = 1; diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/Feature.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/Feature.java index c437112a802..6a9140585c5 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/Feature.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/Feature.java @@ -9,6 +9,7 @@ import com.yahoo.document.predicate.PredicateHash; * @author bjorncs */ public class Feature { + public static final String Z_STAR_COMPRESSED_ATTRIBUTE_NAME = "z-star-compressed"; public static final long Z_STAR_COMPRESSED_ATTRIBUTE_HASH = PredicateHash.hash64(Z_STAR_COMPRESSED_ATTRIBUTE_NAME); @@ -17,4 +18,5 @@ public class Feature { public static long createHash(String key, String value) { return PredicateHash.hash64(key + "=" + value); } + } diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/Interval.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/Interval.java index 500e5207791..a742df139d6 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/Interval.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/Interval.java @@ -12,7 +12,7 @@ package com.yahoo.search.predicate.index; * ZStar1 intervals have end value in 16 MSB and begin in 16 LSB. * ZStar2 intervals have only an end value located at 16 LSB. * - * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + * @author Magnar Nedland * @author bjorncs */ public class Interval { diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/IntervalPostingList.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/IntervalPostingList.java index 67156cc86c2..6d56bd2906b 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/IntervalPostingList.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/IntervalPostingList.java @@ -4,10 +4,12 @@ package com.yahoo.search.predicate.index; /** * Implementation of PostingList for regular features that store * their intervals and nothing else. - * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + * + * @author Magnar Nedland * @author bjorncs */ public class IntervalPostingList extends MultiIntervalPostingList { + private final PredicateIntervalStore store; private int[] currentIntervals; private int currentIntervalIndex; @@ -39,4 +41,5 @@ public class IntervalPostingList extends MultiIntervalPostingList { public int getInterval() { return currentInterval; } + } diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/IntervalWithBounds.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/IntervalWithBounds.java index b80f1880a08..ea4dd56e8d8 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/IntervalWithBounds.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/IntervalWithBounds.java @@ -6,7 +6,7 @@ import java.util.stream.Stream; /** * Represents a collapsed leaf node in the fixed tree range representation. * - * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + * @author Magnar Nedland * @author bjorncs */ public class IntervalWithBounds { @@ -82,4 +82,5 @@ public class IntervalWithBounds { ", bounds=" + getBounds() + '}'; } + } diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/MultiIntervalPostingList.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/MultiIntervalPostingList.java index e4191a2505a..917e4aeef06 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/MultiIntervalPostingList.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/MultiIntervalPostingList.java @@ -5,10 +5,12 @@ import com.yahoo.search.predicate.utils.PostingListSearch; /** * Shared implementation for posting lists that may have multiple intervals. - * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + * + * @author Magnar Nedland * @author bjorncs */ public abstract class MultiIntervalPostingList implements PostingList { + private final int[] docIds; private final int[] dataRefs; private final long subquery; @@ -64,4 +66,5 @@ public abstract class MultiIntervalPostingList implements PostingList { public final long getSubquery() { return subquery; } + } diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/Posting.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/Posting.java index 7bfac7b2a89..bc1ba0fc475 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/Posting.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/Posting.java @@ -4,7 +4,7 @@ package com.yahoo.search.predicate.index; /** * Represents an entry in a posting list, containing an integer id and integer data reference. * - * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + * @author Magnar Nedland */ public class Posting implements Comparable<Posting> { @@ -47,4 +47,5 @@ public class Posting implements Comparable<Posting> { result = 31 * result + dataRef; return result; } + } diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/PostingList.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/PostingList.java index 4274b7e6496..fd14d18ec31 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/PostingList.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/PostingList.java @@ -4,9 +4,10 @@ package com.yahoo.search.predicate.index; /** * Interface for posting lists to be used by the algorithm implemented in PredicateSearch. * - * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + * @author Magnar Nedland */ public interface PostingList { + /** * Moves the posting list past the supplied document id. * @param docId Document id to move past. @@ -50,4 +51,5 @@ public interface PostingList { * @return The document ids */ int[] getDocIds(); + } diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/PredicateOptimizer.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/PredicateOptimizer.java index 682a78fc7de..f4441173b3e 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/PredicateOptimizer.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/PredicateOptimizer.java @@ -19,6 +19,7 @@ import com.yahoo.search.predicate.optimization.PredicateProcessor; * @author bjorncs */ public class PredicateOptimizer { + private final PredicateProcessor[] processors; private final PredicateOptions options; @@ -43,4 +44,5 @@ public class PredicateOptimizer { } return predicate; } + } diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/PredicateRangeTermExpander.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/PredicateRangeTermExpander.java index 46a6b47a01e..198dfd46b74 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/PredicateRangeTermExpander.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/PredicateRangeTermExpander.java @@ -7,9 +7,10 @@ import com.yahoo.document.predicate.PredicateHash; * Expands range terms from a query to find the set of features they translate to. * * @author bjorncs - * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + * @author Magnar Nedland */ public class PredicateRangeTermExpander { + private final int arity; private final int maxPositiveLevels; private final int maxNegativeLevels; @@ -113,4 +114,5 @@ public class PredicateRangeTermExpander { public interface EdgeHandler { void handleEdge(long featureHash, int value); } + } diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/SimpleIndex.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/SimpleIndex.java index b3d2cb44bc9..64583273e77 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/SimpleIndex.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/SimpleIndex.java @@ -17,7 +17,8 @@ import java.util.Map; /** * An index mapping keys of type Long to lists of postings of generic data. - * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + * + * @author Magnar Nedland * @author bjorncs */ public class SimpleIndex { @@ -30,8 +31,9 @@ public class SimpleIndex { /** * Retrieves a posting list for a given key - * @param key Key to lookup - * @return List of postings + * + * @param key the key to lookup + * @return list of postings */ public Entry getPostingList(long key) { return dictionary.get(key); diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/ZeroConstraintPostingList.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/ZeroConstraintPostingList.java index f4d5bc63afc..7f68897c558 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/ZeroConstraintPostingList.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/ZeroConstraintPostingList.java @@ -6,10 +6,12 @@ import com.yahoo.search.predicate.SubqueryBitmap; /** * Wraps an int stream of document ids into a PostingList. * All documents in the stream are considered matches. - * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + * + * @author Magnar Nedland * @author bjorncs */ public class ZeroConstraintPostingList implements PostingList { + private final int[] docIds; private final int length; private int currentIndex; diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/ZstarCompressedPostingList.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/ZstarCompressedPostingList.java index 78d19c58378..487dc328b0f 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/ZstarCompressedPostingList.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/ZstarCompressedPostingList.java @@ -8,10 +8,12 @@ import com.yahoo.search.predicate.SubqueryBitmap; * The compression works by implying an interval of size 1 after each * stored interval, unless the next interval starts with 16 bits of 0, * in which case the current interval is extended to the next. - * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + * + * @author Magnar Nedland * @author bjorncs */ public class ZstarCompressedPostingList extends MultiIntervalPostingList { + private final PredicateIntervalStore store; private int[] currentIntervals; private int currentIntervalIndex; @@ -63,4 +65,5 @@ public class ZstarCompressedPostingList extends MultiIntervalPostingList { public int getInterval() { return currentInterval; } + } diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionHit.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionHit.java index 1be0cd91c87..1706746af58 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionHit.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionHit.java @@ -9,6 +9,7 @@ import com.yahoo.search.predicate.SubqueryBitmap; * @author bjorncs */ public class ConjunctionHit implements Comparable<ConjunctionHit> { + public final long conjunctionId; public final long subqueryBitmap; @@ -49,4 +50,5 @@ public class ConjunctionHit implements Comparable<ConjunctionHit> { return "[" + conjunctionId + ",0x" + Long.toHexString(subqueryBitmap) + "]"; } } + } diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionId.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionId.java index bba5fcf352c..031e9087268 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionId.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionId.java @@ -25,4 +25,5 @@ public class ConjunctionId { public static int nextId(int c) { return (c | 1) + 1; } + } diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionIdIterator.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionIdIterator.java index 231aa67d791..8c7dd278f1d 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionIdIterator.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionIdIterator.java @@ -44,4 +44,5 @@ public class ConjunctionIdIterator { public int[] getConjunctionIds() { return conjunctionIds; } + } diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionIndex.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionIndex.java index d2709ba956f..5a100ea9cf5 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionIndex.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionIndex.java @@ -23,12 +23,14 @@ import java.util.Optional; /** * A searchable index of conjunctions (see {@link FeatureConjunction} / {@link IndexableFeatureConjunction}). - * Implements the algorithm described in the paper <a href="http://dl.acm.org/citation.cfm?id=1687633">Indexing Boolean Expressions</a>. + * Implements the algorithm described in the paper + * <a href="http://dl.acm.org/citation.cfm?id=1687633">Indexing Boolean Expressions</a>. * - * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + * @author Magnar Nedland * @author bjorncs */ public class ConjunctionIndex { + // A map from K value to FeatureIndex private final IntObjectMap<FeatureIndex> kIndex; private final int[] zList; @@ -276,4 +278,5 @@ public class ConjunctionIndex { return idMapping[internalId >>> 1]; } } + } diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionIndexBuilder.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionIndexBuilder.java index e3b75d85743..a6a03177018 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionIndexBuilder.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/ConjunctionIndexBuilder.java @@ -22,6 +22,7 @@ import java.util.TreeSet; * @author bjorncs */ public class ConjunctionIndexBuilder { + // A map from K value to FeatureIndex private final HashMap<Integer, FeatureIndexBuilder> kIndexBuilder = new HashMap<>(); private final List<Integer> zListBuilder = new ArrayList<>(); diff --git a/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/IndexableFeatureConjunction.java b/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/IndexableFeatureConjunction.java index 35709c1806e..5e423d36245 100644 --- a/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/IndexableFeatureConjunction.java +++ b/predicate-search/src/main/java/com/yahoo/search/predicate/index/conjunction/IndexableFeatureConjunction.java @@ -17,6 +17,7 @@ import java.util.Set; * @author bjorncs */ public class IndexableFeatureConjunction { + /** Conjunction id */ public final long id; /** K value - number of non-negated operands */ @@ -72,4 +73,5 @@ public class IndexableFeatureConjunction { public int hashCode() { return (int) (id ^ (id >>> 32)); } + } |