Skip to content

Commit 383ec56

Browse files
authored
fix: merge all Bloom filter states and respect sliced offsets (#7173)
* fix: merge all Bloom filter states and respect sliced offsets * test: cover batched Bloom states in default final aggregation
1 parent 044b3ea commit 383ec56

2 files changed

Lines changed: 175 additions & 3 deletions

File tree

‎native/spark-expr/src/bloom_filter/bloom_filter_agg.rs‎

Lines changed: 70 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -190,16 +190,83 @@ impl Accumulator for SparkBloomFilter {
190190
"Expect one element in 'states' but found {}",
191191
states.len()
192192
);
193-
assert_eq!(states[0].len(), 1);
194-
let state_sv = downcast_value!(states[0], BinaryArray);
195-
self.merge_filter(state_sv.value_data())
193+
let states = downcast_value!(states[0], BinaryArray);
194+
// A final aggregate can pass several partial states in one batch. Merge each
195+
// row's byte slice because the backing buffer can also contain other groups' states.
196+
for state in states.iter().flatten() {
197+
self.merge_filter(state)?;
198+
}
199+
Ok(())
196200
}
197201
}
198202

199203
#[cfg(test)]
200204
mod tests {
201205
use super::*;
202206

207+
fn filter_with_values(version: SparkBloomFilterVersion, values: &[i64]) -> SparkBloomFilter {
208+
let mut filter = SparkBloomFilter::new(version, 3, 1024, 0);
209+
for &value in values {
210+
filter.put_long(value);
211+
}
212+
filter
213+
}
214+
215+
#[test]
216+
fn merge_batch_merges_each_row() {
217+
for version in [SparkBloomFilterVersion::V1, SparkBloomFilterVersion::V2] {
218+
let first = filter_with_values(version, &[11]).state_as_bytes();
219+
let second = filter_with_values(version, &[22]).state_as_bytes();
220+
let states =
221+
BinaryArray::from(vec![Some(first.as_slice()), None, Some(second.as_slice())]);
222+
let mut acc = filter_with_values(version, &[33]);
223+
acc.merge_batch(&[Arc::new(states)]).unwrap();
224+
assert_eq!(
225+
acc.state_as_bytes(),
226+
filter_with_values(version, &[11, 22, 33]).state_as_bytes()
227+
);
228+
}
229+
}
230+
231+
#[test]
232+
fn merge_batch_respects_sliced_row_offsets() {
233+
for version in [SparkBloomFilterVersion::V1, SparkBloomFilterVersion::V2] {
234+
let excluded = filter_with_values(version, &[99]).state_as_bytes();
235+
let included = filter_with_values(version, &[11]).state_as_bytes();
236+
let states = BinaryArray::from(vec![
237+
excluded.as_slice(),
238+
included.as_slice(),
239+
excluded.as_slice(),
240+
]);
241+
let mut acc = filter_with_values(version, &[]);
242+
acc.merge_batch(&[Arc::new(states.slice(1, 1))]).unwrap();
243+
assert_eq!(acc.state_as_bytes(), included);
244+
}
245+
}
246+
247+
#[test]
248+
fn merge_batch_ignores_empty_and_null_states() {
249+
let mut acc = filter_with_values(SparkBloomFilterVersion::V1, &[11]);
250+
let expected = acc.state_as_bytes();
251+
for states in [
252+
BinaryArray::from(Vec::<Option<&[u8]>>::new()),
253+
BinaryArray::from(vec![None::<&[u8]>]),
254+
] {
255+
acc.merge_batch(&[Arc::new(states)]).unwrap();
256+
assert_eq!(acc.state_as_bytes(), expected);
257+
}
258+
}
259+
260+
#[test]
261+
fn merge_batch_propagates_incompatible_state_error() {
262+
let first = filter_with_values(SparkBloomFilterVersion::V1, &[11]).state_as_bytes();
263+
let second = filter_with_values(SparkBloomFilterVersion::V2, &[22]).state_as_bytes();
264+
let states = BinaryArray::from(vec![first.as_slice(), second.as_slice()]);
265+
let mut acc = filter_with_values(SparkBloomFilterVersion::V1, &[]);
266+
let error = acc.merge_batch(&[Arc::new(states)]).unwrap_err();
267+
assert!(error.to_string().contains("version mismatch"));
268+
}
269+
203270
/// Spark's BloomFilterAggregate.eval returns NULL when the filter saw no
204271
/// non-null input (cardinality 0); an untouched accumulator must match.
205272
#[test]
Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
use std::sync::Arc;
19+
20+
use arrow::array::{AsArray, BinaryArray, Int64Array, RecordBatch};
21+
use arrow::datatypes::{DataType, Field, Int64Type, Schema};
22+
use datafusion::common::{Result, ScalarValue};
23+
use datafusion::datasource::memory::MemorySourceConfig;
24+
use datafusion::execution::TaskContext;
25+
use datafusion::logical_expr::AggregateUDF;
26+
use datafusion::physical_expr::aggregate::{AggregateExprBuilder, AggregateFunctionExpr};
27+
use datafusion::physical_expr::expressions::{Column, Literal};
28+
use datafusion::physical_plan::aggregates::{AggregateExec, AggregateMode, PhysicalGroupBy};
29+
use datafusion::physical_plan::{common::collect, ExecutionPlan};
30+
use datafusion_comet_spark_expr::{BloomFilterAgg, SparkBloomFilterVersion};
31+
32+
fn bloom_state(aggregate: &AggregateFunctionExpr, values: &[i64]) -> Result<Vec<u8>> {
33+
let mut accumulator = aggregate.create_accumulator()?;
34+
accumulator.update_batch(&[Arc::new(Int64Array::from_iter_values(
35+
values.iter().copied(),
36+
))])?;
37+
let ScalarValue::Binary(Some(state)) = accumulator.state()?.remove(0) else {
38+
panic!("a nonempty Bloom filter must have a binary state");
39+
};
40+
Ok(state)
41+
}
42+
43+
#[tokio::test]
44+
async fn grouped_final_bloom_filter_merges_batched_states() -> Result<()> {
45+
let value_schema = Arc::new(Schema::new(vec![
46+
Field::new("key", DataType::Int64, false),
47+
Field::new("value", DataType::Int64, false),
48+
]));
49+
let aggregate_udf = Arc::new(AggregateUDF::new_from_impl(BloomFilterAgg::new(
50+
Arc::new(Literal::new(ScalarValue::Int64(Some(100)))),
51+
Arc::new(Literal::new(ScalarValue::Int64(Some(1024)))),
52+
DataType::Binary,
53+
SparkBloomFilterVersion::V1,
54+
)));
55+
let aggregate_expr = Arc::new(
56+
AggregateExprBuilder::new(aggregate_udf, vec![Arc::new(Column::new("value", 1))])
57+
.schema(Arc::clone(&value_schema))
58+
.alias("bloom")
59+
.build()?,
60+
);
61+
let state_schema = Arc::new(Schema::new(vec![
62+
Field::new("key", DataType::Int64, false),
63+
Field::new("bits", DataType::Binary, false),
64+
]));
65+
66+
// Interleave the keys so one group merges two states and the other uses a
67+
// separate slice of the same binary array.
68+
let states = BinaryArray::from_iter_values([
69+
bloom_state(&aggregate_expr, &[11])?,
70+
bloom_state(&aggregate_expr, &[99])?,
71+
bloom_state(&aggregate_expr, &[22])?,
72+
]);
73+
let batch = RecordBatch::try_new(
74+
Arc::clone(&state_schema),
75+
vec![Arc::new(Int64Array::from(vec![1, 2, 1])), Arc::new(states)],
76+
)?;
77+
let scan = MemorySourceConfig::try_new_exec(&[vec![batch]], state_schema, None)?;
78+
let aggregate = AggregateExec::try_new(
79+
AggregateMode::Final,
80+
PhysicalGroupBy::new_single(vec![(Arc::new(Column::new("key", 0)), "key".into())]),
81+
vec![Arc::clone(&aggregate_expr)],
82+
vec![None],
83+
scan,
84+
value_schema,
85+
)?;
86+
let output = collect(aggregate.execute(0, Arc::new(TaskContext::default()))?).await?;
87+
88+
let mut actual = Vec::new();
89+
for batch in output {
90+
let keys = batch.column(0).as_primitive::<Int64Type>();
91+
let filters = batch.column(1).as_binary::<i32>();
92+
for (key, filter) in keys.iter().zip(filters.iter()) {
93+
actual.push((key.unwrap(), filter.unwrap().to_vec()));
94+
}
95+
}
96+
actual.sort_by_key(|(key, _)| *key);
97+
assert_eq!(
98+
actual,
99+
vec![
100+
(1, bloom_state(&aggregate_expr, &[11, 22])?),
101+
(2, bloom_state(&aggregate_expr, &[99])?),
102+
]
103+
);
104+
Ok(())
105+
}

0 commit comments

Comments
 (0)