SubhamSinghal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3683241123
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,394 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
+/// bytes, capped at `k` distinct keys. Each key's `Vec<TieEntry>` holds
+/// every row seen at that ob value, one entry per contributing source
+/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<TieEntry>>,
+ /// Cached admission boundary: the largest tracked ob value once
+ /// `groups` is full. A `HashMap` is unordered, so finding it otherwise
+ /// costs an O(K) scan of the keys on *every* new distinct ob value —
+ /// O(N·K) overall on mostly-distinct input. Caching makes the common
+ /// "new ob is worse than the boundary → drop" path O(1); the O(K) scan
+ /// is paid only when the cache is stale (`None`) — after a fill or an
+ /// eviction changes the key set.
+ max_key: Option<Vec<u8>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead =
+ self.groups.capacity() * (size_of::<Vec<u8>>() +
size_of::<Vec<TieEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<TieEntry>()
+ + entries
+ .iter()
+ .map(|e| {
+ e.row_indices.capacity() * size_of::<u32>() +
e.batch_bytes
Review Comment:
Fixed in 8e97623c98969a34d9991c4920e479985b0b89e8. Using `RecordBatchStore`
as suggested.
--
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]
