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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
