Skip to content

Commit dab1684

Browse files
joacocconnortsui20
andauthored
Bloom filter implementation (#9398)
## Rationale for this change <!-- Why are you proposing this change, and what is its impact? Is it part of a long term effort, or a bigger change? If this PR is related to a tracked effort or an open issue, please link to the relevant issue. --> This is part of a bigger issue around skip indexes but only focuses on the Bloom filter implementation: - #8901 ## What changes are included in this PR? <!-- No need to duplicate information from the previous section, but if you're touching many parts of the code base, its worth explicitly noting the important changes or how they are tested. --> This is a continuation of a previous PR that already implements a simpler version of a bloom filter: #8933. Most of the changes included in this PR are replacing the hand-rolled bloom-filter from the base PR with the [split block bloom filter](https://arxiv.org/pdf/2101.01719), and expanding support for more canonicals and constants. So far it supports bool, primitives, decimals, varbinview, and extensions, and this PR leaves out composable types out of the implementation (struct, list and so on). <!-- Are there any user-facing changes that might require documentation updates Is any public API changed? --> ## About the code The Bloom filter implementation is a translation from the [paper source code](https://arxiv.org/pdf/2101.01719), given that it is very short I thought it wouldn't be a big deal. The code doesn't use arch-y fn calls, but relies on the compiler optimizer for vectorizing/calling the correct assembler expression, which from my checks on godbolt, seems to get translated well. I could have gone into specializing the code into different architectures but keeping it as is seemed better for maintenance. ### Accumulators Bloom filter's accumulators for canonicals are very similar to those of the min/max aggregation fn. I used those implementations as a reference for manipulating each case, with some slight variations. Invalid values are left out of Bloom filters. Only valid values apply. Accumulating an invalid value will just skip it, but asking for a scalar that is invalid will raise a `VortexError`. ### Options/tuning The Bloom filter has a single tuning option called `blocks_count`. The more blocks, the more memory/space usage (per zone), but the fewer false positives. Defaults to 256 (8KiB p/zone), derived from the default amount of 8192 rows in a zone. The paper suggests keeping between 20 and 52 distinct hash values per block. Assuming all 8,192 values are distinct, choosing 32 values per block gives 8,192 / 32 = 256 blocks (low false positive rate: ~3%). Another approach could be to use statistics from a subset of the data, as is done with encoders, to select the best block count. I think this approach aligns with how Vortex encoders work, but it shouldn't be part of this PR, as it may depend on how the skip index writer is designed. ### Hasher crate This PR also includes a new crate `twox-hash` that implements XxHash, similar to how Parquet uses the same hasher for the same use case, but it relies on vendored code. Happy to change or look for alternatives. ## Pending tasks - [x] Microbenchmarks - [x] Goldenfile - [x] Salt-order check - [x] Define hashing fn (`XxHash3_64` vs `XXH64`) - [x] More docs in source --------- Signed-off-by: Connor Tsui <[email protected]> Signed-off-by: Joaquin Colacci <[email protected]> Co-authored-by: Connor Tsui <[email protected]>
1 parent 792cef7 commit dab1684

19 files changed

Lines changed: 2740 additions & 0 deletions

File tree

‎Cargo.lock‎

Lines changed: 3 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎Cargo.toml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -284,6 +284,7 @@ tpchgen-arrow = "3.0.0"
284284
tracing = { version = "0.1.41", default-features = false }
285285
tracing-perfetto = "0.1.5"
286286
tracing-subscriber = "0.3"
287+
twox-hash = "2.1.2"
287288
url = "2.5.7"
288289
uuid = "1.23"
289290
wasm-bindgen-futures = "0.4.58"

‎vortex-layout/Cargo.toml‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,7 @@ sketches-ddsketch = { workspace = true }
3838
termtree = { workspace = true }
3939
tokio = { workspace = true, features = ["rt"], optional = true }
4040
tracing = { workspace = true }
41+
twox-hash = { workspace = true }
4142
vortex-array = { workspace = true }
4243
vortex-arrow = { workspace = true }
4344
vortex-btrblocks = { workspace = true }
@@ -56,7 +57,9 @@ vortex-utils = { workspace = true, features = ["dashmap"] }
5657
[dev-dependencies]
5758
divan = { workspace = true }
5859
futures = { workspace = true, features = ["executor"] }
60+
goldenfile = { workspace = true }
5961
insta = { workspace = true }
62+
rand = { workspace = true }
6063
rstest = { workspace = true }
6164
temp-env = { workspace = true }
6265
tokio = { workspace = true, features = ["rt", "macros"] }
@@ -79,6 +82,10 @@ harness = false
7982
[target.'cfg(all(target_arch = "wasm32", target_os = "unknown"))'.dependencies]
8083
uuid = { workspace = true, features = ["js"], optional = true }
8184

85+
[[bench]]
86+
name = "bloom_filter"
87+
harness = false
88+
8289
[lints]
8390
workspace = true
8491

Lines changed: 106 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,106 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
//! Microbenchmarks for [`BloomPartial`] insertion and membership checks.
5+
//!
6+
//! The idea is to benchmark `insert` and `contain` across different filter sizes.
7+
//! Larger filters are less cache-friendly.
8+
9+
#![expect(clippy::expect_used)]
10+
11+
use std::num::NonZeroU32;
12+
13+
use divan::Bencher;
14+
use divan::counter::ItemsCount;
15+
use rand::RngExt;
16+
use rand::SeedableRng;
17+
use rand::rngs::StdRng;
18+
use vortex_layout::layouts::zoned::aggregates::bloom_filter::BloomOptions;
19+
use vortex_layout::layouts::zoned::aggregates::bloom_filter::BloomPartial;
20+
use vortex_layout::layouts::zoned::aggregates::bloom_filter::HashFn;
21+
22+
fn main() {
23+
divan::main();
24+
}
25+
26+
/// [Tiny, Default, Cache-unfriendly].
27+
const BLOCK_COUNTS: &[u32] = &[
28+
256, // 8KiB
29+
32_768, // 1MiB
30+
1_048_576, // 32 MiB
31+
];
32+
const VALUE_COUNT: usize = 8192;
33+
34+
fn options(block_count: u32) -> BloomOptions {
35+
BloomOptions::new(
36+
NonZeroU32::new(block_count).expect("benchmark block counts are non-zero"),
37+
HashFn::XxHash3_64,
38+
)
39+
}
40+
41+
fn values(seed: u64) -> Vec<[u8; 16]> {
42+
let mut rng = StdRng::seed_from_u64(seed);
43+
(0..VALUE_COUNT).map(|_| rng.random()).collect()
44+
}
45+
46+
fn populated_filter(options: &BloomOptions, values: &[[u8; 16]]) -> BloomPartial {
47+
let mut filter = BloomPartial::from(options);
48+
49+
for value in values {
50+
filter.insert(value);
51+
}
52+
53+
filter
54+
}
55+
56+
#[divan::bench(args = BLOCK_COUNTS)]
57+
fn insert(bencher: Bencher, block_count: u32) {
58+
let options = options(block_count);
59+
let values = values(0xbeef);
60+
61+
bencher
62+
.counter(ItemsCount::new(VALUE_COUNT))
63+
.with_inputs(|| (BloomPartial::from(&options), values.as_slice()))
64+
.bench_refs(|(filter, values)| {
65+
for value in *values {
66+
filter.insert(value);
67+
}
68+
});
69+
}
70+
71+
#[divan::bench(args = BLOCK_COUNTS)]
72+
fn contains_present(bencher: Bencher, block_count: u32) {
73+
let options = options(block_count);
74+
let values = values(0xbeef);
75+
let filter = populated_filter(&options, &values);
76+
77+
bencher
78+
.counter(ItemsCount::new(VALUE_COUNT))
79+
.with_inputs(|| (&filter, values.as_slice()))
80+
.bench_refs(|(filter, values)| {
81+
let mut matches = 0;
82+
for value in *values {
83+
matches += usize::from(filter.contains(value));
84+
}
85+
divan::black_box(matches);
86+
});
87+
}
88+
89+
#[divan::bench(args = BLOCK_COUNTS)]
90+
fn contains_absent(bencher: Bencher, block_count: u32) {
91+
let options = options(block_count);
92+
let inserted_values = values(0xbeef);
93+
let queries = values(0xfeed);
94+
let filter = populated_filter(&options, &inserted_values);
95+
96+
bencher
97+
.counter(ItemsCount::new(VALUE_COUNT))
98+
.with_inputs(|| (&filter, queries.as_slice()))
99+
.bench_refs(|(filter, queries)| {
100+
let mut matches = 0;
101+
for query in *queries {
102+
matches += usize::from(filter.contains(query));
103+
}
104+
divan::black_box(matches);
105+
});
106+
}
8 Bytes
Binary file not shown.
Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,118 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
use std::ops::BitAnd;
5+
6+
use vortex_array::ExecutionCtx;
7+
use vortex_array::arrays::BoolArray;
8+
use vortex_array::arrays::bool::BoolArrayExt;
9+
use vortex_error::VortexResult;
10+
use vortex_mask::AllOr;
11+
12+
use super::BloomPartial;
13+
14+
/// Similar to `accumulate_bool` implementation in [vortex_array::aggregate_fn::fns::min_max]
15+
pub(super) fn accumulate_bool(
16+
array: &BoolArray,
17+
partial: &mut BloomPartial,
18+
ctx: &mut ExecutionCtx,
19+
) -> VortexResult<()> {
20+
let mask = array.validity()?.execute_mask(array.len(), ctx)?;
21+
22+
let (true_count, valid_count) = match mask.bit_buffer() {
23+
AllOr::None => return Ok(()),
24+
AllOr::All => (array.bit_buffer_view().true_count(), array.as_ref().len()),
25+
AllOr::Some(validity) => (
26+
array.to_bit_buffer().bitand(validity).true_count(),
27+
validity.true_count(),
28+
),
29+
};
30+
31+
if true_count > 0 {
32+
// True present
33+
partial.insert([0x1]);
34+
}
35+
if true_count < valid_count {
36+
// False present
37+
partial.insert([0x0]);
38+
}
39+
40+
Ok(())
41+
}
42+
43+
#[cfg(test)]
44+
mod tests {
45+
use rstest::rstest;
46+
use vortex_array::IntoArray;
47+
use vortex_array::arrays::BoolArray;
48+
use vortex_array::dtype::DType;
49+
use vortex_array::dtype::Nullability;
50+
use vortex_array::scalar::Scalar;
51+
use vortex_error::VortexResult;
52+
use vortex_error::vortex_err;
53+
54+
use crate::layouts::zoned::aggregates::bloom_filter::test_utils::build_filter;
55+
use crate::layouts::zoned::aggregates::bloom_filter::test_utils::setup;
56+
57+
#[rstest]
58+
#[case::inserts_each_valid_boolean_value(
59+
&[Some(true), Some(false)],
60+
Nullability::NonNullable,
61+
true,
62+
true
63+
)]
64+
#[case::inserts_only_false(
65+
&[Some(false), Some(false)],
66+
Nullability::NonNullable,
67+
false,
68+
true
69+
)]
70+
#[case::inserts_only_true(
71+
&[Some(true), Some(true)],
72+
Nullability::NonNullable,
73+
true,
74+
false
75+
)]
76+
#[case::ignores_null_boolean_values(
77+
&[Some(true), None, Some(true)],
78+
Nullability::Nullable,
79+
true,
80+
false
81+
)]
82+
#[case::all_null_booleans_leave_the_filter_empty(
83+
&[None, None],
84+
Nullability::Nullable,
85+
false,
86+
false
87+
)]
88+
fn membership(
89+
#[case] values: &[Option<bool>],
90+
#[case] nullability: Nullability,
91+
#[case] expect_true: bool,
92+
#[case] expect_false: bool,
93+
) -> VortexResult<()> {
94+
let ctx = setup()?;
95+
let array = match nullability {
96+
Nullability::NonNullable => BoolArray::from_iter(
97+
values
98+
.iter()
99+
.copied()
100+
.collect::<Option<Vec<_>>>()
101+
.ok_or_else(|| vortex_err!("non-null test case contains a null"))?,
102+
),
103+
Nullability::Nullable => BoolArray::from_iter(values.iter().copied()),
104+
};
105+
let bloom_filter = build_filter(array.into_array(), DType::Bool(nullability), ctx)?;
106+
107+
assert_eq!(
108+
bloom_filter.contains_scalar(&Scalar::bool(true, nullability))?,
109+
expect_true
110+
);
111+
assert_eq!(
112+
bloom_filter.contains_scalar(&Scalar::bool(false, nullability))?,
113+
expect_false
114+
);
115+
116+
Ok(())
117+
}
118+
}
Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
use vortex_array::Canonical;
5+
use vortex_array::ExecutionCtx;
6+
use vortex_array::arrays::ExtensionArray;
7+
use vortex_array::arrays::extension::ExtensionArrayExt;
8+
use vortex_error::VortexResult;
9+
10+
use super::BloomPartial;
11+
12+
pub(super) fn accumulate_extension(
13+
array: &ExtensionArray,
14+
partial: &mut BloomPartial,
15+
ctx: &mut ExecutionCtx,
16+
) -> VortexResult<()> {
17+
let storage = array.storage_array().clone();
18+
let canonical = storage.execute::<Canonical>(ctx)?;
19+
20+
super::accumulate_canonical(&canonical, partial, ctx)
21+
}
22+
23+
#[cfg(test)]
24+
mod tests {
25+
use vortex_array::IntoArray;
26+
use vortex_array::arrays::ExtensionArray;
27+
use vortex_array::arrays::PrimitiveArray;
28+
use vortex_array::dtype::DType;
29+
use vortex_array::dtype::Nullability;
30+
use vortex_array::extension::datetime::TimeUnit;
31+
use vortex_array::extension::datetime::Timestamp;
32+
use vortex_array::scalar::Scalar;
33+
use vortex_error::VortexResult;
34+
35+
use crate::layouts::zoned::aggregates::bloom_filter::test_utils::build_filter;
36+
use crate::layouts::zoned::aggregates::bloom_filter::test_utils::setup;
37+
38+
#[test]
39+
fn hashes_extension_values_through_storage() -> VortexResult<()> {
40+
let ctx = setup()?;
41+
let ext_dtype = Timestamp::new(TimeUnit::Milliseconds, Nullability::NonNullable).erased();
42+
let bloom_filter = build_filter(
43+
ExtensionArray::new(
44+
ext_dtype.clone(),
45+
PrimitiveArray::from_iter([1_000i64, 2_000, 3_000]).into_array(),
46+
)
47+
.into_array(),
48+
DType::Extension(ext_dtype.clone()),
49+
ctx,
50+
)?;
51+
52+
for value in [1_000i64, 2_000, 3_000] {
53+
let scalar = Scalar::extension_ref(
54+
ext_dtype.clone(),
55+
Scalar::primitive(value, Nullability::NonNullable),
56+
);
57+
assert!(bloom_filter.contains_scalar(&scalar)?);
58+
}
59+
60+
let absent = Scalar::extension_ref(
61+
ext_dtype,
62+
Scalar::primitive(4_000i64, Nullability::NonNullable),
63+
);
64+
assert!(!bloom_filter.contains_scalar(&absent)?);
65+
Ok(())
66+
}
67+
68+
#[test]
69+
fn ignores_null_extension_values() -> VortexResult<()> {
70+
let ctx = setup()?;
71+
let ext_dtype = Timestamp::new(TimeUnit::Milliseconds, Nullability::Nullable).erased();
72+
let bloom_filter = build_filter(
73+
ExtensionArray::new(
74+
ext_dtype.clone(),
75+
PrimitiveArray::from_option_iter([Some(1_000i64), None, Some(3_000)]).into_array(),
76+
)
77+
.into_array(),
78+
DType::Extension(ext_dtype.clone()),
79+
ctx,
80+
)?;
81+
82+
let present = Scalar::extension_ref(
83+
ext_dtype.clone(),
84+
Scalar::primitive(1_000i64, Nullability::Nullable),
85+
);
86+
let null_slot_value =
87+
Scalar::extension_ref(ext_dtype, Scalar::primitive(0i64, Nullability::Nullable));
88+
assert!(bloom_filter.contains_scalar(&present)?);
89+
assert!(!bloom_filter.contains_scalar(&null_slot_value)?);
90+
Ok(())
91+
}
92+
}

0 commit comments

Comments
 (0)