andygrove commented on PR #2216:
URL:
https://github.com/apache/datafusion-ballista/pull/2216#issuecomment-5226692503
This is still a draft so please feel free to disregard any or all of this, I
know you're mid iteration. I had it open anyway and found one thing I thought
was worth passing along early rather than sitting on.
First the good parts. The statistical tests against the DataSketches
empirical rank error bound are a real upgrade over what was in `kll.rs` before,
and they're all seeded so they won't flake. The deferred optimizations section
with the struck through items and measured numbers next to each is unusually
easy to follow. And reporting the 5.7x `OwnedRow` regression plainly instead of
burying it is the right call.
## CI
Three jobs are red. `test linux ballista` is the `ballista-chaos` cluster
startup flake and has nothing to do with this PR. The other two are real:
```
test kll::tests::absorb_sorted_slice_debug_asserts_on_unsorted - should
panic ... FAILED
```
The cause is that `[profile.ci]` in the root `Cargo.toml` sets
`debug-assertions = false`, and CI runs `cargo test --profile ci`. So
`debug_assert!` never fires under CI and a `#[should_panic]` test on one can't
pass.
## The thing I'd actually push on
That failure isn't just a broken test, I think it's the API telling on
itself. `absorb_sorted_slice` is a safe `pub fn` whose own docs say that
violating the precondition silently corrupts the sketch, and the only guard is
a `debug_assert!` that the project's test profile compiles out. So the
protection doesn't exist in the configuration we test and ship.
What I'd suggest is verifying sortedness unconditionally and falling back to
`absorb_slice` when the input isn't sorted. Checking costs O(n) comparisons
against the O(n log n) sort you're skipping, so on the 1M row f64 case that's
about a million `<=` comparisons against a 7.3 ms budget. Most of the win
survives, the footgun goes away entirely, and the `should_panic` test turns
into a "falls back correctly" test that passes under any profile.
I care about this more than I normally would for an unchecked precondition
because of who the caller is. The invariant is a plan shape one, that a
`SortExec` sits above `RuntimeStatsExec`. If some later optimizer change moves
or drops that sort, the sketch quietly returns wrong quantiles, and those
become wrong partition boundaries. Silent wrong answers from a plan shape
assumption is a bad failure mode to design in.
## The sortedness invariant itself looks right
I went through this carefully since it's the risky part of the change. Every
`levels[...]` mutation site on main is covered, `merge`, `insert`, and the
three inside `compact_level`. `compact_all` only compacts levels at or over
capacity and consumes no RNG when it no ops, so the "bit identical to insert in
a loop" claim for `absorb` holds up. The merge branch in `compact_level`
maintains the flag correctly, and the conservative `sorted[h] = false` in cross
sketch `merge` is safe.
Two things I'd tighten:
- `absorb_sorted_slice` degrades silently when `sorted[0]` is false on
entry. If you mix it with `insert` or `absorb_slice` on the same sketch,
`merge_sorted` interleaves into an unsorted level 0. It stays correct, since
the flag stays false and compaction sorts, and it self heals after the first
compaction. But the doc's claim that level 0 stays permanently sorted only
holds for a sketch used exclusively through this one method. A sort and set at
the top would make the doc true.
- This PR changes the output of the existing `insert` path. `compact_level`
now merge extends where it used to extend then `sort_unstable`. With ties a
different set of duplicate copies survives. Values and weights are unchanged so
quantiles are identical for any `T` where equal items are interchangeable,
which covers every current use, but the PR reads as purely additive and this
part isn't. Worth a line in the description.
## Smaller
- `absorb_sorted_slice` allocates twice per chunk, once for `to_vec()` and
once for `merge_sorted`'s output, and drops `existing`. At level 0 chunk sizes
across 1M rows that's a lot of small allocations. Already fast at 7.3 ms so not
urgent, but an in place merge would probably widen the gap further.
- `datafusion-functions-aggregate-common` went into `[dependencies]` but is
only used by the bench. Looks like it belongs in `[dev-dependencies]`.
- `ordered-float = "4"` is a raw version rather than `{ workspace = true }`.
It isn't in `[workspace.dependencies]` yet, and we manage versions there.
No concerns on the persona side. The `absorb*` methods are additive on an
existing public type and nothing is wired into `RuntimeStatsExec` yet.
--
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]
