Frank Chen created CALCITE-7782:
-----------------------------------
Summary: 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.42.0, 1.41.0, 1.40.0, 1.39.0, 1.38.0, 1.37.0, 1.36.0
Reporter: Frank Chen
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)
