[
https://issues.apache.org/jira/browse/CALCITE-7867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18130181#comment-18130181
]
Alessandro Solimando commented on CALCITE-7867:
-----------------------------------------------
Thanks a lot [~zabetak] for making this connection with CALCITE-7226, we should
indeed produce a SEARCH/SARG representation in place of OR/AND chains in
_SqlToRelConverter._
This said, I agree with [~jooger] that this can be done as a follow-up and what
this ticket brings is valuable in itself, as we can end up with OR/AND chains
in other ways (including custom rules), and we might end up trying to simplify
them.
Please let me know if there are outstanding concerns, or if the approved PR can
be merged.
> 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
(v10.3.26#10030026)
