[
https://issues.apache.org/jira/browse/SPARK-59028?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
ASF GitHub Bot updated SPARK-59028:
-----------------------------------
Labels: pull-request-available (was: )
> Transpilation: category inference is quadratic in expression length
> -------------------------------------------------------------------
>
> Key: SPARK-59028
> URL: https://issues.apache.org/jira/browse/SPARK-59028
> Project: Spark
> Issue Type: Sub-task
> Components: PySpark, SQL
> Affects Versions: 4.3.0
> Reporter: Holden Karau
> Priority: Minor
> Labels: pull-request-available
>
> `_convert_chunk`'s `BinOp` arm calls `_category` on the left and right
> subtrees,
> then recurses into `_convert_chunk` on each — which calls `_category` over
> those
> same subtrees again, one level down. Each level walks the whole subtree and
> the
> result is discarded on descent, so inference is quadratic in expression
> length.
> Measured on the branch, replaying that call pattern against the unmodified
> `_category`: an `a0 + a1 + ... + aN` chain with N=160 operators produced 25760
> `_category` calls, i.e. calls/N² = 1.006. The same double-call pattern recurs
> at the
> comparison site, so a UDF mixing a long arithmetic chain with a comparison
> compounds.
> This is driver-side, inside query planning, once per `_build_transpiled` — and
> `_build_transpiled` now runs per `judf` build and per read of the `transpiled`
> property, so it is paid more often than it used to be.
> **Proposed fix:** memoize `_category` per `id(node)` for the duration of one
> combo
> (categories depend on `self._param_categories`, which changes per combo), or
> have
> `_convert_chunk` return `(Column, category)` so the separate pass disappears.
> The
> second is the better shape and a bigger change.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
