xiangfu0 commented on code in PR #19799:
URL: https://github.com/apache/pinot/pull/19799#discussion_r4224839587
##########
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:
**[efficiency, plausible]** In RoaringBitmap 1.6.23 this is `new
MutableRoaringBitmap(RoaringBitmap)` — a full container-by-container
re-materialization (per-container `CharBuffer`/`LongBuffer` allocate + copy) of
the entire result on every range-path query. For the shape the PR optimizes
(many tiny ranges) this is a clear net win, but for a query matching a few leaf
nodes with very wide ranges the old code did 2-3 cheap range adds and zero
whole-bitmap copies, while the new code pays one full heap→buffer copy
(hundreds of KB for a few-million-doc match) — allocation can regress for that
shape, consistent with the “dense/wider ranges still pay conversion overhead”
caveat in the description. Two cheaper options worth considering: serialize
once and wrap zero-copy (`new
ImmutableRoaringBitmap(ByteBuffer.wrap(RoaringBitmapUtils.serialize(heapMatchingDocIds)))`
— one contiguous allocation; `ImmutableSegmentImpl` already uses the
wrap-serialized-bytes pattern), or only take
the heap path after N range additions so the few-wide-ranges shape keeps the
old single-bitmap behavior.
##########
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:
**[altitude, plausible]** The root cause being worked around here is not
star-tree-specific: buffer `MappeableArrayContainer.iadd(begin, end)` allocates
an exact-size `CharBuffer` on every extending range add (no geometric growth),
while heap `ArrayContainer.iadd` grows via `calculateCapacity` — any repeated
range-add on a `MutableRoaringBitmap` hits the same quadratic re-allocation.
`SortedIndexBasedFilterOperator.getBitmaps()` does the identical per-range
`bitmap.add(left, right + 1L)` loop and would benefit equally. If the
heap-then-convert trick is worth keeping, consider extracting it into a small
shared helper (e.g. next to `RoaringBitmapUtils` in pinot-common) rather than
an inline one-off, and naming the upstream cause
(`MappeableArrayContainer.iadd`) in a comment so the workaround can be retired
if a future RoaringBitmap upgrade fixes the buffer container growth.
##########
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:
**[test robustness, plausible]** This mid-test re-stub of the shared `root`
mock is only safe because the `unfiltered` assertion above has already eagerly
evaluated its traversal via `nextBlock()`, and that traversal never reads
root's aggregated doc id. If the assertions are ever reordered, or the first
assertion is moved below this line, the fixture semantics silently change
across cases instead of failing clearly. Building a fresh root mock (or
stubbing the aggregated id up front in `branch()`) per case would remove the
ordering dependency.
##########
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:
**[test robustness, plausible]** The residual-predicate path routing to an
inverted-index-based operator relies entirely on Mockito defaults for unstubbed
methods (`isSorted()` = false, `getDictionary()` = null, `getColumnName()` =
null — the last tolerated only because the default `QueryContext` has no
skip-indexes), and the test never asserts which leaf operator
`FilterOperatorUtils` actually selected. If the dispatch precedence changes,
the test either dies in `ScanBasedFilterOperator` with a confusing `checkState`
failure instead of an assertion diff, or keeps passing through a different
operator than the fixture was designed to exercise. Stubbing the
routing-relevant methods explicitly (and/or asserting the selected operator
type) would make the intent explicit.
##########
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);
Review Comment:
**[test clarity, minor]** `firstAggregate`'s aggregated doc id of 0
coincides with Mockito's default int return (so this stub verifies nothing if
lost) and doc 0 also appears in the dictId-0 inverted-index bitmap, giving it
dual provenance in the filtered assertion. A unique non-zero id (e.g. 50, with
the expected lists updated) would make each asserted doc id's provenance
unambiguous.
--
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]
