coderfender opened a new issue, #2783: URL: https://github.com/apache/datafusion-ballista/issues/2783
**Is your feature request related to a problem or challenge? Please describe what you are trying to do.** #1916 and #2671 collect per-column statistics on shuffle writes: null counts, plus a HyperLogLog distinct-count sketch on hash-partitioning keys, merged per stage and surfaced to AQE through `ExchangeExec`. The next sketch I'd like to add is **top-k / heavy hitters** on the same key columns, so AQE can tell *which keys* cause skew, not only *which partitions* are large (`OptimizeSkewedJoinRule` sees partition sizes only today). Ballista currently writes its sketches itself: `hll.rs` (~350 lines) and `kll.rs` (#2180, ~1,550 lines, ported from DataSketches C++). Before adding a third, I'd like feedback on whether to keep porting or to depend on the upstream library. **Describe the solution you'd like** Add [`apache/datasketches-rust`](https://github.com/apache/datasketches-rust) (the `datasketches` crate, latest `0.6.0`) with only the features we use, starting with `frequencies`: - Top-k via `FrequentItemsSketch<u64>` (Misra-Gries; mergeable; serializable; error at most 3.5 / map_size of the rows) on the same key columns HLL sketches, keyed by the value hash HLL already computes, so there is no extra hashing on the write path. It travels as a new `SketchType` in the existing `ColumnSketch` slot of `TaskColumnStats`, and is on by default under `ballista.shuffle.collect_distinct_counts`. About the dependency: it is an ASF project, Apache-2.0, has no runtime dependencies, and puts every sketch behind its own feature flag. Its serialization is compatible with the Java/C++/Python DataSketches libraries. What else the same crate would give the stats feeder later: - **theta**: distinct counts that support intersection, to estimate how many join keys the two sides actually share instead of assuming containment (inner/semi/anti join estimates). - **tuple**: theta with a per-key summary such as a row count, to estimate join output size including fan-out (the kind of underestimate behind #2662). - **hll / cpc**: compact distinct-count sketches (HLL_4 is 4 bits per register; CPC is smaller still at the same accuracy), which would shrink the per-task status payload compared with `hll.rs`'s fixed 1 byte per register. - **kll / req / tdigest**: quantiles, so `kll.rs` could move onto the library. **Describe alternatives you've considered** 1. **Keep writing our own:** a small Misra-Gries `topk.rs`, as with `hll.rs` and `kll.rs`. No new dependency, but more code to maintain and test. 2. **Reuse DataFusion's `approx_top_k`** once apache/datafusion#20968 lands (for apache/datafusion#20967), if its sketch is exposed publicly. **Additional context** Related: #1827, #1916, #2671, #2662. -- 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]
