Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
23 changes: 23 additions & 0 deletions crates/dbsp/src/algebra/zset.rs
Original file line number Diff line number Diff line change
Expand Up @@ -250,6 +250,11 @@ pub trait ZSet: IndexedZSet<Val = DynUnit> {
/// negative, so the result can be zero even if the Z-set contains nonzero
/// weights.
fn weighted_count(&self, sum: &mut Self::R);

/// Returns a Z-set that contains all elements with positive weights from
/// `self` with their weights preserved.
#[cfg(test)]
fn positive(&self) -> Self;
}

impl<Z, K> ZSet for Z
Expand All @@ -266,6 +271,24 @@ where
cursor.step_key();
}
}

#[cfg(test)]
fn positive(&self) -> Self {
let factories = self.factories();
let mut builder = Self::Builder::with_capacity(&factories, self.key_count(), self.len());
let mut cursor = self.cursor();

while cursor.key_valid() {
let weight = **cursor.weight();
if weight > 0 {
builder.push_val_diff(cursor.val(), weight.erase());
builder.push_key(cursor.key());
}
cursor.step_key();
}

builder.done()
}
}

#[cfg(test)]
Expand Down
4 changes: 4 additions & 0 deletions crates/dbsp/src/circuit/circuit_builder.rs
Original file line number Diff line number Diff line change
Expand Up @@ -544,6 +544,10 @@ dyn_clone::clone_trait_object!(StreamMetadata);
/// data. It sets each record's weight to 1 if it is positive and drops the
/// others.
///
/// The "positive" operator on a Z-set keeps positive weights unchanged and
/// maps all other weights to 0. It differs from "distinct" only in that it
/// does not clamp positive weights to 1.
///
/// ## Join on equal keys
///
/// A DBSP equi-join takes batches `a` and `b` as input, finds all pairs of a
Expand Down
14 changes: 14 additions & 0 deletions crates/dbsp/src/mono.rs
Original file line number Diff line number Diff line change
Expand Up @@ -762,6 +762,13 @@ where
self.inner().dyn_distinct_mono(&factories).typed()
}

#[track_caller]
pub fn positive(&self) -> Self {
let factories = DistinctFactories::new::<K, ()>();

self.inner().dyn_positive_mono(&factories).typed()
}

#[track_caller]
pub fn hash_distinct(&self) -> Self {
let factories = HashDistinctFactories::new::<K, ()>();
Expand Down Expand Up @@ -1244,6 +1251,13 @@ where
self.inner().dyn_distinct_mono(&factories).typed()
}

#[track_caller]
pub fn positive(&self) -> Self {
let factories = DistinctFactories::new::<K, ()>();

self.inner().dyn_positive_mono(&factories).typed()
}

#[track_caller]
pub fn hash_distinct(&self) -> Self {
let factories = HashDistinctFactories::new::<K, ()>();
Expand Down
28 changes: 21 additions & 7 deletions crates/dbsp/src/operator/distinct.rs
Original file line number Diff line number Diff line change
Expand Up @@ -22,14 +22,7 @@ where

self.inner().dyn_stream_distinct(&factories).typed()
}
}

impl<C, Z> Stream<C, Z>
where
C: Circuit,
Z: IndexedZSet,
Z::InnerBatch: Send,
{
/// Incrementally deduplicate input stream.
///
/// This is an incremental version of the
Expand Down Expand Up @@ -62,4 +55,25 @@ where

self.inner().dyn_has_distinct(&factories).typed()
}

/// Incrementally filter out tuples with non-positive weights.
///
/// Given a stream of changes to relation `A`, computes a stream of
/// changes to relation `A'` that contains every `(key, weight)` tuple of
/// `A` with `weight > 0`, with the weight unchanged.
///
/// This operator is like [`distinct`](`Self::distinct`), except that it
/// preserves the weights of the retained tuples instead of clamping them
/// to 1.
#[cfg(not(feature = "backend-mode"))]
#[track_caller]
pub fn positive(&self) -> Stream<C, Z>
where
Z: crate::typed_batch::ZSet,
{
let factories =
crate::operator::dynamic::distinct::DistinctFactories::new::<Z::Key, Z::Val>();

self.inner().dyn_positive(&factories).typed()
}
}
Loading