You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "aprimadi (via GitHub)" <gi...@apache.org> on 2023/05/16 08:10:02 UTC

[GitHub] [arrow-datafusion] aprimadi opened a new pull request, #6360: Switch to non-recursive on heap virtual stack to parse expr

aprimadi opened a new pull request, #6360:
URL: https://github.com/apache/arrow-datafusion/pull/6360

   # Which issue does this PR close?
   
   TODO
   
   # Rationale for this change
   
   TODO
   
   # What changes are included in this PR?
   
   TODO
   
   # Are these changes tested?
   
   Yes. Tested by existing tests. Also added a few stack overflow tests.
   
   # Are there any user-facing changes?
   
   No


-- 
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


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

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6360:
URL: https://github.com/apache/arrow-datafusion/pull/6360#issuecomment-1553481183

   Thanks again @aprimadi 


-- 
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


[GitHub] [arrow-datafusion] alamb merged pull request #6360: Switch to non-recursive on heap virtual stack when building logical plan from SQL expression

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #6360:
URL: https://github.com/apache/arrow-datafusion/pull/6360


-- 
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


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

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #6360:
URL: https://github.com/apache/arrow-datafusion/pull/6360#discussion_r1196960005


##########
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 +`.

Review Comment:
   Can you please add a link to https://github.com/apache/arrow-datafusion/issues/1444 (so the rationale for using this stack machine is clearer):
   
   ```suggestion
           // produces expressions in postfix notations, i.e. `a + b` => `a b +`.
           // See https://github.com/apache/arrow-datafusion/issues/1444
   ```



##########
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:
   I don't think `Box`ing the `Vec` is necessary in this case (as there is a `Box` internally in the `Vec` for the actual data items).
   
   I tried switching it to 
   ```suggestion
           let mut stack = vec![StackEntry::SQLExpr(Box::new(sql))];
           let mut eval_stack = vec![];
   ```
   
   And all the tests continue to pass



##########
datafusion/sql/src/expr/mod.rs:
##########
@@ -566,3 +595,124 @@ fn plan_indexed(expr: Expr, mut keys: Vec<SQLExpr>) -> Result<Expr> {
         plan_key(key)?,
     )))
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    use std::collections::HashMap;
+    use std::sync::Arc;
+
+    use arrow::datatypes::{DataType, Field, Schema};
+    use sqlparser::dialect::GenericDialect;
+    use sqlparser::parser::Parser;
+
+    use datafusion_common::config::ConfigOptions;
+    use datafusion_expr::logical_plan::builder::LogicalTableSource;
+    use datafusion_expr::{AggregateUDF, ScalarUDF, TableSource};
+
+    use crate::TableReference;
+
+    struct TestSchemaProvider {
+        options: ConfigOptions,
+        tables: HashMap<String, Arc<dyn TableSource>>,
+    }
+
+    impl TestSchemaProvider {
+        pub fn new() -> Self {
+            let mut tables = HashMap::new();
+            tables.insert(
+                "table1".to_string(),
+                create_table_source(vec![Field::new(
+                    "column1".to_string(),
+                    DataType::Utf8,
+                    false,
+                )]),
+            );
+
+            Self {
+                options: Default::default(),
+                tables,
+            }
+        }
+    }
+
+    impl ContextProvider for TestSchemaProvider {
+        fn get_table_provider(
+            &self,
+            name: TableReference,
+        ) -> Result<Arc<dyn TableSource>> {
+            match self.tables.get(name.table()) {
+                Some(table) => Ok(table.clone()),
+                _ => Err(DataFusionError::Plan(format!(
+                    "Table not found: {}",
+                    name.table()
+                ))),
+            }
+        }
+
+        fn get_function_meta(&self, _name: &str) -> Option<Arc<ScalarUDF>> {
+            None
+        }
+
+        fn get_aggregate_meta(&self, _name: &str) -> Option<Arc<AggregateUDF>> {
+            None
+        }
+
+        fn get_variable_type(&self, _variable_names: &[String]) -> Option<DataType> {
+            None
+        }
+
+        fn options(&self) -> &ConfigOptions {
+            &self.options
+        }
+    }
+
+    fn create_table_source(fields: Vec<Field>) -> Arc<dyn TableSource> {
+        Arc::new(LogicalTableSource::new(Arc::new(
+            Schema::new_with_metadata(fields, HashMap::new()),
+        )))
+    }
+
+    macro_rules! test_stack_overflow {
+        ($num_expr:expr) => {
+            paste::item! {
+                #[test]
+                fn [<test_stack_overflow_ $num_expr>]() {
+                    let schema = DFSchema::empty();
+                    let mut planner_context = PlannerContext::default();
+
+                    let expr_str = (0..$num_expr)
+                        .map(|i| format!("column1 = 'value{:?}'", i))
+                        .collect::<Vec<String>>()
+                        .join(" OR ");
+
+                    let dialect = GenericDialect{};
+                    let mut parser = Parser::new(&dialect)
+                        .try_with_sql(expr_str.as_str())
+                        .unwrap();
+                    let sql_expr = parser.parse_expr().unwrap();
+
+                    let schema_provider = TestSchemaProvider::new();
+                    let sql_to_rel = SqlToRel::new(&schema_provider);
+
+                    // Should not stack overflow
+                    sql_to_rel.sql_expr_to_logical_expr(
+                        sql_expr,
+                        &schema,
+                        &mut planner_context,
+                    ).unwrap();
+                }
+            }
+        };
+    }
+
+    test_stack_overflow!(64);

Review Comment:
   I verified that without the code in this PR, the tests fail as expected:
   
   ```
   running 14 tests
   test expr::arrow_cast::test::test_parse_data_type_whitespace_tolerance ... ok
   test expr::identifier::test::test_form_identifier ... ok
   test expr::identifier::test::test_generate_schema_search_terms ... ok
   test expr::arrow_cast::test::parse_data_type_errors ... ok
   test expr::arrow_cast::test::test_parse_data_type ... ok
   test parser::tests::create_external_table ... ok
   test expr::tests::test_stack_overflow_64 ... ok
   test expr::tests::test_stack_overflow_128 ... ok
   test expr::tests::test_stack_overflow_256 ... ok
   test expr::tests::test_stack_overflow_512 ... ok
   
   thread 'expr::tests::test_stack_overflow_1024' has overflowed its stack
   fatal runtime error: stack overflow
   error: test failed, to rerun pass `-p datafusion-sql --lib`
   
   Caused by:
     process didn't exit successfully: `/Users/alamb/Software/target-df2/debug/deps/datafusion_sql-8a77caa8d397a04b` (signal: 6, SIGABRT: process abort signal)
   
   ```



-- 
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


[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

Posted by "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


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

Posted by "aprimadi (via GitHub)" <gi...@apache.org>.
aprimadi commented on PR #6360:
URL: https://github.com/apache/arrow-datafusion/pull/6360#issuecomment-1554033321

   Thank you @alamb for the review


-- 
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