You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "findepi (via GitHub)" <gi...@apache.org> on 2025/09/04 07:26:16 UTC
[I] Long planning time when window function is partitioned by multiple columns [datafusion]
findepi opened a new issue, #17401:
URL: https://github.com/apache/datafusion/issues/17401
### Describe the bug
Planning time, or to be precise: optimization time, is high for queries that have a window function partitioned by multiple columns.
### To Reproduce
```sql
WITH source AS (
SELECT
1 AS n,
'' AS a1, '' AS a2, '' AS a3, '' AS a4, '' AS a5, '' AS a6, '' AS a7, '' AS a8,
'' AS a9, '' AS a10, '' AS a11, '' AS a12
)
SELECT
sum(n) OVER (PARTITION BY
a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12
)
FROM source;
```
In 48.0.1 this takes ~543 seconds.
On current `main` this takes ~292 seconds
It looks `O(4ⁿ)`[^1] where `n` is number of columns partitioned by
[^1]: based on timings when adding or removing a column
### Expected behavior
In DataFusion 45.0.0 this query runs in <100ms.
### Additional context
_No response_
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Exponential planning time when window function is partitioned by multiple columns [datafusion]
Posted by "findepi (via GitHub)" <gi...@apache.org>.
findepi commented on issue #17401:
URL: https://github.com/apache/datafusion/issues/17401#issuecomment-3252697480
Some code pieces with seemingly exponential complexity
- https://github.com/apache/datafusion/blob/a5c242c21443e4881e6843f754493ab02238b655/datafusion/physical-plan/src/windows/mod.rs#L375-L376
- for each of N input expressions, `sort_options_resolving_constant` returns pair of values (N pairs)
then `multi_cartesian_product` calculates cartesian product of these pairs, 2^N combinations
- https://github.com/apache/datafusion/blob/a5c242c21443e4881e6843f754493ab02238b655/datafusion/physical-plan/src/windows/mod.rs#L469-L470
- looks same as above
However, every usage of `multi_cartesian_product` looks suspicious.
For example, this one looks also dangerous, just not related to window functions
https://github.com/apache/datafusion/blob/9e062dfb41efbf817e6f0be5bb4e238f8c9ec93c/datafusion/expr-common/src/signature.rs#L551
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Exponential planning time when window function is partitioned by multiple columns [datafusion]
Posted by "findepi (via GitHub)" <gi...@apache.org>.
findepi commented on issue #17401:
URL: https://github.com/apache/datafusion/issues/17401#issuecomment-3252548104
I run `git bisect`, inspecting timing of the query
```bash
( cd datafusion-cli && cargo run --bin datafusion-cli -- --command "
WITH source AS (
SELECT
1 AS n,
'' AS a1, '' AS a2, '' AS a3, '' AS a4, '' AS a5, '' AS a6, '' AS a7, '' AS a8,
'' AS a9, '' AS a10, '' AS a11, '' AS a12
)
SELECT
sum(n) OVER (PARTITION BY
a1, a2, a3, a4, a5, a6, a7, a8, a9
)
FROM source;
"; )
```
```
ea0686b8ce4b45cb61ba7fecac563cfa17f13595 is the first bad commit
commit ea0686b8ce4b45cb61ba7fecac563cfa17f13595 (HEAD)
Date: Wed Feb 26 17:35:37 2025 +0300
Window Functions Order Conservation -- Follow-up On Set Monotonicity (#14813)
```
- https://github.com/apache/datafusion/pull/14813 landed in 46.0.0 and that's the first version affected
cc @berkaysynnada @ozankabak @Omega359 @alamb
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Exponential planning time when window function is partitioned by multiple columns [datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on issue #17401:
URL: https://github.com/apache/datafusion/issues/17401#issuecomment-3262089632
Perhaps we can find a way of detecting redundancy of the order propagation over window ops (or just a simple rule) and skip those high complexity calculations
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Exponential planning time when window function is partitioned by multiple columns [datafusion]
Posted by "findepi (via GitHub)" <gi...@apache.org>.
findepi commented on issue #17401:
URL: https://github.com/apache/datafusion/issues/17401#issuecomment-3252329941
Related issues
- https://github.com/apache/datafusion/issues/13015 -- but that one does not involve aggregate functions. It indicates `EquivalenceProperties` as the culprit and my naive analysis also points at that class.
- https://github.com/apache/datafusion/issues/7698 -- but that one talks about wide tables. Here the reproducer is table with only dozen columns
- https://github.com/apache/datafusion/issues/17261 -- but that one talks about UNION and ORDER BY, here we have only a window function
- https://github.com/apache/datafusion/issues/13748 -- because that one is also about exponential planning time, however talks about UNION and ORDER BY, here we have only a window function
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Exponential planning time when window function is partitioned by multiple columns [datafusion]
Posted by "findepi (via GitHub)" <gi...@apache.org>.
findepi commented on issue #17401:
URL: https://github.com/apache/datafusion/issues/17401#issuecomment-3271751244
@berkaysynnada has an idea how to replace the exponential algorithm with a linear one: https://github.com/apache/datafusion/pull/14813#discussion_r2334061407
🚀
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Exponential planning time when window function is partitioned by multiple columns [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed issue #17401: Exponential planning time when window function is partitioned by multiple columns
URL: https://github.com/apache/datafusion/issues/17401
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org