[
https://issues.apache.org/jira/browse/CALCITE-7868?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18129886#comment-18129886
]
Julian Hyde commented on CALCITE-7868:
--------------------------------------
I certainly recommend using {{SEARCH}} and sargs where possible. Making large
disjunctions tractable was one of my goals when I introduced sargs. But I think
of it as a best practice... if people choose not to convert their \{{IN}} lists
to sargs, they should not be surprised that large expressions are slow to
optimize. Do you think that Calcite should automatically convert disjunctions
to sargs?
> 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)
