Skip to content

Commit cb613ac

Browse files
authored
Preserve DuckDB dictionaries across run-end chunks (vortex-data#11378)
## Summary Follow-up to vortex-data#11375 and [the DuckDB exporter review](vortex-data#11360 (comment)). Chunked run-end inputs currently lose their cached dictionary when an output batch crosses a chunk boundary. Exposing the existing batch codes through `DictionaryParts` lets those ranges reuse the values dictionary, including ranges shared with ordinary dictionary chunks. ## Changes Keep the run-end specialization because routing through `to_dict()` would make the generic exporter materialize the entire codes array. The existing fill loop also remains: using `slice_relative_ends` increased standalone single-row-run export time in all five trial pairs (median paired ratio 1.064). Empty inputs now avoid run lookup and values conversion, and zero-length requests avoid scalar access. Constant batches include requests ending exactly at a run boundary. Compact inline regressions cover empty requests, slice offsets, exact run boundaries, nulls, successive batches, and shared or different dictionaries across chunks. The existing null and chunked-values tests remain. Measurements on `702fd58dea`, before the test and module cleanup, showed about 15% lower batch-export time for single-row runs and 16% for long runs. Rust allocations per export loop fall from 146 to 112 and from 212 to 188, respectively. Standalone export and construction timings show no clear material change. Native DuckDB allocations were not measured. <details> <summary>Validation</summary> - After cleanup, `cargo nextest run -p vortex-duckdb -E 'test(exporter::run_end::)'`: 7 passed, 265 outside the filter. - Before cleanup, the full exporter filter passed all 80 tests. - `cargo clippy -p vortex-duckdb --all-targets --all-features -- -D warnings`: passed. - `cargo +nightly-2026-09-10 fmt -p vortex-duckdb`: passed. - Commit hook: workspace Rust and TOML formatting passed. - Pre-push hook: DCO checks and workspace Clippy with all targets, all features, and warnings denied passed. - Broader runtime suites and doctests were not run. </details> <details> <summary>Benchmark methodology and full results</summary> Baseline: `b367941e9d490b4a19ef9bdd6653f63d712c581f` with the same benchmark harness. Candidate: `702fd58dea3c0eeb214d590b3cc6d6b5b3c89c9b`. This comparison isolates the follow-up from the Arrow extension/property stack. The [measurement harness](https://github.com/vortex-data/vortex/blob/702fd58dea3c0eeb214d590b3cc6d6b5b3c89c9b/vortex-duckdb/benches/run_end_export.rs) and its Cargo target remain available in that measured commit. The permanent benchmark target was removed during review, along with duplicate test setup and the module split. The production algorithm is unchanged, but these measurements were not rerun after the file move. macOS 27.0.1, aarch64, rustc 1.99.1, LLVM 23.1.1, Cargo bench profile, and DuckDB 2.0.0. Build both revisions with `cargo bench -p vortex-duckdb --bench run_end_export --no-run`. Run their saved executables with `--bench --sample-count 300 --sample-size 20 --color never` in five pairs, alternating baseline/candidate order. The table shows the median of each executable's five run medians, plus the median of the five paired candidate/baseline ratios. These two aggregations need not agree exactly. Inputs are non-null i64 run values with run lengths 1 or 8192. Short-run sources have 16,383 runs, and long-run sources have eight. Chunked inputs repeat the same source four times. Every input is sliced from row 17 to 13 rows before its end, so exports span multiple batches and chunk boundaries fall inside output batches. Fixtures execute the slice to its encoded representation before exporter construction. Construction uses a fresh conversion cache per iteration. Batch export uses a warm cache and excludes exporter construction and data-chunk creation. `AllocProfiler<MiMalloc>` counts Rust allocations in the measured region, including its timing overhead. It does not count native DuckDB allocations. Neither `xctrace` nor `heaptrack` is available on this machine. Allocation figures below are allocation counts and requested bytes, not peak resident memory. | Phase | Input | Run length | Baseline (us) | Candidate (us) | Paired ratio | All five paired ratios | | --- | --- | ---: | ---: | ---: | ---: | --- | | batches | standalone | 1 | 14.02 | 13.51 | 0.961 | 0.961, 0.954, 0.968, 0.949, 1.028 | | batches | standalone | 8192 | 3.349 | 3.293 | 0.980 | 0.866, 1.007, 1.015, 0.926, 0.980 | | batches | shared chunks | 1 | 48.3 | 41.15 | 0.851 | 0.849, 0.851, 0.858, 0.852, 0.850 | | batches | shared chunks | 8192 | 19.74 | 16.57 | 0.839 | 0.839, 0.839, 0.833, 0.864, 0.832 | | construct | standalone | 1 | 0.8631 | 0.8464 | 0.981 | 0.951, 0.979, 0.984, 0.981, 1.016 | | construct | standalone | 8192 | 0.7922 | 0.7714 | 0.981 | 0.934, 0.982, 0.981, 0.966, 1.004 | | construct | shared chunks | 1 | 51.69 | 51.68 | 1.000 | 1.012, 0.999, 0.997, 1.000, 1.000 | | construct | shared chunks | 8192 | 12.9 | 12.88 | 0.998 | 1.002, 0.997, 0.998, 0.998, 0.998 | | Phase | Input | Run length | Baseline Rust allocations | Candidate Rust allocations | Baseline bytes | Candidate bytes | | --- | --- | ---: | ---: | ---: | ---: | ---: | | Batches | Standalone | 1 | 0 | 0 | 0 | 0 | | Batches | Standalone | 8192 | 0 | 0 | 0 | 0 | | Batches | Shared chunks | 1 | 146 | 112 | 193.1 KB | 130.5 KB | | Batches | Shared chunks | 8192 | 212 | 188 | 200.2 KB | 139.3 KB | | Construct | Standalone | 1 | 5 | 5 | 308 B | 308 B | | Construct | Standalone | 8192 | 5 | 5 | 308 B | 308 B | | Construct | Shared chunks | 1 | 32 | 32 | 265.8 KB | 265.8 KB | | Construct | Shared chunks | 8192 | 22 | 22 | 1.05 MB | 1.05 MB | The shared-chunk batch timing improved in every pair. Standalone controls and construction moved much less, and the standalone long-run ratios varied in direction. No compiler-output analysis was performed, so those small movements are not attributed to a particular code-generation change. These microbenchmarks do not establish an end-to-end query speedup. </details> --------- Signed-off-by: Connor Tsui <[email protected]>
1 parent 49acec0 commit cb613ac

2 files changed

Lines changed: 214 additions & 65 deletions

File tree

‎vortex-duckdb/src/exporter/mod.rs‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -157,7 +157,7 @@ impl ArrayExporter {
157157
/// the offset, len and `WritableVector` as options. Not sure what it should return though?
158158
/// This would allow Vortex extension authors to plug into the DuckDB exporter system.
159159
pub trait ColumnExporter: 'static {
160-
/// The dictionary parts of this exporter, if it exports DuckDB dictionary vectors.
160+
/// The dictionary parts of this exporter, if it can export DuckDB dictionary vectors.
161161
///
162162
/// A chunked exporter uses them to export a range across chunks as one dictionary vector.
163163
fn as_dictionary(&self) -> Option<&dyn DictionaryParts> {
@@ -175,6 +175,9 @@ pub trait ColumnExporter: 'static {
175175
}
176176

177177
/// The values and codes of an exporter that emits DuckDB dictionary vectors.
178+
///
179+
/// Codes can be generated per request rather than stored for the whole array. This capability also
180+
/// applies when the exporter uses a constant vector for a request contained in one run.
178181
pub trait DictionaryParts {
179182
/// The DuckDB vector of the dictionary values.
180183
fn values(&self) -> &ReusableDict;
@@ -183,6 +186,9 @@ pub trait DictionaryParts {
183186
fn values_key(&self) -> usize;
184187

185188
/// Write the codes of rows `offset..offset + codes.len()` into `codes`.
189+
///
190+
/// The offset is relative to the exported array, including any slice. The range must lie within
191+
/// that array, and every code must index [`Self::values`], including codes for null rows.
186192
fn write_codes(&self, offset: usize, codes: &mut [u32]);
187193
}
188194

Lines changed: 207 additions & 64 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,20 @@
11
// SPDX-License-Identifier: Apache-2.0
22
// SPDX-FileCopyrightText: Copyright the Vortex contributors
33

4+
//! Batch-sized run selections over a cached DuckDB values dictionary.
5+
//!
6+
//! [`DictionaryParts`] lets the chunked exporter join run-end and dictionary chunks that share
7+
//! values without flattening them. Codes are expanded only for the requested batch. Routing through
8+
//! [`RunEndArray::to_dict`] would make the generic dictionary exporter materialize all codes at setup.
9+
410
use std::marker::PhantomData;
511

612
use vortex::array::ArrayRef;
13+
use vortex::array::Canonical;
714
use vortex::array::ExecutionCtx;
815
use vortex::array::IntoArray;
916
use vortex::array::arrays::PrimitiveArray;
1017
use vortex::array::match_each_integer_ptype;
11-
use vortex::array::search_sorted::SearchSorted;
12-
use vortex::array::search_sorted::SearchSortedSide;
1318
use vortex::dtype::IntegerPType;
1419
use vortex::encodings::runend::RunEndArray;
1520
use vortex::encodings::runend::RunEndArrayExt;
@@ -22,17 +27,18 @@ use crate::duckdb::ReusableDict;
2227
use crate::duckdb::SelectionVector;
2328
use crate::duckdb::VectorRef;
2429
use crate::exporter::ColumnExporter;
30+
use crate::exporter::DictionaryParts;
2531
use crate::exporter::cache::ConversionCache;
2632
use crate::exporter::cached_values_dict;
2733
use crate::exporter::canonical;
2834

29-
/// We export run-end arrays to a DuckDB dictionary vector. Values are exported
30-
/// into a ReusableDict with SelectionVector applied in export().
35+
/// Keeps the values dictionary cached while generating selections for each requested batch.
3136
struct RunEndExporter<E: IntegerPType> {
3237
ends: PrimitiveArray,
3338
ends_type: PhantomData<E>,
3439
values: ArrayRef,
3540
values_dict: ReusableDict,
41+
/// Added to request offsets because sliced run ends retain their source coordinates.
3642
run_end_offset: usize,
3743
}
3844

@@ -42,8 +48,11 @@ pub(crate) fn new_exporter_with_flatten(
4248
ctx: &mut ExecutionCtx,
4349
flatten: bool,
4450
) -> VortexResult<Box<dyn ColumnExporter>> {
45-
// Our canonicalization is faster than creating a dictionary vector and
46-
// letting duckdb flatten it for us.
51+
if array.is_empty() {
52+
return canonical::new_exporter(Canonical::empty(array.dtype()).into_array(), cache, ctx);
53+
}
54+
55+
// Canonicalize directly to avoid building a dictionary that DuckDB would immediately flatten.
4756
if flatten {
4857
return canonical::new_exporter(array.into_array(), cache, ctx);
4958
}
@@ -65,107 +74,160 @@ pub(crate) fn new_exporter_with_flatten(
6574
})
6675
}
6776

77+
impl<E: IntegerPType> RunEndExporter<E> {
78+
/// Finds the run containing an absolute row offset. Run ends are exclusive.
79+
///
80+
/// The offset must refer to an existing row, rather than the end of an empty request.
81+
fn first_run(&self, offset: usize) -> usize {
82+
let offset =
83+
E::from_usize(offset).vortex_expect("the request offset fits the run-end type");
84+
self.ends
85+
.as_slice::<E>()
86+
.partition_point(|&end| end <= offset)
87+
}
88+
89+
/// Fills a non-empty request with indices into the original values child.
90+
///
91+
/// `offset` is absolute, and `first_run` must be the index returned by [`Self::first_run`].
92+
fn write_run_codes(&self, offset: usize, first_run: usize, codes: &mut [u32]) {
93+
let mut position =
94+
E::from_usize(offset).vortex_expect("the request offset fits the run-end type");
95+
let end_offset = position
96+
+ E::from_usize(codes.len()).vortex_expect("the request length fits the run-end type");
97+
let mut remaining = codes;
98+
99+
for (index, &end) in self.ends.as_slice::<E>()[first_run..].iter().enumerate() {
100+
let next_end = end.min(end_offset);
101+
let run_len = (next_end - position)
102+
.to_usize()
103+
.vortex_expect("run length fits usize");
104+
let code = u32::try_from(first_run + index).vortex_expect("run index exceeds u32");
105+
remaining[..run_len].fill(code);
106+
remaining = &mut remaining[run_len..];
107+
if remaining.is_empty() {
108+
return;
109+
}
110+
position = next_end;
111+
}
112+
113+
assert!(
114+
remaining.is_empty(),
115+
"run ends must cover the requested range"
116+
);
117+
}
118+
}
119+
120+
impl<E: IntegerPType> DictionaryParts for RunEndExporter<E> {
121+
fn values(&self) -> &ReusableDict {
122+
&self.values_dict
123+
}
124+
125+
fn values_key(&self) -> usize {
126+
self.values.addr()
127+
}
128+
129+
fn write_codes(&self, offset: usize, codes: &mut [u32]) {
130+
if codes.is_empty() {
131+
return;
132+
}
133+
134+
let offset = self.run_end_offset + offset;
135+
self.write_run_codes(offset, self.first_run(offset), codes);
136+
}
137+
}
138+
68139
impl<E: IntegerPType> ColumnExporter for RunEndExporter<E> {
140+
fn as_dictionary(&self) -> Option<&dyn DictionaryParts> {
141+
Some(self)
142+
}
143+
69144
fn export(
70145
&self,
71146
offset: usize,
72147
len: usize,
73148
vector: &mut VectorRef,
74149
ctx: &mut ExecutionCtx,
75150
) -> VortexResult<()> {
76-
let ends_slice = self.ends.as_slice::<E>();
77-
78-
// Adjust offset to account for the run-end offset.
79-
let mut offset = E::from_usize(self.run_end_offset + offset)
80-
.vortex_expect("RunEndExporter::export: offset is not a valid value");
81-
// Compute the final end offset.
82-
let end_offset = offset + E::from_usize(len).vortex_expect("len is not end type");
83-
84-
// Find the run that contains the start offset.
85-
let start_run_idx = ends_slice
86-
.search_sorted(&offset, SearchSortedSide::Right)?
87-
.to_ends_index(ends_slice.len());
88-
89-
// Find the final run in case we can short-circuit and return a constant vector.
90-
let end_run_idx = ends_slice
91-
.search_sorted(&end_offset, SearchSortedSide::Right)?
92-
.to_ends_index(ends_slice.len());
93-
94-
if start_run_idx == end_run_idx {
95-
// NOTE(ngates): would be great if we could just export and set type == CONSTANT
96-
// self.values_exporter.export(start_run_idx, 1, vector, cache);
97-
let constant = self.values.execute_scalar(start_run_idx, ctx)?;
98-
let value = constant.try_to_duckdb_scalar()?;
99-
vector.reference_value(&value);
151+
if len == 0 {
100152
return Ok(());
101153
}
102154

103-
// Build up a selection vector
104-
let mut sel_vec = SelectionVector::with_capacity(len);
105-
let mut sel_vec_slice = unsafe { sel_vec.as_slice_mut(len) };
106-
107-
for (run_idx, &next_end) in ends_slice[start_run_idx..=end_run_idx].iter().enumerate() {
108-
let next_end = next_end.min(end_offset);
109-
let run_len = (next_end - offset)
110-
.to_usize()
111-
.vortex_expect("run_len is usize");
112-
113-
let global_run_idx =
114-
u32::try_from(start_run_idx + run_idx).vortex_expect("run index exceeds u32");
115-
sel_vec_slice[..run_len].fill(global_run_idx);
116-
sel_vec_slice = &mut sel_vec_slice[run_len..];
155+
let offset = self.run_end_offset + offset;
156+
let first_run = self.first_run(offset);
157+
let end =
158+
E::from_usize(offset + len).vortex_expect("the request end fits the run-end type");
117159

118-
offset = next_end;
160+
// The request end is exclusive, so equality still leaves every row inside this run.
161+
if end <= self.ends.as_slice::<E>()[first_run] {
162+
let constant = self.values.execute_scalar(first_run, ctx)?;
163+
let value = constant.try_to_duckdb_scalar()?;
164+
vector.reference_value(&value);
165+
return Ok(());
119166
}
120-
debug_assert!(sel_vec_slice.is_empty());
121167

122-
vector.reuse_dictionary(&self.values_dict, &sel_vec, len);
168+
let mut selection = SelectionVector::with_capacity(len);
169+
// SAFETY: the selection has capacity for `len` entries. The validated run ends cover the
170+
// requested range, and write_run_codes fills every entry before DuckDB reads the selection.
171+
let codes = unsafe { selection.as_slice_mut(len) };
172+
self.write_run_codes(offset, first_run, codes);
173+
vector.reuse_dictionary(&self.values_dict, &selection, len);
174+
123175
Ok(())
124176
}
125177
}
126178

127179
#[cfg(test)]
128180
mod tests {
181+
use rstest::rstest;
182+
use vortex::array::ArrayRef;
129183
use vortex::array::IntoArray;
130184
use vortex::array::VortexSessionExecute;
131185
use vortex::array::arrays::ChunkedArray;
186+
use vortex::array::arrays::DictArray;
132187
use vortex::array::arrays::PrimitiveArray;
133188
use vortex::array::arrays::StructArray;
189+
use vortex::buffer::Buffer;
134190
use vortex::buffer::buffer;
135191
use vortex::encodings::runend::RunEnd;
136192
use vortex::error::VortexResult;
137193

138194
use crate::SESSION;
139-
use crate::cpp::duckdb_type::DUCKDB_TYPE_INTEGER;
140195
use crate::duckdb::DataChunk;
141196
use crate::duckdb::LogicalType;
142197
use crate::exporter::ArrayExporter;
143198
use crate::exporter::ConversionCache;
144199
use crate::exporter::new_array_exporter;
145200

201+
#[track_caller]
202+
fn check_exports(array: ArrayRef, requests: &[(usize, usize, &str)]) -> VortexResult<()> {
203+
let mut ctx = SESSION.create_execution_ctx();
204+
let exporter = new_array_exporter(array, &ConversionCache::default(), &mut ctx)?;
205+
let mut chunk = DataChunk::new([LogicalType::int32()]);
206+
207+
for &(offset, len, expected) in requests {
208+
chunk.reset();
209+
exporter.export(offset, len, chunk.get_vector_mut(0), &mut ctx)?;
210+
chunk.set_len(len);
211+
assert_eq!(
212+
String::try_from(&*chunk)?,
213+
format!("Chunk - [1 Columns]\n{expected}\n")
214+
);
215+
}
216+
217+
Ok(())
218+
}
219+
146220
#[test]
147221
fn test_one_chunk_null() -> VortexResult<()> {
148222
let mut ctx = SESSION.create_execution_ctx();
149223
let source = vec![Some(0u32), Some(1), None, Some(3), None];
150224
let array = PrimitiveArray::from_option_iter(source);
151225
let array = RunEnd::encode(array.into_array(), &mut ctx)?;
152226

153-
let mut chunk = DataChunk::new([LogicalType::new(DUCKDB_TYPE_INTEGER)]);
154-
new_array_exporter(array.into_array(), &ConversionCache::default(), &mut ctx)?.export(
155-
0,
156-
5,
157-
chunk.get_vector_mut(0),
158-
&mut ctx,
159-
)?;
160-
chunk.set_len(5);
161-
let chunk_str = String::try_from(&*chunk)?;
162-
assert_eq!(
163-
chunk_str,
164-
r#"Chunk - [1 Columns]
165-
- DICTIONARY INTEGER: 5 = [ 0, 1, NULL, 3, NULL]
166-
"#
167-
);
168-
Ok(())
227+
check_exports(
228+
array.into_array(),
229+
&[(0, 5, "- DICTIONARY INTEGER: 5 = [ 0, 1, NULL, 3, NULL]")],
230+
)
169231
}
170232

171233
#[test]
@@ -191,4 +253,85 @@ mod tests {
191253
assert!(!exporter.export(&mut chunk, None)?);
192254
Ok(())
193255
}
256+
257+
#[test]
258+
fn sliced_batches_keep_run_boundaries() -> VortexResult<()> {
259+
let mut ctx = SESSION.create_execution_ctx();
260+
let array = RunEnd::try_new_offset_length(
261+
buffer![3u32, 5, 8].into_array(),
262+
PrimitiveArray::from_option_iter([Some(10i32), None, Some(30)]).into_array(),
263+
2,
264+
5,
265+
&mut ctx,
266+
)?;
267+
268+
check_exports(
269+
array.into_array(),
270+
&[
271+
(0, 1, "- CONSTANT INTEGER: 1 = [ 10]"), // Exact first run end.
272+
(1, 2, "- CONSTANT INTEGER: 2 = [ NULL]"), // Exact null run.
273+
(2, 3, "- DICTIONARY INTEGER: 3 = [ NULL, 30, 30]"), // Clipped batch.
274+
(5, 0, "- FLAT INTEGER: 0 = [ ]"), // Empty request at the end.
275+
],
276+
)
277+
}
278+
279+
#[test]
280+
fn empty_arrays_do_not_cache_values() -> VortexResult<()> {
281+
let mut ctx = SESSION.create_execution_ctx();
282+
let values = buffer![10i32].into_array();
283+
let retained =
284+
RunEnd::try_new_offset_length(buffer![3u32].into_array(), values, 3, 0, &mut ctx)?;
285+
let empty = RunEnd::try_new(
286+
Buffer::<u32>::empty().into_array(),
287+
Buffer::<i32>::empty().into_array(),
288+
&mut ctx,
289+
)?;
290+
291+
for array in [empty, retained] {
292+
let cache = ConversionCache::default();
293+
let exporter = new_array_exporter(array.into_array(), &cache, &mut ctx)?;
294+
let mut chunk = DataChunk::new([LogicalType::int32()]);
295+
exporter.export(0, 0, chunk.get_vector_mut(0), &mut ctx)?;
296+
assert!(cache.dict_cache.is_empty());
297+
}
298+
299+
Ok(())
300+
}
301+
302+
#[rstest]
303+
#[case::runend(false, true)]
304+
#[case::dictionary(true, true)]
305+
#[case::different_values(false, false)]
306+
fn chunk_boundaries(#[case] dictionary: bool, #[case] shared: bool) -> VortexResult<()> {
307+
let mut ctx = SESSION.create_execution_ctx();
308+
let values = PrimitiveArray::from_option_iter([Some(10i32), None, Some(30)]).into_array();
309+
let first = RunEnd::try_new_offset_length(
310+
buffer![2u32, 4, 6].into_array(),
311+
values.clone(),
312+
2,
313+
4,
314+
&mut ctx,
315+
)?
316+
.into_array();
317+
let next_values = if shared {
318+
values
319+
} else {
320+
PrimitiveArray::from_option_iter([Some(10i32), None, Some(30)]).into_array()
321+
};
322+
let second = if dictionary {
323+
DictArray::try_new(buffer![0u32, 1, 1, 2].into_array(), next_values)?.into_array()
324+
} else {
325+
RunEnd::try_new(buffer![1u32, 3, 4].into_array(), next_values, &mut ctx)?.into_array()
326+
};
327+
let dtype = first.dtype().clone();
328+
let array = ChunkedArray::try_new(vec![first, second], dtype)?.into_array();
329+
let crossing = if shared {
330+
"- DICTIONARY INTEGER: 6 = [ NULL, 30, 30, 10, NULL, NULL]"
331+
} else {
332+
"- FLAT INTEGER: 6 = [ NULL, 30, 30, 10, NULL, NULL]"
333+
};
334+
335+
check_exports(array, &[(1, 6, crossing)])
336+
}
194337
}

0 commit comments

Comments
 (0)