Skip to content

Commit 350ca76

Browse files
perf: deduplicate found expressions with an IndexSet (#26474)
I've got a few fixes to upstream so just starting with small ones. ## Which issue does this PR close? <!-- We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123. --> - Closes #26473 ## Rationale for this change `find_exprs_in_exprs` and `find_exprs_in_expr` deduplicate with `Vec::contains`, which is quadratic in the number of distinct matches. On 20,000 distinct aggregates `find_aggregate_exprs` takes 932 ms; with this change it takes 2.8 ms (release build, see the issue for the full table). ## What changes are included in this PR? Both functions now collect into a single index set. ## Are there any user-facing changes? No
1 parent 51a4bfc commit 350ca76

1 file changed

Lines changed: 29 additions & 13 deletions

File tree

‎datafusion/expr/src/utils.rs‎

Lines changed: 29 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -862,15 +862,11 @@ fn find_exprs_in_exprs<'a, F>(
862862
where
863863
F: Fn(&Expr) -> bool,
864864
{
865-
exprs
866-
.into_iter()
867-
.flat_map(|expr| find_exprs_in_expr(expr, test_fn))
868-
.fold(vec![], |mut acc, expr| {
869-
if !acc.contains(&expr) {
870-
acc.push(expr)
871-
}
872-
acc
873-
})
865+
let mut found = IndexSet::new();
866+
for expr in exprs {
867+
collect_exprs_in_expr(expr, test_fn, &mut found);
868+
}
869+
found.into_iter().collect()
874870
}
875871

876872
/// Search an `Expr`, and all of its nested `Expr`'s, for any that pass the
@@ -880,11 +876,17 @@ fn find_exprs_in_expr<F>(expr: &Expr, test_fn: &F) -> Vec<Expr>
880876
where
881877
F: Fn(&Expr) -> bool,
882878
{
883-
let mut exprs = vec![];
879+
find_exprs_in_exprs(std::iter::once(expr), test_fn)
880+
}
881+
882+
fn collect_exprs_in_expr<F>(expr: &Expr, test_fn: &F, found: &mut IndexSet<Expr>)
883+
where
884+
F: Fn(&Expr) -> bool,
885+
{
884886
expr.apply(|expr| {
885887
if test_fn(expr) {
886-
if !(exprs.contains(expr)) {
887-
exprs.push(expr.clone())
888+
if !found.contains(expr) {
889+
found.insert(expr.clone());
888890
}
889891
// Stop recursing down this expr once we find a match
890892
return Ok(TreeNodeRecursion::Jump);
@@ -894,7 +896,6 @@ where
894896
})
895897
// pre_visit always returns OK, so this will always too
896898
.expect("no way to return error during recursion");
897-
exprs
898899
}
899900

900901
/// Recursively inspect an [`Expr`] and all its children.
@@ -1666,6 +1667,21 @@ mod tests {
16661667
Ok(())
16671668
}
16681669

1670+
#[test]
1671+
fn find_aggregate_exprs_dedups_in_order_of_appearance() {
1672+
use crate::test::function_stub::{count, sum};
1673+
1674+
let exprs = [
1675+
sum(col("a")) + count(col("b")),
1676+
count(col("b")) * sum(col("c")),
1677+
sum(col("a")) + sum(col("a")),
1678+
];
1679+
assert_eq!(
1680+
find_aggregate_exprs(&exprs),
1681+
vec![sum(col("a")), count(col("b")), sum(col("c"))]
1682+
);
1683+
}
1684+
16691685
#[test]
16701686
fn test_group_window_expr_by_sort_keys_empty_case() -> Result<()> {
16711687
let result = group_window_expr_by_sort_keys(vec![])?;

0 commit comments

Comments
 (0)