xiangfu0 commented on code in PR #19799:
URL: https://github.com/apache/pinot/pull/19799#discussion_r4224956647
##########
pinot-core/src/main/java/org/apache/pinot/core/startree/operator/StarTreeFilterOperator.java:
##########
@@ -233,15 +235,23 @@ private StarTreeResult traverseStarTree() {
// If all predicate columns and group-by columns are matched, we can use
aggregated document
if (remainingPredicateColumns.isEmpty() &&
remainingGroupByColumns.isEmpty()) {
- matchingDocIds.add(starTreeNode.getAggregatedDocId());
+ if (heapMatchingDocIds == null) {
+ matchingDocIds.add(starTreeNode.getAggregatedDocId());
+ } else {
+ heapMatchingDocIds.add(starTreeNode.getAggregatedDocId());
+ }
continue;
}
// For leaf node, because we haven't exhausted all predicate columns and
group-by columns, we cannot use
// the aggregated document. Add the range of documents for this node to
the bitmap, and keep track of the
// remaining predicate columns for this node
if (starTreeNode.isLeaf()) {
- matchingDocIds.add((long) starTreeNode.getStartDocId(),
starTreeNode.getEndDocId());
+ if (heapMatchingDocIds == null) {
+ // Range additions grow heap array containers geometrically. Keep
aggregate-only matches in the buffer bitmap.
+ heapMatchingDocIds = matchingDocIds.toRoaringBitmap();
Review Comment:
Fixed in c9cedaa462: the first leaf range now uses `new RoaringBitmap()`.
The comment documents the monotonic remaining-column invariant: once both sets
become empty, every later node takes the aggregate branch before leaf handling.
The empty buffer conversion is gone. All 18 selected tests and the 16
public-operator shapes pass.
##########
pinot-core/src/main/java/org/apache/pinot/core/startree/operator/StarTreeFilterOperator.java:
##########
@@ -342,6 +352,9 @@ private StarTreeResult traverseStarTree() {
}
}
+ if (heapMatchingDocIds != null) {
+ matchingDocIds = heapMatchingDocIds.toMutableRoaringBitmap();
Review Comment:
Considered both alternatives. Fresh wide ranges create RUN containers in
1.6.23; the updated actual-operator controls measure +264 B/op for one dense
range and +416 B/op for three wide ranges/four keys, including conversion.
BITMAP containers can still copy 8 KiB/key, so the cost depends on
representation. Serialization still copies payload and adds uncached
buffer/container views during reads, losing primitive-array fast paths; an
N-range gate does not predict representation and needs a populated-buffer
handoff. I kept the measured container conversion in this scoped change and
retained the overhead caveat. The constructor cleanup is in c9cedaa462; full
query row/schema/decoded-wire parity and all 18 selected tests pass.
##########
pinot-core/src/main/java/org/apache/pinot/core/startree/operator/StarTreeFilterOperator.java:
##########
@@ -233,15 +235,23 @@ private StarTreeResult traverseStarTree() {
// If all predicate columns and group-by columns are matched, we can use
aggregated document
if (remainingPredicateColumns.isEmpty() &&
remainingGroupByColumns.isEmpty()) {
- matchingDocIds.add(starTreeNode.getAggregatedDocId());
+ if (heapMatchingDocIds == null) {
+ matchingDocIds.add(starTreeNode.getAggregatedDocId());
+ } else {
+ heapMatchingDocIds.add(starTreeNode.getAggregatedDocId());
+ }
continue;
}
// For leaf node, because we haven't exhausted all predicate columns and
group-by columns, we cannot use
// the aggregated document. Add the range of documents for this node to
the bitmap, and keep track of the
// remaining predicate columns for this node
if (starTreeNode.isLeaf()) {
- matchingDocIds.add((long) starTreeNode.getStartDocId(),
starTreeNode.getEndDocId());
+ if (heapMatchingDocIds == null) {
+ // Range additions grow heap array containers geometrically. Keep
aggregate-only matches in the buffer bitmap.
+ heapMatchingDocIds = matchingDocIds.toRoaringBitmap();
+ }
+ heapMatchingDocIds.add((long) starTreeNode.getStartDocId(),
starTreeNode.getEndDocId());
Review Comment:
Added the explicit `MappeableArrayContainer.iadd` cause next to the heap
initialization in c9cedaa462. I kept this PR scoped to the measured StarTree
caller: extracting a public/shared builder and changing sorted-index filtering
would add another execution path whose range merging and container-shape
tradeoffs need separate measurements. The comment makes the workaround
straightforward to revisit after a Roaring upgrade.
##########
pinot-core/src/test/java/org/apache/pinot/core/startree/operator/StarTreeFilterOperatorTest.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.pinot.core.startree.operator;
+
+import it.unimi.dsi.fastutil.objects.ObjectBooleanPair;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import org.apache.pinot.common.request.context.predicate.Predicate;
+import org.apache.pinot.core.operator.filter.TestUtils;
+import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
+import org.apache.pinot.core.query.request.context.QueryContext;
+import org.apache.pinot.core.startree.CompositePredicateEvaluator;
+import org.apache.pinot.segment.spi.datasource.DataSource;
+import org.apache.pinot.segment.spi.datasource.DataSourceMetadata;
+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.startree.StarTree;
+import org.apache.pinot.segment.spi.index.startree.StarTreeNode;
+import org.apache.pinot.segment.spi.index.startree.StarTreeV2;
+import org.apache.pinot.segment.spi.index.startree.StarTreeV2Metadata;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Test;
+
+import static org.mockito.Mockito.doReturn;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+import static org.testng.Assert.assertEquals;
+
+
+/// Tests star-tree document selection through the public filter result. Each
invocation owns its fixture.
+public class StarTreeFilterOperatorTest {
+ @DataProvider(name = "nullHandling")
+ public Object[][] nullHandling() {
+ return new Object[][]{{false}, {true}};
+ }
+
+ @Test(dataProvider = "nullHandling")
+ public void testRangesAndAggregatedDocsWithResidualPredicate(boolean
nullHandlingEnabled) {
+ // Early leaves retain the dim1 predicate, while deeper dim1 nodes
contribute aggregate document ids.
+ // Keep the range order deliberately unsorted, overlap two ranges, and
cross the 16-bit container boundary.
+ StarTreeNode firstAggregate = leaf(1, 0, 20, 21, 0);
+ StarTreeNode lastAggregate = leaf(1, 1, 30, 31, 70000);
+ StarTreeNode branch = branch(0, 4, List.of(firstAggregate, lastAggregate));
+ StarTreeNode root = branch(-1, StarTreeNode.ALL, List.of(
+ leaf(0, 0, 65534, 65538, 40), leaf(0, 1, 3, 4, 41), leaf(0, 2, 2, 4,
42),
+ leaf(0, 3, 10, 10, 43), branch));
+ StarTree starTree = mock(StarTree.class);
+ when(starTree.getRoot()).thenReturn(root);
+ when(starTree.getDimensionNames()).thenReturn(List.of("dim0", "dim1"));
+ StarTreeV2Metadata metadata = mock(StarTreeV2Metadata.class);
+ when(metadata.getNumDocs()).thenReturn(70001);
+ StarTreeV2 starTreeV2 = mock(StarTreeV2.class);
+ when(starTreeV2.getStarTree()).thenReturn(starTree);
+ when(starTreeV2.getMetadata()).thenReturn(metadata);
+ QueryContext queryContext = new QueryContext.Builder().build();
+ queryContext.setNullHandlingEnabled(nullHandlingEnabled);
+
+ // A group-by on dim1 takes the same range/singleton paths without
applying the residual predicate.
+ StarTreeFilterOperator unfiltered = new
StarTreeFilterOperator(queryContext, starTreeV2, Map.of(), Set.of("dim1"));
+
assertEquals(TestUtils.getDocIds(unfiltered.nextBlock().getBlockDocIdSet()),
+ List.of(0, 2, 3, 65534, 65535, 65536, 65537, 70000));
+
+ when(root.getAggregatedDocId()).thenReturn(70000);
Review Comment:
Fixed in c9cedaa462: the root aggregate id is now stubbed during fixture
setup before any operator/assertion. There is no mid-test re-stub, so assertion
ordering no longer changes fixture semantics. Both null-handling cases pass.
##########
pinot-core/src/test/java/org/apache/pinot/core/startree/operator/StarTreeFilterOperatorTest.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.pinot.core.startree.operator;
+
+import it.unimi.dsi.fastutil.objects.ObjectBooleanPair;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import org.apache.pinot.common.request.context.predicate.Predicate;
+import org.apache.pinot.core.operator.filter.TestUtils;
+import org.apache.pinot.core.operator.filter.predicate.PredicateEvaluator;
+import org.apache.pinot.core.query.request.context.QueryContext;
+import org.apache.pinot.core.startree.CompositePredicateEvaluator;
+import org.apache.pinot.segment.spi.datasource.DataSource;
+import org.apache.pinot.segment.spi.datasource.DataSourceMetadata;
+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.startree.StarTree;
+import org.apache.pinot.segment.spi.index.startree.StarTreeNode;
+import org.apache.pinot.segment.spi.index.startree.StarTreeV2;
+import org.apache.pinot.segment.spi.index.startree.StarTreeV2Metadata;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Test;
+
+import static org.mockito.Mockito.doReturn;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+import static org.testng.Assert.assertEquals;
+
+
+/// Tests star-tree document selection through the public filter result. Each
invocation owns its fixture.
+public class StarTreeFilterOperatorTest {
+ @DataProvider(name = "nullHandling")
+ public Object[][] nullHandling() {
+ return new Object[][]{{false}, {true}};
+ }
+
+ @Test(dataProvider = "nullHandling")
+ public void testRangesAndAggregatedDocsWithResidualPredicate(boolean
nullHandlingEnabled) {
+ // Early leaves retain the dim1 predicate, while deeper dim1 nodes
contribute aggregate document ids.
+ // Keep the range order deliberately unsorted, overlap two ranges, and
cross the 16-bit container boundary.
+ StarTreeNode firstAggregate = leaf(1, 0, 20, 21, 0);
+ StarTreeNode lastAggregate = leaf(1, 1, 30, 31, 70000);
+ StarTreeNode branch = branch(0, 4, List.of(firstAggregate, lastAggregate));
+ StarTreeNode root = branch(-1, StarTreeNode.ALL, List.of(
+ leaf(0, 0, 65534, 65538, 40), leaf(0, 1, 3, 4, 41), leaf(0, 2, 2, 4,
42),
+ leaf(0, 3, 10, 10, 43), branch));
+ StarTree starTree = mock(StarTree.class);
+ when(starTree.getRoot()).thenReturn(root);
+ when(starTree.getDimensionNames()).thenReturn(List.of("dim0", "dim1"));
+ StarTreeV2Metadata metadata = mock(StarTreeV2Metadata.class);
+ when(metadata.getNumDocs()).thenReturn(70001);
+ StarTreeV2 starTreeV2 = mock(StarTreeV2.class);
+ when(starTreeV2.getStarTree()).thenReturn(starTree);
+ when(starTreeV2.getMetadata()).thenReturn(metadata);
+ QueryContext queryContext = new QueryContext.Builder().build();
+ queryContext.setNullHandlingEnabled(nullHandlingEnabled);
+
+ // A group-by on dim1 takes the same range/singleton paths without
applying the residual predicate.
+ StarTreeFilterOperator unfiltered = new
StarTreeFilterOperator(queryContext, starTreeV2, Map.of(), Set.of("dim1"));
+
assertEquals(TestUtils.getDocIds(unfiltered.nextBlock().getBlockDocIdSet()),
+ List.of(0, 2, 3, 65534, 65535, 65536, 65537, 70000));
+
+ when(root.getAggregatedDocId()).thenReturn(70000);
+ StarTreeFilterOperator aggregateOnly = new
StarTreeFilterOperator(queryContext, starTreeV2, Map.of(), null);
+
assertEquals(TestUtils.getDocIds(aggregateOnly.nextBlock().getBlockDocIdSet()),
List.of(70000));
+
+ PredicateEvaluator predicateEvaluator = mock(PredicateEvaluator.class);
+ when(predicateEvaluator.getPredicateType()).thenReturn(Predicate.Type.IN);
+ when(predicateEvaluator.getMatchingDictIds()).thenReturn(new int[]{0, 1});
+ CompositePredicateEvaluator compositePredicateEvaluator =
+ new
CompositePredicateEvaluator(List.of(ObjectBooleanPair.of(predicateEvaluator,
false)));
+ InvertedIndexReader<?> invertedIndex = mock(InvertedIndexReader.class);
+ // Include a matching indexed document outside the selected ranges to
prove the residual is conjoined with them.
+ doReturn(MutableRoaringBitmap.bitmapOf(0, 2, 999, 65535,
65536)).when(invertedIndex).getDocIds(0);
+
doReturn(MutableRoaringBitmap.bitmapOf(70000)).when(invertedIndex).getDocIds(1);
+ DataSourceMetadata dataSourceMetadata = mock(DataSourceMetadata.class);
+ when(dataSourceMetadata.isSingleValue()).thenReturn(true);
+ NullValueVectorReader nullValueVector = mock(NullValueVectorReader.class);
+
when(nullValueVector.getNullBitmap()).thenReturn(MutableRoaringBitmap.bitmapOf(65536));
+ DataSource dataSource = mock(DataSource.class);
Review Comment:
Fixed in c9cedaa462: the fixture now explicitly sets unsorted metadata,
column name, absent dictionary/range index, and the inverted index. It also
asserts `FilterOperatorUtils.getLeafFilterOperator(...)` selects
`InvertedIndexFilterOperator` before exercising the residual conjunction. Both
null-handling cases pass and document 999 remains excluded as an
out-of-selection indexed match.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
