xiangfu0 commented on code in PR #19408:
URL: https://github.com/apache/pinot/pull/19408#discussion_r4105094375
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/OrDocIdSet.java:
##########
@@ -133,6 +138,82 @@ public long getNumEntriesScannedInFilter() {
return _numEntriesScannedInFilter + numEntriesScannedForScanBasedDocIdSets;
}
+ @Override
+ public boolean isScanBased() {
+ List<BlockDocIdSet> docIdSets = _docIdSets;
+ if (docIdSets == null) {
+ return false;
+ }
+ for (BlockDocIdSet docIdSet : docIdSets) {
+ if (docIdSet.isScanBased()) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ @Override
+ public boolean isApplyAndDeferrable() {
+ return isScanBased();
+ }
+
+ /// Unions the branches, each restricted to the candidate document ids.
+ ///
+ /// A branch only has to look at the candidates no earlier branch has
matched yet, because
+ /// `(A OR B) AND S == (A AND S) OR (B AND (S MINUS (A AND S)))`. That
matters because the cost of a scan-based
+ /// branch is linear in the size of the candidate set it is given, so
handing every branch the full candidate set
+ /// would scan it once per branch.
+ @Override
+ public ImmutableRoaringBitmap applyAnd(ImmutableRoaringBitmap docIds) {
Review Comment:
Consider bounding the candidate set at entry, mirroring `NotDocIdSet`:
`docIds = NotDocIdSet.bound(docIds, _numDocs)` (or promote `bound` to a shared
helper).
NOT and MatchAll are bounded, but a bitmap **leaf** under this OR is reached
through the default `BlockDocIdSet#applyAnd`, which intersects the raw
`BitmapBasedDocIdIterator.getDocIds()` with no `[0, numDocs)` clamp. On the
lazy path this replaces, bitmap leaves are always clamped
(`BitmapDocIdIterator#next()`, and `iterator()` above wraps its merged bitmap
in `new BitmapDocIdIterator(docIds, _numDocs)`). So on a realtime segment whose
bitmaps grow past the query snapshot, a candidate id >= `numDocs` that also
appears in a branch's raw bitmap survives the push-down where master would drop
it. "An intersection cannot introduce such ids" is true, but it can *preserve*
ids the old iterator path would have excluded.
Racy realtime-only edge case behind a default-off flag, so not blocking -
but it is a one-line fix in exactly the contract area #15756 showed to be
fragile, and bounding here covers every leaf reached through an OR. A test with
a tail-carrying `BitmapDocIdSet` under a deferred OR would pin it.
(Minor, same method: the `docIds.isEmpty()` early return skips releasing the
branches. Unreachable from current callers - `AndDocIdSet` guards, and the loop
below never hands a branch an empty set - but cheap to make safe.)
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/NotDocIdSet.java:
##########
@@ -41,4 +43,46 @@ public BlockDocIdIterator iterator() {
public long getNumEntriesScannedInFilter() {
return _childDocIdSet.getNumEntriesScannedInFilter();
}
+
+ @Override
+ public boolean isScanBased() {
+ return _childDocIdSet.isScanBased();
+ }
+
+ @Override
+ public boolean isApplyAndDeferrable() {
+ return isScanBased();
+ }
+
+ @Override
+ public void release() {
+ _childDocIdSet.release();
+ }
+
+ @Override
+ public ImmutableRoaringBitmap applyAnd(ImmutableRoaringBitmap docIds) {
+ if (docIds.isEmpty()) {
+ return new MutableRoaringBitmap();
+ }
+ // NOTE: The candidate set can carry document ids beyond numDocs, because
BitmapDocIdIterator#getDocIds() hands out
+ // the raw bitmap while its next() stops at numDocs. An intersection
cannot introduce such ids, but a
+ // complement can, so the bound NotDocIdIterator applies has to be
applied here too.
+ ImmutableRoaringBitmap boundedDocIds = bound(docIds, _numDocs);
+ if (boundedDocIds.isEmpty()) {
Review Comment:
Both empty early returns in this method skip `_childDocIdSet.release()`. The
`docIds.isEmpty()` one is guarded by every current caller, but this
`boundedDocIds.isEmpty()` path is reachable (all candidates >= `numDocs`), and
the child - e.g. a scan whose iterator was built in its constructor - then
never gets its `ForwardIndexReaderContext` closed. Since `release()` exists
precisely for subtrees that are never evaluated, suggest calling it on both
paths.
##########
pinot-common/src/main/java/org/apache/pinot/common/utils/config/QueryOptionsUtils.java:
##########
@@ -341,6 +342,25 @@ public static boolean
isAndScanReorderingEnabled(Map<String, String> queryOption
return
Boolean.parseBoolean(queryOptions.get(QueryOptionKey.AND_SCAN_REORDERING));
}
+ /// Per-query override of [AndRestrictionPushdownMode], or `null` when the
query does not set one, in which case
+ /// the server default applies.
+ @Nullable
+ public static AndRestrictionPushdownMode
getAndRestrictionPushdownMode(Map<String, String> queryOptions) {
+ String mode =
queryOptions.get(QueryOptionKey.AND_RESTRICTION_PUSHDOWN_MODE);
+ return mode != null ?
parseAndRestrictionPushdownMode(QueryOptionKey.AND_RESTRICTION_PUSHDOWN_MODE,
mode) : null;
+ }
+
+ /// Parses an [AndRestrictionPushdownMode], naming the offending key and the
legal values on failure. The option
+ /// reads like a toggle, so `true`/`false` is a likely mistake and the
message has to say so.
Review Comment:
Nit: the comment says the message has to call out that `true`/`false` is a
likely mistake, but the message below only lists the legal values. Either
extend the message (e.g. append "this option is a mode, not a boolean toggle")
or trim the comment. While here, deriving the list from
`AndRestrictionPushdownMode.values()` would keep it from drifting if a mode is
ever added.
##########
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()) {
Review Comment:
Same `release()` consideration as in the composites: for a scan-based
DocIdSet the iterator (and its `ForwardIndexReaderContext`) already exists by
the time this early return fires, and nothing closes it. All current callers
guard against empty candidates so this is latent, but calling `release()` here
instead of the bare return makes the contract self-enforcing rather than
convention-enforced.
##########
pinot-core/src/test/java/org/apache/pinot/core/plan/maker/AndRestrictionPushdownModeTest.java:
##########
@@ -0,0 +1,129 @@
+/**
+ * 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.plan.maker;
+
+import java.util.Map;
+import javax.annotation.Nullable;
+import org.apache.pinot.core.query.request.context.QueryContext;
+import
org.apache.pinot.core.query.request.context.utils.QueryContextConverterUtils;
+import org.apache.pinot.spi.env.PinotConfiguration;
+import
org.apache.pinot.spi.utils.CommonConstants.Broker.Request.QueryOptionKey;
+import org.apache.pinot.spi.utils.CommonConstants.Server;
+import org.testng.annotations.Test;
+
+import static org.testng.Assert.assertFalse;
+import static org.testng.Assert.assertTrue;
+
+
+/// Tests how [InstancePlanMakerImplV2] resolves
[Server.AndRestrictionPushdownMode] into the per-query flag read by
+/// the AND filter operators.
+///
+/// Under `AUTO` the push-down is skipped for a selection query without ORDER
BY: it stops once it has LIMIT rows,
+/// while the push-down materializes the whole filter result. See
+/// [issue 19339](https://github.com/apache/pinot/issues/19339).
+public class AndRestrictionPushdownModeTest {
+ private static final String SELECTION_ONLY = "SELECT col1 FROM testTable
WHERE col2 = 1";
+ private static final String SELECTION_ORDER_BY = "SELECT col1 FROM testTable
WHERE col2 = 1 ORDER BY col1";
+ private static final String AGGREGATION = "SELECT SUM(col1) FROM testTable
WHERE col2 = 1";
+ private static final String GROUP_BY = "SELECT col1, SUM(col3) FROM
testTable WHERE col2 = 1 GROUP BY col1";
+ private static final String DISTINCT = "SELECT DISTINCT col1 FROM testTable
WHERE col2 = 1";
+
+ @Test
+ public void testDefaultIsNever() {
+ assertFalse(resolve(null, AGGREGATION), "The push-down ships disabled");
+ assertFalse(resolve(null, SELECTION_ONLY));
+ }
+
+ @Test
+ public void testAutoSkipsQueriesThatCanStopEarly() {
+ assertFalse(resolve("auto", SELECTION_ONLY), "A selection-only query stops
at its LIMIT");
+ assertFalse(resolve("auto", DISTINCT), "DistinctOperator stops once it has
LIMIT rows");
+ // Whether an ORDER BY selection can stop early is decided per segment, so
AUTO excludes it conservatively
+ assertFalse(resolve("auto", SELECTION_ORDER_BY));
+ assertFalse(resolve("auto", AGGREGATION + " LIMIT 0"), "LIMIT 0 reads
nothing");
+ }
+
+ @Test
+ public void testAutoAppliesToQueriesThatReadEveryMatchingDocument() {
+ assertTrue(resolve("auto", AGGREGATION));
+ assertTrue(resolve("auto", GROUP_BY));
+ }
+
+ @Test
+ public void testAlwaysAppliesEvenToQueriesThatCanStopEarly() {
+ assertTrue(resolve("always", SELECTION_ONLY));
+ assertTrue(resolve("always", DISTINCT));
+ }
+
+ @Test
+ public void testNeverSkipsEvenAggregationQuery() {
+ assertFalse(resolve("never", AGGREGATION));
+ }
+
+ @Test
+ public void testModeIsCaseInsensitive() {
+ assertTrue(resolve("AlWaYs", SELECTION_ONLY));
+ assertTrue(resolve("AuTo", AGGREGATION));
+ }
+
+ @Test(expectedExceptions = IllegalArgumentException.class)
+ public void testInvalidQueryOptionValueIsRejected() {
+ // A boolean is the most likely mistake, since the option name reads like
a toggle
+ resolve("true", AGGREGATION);
+ }
+
+ @Test(expectedExceptions = IllegalArgumentException.class)
+ public void testInvalidServerConfigValueIsRejected() {
+ planMakerWithServerDefault("sometimes");
+ }
+
+ @Test
+ public void testServerDefaultAppliesWithoutQueryOption() {
+ InstancePlanMakerImplV2 planMaker = planMakerWithServerDefault("always");
+ QueryContext queryContext =
QueryContextConverterUtils.getQueryContext(SELECTION_ONLY);
+ planMaker.applyQueryOptions(queryContext);
+ assertTrue(queryContext.isAndRestrictionPushdownEnabled(), "The server
default must apply");
+ }
+
+ @Test
+ public void testQueryOptionOverridesServerDefault() {
+ InstancePlanMakerImplV2 planMaker = planMakerWithServerDefault("always");
+ QueryContext queryContext =
QueryContextConverterUtils.getQueryContext(AGGREGATION);
+
queryContext.getQueryOptions().put(QueryOptionKey.AND_RESTRICTION_PUSHDOWN_MODE,
"never");
+ planMaker.applyQueryOptions(queryContext);
+ assertFalse(queryContext.isAndRestrictionPushdownEnabled(), "The query
option must win over the server default");
+ }
+
+ private static InstancePlanMakerImplV2 planMakerWithServerDefault(String
mode) {
+ InstancePlanMakerImplV2 planMaker = new InstancePlanMakerImplV2();
+ planMaker.init(new
PinotConfiguration(Map.of(Server.AND_RESTRICTION_PUSHDOWN_MODE, mode)));
+ return planMaker;
+ }
+
+ /// Resolves the flag for the given query, optionally setting the
`andRestrictionPushdown` query option. With no
+ /// option the server default (AUTO) applies.
Review Comment:
Nit: the server default is `NEVER` (as `testDefaultIsNever` asserts), not
`AUTO`.
--
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]
