Exponential planning time when window function is partitioned by multiple columns

[findepi]

Describe the bug

Planning time, or to be precise: optimization time, is very long for queries that have a window function partitioned by multiple columns.

To Reproduce

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ⁿ)¹ where n is number of columns used in PARTITION BY

Expected behavior

In DataFusion 45.0.0 this query runs in <100ms.

Additional context

No response

Footnotes

1. based on timings when adding or removing a column. Definitely exponential, not sure the base. ↩

[findepi]

Related issues

• Improve Planning Time #13015 -- but that one does not involve aggregate functions. It indicates EquivalenceProperties as the culprit and my naive analysis also points at that class.
• Bad performance on wide tables (1000+ columns) #7698 -- but that one talks about wide tables and quadratic behavior. Here the reproducer is table with only dozen columns, and the problem is exponential
• Planning time for queries with many columns with union and order by is very slow #17261 -- but that one talks about UNION and ORDER BY, here we have only a window function
• Exponential planning time (100s of seconds) with UNION and ORDER BY queries #13748 -- because that one is also about exponential planning time, however talks about UNION and ORDER BY, here we have only a window function

[findepi]

I run git bisect, inspecting timing of the query

( 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;
"; )

it resulted in

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)

• Window Functions Order Conservation -- Follow-up On Set Monotonicity #14813 landed in 46.0.0 and that's the first version affected

cc @berkaysynnada @ozankabak @Omega359 @alamb

[findepi]

Some code pieces with seemingly exponential complexity

• datafusion/datafusion/physical-plan/src/windows/mod.rs

  Lines 375 to 376 in a5c242c

  	.map(|pb_order| sort_options_resolving_constant(Arc::clone(pb_order)))
  	.multi_cartesian_product()

  • 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

• datafusion/datafusion/physical-plan/src/windows/mod.rs

  Lines 469 to 470 in a5c242c

  	.map(sort_options_resolving_constant)
  	.multi_cartesian_product();

  • 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

datafusion/datafusion/expr-common/src/signature.rs

Line 551 in 9e062df

.multi_cartesian_product()

[berkaysynnada]

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

[findepi]

@berkaysynnada has an idea how to replace the exponential algorithm with a linear one: #14813 (comment)

🚀