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)

Most upvoted comments

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 the oeq_class is 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_class will 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.

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() and satisfy() APIs. Below are my brief findings:

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() and satisfy() 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:

a b c d
1 1 1 1
1 1 2 2
1 2 3 3
1 3 4 1

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:

a b c d
1 1 1 1
1 1 2 2
1 2 3 3
1 3 3 1

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 that a is unique, we can ensure that [a, c] is valid. Similarly, if b is unique, then [b, c] is valid. This is a task for another day.

Hmm, will take a look. cc @akurmustafa