jayzhan211 commented on code in PR #26853:
URL: https://github.com/apache/datafusion/pull/26853#discussion_r4430034428
##########
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:
I measured both shapes locally on a laptop: 7 alternating runs, median time
of this PR divided by the merge base, at depths 4 / 8 / 16 / 32. The laptop
runs a bit higher than the bot at depths 16 and 32 (the bot had 1.13 / 1.28 for
the first row).
| Key | 4 | 8 | 16 | 32 |
|---|---|---|---|---|
| Left-nested `c1 + 1 + ... + 1` (the bench case) | 0.79 | 1.02 | 1.21 |
1.44 |
| Right-nested `1 + (1 + (... + c1))` | 0.81 | 1.02 | 1.16 | 1.39 |
| Left-nested, `+` with overflow checks | 0.82 | 1.02 | 1.24 | 1.44 |
| Right-nested, `+` with overflow checks | 0.83 | 1.04 | 1.20 | 1.42 |
The right-nested key tracks the left-nested one. For it, `is_fixed` checks
the literal child first, which is only a type check, and then goes down the
same depth.
The assertions you asked for in the other thread showed that the bench case
never gets past `e`: since #23910, a `+` that may overflow is unordered, so
both versions compute the properties of `e` and stop there. That is why I added
the rows with overflow checks, where `e` is ordered and the check goes on to
`c1`. The ratios are the same. The bench case now asserts that it is not
satisfied, and its comment says why.
I did not add the right-nested shape to the bench, since it shows nothing
the left-nested one does not. Let me know if you would like it there anyway.
--
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]
