[
https://issues.apache.org/jira/browse/CALCITE-7867?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Alessandro Solimando updated CALCITE-7867:
------------------------------------------
Description:
{{RexSimplify}} takes time cubic in the number of values to simplify two common
shapes:
* {{x = c1 OR x = c2 OR ... OR x = cN}} when {{x}} is NOT NULL;
* {{x <> c1 AND x <> c2 AND ... AND x <> cN}} when UNKNOWN is treated as FALSE
(a filter), whether or not {{x}} is nullable.
{{SqlToRelConverter}} produces these for {{x IN (c1, ..., cN)}} and {{x NOT IN
(c1, ..., cN)}} when the list is shorter than {{{}inSubQueryThreshold{}}}.
{{RelBuilder.project}} simplifies the first one right away, so a query like
{code:sql}
SELECT x IN (0, 1, ..., 1999) FROM t -- x INTEGER NOT NULL
{code}
spends minutes in {{{}SqlToRelConverter{}}}, before the planner runs. On
current main, with N = 2,000:
* {{simplifyPreservingType}} on the OR takes about 425 s (a few milliseconds
if {{x}} is nullable);
{{simplifyUnknownAsFalse}} on the AND takes about 475 s, and 512 s if {{x}} is
nullable.
*Cause*
{{simplifyOrTerms}} visits the terms in order. After term {{x = ci}} it adds
{{{}NOT(x = ci){}}}, i.e. {{{}x <> ci{}}}, to the predicates used to simplify
the following terms. {{Comparison.allowedInOr}} allows this only for a NOT NULL
operand, which is why a nullable {{x}} is fast. {{simplifyAndTerms}} does the
same with the terms of an AND, for any operand.
So term {{i}} is simplified by {{{}simplifyUsingPredicates{}}}, which calls
{{residue}} with {{i - 1}} predicates on the same operand. When those are {{{}x
<> cj{}}}, the residue range set gains one range per predicate. {{residue}}
applies each predicate with {{{}RangeSets.minus{}}}, which copies the whole
range set into a {{{}TreeRangeSet{}}}, compares it and copies it back into an
{{{}ImmutableRangeSet{}}}, so each step costs O(j) and one call costs O(i^2).
Over all terms that is O(N^3).
A profile of the query above shows almost all time in {{RexSimplify.residue}} →
{{RangeSets.minus}} → {{TreeMap.put}} / {{{}TreeMap.compare{}}}, called from
{{simplifyOrTerms}} via {{simplifyNot}} / {{simplifyComparison}} →
{{{}simplifyUsingPredicates{}}}.
*Proposed fix*
Let {{residue}} narrow a single mutable {{TreeRangeSet}} in place
({{{}remove{}}} for {{{}<>{}}}, {{removeAll(complement)}} for the other
comparisons, {{add(Range.all())}} where it currently resets to the full range
set) and return an immutable copy at the end. Each predicate then costs O(log
k), a {{residue}} call O(i log i), and the whole list O(N^2 log N). The result
of {{residue}} is unchanged, so no plan changes are expected.
With the fix, N = 2,000 takes about 1.4 s for the OR and 1.2 s for the AND.
*Note*
The O(N^2) that remains comes from {{simplifyOrTerms}} and {{simplifyAndTerms}}
themselves: they pass all preceding terms as predicates to each term. Folding
the comparisons of one operand into a {{SEARCH}} before those loops would
remove it, but {{simplifySearch}} does not use predicates the way
{{simplifyUsingPredicates}} does. For example, with predicate {{{}x > 5{}}},
{{x = 1 OR x = 2}} simplifies to {{false}} today but would stay {{{}SEARCH(x,
Sarg[1, 2]){}}}, and {{RexProgramTest.testSimplifyFilter}} and
{{testSimplifyOrTerms}} fail. That needs {{simplifySearch}} to take predicates
into account, which is a separate change.
was:
{{RexSimplify}} takes time cubic in the number of values to simplify two common
shapes:
* {{x = c1 OR x = c2 OR ... OR x = cN}} when {{x}} is NOT NULL;
* {{x <> c1 AND x <> c2 AND ... AND x <> cN}} when UNKNOWN is treated as FALSE
(a filter), whether or not {{x}} is nullable.
{{SqlToRelConverter}} produces these for {{x IN (c1, ..., cN)}} and {{x NOT IN
(c1, ..., cN)}} when the list is shorter than {{inSubQueryThreshold}}.
{{RelBuilder.project}} simplifies the first one right away, so a query like
{code:sql}
SELECT x IN (0, 1, ..., 1999) FROM t -- x INTEGER NOT NULL
{code}
spends minutes in {{SqlToRelConverter}}, before the planner runs. On current
main, with N = 2,000:
* {{simplifyPreservingType}} on the OR takes about 425 s (a few milliseconds if
{{x}} is nullable);
* {{simplifyUnknownAsFalse}} on the AND takes about 475 s, and 512 s if {{x}}
is nullable.
*Cause*
{{simplifyOrTerms}} visits the terms in order. After term {{x = ci}} it adds
{{NOT(x = ci)}}, i.e. {{x <> ci}}, to the predicates used to simplify the
following terms. {{Comparison.allowedInOr}} allows this only for a NOT NULL
operand, which is why a nullable {{x}} is fast. {{simplifyAndTerms}} does the
same with the terms of an AND, for any operand.
So term {{i}} is simplified by {{simplifyUsingPredicates}}, which calls
{{residue}} with {{i - 1}} predicates on the same operand. When those are {{x
<> cj}}, the residue range set gains one range per predicate. {{residue}}
applies each predicate with {{RangeSets.minus}}, which copies the whole range
set into a {{TreeRangeSet}}, compares it and copies it back into an
{{ImmutableRangeSet}}, so each step costs O(j) and one call costs O(i^2). Over
all terms that is O(N^3).
A profile of the query above shows almost all time in {{RexSimplify.residue}} →
{{RangeSets.minus}} → {{TreeMap.put}} / {{TreeMap.compare}}, called from
{{simplifyOrTerms}} via {{simplifyNot}} / {{simplifyComparison}} →
{{simplifyUsingPredicates}}.
*Proposed fix*
Let {{residue}} narrow a single mutable {{TreeRangeSet}} in place ({{remove}}
for {{<>}}, {{removeAll(complement)}} for the other comparisons,
{{add(Range.all())}} where it currently resets to the full range set) and
return an immutable copy at the end. Each predicate then costs O(log k), a
{{residue}} call O(i log i), and the whole list O(N^2 log N). The result of
{{residue}} is unchanged, so no plan changes are expected.
With the fix, N = 2,000 takes about 1.4 s for the OR and 1.2 s for the AND.
*Note*
The O(N^2) that remains comes from {{simplifyOrTerms}} and {{simplifyAndTerms}}
themselves: they pass all preceding terms as predicates to each term. Folding
the comparisons of one operand into a {{SEARCH}} before those loops would
remove it, but {{simplifySearch}} does not use predicates the way
{{simplifyUsingPredicates}} does. For example, with predicate {{x > 5}}, {{x =
1 OR x = 2}} simplifies to {{false}} today but would stay {{SEARCH(x, Sarg[1,
2])}}, and {{RexProgramTest.testSimplifyFilter}} and {{testSimplifyOrTerms}}
fail. That needs {{simplifySearch}} to take predicates into account, which is a
separate change.
> RexSimplify takes cubic time on long IN and NOT IN lists
> --------------------------------------------------------
>
> Key: CALCITE-7867
> URL: https://issues.apache.org/jira/browse/CALCITE-7867
> Project: Calcite
> Issue Type: Bug
> Components: core
> Affects Versions: 1.42.0
> Reporter: Iurii Gerzhedovich
> Assignee: Iurii Gerzhedovich
> Priority: Major
> Labels: pull-request-available
>
> {{RexSimplify}} takes time cubic in the number of values to simplify two
> common shapes:
> * {{x = c1 OR x = c2 OR ... OR x = cN}} when {{x}} is NOT NULL;
> * {{x <> c1 AND x <> c2 AND ... AND x <> cN}} when UNKNOWN is treated as
> FALSE (a filter), whether or not {{x}} is nullable.
> {{SqlToRelConverter}} produces these for {{x IN (c1, ..., cN)}} and {{x NOT
> IN (c1, ..., cN)}} when the list is shorter than {{{}inSubQueryThreshold{}}}.
> {{RelBuilder.project}} simplifies the first one right away, so a query like
> {code:sql}
> SELECT x IN (0, 1, ..., 1999) FROM t -- x INTEGER NOT NULL
> {code}
> spends minutes in {{{}SqlToRelConverter{}}}, before the planner runs. On
> current main, with N = 2,000:
> * {{simplifyPreservingType}} on the OR takes about 425 s (a few milliseconds
> if {{x}} is nullable);
> {{simplifyUnknownAsFalse}} on the AND takes about 475 s, and 512 s if {{x}}
> is nullable.
> *Cause*
> {{simplifyOrTerms}} visits the terms in order. After term {{x = ci}} it adds
> {{{}NOT(x = ci){}}}, i.e. {{{}x <> ci{}}}, to the predicates used to simplify
> the following terms. {{Comparison.allowedInOr}} allows this only for a NOT
> NULL operand, which is why a nullable {{x}} is fast. {{simplifyAndTerms}}
> does the same with the terms of an AND, for any operand.
> So term {{i}} is simplified by {{{}simplifyUsingPredicates{}}}, which calls
> {{residue}} with {{i - 1}} predicates on the same operand. When those are
> {{{}x <> cj{}}}, the residue range set gains one range per predicate.
> {{residue}} applies each predicate with {{{}RangeSets.minus{}}}, which copies
> the whole range set into a {{{}TreeRangeSet{}}}, compares it and copies it
> back into an {{{}ImmutableRangeSet{}}}, so each step costs O(j) and one call
> costs O(i^2). Over all terms that is O(N^3).
> A profile of the query above shows almost all time in {{RexSimplify.residue}}
> → {{RangeSets.minus}} → {{TreeMap.put}} / {{{}TreeMap.compare{}}}, called
> from {{simplifyOrTerms}} via {{simplifyNot}} / {{simplifyComparison}} →
> {{{}simplifyUsingPredicates{}}}.
> *Proposed fix*
> Let {{residue}} narrow a single mutable {{TreeRangeSet}} in place
> ({{{}remove{}}} for {{{}<>{}}}, {{removeAll(complement)}} for the other
> comparisons, {{add(Range.all())}} where it currently resets to the full range
> set) and return an immutable copy at the end. Each predicate then costs O(log
> k), a {{residue}} call O(i log i), and the whole list O(N^2 log N). The
> result of {{residue}} is unchanged, so no plan changes are expected.
> With the fix, N = 2,000 takes about 1.4 s for the OR and 1.2 s for the AND.
> *Note*
> The O(N^2) that remains comes from {{simplifyOrTerms}} and
> {{simplifyAndTerms}} themselves: they pass all preceding terms as predicates
> to each term. Folding the comparisons of one operand into a {{SEARCH}} before
> those loops would remove it, but {{simplifySearch}} does not use predicates
> the way {{simplifyUsingPredicates}} does. For example, with predicate {{{}x >
> 5{}}}, {{x = 1 OR x = 2}} simplifies to {{false}} today but would stay
> {{{}SEARCH(x, Sarg[1, 2]){}}}, and {{RexProgramTest.testSimplifyFilter}} and
> {{testSimplifyOrTerms}} fail. That needs {{simplifySearch}} to take
> predicates into account, which is a separate change.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
