Skip to content

Commit 00130bd

Browse files
perf(scan): merge narrow splits at boundaries only some fields of a struct have (#67)
Fixes #61. ## Problem - A scan splits a file wherever any column's chunk ends, and a split decodes the whole chunk of every column it overlaps. - When a struct's fields chunk at unrelated rows, as list elements and dictionary-encoded columns of a wide nested file do, the union of their boundaries holds spans of a few dozen rows. - Successive splits then each decode the same chunks of the other fields. On a 180 MB list-layout file, a full scan held 3.6 GiB of native memory, and one 176-row output array referenced 42 MB. ## Change - **The struct reader marks soft boundaries.** These are boundaries that only some of its fields have. Each field registers into its own `RowSplits`, and the struct takes their union, marking any boundary not every field has as soft. A single-field struct registers exactly as before. - **`SplitBy::LayoutSubSplitting` merges spans ending at a soft boundary** until they reach `DEFAULT_MIN_SPLIT_ROWS` (8,192, the writer's row block), or `max_rows` if that is smaller. It runs before the existing sub-division of wide spans. - **Hard boundaries are never merged.** These are boundaries every field has, and those registered by layouts above the struct, such as top-level chunk ends. Files whose columns chunk alike split as before. ## Effect Full scan of one file, with Arrow conversion as JNI does it. Live native bytes are measured with a counting allocator: | | Splits | Peak live | Time | Bytes requested | |---|---|---|---|---| | List layout, 180 MB, before | 139 (smallest 70 rows) | 3.57 GiB | 1.7 s | 6.2 GB | | List layout, 180 MB, after | 60 (smallest 8,192 rows) | **1.10 GiB** | **0.6 s** | 0.99 GB | | Default layout, 111 MB, before | 59 | 224 MiB | 0.2 s | | | Default layout, 111 MB, after | 48 | 224 MiB | 0.2 s | | ## Tests - **Struct reader** (real layouts written with `RepartitionStrategy`): - fields chunked every 1,000 and 3,000 rows mark only the unshared boundaries soft; - the same struct under a top-level chunked layout keeps the chunk end hard; - `LayoutSubSplitting` merges soft boundaries and preserves shared and validity boundaries, for nullable and non-nullable structs. - **`merge_small_spans`:** unit cases plus 1,000 generated cases checking endpoints, hard boundaries, exact coverage, minimum spans at retained soft boundaries, and subsequent subdivision. - The nullable integration regression failed before the validity-boundary fix. - **Checks:** 836 `vortex-layout` library tests; all-target, all-feature Clippy for `vortex-layout` and `vortex-file` with `-D warnings`; pinned Rust formatting; Java Spotless; full `./gradlew build --no-parallel --max-workers=1` including JNI and Spark checks; patch whitespace. All passed. The full Rust workspace suite was not rerun locally; Linux musl CI passed the workspace tests. ## Review follow-up - Compute the shared-boundary intersection once instead of searching every field for every boundary. The existing 256-column split-collection debug benchmark's warm median fell from about 338 ms to 3 ms. - Preserve inherited soft marks while keeping this struct's validity boundaries hard, including where they overlap a soft data-field boundary. - Move soft marks when appending split sets instead of cloning their buffer. ## Not done here - The minimum is a row count. Rows with many list elements are larger than rows with few, so a byte-based minimum would be more precise. - An earlier variant measured less memory at 16,384 rows; the minimum isn't tuned beyond 8,192. 🤖 Generated with [Claude Code](https://claude.com/claude-code) --------- Signed-off-by: Christopher Wirt <[email protected]> Co-authored-by: Claude Opus 5.5 <[email protected]>
1 parent 1aa2ad7 commit 00130bd

4 files changed

Lines changed: 368 additions & 12 deletions

File tree

‎vortex-file/benches/split_collection.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -55,7 +55,7 @@ fn main() {
5555
const ROWS_PER_CHUNK: usize = 1024;
5656

5757
/// (columns, chunks) configurations.
58-
const CONFIGS: &[(usize, usize)] = &[(16, 64)];
58+
const CONFIGS: &[(usize, usize)] = &[(16, 64), (256, 64)];
5959

6060
static RUNTIME: LazyLock<tokio::runtime::Runtime> = LazyLock::new(|| {
6161
tokio::runtime::Builder::new_current_thread()

‎vortex-layout/src/layouts/struct_/reader.rs‎

Lines changed: 193 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -523,15 +523,54 @@ impl LayoutReader for StructReader {
523523
split_range: &SplitRange,
524524
splits: &mut RowSplits,
525525
) -> VortexResult<()> {
526-
// Register splits for the validity child, if there is one
527-
if let Some(validity_ref) = self.validity()? {
528-
validity_ref.register_splits(field_mask, split_range, splits)?;
529-
}
526+
// Validity boundaries must stay hard even when they overlap a soft data-field boundary.
527+
let validity_boundaries = if let Some(validity_ref) = self.validity()? {
528+
let mut validity_splits = RowSplits::new_capacity(16);
529+
validity_ref.register_splits(field_mask, split_range, &mut validity_splits)?;
530+
validity_splits.into_sorted_deduped()
531+
} else {
532+
Vec::new()
533+
};
534+
splits.extend_ascending(validity_boundaries.iter().copied());
530535

536+
// Each field's boundaries, kept apart so the ones only some fields have can be marked soft.
537+
let mut fields: Vec<RowSplits> = Vec::new();
531538
self.layout.matching_fields(field_mask, |mask, idx| {
539+
let mut field = RowSplits::new_capacity(16);
532540
self.field_reader_by_index(idx)?
533-
.register_splits(&[mask], split_range, splits)
541+
.register_splits(&[mask], split_range, &mut field)?;
542+
fields.push(field);
543+
Ok(())
534544
})?;
545+
let mut field_splits = RowSplits::new_capacity(0);
546+
if let [field] = &mut fields[..] {
547+
field_splits = std::mem::replace(field, RowSplits::new_capacity(0));
548+
} else if !fields.is_empty() {
549+
let fields: Vec<(Vec<u64>, Vec<u64>)> = fields
550+
.into_iter()
551+
.map(RowSplits::into_sorted_deduped_with_soft)
552+
.collect();
553+
// Intersect once; checking every field for every boundary is quadratic in field count.
554+
let mut shared = fields[0].0.clone();
555+
for (boundaries, _) in &fields[1..] {
556+
shared.retain(|row| boundaries.binary_search(row).is_ok());
557+
if shared.is_empty() {
558+
break;
559+
}
560+
}
561+
for (boundaries, soft) in fields.iter() {
562+
field_splits.extend_ascending(boundaries.iter().copied());
563+
field_splits.mark_soft(soft.iter().copied());
564+
field_splits.mark_soft(
565+
boundaries
566+
.iter()
567+
.copied()
568+
.filter(|row| shared.binary_search(row).is_err()),
569+
);
570+
}
571+
}
572+
field_splits.remove_soft(&validity_boundaries);
573+
splits.append(field_splits);
535574

536575
// In the case of an empty struct, we need to register the end split. Pushed last so it
537576
// extends the final field's ascending run rather than starting a run of its own.
@@ -679,7 +718,9 @@ mod tests {
679718
use vortex_array::assert_arrays_eq;
680719
use vortex_array::assert_nth_scalar;
681720
use vortex_array::dtype::DType;
721+
use vortex_array::dtype::FieldMask;
682722
use vortex_array::dtype::FieldName;
723+
use vortex_array::dtype::FieldPath;
683724
use vortex_array::dtype::Nullability;
684725
use vortex_array::dtype::PType;
685726
use vortex_array::dtype::RESERVED_VALIDITY_FIELD_NAME;
@@ -712,11 +753,16 @@ mod tests {
712753
use crate::LayoutReaderRef;
713754
use crate::LayoutRef;
714755
use crate::LayoutStrategy;
756+
use crate::RowSplits;
757+
use crate::SplitRange;
715758
use crate::layouts::chunked::writer::ChunkedLayoutStrategy;
716759
use crate::layouts::flat::writer::FlatLayoutStrategy;
760+
use crate::layouts::repartition::RepartitionStrategy;
761+
use crate::layouts::repartition::RepartitionWriterOptions;
717762
use crate::layouts::table::TableStrategy;
718763
use crate::layouts::zoned::writer::ZonedLayoutOptions;
719764
use crate::layouts::zoned::writer::ZonedStrategy;
765+
use crate::scan::split_by::SplitBy;
720766
use crate::segments::CountingSegmentSource;
721767
use crate::segments::SegmentFuture;
722768
use crate::segments::SegmentId;
@@ -803,6 +849,148 @@ mod tests {
803849
(segments, layout)
804850
}
805851

852+
/// A leaf writer that chunks every `rows` rows.
853+
fn chunked_every(rows: usize) -> Arc<dyn LayoutStrategy> {
854+
Arc::new(RepartitionStrategy::new(
855+
ChunkedLayoutStrategy::new(FlatLayoutStrategy::default()),
856+
RepartitionWriterOptions {
857+
block_size_minimum: 0,
858+
block_len_multiple: rows,
859+
block_size_target: None,
860+
canonicalize: false,
861+
},
862+
))
863+
}
864+
865+
/// A struct of 12,000 rows whose field `a` chunks every 1,000 rows and `b` every 3,000,
866+
/// written in `pieces` pushes. With `chunked`, the struct is itself a chunk of a chunked layout
867+
/// per push.
868+
fn misaligned_struct_layout(
869+
pieces: usize,
870+
chunked: bool,
871+
nullable: bool,
872+
) -> (Arc<dyn SegmentSource>, LayoutRef) {
873+
let ctx = ArrayContext::empty();
874+
let segments = Arc::new(TestSegments::default());
875+
let (ptr, eof) = SequenceId::root().split();
876+
let table = TableStrategy::new(chunked_every(2000), chunked_every(1000))
877+
.with_field_writer(FieldPath::from_name("b"), chunked_every(3000));
878+
let strategy: Arc<dyn LayoutStrategy> = if chunked {
879+
Arc::new(ChunkedLayoutStrategy::new(table))
880+
} else {
881+
Arc::new(table)
882+
};
883+
let rows = 12_000 / pieces;
884+
let chunks: Vec<ArrayRef> = (0..pieces)
885+
.map(|piece| {
886+
let start = i32::try_from(piece * rows).unwrap();
887+
let end = start + i32::try_from(rows).unwrap();
888+
StructArray::try_from_iter_with_validity(
889+
[
890+
("a", PrimitiveArray::from_iter(start..end).into_array()),
891+
("b", PrimitiveArray::from_iter(start..end).into_array()),
892+
],
893+
if nullable {
894+
Validity::Array(
895+
BoolArray::from_iter((start..end).map(|row| row % 2 == 0)).into_array(),
896+
)
897+
} else {
898+
Validity::NonNullable
899+
},
900+
)
901+
.unwrap()
902+
.into_array()
903+
})
904+
.collect();
905+
let dtype = chunks[0].dtype().clone();
906+
let segments2 = Arc::<TestSegments>::clone(&segments);
907+
let layout = block_on(|handle| async move {
908+
let session = new_session().with_handle(handle);
909+
strategy
910+
.write_stream(
911+
ctx.into(),
912+
segments2,
913+
ChunkedArray::try_new(chunks, dtype)
914+
.unwrap()
915+
.into_array()
916+
.to_array_stream()
917+
.sequenced(ptr),
918+
eof,
919+
&session,
920+
)
921+
.await
922+
})
923+
.unwrap();
924+
(segments, layout)
925+
}
926+
927+
/// Registers `layout`'s boundaries over its rows, as a scan does.
928+
fn boundaries_and_soft(
929+
segments: Arc<dyn SegmentSource>,
930+
layout: &LayoutRef,
931+
) -> (Vec<u64>, Vec<u64>) {
932+
let reader = layout
933+
.new_reader("".into(), segments, &SESSION, &Default::default())
934+
.unwrap();
935+
let mut splits = RowSplits::new_capacity(16);
936+
splits.push(0);
937+
reader
938+
.register_splits(
939+
&[FieldMask::All],
940+
&SplitRange::root(0..reader.row_count()).unwrap(),
941+
&mut splits,
942+
)
943+
.unwrap();
944+
splits.into_sorted_deduped_with_soft()
945+
}
946+
947+
#[test]
948+
fn boundaries_only_some_fields_have_are_soft() {
949+
let (segments, layout) = misaligned_struct_layout(1, false, false);
950+
let (boundaries, soft) = boundaries_and_soft(segments, &layout);
951+
// `a` chunks every 1,000 rows and `b` every 3,000, so only `b`'s are shared.
952+
assert_eq!(boundaries, (0..=12).map(|k| k * 1000).collect::<Vec<u64>>());
953+
assert_eq!(
954+
soft,
955+
(1..12)
956+
.filter(|k| k % 3 != 0)
957+
.map(|k| k * 1000)
958+
.collect::<Vec<u64>>()
959+
);
960+
}
961+
962+
#[test]
963+
fn chunk_ends_above_the_struct_stay_hard() {
964+
// Two top-level chunks of 6,000 rows, each a struct whose `a` chunks every 1,000 rows and
965+
// `b` every 3,000: the top-level chunk end at 6,000 is every column's, so it stays hard.
966+
let (segments, layout) = misaligned_struct_layout(2, true, false);
967+
let (boundaries, soft) = boundaries_and_soft(segments, &layout);
968+
assert_eq!(boundaries, (0..=12).map(|k| k * 1000).collect::<Vec<u64>>());
969+
assert!(!soft.contains(&6000), "the chunk end is soft: {soft:?}");
970+
assert!(!soft.contains(&3000) && !soft.contains(&9000), "{soft:?}");
971+
assert!(soft.contains(&1000) && soft.contains(&7000), "{soft:?}");
972+
}
973+
974+
#[rstest]
975+
#[case::non_nullable(false, vec![0, 3000, 6000, 9000, 12000])]
976+
#[case::nullable(true, vec![0, 2000, 3000, 4000, 6000, 8000, 9000, 10000, 12000])]
977+
fn scan_merges_soft_boundaries_and_keeps_validity_boundaries(
978+
#[case] nullable: bool,
979+
#[case] expected: Vec<u64>,
980+
) -> VortexResult<()> {
981+
let (segments, layout) = misaligned_struct_layout(1, false, nullable);
982+
let reader = layout.new_reader("".into(), segments, &SESSION, &Default::default())?;
983+
assert_eq!(
984+
SplitBy::default().splits(
985+
reader.as_ref(),
986+
&(0..reader.row_count()),
987+
&[FieldMask::All],
988+
)?,
989+
expected,
990+
);
991+
Ok(())
992+
}
993+
806994
#[fixture]
807995
/// Create a chunked layout with three chunks of primitive arrays.
808996
fn null_struct_layout() -> (Arc<dyn SegmentSource>, LayoutRef) {

‎vortex-layout/src/reader.rs‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -100,12 +100,18 @@ impl SplitRange {
100100
/// starts a new run. A run that exactly repeats the previous surviving run — common when sibling
101101
/// columns share chunk boundaries — is dropped as it completes, and the final sort is skipped
102102
/// when only a single run survives (the boundaries are then already ascending).
103+
///
104+
/// A boundary can also be marked soft: one that only some of a struct's fields have. A split there
105+
/// lets the fields that chunk across it decode the same chunk in two splits, so the scan may merge
106+
/// it away (see [`crate::scan::split_by::SplitBy::LayoutSubSplitting`]).
103107
pub struct RowSplits {
104108
splits: Vec<u64>,
105109
/// Start index of the run currently being appended.
106110
run_start: usize,
107111
/// Start index of the surviving run immediately before `run_start`.
108112
prev_run_start: usize,
113+
/// Boundaries marked soft, unsorted and possibly repeated.
114+
soft: Vec<u64>,
109115
}
110116

111117
impl RowSplits {
@@ -162,15 +168,45 @@ impl RowSplits {
162168
self.splits.reserve(additional);
163169
}
164170

171+
/// Mark boundaries soft: ones that only some fields of a struct have. They must also be
172+
/// pushed.
173+
pub fn mark_soft(&mut self, rows: impl IntoIterator<Item = u64>) {
174+
self.soft.extend(rows);
175+
}
176+
177+
/// Push `other`'s boundaries into this set as a batch, keeping its soft marks.
178+
pub(crate) fn append(&mut self, mut other: RowSplits) {
179+
let soft = std::mem::take(&mut other.soft);
180+
self.extend_ascending(other.into_sorted_deduped());
181+
self.soft.extend(soft);
182+
}
183+
184+
/// Remove soft marks at the supplied sorted boundaries.
185+
pub(crate) fn remove_soft(&mut self, rows: &[u64]) {
186+
debug_assert!(rows.is_sorted());
187+
if !rows.is_empty() {
188+
self.soft.retain(|row| rows.binary_search(row).is_err());
189+
}
190+
}
191+
165192
/// Create a new RowSplits with preallocated "capacity"
166193
pub(crate) fn new_capacity(capacity: usize) -> Self {
167194
Self {
168195
splits: Vec::with_capacity(capacity),
169196
run_start: 0,
170197
prev_run_start: 0,
198+
soft: Vec::new(),
171199
}
172200
}
173201

202+
/// The sorted, deduplicated boundaries, and the sorted soft ones among them.
203+
pub(crate) fn into_sorted_deduped_with_soft(mut self) -> (Vec<u64>, Vec<u64>) {
204+
let mut soft = std::mem::take(&mut self.soft);
205+
soft.sort_unstable();
206+
soft.dedup();
207+
(self.into_sorted_deduped(), soft)
208+
}
209+
174210
pub(crate) fn into_sorted_deduped(mut self) -> Vec<u64> {
175211
let final_run_dropped = self.drop_repeated_run();
176212
// Surviving runs always have a descent between them, so the boundaries are ascending

0 commit comments

Comments
 (0)