datafusion: Stack overflow calling `EqvalenceProperties::project` with certain order
Describe the bug
Given equivalence sort orders like this:
[
[a,b,c,d],
[a,c,b,d], // note b,d are swapped
]
When EqvalenceProperties::project is called to project a, b, c, d the stack overflows
To Reproduce
Reproducer:
#[test]
fn project_equivalence_properties_test_multi() -> Result<()> {
// test multiple input orderings with equivalence properties
let input_schema = Arc::new(Schema::new(vec![
Field::new("a", DataType::Int64, true),
Field::new("b", DataType::Int64, true),
Field::new("c", DataType::Int64, true),
Field::new("d", DataType::Int64, true),
]));
let mut input_properties = EquivalenceProperties::new(Arc::clone(&input_schema));
// add equivalent ordering [a, b, c, d]
input_properties.add_new_ordering(vec![
parse_sort_expr("a", &input_schema),
parse_sort_expr("b", &input_schema),
parse_sort_expr("c", &input_schema),
parse_sort_expr("d", &input_schema),
]);
// add equivalent ordering [a, c, b, d]
input_properties.add_new_ordering(vec![
parse_sort_expr("a", &input_schema),
parse_sort_expr("c", &input_schema),
parse_sort_expr("b", &input_schema), // NB b and c are swapped
parse_sort_expr("d", &input_schema),
]);
let proj_exprs = vec![
(col("a", &input_schema)?, "a".to_string()),
(col("b", &input_schema)?, "b".to_string()),
(col("c", &input_schema)?, "c".to_string()),
(col("d", &input_schema)?, "d".to_string()),
];
let projection_mapping = ProjectionMapping::try_new(&proj_exprs, &input_schema)?;
let out_properties = input_properties.project(&projection_mapping, input_schema);
assert_eq!(out_properties.to_string(), "order: [[a@0 ASC,b@1 ASC,c@2 ASC]]");
Ok(())
}
Full Diff
andrewlamb@Andrews-MacBook-Pro-2:~/Software/datafusion2$ git diff
diff --git a/datafusion/physical-expr/src/equivalence/properties.rs b/datafusion/physical-expr/src/equivalence/properties.rs
index dc59a1eb8..dc3929188 100644
--- a/datafusion/physical-expr/src/equivalence/properties.rs
+++ b/datafusion/physical-expr/src/equivalence/properties.rs
@@ -1755,6 +1761,46 @@ mod tests {
Ok(())
}
+ #[test]
+ fn project_equivalence_properties_test_multi() -> Result<()> {
+ // test multiple input orderings with equivalence properties
+ let input_schema = Arc::new(Schema::new(vec![
+ Field::new("a", DataType::Int64, true),
+ Field::new("b", DataType::Int64, true),
+ Field::new("c", DataType::Int64, true),
+ Field::new("d", DataType::Int64, true),
+ ]));
+
+ let mut input_properties = EquivalenceProperties::new(Arc::clone(&input_schema));
+ // add equivalent ordering [a, b, c, d]
+ input_properties.add_new_ordering(vec![
+ parse_sort_expr("a", &input_schema),
+ parse_sort_expr("b", &input_schema),
+ parse_sort_expr("c", &input_schema),
+ parse_sort_expr("d", &input_schema),
+ ]);
+
+ // add equivalent ordering [a, c, b, d]
+ input_properties.add_new_ordering(vec![
+ parse_sort_expr("a", &input_schema),
+ parse_sort_expr("c", &input_schema),
+ parse_sort_expr("b", &input_schema), // NB b and c are swapped
+ parse_sort_expr("d", &input_schema),
+ ]);
+
+ let proj_exprs = vec![
+ (col("a", &input_schema)?, "a".to_string()),
+ (col("b", &input_schema)?, "b".to_string()),
+ (col("c", &input_schema)?, "c".to_string()),
+ (col("d", &input_schema)?, "d".to_string()),
+ ];
+ let projection_mapping = ProjectionMapping::try_new(&proj_exprs, &input_schema)?;
+ let out_properties = input_properties.project(&projection_mapping, input_schema);
+
+ assert_eq!(out_properties.to_string(), "order: [[a@0 ASC,b@1 ASC,c@2 ASC]]");
+ Ok(())
+ }
+
#[test]
fn test_join_equivalence_properties() -> Result<()> {
let schema = create_test_schema()?;
@@ -3108,4 +3154,36 @@ mod tests {
assert!(lhs_orderings.contains(rhs_ordering), "{}", err_msg);
}
}
+
+ /// Converts a string to a physical sort expression
+ ///
+ /// # Example
+ /// * `"a"` -> (`"a"`, `SortOptions::default()`)
+ /// * `"a ASC"` -> (`"a"`, `SortOptions { descending: false, nulls_first: false }`)
+ fn parse_sort_expr(name: &str, schema: &SchemaRef) -> PhysicalSortExpr {
+ let mut parts = name.split_whitespace();
+ let name = parts.next().expect("empty sort expression");
+ let mut sort_expr = PhysicalSortExpr::new(
+ col(name, schema).expect("invalid column name"),
+ SortOptions::default(),
+ );
+
+ if let Some(options) = parts.next() {
+ sort_expr = match options {
+ "ASC" => sort_expr.asc(),
+ "DESC" => sort_expr.desc(),
+ _ => panic!(
+ "unknown sort options. Expected 'ASC' or 'DESC', got {}",
+ options
+ ),
+ }
+ }
+
+ assert!(
+ parts.next().is_none(),
+ "unexpected tokens in column name. Expected 'name' / 'name ASC' / 'name DESC' but got '{name}'"
+ );
+
+ sort_expr
+ }
Then run
cargo test --package datafusion-physical-expr --lib equivalence::properties::tests::project_equivalence_properties_test_multi -- --exact
Compiling datafusion-physical-expr v42.0.0 (/Users/andrewlamb/Software/datafusion2/datafusion/physical-expr)
Finished `test` profile [unoptimized + debuginfo] target(s) in 1.65s
Running unittests src/lib.rs (target/debug/deps/datafusion_physical_expr-a6fc7a49851ed9b5)
running 1 test
thread 'equivalence::properties::tests::project_equivalence_properties_test_multi' has overflowed its stack
fatal runtime error: stack overflow
error: test failed, to rerun pass `-p datafusion-physical-expr --lib`
Caused by:
process didn't exit successfully: `/Users/andrewlamb/Software/datafusion2/target/debug/deps/datafusion_physical_expr-a6fc7a49851ed9b5 'equivalence::properties::tests::project_equivalence_properties_test_multi' --exact` (signal: 6, SIGABRT: process abort signal)
Expected behavior
Test should pass (expected output will need to be updated)
Additional context
I found this while working on https://github.com/apache/datafusion/issues/12446 / https://github.com/apache/datafusion/pull/12562
About this issue
- Original URL
- State: closed
- Created 2 years ago
- Comments: 16 (16 by maintainers)
I couldn’t look this in detail. However, posting my thoughts, in case that helps. Given orderings are
[a,b,c,d]. [a,c,b,d]. One of the assumptions about theoeq_classis that, ordering representations inside it doesn’t contain any redundant information. As an example, if ordering given is[a,b,a,c]then it would be converted to the[a,b,c]internally. As another example, if orderings given are[a,b,c,d]and[a,b].oeq_classwill only store[a,b,c,d]internally.Similary, for the orderings
[a,b,c,d]and[a,c,b,d]. Their most condensed representation would be[a,b,d]and[a,c,d]. If we fail to represent ordering with this condensed version, subsequent stages might behave unexpectedly. This might be the root cause of the problem. However, as again I didn’t look into this problem in detail. I don’t want to misdirect anyone, just posting my immature thoughts.Thanks @berkaysynnada for this finding. Nice catch. I hope, I didn’t waste your time by misdirecting.
I have worked through this comment in detail to determine whether there is an actual bug in the current implementation. Initially, my thoughts were similar to @akurmustafa’s intuition, and I draft a few designs. However, I can now safely say that the current implementation is correct, and the tests are valid for both the
add_new_orderings()andsatisfy()APIs. Below are my brief findings:The example that triggered the initial bug was
[a, b, c, d]and[a, c, b, d]. We thought it could be simplified to[a, b, d]and[a, c, d], but this is a mistaken assumption.Why?
Consider this table:
This table is ordered by both
[a, b, c, d]and[a, c, b, d]; also[a, b, d]and[a, c, d]are also valid orderings. However, when we add these orderings to the equivalence properties, can we make them stored as[a, b, d]and[a, c, d]?The answer is no.
Consider this table:
This table also satisfies both
[a, b, c, d]and[a, c, b, d], but we cannot simplify them to[a, b, d]and[a, c, d]. In this case,[a, c, d]is not valid.If someone needs to infer an ordering corresponding to the first table, it should be given as
[a, b, d]and[a, c, d]because we can derive both[a, b, c, d]and[a, c, b, d]from these. However, the reverse is not true.In short:
[a, c]+[b, c]satisfies both[a, b, c]and[b, a, c]. (Global prefixes can be inserted anywhere in other orderings, and we can safely remove the duplicate element closer to the right-hand side.)[a, b, c]+[b, a, c]does not satisfy[a, c]or[b, c]. (It actually satisfies one of them, but since we cannot know which one, we say it does not satisfy either.) However, if we know thatais unique, we can ensure that[a, c]is valid. Similarly, ifbis unique, then[b, c]is valid. This is a task for another day.Hmm, will take a look. cc @akurmustafa