[
https://issues.apache.org/jira/browse/CALCITE-7868?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Iurii Gerzhedovich updated CALCITE-7868:
----------------------------------------
Description:
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.
was:
## 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.
> 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
>
> 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.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
