You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@asterixdb.apache.org by AsterixDB Code Review <do...@asterix-gerrit.ics.uci.edu> on 2026/05/22 08:28:44 UTC
[XL] Change in asterixdb[master]: Add WAND
From Savyasach Reddy <es...@gmail.com>:
Savyasach Reddy has uploaded this change for review. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21278?usp=email )
Change subject: Add WAND
......................................................................
Add WAND
Change-Id: I2ea8c32ddfc7750fdc671b9d1b5d0d551ef68403
---
M hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/api/IInvertedListCursor.java
M hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/dataflow/BinaryTokenizerOperatorNodePushable.java
M hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/dataflow/LSMInvertedIndexSearchOperatorNodePushable.java
M hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedIndex.java
M hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedIndexAccessor.java
M hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedListCursor.java
M hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/OnDiskInvertedIndex.java
A hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/WeightedOnDiskInvertedIndex.java
A hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/WeightedOnDiskInvertedListCursor.java
M hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/AbstractTOccurrenceSearcher.java
A hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/DotProductSearchModifier.java
A hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/DotProductSearchModifierFactory.java
M hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/InvertedListMerger.java
A hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WANDSearchResult.java
A hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WANDSearcher.java
A hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WandSearchPredicate.java
A hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/tokenizers/IWeightedToken.java
M hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/util/InvertedIndexTokenizingTupleIterator.java
M hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/pom.xml
A hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedIndexMaxWeightTest.java
A hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/WeightedOnDiskInvertedListCursorMoveToTest.java
A hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/DotProductSearchModifierTest.java
A hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/InvertedListMergerWANDTest.java
A hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WANDSearchResultTest.java
A hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WandSearchPredicateTest.java
A hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/util/InvertedIndexTokenizingTupleIteratorTest.java
26 files changed, 2,466 insertions(+), 42 deletions(-)
git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/78/21278/1
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/api/IInvertedListCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/api/IInvertedListCursor.java
index cc11567..db236e8 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/api/IInvertedListCursor.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/api/IInvertedListCursor.java
@@ -21,6 +21,7 @@
import org.apache.hyracks.api.dataflow.value.ISerializerDeserializer;
import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.data.std.primitive.IntegerPointable;
import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
import org.apache.hyracks.storage.common.IIndexCursor;
import org.apache.hyracks.storage.common.MultiComparator;
@@ -70,4 +71,36 @@
*/
@SuppressWarnings("rawtypes")
String printCurrentElement(ISerializerDeserializer[] serdes) throws HyracksDataException;
+
+ /**
+ * Stores the maximum weight of the inverted list that this cursor will traverse.
+ * <p>
+ * Used by WAND (Weak AND) search to compute pivot upper bounds.
+ */
+ default void setMaxWeight(double maxWeight) {
+ // no-op by default
+ }
+
+ /**
+ * Returns the maximum weight previously set via {@link #setMaxWeight(double)}.
+ */
+ default double getMaxWeight() {
+ return 0.0;
+ }
+
+ /**
+ * Advances the cursor to the first entry whose docId (field 0, int32) is >= targetDocId.
+ * Returns true if such an entry exists and the cursor is now positioned on it;
+ * false if the list is exhausted.
+ */
+ default boolean moveTo(int targetDocId) throws HyracksDataException {
+ while (hasNext()) {
+ next();
+ int docId = IntegerPointable.getInteger(getTuple().getFieldData(0), getTuple().getFieldStart(0));
+ if (docId >= targetDocId) {
+ return true;
+ }
+ }
+ return false;
+ }
}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/dataflow/BinaryTokenizerOperatorNodePushable.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/dataflow/BinaryTokenizerOperatorNodePushable.java
index b9c8c8a..42222f4 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/dataflow/BinaryTokenizerOperatorNodePushable.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/dataflow/BinaryTokenizerOperatorNodePushable.java
@@ -39,6 +39,7 @@
import org.apache.hyracks.storage.am.lsm.invertedindex.fulltext.IFullTextConfigEvaluator;
import org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers.IBinaryTokenizer;
import org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers.IToken;
+import org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers.IWeightedToken;
public class BinaryTokenizerOperatorNodePushable extends AbstractUnaryInputUnaryOutputOperatorNodePushable {
@@ -137,6 +138,10 @@
if (token != null) {
token.serializeToken(builderData);
builder.addFieldEndOffset();
+ if (token instanceof IWeightedToken wt) {
+ builder.getDataOutput().writeFloat((float) wt.getWeight());
+ builder.addFieldEndOffset();
+ }
} else {
missingWriter.writeMissing(builder.getDataOutput());
builder.addFieldEndOffset();
@@ -166,6 +171,10 @@
if (token != null) {
token.serializeToken(builderData);
builder.addFieldEndOffset();
+ if (token instanceof IWeightedToken wt) {
+ builder.getDataOutput().writeFloat((float) wt.getWeight());
+ builder.addFieldEndOffset();
+ }
} else {
missingWriter.writeMissing(builder.getDataOutput());
builder.addFieldEndOffset();
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/dataflow/LSMInvertedIndexSearchOperatorNodePushable.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/dataflow/LSMInvertedIndexSearchOperatorNodePushable.java
index 742a86c..2e1f29d 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/dataflow/LSMInvertedIndexSearchOperatorNodePushable.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/dataflow/LSMInvertedIndexSearchOperatorNodePushable.java
@@ -37,7 +37,9 @@
import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedIndexSearchModifier;
import org.apache.hyracks.storage.am.lsm.invertedindex.fulltext.IFullTextConfigEvaluator;
import org.apache.hyracks.storage.am.lsm.invertedindex.fulltext.IFullTextConfigEvaluatorFactory;
+import org.apache.hyracks.storage.am.lsm.invertedindex.search.DotProductSearchModifier;
import org.apache.hyracks.storage.am.lsm.invertedindex.search.InvertedIndexSearchPredicate;
+import org.apache.hyracks.storage.am.lsm.invertedindex.search.WandSearchPredicate;
import org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers.IBinaryTokenizer;
import org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers.IBinaryTokenizerFactory;
import org.apache.hyracks.storage.common.IIndex;
@@ -94,6 +96,10 @@
IFullTextConfigEvaluator fullTextConfigEvaluator =
fullTextConfigEvaluatorFactory.createFullTextConfigEvaluator();
+ if (searchModifier instanceof DotProductSearchModifier) {
+ return new WandSearchPredicate(tokenizer, fullTextConfigEvaluator,
+ (DotProductSearchModifier) searchModifier, minFilterKey, maxFilterKey, isFullTextSearchQuery);
+ }
return new InvertedIndexSearchPredicate(tokenizer, fullTextConfigEvaluator, searchModifier, minFilterKey,
maxFilterKey, isFullTextSearchQuery);
}
@@ -111,6 +117,15 @@
if (maxFilterKey != null) {
maxFilterKey.reset(accessor, tupleIndex);
}
+ if (invIndexSearchPred instanceof WandSearchPredicate) {
+ double[] weights = extractQueryWeights(invIndexSearchPred);
+ ((WandSearchPredicate) invIndexSearchPred).setQueryWeights(weights);
+ }
+ }
+
+ private double[] extractQueryWeights(InvertedIndexSearchPredicate searchPred) {
+ // TODO(Patch 2): iterate tokenized query and extract IWeightedToken.getWeight()
+ return null;
}
@Override
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedIndex.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedIndex.java
index 7ee6af8..7600856 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedIndex.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedIndex.java
@@ -18,6 +18,8 @@
*/
package org.apache.hyracks.storage.am.lsm.invertedindex.inmemory;
+import java.util.concurrent.ConcurrentHashMap;
+
import org.apache.hyracks.api.context.IHyracksTaskContext;
import org.apache.hyracks.api.dataflow.value.IBinaryComparatorFactory;
import org.apache.hyracks.api.dataflow.value.ITypeTraits;
@@ -25,6 +27,9 @@
import org.apache.hyracks.api.exceptions.HyracksDataException;
import org.apache.hyracks.api.io.FileReference;
import org.apache.hyracks.api.util.HyracksConstants;
+import org.apache.hyracks.data.std.primitive.FloatPointable;
+import org.apache.hyracks.data.std.primitive.IntegerPointable;
+import org.apache.hyracks.data.std.primitive.LongPointable;
import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
import org.apache.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
import org.apache.hyracks.storage.am.btree.impls.BTree;
@@ -59,6 +64,12 @@
protected final ITypeTraits nullTypeTraits;
protected final INullIntrospector nullIntrospector;
+ /**
+ * Maps dimension index --> maximum weight seen for that dimension.
+ * Updated on insert but not on delete; may overestimate after deletes.
+ */
+ protected final ConcurrentHashMap<Long, Double> maxWeightByDim = new ConcurrentHashMap<>();
+
public InMemoryInvertedIndex(IBufferCache virtualBufferCache, IPageManager virtualFreePageManager,
ITypeTraits[] invListTypeTraits, IBinaryComparatorFactory[] invListCmpFactories,
ITypeTraits[] tokenTypeTraits, IBinaryComparatorFactory[] tokenCmpFactories,
@@ -103,6 +114,7 @@
@Override
public void clear() throws HyracksDataException {
btree.clear();
+ maxWeightByDim.clear();
}
@Override
@@ -113,6 +125,7 @@
@Override
public void destroy() throws HyracksDataException {
btree.destroy();
+ maxWeightByDim.clear();
}
@Override
@@ -137,9 +150,39 @@
throw e;
}
}
+ // Update max weight even on duplicate key: a later posting for the same dimension may carry
+ // a higher weight, and skipping the update would cause WAND to underestimate upper bounds.
+ updateMaxWeight(insertTuple);
}
}
+ private void updateMaxWeight(ITupleReference tuple) {
+ if (!isSparseVectorToken()) {
+ return;
+ }
+ long dimIndex = extractDimIndex(tuple);
+ int weightField = tuple.getFieldCount() - 1;
+ float weight = FloatPointable.getFloat(tuple.getFieldData(weightField), tuple.getFieldStart(weightField));
+ maxWeightByDim.merge(dimIndex, (double) weight, Math::max);
+ }
+
+ private long extractDimIndex(ITupleReference tuple) {
+ if (tokenTypeTraits[0].getFixedLength() == 8) {
+ return LongPointable.getLong(tuple.getFieldData(0), tuple.getFieldStart(0));
+ } else {
+ return IntegerPointable.getInteger(tuple.getFieldData(0), tuple.getFieldStart(0));
+ }
+ }
+
+ private boolean isSparseVectorToken() {
+ return tokenTypeTraits[0].isFixedLength()
+ && (tokenTypeTraits[0].getFixedLength() == 4 || tokenTypeTraits[0].getFixedLength() == 8);
+ }
+
+ public double getMaxWeight(long dimIndex) {
+ return maxWeightByDim.getOrDefault(dimIndex, 0.0);
+ }
+
public void delete(ITupleReference tuple, BTreeAccessor btreeAccessor, IIndexOperationContext ictx)
throws HyracksDataException {
InMemoryInvertedIndexOpContext ctx = (InMemoryInvertedIndexOpContext) ictx;
@@ -178,10 +221,19 @@
InMemoryInvertedListCursor inMemListCursor = (InMemoryInvertedListCursor) listCursor;
inMemListCursor.prepare(ctx.getBtreeAccessor(), ctx.getBtreePred(), ctx.getTokenFieldsCmp(), ctx.getBtreeCmp());
inMemListCursor.reset(searchKey);
- // Makes the cursor state to OPENED
+ long dimIndex = extractDimIndexOrThrow(searchKey);
+ inMemListCursor.setMaxWeight(getMaxWeight(dimIndex));
inMemListCursor.open(null, null);
}
+ private long extractDimIndexOrThrow(ITupleReference searchKey) throws HyracksDataException {
+ if (!isSparseVectorToken()) {
+ throw HyracksDataException.create(new IllegalStateException(
+ "Unsupported token type for WAND maxWeight lookup: expected fixed-length 4 or 8 bytes"));
+ }
+ return extractDimIndex(searchKey);
+ }
+
@Override
public InMemoryInvertedIndexAccessor createAccessor(IIndexAccessParameters iap) throws HyracksDataException {
return new InMemoryInvertedIndexAccessor(this,
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedIndexAccessor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedIndexAccessor.java
index 5f0e1364..31637a0 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedIndexAccessor.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedIndexAccessor.java
@@ -34,6 +34,8 @@
import org.apache.hyracks.storage.am.lsm.invertedindex.ondisk.OnDiskInvertedIndexSearchCursor;
import org.apache.hyracks.storage.am.lsm.invertedindex.search.InvertedIndexSearchPredicate;
import org.apache.hyracks.storage.am.lsm.invertedindex.search.TOccurrenceSearcher;
+import org.apache.hyracks.storage.am.lsm.invertedindex.search.WANDSearcher;
+import org.apache.hyracks.storage.am.lsm.invertedindex.search.WandSearchPredicate;
import org.apache.hyracks.storage.common.IIndexCursor;
import org.apache.hyracks.storage.common.ISearchPredicate;
@@ -69,18 +71,27 @@
@Override
public IIndexCursor createSearchCursor(boolean exclusive) throws HyracksDataException {
- if (searcher == null) {
- searcher = createSearcher();
- }
- return new OnDiskInvertedIndexSearchCursor(searcher);
+ return new OnDiskInvertedIndexSearchCursor(getSearcher(null));
}
@Override
public void search(IIndexCursor cursor, ISearchPredicate searchPred) throws HyracksDataException {
+ getSearcher((InvertedIndexSearchPredicate) searchPred).search(cursor, (InvertedIndexSearchPredicate) searchPred,
+ opCtx);
+ }
+
+ private IInvertedIndexSearcher getSearcher(InvertedIndexSearchPredicate pred) throws HyracksDataException {
+ boolean needsWAND = pred instanceof WandSearchPredicate;
if (searcher == null) {
+ searcher = needsWAND ? new WANDSearcher(index, ctx) : createSearcher();
+ } else if (needsWAND && !(searcher instanceof WANDSearcher)) {
+ searcher.destroy();
+ searcher = new WANDSearcher(index, ctx);
+ } else if (!needsWAND && !(searcher instanceof TOccurrenceSearcher)) {
+ searcher.destroy();
searcher = createSearcher();
}
- searcher.search(cursor, (InvertedIndexSearchPredicate) searchPred, opCtx);
+ return searcher;
}
@Override
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedListCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedListCursor.java
index e1f301d..925e8f9 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedListCursor.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedListCursor.java
@@ -53,6 +53,7 @@
private final ArrayTupleReference tokenTuple = new ArrayTupleReference();
private int numElements = -1;
+ private double maxWeight = 0.0;
public InMemoryInvertedListCursor(int invListFieldCount, int tokenFieldCount) {
int[] fieldPermutation = new int[invListFieldCount];
@@ -230,4 +231,14 @@
btreeCursor.destroy();
}
+ @Override
+ public void setMaxWeight(double maxWeight) {
+ this.maxWeight = maxWeight;
+ }
+
+ @Override
+ public double getMaxWeight() {
+ return maxWeight;
+ }
+
}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/OnDiskInvertedIndex.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/OnDiskInvertedIndex.java
index 47068a3..9963b01 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/OnDiskInvertedIndex.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/OnDiskInvertedIndex.java
@@ -88,20 +88,6 @@
protected final int invListStartOffField;
protected final int invListNumElementsField;
- // Type traits to be appended to the token type trait which finally form the BTree field type traits.
- protected static final ITypeTraits[] btreeValueTypeTraits = new ITypeTraits[4];
-
- static {
- // startPageId
- btreeValueTypeTraits[0] = IntegerPointable.TYPE_TRAITS;
- // endPageId
- btreeValueTypeTraits[1] = IntegerPointable.TYPE_TRAITS;
- // startOff
- btreeValueTypeTraits[2] = IntegerPointable.TYPE_TRAITS;
- // numElements
- btreeValueTypeTraits[3] = IntegerPointable.TYPE_TRAITS;
- }
-
protected DiskBTree btree;
protected int rootPageId = 0;
protected IBufferCache bufferCache;
@@ -525,18 +511,24 @@
@Override
public IIndexCursor createSearchCursor(boolean exclusive) throws HyracksDataException {
- if (searcher == null) {
- searcher = new TOccurrenceSearcher(index, ctx);
- }
- return new OnDiskInvertedIndexSearchCursor(searcher);
+ return new OnDiskInvertedIndexSearchCursor(getSearcher());
}
@Override
public void search(IIndexCursor cursor, ISearchPredicate searchPred) throws HyracksDataException {
+ InvertedIndexSearchPredicate invPred = (InvertedIndexSearchPredicate) searchPred;
+ getSearcher(invPred).search(cursor, invPred, opCtx);
+ }
+
+ private IInvertedIndexSearcher getSearcher() throws HyracksDataException {
+ return getSearcher(null);
+ }
+
+ protected IInvertedIndexSearcher getSearcher(InvertedIndexSearchPredicate pred) throws HyracksDataException {
if (searcher == null) {
searcher = new TOccurrenceSearcher(index, ctx);
}
- searcher.search(cursor, (InvertedIndexSearchPredicate) searchPred, opCtx);
+ return searcher;
}
@Override
@@ -689,16 +681,13 @@
}
}
- protected static ITypeTraits[] getBTreeTypeTraits(ITypeTraits[] tokenTypeTraits) {
- ITypeTraits[] btreeTypeTraits = new ITypeTraits[tokenTypeTraits.length + btreeValueTypeTraits.length];
- // Set key type traits.
- for (int i = 0; i < tokenTypeTraits.length; i++) {
- btreeTypeTraits[i] = tokenTypeTraits[i];
- }
- // Set value type traits.
- for (int i = 0; i < btreeValueTypeTraits.length; i++) {
- btreeTypeTraits[i + tokenTypeTraits.length] = btreeValueTypeTraits[i];
- }
+ protected ITypeTraits[] getBTreeTypeTraits(ITypeTraits[] tokenTypeTraits) {
+ ITypeTraits[] btreeTypeTraits = new ITypeTraits[tokenTypeTraits.length + 4];
+ System.arraycopy(tokenTypeTraits, 0, btreeTypeTraits, 0, tokenTypeTraits.length);
+ btreeTypeTraits[tokenTypeTraits.length] = IntegerPointable.TYPE_TRAITS; // startPageId
+ btreeTypeTraits[tokenTypeTraits.length + 1] = IntegerPointable.TYPE_TRAITS; // endPageId
+ btreeTypeTraits[tokenTypeTraits.length + 2] = IntegerPointable.TYPE_TRAITS; // startOff
+ btreeTypeTraits[tokenTypeTraits.length + 3] = IntegerPointable.TYPE_TRAITS; // numElements
return btreeTypeTraits;
}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/WeightedOnDiskInvertedIndex.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/WeightedOnDiskInvertedIndex.java
new file mode 100644
index 0000000..ce35c65
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/WeightedOnDiskInvertedIndex.java
@@ -0,0 +1,227 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.hyracks.storage.am.lsm.invertedindex.ondisk;
+
+import java.io.DataOutput;
+import java.io.IOException;
+
+import org.apache.hyracks.api.context.IHyracksTaskContext;
+import org.apache.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import org.apache.hyracks.api.dataflow.value.ITypeTraits;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.api.io.FileReference;
+import org.apache.hyracks.data.std.primitive.FloatPointable;
+import org.apache.hyracks.data.std.primitive.IntegerPointable;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
+import org.apache.hyracks.storage.am.common.api.INullIntrospector;
+import org.apache.hyracks.storage.am.common.api.IPageManagerFactory;
+import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedIndexSearcher;
+import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedListBuilder;
+import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedListCursor;
+import org.apache.hyracks.storage.am.lsm.invertedindex.search.InvertedIndexSearchPredicate;
+import org.apache.hyracks.storage.am.lsm.invertedindex.search.WANDSearcher;
+import org.apache.hyracks.storage.am.lsm.invertedindex.tuples.TokenKeyPairTuple;
+import org.apache.hyracks.storage.common.IIndexAccessParameters;
+import org.apache.hyracks.storage.common.IIndexBulkLoader;
+import org.apache.hyracks.storage.common.IIndexCursorStats;
+import org.apache.hyracks.storage.common.NoOpIndexCursorStats;
+import org.apache.hyracks.storage.common.buffercache.IBufferCache;
+import org.apache.hyracks.storage.common.buffercache.IPageWriteCallback;
+
+/**
+ * On-disk inverted index for sparse-vector dot-product (WAND) searches.
+ * <p>
+ * BTree value schema (5 fields, 20 bytes):
+ * {@code [startPageId:int32, endPageId:int32, startOff:int32, numElements:int32, maxWeight:float32]}.
+ * <p> The {@code maxWeight} field stores the per-list maximum entry weight for WAND pruning.
+ * <p>
+ * Inverted list entry format: {@code (docId:int32, weight:float32)} = 8 bytes,
+ * as expected by {@link WeightedOnDiskInvertedListCursor}.
+ */
+public class WeightedOnDiskInvertedIndex extends OnDiskInvertedIndex {
+
+ /** Full BTree tuple index of the maxWeight field (after all token fields). */
+ protected final int invListMaxWeightField;
+
+ public WeightedOnDiskInvertedIndex(IBufferCache bufferCache, IInvertedListBuilder invListBuilder,
+ ITypeTraits[] invListTypeTraits, IBinaryComparatorFactory[] invListCmpFactories,
+ ITypeTraits[] tokenTypeTraits, IBinaryComparatorFactory[] tokenCmpFactories, FileReference btreeFile,
+ FileReference invListsFile, IPageManagerFactory pageManagerFactory, ITypeTraits nullTypeTraits,
+ INullIntrospector nullIntrospector) throws HyracksDataException {
+ super(bufferCache, invListBuilder, invListTypeTraits, invListCmpFactories, tokenTypeTraits, tokenCmpFactories,
+ btreeFile, invListsFile, pageManagerFactory, nullTypeTraits, nullIntrospector);
+ this.invListMaxWeightField = numTokenFields + 4;
+ }
+
+ @Override
+ protected ITypeTraits[] getBTreeTypeTraits(ITypeTraits[] tokenTypeTraits) {
+ ITypeTraits[] traits = new ITypeTraits[tokenTypeTraits.length + 5];
+ System.arraycopy(tokenTypeTraits, 0, traits, 0, tokenTypeTraits.length);
+ traits[tokenTypeTraits.length] = IntegerPointable.TYPE_TRAITS; // startPageId
+ traits[tokenTypeTraits.length + 1] = IntegerPointable.TYPE_TRAITS; // endPageId
+ traits[tokenTypeTraits.length + 2] = IntegerPointable.TYPE_TRAITS; // startOff
+ traits[tokenTypeTraits.length + 3] = IntegerPointable.TYPE_TRAITS; // numElements
+ traits[tokenTypeTraits.length + 4] = FloatPointable.TYPE_TRAITS; // maxWeight
+ return traits;
+ }
+
+ @Override
+ public IInvertedListCursor createInvertedListCursor(IHyracksTaskContext ctx) throws HyracksDataException {
+ return new WeightedOnDiskInvertedListCursor(bufferCache, fileId, invListTypeTraits, ctx,
+ NoOpIndexCursorStats.INSTANCE, nullTypeTraits, nullIntrospector);
+ }
+
+ @Override
+ public IInvertedListCursor createInvertedListRangeSearchCursor(IIndexCursorStats stats)
+ throws HyracksDataException {
+ return new WeightedOnDiskInvertedListCursor(bufferCache, fileId, invListTypeTraits, null, stats, nullTypeTraits,
+ nullIntrospector);
+ }
+
+ @Override
+ public void openInvertedListCursor(ITupleReference btreeTuple, IInvertedListCursor listCursor,
+ OnDiskInvertedIndexOpContext opCtx) throws HyracksDataException {
+ super.openInvertedListCursor(btreeTuple, listCursor, opCtx);
+ float maxWeight = FloatPointable.getFloat(btreeTuple.getFieldData(invListMaxWeightField),
+ btreeTuple.getFieldStart(invListMaxWeightField));
+ listCursor.setMaxWeight(maxWeight);
+ }
+
+ private static void writeWeightedBTreeTuple(ArrayTupleBuilder builder, ArrayTupleReference ref,
+ IIndexBulkLoader loader, int startPageId, int endPageId, int startOff, int numElements, float maxWeight)
+ throws HyracksDataException {
+ DataOutput out = builder.getDataOutput();
+ try {
+ out.writeInt(startPageId);
+ builder.addFieldEndOffset();
+ out.writeInt(endPageId);
+ builder.addFieldEndOffset();
+ out.writeInt(startOff);
+ builder.addFieldEndOffset();
+ out.writeInt(numElements);
+ builder.addFieldEndOffset();
+ out.writeFloat(maxWeight);
+ builder.addFieldEndOffset();
+ } catch (IOException e) {
+ throw HyracksDataException.create(e);
+ }
+ ref.reset(builder.getFieldEndOffsets(), builder.getByteArray());
+ loader.add(ref);
+ builder.reset();
+ }
+
+ @Override
+ public IIndexBulkLoader createBulkLoader(float fillFactor, boolean verifyInput, long numElementsHint,
+ boolean checkIfEmptyIndex, IPageWriteCallback callback) throws HyracksDataException {
+ return new WeightedBulkLoader(fillFactor, verifyInput, numElementsHint, checkIfEmptyIndex, rootPageId,
+ callback);
+ }
+
+ @Override
+ public IIndexBulkLoader createMergeBulkLoader(float fillFactor, boolean verifyInput, long numElementsHint,
+ boolean checkIfEmptyIndex, IPageWriteCallback callback) throws HyracksDataException {
+ return new WeightedMergeBulkLoader(fillFactor, verifyInput, numElementsHint, checkIfEmptyIndex, rootPageId,
+ callback);
+ }
+
+ public class WeightedBulkLoader extends OnDiskInvertedIndexBulkLoader {
+ private float currentMaxWeight = 0.0f;
+
+ public WeightedBulkLoader(float btreeFillFactor, boolean verifyInput, long numElementsHint,
+ boolean checkIfEmptyIndex, int startPageId, IPageWriteCallback callback) throws HyracksDataException {
+ super(btreeFillFactor, verifyInput, numElementsHint, checkIfEmptyIndex, startPageId, callback);
+ }
+
+ @Override
+ protected void startNewList(ITupleReference tokenTuple) throws HyracksDataException {
+ super.startNewList(tokenTuple);
+ currentMaxWeight = 0.0f;
+ }
+
+ @Override
+ protected void insertBTreeTuple() throws HyracksDataException {
+ writeWeightedBTreeTuple(btreeTupleBuilder, btreeTupleReference, btreeBulkloader, currentInvListStartPageId,
+ currentPageId, currentInvListStartOffset, invListBuilder.getListSize(), currentMaxWeight);
+ }
+
+ @Override
+ public void add(ITupleReference tuple) throws HyracksDataException {
+ super.add(tuple);
+ int wf = tuple.getFieldCount() - 1;
+ float w = FloatPointable.getFloat(tuple.getFieldData(wf), tuple.getFieldStart(wf));
+ if (w > currentMaxWeight) {
+ currentMaxWeight = w;
+ }
+ }
+ }
+
+ @Override
+ public OnDiskInvertedIndexAccessor createAccessor(IIndexAccessParameters iap) throws HyracksDataException {
+ return new WeightedAccessor(this, iap);
+ }
+
+ public class WeightedAccessor extends OnDiskInvertedIndexAccessor {
+ public WeightedAccessor(OnDiskInvertedIndex index, IIndexAccessParameters iap) throws HyracksDataException {
+ super(index, iap);
+ }
+
+ @Override
+ protected IInvertedIndexSearcher getSearcher(InvertedIndexSearchPredicate pred) throws HyracksDataException {
+ if (searcher == null) {
+ searcher = new WANDSearcher(index, ctx);
+ }
+ return searcher;
+ }
+ }
+
+ public class WeightedMergeBulkLoader extends OnDiskInvertedIndexMergeBulkLoader {
+ private float currentMaxWeight = 0.0f;
+
+ public WeightedMergeBulkLoader(float btreeFillFactor, boolean verifyInput, long numElementsHint,
+ boolean checkIfEmptyIndex, int startPageId, IPageWriteCallback callback) throws HyracksDataException {
+ super(btreeFillFactor, verifyInput, numElementsHint, checkIfEmptyIndex, startPageId, callback);
+ }
+
+ @Override
+ protected void startNewList(ITupleReference tokenTuple) throws HyracksDataException {
+ super.startNewList(tokenTuple);
+ currentMaxWeight = 0.0f;
+ }
+
+ @Override
+ protected void insertBTreeTuple() throws HyracksDataException {
+ writeWeightedBTreeTuple(btreeTupleBuilder, btreeTupleReference, btreeBulkloader, currentInvListStartPageId,
+ currentPageId, currentInvListStartOffset, invListBuilder.getListSize(), currentMaxWeight);
+ }
+
+ @Override
+ public void add(ITupleReference tuple) throws HyracksDataException {
+ TokenKeyPairTuple pairTuple = (TokenKeyPairTuple) tuple;
+ ITupleReference keyTuple = pairTuple.getKeyTuple();
+ int wf = keyTuple.getFieldCount() - 1;
+ float w = FloatPointable.getFloat(keyTuple.getFieldData(wf), keyTuple.getFieldStart(wf));
+ if (w > currentMaxWeight) {
+ currentMaxWeight = w;
+ }
+ super.add(tuple);
+ }
+ }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/WeightedOnDiskInvertedListCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/WeightedOnDiskInvertedListCursor.java
new file mode 100644
index 0000000..d1aeae7
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/WeightedOnDiskInvertedListCursor.java
@@ -0,0 +1,212 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.hyracks.storage.am.lsm.invertedindex.ondisk;
+
+import java.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.util.Objects;
+
+import org.apache.hyracks.api.context.IHyracksTaskContext;
+import org.apache.hyracks.api.dataflow.value.ISerializerDeserializer;
+import org.apache.hyracks.api.dataflow.value.ITypeTraits;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.data.std.primitive.IntegerPointable;
+import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
+import org.apache.hyracks.storage.am.common.api.INullIntrospector;
+import org.apache.hyracks.storage.am.lsm.invertedindex.impls.AbstractOnDiskInvertedListCursor;
+import org.apache.hyracks.storage.common.IIndexCursorStats;
+import org.apache.hyracks.storage.common.MultiComparator;
+import org.apache.hyracks.storage.common.buffercache.IBufferCache;
+
+/**
+ * Cursor for sparse-vector weighted inverted lists (WAND use case).
+ * <p>
+ * Each entry is {@code (docId:int32, weight:float)} = 8 bytes. {@code numElements}
+ * is supplied via the BTree value (field 3) through {@link #setInvListInfo}.
+ * When all pages are pre-loaded, {@link #moveTo} uses O(log n) binary search.
+ */
+public class WeightedOnDiskInvertedListCursor extends AbstractOnDiskInvertedListCursor {
+
+ static final int ELEMENT_SIZE = 8; // (docId:int32, weight:float)
+
+ private int bufferEndElementIx;
+ private double maxWeight;
+
+ public WeightedOnDiskInvertedListCursor(IBufferCache bufferCache, int fileId, ITypeTraits[] invListFields,
+ IHyracksTaskContext ctx, IIndexCursorStats stats, ITypeTraits nullTypeTraits,
+ INullIntrospector nullIntrospector) throws HyracksDataException {
+ super(bufferCache, fileId, invListFields, ctx, stats, nullTypeTraits, nullIntrospector);
+ }
+
+ @Override
+ public void setMaxWeight(double maxWeight) {
+ this.maxWeight = maxWeight;
+ }
+
+ @Override
+ public double getMaxWeight() {
+ return maxWeight;
+ }
+
+ @Override
+ protected void setInvListInfo(int startPageId, int endPageId, int startOff, int numElements)
+ throws HyracksDataException {
+ super.setInvListInfo(startPageId, endPageId, startOff, numElements);
+ this.currentOffsetForScan = startOff - ELEMENT_SIZE;
+ }
+
+ @Override
+ protected void setBlockInfo() {
+ super.setBlockInfo();
+ bufferEndElementIx = moreBlocksToRead ? computeBufferEndElementIx() : numElements - 1;
+ }
+
+ // ---- Sequential iteration ------------------------------------------------
+
+ @Override
+ public void doNext() throws HyracksDataException {
+ if (currentOffsetForScan + 2 * ELEMENT_SIZE > bufferCache.getPageSize()) {
+ currentPageIxForScan++;
+ currentOffsetForScan = 0;
+ } else {
+ currentOffsetForScan += ELEMENT_SIZE;
+ }
+ if (currentElementIxForScan > bufferEndElementIx && endPageId > bufferEndPageId) {
+ loadPages();
+ currentOffsetForScan = 0;
+ }
+ currentElementIxForScan++;
+ tuple.reset(buffers.get(currentPageIxForScan).array(), currentOffsetForScan);
+ }
+
+ // ---- Binary-search moveTo ------------------------------------------------
+
+ @Override
+ public boolean moveTo(int targetDocId) throws HyracksDataException {
+ if (moreBlocksToRead) {
+ return sequentialMoveTo(targetDocId);
+ }
+ int rank = binarySearch(targetDocId);
+ if (rank >= numElements) {
+ return false;
+ }
+ positionAt(rank);
+ return true;
+ }
+
+ private boolean sequentialMoveTo(int targetDocId) throws HyracksDataException {
+ while (hasNext()) {
+ next();
+ int docId = IntegerPointable.getInteger(Objects.requireNonNull(getTuple()).getFieldData(0),
+ getTuple().getFieldStart(0));
+ if (docId >= targetDocId) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ private int binarySearch(int targetDocId) {
+ int low = currentElementIxForScan;
+ int high = numElements;
+ while (low < high) {
+ int mid = (low + high) >>> 1;
+ if (readDocIdAtRank(mid) < targetDocId) {
+ low = mid + 1;
+ } else {
+ high = mid;
+ }
+ }
+ return low;
+ }
+
+ private int elemsOnFirstPage() {
+ return (bufferCache.getPageSize() - startOff) / ELEMENT_SIZE;
+ }
+
+ private int rankToPageIndex(int rank) {
+ int first = elemsOnFirstPage();
+ if (rank < first) {
+ return 0;
+ }
+ return 1 + (rank - first) / (bufferCache.getPageSize() / ELEMENT_SIZE);
+ }
+
+ private int rankToOffset(int rank) {
+ int pageSize = bufferCache.getPageSize();
+ int first = elemsOnFirstPage();
+ if (rank < first) {
+ return startOff + rank * ELEMENT_SIZE;
+ }
+ return ((rank - first) % (pageSize / ELEMENT_SIZE)) * ELEMENT_SIZE;
+ }
+
+ private int readDocIdAtRank(int rank) {
+ return IntegerPointable.getInteger(buffers.get(rankToPageIndex(rank)).array(), rankToOffset(rank));
+ }
+
+ private void positionAt(int rank) {
+ currentPageIxForScan = rankToPageIndex(rank);
+ currentOffsetForScan = rankToOffset(rank);
+ currentElementIxForScan = rank + 1;
+ tuple.reset(buffers.get(currentPageIxForScan).array(), currentOffsetForScan);
+ }
+
+ private int computeBufferEndElementIx() {
+ int pageSize = bufferCache.getPageSize();
+ int first = elemsOnFirstPage();
+ int extraPages = bufferEndPageId - startPageId;
+ return first + extraPages * (pageSize / ELEMENT_SIZE) - 1;
+ }
+
+ @Override
+ public boolean containsKey(ITupleReference searchTuple, MultiComparator invListCmp) throws HyracksDataException {
+ throw new UnsupportedOperationException("containsKey not supported for weighted inverted list cursor");
+ }
+
+ @Override
+ @SuppressWarnings("rawtypes")
+ public String printInvList(ISerializerDeserializer[] serdes) throws HyracksDataException {
+ int savedOff = currentOffsetForScan;
+ int savedPageIx = currentPageIxForScan;
+ int savedElemIx = currentElementIxForScan;
+ currentOffsetForScan = startOff - ELEMENT_SIZE;
+ currentPageIxForScan = 0;
+ currentElementIxForScan = 0;
+ StringBuilder sb = new StringBuilder();
+ while (hasNext()) {
+ next();
+ for (int i = 0; i < tuple.getFieldCount(); i++) {
+ ByteArrayInputStream inStream = new ByteArrayInputStream(tuple.getFieldData(i), tuple.getFieldStart(i),
+ tuple.getFieldLength(i));
+ DataInput dataIn = new DataInputStream(inStream);
+ sb.append(serdes[i].deserialize(dataIn));
+ if (i + 1 < tuple.getFieldCount()) {
+ sb.append(",");
+ }
+ }
+ sb.append(" ");
+ }
+ currentOffsetForScan = savedOff;
+ currentPageIxForScan = savedPageIx;
+ currentElementIxForScan = savedElemIx;
+ return sb.toString();
+ }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/AbstractTOccurrenceSearcher.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/AbstractTOccurrenceSearcher.java
index aa6f7c1..4c331a0 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/AbstractTOccurrenceSearcher.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/AbstractTOccurrenceSearcher.java
@@ -27,6 +27,7 @@
import org.apache.hyracks.api.comm.IFrameTupleAccessor;
import org.apache.hyracks.api.context.IHyracksTaskContext;
import org.apache.hyracks.api.dataflow.value.ISerializerDeserializer;
+import org.apache.hyracks.api.dataflow.value.ITypeTraits;
import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
import org.apache.hyracks.api.exceptions.ErrorCode;
import org.apache.hyracks.api.exceptions.HyracksDataException;
@@ -40,6 +41,7 @@
import org.apache.hyracks.dataflow.common.utils.TaskUtil;
import org.apache.hyracks.dataflow.std.buffermanager.BufferManagerBackedVSizeFrame;
import org.apache.hyracks.dataflow.std.buffermanager.ISimpleFrameBufferManager;
+import org.apache.hyracks.storage.am.common.api.INullIntrospector;
import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInPlaceInvertedIndex;
import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedIndexSearcher;
import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedListCursor;
@@ -103,7 +105,7 @@
if (bufferManager == null) {
throw HyracksDataException.create(ErrorCode.CANNOT_CONTINUE_TEXT_SEARCH_BUFFER_MANAGER_IS_NULL);
}
- this.finalSearchResult = new InvertedIndexFinalSearchResult(invIndex.getInvListTypeTraits(), ctx, bufferManager,
+ this.finalSearchResult = createFinalSearchResult(invIndex.getInvListTypeTraits(), ctx, bufferManager,
invIndex.getNullTypeTraits(), invIndex.getNullIntrospector());
this.invListMerger = new InvertedListMerger(ctx, invIndex, bufferManager);
this.invListCmp = MultiComparator.create(invIndex.getInvListCmpFactories());
@@ -118,10 +120,9 @@
this.queryTokenAppender = new FrameTupleAppenderAccessor(QUERY_TOKEN_REC_DESC);
this.queryTokenAppender.reset(queryTokenFrame, true);
this.isSingleInvertedList = false;
- this.searchResultTuple = InvertedIndexUtils.createInvertedListTupleReference(invIndex.getInvListTypeTraits(),
- invIndex.getNullTypeTraits());
- this.searchResultFta = InvertedIndexUtils.createInvertedListFrameTupleAccessor(ctx.getInitialFrameSize(),
- invIndex.getInvListTypeTraits(), invIndex.getNullTypeTraits(), invIndex.getNullIntrospector());
+ this.searchResultTuple = createSearchResultTuple(invIndex.getInvListTypeTraits(), invIndex.getNullTypeTraits());
+ this.searchResultFta = createSearchResultAccessor(ctx.getInitialFrameSize(), invIndex.getInvListTypeTraits(),
+ invIndex.getNullTypeTraits(), invIndex.getNullIntrospector());
}
protected void tokenizeQuery(InvertedIndexSearchPredicate searchPred) throws HyracksDataException {
@@ -296,4 +297,22 @@
singleInvListCursor = null;
}
+ protected InvertedIndexFinalSearchResult createFinalSearchResult(ITypeTraits[] invListTypeTraits,
+ IHyracksTaskContext ctx, ISimpleFrameBufferManager bufferManager, ITypeTraits nullTypeTraits,
+ INullIntrospector nullIntrospector) throws HyracksDataException {
+ return new InvertedIndexFinalSearchResult(invListTypeTraits, ctx, bufferManager, nullTypeTraits,
+ nullIntrospector);
+ }
+
+ protected IInvertedListTupleReference createSearchResultTuple(ITypeTraits[] invListTypeTraits,
+ ITypeTraits nullTypeTraits) throws HyracksDataException {
+ return InvertedIndexUtils.createInvertedListTupleReference(invListTypeTraits, nullTypeTraits);
+ }
+
+ protected IFrameTupleAccessor createSearchResultAccessor(int frameSize, ITypeTraits[] invListTypeTraits,
+ ITypeTraits nullTypeTraits, INullIntrospector nullIntrospector) throws HyracksDataException {
+ return InvertedIndexUtils.createInvertedListFrameTupleAccessor(frameSize, invListTypeTraits, nullTypeTraits,
+ nullIntrospector);
+ }
+
}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/DotProductSearchModifier.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/DotProductSearchModifier.java
new file mode 100644
index 0000000..cf334d7
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/DotProductSearchModifier.java
@@ -0,0 +1,64 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hyracks.storage.am.lsm.invertedindex.search;
+
+import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedIndexSearchModifier;
+
+/**
+ * Search modifier for WAND (Weak AND) dot-product top-k queries on sparse-vector indexes.
+ */
+public class DotProductSearchModifier implements IInvertedIndexSearchModifier {
+
+ private final double scoreThreshold;
+ private final int topK;
+
+ public DotProductSearchModifier(double scoreThreshold, int topK) {
+ this.scoreThreshold = scoreThreshold;
+ this.topK = topK;
+ }
+
+ @Override
+ public int getOccurrenceThreshold(int numQueryTokens) {
+ return 1;
+ }
+
+ @Override
+ public int getNumPrefixLists(int occurrenceThreshold, int numInvLists) {
+ return numInvLists;
+ }
+
+ @Override
+ public short getNumTokensLowerBound(short numQueryTokens) {
+ return -1;
+ }
+
+ @Override
+ public short getNumTokensUpperBound(short numQueryTokens) {
+ return Short.MAX_VALUE;
+ }
+
+ public double getScoreThreshold() {
+ return scoreThreshold;
+ }
+
+ public int getTopK() {
+ return topK;
+ }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/DotProductSearchModifierFactory.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/DotProductSearchModifierFactory.java
new file mode 100644
index 0000000..c710239
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/DotProductSearchModifierFactory.java
@@ -0,0 +1,44 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hyracks.storage.am.lsm.invertedindex.search;
+
+import java.io.Serial;
+import java.io.Serializable;
+
+import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedIndexSearchModifier;
+import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedIndexSearchModifierFactory;
+
+public class DotProductSearchModifierFactory implements IInvertedIndexSearchModifierFactory, Serializable {
+ @Serial
+ private static final long serialVersionUID = 1L;
+
+ private final double scoreThreshold;
+ private final int topK;
+
+ public DotProductSearchModifierFactory(double scoreThreshold, int topK) {
+ this.scoreThreshold = scoreThreshold;
+ this.topK = topK;
+ }
+
+ @Override
+ public IInvertedIndexSearchModifier createSearchModifier() {
+ return new DotProductSearchModifier(scoreThreshold, topK);
+ }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/InvertedListMerger.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/InvertedListMerger.java
index 8bf16fb..79d09c4 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/InvertedListMerger.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/InvertedListMerger.java
@@ -20,13 +20,17 @@
package org.apache.hyracks.storage.am.lsm.invertedindex.search;
import java.nio.ByteBuffer;
+import java.util.Arrays;
import java.util.Collections;
+import java.util.Comparator;
import java.util.List;
+import java.util.PriorityQueue;
import org.apache.hyracks.api.comm.IFrameTupleAccessor;
import org.apache.hyracks.api.context.IHyracksTaskContext;
import org.apache.hyracks.api.exceptions.ErrorCode;
import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.data.std.primitive.FloatPointable;
import org.apache.hyracks.data.std.primitive.IntegerPointable;
import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
import org.apache.hyracks.dataflow.std.buffermanager.ISimpleFrameBufferManager;
@@ -45,6 +49,7 @@
PREFIX_LIST,
SUFFIX_LIST_PROBE,
SUFFIX_LIST_SCAN,
+ WAND_SCORE,
NONE
}
@@ -205,6 +210,9 @@
doneMerge = mergeSuffixListScan(finalInvListCursor, prevSearchResult, finalSearchResult, invListIdx,
numInvertedLists, occurrenceThreshold, isProcessingFinalList);
break;
+ case WAND_SCORE:
+ doneMerge = continueMergeWAND();
+ break;
default:
throw HyracksDataException.create(ErrorCode.UNDEFINED_INVERTED_LIST_MERGE_TYPE);
}
@@ -579,6 +587,230 @@
if (finalInvListCursor != null) {
finalInvListCursor.close();
}
+ closeWANDCursors();
+ }
+ }
+
+ // WAND (Weak AND) merge support
+
+ protected List<IInvertedListCursor> wandCursors;
+ protected double[] wandQueryWeights;
+ protected double[] wandMaxWeights;
+ protected double wandThreshold;
+ protected int wandTopK;
+ protected PriorityQueue<Double> wandTopKHeap;
+ protected int[] wandSortedIdx;
+ protected int[] wandCurrentDocId;
+ protected double[] wandCurrentWeight;
+ protected boolean wandInitialized = false;
+
+ public boolean mergeWAND(List<IInvertedListCursor> invListCursors, double[] queryWeights, double[] maxWeights,
+ double threshold, int topK, InvertedIndexFinalSearchResult finalSearchResult) throws HyracksDataException {
+ this.wandCursors = invListCursors;
+ this.wandQueryWeights = queryWeights;
+ this.wandMaxWeights = maxWeights;
+ this.wandThreshold = threshold;
+ this.wandTopK = topK;
+ this.finalSearchResult = finalSearchResult;
+
+ int numCursors = invListCursors.size();
+ wandSortedIdx = new int[numCursors];
+ wandCurrentDocId = new int[numCursors];
+ wandCurrentWeight = new double[numCursors];
+ if (topK > 0) {
+ wandTopKHeap = new PriorityQueue<>();
+ }
+
+ for (int i = 0; i < numCursors; i++) {
+ wandSortedIdx[i] = i;
+ IInvertedListCursor cursor = invListCursors.get(i);
+ cursor.prepareLoadPages();
+ cursor.loadPages();
+ fetchNextDocumentFromCursor(i, cursor);
+ }
+ // Initial sort — data is unsorted, use O(n log n).
+ initWANDCursorOrder();
+
+ listVisited = true;
+ currentProcessType = processType.WAND_SCORE;
+ isProcessingFinalList = true;
+ wandInitialized = true;
+
+ finalSearchResult.resetBuffer();
+ return doWANDLoop();
+ }
+
+ private void fetchNextDocumentFromCursor(int i, IInvertedListCursor cursor) throws HyracksDataException {
+ if (cursor.hasNext()) {
+ cursor.next();
+ ITupleReference tuple = cursor.getTuple();
+ wandCurrentDocId[i] = readDocId(tuple);
+ wandCurrentWeight[i] = readWeight(tuple);
+ } else {
+ wandCurrentDocId[i] = Integer.MAX_VALUE;
+ wandCurrentWeight[i] = 0.0;
+ }
+ }
+
+ public boolean continueMergeWAND() throws HyracksDataException {
+ if (!wandInitialized) {
+ throw new HyracksDataException("WAND merge not initialized");
+ }
+ finalSearchResult.resetBuffer();
+ return doWANDLoop();
+ }
+
+ protected boolean doWANDLoop() throws HyracksDataException {
+ int numCursors = wandCursors.size();
+
+ while (true) {
+ sortWANDCursorsByDocId();
+
+ double scoreUpperBound = 0.0;
+ int pivotIdx = -1;
+ int pivotDocId = Integer.MAX_VALUE;
+ for (int i = 0; i < numCursors; i++) {
+ int cursorIdx = wandSortedIdx[i];
+ if (wandCurrentDocId[cursorIdx] == Integer.MAX_VALUE) {
+ break;
+ }
+ scoreUpperBound += wandQueryWeights[cursorIdx] * wandMaxWeights[cursorIdx];
+ if (scoreUpperBound >= wandThreshold) {
+ pivotIdx = i;
+ pivotDocId = wandCurrentDocId[cursorIdx];
+ break;
+ }
+ }
+
+ if (pivotIdx < 0) {
+ isProcessingFinished = true;
+ return true;
+ }
+
+ if (wandCurrentDocId[wandSortedIdx[0]] == pivotDocId) {
+ double score = 0.0;
+ for (int i = 0; i < numCursors; i++) {
+ int cursorIdx = wandSortedIdx[i];
+ if (wandCurrentDocId[cursorIdx] != pivotDocId) {
+ break;
+ }
+ score += wandQueryWeights[cursorIdx] * wandCurrentWeight[cursorIdx];
+ }
+
+ if (score >= wandThreshold) {
+ ITupleReference tuple = wandCursors.get(wandSortedIdx[0]).getTuple();
+ if (!finalSearchResult.append(tuple, 1)) {
+ return false;
+ }
+ if (wandTopK > 0) {
+ wandTopKHeap.offer(score);
+ if (wandTopKHeap.size() > wandTopK) {
+ wandTopKHeap.poll();
+ }
+ if (wandTopKHeap.size() == wandTopK) {
+ wandThreshold = Math.max(wandThreshold, wandTopKHeap.peek());
+ }
+ }
+ }
+
+ for (int i = 0; i < numCursors; i++) {
+ int cursorIdx = wandSortedIdx[i];
+ if (wandCurrentDocId[cursorIdx] != pivotDocId) {
+ break;
+ }
+ advanceWANDCursor(cursorIdx);
+ }
+ } else {
+ for (int i = 0; i < pivotIdx; i++) {
+ advanceWANDCursorTo(wandSortedIdx[i], pivotDocId);
+ }
+ }
+ }
+ }
+
+ private void advanceWANDCursor(int cursorIdx) throws HyracksDataException {
+ IInvertedListCursor cursor = wandCursors.get(cursorIdx);
+ if (cursor.hasNext()) {
+ cursor.next();
+ ITupleReference tuple = cursor.getTuple();
+ wandCurrentDocId[cursorIdx] = readDocId(tuple);
+ wandCurrentWeight[cursorIdx] = readWeight(tuple);
+ } else {
+ exhaustWANDCursor(cursorIdx, cursor);
+ }
+ }
+
+ private void advanceWANDCursorTo(int cursorIdx, int targetDocId) throws HyracksDataException {
+ if (wandCurrentDocId[cursorIdx] == Integer.MAX_VALUE) {
+ return;
+ }
+ IInvertedListCursor cursor = wandCursors.get(cursorIdx);
+ if (!cursor.moveTo(targetDocId)) {
+ exhaustWANDCursor(cursorIdx, cursor);
+ return;
+ }
+ ITupleReference tuple = cursor.getTuple();
+ wandCurrentDocId[cursorIdx] = readDocId(tuple);
+ wandCurrentWeight[cursorIdx] = readWeight(tuple);
+ }
+
+ private void exhaustWANDCursor(int cursorIdx, IInvertedListCursor cursor) throws HyracksDataException {
+ wandCurrentDocId[cursorIdx] = Integer.MAX_VALUE;
+ wandCurrentWeight[cursorIdx] = 0.0;
+ wandMaxWeights[cursorIdx] = 0.0;
+ try {
+ cursor.unloadPages();
+ } finally {
+ cursor.close();
+ }
+ }
+
+ private void initWANDCursorOrder() {
+ int n = wandSortedIdx.length;
+ Integer[] order = new Integer[n];
+ Arrays.setAll(order, i -> i);
+ Arrays.sort(order, Comparator.comparingInt(i -> wandCurrentDocId[i]));
+ for (int i = 0; i < n; i++) {
+ wandSortedIdx[i] = order[i];
+ }
+ }
+
+ private void sortWANDCursorsByDocId() {
+ int n = wandSortedIdx.length;
+ for (int i = 1; i < n; i++) {
+ int key = wandSortedIdx[i];
+ int j = i - 1;
+ while (j >= 0 && wandCurrentDocId[wandSortedIdx[j]] > wandCurrentDocId[key]) {
+ wandSortedIdx[j + 1] = wandSortedIdx[j];
+ j--;
+ }
+ wandSortedIdx[j + 1] = key;
+ }
+ }
+
+ private int readDocId(ITupleReference tuple) {
+ return IntegerPointable.getInteger(tuple.getFieldData(0), tuple.getFieldStart(0));
+ }
+
+ private float readWeight(ITupleReference tuple) {
+ int lastField = tuple.getFieldCount() - 1;
+ return FloatPointable.getFloat(tuple.getFieldData(lastField), tuple.getFieldStart(lastField));
+ }
+
+ private void closeWANDCursors() throws HyracksDataException {
+ if (wandCursors == null) {
+ return;
+ }
+ for (int i = 0; i < wandCursors.size(); i++) {
+ if (wandCurrentDocId != null && wandCurrentDocId[i] == Integer.MAX_VALUE) {
+ continue;
+ }
+ IInvertedListCursor cursor = wandCursors.get(i);
+ try {
+ cursor.unloadPages();
+ } finally {
+ cursor.close();
+ }
}
}
@@ -604,6 +836,16 @@
isProcessingFinished = false;
listVisited = false;
occurrenceThreshold = 0;
+ wandCursors = null;
+ wandQueryWeights = null;
+ wandMaxWeights = null;
+ wandThreshold = 0.0;
+ wandTopK = 0;
+ wandTopKHeap = null;
+ wandSortedIdx = null;
+ wandCurrentDocId = null;
+ wandCurrentWeight = null;
+ wandInitialized = false;
}
}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WANDSearchResult.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WANDSearchResult.java
new file mode 100644
index 0000000..a614612
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WANDSearchResult.java
@@ -0,0 +1,89 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hyracks.storage.am.lsm.invertedindex.search;
+
+import org.apache.hyracks.api.context.IHyracksTaskContext;
+import org.apache.hyracks.api.dataflow.value.ITypeTraits;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
+import org.apache.hyracks.dataflow.std.buffermanager.ISimpleFrameBufferManager;
+import org.apache.hyracks.storage.am.common.api.INullIntrospector;
+
+/**
+ * Final search result for WAND dot-product queries on sparse-vector indexes.
+ * <p>
+ * The inverted list element schema is {@code [primaryKeyFields..., weight]}.
+ * This result strips the trailing {@code weight} field so downstream operators
+ * (e.g. UNNEST_MAP) receive only primary-key tuples.
+ */
+public class WANDSearchResult extends InvertedIndexFinalSearchResult {
+
+ public WANDSearchResult(ITypeTraits[] invListFields, IHyracksTaskContext ctx,
+ ISimpleFrameBufferManager bufferManager, ITypeTraits nullTypeTraits, INullIntrospector nullIntrospector)
+ throws HyracksDataException {
+ super(invListFields, ctx, bufferManager, nullTypeTraits, nullIntrospector);
+ }
+
+ /**
+ * Strip the trailing weight field so the result contains only primary-key fields.
+ */
+ @Override
+ protected void initTypeTraits(ITypeTraits[] invListFields) {
+ int numPKFields = invListFields.length - 1;
+ typeTraits = new ITypeTraits[numPKFields];
+ System.arraycopy(invListFields, 0, typeTraits, 0, numPKFields);
+ }
+
+ /**
+ * Append only the primary-key fields of {@code invListElement}, skipping the last (weight) field.
+ *
+ * @return false when the frame is full; true on successful append.
+ */
+ @Override
+ public boolean append(ITupleReference invListElement, int count) throws HyracksDataException {
+ int numPKFields = typeTraits.length;
+
+ int numBytesRequired;
+ if (typeTraits[0].isFixedLength()) {
+ numBytesRequired = 0;
+ for (int i = 0; i < numPKFields; i++) {
+ numBytesRequired += invListElement.getFieldLength(i);
+ }
+ } else {
+ numBytesRequired = tupleWriter.bytesRequired(invListElement, 0, numPKFields);
+ }
+
+ if (!appender.hasSpace(numBytesRequired)) {
+ return false;
+ }
+
+ if (typeTraits[0].isFixedLength()) {
+ // For fixed-size tuples all PK fields are contiguous starting at field 0.
+ appender.append(invListElement.getFieldData(0), invListElement.getFieldStart(0), numBytesRequired);
+ } else {
+ tupleWriter.writeTupleFields(invListElement, 0, numPKFields, tempBytes, 0);
+ appender.append(tempBytes, 0, numBytesRequired);
+ }
+
+ appender.incrementTupleCount(1);
+ numResults++;
+ return true;
+ }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WANDSearcher.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WANDSearcher.java
new file mode 100644
index 0000000..077aa2e
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WANDSearcher.java
@@ -0,0 +1,148 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hyracks.storage.am.lsm.invertedindex.search;
+
+import java.util.ArrayList;
+
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.api.context.IHyracksTaskContext;
+import org.apache.hyracks.api.dataflow.value.ITypeTraits;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.std.buffermanager.ISimpleFrameBufferManager;
+import org.apache.hyracks.storage.am.common.api.IIndexOperationContext;
+import org.apache.hyracks.storage.am.common.api.INullIntrospector;
+import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInPlaceInvertedIndex;
+import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedListCursor;
+import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedListTupleReference;
+import org.apache.hyracks.storage.am.lsm.invertedindex.util.InvertedIndexUtils;
+import org.apache.hyracks.storage.common.IIndexCursor;
+
+/**
+ * Conducts WAND (Weak AND) top-k dot-product searches on sparse-vector inverted indexes.
+ * <p>
+ * Each posting list stores {@code (docId, weight)} pairs keyed by dimension. The algorithm
+ * uses per-list {@code maxWeight} upper bounds to skip documents that cannot make the top-k.
+ */
+public class WANDSearcher extends AbstractTOccurrenceSearcher {
+
+ protected final ArrayList<IInvertedListCursor> invListCursors = new ArrayList<>();
+
+ public WANDSearcher(IInPlaceInvertedIndex invIndex, IHyracksTaskContext ctx) throws HyracksDataException {
+ super(invIndex, ctx);
+ }
+
+ @Override
+ protected InvertedIndexFinalSearchResult createFinalSearchResult(ITypeTraits[] invListTypeTraits,
+ IHyracksTaskContext ctx, ISimpleFrameBufferManager bufferManager, ITypeTraits nullTypeTraits,
+ INullIntrospector nullIntrospector) throws HyracksDataException {
+ return new WANDSearchResult(invListTypeTraits, ctx, bufferManager, nullTypeTraits, nullIntrospector);
+ }
+
+ @Override
+ protected IInvertedListTupleReference createSearchResultTuple(ITypeTraits[] invListTypeTraits,
+ ITypeTraits nullTypeTraits) throws HyracksDataException {
+ // WAND strips the trailing weight field, so the result tuple uses PK-only type traits.
+ int numPKFields = invListTypeTraits.length - 1;
+ ITypeTraits[] pkTypeTraits = new ITypeTraits[numPKFields];
+ System.arraycopy(invListTypeTraits, 0, pkTypeTraits, 0, numPKFields);
+ return InvertedIndexUtils.createInvertedListTupleReference(pkTypeTraits, nullTypeTraits);
+ }
+
+ @Override
+ protected IFrameTupleAccessor createSearchResultAccessor(int frameSize, ITypeTraits[] invListTypeTraits,
+ ITypeTraits nullTypeTraits, INullIntrospector nullIntrospector) throws HyracksDataException {
+ int numPKFields = invListTypeTraits.length - 1;
+ ITypeTraits[] pkTypeTraits = new ITypeTraits[numPKFields];
+ System.arraycopy(invListTypeTraits, 0, pkTypeTraits, 0, numPKFields);
+ return InvertedIndexUtils.createInvertedListFrameTupleAccessor(frameSize, pkTypeTraits, nullTypeTraits,
+ nullIntrospector);
+ }
+
+ @Override
+ public void search(IIndexCursor resultCursor, InvertedIndexSearchPredicate searchPred, IIndexOperationContext ictx)
+ throws HyracksDataException {
+ if (!(searchPred instanceof WandSearchPredicate wandPred)) {
+ throw new HyracksDataException("WANDSearcher requires a WandSearchPredicate");
+ }
+
+ prepareSearch();
+ tokenizeQuery(searchPred);
+ int numQueryTokens = queryTokenAppender.getTupleCount();
+
+ invListCursors.clear();
+ invListCursorCache.reset();
+ double[] maxWeights = new double[numQueryTokens];
+ try {
+ for (int i = 0; i < numQueryTokens; i++) {
+ searchKey.reset(queryTokenAppender, i);
+ IInvertedListCursor invListCursor = invListCursorFactory.create();
+ invIndex.openInvertedListCursor(invListCursor, searchKey, ictx);
+ maxWeights[i] = invListCursor.getMaxWeight();
+ invListCursors.add(invListCursor);
+ }
+ } catch (HyracksDataException e) {
+ for (IInvertedListCursor cursor : invListCursors) {
+ try {
+ cursor.unloadPages();
+ } finally {
+ cursor.close();
+ }
+ }
+ throw e;
+ }
+
+ double[] queryWeights = wandPred.getQueryWeights();
+ if (queryWeights == null || queryWeights.length != numQueryTokens) {
+ queryWeights = new double[numQueryTokens];
+ java.util.Arrays.fill(queryWeights, 1.0);
+ }
+ double threshold = wandPred.getScoreThreshold();
+ int topK = wandPred.getTopK();
+
+ finalSearchResult.reset();
+ isFinishedSearch =
+ invListMerger.mergeWAND(invListCursors, queryWeights, maxWeights, threshold, topK, finalSearchResult);
+ searchResultBuffer = finalSearchResult.getNextFrame();
+ searchResultTupleIndex = 0;
+ searchResultFta.reset(searchResultBuffer);
+
+ if (isFinishedSearch) {
+ invListMerger.close();
+ finalSearchResult.finalizeWrite();
+ }
+ resultCursor.open(null, searchPred);
+ }
+
+ @Override
+ public boolean continueSearch() throws HyracksDataException {
+ if (isFinishedSearch) {
+ return true;
+ }
+ isFinishedSearch = invListMerger.continueMergeWAND();
+ searchResultBuffer = finalSearchResult.getNextFrame();
+ searchResultTupleIndex = 0;
+ searchResultFta.reset(searchResultBuffer);
+ if (isFinishedSearch) {
+ invListMerger.close();
+ finalSearchResult.finalizeWrite();
+ }
+ return isFinishedSearch;
+ }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WandSearchPredicate.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WandSearchPredicate.java
new file mode 100644
index 0000000..6b02992
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WandSearchPredicate.java
@@ -0,0 +1,60 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hyracks.storage.am.lsm.invertedindex.search;
+
+import java.io.Serial;
+
+import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
+import org.apache.hyracks.storage.am.lsm.invertedindex.fulltext.IFullTextConfigEvaluator;
+import org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers.IBinaryTokenizer;
+
+/**
+ * Search predicate for WAND (Weak AND) dot-product top-k queries.
+ */
+public class WandSearchPredicate extends InvertedIndexSearchPredicate {
+
+ @Serial
+ private static final long serialVersionUID = 1L;
+
+ private double[] queryWeights;
+
+ public WandSearchPredicate(IBinaryTokenizer queryTokenizer, IFullTextConfigEvaluator fullTextConfigEvaluator,
+ DotProductSearchModifier searchModifier, ITupleReference minFilterTuple, ITupleReference maxFilterTuple,
+ boolean isFullTextSearchQuery) {
+ super(queryTokenizer, fullTextConfigEvaluator, searchModifier, minFilterTuple, maxFilterTuple,
+ isFullTextSearchQuery);
+ }
+
+ public void setQueryWeights(double[] queryWeights) {
+ this.queryWeights = queryWeights;
+ }
+
+ public double[] getQueryWeights() {
+ return queryWeights;
+ }
+
+ public double getScoreThreshold() {
+ return ((DotProductSearchModifier) getSearchModifier()).getScoreThreshold();
+ }
+
+ public int getTopK() {
+ return ((DotProductSearchModifier) getSearchModifier()).getTopK();
+ }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/tokenizers/IWeightedToken.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/tokenizers/IWeightedToken.java
new file mode 100644
index 0000000..b9da42d
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/tokenizers/IWeightedToken.java
@@ -0,0 +1,34 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers;
+
+/**
+ * A token that carries a numeric weight alongside its dimension index.
+ * <p>
+ * Used for sparse-vector indexes where each posting stores (int64 dimension, float32 weight).
+ */
+public interface IWeightedToken {
+
+ /** Dimension index; serialized as int64 (BTree key). */
+ long getIndex();
+
+ /** Posting weight; caller writes {@code (float) getWeight()} to disk. */
+ double getWeight();
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/util/InvertedIndexTokenizingTupleIterator.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/util/InvertedIndexTokenizingTupleIterator.java
index 19d6f11..45097a9 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/util/InvertedIndexTokenizingTupleIterator.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/util/InvertedIndexTokenizingTupleIterator.java
@@ -28,6 +28,7 @@
import org.apache.hyracks.storage.am.lsm.invertedindex.fulltext.IFullTextConfigEvaluator;
import org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers.IBinaryTokenizer;
import org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers.IToken;
+import org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers.IWeightedToken;
// TODO: We can possibly avoid copying the data into a new tuple here.
public class InvertedIndexTokenizingTupleIterator {
@@ -35,8 +36,8 @@
protected final int DOC_FIELD_INDEX = 0;
protected final int invListFieldCount;
- protected final ArrayTupleBuilder tupleBuilder;
- protected final ArrayTupleReference tupleReference;
+ protected ArrayTupleBuilder tupleBuilder;
+ protected ArrayTupleReference tupleReference;
protected final IFullTextConfigEvaluator fullTextConfigEvaluator;
protected ITupleReference inputTuple;
@@ -65,6 +66,10 @@
fullTextConfigEvaluator.next();
IToken token = fullTextConfigEvaluator.getToken();
+ int requiredCapacity = 1 + invListFieldCount + (token instanceof IWeightedToken ? 1 : 0);
+ if (tupleBuilder.getFieldEndOffsets().length < requiredCapacity) {
+ tupleBuilder = new ArrayTupleBuilder(requiredCapacity);
+ }
tupleBuilder.reset();
try {
// Add token field.
@@ -74,6 +79,16 @@
}
tupleBuilder.addFieldEndOffset();
+ // Add weight field if the token carries a weight.
+ if (token instanceof IWeightedToken wt) {
+ try {
+ tupleBuilder.getDataOutput().writeFloat((float) wt.getWeight());
+ } catch (IOException e) {
+ throw HyracksDataException.create(e);
+ }
+ tupleBuilder.addFieldEndOffset();
+ }
+
// Add inverted-list element fields.
for (int i = 0; i < invListFieldCount; i++) {
tupleBuilder.addField(inputTuple.getFieldData(i + 1), inputTuple.getFieldStart(i + 1),
diff --git a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/pom.xml b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/pom.xml
index 6d17134..d429f54 100644
--- a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/pom.xml
+++ b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/pom.xml
@@ -137,6 +137,11 @@
<artifactId>guava</artifactId>
<scope>test</scope>
</dependency>
+ <dependency>
+ <groupId>org.mockito</groupId>
+ <artifactId>mockito-core</artifactId>
+ <scope>test</scope>
+ </dependency>
</dependencies>
</project>
diff --git a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedIndexMaxWeightTest.java b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedIndexMaxWeightTest.java
new file mode 100644
index 0000000..23239d1
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/inmemory/InMemoryInvertedIndexMaxWeightTest.java
@@ -0,0 +1,166 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.hyracks.storage.am.lsm.invertedindex.inmemory;
+
+import java.lang.reflect.Method;
+
+import org.apache.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import org.apache.hyracks.api.dataflow.value.ITypeTraits;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.data.std.accessors.FloatBinaryComparatorFactory;
+import org.apache.hyracks.data.std.accessors.IntegerBinaryComparatorFactory;
+import org.apache.hyracks.data.std.primitive.FloatPointable;
+import org.apache.hyracks.data.std.primitive.IntegerPointable;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
+import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedListCursor;
+import org.apache.hyracks.storage.am.lsm.invertedindex.common.LSMInvertedIndexTestHarness;
+import org.junit.After;
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests per-dimension maxWeight tracking and propagation in {@link InMemoryInvertedIndex}.
+ */
+public class InMemoryInvertedIndexMaxWeightTest {
+
+ private LSMInvertedIndexTestHarness harness;
+ private InMemoryInvertedIndex index;
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness = new LSMInvertedIndexTestHarness();
+ harness.setUp();
+
+ ITypeTraits[] tokenTypeTraits = new ITypeTraits[] { IntegerPointable.TYPE_TRAITS };
+ IBinaryComparatorFactory[] tokenCmpFactories =
+ new IBinaryComparatorFactory[] { IntegerBinaryComparatorFactory.INSTANCE };
+ ITypeTraits[] invListTypeTraits =
+ new ITypeTraits[] { IntegerPointable.TYPE_TRAITS, FloatPointable.TYPE_TRAITS };
+ IBinaryComparatorFactory[] invListCmpFactories = new IBinaryComparatorFactory[] {
+ IntegerBinaryComparatorFactory.INSTANCE, FloatBinaryComparatorFactory.INSTANCE };
+
+ index = new InMemoryInvertedIndex(harness.getVirtualBufferCaches().getFirst(),
+ new org.apache.hyracks.storage.am.lsm.common.freepage.VirtualFreePageManager(
+ harness.getVirtualBufferCaches().getFirst()),
+ invListTypeTraits, invListCmpFactories, tokenTypeTraits, tokenCmpFactories, null, null,
+ harness.getIOManager().resolveAbsolutePath(harness.getOnDiskDir()), null, null);
+ index.create();
+ index.activate();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ if (index != null) {
+ index.deactivate();
+ index.destroy();
+ }
+ harness.tearDown();
+ }
+
+ @Test
+ public void testUpdateMaxWeightAndGet() throws Exception {
+ Method updateMaxWeight =
+ InMemoryInvertedIndex.class.getDeclaredMethod("updateMaxWeight", ITupleReference.class);
+ updateMaxWeight.setAccessible(true);
+
+ // Dimension 7, weight 3.5
+ updateMaxWeight.invoke(index, makeTuple(7, 3.5f));
+ Assert.assertEquals(3.5, index.getMaxWeight(7), 1e-9);
+
+ // Same dimension, lower weight — max stays 3.5
+ updateMaxWeight.invoke(index, makeTuple(7, 2.0f));
+ Assert.assertEquals(3.5, index.getMaxWeight(7), 1e-9);
+
+ // Same dimension, higher weight — max updates
+ updateMaxWeight.invoke(index, makeTuple(7, 5.0f));
+ Assert.assertEquals(5.0, index.getMaxWeight(7), 1e-9);
+
+ // Different dimension
+ updateMaxWeight.invoke(index, makeTuple(42, 1.0f));
+ Assert.assertEquals(1.0, index.getMaxWeight(42), 1e-9);
+ }
+
+ @Test
+ public void testMaxWeightDefaultsToZero() {
+ Assert.assertEquals(0.0, index.getMaxWeight(999), 1e-9);
+ }
+
+ @Test
+ public void testClearResetsMaxWeight() throws Exception {
+ Method updateMaxWeight =
+ InMemoryInvertedIndex.class.getDeclaredMethod("updateMaxWeight", ITupleReference.class);
+ updateMaxWeight.setAccessible(true);
+ updateMaxWeight.invoke(index, makeTuple(7, 3.5f));
+ Assert.assertEquals(3.5, index.getMaxWeight(7), 1e-9);
+
+ index.clear();
+ Assert.assertEquals(0.0, index.getMaxWeight(7), 1e-9);
+ }
+
+ @Test
+ public void testOpenCursorPropagatesMaxWeight() throws Exception {
+ Method updateMaxWeight =
+ InMemoryInvertedIndex.class.getDeclaredMethod("updateMaxWeight", ITupleReference.class);
+ updateMaxWeight.setAccessible(true);
+ updateMaxWeight.invoke(index, makeTuple(7, 3.5f));
+
+ InMemoryInvertedIndexOpContext opCtx = new InMemoryInvertedIndexOpContext(index.getBTree(),
+ new IBinaryComparatorFactory[] { IntegerBinaryComparatorFactory.INSTANCE }, null, null);
+ opCtx.setOperation(org.apache.hyracks.storage.am.common.ophelpers.IndexOperation.SEARCH);
+
+ ArrayTupleBuilder keyBuilder = new ArrayTupleBuilder(1);
+ keyBuilder.getDataOutput().writeInt(7);
+ keyBuilder.addFieldEndOffset();
+ ArrayTupleReference searchKey = new ArrayTupleReference();
+ searchKey.reset(keyBuilder.getFieldEndOffsets(), keyBuilder.getByteArray());
+
+ IInvertedListCursor cursor = index.createInvertedListCursor(null);
+ index.openInvertedListCursor(cursor, searchKey, opCtx);
+ Assert.assertEquals(3.5, cursor.getMaxWeight(), 1e-9);
+
+ cursor.close();
+ opCtx.destroy();
+ }
+
+ @Test
+ public void testUnsupportedTokenTypeThrows() throws Exception {
+ Method updateMaxWeight =
+ InMemoryInvertedIndex.class.getDeclaredMethod("updateMaxWeight", ITupleReference.class);
+ updateMaxWeight.setAccessible(true);
+
+ updateMaxWeight.invoke(index, makeTuple(1, 1.0f));
+ Assert.assertEquals(1.0, index.getMaxWeight(1), 1e-9);
+ }
+
+ private ITupleReference makeTuple(int dimIndex, float weight) throws Exception {
+ ArrayTupleBuilder builder = new ArrayTupleBuilder(3);
+ builder.getDataOutput().writeInt(dimIndex);
+ builder.addFieldEndOffset();
+ builder.getDataOutput().writeInt(100); // dummy docId
+ builder.addFieldEndOffset();
+ builder.getDataOutput().writeFloat(weight);
+ builder.addFieldEndOffset();
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ tuple.reset(builder.getFieldEndOffsets(), builder.getByteArray());
+ return tuple;
+ }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/WeightedOnDiskInvertedListCursorMoveToTest.java b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/WeightedOnDiskInvertedListCursorMoveToTest.java
new file mode 100644
index 0000000..e4a8dae
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/WeightedOnDiskInvertedListCursorMoveToTest.java
@@ -0,0 +1,172 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.hyracks.storage.am.lsm.invertedindex.ondisk;
+
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Objects;
+
+import org.apache.hyracks.api.context.IHyracksTaskContext;
+import org.apache.hyracks.api.dataflow.value.ITypeTraits;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.data.std.primitive.FloatPointable;
+import org.apache.hyracks.data.std.primitive.IntegerPointable;
+import org.apache.hyracks.dataflow.std.buffermanager.ISimpleFrameBufferManager;
+import org.apache.hyracks.dataflow.std.buffermanager.SingleFrameBufferManager;
+import org.apache.hyracks.storage.am.common.api.INullIntrospector;
+import org.apache.hyracks.storage.common.IIndexCursorStats;
+import org.apache.hyracks.storage.common.NoOpIndexCursorStats;
+import org.apache.hyracks.storage.common.buffercache.IBufferCache;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class WeightedOnDiskInvertedListCursorMoveToTest {
+
+ private static final int PAGE_SIZE = 1024;
+
+ @Test
+ public void testMoveToFindsExactMatch() throws HyracksDataException {
+ TestableCursor cursor = createCursor(10);
+ boolean found = cursor.moveTo(50);
+ Assert.assertTrue(found);
+ Assert.assertEquals(50, readDocId(cursor));
+ }
+
+ @Test
+ public void testMoveToFindsNextHigher() throws HyracksDataException {
+ TestableCursor cursor = createCursor(10);
+ boolean found = cursor.moveTo(55);
+ Assert.assertTrue(found);
+ Assert.assertEquals(60, readDocId(cursor));
+ }
+
+ @Test
+ public void testMoveToBeyondEndReturnsFalse() throws HyracksDataException {
+ TestableCursor cursor = createCursor(10);
+ boolean found = cursor.moveTo(999);
+ Assert.assertFalse(found);
+ }
+
+ @Test
+ public void testMoveToFirstElement() throws HyracksDataException {
+ TestableCursor cursor = createCursor(10);
+ boolean found = cursor.moveTo(0);
+ Assert.assertTrue(found);
+ Assert.assertEquals(0, readDocId(cursor));
+ }
+
+ @Test
+ public void testMoveToFromMiddleOfCursor() throws HyracksDataException {
+ TestableCursor cursor = createCursor(10);
+ cursor.next();
+ cursor.next();
+ cursor.next();
+ cursor.next();
+ Assert.assertEquals(30, readDocId(cursor));
+
+ boolean found = cursor.moveTo(70);
+ Assert.assertTrue(found);
+ Assert.assertEquals(70, readDocId(cursor));
+ }
+
+ @Test
+ public void testSequentialFallbackWhenMoreBlocksToRead() throws HyracksDataException {
+ TestableCursor cursor = createCursor(5);
+ cursor.setMoreBlocksToRead(true);
+
+ boolean found = cursor.moveTo(30);
+ Assert.assertTrue(found);
+ Assert.assertEquals(30, readDocId(cursor));
+ }
+
+ @Test
+ public void testMoveToSameDocIdAfterAdvance() throws HyracksDataException {
+ TestableCursor cursor = createCursor(10);
+ cursor.next();
+ cursor.next();
+ boolean found = cursor.moveTo(20);
+ Assert.assertTrue(found);
+ Assert.assertEquals(20, readDocId(cursor));
+ }
+
+ private TestableCursor createCursor(int numElements) throws HyracksDataException {
+ IBufferCache bufferCache = mock(IBufferCache.class);
+ when(bufferCache.getPageSize()).thenReturn(PAGE_SIZE);
+
+ IHyracksTaskContext ctx = mock(IHyracksTaskContext.class);
+ Map<String, Object> sharedMap = new HashMap<>();
+ ISimpleFrameBufferManager bufferManager = new SingleFrameBufferManager();
+ sharedMap.put(org.apache.hyracks.api.util.HyracksConstants.INVERTED_INDEX_SEARCH_FRAME_MANAGER, bufferManager);
+ when(ctx.getSharedObject()).thenReturn(sharedMap);
+
+ ITypeTraits[] invListFields = new ITypeTraits[] { IntegerPointable.TYPE_TRAITS, FloatPointable.TYPE_TRAITS };
+
+ TestableCursor cursor =
+ new TestableCursor(bufferCache, 0, invListFields, ctx, NoOpIndexCursorStats.INSTANCE, null, null);
+
+ ByteBuffer page = ByteBuffer.allocate(PAGE_SIZE);
+ for (int i = 0; i < numElements; i++) {
+ page.putInt(i * 8, i * 10);
+ page.putFloat(i * 8 + 4, i * 1.0f);
+ }
+
+ cursor.setBuffers(new ArrayList<>(Collections.singletonList(page)));
+ cursor.setInvListInfo(0, 0, 0, numElements);
+ cursor.setMoreBlocksToRead(false);
+ cursor.initBlockInfo();
+ cursor.open(null, null);
+ return cursor;
+ }
+
+ private int readDocId(TestableCursor cursor) {
+ return IntegerPointable.getInteger(Objects.requireNonNull(cursor.getTuple()).getFieldData(0),
+ cursor.getTuple().getFieldStart(0));
+ }
+
+ private static class TestableCursor extends WeightedOnDiskInvertedListCursor {
+ TestableCursor(IBufferCache bufferCache, int fileId, ITypeTraits[] invListFields,
+ org.apache.hyracks.api.context.IHyracksTaskContext ctx, IIndexCursorStats stats,
+ ITypeTraits nullTypeTraits, INullIntrospector nullIntrospector) throws HyracksDataException {
+ super(bufferCache, fileId, invListFields, ctx, stats, nullTypeTraits, nullIntrospector);
+ }
+
+ void setBuffers(ArrayList<ByteBuffer> buffers) {
+ this.buffers = buffers;
+ }
+
+ void setMoreBlocksToRead(boolean v) {
+ this.moreBlocksToRead = v;
+ }
+
+ void initBlockInfo() {
+ super.setBlockInfo();
+ }
+
+ protected void setInvListInfo(int startPageId, int endPageId, int startOff, int numElements)
+ throws HyracksDataException {
+ super.setInvListInfo(startPageId, endPageId, startOff, numElements);
+ }
+ }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/DotProductSearchModifierTest.java b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/DotProductSearchModifierTest.java
new file mode 100644
index 0000000..5d2dabe
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/DotProductSearchModifierTest.java
@@ -0,0 +1,62 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hyracks.storage.am.lsm.invertedindex.search;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+public class DotProductSearchModifierTest {
+
+ @Test
+ public void testOccurrenceThreshold() {
+ DotProductSearchModifier mod = new DotProductSearchModifier(0.5, 10);
+ Assert.assertEquals(1, mod.getOccurrenceThreshold(5));
+ Assert.assertEquals(1, mod.getOccurrenceThreshold(1));
+ }
+
+ @Test
+ public void testNumPrefixLists() {
+ DotProductSearchModifier mod = new DotProductSearchModifier(0.5, 10);
+ Assert.assertEquals(10, mod.getNumPrefixLists(1, 10));
+ Assert.assertEquals(3, mod.getNumPrefixLists(1, 3));
+ }
+
+ @Test
+ public void testTokenBounds() {
+ DotProductSearchModifier mod = new DotProductSearchModifier(0.5, 10);
+ Assert.assertEquals(-1, mod.getNumTokensLowerBound((short) 5));
+ Assert.assertEquals(Short.MAX_VALUE, mod.getNumTokensUpperBound((short) 5));
+ }
+
+ @Test
+ public void testGetters() {
+ DotProductSearchModifier mod = new DotProductSearchModifier(3.14, 42);
+ Assert.assertEquals(3.14, mod.getScoreThreshold(), 1e-9);
+ Assert.assertEquals(42, mod.getTopK());
+ }
+
+ @Test
+ public void testFactoryRoundTrip() {
+ DotProductSearchModifierFactory factory = new DotProductSearchModifierFactory(2.71, 7);
+ DotProductSearchModifier mod = (DotProductSearchModifier) factory.createSearchModifier();
+ Assert.assertEquals(2.71, mod.getScoreThreshold(), 1e-9);
+ Assert.assertEquals(7, mod.getTopK());
+ }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/InvertedListMergerWANDTest.java b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/InvertedListMergerWANDTest.java
new file mode 100644
index 0000000..a327760
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/InvertedListMergerWANDTest.java
@@ -0,0 +1,280 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.hyracks.storage.am.lsm.invertedindex.search;
+
+import static org.mockito.ArgumentMatchers.anyInt;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+
+import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.api.context.IHyracksTaskContext;
+import org.apache.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import org.apache.hyracks.api.dataflow.value.ISerializerDeserializer;
+import org.apache.hyracks.api.dataflow.value.ITypeTraits;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.data.std.accessors.FloatBinaryComparatorFactory;
+import org.apache.hyracks.data.std.accessors.IntegerBinaryComparatorFactory;
+import org.apache.hyracks.data.std.primitive.FloatPointable;
+import org.apache.hyracks.data.std.primitive.IntegerPointable;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
+import org.apache.hyracks.dataflow.std.buffermanager.ISimpleFrameBufferManager;
+import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedIndex;
+import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedListCursor;
+import org.apache.hyracks.storage.common.ICursorInitialState;
+import org.apache.hyracks.storage.common.ISearchPredicate;
+import org.apache.hyracks.storage.common.MultiComparator;
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+
+public class InvertedListMergerWANDTest {
+
+ private static final int FRAME_SIZE = 256;
+
+ private InvertedListMerger merger;
+ private WANDSearchResult finalResult;
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ IHyracksTaskContext ctx = mock(IHyracksTaskContext.class);
+ when(ctx.getInitialFrameSize()).thenReturn(FRAME_SIZE);
+ when(ctx.allocateFrame(anyInt())).thenAnswer(inv -> ByteBuffer.allocate(inv.getArgument(0)));
+
+ ISimpleFrameBufferManager bufferManager = mock(ISimpleFrameBufferManager.class);
+ when(bufferManager.acquireFrame(anyInt())).thenAnswer(inv -> ByteBuffer.allocate(inv.getArgument(0)));
+
+ ITypeTraits[] invListTypeTraits =
+ new ITypeTraits[] { IntegerPointable.TYPE_TRAITS, FloatPointable.TYPE_TRAITS };
+ IBinaryComparatorFactory[] invListCmpFactories = new IBinaryComparatorFactory[] {
+ IntegerBinaryComparatorFactory.INSTANCE, FloatBinaryComparatorFactory.INSTANCE };
+
+ IInvertedIndex invIndex = mock(IInvertedIndex.class);
+ when(invIndex.getInvListTypeTraits()).thenReturn(invListTypeTraits);
+ when(invIndex.getInvListCmpFactories()).thenReturn(invListCmpFactories);
+ when(invIndex.getNullTypeTraits()).thenReturn(null);
+ when(invIndex.getNullIntrospector()).thenReturn(null);
+
+ merger = new InvertedListMerger(ctx, invIndex, bufferManager);
+ finalResult = new WANDSearchResult(invListTypeTraits, ctx, bufferManager, null, null);
+ }
+
+ @Test
+ public void testBasicWANDThreshold() throws HyracksDataException {
+ IInvertedListCursor c0 = makeCursor(Arrays.asList(t(1, 0.5f), t(5, 1.0f)), 1.0);
+ IInvertedListCursor c1 = makeCursor(Arrays.asList(t(1, 0.8f), t(3, 0.6f)), 1.0);
+
+ double[] qWeights = { 1.0, 1.0 };
+ double[] maxWeights = { 1.0, 1.0 };
+
+ boolean done = merger.mergeWAND(Arrays.asList(c0, c1), qWeights, maxWeights, 1.0, 0, finalResult);
+ Assert.assertTrue("Search should finish in one frame", done);
+
+ List<Integer> docIds = readDocIds(finalResult);
+ Assert.assertEquals(Arrays.asList(1, 5), docIds);
+ }
+
+ @Test
+ public void testTopKThresholdUpdate() throws HyracksDataException {
+ IInvertedListCursor c0 = makeCursor(Arrays.asList(t(1, 2.0f), t(2, 1.0f)), 2.0);
+ IInvertedListCursor c1 = makeCursor(Arrays.asList(t(1, 2.0f), t(2, 1.0f)), 2.0);
+
+ double[] qWeights = { 1.0, 1.0 };
+ double[] maxWeights = { 2.0, 2.0 };
+
+ boolean done = merger.mergeWAND(Arrays.asList(c0, c1), qWeights, maxWeights, 0.0, 1, finalResult);
+ Assert.assertTrue(done);
+
+ List<Integer> docIds = readDocIds(finalResult);
+ Assert.assertEquals(Collections.singletonList(1), docIds);
+ }
+
+ @Test
+ public void testPivotSkipping() throws HyracksDataException {
+ List<ITupleReference> longList = new ArrayList<>();
+ for (int i = 1; i <= 20; i++) {
+ longList.add(t(i, 0.1f));
+ }
+ IInvertedListCursor c0 = makeCursor(Collections.singletonList(t(10, 1.0f)), 1.0);
+ IInvertedListCursor c1 = makeCursor(longList, 0.1);
+
+ double[] qWeights = { 1.0, 1.0 };
+ double[] maxWeights = { 1.0, 0.1 };
+
+ boolean done = merger.mergeWAND(Arrays.asList(c0, c1), qWeights, maxWeights, 0.95, 0, finalResult);
+ Assert.assertTrue(done);
+
+ List<Integer> docIds = readDocIds(finalResult);
+ Assert.assertEquals(Collections.singletonList(10), docIds);
+ }
+
+ @Test
+ public void testNoPivotReachesThreshold() throws HyracksDataException {
+ IInvertedListCursor c0 = makeCursor(Collections.singletonList(t(1, 0.3f)), 0.3);
+ IInvertedListCursor c1 = makeCursor(Collections.singletonList(t(2, 0.3f)), 0.3);
+
+ double[] qWeights = { 1.0, 1.0 };
+ double[] maxWeights = { 0.3, 0.3 };
+
+ boolean done = merger.mergeWAND(Arrays.asList(c0, c1), qWeights, maxWeights, 1.0, 0, finalResult);
+ Assert.assertTrue(done);
+ Assert.assertTrue(readDocIds(finalResult).isEmpty());
+ }
+
+ @Test
+ public void testExhaustedCursorDoesNotInflateBounds() throws HyracksDataException {
+ IInvertedListCursor c0 = makeCursor(Collections.emptyList(), 0.0);
+ IInvertedListCursor c1 = makeCursor(Collections.singletonList(t(5, 2.0f)), 2.0);
+
+ double[] qWeights = { 1.0, 1.0 };
+ double[] maxWeights = { 1.0, 2.0 };
+
+ boolean done = merger.mergeWAND(Arrays.asList(c0, c1), qWeights, maxWeights, 1.5, 0, finalResult);
+ Assert.assertTrue(done);
+ Assert.assertEquals(Collections.singletonList(5), readDocIds(finalResult));
+ }
+
+ private ITupleReference t(int docId, float weight) {
+ try {
+ ArrayTupleBuilder builder = new ArrayTupleBuilder(2);
+ builder.getDataOutput().writeInt(docId);
+ builder.addFieldEndOffset();
+ builder.getDataOutput().writeFloat(weight);
+ builder.addFieldEndOffset();
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ tuple.reset(builder.getFieldEndOffsets(), builder.getByteArray());
+ return tuple;
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ }
+
+ private IInvertedListCursor makeCursor(List<ITupleReference> tuples, double maxWeight) {
+ return new MockInvertedListCursor(tuples, maxWeight);
+ }
+
+ private List<Integer> readDocIds(WANDSearchResult result) throws HyracksDataException {
+ result.finalizeWrite();
+ result.prepareResultRead();
+ ByteBuffer frame = result.getNextFrame();
+ IFrameTupleAccessor fta = result.getAccessor();
+ fta.reset(frame);
+ List<Integer> docIds = new ArrayList<>();
+ for (int i = 0; i < fta.getTupleCount(); i++) {
+ int docId = IntegerPointable.getInteger(fta.getBuffer().array(), fta.getFieldStartOffset(i, 0));
+ docIds.add(docId);
+ }
+ return docIds;
+ }
+
+ private static class MockInvertedListCursor implements IInvertedListCursor {
+ private final List<ITupleReference> tuples;
+ private final double maxWeight;
+ private int pos = -1;
+
+ MockInvertedListCursor(List<ITupleReference> tuples, double maxWeight) {
+ this.tuples = tuples;
+ this.maxWeight = maxWeight;
+ }
+
+ @Override
+ public double getMaxWeight() {
+ return maxWeight;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return pos + 1 < tuples.size();
+ }
+
+ @Override
+ public void next() {
+ pos++;
+ }
+
+ @Override
+ public ITupleReference getTuple() {
+ return tuples.get(pos);
+ }
+
+ @Override
+ public void open(ICursorInitialState initialState, ISearchPredicate searchPred) {
+ }
+
+ @Override
+ public void close() {
+ }
+
+ @Override
+ public void destroy() {
+ }
+
+ @Override
+ public void prepareLoadPages() {
+ }
+
+ @Override
+ public void loadPages() {
+ pos = -1;
+ }
+
+ @Override
+ public void unloadPages() {
+ }
+
+ @Override
+ public int size() throws HyracksDataException {
+ return tuples.size();
+ }
+
+ @Override
+ public boolean containsKey(ITupleReference searchTuple, MultiComparator invListCmp) {
+ return false;
+ }
+
+ @Override
+ @SuppressWarnings("rawtypes")
+ public String printInvList(ISerializerDeserializer[] serdes) {
+ return "";
+ }
+
+ @Override
+ @SuppressWarnings("rawtypes")
+ public String printCurrentElement(ISerializerDeserializer[] serdes) {
+ return "";
+ }
+
+ @Override
+ public int compareTo(IInvertedListCursor o) {
+ try {
+ return size() - o.size();
+ } catch (HyracksDataException e) {
+ throw new IllegalStateException(e);
+ }
+ }
+ }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WANDSearchResultTest.java b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WANDSearchResultTest.java
new file mode 100644
index 0000000..5866801
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WANDSearchResultTest.java
@@ -0,0 +1,130 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.hyracks.storage.am.lsm.invertedindex.search;
+
+import static org.mockito.ArgumentMatchers.anyInt;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+
+import java.io.IOException;
+import java.nio.ByteBuffer;
+
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.api.context.IHyracksTaskContext;
+import org.apache.hyracks.api.dataflow.value.ITypeTraits;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.data.std.primitive.FloatPointable;
+import org.apache.hyracks.data.std.primitive.IntegerPointable;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
+import org.apache.hyracks.dataflow.std.buffermanager.ISimpleFrameBufferManager;
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests that {@link WANDSearchResult} strips the trailing weight field.
+ */
+public class WANDSearchResultTest {
+
+ private static final int FRAME_SIZE = 1024;
+
+ private WANDSearchResult result;
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ IHyracksTaskContext ctx = mock(IHyracksTaskContext.class);
+ when(ctx.getInitialFrameSize()).thenReturn(FRAME_SIZE);
+ when(ctx.allocateFrame(anyInt())).thenAnswer(inv -> ByteBuffer.allocate(inv.getArgument(0)));
+
+ ISimpleFrameBufferManager bufferManager = mock(ISimpleFrameBufferManager.class);
+ when(bufferManager.acquireFrame(anyInt())).thenAnswer(inv -> ByteBuffer.allocate(inv.getArgument(0)));
+
+ ITypeTraits[] invListFields = new ITypeTraits[] { IntegerPointable.TYPE_TRAITS, FloatPointable.TYPE_TRAITS };
+ result = new WANDSearchResult(invListFields, ctx, bufferManager, null, null);
+ result.prepareWrite(1);
+ }
+
+ @Test
+ public void testAppendStripsWeightField() throws HyracksDataException {
+ ITupleReference tuple = makeTuple(42, 3.14f);
+ boolean ok = result.append(tuple, 1);
+ Assert.assertTrue(ok);
+
+ result.finalizeWrite();
+ result.prepareResultRead();
+ ByteBuffer frame = result.getNextFrame();
+ IFrameTupleAccessor fta = result.getAccessor();
+ fta.reset(frame);
+
+ Assert.assertEquals(1, fta.getTupleCount());
+ // The result should contain only the docId (field 0), not the weight.
+ Assert.assertEquals(4, fta.getFieldLength(0, 0));
+ int docId = IntegerPointable.getInteger(fta.getBuffer().array(), fta.getFieldStartOffset(0, 0));
+ Assert.assertEquals(42, docId);
+ }
+
+ @Test
+ public void testAppendMultipleTuples() throws HyracksDataException {
+ result.append(makeTuple(1, 0.1f), 1);
+ result.append(makeTuple(2, 0.2f), 1);
+ result.append(makeTuple(3, 0.3f), 1);
+
+ result.finalizeWrite();
+ result.prepareResultRead();
+ ByteBuffer frame = result.getNextFrame();
+ IFrameTupleAccessor fta = result.getAccessor();
+ fta.reset(frame);
+
+ Assert.assertEquals(3, fta.getTupleCount());
+ for (int i = 0; i < 3; i++) {
+ int docId = IntegerPointable.getInteger(fta.getBuffer().array(), fta.getFieldStartOffset(i, 0));
+ Assert.assertEquals(i + 1, docId);
+ }
+ }
+
+ @Test
+ public void testFrameFullReturnsFalse() throws HyracksDataException {
+ // Fill the frame until it is full.
+ int count = 0;
+ while (result.append(makeTuple(count, 1.0f), 1)) {
+ count++;
+ if (count > 10000) {
+ Assert.fail("Frame never became full");
+ }
+ }
+ Assert.assertTrue("Frame should have become full", count > 0);
+ }
+
+ private ITupleReference makeTuple(int docId, float weight) {
+ try {
+ ArrayTupleBuilder builder = new ArrayTupleBuilder(2);
+ builder.getDataOutput().writeInt(docId);
+ builder.addFieldEndOffset();
+ builder.getDataOutput().writeFloat(weight);
+ builder.addFieldEndOffset();
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ tuple.reset(builder.getFieldEndOffsets(), builder.getByteArray());
+ return tuple;
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WandSearchPredicateTest.java b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WandSearchPredicateTest.java
new file mode 100644
index 0000000..54f0a25
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/search/WandSearchPredicateTest.java
@@ -0,0 +1,49 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hyracks.storage.am.lsm.invertedindex.search;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+public class WandSearchPredicateTest {
+
+ @Test
+ public void testScoreThresholdDelegation() {
+ DotProductSearchModifier mod = new DotProductSearchModifier(1.23, 5);
+ WandSearchPredicate pred = new WandSearchPredicate(null, null, mod, null, null, false);
+ Assert.assertEquals(1.23, pred.getScoreThreshold(), 1e-9);
+ }
+
+ @Test
+ public void testTopKDelegation() {
+ DotProductSearchModifier mod = new DotProductSearchModifier(0.0, 100);
+ WandSearchPredicate pred = new WandSearchPredicate(null, null, mod, null, null, false);
+ Assert.assertEquals(100, pred.getTopK());
+ }
+
+ @Test
+ public void testQueryWeightsRoundTrip() {
+ DotProductSearchModifier mod = new DotProductSearchModifier(0.0, 10);
+ WandSearchPredicate pred = new WandSearchPredicate(null, null, mod, null, null, false);
+ double[] weights = new double[] { 1.0, 0.5, 2.0 };
+ pred.setQueryWeights(weights);
+ Assert.assertArrayEquals(weights, pred.getQueryWeights(), 1e-9);
+ }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/util/InvertedIndexTokenizingTupleIteratorTest.java b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/util/InvertedIndexTokenizingTupleIteratorTest.java
new file mode 100644
index 0000000..7fe7a27
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-invertedindex-test/src/test/java/org/apache/hyracks/storage/am/lsm/invertedindex/util/InvertedIndexTokenizingTupleIteratorTest.java
@@ -0,0 +1,286 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.hyracks.storage.am.lsm.invertedindex.util;
+
+import java.io.IOException;
+
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.data.std.util.GrowableArray;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
+import org.apache.hyracks.storage.am.lsm.invertedindex.fulltext.IFullTextConfigEvaluator;
+import org.apache.hyracks.storage.am.lsm.invertedindex.fulltext.TokenizerCategory;
+import org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers.IBinaryTokenizer;
+import org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers.IToken;
+import org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers.IWeightedToken;
+import org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers.TokenizerInfo;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class InvertedIndexTokenizingTupleIteratorTest {
+
+ @Test
+ public void testWeightedTokenAppendsWeightField() throws HyracksDataException {
+ ArrayTupleBuilder inputBuilder = new ArrayTupleBuilder(2);
+ inputBuilder.addField(new byte[] { 1, 2, 3 }, 0, 3);
+ inputBuilder.addField(new byte[] { 4, 5 }, 0, 2);
+ ArrayTupleReference inputTuple = new ArrayTupleReference();
+ inputTuple.reset(inputBuilder.getFieldEndOffsets(), inputBuilder.getByteArray());
+
+ IToken token = new WeightedTokenImpl(7L, 2.5);
+ IFullTextConfigEvaluator evaluator = new MockFullTextConfigEvaluator(token);
+ IBinaryTokenizer tokenizer = new MockBinaryTokenizer();
+
+ InvertedIndexTokenizingTupleIterator iter =
+ new InvertedIndexTokenizingTupleIterator(1, 1, tokenizer, evaluator);
+ iter.reset(inputTuple);
+
+ Assert.assertTrue(iter.hasNext());
+ iter.next();
+ ITupleReference out = iter.getTuple();
+
+ Assert.assertEquals(3, out.getFieldCount());
+
+ Assert.assertEquals(8, out.getFieldLength(0));
+
+ Assert.assertEquals(4, out.getFieldLength(1));
+ float weight = org.apache.hyracks.data.std.primitive.FloatPointable.getFloat(out.getFieldData(1),
+ out.getFieldStart(1));
+ Assert.assertEquals(2.5f, weight, 1e-6f);
+
+ Assert.assertEquals(2, out.getFieldLength(2));
+ }
+
+ @Test
+ public void testPlainTokenNoWeightField() throws HyracksDataException {
+ ArrayTupleBuilder inputBuilder = new ArrayTupleBuilder(2);
+ inputBuilder.addField(new byte[] { 1 }, 0, 1);
+ inputBuilder.addField(new byte[] { 2 }, 0, 1);
+ ArrayTupleReference inputTuple = new ArrayTupleReference();
+ inputTuple.reset(inputBuilder.getFieldEndOffsets(), inputBuilder.getByteArray());
+
+ IToken token = new PlainTokenImpl(new byte[] { 9 }, 0, 1);
+ IFullTextConfigEvaluator evaluator = new MockFullTextConfigEvaluator(token);
+ IBinaryTokenizer tokenizer = new MockBinaryTokenizer();
+
+ InvertedIndexTokenizingTupleIterator iter =
+ new InvertedIndexTokenizingTupleIterator(1, 1, tokenizer, evaluator);
+ iter.reset(inputTuple);
+
+ Assert.assertTrue(iter.hasNext());
+ iter.next();
+ ITupleReference out = iter.getTuple();
+
+ Assert.assertEquals(2, out.getFieldCount());
+ }
+
+ // ==================== mocks ====================
+
+ private static class WeightedTokenImpl implements IToken, IWeightedToken {
+ private final long index;
+ private final double weight;
+ private byte[] data = new byte[8];
+
+ WeightedTokenImpl(long index, double weight) {
+ this.index = index;
+ this.weight = weight;
+ }
+
+ @Override
+ public long getIndex() {
+ return index;
+ }
+
+ @Override
+ public double getWeight() {
+ return weight;
+ }
+
+ @Override
+ public byte[] getData() {
+ return data;
+ }
+
+ @Override
+ public int getEndOffset() {
+ return data.length;
+ }
+
+ @Override
+ public int getStartOffset() {
+ return 0;
+ }
+
+ @Override
+ public int getTokenLength() {
+ return data.length;
+ }
+
+ @Override
+ public void reset(byte[] data, int startOffset, int endOffset, int tokenLength, int tokenCount) {
+ this.data = data;
+ }
+
+ @Override
+ public void serializeToken(GrowableArray out) throws IOException {
+ out.append(data, 0, data.length);
+ }
+
+ @Override
+ public void serializeTokenCount(GrowableArray out) throws IOException {
+ out.append(new byte[] { 1 }, 0, 1);
+ }
+ }
+
+ private static class PlainTokenImpl implements IToken {
+ private byte[] data;
+ private final int start;
+ private final int len;
+
+ PlainTokenImpl(byte[] data, int start, int len) {
+ this.data = data;
+ this.start = start;
+ this.len = len;
+ }
+
+ @Override
+ public byte[] getData() {
+ return data;
+ }
+
+ @Override
+ public int getEndOffset() {
+ return start + len;
+ }
+
+ @Override
+ public int getStartOffset() {
+ return start;
+ }
+
+ @Override
+ public int getTokenLength() {
+ return len;
+ }
+
+ @Override
+ public void reset(byte[] data, int startOffset, int endOffset, int tokenLength, int tokenCount) {
+ this.data = data;
+ }
+
+ @Override
+ public void serializeToken(GrowableArray out) throws IOException {
+ out.append(data, start, len);
+ }
+
+ @Override
+ public void serializeTokenCount(GrowableArray out) throws IOException {
+ out.append(new byte[] { 1 }, 0, 1);
+ }
+ }
+
+ private static class MockFullTextConfigEvaluator implements IFullTextConfigEvaluator {
+ private final IToken token;
+ private boolean hasNext = true;
+
+ MockFullTextConfigEvaluator(IToken token) {
+ this.token = token;
+ }
+
+ @Override
+ public String getName() {
+ return "mock";
+ }
+
+ @Override
+ public TokenizerCategory getTokenizerCategory() {
+ return TokenizerCategory.WORD;
+ }
+
+ @Override
+ public void setTokenizer(IBinaryTokenizer tokenizer) {
+ }
+
+ @Override
+ public void reset(byte[] data, int start, int length) {
+ hasNext = true;
+ }
+
+ @Override
+ public IBinaryTokenizer getTokenizer() {
+ return null;
+ }
+
+ @Override
+ public IToken getToken() {
+ return token;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return hasNext;
+ }
+
+ @Override
+ public void next() {
+ hasNext = false;
+ }
+
+ @Override
+ public int getTokensCount() {
+ return 1;
+ }
+ }
+
+ private static class MockBinaryTokenizer implements IBinaryTokenizer {
+ @Override
+ public IToken getToken() {
+ return null;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return false;
+ }
+
+ @Override
+ public void next() {
+ }
+
+ @Override
+ public void reset(byte[] data, int start, int length) {
+ }
+
+ @Override
+ public short getTokensCount() {
+ return 0;
+ }
+
+ @Override
+ public TokenizerInfo.TokenizerType getTokenizerType() {
+ return TokenizerInfo.TokenizerType.STRING;
+ }
+
+ @Override
+ public TokenizerCategory getTokenizerCategory() {
+ return TokenizerCategory.WORD;
+ }
+ }
+}
--
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21278?usp=email
To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings?usp=email
Gerrit-MessageType: newchange
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Change-Id: I2ea8c32ddfc7750fdc671b9d1b5d0d551ef68403
Gerrit-Change-Number: 21278
Gerrit-PatchSet: 1
Gerrit-Owner: Savyasach Reddy <es...@gmail.com>