[
https://issues.apache.org/jira/browse/CALCITE-7782?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
ASF GitHub Bot updated CALCITE-7782:
------------------------------------
Labels: pull-request-available (was: )
> Large string ARRAY validation is quadratic: 81 GB allocated at 100,000
> elements and no result after 20 minutes at 1,000,000
> ---------------------------------------------------------------------------------------------------------------------------
>
> Key: CALCITE-7782
> URL: https://issues.apache.org/jira/browse/CALCITE-7782
> Project: Calcite
> Issue Type: Bug
> Components: core
> Affects Versions: 1.36.0, 1.37.0, 1.38.0, 1.39.0, 1.40.0, 1.41.0, 1.42.0
> Reporter: Frank Chen
> Priority: Major
> Labels: pull-request-available
>
> The 81 GB figure is the cumulative allocation measured during one
> 100,000-element benchmark operation, not peak heap usage. With 1,000,000
> elements, the operation did not complete within 20 minutes, so no
> allocation-per-operation result was available.
> h3. Problem
> Validation of a large ARRAY constructor becomes approximately quadratic when
> many operands require casts to the derived component type.
> This behavior was introduced by
> [CALCITE-5948|https://issues.apache.org/jira/browse/CALCITE-5948],
> implemented in [PR #3395|https://github.com/apache/calcite/pull/3395], and
> released in Calcite 1.36.0. CALCITE-5948 correctly added explicit casts to
> preserve runtime type consistency; this issue concerns the performance of
> applying those casts, not their correctness.
> h3. Root cause
> {{SqlValidatorUtil.adjustTypeForMultisetConstructor}} processes operands
> individually:
> {code:java}
> for (int i = 0; i < operands.size(); i++) {
> if (!operandTypes.get(i).equalsSansFieldNames(elementType)) {
> call.setOperand(i, castTo(operands.get(i), elementType));
> }
> }
> {code}
> For a {{SqlBasicCall}}, every invocation of {{setOperand}} creates a new
> immutable copy of the complete operand list.
> When an ARRAY contains {{n}} operands and most require casts, the resulting
> work is approximately:
> {code}
> n replacements x copying n operands = O(n^2)
> {code}
> Mixed-width string literals trigger this readily. Calcite derives types such
> as {{CHAR(1)}}, {{CHAR(2)}}, and {{CHAR(6)}}, then adjusts them to a common
> {{VARCHAR}} component type. Consequently, nearly every element may enter the
> replacement path.
> The same helper is also used for MAP constructors, although the measurements
> below exercise ARRAY construction.
> h3. Reproducer
> The regression was reproduced through Apache Druid's
> {{InPlanningBenchmark.queryStringFunctionInSql}}. Druid rewrites the large
> literal {{IN}} predicate into a scalar function containing an ARRAY
> constructor.
> The generated query has this form:
> {code:sql}
> EXPLAIN PLAN FOR
> SELECT COUNT(*)
> FROM foo
> WHERE long1 = 8
> OR LOWER(string1) IN ('1', '2', ..., '1000000')
> {code}
> Parameters:
> {code}
> inClauseLiteralsCount = 1000000
> inSubQueryThreshold = 2147483647
> rowsPerSegment = 500000
> {code}
> Results from the same historical benchmark across Calcite upgrades:
> || Calcite version || Result ||
> | 1.35.0 | 10.39 s/op; 14.94 GB allocated/op |
> | 1.37.0 | No completed operation after 20 minutes |
> | 1.41.0 | No completed operation after 20 minutes |
> | 1.42.0 | No completed operation after 20 minutes |
> "No completed operation" means the benchmark was stopped after 20 minutes
> without producing a JMH score.
> The regression first appears after moving from Calcite 1.35 to 1.37. The
> relevant behavior was introduced in Calcite 1.36 by CALCITE-5948.
> h3. Allocation evidence
> With Calcite 1.42.0 and 100,000 string literals:
> {code}
> Average time: 5,305.626 ms/op
> Allocation: 81,622,365,189 B/op
> {code}
> A JFR profile attributed most allocation pressure to copying operations:
> {code}
> ImmutableList.copyOf: 50.29%
> Platform.copy: 41.28%
> {code}
> This is consistent with repeatedly copying a 100,000-element operand list
> while adjusting approximately 100,000 operands.
> h3. Expected behavior
> Applying required casts to ARRAY or MAP operands should scale approximately
> linearly with the number of operands. The explicit-cast correctness behavior
> introduced by CALCITE-5948 must be preserved.
> h3. Related issues
> * [CALCITE-5948|https://issues.apache.org/jira/browse/CALCITE-5948]
> introduced the required explicit ARRAY/MAP operand casts. This issue reports
> the resulting operand-replacement performance regression.
> * [CALCITE-7464|https://issues.apache.org/jira/browse/CALCITE-7464] concerns
> avoiding operand mutation as a side effect of ARRAY/MAP type coercion. It
> overlaps in implementation area but does not report the repeated
> immutable-list copying.
> * [CALCITE-7202|https://issues.apache.org/jira/browse/CALCITE-7202] reports
> memory growth for large IN predicates in {{SubQueryRemoveRule}}. It is
> similar in symptom but follows a different code path.
> * Downstream reproduction and investigation:
> [apache/druid#20326|https://github.com/apache/druid/issues/20326].
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
