Skip to content

Commit cb39bb9

Browse files
Plan V2 random access from known row selections (#10625)
Signed-off-by: Joe Isaacs <[email protected]>
1 parent d7562aa commit cb39bb9

11 files changed

Lines changed: 464 additions & 92 deletions

File tree

‎vortex-bench/src/random_access/take.rs‎

Lines changed: 12 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -29,10 +29,12 @@ use tokio::fs::File;
2929
use vortex::array::Canonical;
3030
use vortex::array::IntoArray;
3131
use vortex::array::VortexSessionExecute;
32+
use vortex::array::stream::ArrayStreamAdapter;
3233
use vortex::array::stream::ArrayStreamExt;
3334
use vortex::buffer::Buffer;
3435
use vortex::file::OpenOptionsSessionExt;
3536
use vortex::file::VortexFile;
37+
use vortex::layout::scan::v2::ScanBuilder;
3638
use vortex::scan::strict_sorted_buffer::StrictSortedBuffer;
3739
use vortex::utils::aliases::hash_map::HashMap;
3840

@@ -128,7 +130,8 @@ impl RandomAccessor for ArrowIpcRandomAccessor {
128130

129131
/// Random accessor for Vortex format files.
130132
///
131-
/// The file handle is opened at construction time and reused across `take()` calls.
133+
/// The file handle is opened at construction time and reused across `take()` calls. Rows are
134+
/// read with the V2 scan, which requires files without list layouts.
132135
pub struct VortexRandomAccessor {
133136
name: String,
134137
format: Format,
@@ -142,11 +145,7 @@ impl VortexRandomAccessor {
142145
name: impl Into<String>,
143146
format: Format,
144147
) -> anyhow::Result<Self> {
145-
let file = SESSION
146-
.open_options()
147-
.with_layout_reader_cache()
148-
.open_path(path.as_ref())
149-
.await?;
148+
let file = SESSION.open_options().open_path(path.as_ref()).await?;
150149
Ok(Self {
151150
name: name.into(),
152151
format,
@@ -163,7 +162,6 @@ impl VortexRandomAccessor {
163162
) -> anyhow::Result<Self> {
164163
let file = SESSION
165164
.open_options()
166-
.with_layout_reader_cache()
167165
.open_object_store(remote.store(), remote.key(path)?)
168166
.await?;
169167
Ok(Self {
@@ -185,16 +183,16 @@ impl RandomAccessor for VortexRandomAccessor {
185183
}
186184

187185
async fn take(&self, indices: &[u64]) -> anyhow::Result<RandomAccessorRet> {
188-
let indices_buf: Buffer<u64> = Buffer::from(indices.to_vec());
189-
let array = self
190-
.file
191-
.scan()?
192-
.with_row_indices(StrictSortedBuffer::try_new(indices_buf)?)
193-
.into_array_stream()?
186+
let indices = StrictSortedBuffer::try_new(Buffer::from(indices.to_vec()))?;
187+
let stream = ScanBuilder::new(SESSION.clone(), self.file.scan_file())
188+
.with_row_indices(indices)
189+
.into_stream()?;
190+
let array = ArrayStreamAdapter::new(self.file.dtype().clone(), stream)
194191
.read_all()
195192
.await?;
196193

197-
// We canonicalize / decompress for equivalence to Arrow's `RecordBatch`es.
194+
// Keep the historical benchmark contract: canonicalize the outer array, leaving nested
195+
// values lazy.
198196
let mut ctx = SESSION.create_execution_ctx();
199197
let canonical = array.execute::<Canonical>(&mut ctx)?.into_array();
200198
Ok(RandomAccessorRet::ArrayRef(canonical))

‎vortex-layout/src/plan/physical/mod.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@ mod optimize;
1919
pub mod optimizer;
2020
pub mod pipeline;
2121
mod plans;
22+
pub(crate) mod selection;
2223
mod typed;
2324
mod vtable;
2425

‎vortex-layout/src/plan/physical/pipeline/tests.rs‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,9 +43,11 @@ use crate::layouts::chunked::ChunkedLayout;
4343
use crate::layouts::dict::DictLayout;
4444
use crate::layouts::flat::FlatLayout;
4545
use crate::layouts::struct_::StructLayout;
46+
use crate::plan::physical::ConcatPlan;
4647
use crate::plan::physical::EvalPlan;
4748
use crate::plan::physical::Filter;
4849
use crate::plan::physical::PackPlan;
50+
use crate::plan::physical::PlanChildren;
4951
use crate::plan::physical::PlanRef;
5052
use crate::plan::physical::SegmentScan;
5153
use crate::plan::physical::Take;
@@ -60,6 +62,7 @@ use crate::plan::physical::operator::SourceReady;
6062
use crate::plan::physical::operator::Step;
6163
use crate::plan::physical::operators::PackSource;
6264
use crate::plan::physical::optimize;
65+
use crate::plan::physical::selection::selected;
6366
use crate::segments::SegmentId;
6467
use crate::test::SESSION;
6568

@@ -834,3 +837,88 @@ fn pack_readiness_tracks_changes_and_consumption(
834837
}
835838
Ok(())
836839
}
840+
841+
#[rstest]
842+
#[case::sparse(2..19, vec![0, 5, 14, 16])]
843+
#[case::contiguous(2..19, (5..10).collect())]
844+
#[case::empty(2..19, vec![])]
845+
fn bound_selection_matches_projection(
846+
#[case] rows: Range<u64>,
847+
#[case] indices: Vec<usize>,
848+
) -> VortexResult<()> {
849+
let mut store = Store::default();
850+
let (plan, expected) = fixture(&mut store)?;
851+
let mask = Mask::from_indices((rows.end - rows.start) as usize, indices);
852+
let plan = selected(plan, rows.clone(), mask.clone());
853+
let result = run(
854+
&store,
855+
&plan,
856+
rows.clone(),
857+
Mask::new_true(mask.len()),
858+
delivery(Delivery::Lifo),
859+
)?;
860+
assert_view(&expected, &rows, &mask, result.arrays)
861+
}
862+
863+
#[test]
864+
fn bound_selection_never_initializes_skipped_chunks() -> VortexResult<()> {
865+
let mut store = Store::default();
866+
let array = PrimitiveArray::from_iter(0..20i32).into_array();
867+
let first = lower(&store.flat(&array.slice(0..5)?)?)?;
868+
let last = lower(&store.flat(&array.slice(15..20)?)?)?;
869+
let children = PlanChildren::lazy(4, move |index| match index {
870+
0 => Ok(first.clone()),
871+
3 => Ok(last.clone()),
872+
_ => Err(vortex_err!("unselected chunk {index} was initialized")),
873+
});
874+
// SAFETY: All four logical chunks have five rows of the same primitive dtype. The two
875+
// unselected initializers deliberately fail to detect discovery as well as compilation.
876+
let plan = unsafe {
877+
ConcatPlan::from_children_unchecked(
878+
array.dtype().clone(),
879+
20,
880+
vec![0, 5, 10, 15].into(),
881+
children,
882+
)
883+
}
884+
.into_plan();
885+
let mask = Mask::from_indices(20, [2, 17]);
886+
let plan = selected(plan, 0..20, mask.clone());
887+
let result = run(
888+
&store,
889+
&plan,
890+
0..20,
891+
Mask::new_true(20),
892+
delivery(Delivery::Fifo),
893+
)?;
894+
assert_eq!(reads(&result.events), 2);
895+
assert_view(&array, &(0..20), &mask, result.arrays)
896+
}
897+
898+
#[test]
899+
fn bound_selection_keeps_whole_dictionary_values() -> VortexResult<()> {
900+
let mut store = Store::default();
901+
let values = PrimitiveArray::from_iter(100..120i32).into_array();
902+
let codes = PrimitiveArray::from_iter((0..20u32).rev()).into_array();
903+
let layout = DictLayout::new(
904+
store.chunked(&values, &[5, 5, 5, 5])?,
905+
store.chunked(&codes, &[5, 5, 5, 5])?,
906+
)
907+
.into_layout();
908+
let mask = Mask::from_indices(20, [1, 18]);
909+
let plan = selected(lower(&layout)?, 0..20, mask);
910+
let result = run(
911+
&store,
912+
&plan,
913+
0..20,
914+
Mask::new_true(20),
915+
delivery(Delivery::Lifo),
916+
)?;
917+
assert_eq!(reads(&result.events), 6, "all values and two code chunks");
918+
assert_arrays_eq!(
919+
join(values.dtype(), result.arrays)?,
920+
PrimitiveArray::from_iter([118, 101]).into_array(),
921+
&mut SESSION.create_execution_ctx()
922+
);
923+
Ok(())
924+
}

‎vortex-layout/src/plan/physical/plans/concat.rs‎

Lines changed: 16 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@ use crate::plan::physical::pipeline::Chain;
2626
use crate::plan::physical::pipeline::Compiler;
2727
use crate::plan::physical::pipeline::Reach;
2828
use crate::plan::physical::pipeline::overlapping;
29+
use crate::plan::physical::selection::selected_slice;
2930
use crate::segments::SegmentId;
3031

3132
/// Concatenates its children row-wise.
@@ -157,20 +158,26 @@ impl PlanVTable for Concat {
157158
mask: &Mask,
158159
compiler: &mut Compiler<'_>,
159160
) -> VortexResult<Option<Chain>> {
160-
let mut chains = Vec::with_capacity(overlapping(plan, &rows).size_hint().1.unwrap_or(0));
161+
let capacity = if mask.all_true() {
162+
overlapping(plan, &rows).size_hint().1.unwrap_or(0)
163+
} else {
164+
0
165+
};
166+
let mut chains = Vec::with_capacity(capacity);
161167
for (index, start, local) in overlapping(plan, &rows) {
162-
let local_mask = mask.slice(
168+
let Some((span, local_mask)) = selected_slice(
169+
mask,
163170
usize::try_from(local.start - rows.start)?
164171
..usize::try_from(local.end - rows.start)?,
165-
);
166-
// A chunk the mask selects nothing of is never built, so never read.
167-
if local_mask.all_false() {
172+
) else {
168173
continue;
169-
}
174+
};
170175
let chunk = plan.child_required(index)?;
171-
if let Some(chain) =
172-
compiler.compile(&chunk, local.start - start..local.end - start, &local_mask)?
173-
{
176+
if let Some(chain) = compiler.compile(
177+
&chunk,
178+
rows.start + span.start as u64 - start..rows.start + span.end as u64 - start,
179+
&local_mask,
180+
)? {
174181
chains.push(chain);
175182
}
176183
}

‎vortex-layout/src/plan/physical/plans/filter.rs‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -103,13 +103,13 @@ impl PlanVTable for Filter {
103103
mask: &Mask,
104104
compiler: &mut Compiler<'_>,
105105
) -> VortexResult<Option<Chain>> {
106+
if mask.all_false() {
107+
return Ok(None);
108+
}
106109
let child = plan.child_plan()?;
107110
if let Some(scan) = child.as_opt::<SegmentScan>() {
108111
return compiler.scan(scan, rows, Some(mask.clone()));
109112
}
110-
if mask.all_false() {
111-
return Ok(None);
112-
}
113113
let len = usize::try_from(rows.end - rows.start)?;
114114
let predicate = plan.dtype().is_boolean();
115115
let chain = compiler.compile(&child, rows, &Mask::new_true(len))?;

0 commit comments

Comments
 (0)