Holden Karau created SPARK-59028:
------------------------------------
Summary: 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
`_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]
