Skip to content

Commit 88653d3

Browse files
authored
OnPair: decode straight into the builder's byte storage (#9100)
Decompress value straight into builders storage
1 parent 5a096b5 commit 88653d3

5 files changed

Lines changed: 137 additions & 75 deletions

File tree

‎Cargo.lock‎

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

‎encodings/onpair/src/array.rs‎

Lines changed: 27 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@ use std::fmt::Debug;
55
use std::fmt::Display;
66
use std::fmt::Formatter;
77
use std::hash::Hasher;
8+
use std::mem::MaybeUninit;
89
use std::sync::Arc;
910
use std::sync::OnceLock;
1011

@@ -21,11 +22,9 @@ use vortex_array::ArrayId;
2122
use vortex_array::ArrayParts;
2223
use vortex_array::ArrayRef;
2324
use vortex_array::ArrayView;
24-
use vortex_array::Canonical;
2525
use vortex_array::EqMode;
2626
use vortex_array::ExecutionCtx;
2727
use vortex_array::ExecutionResult;
28-
use vortex_array::IntoArray;
2928
use vortex_array::array_slots;
3029
use vortex_array::buffer::BufferHandle;
3130
use vortex_array::builders::ArrayBuilder;
@@ -53,8 +52,8 @@ use vortex_error::vortex_panic;
5352
use vortex_session::VortexSession;
5453
use vortex_session::registry::CachedId;
5554

55+
use crate::canonical::OnPairDecodePlan;
5656
use crate::canonical::canonicalize_onpair;
57-
use crate::canonical::onpair_decode_bytes;
5857
use crate::canonical::onpair_decode_views;
5958
use crate::decode::collect_widened;
6059
use crate::rules::RULES;
@@ -598,13 +597,12 @@ impl VTable for OnPair {
598597
return result;
599598
}
600599

600+
// The two arms here are every builder a `Utf8`/`Binary` dtype has: all four
601+
// `VarBinBuilder` widths above, and `VarBinViewBuilder` below. There is deliberately no
602+
// canonicalize-then-append fallback — it would decode to a `VarBinView` only for
603+
// `VarBinView::append_to_builder` to reject the same remainder.
601604
let Some(builder) = builder.as_any_mut().downcast_mut::<VarBinViewBuilder>() else {
602-
return array
603-
.array()
604-
.clone()
605-
.execute::<Canonical>(ctx)?
606-
.into_array()
607-
.append_to_builder(builder, ctx);
605+
vortex_bail!("append_to_builder for OnPair requires a variable-binary builder")
608606
};
609607

610608
let next_buffer_index = builder.completed_block_count() + u32::from(builder.in_progress());
@@ -629,7 +627,10 @@ impl VTable for OnPair {
629627
}
630628
}
631629

632-
/// Decodes the values and appends them to `builder`.
630+
/// Decodes the code stream straight into `builder`'s byte storage.
631+
///
632+
/// The offsets are the running sum of the uncompressed lengths the array already stores, so the
633+
/// only work beyond the bulk `try_decode_into` is one prefix sum over them.
633634
fn append_to_varbin<O: OffsetBuilderPType>(
634635
array: ArrayView<'_, OnPair>,
635636
builder: &mut VarBinBuilder<O>,
@@ -638,20 +639,26 @@ fn append_to_varbin<O: OffsetBuilderPType>(
638639
where
639640
usize: AsPrimitive<O>,
640641
{
641-
let (bytes, lengths) = onpair_decode_bytes(array, ctx)?;
642+
let plan = OnPairDecodePlan::new(array, ctx)?;
642643
let validity = array
643644
.array()
644645
.validity()?
645646
.execute_mask(array.array().len(), ctx)?;
646-
match_each_integer_ptype!(lengths.ptype(), |P| {
647-
builder.append_values(
648-
bytes.as_slice(),
649-
lengths.as_slice::<P>().iter().scan(0usize, |end, length| {
650-
*end += AsPrimitive::<usize>::as_(*length);
651-
Some(*end)
652-
}),
653-
&validity,
654-
)
647+
// Built once, outside the ptype match: `append_decoded` takes it as `&mut dyn FnMut`, so
648+
// creating the closure inside each arm would stamp out a shim per length type for no gain.
649+
let mut decode = |out: &mut [MaybeUninit<u8>]| plan.decode_into(out);
650+
match_each_integer_ptype!(plan.lengths.ptype(), |P| {
651+
// SAFETY: `decode_into` initializes exactly the prefix whose length it returns. It needs
652+
// no slack: it derives its bound from the slice it is handed and writes each value exactly.
653+
unsafe {
654+
builder.append_decoded(
655+
plan.total_size,
656+
0,
657+
plan.lengths.as_slice::<P>(),
658+
&validity,
659+
&mut decode,
660+
)
661+
}
655662
})
656663
}
657664

‎encodings/onpair/src/canonical.rs‎

Lines changed: 95 additions & 54 deletions
Original file line numberDiff line numberDiff line change
@@ -6,9 +6,11 @@
66
//!
77
//! [`OnPairArray`]: crate::OnPairArray
88
9+
use std::mem::MaybeUninit;
910
use std::sync::Arc;
1011

1112
use num_traits::AsPrimitive;
13+
use onpair::CompactDictionaryView;
1214
use vortex_array::ArrayRef;
1315
use vortex_array::ArrayView;
1416
use vortex_array::ExecutionCtx;
@@ -23,8 +25,8 @@ use vortex_buffer::Buffer;
2325
use vortex_buffer::ByteBuffer;
2426
use vortex_buffer::ByteBufferMut;
2527
use vortex_error::VortexResult;
28+
use vortex_error::vortex_bail;
2629
use vortex_error::vortex_ensure;
27-
use vortex_error::vortex_err;
2830

2931
use crate::OnPair;
3032
use crate::OnPairArraySlotsExt;
@@ -44,64 +46,103 @@ pub(super) fn canonicalize_onpair(
4446
})
4547
}
4648

49+
pub(crate) struct OnPairDecodePlan<'a> {
50+
codes: Buffer<u16>,
51+
dict: CompactDictionaryView<'a>,
52+
/// Per-row uncompressed lengths, zero for null rows.
53+
pub(crate) lengths: PrimitiveArray,
54+
/// Total decoded size, i.e. the sum of `lengths`.
55+
pub(crate) total_size: usize,
56+
}
57+
58+
impl<'a> OnPairDecodePlan<'a> {
59+
pub(crate) fn new(array: ArrayView<'a, OnPair>, ctx: &mut ExecutionCtx) -> VortexResult<Self> {
60+
let lengths = array
61+
.uncompressed_lengths()
62+
.clone()
63+
.execute::<PrimitiveArray>(ctx)?;
64+
65+
let total_size: usize = match_each_integer_ptype!(lengths.ptype(), |P| {
66+
lengths
67+
.as_slice::<P>()
68+
.iter()
69+
.map(|&l| AsPrimitive::<usize>::as_(l))
70+
.sum()
71+
});
72+
73+
// `codes_offsets` holds the per-row code boundaries and may itself be a
74+
// sliced or filtered view of the original. Its first and last entries
75+
// bound the contiguous run of `codes` belonging to the rows present in
76+
// this array: `slice` keeps the full `codes` child and only narrows
77+
// `codes_offsets` (so `code_start > 0` and/or `code_end < codes.len()`),
78+
// while `filter` rebuilds both children so the window is the whole stream.
79+
// OnPair has no `TakeExecute`, so a reordering take is served from the
80+
// canonical `VarBinView` and never reaches this path. We only need those
81+
// two boundaries, so point-look them up rather than decoding every offset.
82+
let codes_offsets = array.codes_offsets();
83+
let code_start = code_boundary_at(codes_offsets, 0, ctx)?;
84+
let code_end = code_boundary_at(codes_offsets, array.len(), ctx)?;
85+
vortex_ensure!(
86+
code_start <= code_end,
87+
"OnPair codes_offsets must be nondecreasing"
88+
);
89+
vortex_ensure!(
90+
code_end <= array.codes().len(),
91+
"OnPair codes_offsets end {} exceeds codes len {}",
92+
code_end,
93+
array.codes().len()
94+
);
95+
96+
// Slice the `codes` child to that window *before* unpacking it, so a sliced
97+
// array materialises only its own codes rather than the whole column's. The
98+
// contiguous decoder walks `codes` in order and never reads the per-row
99+
// boundaries, so an empty boundary slice is sound.
100+
let codes = collect_widened::<u16>(&array.codes().slice(code_start..code_end)?, ctx)?;
101+
let dict = dict_view(array, ctx)?;
102+
103+
Ok(Self {
104+
codes,
105+
dict,
106+
lengths,
107+
total_size,
108+
})
109+
}
110+
111+
/// Bulk-decodes the whole code stream into `out`, which must hold at least `total_size` bytes.
112+
///
113+
/// Do not reach for `#[inline(always)]` here. `try_decode_into` is monomorphized for
114+
/// `CompactDictionaryView` whichever way this is annotated, and it is far too large to inline
115+
/// either way — it stays an out-of-line call in both. All `always` buys is dropping this
116+
/// wrapper's own frame, one `bl`/`ret` per decoded chunk against a whole-column decode, which
117+
/// `benches/decode.rs::canonicalize_to_varbinview` cannot tell apart from noise.
118+
#[inline]
119+
pub(crate) fn decode_into(&self, out: &mut [MaybeUninit<u8>]) -> VortexResult<usize> {
120+
let written = match onpair::try_decode_into(self.codes.as_slice(), self.dict, out) {
121+
Ok(written) => written,
122+
Err(_) => {
123+
vortex_bail!("OnPair codes decode to more bytes than uncompressed_lengths records")
124+
}
125+
};
126+
127+
vortex_ensure!(
128+
written == self.total_size,
129+
"OnPair codes decoded to {written} bytes but uncompressed_lengths records {}",
130+
self.total_size
131+
);
132+
Ok(written)
133+
}
134+
}
135+
47136
pub(crate) fn onpair_decode_bytes(
48137
array: ArrayView<'_, OnPair>,
49138
ctx: &mut ExecutionCtx,
50139
) -> VortexResult<(ByteBufferMut, PrimitiveArray)> {
51-
let lengths = array
52-
.uncompressed_lengths()
53-
.clone()
54-
.execute::<PrimitiveArray>(ctx)?;
55-
56-
let total_size: usize = match_each_integer_ptype!(lengths.ptype(), |P| {
57-
lengths
58-
.as_slice::<P>()
59-
.iter()
60-
.map(|&l| AsPrimitive::<usize>::as_(l))
61-
.sum()
62-
});
63-
64-
// `codes_offsets` holds the per-row code boundaries and may itself be a
65-
// sliced or filtered view of the original. Its first and last entries
66-
// bound the contiguous run of `codes` belonging to the rows present in
67-
// this array: `slice` keeps the full `codes` child and only narrows
68-
// `codes_offsets` (so `code_start > 0` and/or `code_end < codes.len()`),
69-
// while `filter` rebuilds both children so the window is the whole stream.
70-
// OnPair has no `TakeExecute`, so a reordering take is served from the
71-
// canonical `VarBinView` and never reaches this path. We only need those
72-
// two boundaries, so point-look them up rather than decoding every offset.
73-
let codes_offsets = array.codes_offsets();
74-
let code_start = code_boundary_at(codes_offsets, 0, ctx)?;
75-
let code_end = code_boundary_at(codes_offsets, array.len(), ctx)?;
76-
vortex_ensure!(
77-
code_start <= code_end,
78-
"OnPair codes_offsets must be nondecreasing"
79-
);
80-
vortex_ensure!(
81-
code_end <= array.codes().len(),
82-
"OnPair codes_offsets end {} exceeds codes len {}",
83-
code_end,
84-
array.codes().len()
85-
);
86-
87-
// Slice the `codes` child to that window *before* unpacking it, so a sliced
88-
// array materialises only its own codes rather than the whole column's. The
89-
// contiguous decoder walks `codes` in order and never reads the per-row
90-
// boundaries, so an empty boundary slice is sound.
91-
let codes = collect_widened::<u16>(&array.codes().slice(code_start..code_end)?, ctx)?;
92-
let dict = dict_view(array, ctx)?;
93-
let mut out_bytes = ByteBufferMut::with_capacity(total_size);
94-
let written = onpair::try_decode_into(codes.as_slice(), dict, out_bytes.spare_capacity_mut())
95-
.map_err(|_| {
96-
vortex_err!("OnPair codes decode to more bytes than uncompressed_lengths records")
97-
})?;
98-
vortex_ensure!(
99-
written == total_size,
100-
"OnPair codes decoded to {written} bytes but uncompressed_lengths records {total_size}"
101-
);
102-
// SAFETY: `try_decode_into` initialised exactly `written` bytes.
140+
let plan = OnPairDecodePlan::new(array, ctx)?;
141+
let mut out_bytes = ByteBufferMut::with_capacity(plan.total_size);
142+
let written = plan.decode_into(out_bytes.spare_capacity_mut())?;
143+
// SAFETY: `decode_into` initialised exactly `written` bytes.
103144
unsafe { out_bytes.set_len(written) };
104-
Ok((out_bytes, lengths))
145+
Ok((out_bytes, plan.lengths))
105146
}
106147

107148
pub(crate) fn onpair_decode_views(

‎vortex-arrow/Cargo.toml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,7 @@ divan = { workspace = true }
4242
rstest = { workspace = true }
4343
vortex-array = { workspace = true, features = ["_test-harness"] }
4444
vortex-fsst = { workspace = true }
45+
vortex-onpair = { workspace = true }
4546
vortex-zstd = { workspace = true }
4647

4748
[[bench]]

‎vortex-arrow/benches/to_arrow.rs‎

Lines changed: 13 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,8 @@ use vortex_arrow::dtype::ToArrowType as _;
4242
use vortex_fsst::fsst_compress;
4343
use vortex_fsst::fsst_train_compressor;
4444
use vortex_mask::Mask;
45+
use vortex_onpair::DEFAULT_CONFIG;
46+
use vortex_onpair::onpair_compress;
4547
use vortex_session::VortexSession;
4648
use vortex_zstd::Zstd;
4749

@@ -53,6 +55,7 @@ fn main() {
5355
static SESSION: LazyLock<VortexSession> = LazyLock::new(|| {
5456
let session = array_session();
5557
vortex_fsst::initialize(&session);
58+
vortex_onpair::initialize(&session);
5659
session.arrays().register(Zstd);
5760
session
5861
});
@@ -122,6 +125,7 @@ fn ArrowExportVTable_to_arrow_field(bencher: Bencher) {
122125
enum StringEncoding {
123126
View,
124127
Fsst,
128+
OnPair,
125129
Zstd,
126130
Dict,
127131
DictFsst,
@@ -140,6 +144,7 @@ enum StringEncoding {
140144
const STRING_ENCODINGS: &[StringEncoding] = &[
141145
StringEncoding::View,
142146
StringEncoding::Fsst,
147+
StringEncoding::OnPair,
143148
StringEncoding::Zstd,
144149
StringEncoding::Dict,
145150
StringEncoding::DictFsst,
@@ -156,12 +161,13 @@ const STRING_ENCODINGS: &[StringEncoding] = &[
156161
/// Encodings whose `append_to_builder` the builder benchmarks reach directly.
157162
///
158163
/// The Arrow export cannot stand in for these: `execute_until` stops at the first canonical array,
159-
/// so a bare FSST/Zstd root is canonicalized to `VarBinView` before any builder sees it.
164+
/// so a bare FSST/OnPair/Zstd root is canonicalized to `VarBinView` before any builder sees it.
160165
/// Only `Chunked`, `Constant` and `VarBin` roots reach an encoding's own `append_to_builder` that
161166
/// way, whereas the scan machinery appends encoded arrays into a builder directly.
162167
const BUILDER_STRING_ENCODINGS: &[StringEncoding] = &[
163168
StringEncoding::View,
164169
StringEncoding::Fsst,
170+
StringEncoding::OnPair,
165171
StringEncoding::Zstd,
166172
StringEncoding::Dict,
167173
StringEncoding::ChunkedFsst,
@@ -250,6 +256,12 @@ fn string_array(encoding: StringEncoding) -> ArrayRef {
250256
structured_strings(OFFSET_STRING_ROWS).into_array(),
251257
&mut ctx,
252258
),
259+
StringEncoding::OnPair => onpair_compress(
260+
&structured_strings(OFFSET_STRING_ROWS).into_array(),
261+
DEFAULT_CONFIG,
262+
&mut ctx,
263+
)
264+
.unwrap(),
253265
StringEncoding::Zstd => {
254266
let source = structured_strings(OFFSET_STRING_ROWS);
255267
Zstd::from_var_bin_view_without_dict(&source, 3, 8_192, &mut ctx)

0 commit comments

Comments
 (0)