This is an automated email from the ASF dual-hosted git repository.

tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git


The following commit(s) were added to refs/heads/main by this push:
     new 84294f0  feat(theta,tuple): serialize union results directly (#336)
84294f0 is described below

commit 84294f089fdbf1f12f5bc8b58453b7c4ead13810
Author: tison <[email protected]>
AuthorDate: Tue Nov 10 15:53:27 2026 +0800

    feat(theta,tuple): serialize union results directly (#336)
    
    Co-authored-by: Nash Aschenbath <[email protected]>
    Co-authored-by: Claude Opus 5.5 <[email protected]>
---
 CHANGELOG.md                                       |   1 +
 benchmarks/theta/mod.rs                            |   2 +
 benchmarks/theta/serde.rs                          |  64 +++++++
 benchmarks/tuple/mod.rs                            |   2 +
 benchmarks/tuple/serde.rs                          | 188 +++++++++++++++++++
 datasketches/src/thetafamily/common/mod.rs         |  12 ++
 .../src/thetafamily/common/sketch_state.rs         |  13 ++
 datasketches/src/thetafamily/common/union.rs       |  36 +++-
 .../src/thetafamily/theta/serialization.rs         |  49 ++++-
 datasketches/src/thetafamily/theta/sketch.rs       |  50 +----
 datasketches/src/thetafamily/theta/union.rs        |  11 ++
 .../src/thetafamily/tuple/serialization.rs         |  56 ++++++
 datasketches/src/thetafamily/tuple/sketch.rs       |  54 +-----
 datasketches/src/thetafamily/tuple/union.rs        |  40 ++++
 tests-integration/tests/serde_tests/theta.rs       |  66 +++++++
 tests-integration/tests/serde_tests/tuple.rs       | 205 +++++++++++++++++++++
 16 files changed, 738 insertions(+), 111 deletions(-)

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 9f68d7e..fe7a6c4 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -9,6 +9,7 @@ All significant changes to this project will be documented in 
this file.
 * Use serial version 2 for new `CountMinSketch` instances, enabling 
cross-language interchange with the documented input encodings. New sketches 
support `1..=127` rows and require a version 2 reader. Existing version 1 data 
remains readable and updatable, but must be rebuilt from source items to merge 
with new sketches.
 * Add `CpcUnion::serialize`, which produces the same bytes as 
`to_sketch().serialize()` and can be faster.
 * Add `HllUnion::serialize` to serialize union results directly.
+* Add `ThetaUnion::serialize` and `TupleUnion::serialize` to serialize ordered 
or unordered union results directly in their compact binary formats. Tuple 
summaries are serialized without cloning, avoiding per-entry allocations for 
heap-backed summaries.
 * Add `XorFilter` and `XorFilterBuilder` behind the `xor` feature for 
immutable membership queries on values or precomputed hashes. Filters support 
8-, 16-, and 32-bit fingerprints and can be serialized for later queries.
 
 ### Improvements
diff --git a/benchmarks/theta/mod.rs b/benchmarks/theta/mod.rs
index 4839176..32c8b7f 100644
--- a/benchmarks/theta/mod.rs
+++ b/benchmarks/theta/mod.rs
@@ -15,8 +15,10 @@
 // specific language governing permissions and limitations
 // under the License.
 
+mod serde;
 mod update;
 
 pub fn register(runner: &mut benchmarks::Runner) {
+    serde::register(runner);
     update::register(runner);
 }
diff --git a/benchmarks/theta/serde.rs b/benchmarks/theta/serde.rs
new file mode 100644
index 0000000..89d2e59
--- /dev/null
+++ b/benchmarks/theta/serde.rs
@@ -0,0 +1,64 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::hint::black_box;
+
+use benchmarks::Bencher;
+use benchmarks::Runner;
+use datasketches::theta::ThetaSketchBuilder;
+use datasketches::theta::ThetaUnion;
+use datasketches::theta::ThetaUnionBuilder;
+
+fn serialize_union(bencher: Bencher, rows: u64, ordered: bool, direct: bool) {
+    let union = union(rows);
+    if direct {
+        bencher.bench_local(|| black_box(&union).serialize(ordered));
+    } else {
+        bencher.bench_local(|| 
black_box(&union).to_sketch(ordered).serialize());
+    }
+}
+
+fn union(rows: u64) -> ThetaUnion {
+    let mut sketch = ThetaSketchBuilder::default().lg_k(14).build().unwrap();
+    for value in 0..rows {
+        sketch.update(value);
+    }
+    let mut union = ThetaUnionBuilder::default().lg_k(12).build().unwrap();
+    union.update(&sketch).unwrap();
+    union
+}
+
+pub fn register(runner: &mut Runner) {
+    // Reuse each union for repeated serialization, including fixture 
construction in timing.
+    for (rows, rounds) in [(40, 1_000_000), (8_000, 10_000)] {
+        for ordered in [false, true] {
+            let order = if ordered { "ordered" } else { "unordered" };
+            runner.compare(
+                &format!("theta::serde::{order}/{rows}"),
+                rounds,
+                &[
+                    ("via_compact", &|b| {
+                        serialize_union(b, rows, ordered, false);
+                    }),
+                    ("direct", &|b| {
+                        serialize_union(b, rows, ordered, true);
+                    }),
+                ],
+            );
+        }
+    }
+}
diff --git a/benchmarks/tuple/mod.rs b/benchmarks/tuple/mod.rs
index 4839176..32c8b7f 100644
--- a/benchmarks/tuple/mod.rs
+++ b/benchmarks/tuple/mod.rs
@@ -15,8 +15,10 @@
 // specific language governing permissions and limitations
 // under the License.
 
+mod serde;
 mod update;
 
 pub fn register(runner: &mut benchmarks::Runner) {
+    serde::register(runner);
     update::register(runner);
 }
diff --git a/benchmarks/tuple/serde.rs b/benchmarks/tuple/serde.rs
new file mode 100644
index 0000000..700675b
--- /dev/null
+++ b/benchmarks/tuple/serde.rs
@@ -0,0 +1,188 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::hint::black_box;
+
+use benchmarks::Bencher;
+use benchmarks::Runner;
+use datasketches::codec::SketchBytes;
+use datasketches::codec::SketchSlice;
+use datasketches::error::Error;
+use datasketches::tuple::DefaultUnionPolicy;
+use datasketches::tuple::DefaultUpdatePolicy;
+use datasketches::tuple::SummaryCombinePolicy;
+use datasketches::tuple::SummaryPolicy;
+use datasketches::tuple::SummaryUpdatePolicy;
+use datasketches::tuple::TupleSketchBuilder;
+use datasketches::tuple::TupleSummaryValue;
+use datasketches::tuple::TupleUnion;
+use datasketches::tuple::TupleUnionBuilder;
+
+fn u64_union(rows: u64, lg_k: u8) -> TupleUnion<DefaultUnionPolicy<u64>> {
+    let mut sketch = 
TupleSketchBuilder::new(DefaultUpdatePolicy::<u64>::default())
+        .lg_k(lg_k)
+        .build()
+        .unwrap();
+    for value in 0..rows {
+        sketch.update(value, 1);
+    }
+    let mut union = 
TupleUnionBuilder::new(DefaultUnionPolicy::<u64>::default())
+        .lg_k(lg_k)
+        .build()
+        .unwrap();
+    union.update(&sketch).unwrap();
+    union
+}
+
+fn serialize_union<const ORDERED: bool>(bencher: Bencher, rows: u64, lg_k: u8) 
{
+    let union = u64_union(rows, lg_k);
+    bencher.bench_local(|| black_box(&union).serialize(ORDERED));
+}
+
+fn serialize_union_via_sketch<const ORDERED: bool>(bencher: Bencher, rows: 
u64, lg_k: u8) {
+    let union = u64_union(rows, lg_k);
+    bencher.bench_local(|| black_box(&union).to_sketch(ORDERED).serialize());
+}
+
+/// Heap-backed summary holding a few short labels per key.
+#[derive(Clone, Default)]
+struct Labels(Vec<String>);
+
+impl TupleSummaryValue for Labels {
+    fn serialize_size(&self) -> usize {
+        4 + self.0.iter().map(|label| 4 + label.len()).sum::<usize>()
+    }
+
+    fn serialize_value(&self, bytes: &mut SketchBytes) {
+        bytes.write_u32_le(self.0.len() as u32);
+        for label in &self.0 {
+            bytes.write_u32_le(label.len() as u32);
+            bytes.write(label.as_bytes());
+        }
+    }
+
+    fn deserialize_value(_cursor: &mut SketchSlice<'_>) -> Result<Self, Error> 
{
+        unimplemented!("only serialization is benchmarked")
+    }
+}
+
+#[derive(Clone, Copy)]
+struct LabelsPolicy;
+
+impl SummaryPolicy for LabelsPolicy {
+    type Summary = Labels;
+
+    fn create(&self) -> Self::Summary {
+        Labels::default()
+    }
+}
+
+impl SummaryUpdatePolicy<u64> for LabelsPolicy {
+    fn update(&self, summary: &mut Self::Summary, value: u64) {
+        for i in 0..4 {
+            summary.0.push(format!("label-{value:08}-{i}"));
+        }
+    }
+}
+
+impl SummaryCombinePolicy for LabelsPolicy {
+    fn combine(&self, summary: &mut Self::Summary, other: &Self::Summary) {
+        summary.0.extend(other.0.iter().cloned());
+    }
+}
+
+fn labels_union(rows: u64, lg_k: u8) -> TupleUnion<LabelsPolicy> {
+    let mut sketch = TupleSketchBuilder::new(LabelsPolicy)
+        .lg_k(lg_k)
+        .build()
+        .unwrap();
+    for value in 0..rows {
+        sketch.update(value, value);
+    }
+    let mut union = TupleUnionBuilder::new(LabelsPolicy)
+        .lg_k(lg_k)
+        .build()
+        .unwrap();
+    union.update(&sketch).unwrap();
+    union
+}
+
+fn serialize_labels_union<const ORDERED: bool>(bencher: Bencher, rows: u64, 
lg_k: u8) {
+    let union = labels_union(rows, lg_k);
+    bencher.bench_local(|| black_box(&union).serialize(ORDERED));
+}
+
+fn serialize_labels_union_via_sketch<const ORDERED: bool>(bencher: Bencher, 
rows: u64, lg_k: u8) {
+    let union = labels_union(rows, lg_k);
+    bencher.bench_local(|| black_box(&union).to_sketch(ORDERED).serialize());
+}
+
+pub fn register(runner: &mut Runner) {
+    // Reuse each union for repeated serialization, including fixture 
construction in timing.
+    // Cover exact results and estimation results with different retained 
sizes.
+    for (rows, lg_k, u64_rounds, labels_rounds) in [
+        (0, 12, 10_000_000, 10_000_000),
+        (4, 12, 2_000_000, 500_000),
+        (100, 12, 300_000, 20_000),
+        (1_000, 12, 30_000, 2_000),
+        (80_000, 8, 100_000, 6_000),
+        (80_000, 12, 5_000, 500),
+        (80_000, 16, 250, 20),
+    ] {
+        register_order::<false>(runner, rows, lg_k, u64_rounds, labels_rounds);
+        register_order::<true>(runner, rows, lg_k, u64_rounds, labels_rounds);
+    }
+}
+
+fn register_order<const ORDERED: bool>(
+    runner: &mut Runner,
+    rows: u64,
+    lg_k: u8,
+    u64_rounds: usize,
+    labels_rounds: usize,
+) {
+    let size = if lg_k == 12 {
+        rows.to_string()
+    } else {
+        format!("{rows}/lg_k={lg_k}")
+    };
+    let order = if ORDERED { "ordered" } else { "unordered" };
+    runner.compare(
+        &format!("tuple::serde::u64::{order}/{size}"),
+        u64_rounds,
+        &[
+            ("via_compact_sketch", &|bencher| {
+                serialize_union_via_sketch::<ORDERED>(bencher, rows, lg_k)
+            }),
+            ("direct", &|bencher| {
+                serialize_union::<ORDERED>(bencher, rows, lg_k)
+            }),
+        ],
+    );
+    runner.compare(
+        &format!("tuple::serde::labels::{order}/{size}"),
+        labels_rounds,
+        &[
+            ("via_compact_sketch", &|bencher| {
+                serialize_labels_union_via_sketch::<ORDERED>(bencher, rows, 
lg_k)
+            }),
+            ("direct", &|bencher| {
+                serialize_labels_union::<ORDERED>(bencher, rows, lg_k)
+            }),
+        ],
+    );
+}
diff --git a/datasketches/src/thetafamily/common/mod.rs 
b/datasketches/src/thetafamily/common/mod.rs
index dbc273e..e1a9ae8 100644
--- a/datasketches/src/thetafamily/common/mod.rs
+++ b/datasketches/src/thetafamily/common/mod.rs
@@ -33,6 +33,18 @@ pub(super) trait SketchEntry {
     fn hash(&self) -> u64;
 }
 
+impl SketchEntry for u64 {
+    fn hash(&self) -> u64 {
+        *self
+    }
+}
+
+impl<E: SketchEntry> SketchEntry for &E {
+    fn hash(&self) -> u64 {
+        E::hash(self)
+    }
+}
+
 pub(super) trait KeySketch: Copy {
     fn metadata(self) -> sketch_state::ThetaFamilySketchMetadata;
 
diff --git a/datasketches/src/thetafamily/common/sketch_state.rs 
b/datasketches/src/thetafamily/common/sketch_state.rs
index d59f74f..44928c0 100644
--- a/datasketches/src/thetafamily/common/sketch_state.rs
+++ b/datasketches/src/thetafamily/common/sketch_state.rs
@@ -82,6 +82,19 @@ impl<E> CompactSketchState<E> {
         matches!(self, Self::NonEmpty { theta, .. } if *theta < MAX_THETA)
     }
 
+    /// Returns the preamble size in 8-byte words for uncompressed compact 
Theta and Tuple images.
+    pub fn uncompressed_preamble_longs(&self) -> u8 {
+        if self.is_empty() {
+            1
+        } else if self.is_estimation_mode() {
+            3
+        } else if self.retained_entries().len() == 1 {
+            1
+        } else {
+            2
+        }
+    }
+
     pub fn seed_hash(&self) -> u16 {
         match self {
             Self::Empty { seed_hash } | Self::NonEmpty { seed_hash, .. } => 
*seed_hash,
diff --git a/datasketches/src/thetafamily/common/union.rs 
b/datasketches/src/thetafamily/common/union.rs
index 4ad3b46..b9e5d1d 100644
--- a/datasketches/src/thetafamily/common/union.rs
+++ b/datasketches/src/thetafamily/common/union.rs
@@ -113,21 +113,37 @@ where
     where
         E: Clone,
     {
-        let Some(result_theta) = self.result_theta else {
+        let Some(theta) = self.result_theta else {
             return CompactSketchState::empty(self.table.seed_hash());
         };
+        let entries = self.retained_entries(theta).cloned().collect();
+        self.finish_compaction(entries, theta, ordered)
+    }
 
-        let mut theta = result_theta.min(self.table.retention_theta());
-        let mut retained_entries = if result_theta >= 
self.table.retention_theta() {
-            self.table.iter_entries().cloned().collect::<Vec<_>>()
-        } else {
-            self.table
-                .iter_entries()
-                .filter(|entry| entry.hash() < theta)
-                .cloned()
-                .collect::<Vec<_>>()
+    /// Returns the union as canonical compact-sketch state that borrows the 
retained entries.
+    #[cfg(feature = "tuple")]
+    pub fn to_borrowed_compact_sketch_state(&self, ordered: bool) -> 
CompactSketchState<&E> {
+        let Some(theta) = self.result_theta else {
+            return CompactSketchState::empty(self.table.seed_hash());
         };
+        let entries = self.retained_entries(theta).collect();
+        self.finish_compaction(entries, theta, ordered)
+    }
 
+    fn retained_entries(&self, theta: u64) -> impl Iterator<Item = &E> {
+        let all_retained = theta >= self.table.retention_theta();
+        self.table
+            .iter_entries()
+            .filter(move |entry| all_retained || entry.hash() < theta)
+    }
+
+    fn finish_compaction<T: SketchEntry>(
+        &self,
+        mut retained_entries: Vec<T>,
+        result_theta: u64,
+        ordered: bool,
+    ) -> CompactSketchState<T> {
+        let mut theta = result_theta.min(self.table.retention_theta());
         let nominal_num = 1usize << self.table.lg_nom_size();
         if retained_entries.len() > nominal_num {
             let (_, kth, _) =
diff --git a/datasketches/src/thetafamily/theta/serialization.rs 
b/datasketches/src/thetafamily/theta/serialization.rs
index d10917f..b25edcf 100644
--- a/datasketches/src/thetafamily/theta/serialization.rs
+++ b/datasketches/src/thetafamily/theta/serialization.rs
@@ -15,7 +15,15 @@
 // specific language governing permissions and limitations
 // under the License.
 
-//! Binary serialization format constants for Theta sketches.
+//! Binary serialization for compact Theta sketches.
+
+use crate::codec::SketchBytes;
+use crate::codec::family::Family;
+use crate::thetacommon::SketchEntry;
+use crate::thetacommon::constants::FLAGS_IS_COMPACT;
+use crate::thetacommon::constants::FLAGS_IS_ORDERED;
+use crate::thetacommon::constants::FLAGS_IS_READ_ONLY;
+use crate::thetacommon::sketch_state::CompactSketchState;
 
 pub const UNCOMPRESSED_SERIAL_VERSION: u8 = 3;
 pub const COMPRESSED_SERIAL_VERSION: u8 = 4;
@@ -26,3 +34,42 @@ pub const EMPTY_SKETCH_BYTES: [u8; 8] = [1, 3, 3, 0, 0, 
0x1e, 0, 0];
 pub const V2_PREAMBLE_EMPTY: u8 = 1;
 pub const V2_PREAMBLE_PRECISE: u8 = 2;
 pub const V2_PREAMBLE_ESTIMATE: u8 = 3;
+
+pub(super) fn serialize_compact_uncompressed<E: SketchEntry>(
+    state: &CompactSketchState<E>,
+) -> Vec<u8> {
+    if state.is_empty() {
+        return EMPTY_SKETCH_BYTES.to_vec();
+    }
+
+    let entries = state.retained_entries();
+    let pre_longs = state.uncompressed_preamble_longs();
+    let mut bytes = SketchBytes::with_capacity((usize::from(pre_longs) + 
entries.len()) * 8);
+    bytes.write_u8(pre_longs);
+    bytes.write_u8(UNCOMPRESSED_SERIAL_VERSION);
+    bytes.write_u8(Family::THETA.id);
+    bytes.write_u16_be(0); // unused for compact
+
+    let mut flags = 0u8;
+    flags |= FLAGS_IS_READ_ONLY;
+    flags |= FLAGS_IS_COMPACT;
+    if state.is_ordered() {
+        flags |= FLAGS_IS_ORDERED;
+    }
+    bytes.write_u8(flags);
+
+    bytes.write_u16_le(state.seed_hash());
+
+    if pre_longs > 1 {
+        bytes.write_u32_le(entries.len() as u32);
+        // Unused by compact sketches; matches datasketches-java and 
datasketches-cpp.
+        bytes.write_u32_be(0);
+    }
+    if state.is_estimation_mode() {
+        bytes.write_u64_le(state.theta());
+    }
+    for entry in entries {
+        bytes.write_u64_le(entry.hash());
+    }
+    bytes.into_bytes()
+}
diff --git a/datasketches/src/thetafamily/theta/sketch.rs 
b/datasketches/src/thetafamily/theta/sketch.rs
index e7d0b9b..71105cf 100644
--- a/datasketches/src/thetafamily/theta/sketch.rs
+++ b/datasketches/src/thetafamily/theta/sketch.rs
@@ -531,18 +531,6 @@ impl CompactThetaSketch {
         .expect("compact theta should always be valid")
     }
 
-    fn preamble_longs(&self, compressed: bool) -> u8 {
-        if compressed {
-            if self.is_estimation_mode() { 2 } else { 1 }
-        } else if self.is_estimation_mode() {
-            3
-        } else if self.num_retained() == 1 {
-            1
-        } else {
-            2
-        }
-    }
-
     /// Serializes this sketch in compressed form if applicable.
     ///
     /// The serialized data can be read by other DataSketches implementations.
@@ -568,46 +556,12 @@ impl CompactThetaSketch {
     ///
     /// Empty sketches serialize with a zero seed hash.
     pub fn serialize(&self) -> Vec<u8> {
-        if self.is_empty() {
-            return serialization::EMPTY_SKETCH_BYTES.to_vec();
-        }
-
-        let retained_hashes = self.retained_hashes();
-        let mut bytes = SketchBytes::with_capacity(64 + retained_hashes.len() 
* 8);
-
-        let pre_longs = self.preamble_longs(false);
-        bytes.write_u8(pre_longs);
-        bytes.write_u8(serialization::UNCOMPRESSED_SERIAL_VERSION);
-        bytes.write_u8(Family::THETA.id);
-        bytes.write_u16_be(0); // unused for compact
-
-        let mut flags = 0u8;
-        flags |= FLAGS_IS_READ_ONLY;
-        flags |= FLAGS_IS_COMPACT;
-        if self.is_ordered() {
-            flags |= FLAGS_IS_ORDERED;
-        }
-        bytes.write_u8(flags);
-
-        bytes.write_u16_le(self.seed_hash());
-
-        if pre_longs > 1 {
-            bytes.write_u32_le(retained_hashes.len() as u32);
-            // Unused by compact sketches; matches datasketches-java and 
datasketches-cpp.
-            bytes.write_u32_be(0);
-        }
-        if self.is_estimation_mode() {
-            bytes.write_u64_le(self.theta64());
-        }
-        for hash in retained_hashes {
-            bytes.write_u64_le(*hash);
-        }
-        bytes.into_bytes()
+        serialization::serialize_compact_uncompressed(&self.compact_state)
     }
 
     fn serialize_v4(&self) -> Vec<u8> {
         let retained_hashes = self.retained_hashes();
-        let pre_longs = self.preamble_longs(true);
+        let pre_longs = if self.is_estimation_mode() { 2u8 } else { 1u8 };
         let entry_bits = Self::compute_entry_bits(retained_hashes);
         let num_entries_bytes = Self::num_entries_bytes(retained_hashes.len());
 
diff --git a/datasketches/src/thetafamily/theta/union.rs 
b/datasketches/src/thetafamily/theta/union.rs
index 1b26d7a..a8f21fa 100644
--- a/datasketches/src/thetafamily/theta/union.rs
+++ b/datasketches/src/thetafamily/theta/union.rs
@@ -21,6 +21,7 @@ use crate::hash::DEFAULT_UPDATE_SEED;
 use crate::theta::CompactThetaSketch;
 use crate::theta::ThetaSketchView;
 use crate::theta::hash_table::ThetaEntry;
+use crate::theta::serialization;
 use crate::thetacommon::constants::DEFAULT_LG_K;
 use crate::thetacommon::union::UnionMergePolicy;
 use crate::thetacommon::union::UnionState;
@@ -59,6 +60,16 @@ impl ThetaUnion {
         CompactThetaSketch::from_compact_state(compact_state)
     }
 
+    /// Serializes this union result into the uncompressed compact Theta 
format.
+    ///
+    /// Produces the same bytes as `self.to_sketch(ordered).serialize()`. When 
`ordered` is `true`,
+    /// retained hashes are sorted. Otherwise they may be unordered; empty 
results and exact
+    /// singletons always use their canonical encoding.
+    pub fn serialize(&self, ordered: bool) -> Vec<u8> {
+        let state = self.state.to_compact_sketch_state(ordered);
+        serialization::serialize_compact_uncompressed(&state)
+    }
+
     /// Resets the union to its empty state.
     pub fn reset(&mut self) {
         self.state.reset();
diff --git a/datasketches/src/thetafamily/tuple/serialization.rs 
b/datasketches/src/thetafamily/tuple/serialization.rs
index cc208e0..1e7b916 100644
--- a/datasketches/src/thetafamily/tuple/serialization.rs
+++ b/datasketches/src/thetafamily/tuple/serialization.rs
@@ -25,10 +25,18 @@
 //! type is opaque to the sketch, (de)serialization of summaries is delegated 
to the summary type
 //! itself via the [`TupleSummaryValue`] trait, mirroring `FrequentItemValue`.
 
+use std::borrow::Borrow;
+
 use crate::codec::SketchBytes;
 use crate::codec::SketchSlice;
 use crate::codec::assert::insufficient_data;
+use crate::codec::family::Family;
 use crate::error::Error;
+use crate::thetacommon::constants::FLAGS_IS_COMPACT;
+use crate::thetacommon::constants::FLAGS_IS_ORDERED;
+use crate::thetacommon::constants::FLAGS_IS_READ_ONLY;
+use crate::thetacommon::sketch_state::CompactSketchState;
+use crate::tuple::hash_table::TupleEntry;
 
 /// Current serial version written by this implementation.
 pub const SERIAL_VERSION: u8 = 3;
@@ -43,6 +51,54 @@ pub const SKETCH_TYPE_LEGACY: u8 = 5;
 /// Canonical empty compact image, independent of the configured seed and 
summary type.
 pub const EMPTY_SKETCH_BYTES: [u8; 8] = [1, 3, 9, 1, 0, 0x1e, 0, 0];
 
+/// Serializes compact Tuple state whose retained entries are owned or 
borrowed.
+pub(super) fn serialize_compact_uncompressed<S, E>(compact_state: 
&CompactSketchState<E>) -> Vec<u8>
+where
+    S: TupleSummaryValue,
+    E: Borrow<TupleEntry<S>>,
+{
+    if compact_state.is_empty() {
+        return EMPTY_SKETCH_BYTES.to_vec();
+    }
+
+    let retained_entries = compact_state.retained_entries();
+    let is_estimation_mode = compact_state.is_estimation_mode();
+    let pre_longs = compact_state.uncompressed_preamble_longs();
+    let entries_size: usize = retained_entries
+        .iter()
+        .map(|entry| 8 + entry.borrow().summary().serialize_size())
+        .sum();
+    let mut bytes = SketchBytes::with_capacity(8 * pre_longs as usize + 
entries_size);
+
+    bytes.write_u8(pre_longs);
+    bytes.write_u8(SERIAL_VERSION);
+    bytes.write_u8(Family::TUPLE.id);
+    bytes.write_u8(SKETCH_TYPE);
+    bytes.write_u8(0); // unused
+
+    let mut flags = FLAGS_IS_READ_ONLY | FLAGS_IS_COMPACT;
+    if compact_state.is_ordered() {
+        flags |= FLAGS_IS_ORDERED;
+    }
+    bytes.write_u8(flags);
+    bytes.write_u16_le(compact_state.seed_hash());
+
+    if pre_longs > 1 {
+        bytes.write_u32_le(retained_entries.len() as u32);
+        bytes.write_u32_le(0); // unused
+    }
+    if is_estimation_mode {
+        bytes.write_u64_le(compact_state.theta());
+    }
+
+    for entry in retained_entries {
+        let entry = entry.borrow();
+        bytes.write_u64_le(entry.hash());
+        entry.summary().serialize_value(&mut bytes);
+    }
+    bytes.into_bytes()
+}
+
 /// Trait for values that can be stored as Tuple sketch summaries.
 ///
 /// Implement this trait for a summary type to make it (de)serializable by
diff --git a/datasketches/src/thetafamily/tuple/sketch.rs 
b/datasketches/src/thetafamily/tuple/sketch.rs
index 37bd946..0cd368b 100644
--- a/datasketches/src/thetafamily/tuple/sketch.rs
+++ b/datasketches/src/thetafamily/tuple/sketch.rs
@@ -25,7 +25,6 @@
 use std::hash::Hash;
 use std::slice;
 
-use crate::codec::SketchBytes;
 use crate::codec::SketchSlice;
 use crate::codec::assert::ensure_preamble_longs_in_range;
 use crate::codec::assert::insufficient_data;
@@ -41,10 +40,8 @@ use crate::thetacommon::EntrySketch;
 use crate::thetacommon::KeySketch;
 use crate::thetacommon::binomial_bounds;
 use crate::thetacommon::constants::DEFAULT_LG_K;
-use crate::thetacommon::constants::FLAGS_IS_COMPACT;
 use crate::thetacommon::constants::FLAGS_IS_EMPTY;
 use crate::thetacommon::constants::FLAGS_IS_ORDERED;
-use crate::thetacommon::constants::FLAGS_IS_READ_ONLY;
 use crate::thetacommon::constants::MAX_THETA;
 use crate::thetacommon::hash_table::SketchHashTableIter;
 use crate::thetacommon::sketch_state::CompactSketchState;
@@ -53,12 +50,12 @@ use crate::tuple::hash_table::TupleEntry;
 use crate::tuple::hash_table::TupleHashTable;
 use crate::tuple::policy::SummaryPolicy;
 use crate::tuple::policy::SummaryUpdatePolicy;
-use crate::tuple::serialization::EMPTY_SKETCH_BYTES;
 use crate::tuple::serialization::SERIAL_VERSION;
 use crate::tuple::serialization::SERIAL_VERSION_LEGACY;
 use crate::tuple::serialization::SKETCH_TYPE;
 use crate::tuple::serialization::SKETCH_TYPE_LEGACY;
 use crate::tuple::serialization::TupleSummaryValue;
+use crate::tuple::serialization::serialize_compact_uncompressed;
 
 /// Read-only view of a mutable or compact Tuple sketch.
 ///
@@ -548,16 +545,6 @@ impl<S> CompactTupleSketch<S> {
         self.compact_state.retained_entries_capacity() * 
size_of::<TupleEntry<S>>()
     }
 
-    fn preamble_longs(&self) -> u8 {
-        if self.is_estimation_mode() {
-            3
-        } else if self.num_retained() == 1 {
-            1
-        } else {
-            2
-        }
-    }
-
     /// Serializes this sketch into the compact Tuple binary format.
     ///
     /// The serialized data can be read by other DataSketches implementations 
when both
@@ -581,44 +568,7 @@ impl<S> CompactTupleSketch<S> {
     where
         S: TupleSummaryValue,
     {
-        if self.is_empty() {
-            return EMPTY_SKETCH_BYTES.to_vec();
-        }
-
-        let retained_entries = self.retained_entries();
-        let pre_longs = self.preamble_longs();
-        let entries_size: usize = retained_entries
-            .iter()
-            .map(|entry| 8 + entry.summary().serialize_size())
-            .sum();
-        let mut bytes = SketchBytes::with_capacity(8 * pre_longs as usize + 
entries_size);
-
-        bytes.write_u8(pre_longs);
-        bytes.write_u8(SERIAL_VERSION);
-        bytes.write_u8(Family::TUPLE.id);
-        bytes.write_u8(SKETCH_TYPE);
-        bytes.write_u8(0); // unused
-
-        let mut flags = FLAGS_IS_READ_ONLY | FLAGS_IS_COMPACT;
-        if self.is_ordered() {
-            flags |= FLAGS_IS_ORDERED;
-        }
-        bytes.write_u8(flags);
-        bytes.write_u16_le(self.seed_hash());
-
-        if pre_longs > 1 {
-            bytes.write_u32_le(retained_entries.len() as u32);
-            bytes.write_u32_le(0); // unused
-        }
-        if self.is_estimation_mode() {
-            bytes.write_u64_le(self.theta64());
-        }
-
-        for entry in retained_entries {
-            bytes.write_u64_le(entry.hash());
-            entry.summary().serialize_value(&mut bytes);
-        }
-        bytes.into_bytes()
+        serialize_compact_uncompressed(&self.compact_state)
     }
 
     /// Deserializes a compact Tuple sketch using the default seed.
diff --git a/datasketches/src/thetafamily/tuple/union.rs 
b/datasketches/src/thetafamily/tuple/union.rs
index 029aeba..f2d419a 100644
--- a/datasketches/src/thetafamily/tuple/union.rs
+++ b/datasketches/src/thetafamily/tuple/union.rs
@@ -29,6 +29,8 @@ use crate::thetacommon::constants::DEFAULT_LG_K;
 use crate::thetacommon::union::UnionState;
 use crate::tuple::hash_table::TupleEntry;
 use crate::tuple::policy::SummaryCombinePolicy;
+use crate::tuple::serialization::TupleSummaryValue;
+use crate::tuple::serialization::serialize_compact_uncompressed;
 use crate::tuple::sketch::CompactTupleSketch;
 use crate::tuple::sketch::TupleSketchView;
 
@@ -107,6 +109,44 @@ where
         
CompactTupleSketch::from_compact_state(self.state.to_compact_sketch_state(ordered))
     }
 
+    /// Serializes the union result into the compact Tuple binary format.
+    ///
+    /// The result is the same as `self.to_sketch(ordered).serialize()`: the 
same retained entries,
+    /// theta, and seed hash, and identical bytes when `ordered` is `true`. 
Unordered results may
+    /// list the retained entries in a different order. Summaries are encoded 
in
+    /// place instead of being cloned into an intermediate sketch, so 
`P::Summary` does not need to
+    /// implement [`Clone`].
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use datasketches::tuple::CompactTupleSketch;
+    /// use datasketches::tuple::DefaultUnionPolicy;
+    /// use datasketches::tuple::DefaultUpdatePolicy;
+    /// use datasketches::tuple::TupleSketchBuilder;
+    /// use datasketches::tuple::TupleUnionBuilder;
+    ///
+    /// let mut sketch = 
TupleSketchBuilder::new(DefaultUpdatePolicy::<u64>::default())
+    ///     .build()
+    ///     .unwrap();
+    /// sketch.update("apple", 1);
+    ///
+    /// let mut union = 
TupleUnionBuilder::new(DefaultUnionPolicy::<u64>::default())
+    ///     .build()
+    ///     .unwrap();
+    /// union.update(&sketch).unwrap();
+    ///
+    /// let bytes = union.serialize(true);
+    /// let result = CompactTupleSketch::<u64>::deserialize(&bytes).unwrap();
+    /// assert_eq!(result.num_retained(), 1);
+    /// ```
+    pub fn serialize(&self, ordered: bool) -> Vec<u8>
+    where
+        P::Summary: TupleSummaryValue,
+    {
+        
serialize_compact_uncompressed(&self.state.to_borrowed_compact_sketch_state(ordered))
+    }
+
     /// Resets the union to its initial empty state.
     pub fn reset(&mut self) {
         self.state.reset();
diff --git a/tests-integration/tests/serde_tests/theta.rs 
b/tests-integration/tests/serde_tests/theta.rs
index 4f6dd0f..04857ca 100644
--- a/tests-integration/tests/serde_tests/theta.rs
+++ b/tests-integration/tests/serde_tests/theta.rs
@@ -23,6 +23,7 @@ use datasketches::common::NumStdDev;
 use datasketches::error::ErrorKind;
 use datasketches::theta::CompactThetaSketch;
 use datasketches::theta::ThetaSketchBuilder;
+use datasketches::theta::ThetaUnionBuilder;
 use googletest::assert_that;
 use googletest::prelude::near;
 use tests_integration::ZERO_HASH_SEED;
@@ -318,3 +319,68 @@ fn test_v2_java_empty_layouts() {
         }
     }
 }
+
+#[test]
+fn union_serialization_matches_compact_result() {
+    for (rows, probability, mixed_precision) in [
+        (0, 1.0, false),
+        (1, 1.0, false),
+        (12, 1.0, false),
+        (40, 1.0, false),
+        (64, 0.5, false),
+        (64, 1e-12, false),
+        (64, 1.0, true),
+    ] {
+        let seed = 123;
+        let mut input = ThetaSketchBuilder::default()
+            .lg_k(8)
+            .seed(seed)
+            .sampling_probability(probability)
+            .build()
+            .unwrap();
+        for value in 0..rows {
+            input.update(value);
+        }
+        let mut union = ThetaUnionBuilder::default()
+            .lg_k(5)
+            .seed(seed)
+            .build()
+            .unwrap();
+        for ordered in [false, true] {
+            assert_eq!(
+                union.serialize(ordered),
+                union.to_sketch(ordered).serialize()
+            );
+        }
+        union.update(&input).unwrap();
+        if mixed_precision {
+            let mut other = ThetaSketchBuilder::default()
+                .lg_k(5)
+                .seed(seed)
+                .build()
+                .unwrap();
+            for value in 32..96 {
+                other.update(value);
+            }
+            union.update(&other.compact(true)).unwrap();
+        }
+
+        for ordered in [false, true] {
+            let bytes = union.serialize(ordered);
+            assert_eq!(
+                bytes,
+                union.to_sketch(ordered).serialize(),
+                "rows={rows}, probability={probability}, 
mixed={mixed_precision}, ordered={ordered}",
+            );
+            let restored = CompactThetaSketch::deserialize_with_seed(&bytes, 
seed).unwrap();
+            assert_eq!(restored.serialize(), bytes);
+        }
+        union.reset();
+        for ordered in [false, true] {
+            assert_eq!(
+                union.serialize(ordered),
+                union.to_sketch(ordered).serialize()
+            );
+        }
+    }
+}
diff --git a/tests-integration/tests/serde_tests/tuple.rs 
b/tests-integration/tests/serde_tests/tuple.rs
index 3a71e25..679923c 100644
--- a/tests-integration/tests/serde_tests/tuple.rs
+++ b/tests-integration/tests/serde_tests/tuple.rs
@@ -15,13 +15,25 @@
 // specific language governing permissions and limitations
 // under the License.
 
+use std::cell::Cell;
+use std::fmt::Debug;
 use std::fs;
+use std::io;
 use std::path::PathBuf;
 
+use datasketches::codec::SketchBytes;
+use datasketches::codec::SketchSlice;
+use datasketches::error::Error;
 use datasketches::error::ErrorKind;
 use datasketches::tuple::CompactTupleSketch;
+use datasketches::tuple::DefaultUnionPolicy;
 use datasketches::tuple::DefaultUpdatePolicy;
+use datasketches::tuple::SummaryCombinePolicy;
+use datasketches::tuple::SummaryPolicy;
+use datasketches::tuple::SummaryUpdatePolicy;
 use datasketches::tuple::TupleSketchBuilder;
+use datasketches::tuple::TupleSummaryValue;
+use datasketches::tuple::TupleUnionBuilder;
 use googletest::assert_that;
 use googletest::prelude::each;
 use googletest::prelude::eq;
@@ -214,3 +226,196 @@ fn declared_entry_payload_is_checked_before_allocating() {
 
     assert!(CompactTupleSketch::<u64>::deserialize(&bytes).is_err());
 }
+
+/// Asserts that two serialized compact Tuple sketches hold the same result. 
Unordered images may
+/// list the same entries in a different order.
+fn assert_same_compact_result<S>(actual: &[u8], expected: &[u8], seed: u64)
+where
+    S: TupleSummaryValue + PartialEq + Debug,
+{
+    let actual = CompactTupleSketch::<S>::deserialize_with_seed(actual, 
seed).unwrap();
+    let expected = CompactTupleSketch::<S>::deserialize_with_seed(expected, 
seed).unwrap();
+    assert_eq!(actual.is_empty(), expected.is_empty());
+    assert_eq!(actual.is_ordered(), expected.is_ordered());
+    assert_eq!(actual.theta64(), expected.theta64());
+    assert_eq!(actual.seed_hash(), expected.seed_hash());
+
+    fn sorted_entries<S>(sketch: &CompactTupleSketch<S>) -> Vec<(u64, &S)> {
+        let mut entries: Vec<_> = sketch
+            .iter()
+            .map(|entry| (entry.hash(), entry.summary()))
+            .collect();
+        entries.sort_unstable_by_key(|(hash, _)| *hash);
+        entries
+    }
+    assert_eq!(sorted_entries(&actual), sorted_entries(&expected));
+}
+
+#[test]
+fn union_serialization_matches_compact_result() {
+    let union_builder = || 
TupleUnionBuilder::new(DefaultUnionPolicy::<u64>::default());
+    let empty = union_builder().build().unwrap();
+    for ordered in [true, false] {
+        assert_eq!(
+            empty.serialize(ordered),
+            empty.to_sketch(ordered).serialize()
+        );
+    }
+
+    // Covers exact mode with zero, one and many entries, trimming to nominal 
capacity, a sampled
+    // union, and a non-empty result whose entries were all screened by theta.
+    let seed = 123;
+    for (lg_k, sampling_probability, input_probability, count) in [
+        (5, 1.0, 1.0, 0),
+        (5, 1.0, 1.0, 1),
+        (5, 1.0, 1.0, 20),
+        (5, 1.0, 1.0, 10_000),
+        (12, 1.0, 1.0, 10_000),
+        (8, 0.5, 1.0, 10_000),
+        (5, 1e-12, 1.0, 10),
+        (5, 1.0, 0.1, 100),
+    ] {
+        let mut a = 
TupleSketchBuilder::new(DefaultUpdatePolicy::<u64>::default())
+            .seed(seed)
+            .build()
+            .unwrap();
+        let mut b = 
TupleSketchBuilder::new(DefaultUpdatePolicy::<u64>::default())
+            .seed(seed)
+            .sampling_probability(input_probability)
+            .build()
+            .unwrap();
+        for value in 0..count {
+            a.update(value, 1u64);
+            b.update(value + count / 2, 2u64);
+        }
+        let mut union = union_builder()
+            .seed(seed)
+            .lg_k(lg_k)
+            .sampling_probability(sampling_probability)
+            .build()
+            .unwrap();
+        union.update(&a).unwrap();
+        union.update(&b).unwrap();
+
+        for ordered in [true, false] {
+            let bytes = union.serialize(ordered);
+            let expected = union.to_sketch(ordered).serialize();
+            if ordered {
+                assert_eq!(bytes, expected);
+            }
+            assert_same_compact_result::<u64>(&bytes, &expected, seed);
+        }
+    }
+}
+
+/// Variable-size, heap-backed summary: the tags recorded for a key.
+#[derive(Debug, Default, PartialEq)]
+struct Tags(Vec<String>);
+
+thread_local! {
+    static SUMMARY_CLONES: Cell<usize> = const { Cell::new(0) };
+}
+
+impl Clone for Tags {
+    fn clone(&self) -> Self {
+        SUMMARY_CLONES.with(|count| count.set(count.get() + 1));
+        Self(self.0.clone())
+    }
+}
+
+impl TupleSummaryValue for Tags {
+    fn serialize_size(&self) -> usize {
+        4 + self.0.iter().map(|tag| 4 + tag.len()).sum::<usize>()
+    }
+
+    fn serialize_value(&self, bytes: &mut SketchBytes) {
+        bytes.write_u32_le(self.0.len() as u32);
+        for tag in &self.0 {
+            bytes.write_u32_le(tag.len() as u32);
+            bytes.write(tag.as_bytes());
+        }
+    }
+
+    fn deserialize_value(cursor: &mut SketchSlice<'_>) -> Result<Self, Error> {
+        let malformed = |_: io::Error| Error::new(ErrorKind::InvalidData, 
"malformed tags");
+        let count = cursor.read_u32_le().map_err(malformed)?;
+        let mut tags = Vec::new();
+        for _ in 0..count {
+            let mut tag = vec![0; cursor.read_u32_le().map_err(malformed)? as 
usize];
+            cursor.read_exact(&mut tag).map_err(malformed)?;
+            tags.push(
+                String::from_utf8(tag)
+                    .map_err(|_| Error::new(ErrorKind::InvalidData, "tag is 
not UTF-8"))?,
+            );
+        }
+        Ok(Tags(tags))
+    }
+}
+
+#[derive(Debug, Clone, Copy)]
+struct TagsPolicy;
+
+impl SummaryPolicy for TagsPolicy {
+    type Summary = Tags;
+
+    fn create(&self) -> Self::Summary {
+        Tags::default()
+    }
+}
+
+impl SummaryUpdatePolicy<&str> for TagsPolicy {
+    fn update(&self, summary: &mut Self::Summary, value: &str) {
+        summary.0.push(value.to_string());
+    }
+}
+
+impl SummaryCombinePolicy for TagsPolicy {
+    fn combine(&self, summary: &mut Self::Summary, other: &Self::Summary) {
+        summary.0.extend(other.0.iter().cloned());
+    }
+}
+
+#[test]
+fn union_serialization_with_heap_backed_summaries_supports_later_merges() {
+    for lg_k in [5, 9] {
+        let seed = 123;
+        let sketch = |values: std::ops::Range<u64>, tag: &str| {
+            let mut sketch = TupleSketchBuilder::new(TagsPolicy)
+                .lg_k(lg_k)
+                .seed(seed)
+                .build()
+                .unwrap();
+            for value in values {
+                sketch.update(value, tag);
+            }
+            sketch
+        };
+        let union_builder = || 
TupleUnionBuilder::new(TagsPolicy).lg_k(lg_k).seed(seed);
+
+        let mut union = union_builder().build().unwrap();
+        union.update(&sketch(0..1_000, "first")).unwrap();
+        union
+            .update(&sketch(500..1_500, "a longer second tag"))
+            .unwrap();
+        let later = sketch(1_000..2_000, "third");
+
+        for ordered in [true, false] {
+            let clones = SUMMARY_CLONES.get();
+            let bytes = union.serialize(ordered);
+            assert_eq!(SUMMARY_CLONES.get(), clones);
+            let expected = union.to_sketch(ordered).serialize();
+            assert_same_compact_result::<Tags>(&bytes, &expected, seed);
+
+            let restored = 
CompactTupleSketch::<Tags>::deserialize_with_seed(&bytes, seed).unwrap();
+            let mut from_bytes = union_builder().build().unwrap();
+            from_bytes.update(&restored).unwrap();
+            from_bytes.update(&later).unwrap();
+
+            let mut from_sketch = union_builder().build().unwrap();
+            from_sketch.update(&union.to_sketch(ordered)).unwrap();
+            from_sketch.update(&later).unwrap();
+
+            assert_eq!(from_bytes.serialize(true), 
from_sketch.serialize(true));
+        }
+    }
+}


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to