[
https://issues.apache.org/jira/browse/CALCITE-7868?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Iurii Gerzhedovich updated CALCITE-7868:
----------------------------------------
Description:
## Changes Proposed
This PR is on top of #5343
([CALCITE-7867](https://issues.apache.org/jira/browse/CALCITE-7867)); only the
last commit is new.
`simplifyOrTerms` and `simplifyAndTerms` use every term as a predicate for the
following terms, which is quadratic in the number of terms. For long IN and NOT
IN lists that is one term per value, even though `simplifyOrs` / `simplifyAnd`
fold the same comparisons into a single `SEARCH` right after the loop.
1. `foldComparisonsIntoSargs` folds the comparisons of an operand with literals
into one `SEARCH` before those loops, using `SargCollector` as `simplifyOrs` /
`simplifyAnd` do afterwards. Comparisons on a literal operand are skipped:
`simplifySearch` expands a `SEARCH` on a literal back into an OR.
2. A `SEARCH` is now a predicate (`SearchPredicate`), so it narrows the other
terms of the same OR or AND as the comparisons it replaces did. `residue`
intersects with the Sarg of a `SEARCH` predicate on the same operand. A Sarg
that is TRUE for NULL is not used, because it does not imply that the operand
is not null.
3. `simplifySearch` narrows a `SEARCH` by the predicates on its operand, as
`simplifyUsingPredicates` does for a single comparison: `false` if no value is
left, `IS NOT NULL` / `true` if every allowed value satisfies it, a smaller
`SEARCH` if only points are left. Narrowing into ranges is not applied, as for
a single comparison.
Without 2 and 3, folding loses simplifications: with predicate `x > 5`, `x = 1
OR x = 2` would stay a `SEARCH` instead of becoming `false`, and `x > 1 AND x <
10 AND (x = 0 OR y)` would keep `x = 0`.
A `SEARCH` that was already in the input, including a predicate pulled up from
a `Filter` or `Values`, now narrows other expressions too. This changes two
expected plans, both for the better:
- `RelOptRulesTest.testReduceCaseWhenWithCast`: `$0` is 1 or 2 in the `Values`,
so `$0 < 2`, `$0 < 1`, `$0 < 3` become `$0 = 1`, `false`, `true`; the
conditions on `MOD` stay. The test now checks the plan after instead of an
unchanged plan.
- `planner.iq`: `t2.i > 0` over `VALUES (0), (1)` becomes `t2.i = 1`.
Timings, worst `RexUnknownAs` mode:
| Expression | N | main | CALCITE-7867 | this PR |
|---|---|---|---|---|
| `x = c1 OR ... OR x = cN`, `x <> c1 AND ... AND x <> cN` | 2,000 | 425-512 s
| 1.2-1.4 s | 7-49 ms |
| same | 4,000 | | ~5 s | 6-11 ms |
| same | 8,000 | | | 13-20 ms |
| `x = c OR (x = c' AND y) OR ...` | 2,000 | 46 s | 555 ms | 168 ms |
| `x <> c AND (x <> c' OR y) AND ...` | 2,000 | 197 s | 896 ms | 506 ms |
The mixed expressions in the last two rows stay quadratic: each term that is
not a comparison is still simplified with a predicate that has N values. On
small expressions there is no measurable difference from main (about 16 µs per
simplification on both, in a loop over 7 typical expressions).
Tests: `RexProgramTest.testSimplifySearchUsingPredicates`,
`testSimplifyOrOfEqualitiesUsingPredicates`,
`testSimplifyUsingSearchAsPredicate`. `:core:test`, `:babel:test`,
`:plus:test`, `:piglet:test`, `:server:test`, `:linq4j:test` and
`:testkit:test` pass, as do Error Prone and the Checker Framework (JDK 11) and
the `:core` rex tests and `RelOptRulesTest` with Guava 21.0.
was:
This is a follow-up to CALCITE-7867, which made simplification of long IN and
NOT IN lists O(N^2 log N) instead of O(N^3). With that fix, simplifying these
lists still takes about 1.2-1.4 s for N = 2,000 and about 5 s for N = 4,000:
* {{x = c1 OR ... OR x = cN}} when {{x}} is NOT NULL ({{x IN (...)}});
* {{x <> c1 AND ... AND x <> cN}} when UNKNOWN is treated as FALSE ({{x NOT IN
(...)}} in a filter).
*Cause*
{{simplifyOrTerms}} and {{simplifyAndTerms}} visit the terms in order and add
each term (or its inverse) to the predicates used for the following terms. For
term {{i}} they:
* copy the predicate list in {{RelOptPredicateList.union}};
* rebuild the constant map in {{RelOptPredicateList.of}};
* scan all {{i}} predicates in {{residue}}, calling {{Comparison.of}} on each.
All three are O(i), so the list costs O(N^2) even though {{simplifyOrs}} /
{{simplifyAnd}} fold the same terms into one {{SEARCH}} right after the loop.
*Proposal*
1. Fold the comparisons of an operand with literals into one {{SEARCH}} before
{{simplifyOrTerms}} / {{simplifyAndTerms}}, using {{SargCollector}} as
{{simplifyOrs}} / {{simplifyAnd}} already do afterwards. Then the loops see one
term instead of N. Comparisons whose operand is itself a literal have to be
skipped: {{simplifySearch}} expands a {{SEARCH}} on a literal back into an OR,
so folding it again recurses forever.
2. Let {{simplifySearch}} use the predicates the way
{{simplifyUsingPredicates}} does for a single comparison: intersect the Sarg's
range set with the range set that the predicates on the same operand allow,
then return {{false}} if the result is empty, or {{IS NOT NULL}} / {{true}} if
the Sarg covers everything the predicates allow.
Step 1 alone loses simplifications, because today each comparison is checked
against the predicates and a {{SEARCH}} is not. For example, with predicate {{x
> 5}}:
||Expression||Today||With step 1 only||
|{{x = 1 OR x = 2}}|{{false}}|{{SEARCH(x, Sarg[1, 2])}}|
|{{x = 1 OR x = 7}}|{{=(x, 7)}}|{{SEARCH(x, Sarg[1, 7])}}|
|{{x > 1 AND x < 10 AND x < 5}}|{{false}}|{{SEARCH(x, Sarg[(1..5)])}}|
{{RexProgramTest.testSimplifyFilter}} and {{testSimplifyOrTerms}} fail with
step 1 alone, so step 2 is required. Step 2 changes how every {{SEARCH}} is
simplified, not only folded ones, so some expected plans in other tests may
change.
In a local experiment with step 1 only, N = 4,000 took 10-95 ms for all the
shapes above, in every {{RexUnknownAs}} mode.
> RexSimplify takes quadratic time on long IN and NOT IN lists
> ------------------------------------------------------------
>
> Key: CALCITE-7868
> URL: https://issues.apache.org/jira/browse/CALCITE-7868
> Project: Calcite
> Issue Type: Improvement
> Components: core
> Reporter: Iurii Gerzhedovich
> Priority: Major
>
> ## Changes Proposed
> This PR is on top of #5343
> ([CALCITE-7867](https://issues.apache.org/jira/browse/CALCITE-7867)); only
> the last commit is new.
> `simplifyOrTerms` and `simplifyAndTerms` use every term as a predicate for
> the following terms, which is quadratic in the number of terms. For long IN
> and NOT IN lists that is one term per value, even though `simplifyOrs` /
> `simplifyAnd` fold the same comparisons into a single `SEARCH` right after
> the loop.
> 1. `foldComparisonsIntoSargs` folds the comparisons of an operand with
> literals into one `SEARCH` before those loops, using `SargCollector` as
> `simplifyOrs` / `simplifyAnd` do afterwards. Comparisons on a literal operand
> are skipped: `simplifySearch` expands a `SEARCH` on a literal back into an OR.
> 2. A `SEARCH` is now a predicate (`SearchPredicate`), so it narrows the other
> terms of the same OR or AND as the comparisons it replaces did. `residue`
> intersects with the Sarg of a `SEARCH` predicate on the same operand. A Sarg
> that is TRUE for NULL is not used, because it does not imply that the operand
> is not null.
> 3. `simplifySearch` narrows a `SEARCH` by the predicates on its operand, as
> `simplifyUsingPredicates` does for a single comparison: `false` if no value
> is left, `IS NOT NULL` / `true` if every allowed value satisfies it, a
> smaller `SEARCH` if only points are left. Narrowing into ranges is not
> applied, as for a single comparison.
> Without 2 and 3, folding loses simplifications: with predicate `x > 5`, `x =
> 1 OR x = 2` would stay a `SEARCH` instead of becoming `false`, and `x > 1 AND
> x < 10 AND (x = 0 OR y)` would keep `x = 0`.
> A `SEARCH` that was already in the input, including a predicate pulled up
> from a `Filter` or `Values`, now narrows other expressions too. This changes
> two expected plans, both for the better:
> - `RelOptRulesTest.testReduceCaseWhenWithCast`: `$0` is 1 or 2 in the
> `Values`, so `$0 < 2`, `$0 < 1`, `$0 < 3` become `$0 = 1`, `false`, `true`;
> the conditions on `MOD` stay. The test now checks the plan after instead of
> an unchanged plan.
> - `planner.iq`: `t2.i > 0` over `VALUES (0), (1)` becomes `t2.i = 1`.
> Timings, worst `RexUnknownAs` mode:
> | Expression | N | main | CALCITE-7867 | this PR |
> |---|---|---|---|---|
> | `x = c1 OR ... OR x = cN`, `x <> c1 AND ... AND x <> cN` | 2,000 | 425-512
> s | 1.2-1.4 s | 7-49 ms |
> | same | 4,000 | | ~5 s | 6-11 ms |
> | same | 8,000 | | | 13-20 ms |
> | `x = c OR (x = c' AND y) OR ...` | 2,000 | 46 s | 555 ms | 168 ms |
> | `x <> c AND (x <> c' OR y) AND ...` | 2,000 | 197 s | 896 ms | 506 ms |
> The mixed expressions in the last two rows stay quadratic: each term that is
> not a comparison is still simplified with a predicate that has N values. On
> small expressions there is no measurable difference from main (about 16 µs
> per simplification on both, in a loop over 7 typical expressions).
> Tests: `RexProgramTest.testSimplifySearchUsingPredicates`,
> `testSimplifyOrOfEqualitiesUsingPredicates`,
> `testSimplifyUsingSearchAsPredicate`. `:core:test`, `:babel:test`,
> `:plus:test`, `:piglet:test`, `:server:test`, `:linq4j:test` and
> `:testkit:test` pass, as do Error Prone and the Checker Framework (JDK 11)
> and the `:core` rex tests and `RelOptRulesTest` with Guava 21.0.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
