Why ddx uses a SQL rewrite, not a Substrait plan round-trip (recursive CTEs & DML unsupported)

[alxmrs]

Why ddx uses a SQL rewrite, not a Substrait plan round-trip

ddx differentiates grad()/jvp()/vjp() as a plan-time rewrite (they are
markers that must be rewritten away before execution — see
docs/design.md §3.1). One approach we evaluated
and rejected — the intermediate design in the
xarray-sql prototype PR #192
(commit 672e7d0) — round-tripped the entire DataFusion LogicalPlan through
Substrait to apply the rewrite in a separately-linked copy of DataFusion:

produce LogicalPlan as Substrait → rewrite grad() → re-produce Substrait →
consume & execute.

That approach was deleted (PR #192 commit 14b26971) because Substrait's producer
cannot represent the query shapes that make in-SQL training loops interesting.
This issue records a fresh, reproduced account of the limitation and is the
reference for design.md §3.2 and §6 (Substrait is
off the critical path; we rewrite grad() as SQL text before planning instead).

Reproduction (datafusion 54.0.0)

import datafusion
from datafusion import SessionContext
from datafusion.substrait import Producer

ctx = SessionContext()
ctx.from_pydict({"x": [1.0, 2.0, 3.0]}, "t")

def produce(label, sql):
    try:
        plan = ctx.sql(sql).logical_plan()
        Producer.to_substrait_plan(plan, ctx)
        print(f"{label}: OK")
    except Exception as e:
        print(f"{label}: FAILED -> {type(e).__name__}: {str(e)[:160]}")

produce("control (projection)", "SELECT x + 1.0 AS y FROM t")
produce("recursive CTE",
        "WITH RECURSIVE r(step, v) AS ("
        " SELECT 0 AS step, CAST(1.0 AS DOUBLE) AS v UNION ALL"
        " SELECT step + 1, v / 2 FROM r WHERE step < 5) SELECT v FROM r")
produce("scalar subquery", "SELECT x, (SELECT max(x) FROM t) AS mx FROM t")
produce("DML (INSERT...SELECT)", "INSERT INTO t SELECT x + 1.0 FROM t")

Output:

control (projection):  OK
recursive CTE:         FAILED -> RuntimeError: NotImplemented("Unsupported plan type: RecursiveQuery { name: \"r\", ... }")
scalar subquery:       OK
DML (INSERT...SELECT): FAILED -> RuntimeError: NotImplemented("Unsupported plan type: DmlStatement { table_name: ... op: Insert ... }")

What's still blocking vs. what has been fixed upstream

Query shape	to_substrait_plan (datafusion 54.0.0)
Plain scalar projection	✅ works
Recursive CTE (WITH RECURSIVE)	❌ Unsupported plan type: RecursiveQuery
DML (INSERT … SELECT)	❌ Unsupported plan type: DmlStatement
Scalar subquery	✅ works (this was a limitation at xarray-sql#197 time; fixed since)

Recursive CTEs and DML are precisely the shapes needed to express a training
loop in one query (e.g. gradient descent / Newton's method in a WITH RECURSIVE, or INSERT-ing updated parameters), so their absence is
disqualifying for a Substrait-plan-transport design.

Root cause

• datafusion-substrait's producer does not (yet) support the RecursiveQuery or
  DmlStatement logical-plan nodes. Upstream tracking:
  apache/datafusion#16248 (Substrait conversion issues epic).
• The deeper reason a bridge was needed at all: the native extension statically
  links its own copy of DataFusion, so it cannot share Expr/LogicalPlan
  objects with datafusion-python — forcing Substrait serialization as the
  transport, which makes Substrait's representational limits the bottleneck.

Design consequence (what ddx does instead)

Rewrite grad()/jvp()/vjp() as a SQL source-to-source transform before
planning (ddx-core::rewrite_sql): parse with a dialect-aware parser
(sqlparser), differentiate the marker's argument on the AST, unparse, splice
back. This works for every query shape the parser accepts — recursive CTEs, DML,
subqueries — needs no Substrait, no protoc, and no engine fork. See
design.md §3.2, §5, §6.

Follow-up (optional)

If/when datafusion-substrait gains RecursiveQuery + DmlStatement producer
support, a Substrait scalar-expression front-end could be revisited as an
optional adapter — but it is not required and not planned for v1.

Reproduced with datafusion==54.0.0 on macOS (CPython 3.13).