This is an automated email from the ASF dual-hosted git repository.
xiangfu0 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/pinot.git
The following commit(s) were added to refs/heads/master by this push:
new c32ae438eb0 [Vector Upsert 3/5] Never materialize nested vector
subtrees as metadata filters (#19299)
c32ae438eb0 is described below
commit c32ae438eb02760009aeecc4cafc0bf54656f724
Author: Xiang Fu <[email protected]>
AuthorDate: Wed Aug 26 16:30:10 2026 -0700
[Vector Upsert 3/5] Never materialize nested vector subtrees as metadata
filters (#19299)
FilterPlanNode treated any non-leaf AND sibling as a metadata filter when
wiring pre-filter bitmaps for filter-aware ANN. A nested subtree containing
a
VECTOR_SIMILARITY predicate (e.g. AND(vector, AND(vector2, metadata)) or
AND(vector, NOT(vector2))) was eagerly materialized into a bitmap, executing
top-K candidate generation out of its boolean context and pushing its
results
into the sibling vector search as a pre-filter.
Track the retained child FilterContexts alongside their operators so
wirePreFilterForVectorOperators can pair them, and only treat subtrees with
no
vector predicate as metadata. Adaptive pre-filter selection for plain
metadata
siblings is unchanged.
---
.../org/apache/pinot/core/plan/FilterPlanNode.java | 71 +++++++-----
.../apache/pinot/core/plan/FilterPlanNodeTest.java | 125 +++++++++++++++++++++
2 files changed, 166 insertions(+), 30 deletions(-)
diff --git
a/pinot-core/src/main/java/org/apache/pinot/core/plan/FilterPlanNode.java
b/pinot-core/src/main/java/org/apache/pinot/core/plan/FilterPlanNode.java
index a1a2024c909..34b77301a25 100644
--- a/pinot-core/src/main/java/org/apache/pinot/core/plan/FilterPlanNode.java
+++ b/pinot-core/src/main/java/org/apache/pinot/core/plan/FilterPlanNode.java
@@ -214,9 +214,10 @@ public class FilterPlanNode implements PlanNode {
case AND:
childFilters = filter.getChildren();
childFilterOperators = new ArrayList<>(childFilters.size());
+ List<FilterContext> retainedChildFilters = new
ArrayList<>(childFilters.size());
for (FilterContext childFilter : childFilters) {
BaseFilterOperator childFilterOperator;
- if (isVectorSimilarityFilter(childFilter) &&
hasNonVectorSibling(childFilters)) {
+ if (isVectorSimilarityFilter(childFilter) &&
hasSafeMetadataSibling(childFilters)) {
// Pass filtered context so vector operator reports correct
execution mode
childFilterOperator = constructFilteredVectorOperator(childFilter,
numDocs);
} else {
@@ -228,13 +229,14 @@ public class FilterPlanNode implements PlanNode {
} else if (!childFilterOperator.isResultMatchingAll()) {
// Remove child filter operators that match all records
childFilterOperators.add(childFilterOperator);
+ retainedChildFilters.add(childFilter);
}
}
// Wire pre-filter bitmaps for filter-aware ANN: if an AND contains a
// VectorSimilarityFilterOperator alongside other filter children,
evaluate the
// non-vector filters first and pass the resulting bitmap to the
vector operator
// so it can restrict HNSW graph traversal to the pre-filtered
document set.
- wirePreFilterForVectorOperators(childFilterOperators, numDocs);
+ wirePreFilterForVectorOperators(retainedChildFilters,
childFilterOperators, numDocs);
return FilterOperatorUtils.getAndFilterOperator(_queryContext,
childFilterOperators, numDocs);
case OR:
childFilters = filter.getChildren();
@@ -398,11 +400,10 @@ public class FilterPlanNode implements PlanNode {
numDocs, true);
}
- /// Returns true if the child list contains at least one
non-VECTOR_SIMILARITY predicate
- /// (i.e., a real metadata filter sibling).
- private static boolean hasNonVectorSibling(List<FilterContext> childFilters)
{
+ /// Returns true if the child list contains at least one sibling subtree
with no vector predicate.
+ private static boolean hasSafeMetadataSibling(List<FilterContext>
childFilters) {
for (FilterContext child : childFilters) {
- if (!isVectorSimilarityFilter(child)) {
+ if (!containsVectorPredicate(child)) {
return true;
}
}
@@ -415,6 +416,24 @@ public class FilterPlanNode implements PlanNode {
&& filter.getPredicate().getType() == Predicate.Type.VECTOR_SIMILARITY;
}
+ /// Returns true when any node in the subtree is a vector top-K predicate.
Such a subtree must never be
+ /// materialized as metadata for another vector predicate because doing so
executes candidate generation out of its
+ /// original boolean context and can incorrectly push candidate results into
a sibling.
+ private static boolean containsVectorPredicate(FilterContext filter) {
+ if (filter.getType() == FilterContext.Type.PREDICATE) {
+ return filter.getPredicate().getType() ==
Predicate.Type.VECTOR_SIMILARITY;
+ }
+ if (filter.getType() == FilterContext.Type.AND || filter.getType() ==
FilterContext.Type.OR
+ || filter.getType() == FilterContext.Type.NOT) {
+ for (FilterContext child : filter.getChildren()) {
+ if (containsVectorPredicate(child)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
/// Constructs the vector radius filter operator based on index availability.
///
/// The radius operator always needs the forward index for exact distance
computation.
@@ -430,38 +449,37 @@ public class FilterPlanNode implements PlanNode {
vectorIndexConfig);
}
- /// Wires pre-filter bitmaps for filter-aware ANN search when an AND node
contains both
- /// vector similarity operators and non-vector filter operators.
+ /// Wires metadata bitmaps when an AND node contains both vector similarity
operators and non-vector filters.
///
- /// When the vector index reader supports pre-filtering (implements
- ///
[org.apache.pinot.segment.spi.index.reader.FilterAwareVectorIndexReader]), the
non-vector
- /// siblings are evaluated eagerly to produce a combined bitmap. This bitmap
is passed to the
- /// [VectorSimilarityFilterOperator] so that the HNSW graph traversal is
restricted to
- /// pre-filtered documents, improving recall for selective filters.
+ /// The existing adaptive behavior is preserved: only bitmap-producing
filters are considered, and
+ /// [VectorSearchStrategy] decides whether the filter-aware reader should
receive the bitmap.
///
/// **Trade-off: eager filter evaluation.** The non-vector filter predicates
are materialized
/// into bitmaps before the vector search begins. This is intentional
because the filter bitmap must
/// be fully materialized before it can be passed to the vector index for
pre-filtered ANN search.
- /// The [VectorSearchStrategy] selectivity check below ensures we only pay
this cost when the
- /// estimated cardinality suggests pre-filtering is worthwhile.
+ /// The [VectorSearchStrategy] selectivity check below ensures queries only
pay this cost when the estimated
+ /// cardinality suggests pre-filtering is worthwhile.
///
- /// If no vector operators are found or the reader does not support
pre-filtering,
- /// this method is a no-op and the AND operator falls back to the default
post-filter path.
+ /// If no vector operators are found, this method is a no-op. A query whose
reader does not support
+ /// pre-filtering retains the default post-filter path.
///
/// @param childOperators the list of child filter operators under an AND
node
/// @param numDocs total documents in the segment
- private void wirePreFilterForVectorOperators(List<BaseFilterOperator>
childOperators, int numDocs) {
+ private void wirePreFilterForVectorOperators(List<FilterContext>
childFilters,
+ List<BaseFilterOperator> childOperators, int numDocs) {
if (childOperators.size() < 2) {
return;
}
- // Find vector similarity operators that support pre-filtering
+ // Find indexed vector similarity operators and non-vector metadata
siblings.
List<VectorSimilarityFilterOperator> vectorOps = new ArrayList<>();
List<BaseFilterOperator> nonVectorOps = new ArrayList<>();
- for (BaseFilterOperator op : childOperators) {
- if (op instanceof VectorSimilarityFilterOperator) {
+ for (int i = 0; i < childOperators.size(); i++) {
+ FilterContext childFilter = childFilters.get(i);
+ BaseFilterOperator op = childOperators.get(i);
+ if (isVectorSimilarityFilter(childFilter) && op instanceof
VectorSimilarityFilterOperator) {
vectorOps.add((VectorSimilarityFilterOperator) op);
- } else {
+ } else if (!containsVectorPredicate(childFilter)) {
nonVectorOps.add(op);
}
}
@@ -498,9 +516,7 @@ public class FilterPlanNode implements PlanNode {
}
// Combine non-vector filter bitmaps via AND.
- // Note: this eagerly evaluates non-vector filters. BaseFilterOperator
subclasses cache
- // their results, so the subsequent evaluation by AndFilterOperator will
reuse the cached
- // bitmaps without double-evaluation.
+ // Bitmap-producing filters are cheap to evaluate again when the final AND
executes.
MutableRoaringBitmap combinedBitmap = null;
for (BaseFilterOperator op : nonVectorOps) {
BitmapCollection bitmapCollection = op.getBitmaps();
@@ -520,11 +536,6 @@ public class FilterPlanNode implements PlanNode {
// the estimated selectivity. Only pass the bitmap if the strategy
recommends
// FILTER_THEN_ANN; otherwise fall back to the default post-filter path.
int estimatedFilteredDocs = combinedBitmap.getCardinality();
- // isMutableSegment=false is acceptable here because the
supportsPreFilter() check above
- // already ensures we only reach this point for immutable segments with
- // FilterAwareVectorIndexReader. MutableVectorIndex does not implement
- // FilterAwareVectorIndexReader, so mutable segments exit early via the
- // anySupportsPreFilter guard.
// backendType and searchParams are passed as null here because at the
pre-filter wiring
// stage we are deciding whether to activate pre-filtering at all, not
per-backend tuning.
// The strategy currently uses only selectivity (numDocs,
estimatedFilteredDocs) for this
diff --git
a/pinot-core/src/test/java/org/apache/pinot/core/plan/FilterPlanNodeTest.java
b/pinot-core/src/test/java/org/apache/pinot/core/plan/FilterPlanNodeTest.java
index b505c2e8dfb..ec094f4ff53 100644
---
a/pinot-core/src/test/java/org/apache/pinot/core/plan/FilterPlanNodeTest.java
+++
b/pinot-core/src/test/java/org/apache/pinot/core/plan/FilterPlanNodeTest.java
@@ -19,12 +19,15 @@
package org.apache.pinot.core.plan;
import java.lang.reflect.Method;
+import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
import org.apache.commons.lang3.tuple.Pair;
import org.apache.pinot.common.request.context.ExpressionContext;
import org.apache.pinot.common.request.context.FilterContext;
+import org.apache.pinot.common.request.context.predicate.IsNullPredicate;
import org.apache.pinot.common.request.context.predicate.Predicate;
import org.apache.pinot.common.request.context.predicate.RegexpLikePredicate;
+import
org.apache.pinot.common.request.context.predicate.VectorSimilarityPredicate;
import org.apache.pinot.core.common.BlockDocIdIterator;
import org.apache.pinot.core.common.BlockDocIdSet;
import org.apache.pinot.core.operator.blocks.FilterBlock;
@@ -42,8 +45,10 @@ import
org.apache.pinot.segment.spi.datasource.DataSourceMetadata;
import org.apache.pinot.segment.spi.index.creator.VectorIndexConfig;
import
org.apache.pinot.segment.spi.index.mutable.ThreadSafeMutableRoaringBitmap;
import org.apache.pinot.segment.spi.index.reader.Dictionary;
+import org.apache.pinot.segment.spi.index.reader.FilterAwareVectorIndexReader;
import org.apache.pinot.segment.spi.index.reader.ForwardIndexReader;
import org.apache.pinot.segment.spi.index.reader.InvertedIndexReader;
+import org.apache.pinot.segment.spi.index.reader.NullValueVectorReader;
import org.apache.pinot.segment.spi.index.reader.TextIndexReader;
import org.apache.pinot.spi.config.table.FieldConfig;
import org.apache.pinot.spi.data.DimensionFieldSpec;
@@ -51,9 +56,16 @@ import org.apache.pinot.spi.data.FieldSpec.DataType;
import org.mockito.Mockito;
import org.mockito.stubbing.Answer;
import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+import org.testng.Assert;
+import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;
+import static org.mockito.ArgumentMatchers.any;
+import static org.mockito.ArgumentMatchers.eq;
import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.never;
+import static org.mockito.Mockito.verify;
import static org.mockito.Mockito.when;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
@@ -62,6 +74,103 @@ import static org.testng.Assert.assertTrue;
public class FilterPlanNodeTest {
+ @DataProvider(name = "nestedVectorSubtreeShapes")
+ public Object[][] nestedVectorSubtreeShapes() {
+ return new Object[][]{{"AND"}, {"OR"}, {"NOT_OR"}};
+ }
+
+ @Test(dataProvider = "nestedVectorSubtreeShapes")
+ public void
testNestedVectorSimilaritySubtreeIsNeverMaterializedAsMetadata(String shape) {
+ FilterAwareVectorIndexReader directVectorReader =
mock(FilterAwareVectorIndexReader.class);
+ FilterAwareVectorIndexReader nestedVectorReader =
mock(FilterAwareVectorIndexReader.class);
+ when(directVectorReader.supportsPreFilter()).thenReturn(true);
+ when(nestedVectorReader.supportsPreFilter()).thenReturn(true);
+ when(nestedVectorReader.getDocIds(Mockito.any(float[].class),
Mockito.anyInt(),
+ any(ImmutableRoaringBitmap.class))).thenReturn(bitmapOf(1));
+ DataSource directVectorDataSource = mock(DataSource.class);
+ DataSource nestedVectorDataSource = mock(DataSource.class);
+
when(directVectorDataSource.getVectorIndex()).thenReturn(directVectorReader);
+
when(nestedVectorDataSource.getVectorIndex()).thenReturn(nestedVectorReader);
+ DataSource metadataDataSource = mock(DataSource.class);
+ NullValueVectorReader nullValueVectorReader =
mock(NullValueVectorReader.class);
+ when(nullValueVectorReader.getNullBitmap()).thenReturn(bitmapOf(1));
+
when(metadataDataSource.getNullValueVector()).thenReturn(nullValueVectorReader);
+
+ IndexSegment segment = mock(IndexSegment.class);
+ SegmentMetadata metadata = mock(SegmentMetadata.class);
+ when(metadata.getTotalDocs()).thenReturn(1_000);
+ when(segment.getSegmentMetadata()).thenReturn(metadata);
+ when(segment.getDataSource("embeddingA",
null)).thenReturn(directVectorDataSource);
+ when(segment.getDataSource("embeddingB",
null)).thenReturn(nestedVectorDataSource);
+ when(segment.getDataSource("tenant", null)).thenReturn(metadataDataSource);
+
+ FilterContext directVector = FilterContext.forPredicate(new
VectorSimilarityPredicate(
+ ExpressionContext.forIdentifier("embeddingA"), new float[]{1.0f,
0.0f}, 2));
+ FilterContext nestedVector = FilterContext.forPredicate(new
VectorSimilarityPredicate(
+ ExpressionContext.forIdentifier("embeddingB"), new float[]{1.0f,
0.0f}, 2));
+ FilterContext metadataFilter = FilterContext.forPredicate(
+ new IsNullPredicate(ExpressionContext.forIdentifier("tenant")));
+ FilterContext nestedSubtree;
+ switch (shape) {
+ case "AND":
+ nestedSubtree = FilterContext.forAnd(List.of(nestedVector,
metadataFilter));
+ break;
+ case "OR":
+ nestedSubtree = FilterContext.forOr(List.of(nestedVector,
metadataFilter));
+ break;
+ case "NOT_OR":
+ nestedSubtree =
FilterContext.forNot(FilterContext.forOr(List.of(nestedVector,
metadataFilter)));
+ break;
+ default:
+ throw new IllegalStateException("Unexpected shape: " + shape);
+ }
+ QueryContext queryContext = mock(QueryContext.class);
+
when(queryContext.getFilter()).thenReturn(FilterContext.forAnd(List.of(directVector,
nestedSubtree)));
+
+ SegmentContext segmentContext = new SegmentContext(segment);
+ segmentContext.setDocIdsSnapshot(bitmapOf(0, 1, 2, 3));
+ new FilterPlanNode(segmentContext, queryContext).run();
+
+ verify(nestedVectorReader, never()).getDocIds(Mockito.any(float[].class),
Mockito.anyInt());
+ verify(nestedVectorReader, never()).getDocIds(Mockito.any(float[].class),
Mockito.anyInt(),
+ any(ImmutableRoaringBitmap.class));
+ verify(directVectorReader, never()).getDocIds(Mockito.any(float[].class),
Mockito.anyInt(),
+ any(ImmutableRoaringBitmap.class));
+ }
+
+ @Test
+ public void
testNonRestrictedMetadataScopePreservesAdaptivePostFilterBehavior() {
+ float[] queryVector = {1.0f, 0.0f};
+ FilterAwareVectorIndexReader vectorReader =
mock(FilterAwareVectorIndexReader.class);
+ when(vectorReader.supportsPreFilter()).thenReturn(true);
+ when(vectorReader.getDocIds(queryVector, 2)).thenReturn(bitmapOf(0, 1));
+
+ DataSource vectorDataSource = mock(DataSource.class);
+ when(vectorDataSource.getVectorIndex()).thenReturn(vectorReader);
+ DataSource metadataDataSource = mock(DataSource.class);
+ NullValueVectorReader nullValueVectorReader =
mock(NullValueVectorReader.class);
+ when(nullValueVectorReader.getNullBitmap()).thenReturn(bitmapOf(2, 3));
+
when(metadataDataSource.getNullValueVector()).thenReturn(nullValueVectorReader);
+
+ IndexSegment segment = mock(IndexSegment.class);
+ SegmentMetadata metadata = mock(SegmentMetadata.class);
+ when(metadata.getTotalDocs()).thenReturn(4);
+ when(segment.getSegmentMetadata()).thenReturn(metadata);
+ when(segment.getDataSource("embedding",
null)).thenReturn(vectorDataSource);
+ when(segment.getDataSource("tenant", null)).thenReturn(metadataDataSource);
+
+ FilterContext vectorFilter = FilterContext.forPredicate(new
VectorSimilarityPredicate(
+ ExpressionContext.forIdentifier("embedding"), queryVector, 2));
+ FilterContext metadataFilter = FilterContext.forPredicate(
+ new IsNullPredicate(ExpressionContext.forIdentifier("tenant")));
+ QueryContext queryContext = mock(QueryContext.class);
+
when(queryContext.getFilter()).thenReturn(FilterContext.forAnd(List.of(vectorFilter,
metadataFilter)));
+
+ Assert.assertTrue(getFilteredDocIds(new FilterPlanNode(new
SegmentContext(segment), queryContext).run()).isEmpty());
+ verify(vectorReader).getDocIds(queryVector, 2);
+ verify(vectorReader, never()).getDocIds(eq(queryVector), eq(2),
any(ImmutableRoaringBitmap.class));
+ }
+
@Test
public void testConsistentSnapshot()
throws Exception {
@@ -154,6 +263,22 @@ public class FilterPlanNodeTest {
return numDocsFiltered;
}
+ private static MutableRoaringBitmap getFilteredDocIds(BaseFilterOperator
operator) {
+ MutableRoaringBitmap docIds = new MutableRoaringBitmap();
+ BlockDocIdIterator iterator =
operator.nextBlock().getBlockDocIdSet().iterator();
+ int docId;
+ while ((docId = iterator.next()) != Constants.EOF) {
+ docIds.add(docId);
+ }
+ return docIds;
+ }
+
+ private static MutableRoaringBitmap bitmapOf(int... docIds) {
+ MutableRoaringBitmap bitmap = new MutableRoaringBitmap();
+ bitmap.add(docIds);
+ return bitmap;
+ }
+
@Test
public void regexpLikeUsesIFSTEvaluatorWhenIFSTAndInvertedAvailable()
throws Exception {
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
