Restructure core codepaths to prevent stack overflows

[ahmed-mez]

Describe the bug

In PR #16506, we added #[recursive] annotations (behind the recursive_protection feature flag) to a subset of recursive functions across the optimizer, physical planner, and expression evaluator. While this prevented stack-overflow panics on deeply nested plans, benchmarks showed a 1–2% slowdown in planning time when the feature is enabled.

“The benchmarks seem to imply this has some non trivial overhead (slows down planning by 1–2%).
I wonder if there is any way to restructure the affected codepaths to avoid the recursion (change them into an iterative version, for example, or Box more structures to reduce the stack size?)”
— @alamb

This epic will serve as a central place to explore multiple approaches (e.g., iterative rewrites, Box-based data structures to shrink stack usage, or other patterns) to reduce/eliminate deep recursion in key codepaths, remove the need for defensive macros, and regain any lost performance, all while still handling arbitrarily nested plans reliably.

To Reproduce

#16787 provides a reproducer.

Expected behavior

DataFusion doesn't overflow its stack.

Additional context

See the discussion in #16506

[gabotechs]

This seems like a recurring problem specially when submitting Substrait plans to DataFusion. There was this other instance that was fixed by @fmonjalet some months ago #16031, and the solution seemed to be to build the LogicalPlan differently.

Do you think there could be an opportunity to map the Substrait -> DataFusion plans differently so that this does not happen? or could this also happen in DataFusion's SQL path.

[ahmed-mez]

From the work done in #16506, this is not substrait specific. The stack overflows happen during the planning / optimization phase and even during execution.