[
https://issues.apache.org/jira/browse/CALCITE-7868?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Julian Hyde 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).
h3. 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.
h3. 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:
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.
h2. 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
>
> 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).
> h3. 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.
> h3. 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)
