You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by ka...@apache.org on 2026/07/09 05:42:22 UTC
(datafusion) branch improve-compare-in-view-map-v2 created (now eab34560ba)
This is an automated email from the ASF dual-hosted git repository.
Rachelint pushed a change to branch improve-compare-in-view-map-v2
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at eab34560ba Store byte view payloads without views
This branch includes the following new commits:
new eab34560ba Store byte view payloads without views
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: Store byte view payloads without views
Posted by ka...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
Rachelint pushed a commit to branch improve-compare-in-view-map-v2
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit eab34560bad8e6bcc8243199e71bec23c2461bff
Author: kamille <ka...@apache.org>
AuthorDate: Thu Jul 9 13:34:37 2026 +0800
Store byte view payloads without views
---
.../physical-expr-common/src/binary_view_map.rs | 88 +++++++++++++---------
1 file changed, 51 insertions(+), 37 deletions(-)
diff --git a/datafusion/physical-expr-common/src/binary_view_map.rs b/datafusion/physical-expr-common/src/binary_view_map.rs
index 9d4b556393..53b84e7dea 100644
--- a/datafusion/physical-expr-common/src/binary_view_map.rs
+++ b/datafusion/physical-expr-common/src/binary_view_map.rs
@@ -33,7 +33,7 @@ use std::sync::Arc;
/// HashSet optimized for storing string or binary values that can produce that
/// the final set as a `GenericBinaryViewArray` with minimal copies.
#[derive(Debug)]
-pub struct ArrowBytesViewSet(ArrowBytesViewMap<()>);
+pub struct ArrowBytesViewSet(ArrowBytesViewMap<usize>);
impl ArrowBytesViewSet {
pub fn new(output_type: OutputType) -> Self {
@@ -42,10 +42,16 @@ impl ArrowBytesViewSet {
/// Inserts each value from `values` into the set
pub fn insert(&mut self, values: &ArrayRef) {
- fn make_payload_fn(_value: Option<&[u8]>) {}
- fn observe_payload_fn(_payload: ()) {}
- self.0
- .insert_if_new(values, make_payload_fn, observe_payload_fn);
+ let mut next_group_index = self.0.len();
+ self.0.insert_if_new(
+ values,
+ |_value| {
+ let group_index = next_group_index;
+ next_group_index += 1;
+ group_index
+ },
+ |_payload| {},
+ );
}
/// Return the contents of this map and replace it with a new empty map with
@@ -108,8 +114,7 @@ impl ArrowBytesViewSet {
/// 2. Retains the insertion order of entries in the final array. The values are
/// in the same order as they were inserted.
///
-/// Note this structure can be used as a `HashSet` by specifying the value type
-/// as `()`, as is done by [`ArrowBytesViewSet`].
+/// [`ArrowBytesViewSet`] wraps this structure to implement set semantics.
///
/// This map is used by the special `COUNT DISTINCT` aggregate function to
/// store the distinct values, and by the `GROUP BY` operator to store
@@ -117,9 +122,25 @@ impl ArrowBytesViewSet {
/// Max size of the in-progress buffer before flushing to completed buffers
const BYTE_VIEW_MAX_BLOCK_SIZE: usize = 2 * 1024 * 1024;
+/// Payload stored in [`ArrowBytesViewMap`].
+///
+/// The payload must expose the logical group index so the map can fetch the
+/// corresponding stored view from [`ArrowBytesViewMap::views`].
+pub trait ByteViewMapPayload: Debug + PartialEq + Eq + Clone + Copy + Default {
+ /// Returns the logical group index for this payload.
+ fn group_index(self) -> usize;
+}
+
+impl ByteViewMapPayload for usize {
+ #[inline]
+ fn group_index(self) -> usize {
+ self
+ }
+}
+
pub struct ArrowBytesViewMap<V>
where
- V: Debug + PartialEq + Eq + Clone + Copy + Default,
+ V: ByteViewMapPayload,
{
/// Should the output be StringView or BinaryView?
output_type: OutputType,
@@ -152,7 +173,7 @@ const INITIAL_MAP_CAPACITY: usize = 512;
impl<V> ArrowBytesViewMap<V>
where
- V: Debug + PartialEq + Eq + Clone + Copy + Default,
+ V: ByteViewMapPayload,
{
pub fn new(output_type: OutputType) -> Self {
Self {
@@ -305,20 +326,22 @@ where
return false;
}
+ let stored_view = self.views[header.payload.group_index()];
+
// Fast path: inline strings can be compared directly
if len <= 12 {
- return header.view == view_u128;
+ return stored_view == view_u128;
}
// For larger strings: first compare the 4-byte prefix
- let stored_prefix = (header.view >> 32) as u32;
+ let stored_prefix = (stored_view >> 32) as u32;
let input_prefix = (view_u128 >> 32) as u32;
if stored_prefix != input_prefix {
return false;
}
// Prefix matched - compare full bytes
- let byte_view = ByteView::from(header.view);
+ let byte_view = ByteView::from(stored_view);
let stored_len = byte_view.length as usize;
let buffer_index = byte_view.buffer_index as usize;
let offset = byte_view.offset as usize;
@@ -339,7 +362,7 @@ where
payload
} else {
// no existing value, make a new one
- let (new_view, payload) = if len <= 12 {
+ let payload = if len <= 12 {
// Inline path: bytes are already packed in view_u128.
// The inline ByteView format is [len:u32 LE][data:12 bytes zero-padded],
// so extracting bytes from the u128 avoids a round-trip through
@@ -352,20 +375,16 @@ where
//
// SAFETY: view_u128 was a valid view, and the enclosing `len <= 12`
// ensures it is inline
- let new_view = unsafe { self.append_inline_view(view_u128) };
- (new_view, payload)
+ unsafe { self.append_inline_view(view_u128) };
+ payload
} else {
let value: &[u8] = values.value(i).as_ref();
let payload = make_payload_fn(Some(value));
- let new_view = self.append_value(value);
- (new_view, payload)
+ self.append_value(value);
+ payload
};
- let new_header = Entry {
- view: new_view,
- hash,
- payload,
- };
+ let new_header = Entry { hash, payload };
self.map
.insert_accounted(new_header, |h| h.hash, &mut self.map_size);
@@ -487,7 +506,7 @@ where
impl<V> Debug for ArrowBytesViewMap<V>
where
- V: Debug + PartialEq + Eq + Clone + Copy + Default,
+ V: ByteViewMapPayload,
{
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("ArrowBytesMap")
@@ -502,24 +521,14 @@ where
}
/// Entry in the hash table -- see [`ArrowBytesViewMap`] for more details
-///
-/// Stores the view pointing to our internal buffers, eliminating the need
-/// for a separate builder index. For inline strings (<=12 bytes), the view
-/// contains the entire value. For out-of-line strings, the view contains
-/// buffer_index and offset pointing directly to our storage.
#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
struct Entry<V>
where
- V: Debug + PartialEq + Eq + Clone + Copy + Default,
+ V: ByteViewMapPayload,
{
- /// The u128 view pointing to our internal buffers. For inline strings,
- /// this contains the complete value. For larger strings, this contains
- /// the buffer_index/offset into our completed/in_progress buffers.
- view: u128,
-
hash: u64,
- /// value stored by the entry
+ /// Value stored by the entry.
payload: V,
}
@@ -717,8 +726,13 @@ mod tests {
#[derive(Debug, PartialEq, Eq, Default, Clone, Copy)]
struct TestPayload {
- // store the string value to check against input
- index: usize, // store the index of the string (each new string gets the next sequential input)
+ index: usize,
+ }
+
+ impl ByteViewMapPayload for TestPayload {
+ fn group_index(self) -> usize {
+ self.index
+ }
}
/// Wraps an [`ArrowBytesViewMap`], validating its invariants
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org