You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pinot.apache.org by "yashmayya (via GitHub)" <gi...@apache.org> on 2026/09/25 21:36:35 UTC
[PR] Seal large IN lists from Calcite during multi-stage planning [pinot]
yashmayya opened a new pull request, #19674:
URL: https://github.com/apache/pinot/pull/19674
## Summary
Multi-stage (MSE) planning time for queries with large IN lists grows much faster than the list size. This has caused production planning timeouts for years (#13617 and the follow-ups below). The cause keeps coming back with each Calcite upgrade and each new planner rule.
This PR hides large IN lists from Calcite while the query is optimized ("sealing"), and restores them after the last rule phase. Calcite sees one small, deterministic function call instead of the value list. For all tested query shapes, EXPLAIN and the plans that servers get are the same as without sealing. The one known difference is in "What changes and what does not".
Measured on the same build with sealing off (`0`, same as master) and on (default `20`):
| Query | Values | Sealing off | Sealing on |
|---|---|---|---|
| Fact table with 2 LEFT JOINs, 3 IN filters, GROUP BY 16 keys, FILTER aggregates, ORDER BY LIMIT | 100,000 | 3,363 ms | 795 ms |
| Same query, V2 physical optimizer | 100,000 | 2,896 ms | 852 ms |
| `JOIN ... ON a.k = b.k AND b.x IN (...)` | 400 | 2,505 ms | 23 ms |
| `JOIN ... ON a.k = b.k AND b.x IN (...)` | 800 | 24.3 s | 43 ms |
| `SUM(CASE WHEN x IN (...) THEN 1 ELSE 0 END)` | 800 | 21.4 s | 35 ms |
| Single table, `WHERE x IN (...)` | 100,000 | 650 ms | 542 ms |
The optimize phase of the first query takes 12–16 ms at every list size with sealing, against 2,514 ms at 100k values without it. Full tables and the method are in the Benchmarks section below.
## Root cause
- Calcite has two regimes for IN lists. A list with fewer than `inSubQueryThreshold` values (default 20) becomes `SEARCH(col, Sarg[...])`, which Calcite optimizes in depth. A longer list becomes a join against an inline `VALUES` table, so the values are data that the simplifier never reads.
- Pinot sets `withInSubQueryThreshold(Integer.MAX_VALUE)` (#10168), so every list stays one `SEARCH` call through every rule and metadata call.
- `RexSimplify` rebuilds the whole range set of the Sarg on every AND or OR that holds it, even when nothing merges. At 37k values this costs about 29 ms and 26 MB per call.
- The number of such calls grows with each release. CALCITE-5036 (Calcite 1.31) and CALCITE-7302 (1.42) added calls in predicate inference. #18554 and #18720 added rules that call `getPulledUpPredicates`. On 1.42, one `getPulledUpPredicates(Join)` call costs 122 ms at 37k values, compared with 2 ms on 1.40.
- HepPlanner clears the metadata cache of a node and all its ancestors after each rewrite, so the same inference runs many times per query.
- Outside WHERE and HAVING (JOIN ON, CASE, `FILTER (WHERE ...)`, the SELECT list, GROUP BY and window expressions), SqlToRel builds an OR of N equalities, and `RelBuilder` simplifies each term against the negation of all earlier terms. This is cubic: on master, 800 values take 20+ s to plan. It is not a 1.42 regression, and no rule config avoids it.
## How it works
1. **Mark** (`SearchSealer#markInLists`). After validation, each `IN` / `NOT IN` with at least T values gets a marker operator in place (`PinotInListOperator`). The marker keeps the name, type derivation and unparse of the original, and it is restored right after SqlToRel. Its kind is not `IN`, so SqlToRel does not expand the list into an OR.
2. **Convert** (`PinotConvertletTable`). Each value becomes `operand = value` through the standard convertlets, exactly like `convertInToOr`, so the types and casts are the same as today. The points of one operand are folded once into one `SEARCH` with `RexBuilder#makeIn`. `NOT IN` uses the negated Sarg. NULL and non-literal values stay as exact OR / AND terms. There is no OR of N terms, so the cubic path is gone.
3. **Seal** (`SearchSealer#seal`). After SqlToRel and field trimming, each filter and join condition that holds a large Sarg is simplified once, like `RelBuilder#filter` does. So the other predicates on the same operand fold into the Sarg exactly as today: `x IS NOT NULL`, ranges, a second list, and contradictions such as `x IN (...) AND x = 5`. Then every `SEARCH` with at least T ranges is sealed, including one that Calcite built from a user-written `x = 1 OR x = 2 ...` chain.
4. **Unseal** (`SearchSealer#unseal`). After the trait program, every sealed call becomes `SEARCH(operand, sarg)` again, and `NOT(sealed)` becomes a `SEARCH` with the negated Sarg, as `RexSimplify` builds today. Copied nodes keep their traits: `LogicalJoin#copy` drops the trait set it is given, so joins are created again with their distribution. `RexExpressionUtils` also accepts a sealed call, in case a conversion runs before the end.
`PinotSealedSearchOperator` is the sealed form. Each distinct Sarg of a query gets its own instance, which holds the Sarg literal:
| Property | Value | Why |
|---|---|---|
| Digest, `equals`, `hashCode` | `$SEARCH#<id>(operand)`, identity | O(1). Different sets never merge, and equal sets share one instance. |
| Kind | `OTHER_FUNCTION` | Calcite reads operand 1 of every `SEARCH` as a Sarg literal. |
| Deterministic, safe | yes | Rules can push it down, pull it up and copy it across equi-joins. |
| `Strong` policy | `ANY` for `NULL AS UNKNOWN`, `NOT_NULL` otherwise | The same answers as `Strong` gives for `SEARCH`, so null-rejecting filters still turn outer joins into inner joins. |
| Return type | `BOOLEAN`, nullable like `SqlSearchOperator` | Row types stay stable across rewrites. |
| Folding | not folded during optimization | Pinot's HepPlanner has no executor. Unseal and `RexExpressionUtils` fold a literal operand, as for `SEARCH`. |
The state is in the operator, not in a `RexCall` subclass, because `RexCopier` and `RexBuilder#makeCall` rebuild calls from `call.getOperator()`.
This PR also changes `RexExpressionUtils#handleSearch` for a Sarg that mixes points and ranges, for example `x IN (<list>) OR x > 10` or `x NOT IN (<list>) AND x > 0`. Today each point becomes `x >= v AND x <= v`, so the servers scan the segment once per value. With a 10k-value list this shape costs 2.7–8.8 s per 250k-row segment on master, against 3 ms for the same query in the single-stage engine, and the stage is 8x larger. Now, when the ranges (or their complement) hold at least 20 single points, the points become one `IN` (or `NOT_IN`) plus the other ranges. Smaller Sargs keep today's shape. `BIG_DECIMAL` keeps today's shape too, because an intermediate stage matches `IN` values with `equals`, which depends on the scale.
## What changes and what does not
- No change for the tested shapes: the leaf filter, broker segment and partition pruning, EXPLAIN output, serialized stage plans, exchange distributions, and the V2 physical optimizer input.
- No wire change: the sealed operator never leaves the broker, so mixed broker and server versions are safe.
- Kept: filter push-down, transitive predicates across equi-joins, outer-join simplification, and hints.
- Lost for sealed lists (T or more values): reasoning across plan nodes during optimization. When a rule moves a predicate next to a sealed list on the same column (for example a `WHERE` filter pushed into a join input that has a list from the `ON` clause), Calcite does not merge it into the Sarg. Contradictions across clauses are not folded during planning, and the query returns 0 rows at runtime.
- One visible case of this: an explicit `x IS NOT NULL` in another clause than a sealed list on `x` is dropped as redundant when the two meet. This is correct in SQL, and plans with null handling on return the same rows. With per-column nullable schemas and null handling off, the leaf no longer filters the rows where `x` is null. Master already does this today for `x < 5 AND x IS NOT NULL`, even in one clause. The same case in one clause keeps its null check (tested).
## Config
- Broker config `pinot.broker.multistage.sealed.in.list.threshold` and query option `sealedInListThreshold`. Default: 20, the same size at which Calcite itself stops treating an IN list as a scalar predicate.
- `0` or a negative value turns sealing off (master behavior). This is the kill switch, per broker or per query.
- Planning outside the broker's multi-stage request handler (for example the controller `/sql` endpoint) does not read the broker config and uses the default. The query option works everywhere.
## Why not the alternatives
- **Calcite's default (IN list → join against `VALUES`).** Measured with `inSubQueryThreshold=20` on a 2M-row table: `NOT IN`, `IN ... OR ...` and CASE shapes shuffle 2.0M–8.1M rows where 15 rows move today. V2 always shuffles the fact rows, and broker pruning is lost. Since Calcite 1.38 (CALCITE-6599), `RelMdPredicates` turns the VALUES table back into one big Sarg, so planning is 1.3–4x slower. With `expand=true` it also returns NULL rows for `NOT IN` on nullable columns, and it fails for IN lists in `JOIN ... ON`. Earlier attempts (#13605, #15027) hit the same problems.
- **Fix Calcite.** A 54-line `RexSimplify` patch removes the 1.42 cost (122 ms → 2 ms per join call). It does not remove the cubic SqlToRel path, and it does not protect against the next caller. It is worth doing upstream as well.
- **Disable rules.** This removes one caller at a time and loses the optimizations of those rules for all queries.
## Benchmarks
- Method: planning only (parse to dispatchable plan), on the same build with `SET sealedInListThreshold=0` (off, same as master) and the default (on). Synthetic tables: a 22-column fact table on 4 servers with 16 segments, and 2 dimension tables. Warm medians on an Apple Silicon laptop with JDK 25. Compare ratios, not absolute times.
- IN plus a range on the same column (`x NOT IN (<10k values>) AND x > 0`): master ships 795,076 bytes in the leaf stage, one range per value. This PR ships 98,047 bytes (one `NOT_IN` plus the range), as SSE does.
<details>
<summary>Full tables</summary>
#### Linear shapes (V1 planner, default rules)
| Query | N | Off | On | Speed-up | Optimize off → on |
|---|---|---|---|---|---|
| Fact + 2 LEFT JOINs, 3 IN filters, GROUP BY 16 keys, FILTER aggs, ORDER BY LIMIT | 1,000 | 66 ms | 43 ms | 1.5x | 30 → 12 ms |
| Fact + 2 LEFT JOINs, 3 IN filters, GROUP BY 16 keys, FILTER aggs, ORDER BY LIMIT | 10,000 | 322 ms | 135 ms | 2.4x | 219 → 12 ms |
| Fact + 2 LEFT JOINs, 3 IN filters, GROUP BY 16 keys, FILTER aggs, ORDER BY LIMIT | 40,000 | 1,326 ms | 426 ms | 3.1x | 922 → 15 ms |
| Fact + 2 LEFT JOINs, 3 IN filters, GROUP BY 16 keys, FILTER aggs, ORDER BY LIMIT | 100,000 | 3,363 ms | 795 ms | 4.2x | 2,514 → 15 ms |
| Same, wrapped in an outer COUNT / SUM | 1,000 | 62 ms | 46 ms | 1.3x | 31 → 12 ms |
| Same, wrapped in an outer COUNT / SUM | 10,000 | 309 ms | 120 ms | 2.6x | 215 → 12 ms |
| Same, wrapped in an outer COUNT / SUM | 40,000 | 1,303 ms | 437 ms | 3.0x | 895 → 15 ms |
| Same, wrapped in an outer COUNT / SUM | 100,000 | 3,298 ms | 793 ms | 4.2x | 2,512 → 15 ms |
| Same with NOT IN | 1,000 | 70 ms | 47 ms | 1.5x | 37 → 12 ms |
| Same with NOT IN | 10,000 | 330 ms | 128 ms | 2.6x | 227 → 11 ms |
| Same with NOT IN | 40,000 | 1,320 ms | 450 ms | 2.9x | 891 → 15 ms |
| Same with NOT IN | 100,000 | 3,594 ms | 923 ms | 3.9x | 2,636 → 16 ms |
| Single table, WHERE x IN (...) | 1,000 | 20 ms | 21 ms | 0.9x | 2 → 2 ms |
| Single table, WHERE x IN (...) | 10,000 | 94 ms | 78 ms | 1.2x | 2 → 2 ms |
| Single table, WHERE x IN (...) | 40,000 | 334 ms | 285 ms | 1.2x | 4 → 2 ms |
| Single table, WHERE x IN (...) | 100,000 | 650 ms | 542 ms | 1.2x | 10 → 3 ms |
| Single table, two lists on two columns | 1,000 | 39 ms | 37 ms | 1.0x | 7 → 2 ms |
| Single table, two lists on two columns | 10,000 | 145 ms | 123 ms | 1.2x | 31 → 3 ms |
| Single table, two lists on two columns | 40,000 | 674 ms | 526 ms | 1.3x | 145 → 3 ms |
| Single table, two lists on two columns | 100,000 | 1,670 ms | 1,341 ms | 1.2x | 400 → 3 ms |
| CTE with the list, referenced twice | 1,000 | 30 ms | 34 ms | 0.9x | 4 → 4 ms |
| CTE with the list, referenced twice | 10,000 | 113 ms | 109 ms | 1.0x | 6 → 3 ms |
| CTE with the list, referenced twice | 40,000 | 448 ms | 356 ms | 1.3x | 7 → 4 ms |
| CTE with the list, referenced twice | 100,000 | 966 ms | 815 ms | 1.2x | 9 → 4 ms |
#### Prod shape with the V2 physical optimizer
| Query | N | Off | On | Speed-up | Optimize off → on |
|---|---|---|---|---|---|
| Fact + 2 LEFT JOINs, 3 IN filters, GROUP BY 16 keys, FILTER aggs, ORDER BY LIMIT | 40,000 | 1,206 ms | 427 ms | 2.8x | 811 → 10 ms |
| Fact + 2 LEFT JOINs, 3 IN filters, GROUP BY 16 keys, FILTER aggs, ORDER BY LIMIT | 100,000 | 2,896 ms | 852 ms | 3.4x | 2,065 → 10 ms |
#### Positions that are cubic today
| Query | N | Off | On | Speed-up |
|---|---|---|---|---|
| JOIN ... ON a.k = b.k AND b.x IN (...) | 100 | 50 ms | 18 ms | 2.8x |
| JOIN ... ON a.k = b.k AND b.x IN (...) | 200 | 294 ms | 21 ms | 14.2x |
| JOIN ... ON a.k = b.k AND b.x IN (...) | 400 | 2,505 ms | 23 ms | 108.9x |
| JOIN ... ON a.k = b.k AND b.x IN (...) | 800 | 24.3 s | 43 ms | 570.8x |
| LEFT JOIN ... ON ... AND a.x IN (...) | 100 | 48 ms | 16 ms | 3.0x |
| LEFT JOIN ... ON ... AND a.x IN (...) | 200 | 296 ms | 21 ms | 14.4x |
| LEFT JOIN ... ON ... AND a.x IN (...) | 400 | 2,413 ms | 23 ms | 104.5x |
| SUM(CASE WHEN x IN (...) ...) | 100 | 46 ms | 14 ms | 3.2x |
| SUM(CASE WHEN x IN (...) ...) | 200 | 277 ms | 18 ms | 15.1x |
| SUM(CASE WHEN x IN (...) ...) | 400 | 2,434 ms | 19 ms | 127.4x |
| SUM(CASE WHEN x IN (...) ...) | 800 | 21.4 s | 35 ms | 607.1x |
| COUNT(*) FILTER (WHERE x IN (...)) | 100 | 45 ms | 13 ms | 3.4x |
| COUNT(*) FILTER (WHERE x IN (...)) | 200 | 279 ms | 17 ms | 16.8x |
| COUNT(*) FILTER (WHERE x IN (...)) | 400 | 2,437 ms | 18 ms | 131.7x |
| SELECT x IN (...) | 100 | 42 ms | 11 ms | 3.7x |
| SELECT x IN (...) | 200 | 277 ms | 15 ms | 18.1x |
| SELECT x IN (...) | 400 | 2,443 ms | 18 ms | 135.7x |
| GROUP BY CASE WHEN x IN (...) ... | 100 | 48 ms | 16 ms | 3.1x |
| GROUP BY CASE WHEN x IN (...) ... | 200 | 274 ms | 18 ms | 14.9x |
| GROUP BY CASE WHEN x IN (...) ... | 400 | 2,782 ms | 20 ms | 140.5x |
| OVER (PARTITION BY CASE WHEN x IN (...) ...) | 100 | 46 ms | 14 ms | 3.2x |
| OVER (PARTITION BY CASE WHEN x IN (...) ...) | 200 | 282 ms | 18 ms | 15.8x |
| OVER (PARTITION BY CASE WHEN x IN (...) ...) | 400 | 2,361 ms | 21 ms | 111.4x |
| HAVING SUM(CASE WHEN x IN (...) ...) | 100 | 46 ms | 15 ms | 3.2x |
| HAVING SUM(CASE WHEN x IN (...) ...) | 200 | 274 ms | 19 ms | 14.3x |
| HAVING SUM(CASE WHEN x IN (...) ...) | 400 | 2,455 ms | 22 ms | 109.1x |
#### Cubic positions with sealing, large N
| Query | 10,000 | 100,000 |
|---|---|---|
| JOIN ... ON a.k = b.k AND b.x IN (...) | 106 ms | 852 ms |
| LEFT JOIN ... ON ... AND a.x IN (...) | 114 ms | 901 ms |
| SUM(CASE WHEN x IN (...) ...) | 73 ms | 566 ms |
| COUNT(*) FILTER (WHERE x IN (...)) | 82 ms | 595 ms |
| SELECT x IN (...) | 82 ms | 591 ms |
| GROUP BY CASE WHEN x IN (...) ... | 87 ms | 723 ms |
| OVER (PARTITION BY CASE WHEN x IN (...) ...) | 79 ms | 598 ms |
| HAVING SUM(CASE WHEN x IN (...) ...) | 86 ms | 616 ms |
#### Stage size for IN plus a range on the same column (10k values)
| Query | Off: plan / stage bytes | On: plan / stage bytes |
|---|---|---|
| NOT IN (...) AND x > 0 | 103 ms / 98,047 | 106 ms / 98,047 |
| IN (...) OR x > c | 85 ms / 98,046 | 93 ms / 98,046 |
#### Phase split, prod shape at 100k values (ms)
| Sealing | parse | validate | sql2rel | optimize | plan | serialize | total |
|---|---|---|---|---|---|---|---|
| Off | 147 | 66 | 606 | 2,514 | 11 | 19 | 3,363 |
| On | 139 | 63 | 552 | 15 | 9 | 18 | 795 |
</details>
## Tests
- `SearchSealerTest` (363 cases): seal and unseal round trips for 8 types × 4 Sarg shapes × 3 null modes. Type and `Strong` answers equal to `SEARCH`. Threshold, operator identity and literal operands.
- `SealedInListPlanningTest` (274 cases): 60 query shapes × V1 and V2 give the same EXPLAIN, implementation plan, serialized stages and worker segments with and without sealing, and EXPLAIN never shows a sealed call. 11 more shapes on nullable columns (with and without null handling, V1 and V2) cover null checks, `NOT IN` with NULL and outer joins. A guard rule in every planner phase fails if any rule sees a `SEARCH` or a comparison list with 20 or more values, and a negative test shows that the guard fires with sealing off. Cubic positions plan 5,000 values within a time limit.
- `LargeInLists.json` (43 H2-checked queries): WHERE, NOT IN, IN plus a range, CASE, FILTER, SELECT list, GROUP BY, HAVING, JOIN ON, LEFT JOIN, CTE, UNION ALL, window, NULL in the list, nullable columns, and mixed Sargs in intermediate stages.
- `RexExpressionUtilsTest`: mixed-Sarg conversion (IN and NOT_IN forms, bounded complements, both null modes, small lists, no points, BIG_DECIMAL). `QueryOptionsUtilsTest`: option parsing.
- Robustness run with every IN list sealed (`DEFAULT_SEALED_IN_LIST_THRESHOLD = 1`): 2,593 planner tests and 3,922 H2-checked runtime queries pass, with 0 failures. The same suites pass at the default threshold.
- An adversarial corpus of 458 H2-checked queries (not committed) gives identical results at T = 0, 1 and 20 for both planners, with and without null handling.
## Follow-ups (not in this PR)
- Many small IN lists, or a long `x = 1 OR x = 2 ...` chain, OR-ed inside CASE or JOIN ON still take the cubic SqlToRel path, because no single list reaches T. The same mechanism can cover this by marking the whole OR tree.
- Runtime: `FilterOperand.In` scans the list for every row, and it compares BIG_DECIMAL values with `equals`, which gives wrong results in intermediate stages.
- Planning is not cancellable: Pinot supplies no Calcite `CancelFlag`, so a timed-out plan keeps its planner thread.
- Upstream Calcite: the `RexSimplify` patch for CALCITE-7302, and bug reports for the `expand=true` issues above.
## References
- Pinot: #10168, #13605, #13614, #13617, #14615, #15027, #18554, #18720, #17481
- Calcite: CALCITE-3178, CALCITE-5036, CALCITE-6467, CALCITE-6599, CALCITE-7226, CALCITE-7232, CALCITE-7302
- Prior art: Druid rewrites IN lists of more than 100 literals before SqlToRel. Hive uses an opaque `HiveIn` above 16 values. Spark uses `InSet` above 10 values.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Seal large IN lists from Calcite during multi-stage planning [pinot]
Posted by "gortiz (via GitHub)" <gi...@apache.org>.
gortiz commented on code in PR #19674:
URL: https://github.com/apache/pinot/pull/19674#discussion_r4124073384
##########
pinot-query-planner/src/main/java/org/apache/pinot/query/planner/logical/RexExpressionUtils.java:
##########
@@ -371,11 +378,89 @@ private static RexExpression handleSearch(RexCall rexCall) {
if (leftOperand instanceof RexLiteral) {
return evaluateLiteralOrRanges((RexLiteral) leftOperand, sarg.rangeSet.asRanges(), sarg.nullAs);
}
- RexExpression orExpr = convertRangesToOr(dataType, leftOperand, sarg.rangeSet.asRanges());
- return addNullCheckIfRequired(leftOperand, sarg.nullAs, orExpr);
+ RexExpression rangesExpr = convertRanges(dataType, leftOperand, sarg.rangeSet);
+ return addNullCheckIfRequired(leftOperand, sarg.nullAs, rangesExpr);
+ }
+ }
+
+ /// The smallest number of single values in a range set with other ranges that ships as one `IN` or `NOT_IN`.
+ /// Below it, one range per value costs the servers little.
+ static final int MIN_POINTS_FOR_IN = 20;
+
+ /// Converts a range set that is neither only points nor only the complement of points.
+ ///
+ /// Each range becomes comparisons, except when the range set holds many single points. A large OR of
+ /// `x >= v AND x <= v` terms costs the servers one scan per value, so:
+ /// - When the ranges hold at least [#MIN_POINTS_FOR_IN] points, for example `x IN (<list>) OR x > 10`, the points
+ /// become one `IN` and only the other ranges become comparisons: `OR(IN(x, <list>), x > 10)`.
+ /// - When the complement holds at least [#MIN_POINTS_FOR_IN] points, for example `x NOT IN (<list>) AND x > 0`, the
+ /// result is `AND(NOT_IN(x, <list>), x > 0)`.
+ /// - When both forms apply, the one with fewer values is used.
+ ///
+ /// `BIG_DECIMAL` ranges always become comparisons: an intermediate stage matches `IN` values with `equals`, which
+ /// depends on the scale of the value.
+ private static RexExpression convertRanges(ColumnDataType dataType, RexNode leftOperand, RangeSet rangeSet) {
Review Comment:
`convertRanges` runs for every mixed point + range Sarg with 20 or more points, whether the list is sealed or not. It does not read `sealedInListThreshold`. The description says that `0` gives master behavior, but with `sealedInListThreshold=0` the servers still get `IN`/`NOT_IN` plus ranges here, not the OR of ranges that master sends. This changes what the servers execute, and there is no way to turn it off.
Also, `SealedInListPlanningTest` compares the sealed plan with the `threshold=0` plan, and both use this new path. So that test does not compare this change with master; only the H2 tests cover it.
Could we gate this with the same option (or a separate one), or at least update the description so that it does not call `0` the master behavior?
##########
pinot-query-planner/src/main/java/org/apache/pinot/calcite/rex/SearchSealer.java:
##########
@@ -0,0 +1,386 @@
+/**
+ * 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.calcite.rex;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import org.apache.calcite.plan.RelOptPredicateList;
+import org.apache.calcite.rel.RelHomogeneousShuttle;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Filter;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexCall;
+import org.apache.calcite.rex.RexLiteral;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexShuttle;
+import org.apache.calcite.rex.RexSimplify;
+import org.apache.calcite.rex.RexSubQuery;
+import org.apache.calcite.rex.RexVisitorImpl;
+import org.apache.calcite.sql.SqlBasicCall;
+import org.apache.calcite.sql.SqlCall;
+import org.apache.calcite.sql.SqlKind;
+import org.apache.calcite.sql.SqlNode;
+import org.apache.calcite.sql.SqlNodeList;
+import org.apache.calcite.sql.fun.SqlInOperator;
+import org.apache.calcite.sql.fun.SqlStdOperatorTable;
+import org.apache.calcite.sql.util.SqlBasicVisitor;
+import org.apache.calcite.util.Sarg;
+import org.apache.pinot.calcite.rel.rules.PinotRuleUtils;
+import org.apache.pinot.calcite.sql.fun.PinotInListOperator;
+
+
+/// Hides the large IN lists of one query from Calcite while the query is optimized.
+///
+/// Calcite keeps an IN list as `SEARCH($x, Sarg[...])`. Many rules and metadata handlers rebuild the Sarg's range set
+/// each time they touch it (`O(N log N)`), and each Calcite release and each new planner rule adds such touches. This
+/// class replaces every `SEARCH` whose Sarg has at least [#getThreshold()] ranges with a call to a
+/// [PinotSealedSearchOperator], which Calcite cannot look into, and turns it back into the same `SEARCH` once
+/// optimization is done. Everything after optimization (EXPLAIN, plan node conversion, broker pruning, the servers)
+/// sees the same `SEARCH` calls as without sealing.
+///
+/// Planning a query uses one instance, in this order:
+/// 1. [#markInLists] after validation. Large `IN` value lists skip `SqlToRelConverter`'s expansion into `OR`, and
+/// `PinotConvertletTable` converts each marked call into one `SEARCH`. Closing the [MarkedInLists] restores the SQL
+/// operators after the conversion.
+/// 2. [#seal(RelNode)] after `SqlToRelConverter`. It first simplifies each filter and join condition that holds a
+/// large Sarg, like `RelBuilder#filter` does, so that the other predicates on the same operand fold into the Sarg
+/// as they do without sealing (for example `x IS NOT NULL`, a range, or a second list). Then it seals the large
+/// `SEARCH` calls, including the ones that Calcite built from a user-written `x = 1 OR x = 2 OR ...`.
+/// 3. [#unseal(RelNode)] after the last optimizer program.
+///
+/// Sealed Sargs lose Calcite's value-level reasoning across plan nodes during optimization. For example, a filter
+/// that a rule pushes onto another filter with a sealed list on the same column is not merged with it. Filter
+/// push-down, transitive predicates across joins, outer join simplification and all rules that treat the predicate
+/// as a whole work as before.
+///
+/// Not thread safe: a query is planned by a single thread.
+public final class SearchSealer {
+ private final int _threshold;
+ /// One operator per distinct Sarg literal (value and type), so that equal lists stay equal (for example in both
+ /// branches of a common table expression).
+ private final Map<RexLiteral, PinotSealedSearchOperator> _operators = new HashMap<>();
+
+ /// @param threshold the smallest number of Sarg ranges (IN list values) to seal; 0 or less disables sealing
+ public SearchSealer(int threshold) {
+ _threshold = threshold;
+ }
+
+ /// Returns the smallest number of Sarg ranges (IN list values) that this instance seals.
+ public int getThreshold() {
+ return _threshold;
+ }
+
+ /// Returns whether this instance seals anything.
+ public boolean isEnabled() {
+ return _threshold > 0;
+ }
+
+ /// Returns whether a Sarg is large enough to seal.
+ boolean shouldSeal(Sarg<?> sarg) {
+ // A Sarg that is all or none has at most one range and is never large. Calcite has special cases for these
+ // (for example RexCall#isAlwaysTrue), so they always stay visible.
+ return _threshold > 0 && !sarg.isAll() && !sarg.isNone() && sarg.rangeSet.asRanges().size() >= _threshold;
+ }
+
+ /// Returns a sealed call for a `SEARCH` call whose Sarg is large enough, or the call itself otherwise.
+ RexNode seal(RexBuilder rexBuilder, RexCall search) {
+ RexLiteral sargLiteral = (RexLiteral) search.getOperands().get(1);
+ Sarg<?> sarg = sargLiteral.getValueAs(Sarg.class);
+ if (sarg == null || !shouldSeal(sarg)) {
+ return search;
+ }
+ PinotSealedSearchOperator operator =
+ _operators.computeIfAbsent(sargLiteral, literal -> new PinotSealedSearchOperator(_operators.size(), literal));
+ return rexBuilder.makeCall(search.getType(), operator, List.of(search.getOperands().get(0)));
+ }
+
+ // --------------------------------------------------------------------------
+ // SQL level
+ // --------------------------------------------------------------------------
+
+ /// Sets [PinotInListOperator] on every `IN` and `NOT IN` call in the validated tree whose value list has at least
+ /// [#getThreshold()] values. Close the result after `SqlToRelConverter` is done, to restore the original operators:
+ ///
+ /// ```
+ /// try (SearchSealer.MarkedInLists ignored = searchSealer.markInLists(validated)) {
+ /// relRoot = converter.convertQuery(validated, false, true);
+ /// }
+ /// ```
+ ///
+ /// Lists on a row (`(a, b) IN (...)`) and lists that contain a sub-query keep the standard conversion.
+ public MarkedInLists markInLists(SqlNode validated) {
+ List<SqlBasicCall> marked = new ArrayList<>();
+ if (!isEnabled()) {
+ return new MarkedInLists(marked);
+ }
+ try {
+ validated.accept(new SqlBasicVisitor<Void>() {
+ @Override
+ public Void visit(SqlCall call) {
+ if (call instanceof SqlBasicCall && isLargeInList(call)) {
+ ((SqlBasicCall) call).setOperator(PinotInListOperator.of(call.getKind()));
+ marked.add((SqlBasicCall) call);
+ // The values have no sub-queries (checked above), so only the left operand needs a visit.
+ call.operand(0).accept(this);
+ return null;
+ }
+ return super.visit(call);
+ }
+ });
+ } catch (Throwable t) {
+ new MarkedInLists(marked).close();
+ throw t;
+ }
+ return new MarkedInLists(marked);
+ }
+
+ /// The `IN` and `NOT IN` calls that [#markInLists] marked. [#close()] restores their original operators.
+ public static final class MarkedInLists implements AutoCloseable {
+ private final List<SqlBasicCall> _calls;
+
+ private MarkedInLists(List<SqlBasicCall> calls) {
+ _calls = calls;
+ }
+
+ @Override
+ public void close() {
+ for (SqlBasicCall call : _calls) {
+ call.setOperator(((PinotInListOperator) call.getOperator()).getOriginal());
+ }
+ }
+ }
+
+ private boolean isLargeInList(SqlCall call) {
+ SqlKind kind = call.getKind();
+ if ((kind != SqlKind.IN && kind != SqlKind.NOT_IN) || !(call.getOperator() instanceof SqlInOperator)
+ || call.operandCount() != 2) {
+ return false;
+ }
+ if (!(call.operand(1) instanceof SqlNodeList) || call.operand(0).getKind() == SqlKind.ROW) {
+ return false;
+ }
+ SqlNodeList values = call.operand(1);
+ return values.size() >= _threshold && !containsQueryOrRow(values);
+ }
+
+ private static boolean containsQueryOrRow(SqlNodeList values) {
+ SqlBasicVisitor<Boolean> finder = new SqlBasicVisitor<>() {
+ @Override
+ public Boolean visit(SqlCall call) {
+ SqlKind kind = call.getKind();
+ if (kind == SqlKind.ROW || kind == SqlKind.SCALAR_QUERY || kind.belongsTo(SqlKind.QUERY)) {
+ return true;
+ }
+ for (SqlNode operand : call.getOperandList()) {
+ if (operand != null && Boolean.TRUE.equals(operand.accept(this))) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ @Override
+ public Boolean visit(SqlNodeList nodeList) {
+ for (SqlNode node : nodeList) {
+ if (node != null && Boolean.TRUE.equals(node.accept(this))) {
+ return true;
+ }
+ }
+ return false;
+ }
+ };
+ return Boolean.TRUE.equals(values.accept(finder));
+ }
+
+ // --------------------------------------------------------------------------
+ // Relational level
+ // --------------------------------------------------------------------------
+
+ /// Seals every large `SEARCH` in a plan that `SqlToRelConverter` produced.
+ ///
+ /// A filter or join condition that holds a large Sarg, or a large `AND` / `OR` of comparisons, is simplified first,
+ /// the same way `RelBuilder#filter` does it. Field trimming usually did this already when it rebuilt the filter,
+ /// but not when the filter keeps all its fields. This folds `x = 1 OR x = 2 OR ...` into a Sarg, and it folds the
+ /// other predicates on the same operand into the Sarg (for example `x IS NOT NULL` into `NULL AS FALSE`), exactly
+ /// as the optimizer would do without sealing. Once sealed, such a predicate cannot merge anymore, and Calcite could
+ /// drop an `x IS NOT NULL` next to it as redundant.
+ public RelNode seal(RelNode rel) {
+ return isEnabled() ? rel.accept(new RelSealer()) : rel;
+ }
+
+ /// Restores the `SEARCH` calls that this instance sealed.
+ public RelNode unseal(RelNode rel) {
+ return _operators.isEmpty() ? rel : rel.accept(new RelUnsealer());
+ }
+
+ /// Returns the `SEARCH` call that a sealed call stands for.
+ static RexNode unsealCall(RexBuilder rexBuilder, RexCall sealed) {
+ PinotSealedSearchOperator operator = (PinotSealedSearchOperator) sealed.getOperator();
+ return rexBuilder.makeCall(sealed.getType(), SqlStdOperatorTable.SEARCH,
+ List.of(sealed.getOperands().get(0), operator.getSargLiteral()));
+ }
+
+ private final class RelSealer extends RelHomogeneousShuttle {
+ @Override
+ public RelNode visit(RelNode other) {
+ RelNode rel = foldLargeLists(super.visit(other));
+ return rel.accept(new RexSealer(rel.getCluster().getRexBuilder()));
+ }
+
+ private RelNode foldLargeLists(RelNode rel) {
+ if (rel instanceof Filter) {
+ Filter filter = (Filter) rel;
+ if (hasLargeList(filter.getCondition())) {
+ return filter.copy(filter.getTraitSet(), filter.getInput(),
+ simplifyCondition(filter.getCluster().getRexBuilder(), filter.getCondition()));
+ }
+ } else if (rel instanceof Join) {
+ Join join = (Join) rel;
+ if (join.getJoinType() != JoinRelType.LEFT_MARK && hasLargeList(join.getCondition())) {
+ return join.copy(join.getTraitSet(), simplifyCondition(join.getCluster().getRexBuilder(),
+ join.getCondition()), join.getLeft(), join.getRight(), join.getJoinType(), join.isSemiJoinDone());
+ }
+ }
+ return rel;
+ }
+ }
+
+ /// Returns whether a condition has a `SEARCH` that is large enough to seal, or an AND or OR with so many comparisons
+ /// to literals that Calcite could fold them into such a Sarg. An AND of `x <> v` comparisons folds into `n + 1`
+ /// ranges.
+ private boolean hasLargeList(RexNode condition) {
+ int minComparisons = Math.max(_threshold - 1, 2);
Review Comment:
`hasLargeList` counts literal comparisons on any operand. So a filter like `WHERE a = 1 AND b = 2 AND ...` with 19 or more conjuncts on different columns is simplified again at seal time, even when the query has no IN list at all. It is probably harmless, because `RelBuilder` already simplified it and `RexSimplify` should give the same result a second time. But it makes the feature affect queries it is not meant for, and the same-plan tests only cover IN shapes.
Would it make sense to count the comparisons per operand (only those can fold into one Sarg)? Or to add a same-plan case with a wide conjunction on many columns?
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Seal large IN lists from Calcite during multi-stage planning [pinot]
Posted by "xiangfu0 (via GitHub)" <gi...@apache.org>.
xiangfu0 commented on PR #19674:
URL: https://github.com/apache/pinot/pull/19674#issuecomment-5914062524
Documentation follow-up: https://github.com/pinot-contrib/pinot-docs/pull/1078 (merged). This documents the MSE sealedInListThreshold query option and broker default.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Seal large IN lists from Calcite during multi-stage planning [pinot]
Posted by "yashmayya (via GitHub)" <gi...@apache.org>.
yashmayya merged PR #19674:
URL: https://github.com/apache/pinot/pull/19674
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Seal large IN lists from Calcite during multi-stage planning [pinot]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #19674:
URL: https://github.com/apache/pinot/pull/19674#issuecomment-5840399243
## [Codecov](https://app.codecov.io/gh/apache/pinot/pull/19674?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:white_check_mark: All modified and coverable lines are covered by tests.
:white_check_mark: Project coverage is 100.00%. Comparing base ([`8a6e620`](https://app.codecov.io/gh/apache/pinot/commit/8a6e620139c4914313a21c17c3da96eeb529851b?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`c77e378`](https://app.codecov.io/gh/apache/pinot/commit/c77e378db3e2584200a18b6efc253585b274826d?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 3 commits behind head on master.
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## master #19674 +/- ##
==============================================
+ Coverage 68.03% 100.00% +31.96%
+ Complexity 1450 6 -1444
==============================================
Files 3511 3 -3508
Lines 227541 6 -227535
Branches 36004 0 -36004
==============================================
- Hits 154812 6 -154806
+ Misses 60585 0 -60585
+ Partials 12144 0 -12144
```
| [Flag](https://app.codecov.io/gh/apache/pinot/pull/19674/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Coverage Δ | |
|---|---|---|
| [integration](https://app.codecov.io/gh/apache/pinot/pull/19674/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `100.00% <ø> (ø)` | |
| [integration1](https://app.codecov.io/gh/apache/pinot/pull/19674/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `100.00% <ø> (ø)` | |
| [integration2](https://app.codecov.io/gh/apache/pinot/pull/19674/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [java-25](https://app.codecov.io/gh/apache/pinot/pull/19674/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `100.00% <ø> (+31.96%)` | :arrow_up: |
| [lane-a](https://app.codecov.io/gh/apache/pinot/pull/19674/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `100.00% <ø> (ø)` | |
| [lane-b](https://app.codecov.io/gh/apache/pinot/pull/19674/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `0.00% <ø> (ø)` | |
| [temurin](https://app.codecov.io/gh/apache/pinot/pull/19674/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `100.00% <ø> (+31.96%)` | :arrow_up: |
| [unittests](https://app.codecov.io/gh/apache/pinot/pull/19674/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [unittests1](https://app.codecov.io/gh/apache/pinot/pull/19674/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [unittests2](https://app.codecov.io/gh/apache/pinot/pull/19674/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#carryforward-flags-in-the-pull-request-comment) to find out more.
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/pinot/pull/19674?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Seal large IN lists from Calcite during multi-stage planning [pinot]
Posted by "yashmayya (via GitHub)" <gi...@apache.org>.
yashmayya commented on code in PR #19674:
URL: https://github.com/apache/pinot/pull/19674#discussion_r4139186714
##########
pinot-spi/src/main/java/org/apache/pinot/spi/utils/CommonConstants.java:
##########
@@ -798,6 +798,27 @@ public static class Broker {
// TODO: Change this default to something very high, as this _optimnization_ is usually not beneficial.
public static final int DEFAULT_SORT_EXCHANGE_COPY_THRESHOLD = 10_000;
+ /// Config for the smallest IN list that the multi-stage planner hides from Calcite's optimizer.
+ ///
+ /// Calcite keeps an IN list as one `SEARCH` call over a sorted range set. Many planner rules and metadata
+ /// handlers rebuild that range set every time they touch the predicate, so planning time grows with the list size
+ /// times the number of touches. IN lists (and `OR` chains of equalities in a filter) with at least this many values
+ /// are sealed into an opaque predicate during optimization and restored afterwards.
+ ///
+ /// Predicates in the same filter or join condition still fold into the list first, as without sealing. Sealed lists
+ /// lose Calcite's value-level reasoning across plan nodes: a predicate that a rule moves next to a sealed list on
+ /// the same column is not merged into it. For example, an `x IS NOT NULL` in another clause than a sealed list on
+ /// `x` is dropped as redundant when the two meet, which is correct in SQL. With null handling disabled, the servers
+ /// then do not filter the rows where `x` is null, as today for `x < 5 AND x IS NOT NULL`.
+ ///
+ /// A value of 0 or less disables sealing. Planning outside the broker's multi-stage request handler (for example
+ /// for the controller `/sql` endpoint) does not read this broker config and uses the default. The query option
+ /// works everywhere.
+ public static final String CONFIG_OF_SEALED_IN_LIST_THRESHOLD = "pinot.broker.multistage.sealed.in.list.threshold";
+ /// Same as the default of Calcite's `SqlToRelConverter.Config#getInSubQueryThreshold()`: the size from which
+ /// Calcite itself stops treating an IN list as a scalar predicate.
+ public static final int DEFAULT_SEALED_IN_LIST_THRESHOLD = 20;
Review Comment:
Thanks for checking. I tested this with the broker's planner setup, and the check is kept:
- With null handling off, the broker plans `IS NULL` and `IS NOT NULL` with Pinot's own operators (`PinotOperatorTable`). Calcite cannot see into them, so it never merges or drops them.
- With null handling on, Calcite can drop the check next to a sealed list, as it does next to `x < 5`. This is correct, because the servers then apply SQL null semantics.
Our planner tests always turn null handling on in the planner, so the old test comment and Javadoc were wrong. I fixed them and added the regression in bc4c1d6 (`testNullChecksWithoutNullHandling`). Checks in another clause, an outer query, a CTE and on a joined column all stay, and the plans match `0`.
##########
pinot-query-planner/src/main/java/org/apache/pinot/query/planner/logical/RexExpressionUtils.java:
##########
@@ -371,11 +378,89 @@ private static RexExpression handleSearch(RexCall rexCall) {
if (leftOperand instanceof RexLiteral) {
return evaluateLiteralOrRanges((RexLiteral) leftOperand, sarg.rangeSet.asRanges(), sarg.nullAs);
}
- RexExpression orExpr = convertRangesToOr(dataType, leftOperand, sarg.rangeSet.asRanges());
- return addNullCheckIfRequired(leftOperand, sarg.nullAs, orExpr);
+ RexExpression rangesExpr = convertRanges(dataType, leftOperand, sarg.rangeSet);
+ return addNullCheckIfRequired(leftOperand, sarg.nullAs, rangesExpr);
+ }
+ }
+
+ /// The smallest number of single values in a range set with other ranges that ships as one `IN` or `NOT_IN`.
+ /// Below it, one range per value costs the servers little.
+ static final int MIN_POINTS_FOR_IN = 20;
+
+ /// Converts a range set that is neither only points nor only the complement of points.
+ ///
+ /// Each range becomes comparisons, except when the range set holds many single points. A large OR of
+ /// `x >= v AND x <= v` terms costs the servers one scan per value, so:
+ /// - When the ranges hold at least [#MIN_POINTS_FOR_IN] points, for example `x IN (<list>) OR x > 10`, the points
+ /// become one `IN` and only the other ranges become comparisons: `OR(IN(x, <list>), x > 10)`.
+ /// - When the complement holds at least [#MIN_POINTS_FOR_IN] points, for example `x NOT IN (<list>) AND x > 0`, the
+ /// result is `AND(NOT_IN(x, <list>), x > 0)`.
+ /// - When both forms apply, the one with fewer values is used.
+ ///
+ /// `BIG_DECIMAL` ranges always become comparisons: an intermediate stage matches `IN` values with `equals`, which
+ /// depends on the scale of the value.
+ private static RexExpression convertRanges(ColumnDataType dataType, RexNode leftOperand, RangeSet rangeSet) {
Review Comment:
Good point. I kept the split in `handleSearch` and fixed the description: `0` only turns sealing off, and the split applies at any threshold. The split does not depend on sealing (it helps any mixed Sarg with 20 or more points), so I kept it separate. `RexExpressionUtilsTest` and the H2 checks in `LargeInLists.json` cover it.
##########
pinot-query-planner/src/main/java/org/apache/pinot/calcite/rex/SearchSealer.java:
##########
@@ -0,0 +1,386 @@
+/**
+ * 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.calcite.rex;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import org.apache.calcite.plan.RelOptPredicateList;
+import org.apache.calcite.rel.RelHomogeneousShuttle;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Filter;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexCall;
+import org.apache.calcite.rex.RexLiteral;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexShuttle;
+import org.apache.calcite.rex.RexSimplify;
+import org.apache.calcite.rex.RexSubQuery;
+import org.apache.calcite.rex.RexVisitorImpl;
+import org.apache.calcite.sql.SqlBasicCall;
+import org.apache.calcite.sql.SqlCall;
+import org.apache.calcite.sql.SqlKind;
+import org.apache.calcite.sql.SqlNode;
+import org.apache.calcite.sql.SqlNodeList;
+import org.apache.calcite.sql.fun.SqlInOperator;
+import org.apache.calcite.sql.fun.SqlStdOperatorTable;
+import org.apache.calcite.sql.util.SqlBasicVisitor;
+import org.apache.calcite.util.Sarg;
+import org.apache.pinot.calcite.rel.rules.PinotRuleUtils;
+import org.apache.pinot.calcite.sql.fun.PinotInListOperator;
+
+
+/// Hides the large IN lists of one query from Calcite while the query is optimized.
+///
+/// Calcite keeps an IN list as `SEARCH($x, Sarg[...])`. Many rules and metadata handlers rebuild the Sarg's range set
+/// each time they touch it (`O(N log N)`), and each Calcite release and each new planner rule adds such touches. This
+/// class replaces every `SEARCH` whose Sarg has at least [#getThreshold()] ranges with a call to a
+/// [PinotSealedSearchOperator], which Calcite cannot look into, and turns it back into the same `SEARCH` once
+/// optimization is done. Everything after optimization (EXPLAIN, plan node conversion, broker pruning, the servers)
+/// sees the same `SEARCH` calls as without sealing.
+///
+/// Planning a query uses one instance, in this order:
+/// 1. [#markInLists] after validation. Large `IN` value lists skip `SqlToRelConverter`'s expansion into `OR`, and
+/// `PinotConvertletTable` converts each marked call into one `SEARCH`. Closing the [MarkedInLists] restores the SQL
+/// operators after the conversion.
+/// 2. [#seal(RelNode)] after `SqlToRelConverter`. It first simplifies each filter and join condition that holds a
+/// large Sarg, like `RelBuilder#filter` does, so that the other predicates on the same operand fold into the Sarg
+/// as they do without sealing (for example `x IS NOT NULL`, a range, or a second list). Then it seals the large
+/// `SEARCH` calls, including the ones that Calcite built from a user-written `x = 1 OR x = 2 OR ...`.
+/// 3. [#unseal(RelNode)] after the last optimizer program.
+///
+/// Sealed Sargs lose Calcite's value-level reasoning across plan nodes during optimization. For example, a filter
+/// that a rule pushes onto another filter with a sealed list on the same column is not merged with it. Filter
+/// push-down, transitive predicates across joins, outer join simplification and all rules that treat the predicate
+/// as a whole work as before.
+///
+/// Not thread safe: a query is planned by a single thread.
+public final class SearchSealer {
+ private final int _threshold;
+ /// One operator per distinct Sarg literal (value and type), so that equal lists stay equal (for example in both
+ /// branches of a common table expression).
+ private final Map<RexLiteral, PinotSealedSearchOperator> _operators = new HashMap<>();
+
+ /// @param threshold the smallest number of Sarg ranges (IN list values) to seal; 0 or less disables sealing
+ public SearchSealer(int threshold) {
+ _threshold = threshold;
+ }
+
+ /// Returns the smallest number of Sarg ranges (IN list values) that this instance seals.
+ public int getThreshold() {
+ return _threshold;
+ }
+
+ /// Returns whether this instance seals anything.
+ public boolean isEnabled() {
+ return _threshold > 0;
+ }
+
+ /// Returns whether a Sarg is large enough to seal.
+ boolean shouldSeal(Sarg<?> sarg) {
+ // A Sarg that is all or none has at most one range and is never large. Calcite has special cases for these
+ // (for example RexCall#isAlwaysTrue), so they always stay visible.
+ return _threshold > 0 && !sarg.isAll() && !sarg.isNone() && sarg.rangeSet.asRanges().size() >= _threshold;
+ }
+
+ /// Returns a sealed call for a `SEARCH` call whose Sarg is large enough, or the call itself otherwise.
+ RexNode seal(RexBuilder rexBuilder, RexCall search) {
+ RexLiteral sargLiteral = (RexLiteral) search.getOperands().get(1);
+ Sarg<?> sarg = sargLiteral.getValueAs(Sarg.class);
+ if (sarg == null || !shouldSeal(sarg)) {
+ return search;
+ }
+ PinotSealedSearchOperator operator =
+ _operators.computeIfAbsent(sargLiteral, literal -> new PinotSealedSearchOperator(_operators.size(), literal));
+ return rexBuilder.makeCall(search.getType(), operator, List.of(search.getOperands().get(0)));
+ }
+
+ // --------------------------------------------------------------------------
+ // SQL level
+ // --------------------------------------------------------------------------
+
+ /// Sets [PinotInListOperator] on every `IN` and `NOT IN` call in the validated tree whose value list has at least
+ /// [#getThreshold()] values. Close the result after `SqlToRelConverter` is done, to restore the original operators:
+ ///
+ /// ```
+ /// try (SearchSealer.MarkedInLists ignored = searchSealer.markInLists(validated)) {
+ /// relRoot = converter.convertQuery(validated, false, true);
+ /// }
+ /// ```
+ ///
+ /// Lists on a row (`(a, b) IN (...)`) and lists that contain a sub-query keep the standard conversion.
+ public MarkedInLists markInLists(SqlNode validated) {
+ List<SqlBasicCall> marked = new ArrayList<>();
+ if (!isEnabled()) {
+ return new MarkedInLists(marked);
+ }
+ try {
+ validated.accept(new SqlBasicVisitor<Void>() {
+ @Override
+ public Void visit(SqlCall call) {
+ if (call instanceof SqlBasicCall && isLargeInList(call)) {
+ ((SqlBasicCall) call).setOperator(PinotInListOperator.of(call.getKind()));
+ marked.add((SqlBasicCall) call);
+ // The values have no sub-queries (checked above), so only the left operand needs a visit.
+ call.operand(0).accept(this);
+ return null;
+ }
+ return super.visit(call);
+ }
+ });
+ } catch (Throwable t) {
+ new MarkedInLists(marked).close();
+ throw t;
+ }
+ return new MarkedInLists(marked);
+ }
+
+ /// The `IN` and `NOT IN` calls that [#markInLists] marked. [#close()] restores their original operators.
+ public static final class MarkedInLists implements AutoCloseable {
+ private final List<SqlBasicCall> _calls;
+
+ private MarkedInLists(List<SqlBasicCall> calls) {
+ _calls = calls;
+ }
+
+ @Override
+ public void close() {
+ for (SqlBasicCall call : _calls) {
+ call.setOperator(((PinotInListOperator) call.getOperator()).getOriginal());
+ }
+ }
+ }
+
+ private boolean isLargeInList(SqlCall call) {
+ SqlKind kind = call.getKind();
+ if ((kind != SqlKind.IN && kind != SqlKind.NOT_IN) || !(call.getOperator() instanceof SqlInOperator)
+ || call.operandCount() != 2) {
+ return false;
+ }
+ if (!(call.operand(1) instanceof SqlNodeList) || call.operand(0).getKind() == SqlKind.ROW) {
+ return false;
+ }
+ SqlNodeList values = call.operand(1);
+ return values.size() >= _threshold && !containsQueryOrRow(values);
+ }
+
+ private static boolean containsQueryOrRow(SqlNodeList values) {
+ SqlBasicVisitor<Boolean> finder = new SqlBasicVisitor<>() {
+ @Override
+ public Boolean visit(SqlCall call) {
+ SqlKind kind = call.getKind();
+ if (kind == SqlKind.ROW || kind == SqlKind.SCALAR_QUERY || kind.belongsTo(SqlKind.QUERY)) {
+ return true;
+ }
+ for (SqlNode operand : call.getOperandList()) {
+ if (operand != null && Boolean.TRUE.equals(operand.accept(this))) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ @Override
+ public Boolean visit(SqlNodeList nodeList) {
+ for (SqlNode node : nodeList) {
+ if (node != null && Boolean.TRUE.equals(node.accept(this))) {
+ return true;
+ }
+ }
+ return false;
+ }
+ };
+ return Boolean.TRUE.equals(values.accept(finder));
+ }
+
+ // --------------------------------------------------------------------------
+ // Relational level
+ // --------------------------------------------------------------------------
+
+ /// Seals every large `SEARCH` in a plan that `SqlToRelConverter` produced.
+ ///
+ /// A filter or join condition that holds a large Sarg, or a large `AND` / `OR` of comparisons, is simplified first,
+ /// the same way `RelBuilder#filter` does it. Field trimming usually did this already when it rebuilt the filter,
+ /// but not when the filter keeps all its fields. This folds `x = 1 OR x = 2 OR ...` into a Sarg, and it folds the
+ /// other predicates on the same operand into the Sarg (for example `x IS NOT NULL` into `NULL AS FALSE`), exactly
+ /// as the optimizer would do without sealing. Once sealed, such a predicate cannot merge anymore, and Calcite could
+ /// drop an `x IS NOT NULL` next to it as redundant.
+ public RelNode seal(RelNode rel) {
+ return isEnabled() ? rel.accept(new RelSealer()) : rel;
+ }
+
+ /// Restores the `SEARCH` calls that this instance sealed.
+ public RelNode unseal(RelNode rel) {
+ return _operators.isEmpty() ? rel : rel.accept(new RelUnsealer());
+ }
+
+ /// Returns the `SEARCH` call that a sealed call stands for.
+ static RexNode unsealCall(RexBuilder rexBuilder, RexCall sealed) {
+ PinotSealedSearchOperator operator = (PinotSealedSearchOperator) sealed.getOperator();
+ return rexBuilder.makeCall(sealed.getType(), SqlStdOperatorTable.SEARCH,
+ List.of(sealed.getOperands().get(0), operator.getSargLiteral()));
+ }
+
+ private final class RelSealer extends RelHomogeneousShuttle {
+ @Override
+ public RelNode visit(RelNode other) {
+ RelNode rel = foldLargeLists(super.visit(other));
+ return rel.accept(new RexSealer(rel.getCluster().getRexBuilder()));
+ }
+
+ private RelNode foldLargeLists(RelNode rel) {
+ if (rel instanceof Filter) {
+ Filter filter = (Filter) rel;
+ if (hasLargeList(filter.getCondition())) {
+ return filter.copy(filter.getTraitSet(), filter.getInput(),
+ simplifyCondition(filter.getCluster().getRexBuilder(), filter.getCondition()));
+ }
+ } else if (rel instanceof Join) {
+ Join join = (Join) rel;
+ if (join.getJoinType() != JoinRelType.LEFT_MARK && hasLargeList(join.getCondition())) {
+ return join.copy(join.getTraitSet(), simplifyCondition(join.getCluster().getRexBuilder(),
+ join.getCondition()), join.getLeft(), join.getRight(), join.getJoinType(), join.isSemiJoinDone());
+ }
+ }
+ return rel;
+ }
+ }
+
+ /// Returns whether a condition has a `SEARCH` that is large enough to seal, or an AND or OR with so many comparisons
+ /// to literals that Calcite could fold them into such a Sarg. An AND of `x <> v` comparisons folds into `n + 1`
+ /// ranges.
+ private boolean hasLargeList(RexNode condition) {
+ int minComparisons = Math.max(_threshold - 1, 2);
Review Comment:
Done in 8e5e57c: `hasLargeList` now counts comparisons per operand, and the test guard rule does the same. I added same-plan cases with wide AND and OR filters on many operands (no IN list), and a unit test that checks that such a filter is left as it is. 78702ef also adds `=` chains that reach this path end to end.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Seal large IN lists from Calcite during multi-stage planning [pinot]
Posted by "Jackie-Jiang (via GitHub)" <gi...@apache.org>.
Jackie-Jiang commented on code in PR #19674:
URL: https://github.com/apache/pinot/pull/19674#discussion_r4113661491
##########
pinot-spi/src/main/java/org/apache/pinot/spi/utils/CommonConstants.java:
##########
@@ -798,6 +798,27 @@ public static class Broker {
// TODO: Change this default to something very high, as this _optimnization_ is usually not beneficial.
public static final int DEFAULT_SORT_EXCHANGE_COPY_THRESHOLD = 10_000;
+ /// Config for the smallest IN list that the multi-stage planner hides from Calcite's optimizer.
+ ///
+ /// Calcite keeps an IN list as one `SEARCH` call over a sorted range set. Many planner rules and metadata
+ /// handlers rebuild that range set every time they touch the predicate, so planning time grows with the list size
+ /// times the number of touches. IN lists (and `OR` chains of equalities in a filter) with at least this many values
+ /// are sealed into an opaque predicate during optimization and restored afterwards.
+ ///
+ /// Predicates in the same filter or join condition still fold into the list first, as without sealing. Sealed lists
+ /// lose Calcite's value-level reasoning across plan nodes: a predicate that a rule moves next to a sealed list on
+ /// the same column is not merged into it. For example, an `x IS NOT NULL` in another clause than a sealed list on
+ /// `x` is dropped as redundant when the two meet, which is correct in SQL. With null handling disabled, the servers
+ /// then do not filter the rows where `x` is null, as today for `x < 5 AND x IS NOT NULL`.
+ ///
+ /// A value of 0 or less disables sealing. Planning outside the broker's multi-stage request handler (for example
+ /// for the controller `/sql` endpoint) does not read this broker config and uses the default. The query option
+ /// works everywhere.
+ public static final String CONFIG_OF_SEALED_IN_LIST_THRESHOLD = "pinot.broker.multistage.sealed.in.list.threshold";
+ /// Same as the default of Calcite's `SqlToRelConverter.Config#getInSubQueryThreshold()`: the size from which
+ /// Calcite itself stops treating an IN list as a scalar predicate.
+ public static final int DEFAULT_SEALED_IN_LIST_THRESHOLD = 20;
Review Comment:
Could we preserve the cross-clause null guard before enabling sealing by default? For a nullable `b.x`, a query with `b.x NOT IN (<20+ values>)` in `JOIN ON` and `b.x IS NOT NULL` in `WHERE` can lose the `IS NOT NULL` check after the sealed predicate meets it. With null handling disabled, the server may then admit rows where `b.x` is null. The new `SealedInListPlanningTest` comment at lines 201-208 acknowledges and excludes this case. Please add a cross-clause regression with null handling disabled and retain the guard (or leave sealing off by default until it is retained).
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org