Exponential planning time when window function is partitioned by multiple columns #17401

Activity

1. findepi

   added

   bugSomething isn't workingSomething isn't working

   optimizerOptimizer rulesOptimizer rules

   on Sep 4, 2025
2. findepi

   added the

   Bug

   issue type on Sep 4, 2025
3. findepi

   changed the title [-]Long planning time when window function is partitioned by multiple columns[/-] [+]Exponential planning time when window function is partitioned by multiple columns[/+] on Sep 4, 2025
4. findepi commented on Sep 4, 2025

   

   findepi

   on Sep 4, 2025

   Last edited by findepi

   MemberAuthor

   More actions

   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) due to planning overhead #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
5. findepi commented on Sep 4, 2025

   

   findepi

   on Sep 4, 2025

   Last edited by findepi

   MemberAuthor

   More actions

   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
6. findepi commented on Sep 4, 2025

   

   findepi

   on Sep 4, 2025

   MemberAuthor

   More actions

   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()
7. berkaysynnada commented on Sep 6, 2025

   

   berkaysynnada

   on Sep 6, 2025

   Contributor

   More actions

   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
8. findepi commented on Sep 9, 2025

   

   findepi

   on Sep 9, 2025

   MemberAuthor

   More actions

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

   🚀

   🚀React with 🚀1Reacted by Andrew Lamb
9. alamb

   closed this as completedin #17684on Sep 25, 2025