Iurii Gerzhedovich created CALCITE-7868:
-------------------------------------------
Summary: 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
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)
