Selective filter cost scales with total chunk count, not with rows selected

[wsulais]

A selective filter costs time proportional to the number of chunks in the file rather than to the number of rows it returns. Zone-map pruning stops pruned chunks being read, but not being constructed: a reader and an array future are built for every chunk in the scanned range before the zone map has pruned anything.

13 i32 columns, 64-row blocks, a filter selecting 499 rows in every case, best of four, open_buffer so there is no real IO:

rows	blocks	chunks	selected	filter ms
16,384	256	3,328	499	2.1
65,536	1,024	13,312	499	7.8
262,144	4,096	53,248	499	40.8

4x the chunks costs 3.7x the time, 16x costs 19x, while the result is identical.

Mechanism

ZonedReader::pruning_evaluation builds its data child's pruning future eagerly, before consulting its own zone map:

let data_eval = self
    .data_child()?
    .pruning_evaluation(row_range, expr, mask.clone())?;

It then only awaits data_eval when the zone map did not already prune the range. But constructing it is not free: ChunkedReader::pruning_evaluation walks every chunk in the range calling self.chunk_reader(chunk_idx)?, which materializes a chunk layout and reader, and ChunkedReader::filter_evaluation does the same and additionally has each FlatReader build an array future — which issues a segment_source.request() per chunk.

Counted with temporary instrumentation, for the 65,536-row case returning 499 of 65,536 rows: 13,313 FlatReaders and 13,321 array futures, one per chunk in the file. Flat::deserialize is not called at all, because ViewedLayoutChildren caches the layouts across scans, so the cost is purely per-scan reader and future construction.

Pruning is working — 499 rows costs 7.8 ms where a full scan of the same file costs 34.5 ms, so the decode is skipped. It is only the construction that is unconditional.

Not the planning path

register_splits already avoids this. VTable::is_indivisible, LayoutChildren::child_is_indivisible and ChunkedReader::chunk_skips classify chunks from the encoding registry without materializing anything, and register_splits takes a fast path that derives splits from chunk_offsets alone. Consistent with that, SplitBy::RowCount — which never calls register_splits — gives byte-identical construction counts, so all of it comes from the evaluation methods.

The same treatment applied to pruning_evaluation and filter_evaluation, deferring child construction until the returned future is polled, would leave a pruned chunk costing nothing.

Context

Found while measuring #9447. A paged layout (#9448) collapses a group of chunks behind one deferred future, so pruned ranges construct nothing and the same filter runs about 2x faster — 4.2 ms against 7.8 ms. That difference is laziness rather than anything paging does, which is why it seemed worth reporting on its own.

Reproducer, as a test in vortex-file

#[tokio::test]
async fn filter_cost_scales_with_total_chunks() -> VortexResult<()> {
    const COLUMNS: usize = 13;
    const BLOCK: usize = 64;
    const SELECTED: i32 = 500;

    println!("\n{:>10} {:>8} {:>8} {:>10} {:>10}", "rows", "blocks", "chunks", "selected", "filter ms");
    for rows in [16_384i32, 65_536, 262_144] {
        let names: Vec<String> = (0..COLUMNS).map(|c| format!("c{c}")).collect();
        let fields: Vec<(&str, ArrayRef)> = names
            .iter()
            .enumerate()
            .map(|(c, name)| {
                let column: PrimitiveArray = (0..rows).map(|r| r + (c as i32 * rows)).collect();
                (name.as_str(), column.into_array())
            })
            .collect();
        let array = StructArray::from_fields(&fields)?.into_array();

        let strategy = crate::strategy::WriteStrategyBuilder::default()
            .with_row_block_size(BLOCK)
            .with_data_block_target_bytes(None)
            .build();
        let mut buf = ByteBufferMut::empty();
        SESSION
            .write_options()
            .with_strategy(strategy)
            .write(&mut buf, array.to_array_stream())
            .await?;
        let file = SESSION.open_options().open_buffer(buf)?;

        // Selects the same number of rows regardless of file size.
        let filter = bind_scan_expr(&file, gt(get_item("c0", root()), lit(rows - SELECTED)));

        let mut best = f64::INFINITY;
        let mut selected = 0;
        for _ in 0..4 {
            let started = std::time::Instant::now();
            let out = file
                .scan()?
                .with_filter(filter.clone())
                .into_array_stream()?
                .read_all()
                .await?;
            best = best.min(started.elapsed().as_secs_f64() * 1e3);
            selected = out.len();
        }
        let blocks = rows as usize / BLOCK;
        println!("{rows:>10} {blocks:>8} {:>8} {selected:>10} {best:>10.1}", blocks * COLUMNS);
    }
    Ok(())
}

[Bardakor]

I’m working on this. I’m taking the lazy-construction route described in the issue: defer the zoned data-child pruning evaluation until after the zone mask is known, propagate that pruned mask into the chunked reader, and avoid constructing per-chunk filter readers for chunks whose resolved mask is empty. I’ll include a regression test that ensures fully masked chunks don’t touch their backing segments.