[GitHub] [arrow-datafusion] aprimadi commented on a diff in pull request #6360: Switch to non-recursive on heap virtual stack when building logical plan from SQL expression

["aprimadi (via GitHub)" <gi...@apache.org>]

aprimadi commented on code in PR #6360:
URL: https://github.com/apache/arrow-datafusion/pull/6360#discussion_r1197347949


##########
datafusion/sql/src/expr/mod.rs:
##########
@@ -46,27 +46,56 @@ impl<'a, S: ContextProvider> SqlToRel<'a, S> {
         schema: &DFSchema,
         planner_context: &mut PlannerContext,
     ) -> Result<Expr> {
-        // Workaround for https://github.com/apache/arrow-datafusion/issues/4065
-        //
-        // Minimize stack space required in debug builds to plan
-        // deeply nested binary operators by keeping the stack space
-        // needed for sql_expr_to_logical_expr minimal for BinaryOp
-        //
-        // The reason this reduces stack size in debug builds is
-        // explained in the "Technical Backstory" heading of
-        // https://github.com/apache/arrow-datafusion/pull/1047
-        //
-        // A likely better way to support deeply nested expressions
-        // would be to avoid recursion all together and use an
-        // iterative algorithm.
-        match sql {
-            SQLExpr::BinaryOp { left, op, right } => {
-                self.parse_sql_binary_op(*left, op, *right, schema, planner_context)
+        enum StackEntry {
+            SQLExpr(Box<SQLExpr>),
+            Operator(Operator),
+        }
+
+        // Virtual stack machine to convert SQLExpr to Expr
+        // This allows visiting the expr tree in a depth-first manner which
+        // produces expressions in postfix notations, i.e. `a + b` => `a b +`.
+        let mut stack: Box<Vec<StackEntry>> =
+            Box::new(vec![StackEntry::SQLExpr(Box::new(sql))]);
+        let mut eval_stack = Box::<Vec<Expr>>::default();

Review Comment:
   Nice. I didn't know that.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org