kosiew commented on code in PR #26853:
URL: https://github.com/apache/datafusion/pull/26853#discussion_r4422111216
##########
datafusion/physical-expr/benches/equivalence_properties.rs:
##########
@@ -152,5 +154,85 @@ fn bench_ordering_satisfaction(c: &mut Criterion) {
group.finish();
}
-criterion_group!(benches, bench_ordering_satisfaction);
+/// Other shapes: `find_longest_permutation`, the orderings that window
+/// aggregates add, and a deeply nested sort key.
+fn bench_shapes(c: &mut Criterion) {
+ let mut group = c.benchmark_group("equivalence_properties_shapes");
+ let opts = [(false, false), (false, true), (true, false), (true,
true)].map(
+ |(descending, nulls_first)| SortOptions {
+ descending,
+ nulls_first,
+ },
+ );
+ let asc_nulls_last = opts[0];
+
+ // `find_longest_permutation` with one expression, and with five: `c0`,
+ // `c1`, `c2` and `c3` are found one per round, `c7` never.
+ for n_classes in [2, 32] {
+ let props = properties(n_classes);
+ let one = vec![col(0)];
+ let five = vec![col(3), col(2), col(1), col(0), col(7)];
+ group.bench_function(
+ BenchmarkId::new("find_longest_permutation/1_expr", n_classes),
+ |b| b.iter(|| props.find_longest_permutation(&one).unwrap()),
+ );
+ group.bench_function(
+ BenchmarkId::new("find_longest_permutation/5_exprs", n_classes),
+ |b| b.iter(|| props.find_longest_permutation(&five).unwrap()),
+ );
+ }
+
+ // `w` window aggregates over a whole partition, such as
+ // `SUM(x) OVER (PARTITION BY c0)`: each is constant per `c0`, which is
+ // recorded by adding `[c0, w_i]` in all four directions of `w_i`
+ // (columns `c1..=cw`). The requirement is `[c0, c1]`.
+ for w in [4, 16, 32] {
+ let mut props = EquivalenceProperties::new(schema(w + 1));
+ let mut orderings = vec![];
+ for i in 1..=w {
+ for o in opts {
+ orderings.push(vec![
+ PhysicalSortExpr::new(col(0), asc_nulls_last),
+ PhysicalSortExpr::new(col(i), o),
+ ]);
+ }
+ }
+ props.add_orderings(orderings);
+ let keys = vec![
+ PhysicalSortExpr::new(col(0), asc_nulls_last),
+ PhysicalSortExpr::new(col(1), asc_nulls_last),
+ ];
+ group.bench_function(BenchmarkId::new("window", w), |b| {
+ b.iter_batched(
+ || keys.clone(),
+ |keys| props.ordering_satisfy(keys).unwrap(),
+ BatchSize::SmallInput,
+ )
+ });
+ }
+
+ // Deep key: `[c0, e, c1]` with `e = c1 + 1 + ... + 1` nested `depth` deep.
+ for depth in [4, 8, 16, 32] {
+ let props = properties(8);
+ let mut e = col(1);
+ for _ in 0..depth {
+ e = Arc::new(BinaryExpr::new(e, Operator::Plus, lit(1i32)));
+ }
+ let keys = vec![
+ asc(0),
+ PhysicalSortExpr::new(e, SortOptions::default()),
+ asc(1),
+ ];
+ group.bench_function(BenchmarkId::new("deep_key", depth), |b| {
+ b.iter_batched(
+ || keys.clone(),
+ |keys| props.ordering_satisfy(keys).unwrap(),
Review Comment:
As a non-blocking follow-up, could we benchmark right-nested `1 + (1 + (...
+ c1))` alongside the current left-nested expression at matching depths?
`Walk::is_fixed` visits children left-to-right, but recursive hashing also
contributes, so compare measured results against the same baseline at the
reviewed tip. Older results showed roughly 13%/28% slowdowns at depths 16/32
for the current shape, not this variant.
##########
datafusion/physical-expr/benches/equivalence_properties.rs:
##########
@@ -152,5 +154,85 @@ fn bench_ordering_satisfaction(c: &mut Criterion) {
group.finish();
}
-criterion_group!(benches, bench_ordering_satisfaction);
+/// Other shapes: `find_longest_permutation`, the orderings that window
+/// aggregates add, and a deeply nested sort key.
+fn bench_shapes(c: &mut Criterion) {
+ let mut group = c.benchmark_group("equivalence_properties_shapes");
+ let opts = [(false, false), (false, true), (true, false), (true,
true)].map(
+ |(descending, nulls_first)| SortOptions {
+ descending,
+ nulls_first,
+ },
+ );
+ let asc_nulls_last = opts[0];
+
+ // `find_longest_permutation` with one expression, and with five: `c0`,
+ // `c1`, `c2` and `c3` are found one per round, `c7` never.
+ for n_classes in [2, 32] {
+ let props = properties(n_classes);
+ let one = vec![col(0)];
+ let five = vec![col(3), col(2), col(1), col(0), col(7)];
+ group.bench_function(
+ BenchmarkId::new("find_longest_permutation/1_expr", n_classes),
+ |b| b.iter(|| props.find_longest_permutation(&one).unwrap()),
Review Comment:
Could we add untimed assertions before registering these benchmarks? For
`[c3, c2, c1, c0, c7]`, verify permutation indices `[3, 2, 1, 0]` (excluding
`c7`), the single-expression result `[0]`, and successful window ordering
satisfaction. Currently `unwrap()` misses incorrect results that could appear
faster. This validates the direct-column workload but does not replace the
requested computed-key partial-constant test.
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
