Skip to content

Commit aab5de1

Browse files
fix(scan): address soft split boundary review
Compute the shared boundary intersection once, preserve validity boundaries, and move inherited soft marks without cloning their buffer. Add merge invariants, real-layout regression coverage, and a wider split-collection benchmark case. Signed-off-by: Christopher Wirt <[email protected]>
1 parent 7c26a2d commit aab5de1

4 files changed

Lines changed: 140 additions & 24 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: 64 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -523,10 +523,15 @@ 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

531536
// Each field's boundaries, kept apart so the ones only some fields have can be marked soft.
532537
let mut fields: Vec<RowSplits> = Vec::new();
@@ -537,24 +542,35 @@ impl LayoutReader for StructReader {
537542
fields.push(field);
538543
Ok(())
539544
})?;
545+
let mut field_splits = RowSplits::new_capacity(0);
540546
if let [field] = &mut fields[..] {
541-
splits.append(std::mem::replace(field, RowSplits::new_capacity(0)));
547+
field_splits = std::mem::replace(field, RowSplits::new_capacity(0));
542548
} else if !fields.is_empty() {
543549
let fields: Vec<(Vec<u64>, Vec<u64>)> = fields
544550
.into_iter()
545551
.map(RowSplits::into_sorted_deduped_with_soft)
546552
.collect();
547-
let shared = |row: &u64| {
548-
fields
549-
.iter()
550-
.all(|(boundaries, _)| boundaries.binary_search(row).is_ok())
551-
};
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+
}
552561
for (boundaries, soft) in fields.iter() {
553-
splits.extend_ascending(boundaries.iter().copied());
554-
splits.mark_soft(soft.iter().copied());
555-
splits.mark_soft(boundaries.iter().copied().filter(|row| !shared(row)));
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+
);
556570
}
557571
}
572+
field_splits.remove_soft(&validity_boundaries);
573+
splits.append(field_splits);
558574

559575
// In the case of an empty struct, we need to register the end split. Pushed last so it
560576
// extends the final field's ascending run rather than starting a run of its own.
@@ -746,6 +762,7 @@ mod tests {
746762
use crate::layouts::table::TableStrategy;
747763
use crate::layouts::zoned::writer::ZonedLayoutOptions;
748764
use crate::layouts::zoned::writer::ZonedStrategy;
765+
use crate::scan::split_by::SplitBy;
749766
use crate::segments::CountingSegmentSource;
750767
use crate::segments::SegmentFuture;
751768
use crate::segments::SegmentId;
@@ -851,13 +868,13 @@ mod tests {
851868
fn misaligned_struct_layout(
852869
pieces: usize,
853870
chunked: bool,
871+
nullable: bool,
854872
) -> (Arc<dyn SegmentSource>, LayoutRef) {
855873
let ctx = ArrayContext::empty();
856874
let segments = Arc::new(TestSegments::default());
857875
let (ptr, eof) = SequenceId::root().split();
858-
let table =
859-
TableStrategy::new(Arc::new(FlatLayoutStrategy::default()), chunked_every(1000))
860-
.with_field_writer(FieldPath::from_name("b"), chunked_every(3000));
876+
let table = TableStrategy::new(chunked_every(2000), chunked_every(1000))
877+
.with_field_writer(FieldPath::from_name("b"), chunked_every(3000));
861878
let strategy: Arc<dyn LayoutStrategy> = if chunked {
862879
Arc::new(ChunkedLayoutStrategy::new(table))
863880
} else {
@@ -868,12 +885,18 @@ mod tests {
868885
.map(|piece| {
869886
let start = i32::try_from(piece * rows).unwrap();
870887
let end = start + i32::try_from(rows).unwrap();
871-
StructArray::from_fields(
888+
StructArray::try_from_iter_with_validity(
872889
[
873890
("a", PrimitiveArray::from_iter(start..end).into_array()),
874891
("b", PrimitiveArray::from_iter(start..end).into_array()),
875-
]
876-
.as_slice(),
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+
},
877900
)
878901
.unwrap()
879902
.into_array()
@@ -923,7 +946,7 @@ mod tests {
923946

924947
#[test]
925948
fn boundaries_only_some_fields_have_are_soft() {
926-
let (segments, layout) = misaligned_struct_layout(1, false);
949+
let (segments, layout) = misaligned_struct_layout(1, false, false);
927950
let (boundaries, soft) = boundaries_and_soft(segments, &layout);
928951
// `a` chunks every 1,000 rows and `b` every 3,000, so only `b`'s are shared.
929952
assert_eq!(boundaries, (0..=12).map(|k| k * 1000).collect::<Vec<u64>>());
@@ -940,14 +963,34 @@ mod tests {
940963
fn chunk_ends_above_the_struct_stay_hard() {
941964
// Two top-level chunks of 6,000 rows, each a struct whose `a` chunks every 1,000 rows and
942965
// `b` every 3,000: the top-level chunk end at 6,000 is every column's, so it stays hard.
943-
let (segments, layout) = misaligned_struct_layout(2, true);
966+
let (segments, layout) = misaligned_struct_layout(2, true, false);
944967
let (boundaries, soft) = boundaries_and_soft(segments, &layout);
945968
assert_eq!(boundaries, (0..=12).map(|k| k * 1000).collect::<Vec<u64>>());
946969
assert!(!soft.contains(&6000), "the chunk end is soft: {soft:?}");
947970
assert!(!soft.contains(&3000) && !soft.contains(&9000), "{soft:?}");
948971
assert!(soft.contains(&1000) && soft.contains(&7000), "{soft:?}");
949972
}
950973

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+
951994
#[fixture]
952995
/// Create a chunked layout with three chunks of primitive arrays.
953996
fn null_struct_layout() -> (Arc<dyn SegmentSource>, LayoutRef) {

‎vortex-layout/src/reader.rs‎

Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -175,12 +175,20 @@ impl RowSplits {
175175
}
176176

177177
/// Push `other`'s boundaries into this set as a batch, keeping its soft marks.
178-
pub(crate) fn append(&mut self, other: RowSplits) {
179-
let soft = other.soft.clone();
178+
pub(crate) fn append(&mut self, mut other: RowSplits) {
179+
let soft = std::mem::take(&mut other.soft);
180180
self.extend_ascending(other.into_sorted_deduped());
181181
self.soft.extend(soft);
182182
}
183183

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+
184192
/// Create a new RowSplits with preallocated "capacity"
185193
pub(crate) fn new_capacity(capacity: usize) -> Self {
186194
Self {

‎vortex-layout/src/scan/split_by.rs‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -223,6 +223,10 @@ mod test {
223223
use std::sync::Arc;
224224

225225
use futures::future::BoxFuture;
226+
use rand::RngExt;
227+
use rand::SeedableRng;
228+
use rand::prelude::StdRng;
229+
use rstest::rstest;
226230
use vortex_array::ArrayContext;
227231
use vortex_array::ArrayRef;
228232
use vortex_array::IntoArray;
@@ -430,6 +434,67 @@ mod test {
430434
assert_eq!(subdivide_large_spans(vec![7], 100), vec![7]);
431435
}
432436

437+
#[rstest]
438+
#[case::empty(vec![], vec![], 5, vec![])]
439+
#[case::single(vec![7], vec![7], 5, vec![7])]
440+
#[case::hard(vec![0, 1, 2, 10], vec![], 5, vec![0, 1, 2, 10])]
441+
#[case::soft(vec![0, 1, 2, 10], vec![1, 2], 5, vec![0, 10])]
442+
#[case::short_tail(vec![0, 5, 6], vec![5], 5, vec![0, 6])]
443+
#[case::hard_collision(vec![0, 3, 5, 6], vec![3, 5], 5, vec![0, 6])]
444+
#[case::hard_start(vec![0, 3, 5, 6], vec![5], 5, vec![0, 3, 6])]
445+
#[case::threshold(vec![0, 5, 10], vec![5], 5, vec![0, 5, 10])]
446+
#[case::nonzero_range(vec![100, 101, 102, 110], vec![101, 102], 5, vec![100, 110])]
447+
fn merge_small_spans_cases(
448+
#[case] boundaries: Vec<u64>,
449+
#[case] soft: Vec<u64>,
450+
#[case] minimum: u64,
451+
#[case] expected: Vec<u64>,
452+
) {
453+
assert_eq!(merge_small_spans(boundaries, &soft, minimum), expected);
454+
}
455+
456+
#[test]
457+
fn merging_preserves_hard_boundaries_and_exact_coverage() {
458+
let mut rng = StdRng::seed_from_u64(67);
459+
for _ in 0..1000 {
460+
let start = rng.random_range(0..1000u64);
461+
let mut boundaries = vec![start];
462+
for _ in 0..rng.random_range(1..50) {
463+
boundaries.push(boundaries.last().unwrap() + rng.random_range(1..1000));
464+
}
465+
let soft = boundaries
466+
.iter()
467+
.copied()
468+
.filter(|_| rng.random_bool(0.5))
469+
.collect::<Vec<_>>();
470+
let max_rows = rng.random_range(1..3000);
471+
let minimum = DEFAULT_MIN_SPLIT_ROWS.min(max_rows);
472+
let merged = merge_small_spans(boundaries.clone(), &soft, minimum);
473+
assert_eq!(merged.first(), boundaries.first());
474+
assert_eq!(merged.last(), boundaries.last());
475+
assert!(merged.windows(2).all(|w| w[0] < w[1]));
476+
assert!(
477+
merged
478+
.iter()
479+
.all(|row| boundaries.binary_search(row).is_ok())
480+
);
481+
assert!(boundaries.iter().all(|row| {
482+
soft.binary_search(row).is_ok() || merged.binary_search(row).is_ok()
483+
}));
484+
assert!(merged.windows(2).all(|w| {
485+
Some(&w[1]) == merged.last()
486+
|| soft.binary_search(&w[1]).is_err()
487+
|| w[1] - w[0] >= minimum
488+
}));
489+
let subdivided = subdivide_large_spans(merged, max_rows);
490+
assert!(subdivided.windows(2).all(|w| w[1] - w[0] <= max_rows));
491+
assert_eq!(
492+
subdivided.windows(2).map(|w| w[1] - w[0]).sum::<u64>(),
493+
boundaries.last().unwrap() - start,
494+
);
495+
}
496+
}
497+
433498
#[test]
434499
fn subdivide_near_u64_max_does_not_overflow() {
435500
// The increment past the last interior point would overflow without saturating math.

0 commit comments

Comments
 (0)