Skip to content

Commit faad45c

Browse files
anirvinvclaude
authored andcommitted
perf: avoid repeated zstd decompression in list_contains
Add a Zstd execute-parent kernel for ListContains. The generic path compares every list element against the needle, and each comparison decompresses the Zstd needle again. The kernel decompresses it once, then either: - for a non-null constant list of at least 32 strings or binaries against at least 256 values, probes a hash set of the list's elements, or - delegates to ListContains with the caller's options. Benchmark (8k rows, encodings/zstd/benches/list_contains.rs): list length per element decompress once hash path 32 3.7 ms 0.54 ms 0.15 ms 2,048 252 ms 29 ms 0.18 ms 24,999 2.8 s 359 ms 0.62 ms Ported onto upstream develop 2664573, which added SQL null semantics to list_contains (vortex-data#10057). The release-13 version had to change to match them: - The fallback dropped the caller's ListContainsOptions, so SQL NOT IN could admit rows. It now passes them through. - The hash path returned false for a null needle; it now returns null. - Under SQL null semantics, a non-match against a list holding a null is now null. - The result nullability comes from ListContainsOptions::result_nullability. The tests compare the hash path and the Zstd kernel against the generic path over null needles and null list elements, under both null semantics. The kernel is registered in vortex_zstd::initialize. (cherry picked from commit d90b794) Co-Authored-By: Claude Opus 5.5 <[email protected]>
1 parent 70bdbf7 commit faad45c

8 files changed

Lines changed: 478 additions & 2 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.

‎encodings/zstd/Cargo.toml‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,8 +28,15 @@ vortex-edition = { workspace = true }
2828
vortex-error = { workspace = true }
2929
vortex-mask = { workspace = true }
3030
vortex-session = { workspace = true }
31+
vortex-utils = { workspace = true }
3132
zstd = { workspace = true }
3233

3334
[dev-dependencies]
35+
divan = { workspace = true }
36+
mimalloc = { workspace = true }
3437
rstest = { workspace = true }
3538
vortex-array = { workspace = true, features = ["_test-harness"] }
39+
40+
[[bench]]
41+
name = "list_contains"
42+
harness = false
Lines changed: 156 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,156 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
#![expect(clippy::unwrap_used)]
5+
6+
use std::sync::Arc;
7+
use std::sync::LazyLock;
8+
9+
use divan::Bencher;
10+
use mimalloc::MiMalloc;
11+
use vortex_array::ArrayRef;
12+
use vortex_array::IntoArray;
13+
use vortex_array::VortexSessionExecute;
14+
use vortex_array::arrays::BoolArray;
15+
use vortex_array::arrays::ConstantArray;
16+
use vortex_array::arrays::VarBinViewArray;
17+
use vortex_array::builtins::ArrayBuiltins;
18+
use vortex_array::dtype::DType;
19+
use vortex_array::dtype::Nullability;
20+
use vortex_array::scalar::Scalar;
21+
use vortex_array::scalar_fn::fns::operators::Operator;
22+
use vortex_session::VortexSession;
23+
use vortex_zstd::Zstd;
24+
use vortex_zstd::ZstdArray;
25+
26+
#[global_allocator]
27+
static GLOBAL: MiMalloc = MiMalloc;
28+
29+
const ROW_COUNT: usize = 8 * 1024;
30+
const LIST_LENGTHS: &[usize] = &[4, 32, 256, 2 * 1024, 16 * 1024, 24_999];
31+
32+
static SESSION: LazyLock<VortexSession> = LazyLock::new(|| {
33+
let session = VortexSession::empty();
34+
vortex_zstd::initialize(&session);
35+
session
36+
});
37+
38+
struct Inputs {
39+
list: ArrayRef,
40+
elements: Vec<Scalar>,
41+
values: ZstdArray,
42+
}
43+
44+
fn inputs(list_len: usize) -> Inputs {
45+
let strings = (0..ROW_COUNT)
46+
.map(|i| format!("{i:08x}-0000-0000-0000-{i:012x}"))
47+
.collect::<Vec<_>>();
48+
let values = VarBinViewArray::from_iter_str(&strings);
49+
let values =
50+
Zstd::from_var_bin_view(&values, 3, ROW_COUNT, &mut SESSION.create_execution_ctx())
51+
.unwrap();
52+
let elements = (0..list_len)
53+
.map(|i| Scalar::from(strings[i * ROW_COUNT / list_len].as_str()))
54+
.collect::<Vec<_>>();
55+
let list = ConstantArray::new(
56+
Scalar::list(
57+
Arc::new(DType::Utf8(Nullability::NonNullable)),
58+
elements.clone(),
59+
Nullability::NonNullable,
60+
),
61+
ROW_COUNT,
62+
)
63+
.into_array();
64+
65+
Inputs {
66+
list,
67+
elements,
68+
values,
69+
}
70+
}
71+
72+
/// Registered Zstd kernel: hash large lists and decompress the values once otherwise.
73+
#[divan::bench(args = LIST_LENGTHS, sample_count = 10)]
74+
fn hybrid_hash(bencher: Bencher, list_len: usize) {
75+
let inputs = inputs(list_len);
76+
let mut ctx = SESSION.create_execution_ctx();
77+
78+
bencher.bench_local(|| {
79+
inputs
80+
.list
81+
.list_contains(inputs.values.clone().into_array())
82+
.unwrap()
83+
.execute::<BoolArray>(&mut ctx)
84+
.unwrap()
85+
});
86+
}
87+
88+
/// Decompress once, then execute generic `list_contains` comparisons.
89+
#[divan::bench(args = LIST_LENGTHS, sample_count = 10)]
90+
fn decompress_once(bencher: Bencher, list_len: usize) {
91+
let inputs = inputs(list_len);
92+
let mut ctx = SESSION.create_execution_ctx();
93+
94+
bencher.bench_local(|| {
95+
let values = Zstd::decompress(&inputs.values, &mut ctx).unwrap();
96+
inputs
97+
.list
98+
.list_contains(values)
99+
.unwrap()
100+
.execute::<BoolArray>(&mut ctx)
101+
.unwrap()
102+
});
103+
}
104+
105+
/// Reproduction of the generic fallback: compare against Zstd once per list element.
106+
#[divan::bench(args = LIST_LENGTHS, sample_count = 10)]
107+
fn decompress_per_element(bencher: Bencher, list_len: usize) {
108+
let inputs = inputs(list_len);
109+
let mut ctx = SESSION.create_execution_ctx();
110+
111+
bencher.bench_local(|| {
112+
old_fallback(&inputs.values, &inputs.elements)
113+
.execute::<BoolArray>(&mut ctx)
114+
.unwrap()
115+
});
116+
}
117+
118+
fn old_fallback(values: &ZstdArray, elements: &[Scalar]) -> ArrayRef {
119+
let len = values.len();
120+
let false_scalar = Scalar::bool(false, Nullability::NonNullable);
121+
122+
let comparisons = elements
123+
.iter()
124+
.map(|element| {
125+
ConstantArray::new(element.clone(), len)
126+
.into_array()
127+
.binary(values.clone().into_array(), Operator::Eq)
128+
.unwrap()
129+
.fill_null(false_scalar.clone())
130+
.unwrap()
131+
})
132+
.collect();
133+
134+
reduce_or_balanced(comparisons)
135+
}
136+
137+
fn reduce_or_balanced(mut arrays: Vec<ArrayRef>) -> ArrayRef {
138+
while arrays.len() > 1 {
139+
let mut next = Vec::with_capacity(arrays.len().div_ceil(2));
140+
let mut iter = arrays.into_iter();
141+
while let Some(lhs) = iter.next() {
142+
next.push(match iter.next() {
143+
Some(rhs) => lhs.binary(rhs, Operator::Or).unwrap(),
144+
None => lhs,
145+
});
146+
}
147+
arrays = next;
148+
}
149+
150+
arrays.pop().unwrap()
151+
}
152+
153+
fn main() {
154+
LazyLock::force(&SESSION);
155+
divan::main();
156+
}

0 commit comments

Comments
 (0)