[jira] [Created] (SPARK-55348) async_track expressions for efficient convergent algorithms in recursive CTEs (avoids exponential blowup)

["Bruno Messias (Jira)" <ji...@apache.org>]

Bruno Messias created SPARK-55348:
-------------------------------------

             Summary: async_track expressions for efficient convergent algorithms in recursive CTEs (avoids exponential blowup)
                 Key: SPARK-55348
                 URL: https://issues.apache.org/jira/browse/SPARK-55348
             Project: Spark
          Issue Type: New Feature
          Components: SQL
    Affects Versions: 4.1.1
            Reporter: Bruno Messias


This proposal introduces a *family of stateful expressions* (`async_track_min`, `async_track_max`, `async_track_...`) that prevent exponential row explosion in recursive CTEs for graph algorithms for example. These expressions filter redundant rows during iteration by tracking the "best" value seen for each key.

{*}Why it works{*}: For operators like `min`, `max`, and `first-seen` etc, the result is the same regardless of processing order. Spark's distributed task  is actually an advantage here: zero coordination overhead, with correctness guaranteed by the mathematical properties of these operators.

{*}Complexity improvement{*}: Without filtering, recursive CTEs enumerate all paths (exponential in graph density). With `async_track`, each key is accepted at most once per iteration, reducing worst-case complexity 


h3. Motivation: Need for Efficient Recursive CTEs

The introduction of recursive CTEs in Spark  was a significant step forward. I work in financial services where we are usubg recursive CTEs 

However, there's a hard ceiling: {*}row explosion{*}. Once graphs exceed a certain density or depth, queries become impractical due to exponential intermediate row growth. This forces teams to either:
 * Limit query scope to small subgraphs
 * Accept long runtimes and high compute costs
 * Move data to external graph systems (breaking the SQL-native workflow) and going outside from databrick



--
This message was sent by Atlassian Jira
(v8.20.10#820010)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org