gortiz commented on code in PR #19408:
URL: https://github.com/apache/pinot/pull/19408#discussion_r4123727087
##########
pinot-core/src/main/java/org/apache/pinot/core/common/BlockDocIdSet.java:
##########
@@ -52,6 +56,87 @@ default BlockDocIdSet getOptimizedDocIdSet() {
return this;
}
+ /// Returns whether evaluating this DocIdSet costs time proportional to the
number of documents it is asked about,
+ /// i.e. whether the subtree still has a scan- or expression-based predicate
left to evaluate.
+ ///
+ /// Only such a subtree gains anything from being handed a candidate set. An
index-only subtree produces the same
+ /// bitmap either way, so restricting it just adds intersection work. Note
this is a property of the *DocIdSet*, not
+ /// of the operator that built it: an operator that scans internally and
hands back a bitmap -- a non-exact range
+ /// index, an H3 index -- has already paid for the scan by the time its
DocIdSet exists, and correctly reports
+ /// `false`.
+ default boolean isScanBased() {
+ return false;
+ }
+
+ /// Returns whether a parent AND may defer calling [#iterator] on this
DocIdSet and reach it through [#applyAnd]
+ /// instead.
+ ///
+ /// True only for a composite DocIdSet (AND, OR, NOT) whose subtree is still
scan-based. Forwarding a candidate set
+ /// to its children is how a restriction from an enclosing AND reaches a
scan-based predicate nested inside an OR,
+ /// which would otherwise be evaluated against every document that branch
matches. A leaf is never deferrable: its
+ /// index lookup has already happened, and a scan-based leaf is already
reached through
+ /// [ScanBasedDocIdIterator#applyAnd] by the enclosing AND.
+ ///
+ /// This says nothing about whether [#applyAnd] may be called -- every
DocIdSet supports it.
+ default boolean isApplyAndDeferrable() {
+ return false;
+ }
+
+ /// Returns the document ids matching this DocIdSet that are also in
`docIds`, i.e. the intersection of this
+ /// DocIdSet with the given candidate set.
+ ///
+ /// `docIds` is never modified, so the same candidate set may be handed to
several DocIdSets. The returned bitmap
+ /// must not be modified by the caller either: it may be a view of a bitmap
the DocIdSet still owns.
+ ///
+ /// Like [ScanBasedDocIdIterator#applyAnd], this method consumes the
DocIdSet: call it at most once, and never
+ /// together with [#iterator]. [#getNumEntriesScannedInFilter] stays valid
afterwards.
+ default ImmutableRoaringBitmap applyAnd(ImmutableRoaringBitmap docIds) {
+ if (docIds.isEmpty()) {
+ return new MutableRoaringBitmap();
+ }
+ BlockDocIdIterator docIdIterator = iterator();
+ if (docIdIterator instanceof ScanBasedDocIdIterator) {
+ // The scan only visits the candidate documents, which is the whole
point of the push-down
+ return ((ScanBasedDocIdIterator) docIdIterator).applyAnd(docIds);
Review Comment:
Good catch, done in 0c87bb5ae7: `MVScanDocIdIterator.applyAnd` now closes
its reader context in a `finally` block, which also covers the existing
flat-AND path.
##########
pinot-core/src/test/java/org/apache/pinot/queries/AndRestrictionPushdownQueriesTest.java:
##########
@@ -0,0 +1,121 @@
+/**
+ * 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.queries;
+
+import java.util.List;
+import org.apache.pinot.common.response.broker.BrokerResponseNative;
+import
org.apache.pinot.spi.utils.CommonConstants.Broker.Request.QueryOptionKey;
+import org.testng.annotations.Test;
+
+import static org.testng.Assert.assertEquals;
+import static org.testng.Assert.assertTrue;
+
+
+/// End-to-end test of the AND restriction push-down against a real segment.
+///
+/// The shared `FILTER` is `col1 > x AND col3 BETWEEN y AND z AND col5 =
'gFuH' AND (col6 < w OR col11 NOT IN (..))
+/// AND daysSinceEpoch = d`, i.e. an OR containing scan-based predicates under
an AND with index-based ones -- the
+/// shape from [issue 19339](https://github.com/apache/pinot/issues/19339).
The push-down ships disabled, so this is
+/// the only coverage that runs a real query with it on.
+public class AndRestrictionPushdownQueriesTest extends
BaseSingleValueQueriesTest {
+ private static final String AGGREGATION = "SELECT SUM(column1) FROM
testTable";
+ private static final String SELECTION = "SELECT column1, column5, column11
FROM testTable";
+
+ @Test
+ public void testPushdownScansFewerEntriesAndKeepsTheSameResult() {
+ BrokerResponseNative disabled = getBrokerResponse(withMode("never",
AGGREGATION + FILTER));
+ BrokerResponseNative enabled = getBrokerResponse(withMode("always",
AGGREGATION + FILTER));
+
+ assertRowsEqual(enabled, disabled);
+ assertEquals(enabled.getNumDocsScanned(), disabled.getNumDocsScanned(),
"The same documents must match");
+ assertEquals(enabled.getTotalDocs(), disabled.getTotalDocs());
+ assertTrue(enabled.getNumEntriesScannedInFilter() <
disabled.getNumEntriesScannedInFilter(),
+ "The push-down must reduce the entries scanned in the filter, but
scanned "
+ + enabled.getNumEntriesScannedInFilter() + " with it and " +
disabled.getNumEntriesScannedInFilter()
+ + " without");
+ }
+
+ @Test
+ public void testPushdownKeepsTheSameRowsForASelectionQuery() {
+ // ALWAYS is the only mode that reaches a selection query: AUTO excludes
it because it can stop at its LIMIT
+ assertRowsEqual(getBrokerResponse(withMode("always", SELECTION + FILTER)),
+ getBrokerResponse(withMode("never", SELECTION + FILTER)));
+ }
+
+ @Test
+ public void testAutoLeavesSelectionQueriesAlone() {
+ BrokerResponseNative auto = getBrokerResponse(withMode("auto", SELECTION +
FILTER));
+ BrokerResponseNative disabled = getBrokerResponse(withMode("never",
SELECTION + FILTER));
+
+ assertRowsEqual(auto, disabled);
+ assertEquals(auto.getNumEntriesScannedInFilter(),
disabled.getNumEntriesScannedInFilter(),
+ "AUTO must not push down for a selection query");
+ }
+
+ @Test
+ public void testAutoPushesDownForAnAggregationQuery() {
+ assertEquals(getBrokerResponse(withMode("auto", AGGREGATION +
FILTER)).getNumEntriesScannedInFilter(),
+ getBrokerResponse(withMode("always", AGGREGATION +
FILTER)).getNumEntriesScannedInFilter());
+ }
+
+ @Test
+ public void testDefaultLeavesEveryQueryAlone() {
+ assertEquals(getBrokerResponse(AGGREGATION +
FILTER).getNumEntriesScannedInFilter(),
+ getBrokerResponse(withMode("never", AGGREGATION +
FILTER)).getNumEntriesScannedInFilter(),
+ "The push-down must be off by default");
+ }
+
+ /// Filtered aggregations build the outer AND through
CombinedFilterOperator, where both the main and the sub
+ /// filter can be deferrable, so it can reach the lazy fallback arm of
AndDocIdSet#iterator().
+ @Test
+ public void testPushdownForFilteredAggregation() {
+ String query = "SELECT SUM(column1) FILTER (WHERE column3 > 0), COUNT(*)
FROM testTable" + FILTER;
+
+ assertRowsEqual(getBrokerResponse(withMode("always", query)),
getBrokerResponse(withMode("never", query)));
+ }
+
+ /// With null handling on, AndFilterOperator#getFalses() wraps the push-down
in a NOT over OR(trues, nulls), and
+ /// excludeNulls() builds its AND with the flag -- the two paths where the
push-down changes how nulls flow.
+ @Test
+ public void testPushdownWithNullHandlingKeepsTheSameRows() {
Review Comment:
Agreed. In 0c87bb5ae7 I added `AndRestrictionPushdownNullQueriesTest`: a
segment with null and non-null rows in the scanned columns (`a`, `b`) and an
inverted-indexed seed column. It covers `(a > 50 OR b = 'x')` (`excludeNulls`),
`NOT (a > 50 OR b = 'x')` and `NOT (a > 50 AND b = 'x')` (`getNotFalses`).
ALWAYS and NEVER are both checked against a row-by-row three-valued-logic
evaluation (COUNT, SUM, selection rows), and ALWAYS must scan fewer filter
entries. I removed the old test here, since it could not catch a null
regression.
##########
pinot-core/src/test/java/org/apache/pinot/core/operator/docidsets/AndDocIdSetPushdownTest.java:
##########
@@ -0,0 +1,420 @@
+/**
+ * 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.operator.docidsets;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.OptionalInt;
+import java.util.Random;
+import org.apache.pinot.core.common.BlockDocIdIterator;
+import org.apache.pinot.core.common.BlockDocIdSet;
+import
org.apache.pinot.core.operator.dociditerators.RangelessBitmapDocIdIterator;
+import org.apache.pinot.core.operator.dociditerators.ScanBasedDocIdIterator;
+import org.apache.pinot.segment.spi.Constants;
+import org.apache.pinot.spi.utils.Pairs.IntPair;
+import org.roaringbitmap.BatchIterator;
+import org.roaringbitmap.buffer.ImmutableRoaringBitmap;
+import org.roaringbitmap.buffer.MutableRoaringBitmap;
+import org.testng.annotations.Test;
+
+import static org.testng.Assert.assertEquals;
+import static org.testng.Assert.assertFalse;
+import static org.testng.Assert.assertTrue;
+
+
+/// Unit test for the restriction push-down: an AND hands the document ids
matched by its index-based children to its
+/// composite (AND/OR/NOT) children, so that a scan-based predicate nested
inside one of them is only evaluated on the
+/// documents that can still match.
+///
+/// See [issue 19339](https://github.com/apache/pinot/issues/19339).
+public class AndDocIdSetPushdownTest {
+ private static final int NUM_DOCS = 10000;
+ private static final long RANDOM_SEED = System.currentTimeMillis();
+ private static final String ERROR_MESSAGE = "Random seed: " + RANDOM_SEED;
+
+ /// The shape reported in the issue: a scan-based predicate sits in an OR
branch next to an index-based predicate.
+ /// That makes the branch take the eager path in [AndDocIdSet#iterator],
materializing it over the whole segment and
+ /// evaluating the scan on every document its sibling matches, regardless of
how selective the enclosing AND is.
+ @Test
+ public void testScanNestedInsideOrBranchIsRestrictedByEnclosingAnd() {
+ ImmutableRoaringBitmap selective = range(0, 100);
+ ImmutableRoaringBitmap indexedInBranch = range(0, 5000);
+ ImmutableRoaringBitmap otherBranch = range(9000, 9010);
+ ImmutableRoaringBitmap scanMatches = multiplesOf(3);
+
+ // Expected: selective AND ((indexedInBranch AND scanMatches) OR
otherBranch)
+ MutableRoaringBitmap expected = MutableRoaringBitmap.and(indexedInBranch,
scanMatches);
+ expected.or(otherBranch);
+ expected.and(selective);
+
+ CountingScanDocIdSet pushedDownScan = new
CountingScanDocIdSet(scanMatches);
+ BlockDocIdSet withPushdown = orBranchTree(true, pushedDownScan, selective,
indexedInBranch, otherBranch);
+ assertEquals(collectDocIds(withPushdown), expected.toArray());
+ long scannedWithPushdown = pushedDownScan.getNumEntriesScannedInFilter();
+ assertEquals(scannedWithPushdown, selective.getCardinality(),
+ "The scan must only visit the documents matching the enclosing AND");
+ assertEquals(withPushdown.getNumEntriesScannedInFilter(),
scannedWithPushdown,
+ "Entries scanned inside the OR must be reported by the enclosing AND");
+
+ CountingScanDocIdSet unrestrictedScan = new
CountingScanDocIdSet(scanMatches);
+ BlockDocIdSet withoutPushdown =
+ orBranchTree(false, unrestrictedScan, selective, indexedInBranch,
otherBranch);
+ assertEquals(collectDocIds(withoutPushdown), expected.toArray(),
+ "Disabling the push-down must not change the result");
+ long scannedWithoutPushdown =
unrestrictedScan.getNumEntriesScannedInFilter();
+ assertEquals(scannedWithoutPushdown, indexedInBranch.getCardinality(),
+ "Without the push-down the scan visits every document matching its
sibling index predicate");
+ assertTrue(scannedWithPushdown < scannedWithoutPushdown,
+ "The push-down must reduce the number of scanned entries");
+ }
+
+ /// AND(selective, NOT(scan)): the scan only has to be evaluated on the
candidates, because
+ /// `NOT(child) AND candidates == candidates MINUS (child AND candidates)`.
+ @Test
+ public void testScanUnderNotIsRestrictedByEnclosingAnd() {
+ ImmutableRoaringBitmap selective = range(0, 100);
+ ImmutableRoaringBitmap scanMatches = multiplesOf(3);
+
+ MutableRoaringBitmap expected = selective.toMutableRoaringBitmap();
+ expected.andNot(scanMatches);
+
+ CountingScanDocIdSet scan = new CountingScanDocIdSet(scanMatches);
+ BlockDocIdSet docIdSet = new AndDocIdSet(
+ List.of(new BitmapDocIdSet(selective, NUM_DOCS), new NotDocIdSet(scan,
NUM_DOCS)), null, true);
+
+ assertEquals(collectDocIds(docIdSet), expected.toArray());
+ assertEquals(scan.getNumEntriesScannedInFilter(),
selective.getCardinality(),
+ "The scan under the NOT must only visit the documents matching the
enclosing AND");
+ }
+
+ /// With no index-based child there is nothing to seed the push-down with,
so the AND must fall back to the lazy
+ /// iterator over all of its children, including the deferred composite ones.
+ @Test
+ public void testFallsBackToLazyPathWithoutIndexBasedChild() {
+ ImmutableRoaringBitmap firstBranch = range(0, 50);
+ ImmutableRoaringBitmap secondBranch = range(40, 90);
+ ImmutableRoaringBitmap scanMatches = multiplesOf(3);
+
+ MutableRoaringBitmap expected = firstBranch.toMutableRoaringBitmap();
+ expected.or(secondBranch);
+ expected.and(scanMatches);
+
+ BlockDocIdSet or = new OrDocIdSet(
+ List.of(new BitmapDocIdSet(firstBranch, NUM_DOCS), new
BitmapDocIdSet(secondBranch, NUM_DOCS)), NUM_DOCS);
Review Comment:
Right, done in 0c87bb5ae7: one OR leaf is now a `CountingScanDocIdSet`, and
the test asserts `or.isApplyAndDeferrable()` so it cannot silently stop
reaching the lazy fallback.
##########
pinot-core/src/main/java/org/apache/pinot/core/common/BlockDocIdSet.java:
##########
@@ -52,6 +56,87 @@ default BlockDocIdSet getOptimizedDocIdSet() {
return this;
}
+ /// Returns whether evaluating this DocIdSet costs time proportional to the
number of documents it is asked about,
+ /// i.e. whether the subtree still has a scan- or expression-based predicate
left to evaluate.
+ ///
+ /// Only such a subtree gains anything from being handed a candidate set. An
index-only subtree produces the same
+ /// bitmap either way, so restricting it just adds intersection work. Note
this is a property of the *DocIdSet*, not
+ /// of the operator that built it: an operator that scans internally and
hands back a bitmap -- a non-exact range
+ /// index, an H3 index -- has already paid for the scan by the time its
DocIdSet exists, and correctly reports
+ /// `false`.
+ default boolean isScanBased() {
+ return false;
+ }
+
+ /// Returns whether a parent AND may defer calling [#iterator] on this
DocIdSet and reach it through [#applyAnd]
+ /// instead.
+ ///
+ /// True only for a composite DocIdSet (AND, OR, NOT) whose subtree is still
scan-based. Forwarding a candidate set
+ /// to its children is how a restriction from an enclosing AND reaches a
scan-based predicate nested inside an OR,
+ /// which would otherwise be evaluated against every document that branch
matches. A leaf is never deferrable: its
+ /// index lookup has already happened, and a scan-based leaf is already
reached through
+ /// [ScanBasedDocIdIterator#applyAnd] by the enclosing AND.
+ ///
+ /// This says nothing about whether [#applyAnd] may be called -- every
DocIdSet supports it.
+ default boolean isApplyAndDeferrable() {
+ return false;
+ }
+
+ /// Returns the document ids matching this DocIdSet that are also in
`docIds`, i.e. the intersection of this
+ /// DocIdSet with the given candidate set.
+ ///
+ /// `docIds` is never modified, so the same candidate set may be handed to
several DocIdSets. The returned bitmap
+ /// must not be modified by the caller either: it may be a view of a bitmap
the DocIdSet still owns.
+ ///
+ /// Like [ScanBasedDocIdIterator#applyAnd], this method consumes the
DocIdSet: call it at most once, and never
+ /// together with [#iterator]. [#getNumEntriesScannedInFilter] stays valid
afterwards.
+ default ImmutableRoaringBitmap applyAnd(ImmutableRoaringBitmap docIds) {
+ if (docIds.isEmpty()) {
+ return new MutableRoaringBitmap();
+ }
+ BlockDocIdIterator docIdIterator = iterator();
+ if (docIdIterator instanceof ScanBasedDocIdIterator) {
+ // The scan only visits the candidate documents, which is the whole
point of the push-down
+ return ((ScanBasedDocIdIterator) docIdIterator).applyAnd(docIds);
+ }
+ if (docIdIterator instanceof BitmapBasedDocIdIterator) {
+ return ImmutableRoaringBitmap.and(((BitmapBasedDocIdIterator)
docIdIterator).getDocIds(), docIds);
+ }
+ if (docIdIterator instanceof SortedDocIdIterator) {
+ MutableRoaringBitmap docIdsFromRanges = new MutableRoaringBitmap();
+ for (IntPair docIdRange : ((SortedDocIdIterator)
docIdIterator).getDocIdRanges()) {
+ // NOTE: docIdRange has inclusive start and end.
+ docIdsFromRanges.add(docIdRange.getLeft(), docIdRange.getRight() + 1L);
+ }
+ docIdsFromRanges.and(docIds);
+ return docIdsFromRanges;
+ }
+ // Generic fallback: drive the iterator from the candidate set so that it
is only asked about candidate documents
+ return collect(new AndDocIdIterator(
+ new BlockDocIdIterator[]{new RangelessBitmapDocIdIterator(docIds),
docIdIterator}));
+ }
+
+ /// Releases a DocIdSet that will not be evaluated, e.g. an OR branch a
short-circuit skipped past.
+ ///
+ /// Scan-based DocIdSets build their iterator in the constructor, and that
iterator holds a
+ /// `ForwardIndexReaderContext` -- a direct ByteBuffer for a
chunk-compressed column. Evaluation normally releases it
+ /// because the iterator closes itself on reaching EOF, so a DocIdSet that
is never evaluated has to be released
+ /// explicitly. Calling this instead of evaluating never reads any data.
+ default void release() {
+ iterator().close();
+ }
+
+ /// Materializes the document ids remaining in the given iterator.
+ static MutableRoaringBitmap collect(BlockDocIdIterator docIdIterator) {
Review Comment:
Done in 0c87bb5ae7: `toNonScanDocIdSet()` now returns `new
RangelessBitmapDocIdSet(collect(docIdIterator))`.
--
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]
