This is an automated email from the ASF dual-hosted git repository. github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-11389-42aae335ebc666a5ef52e14477a51d13be3d025e in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
commit a1833f2bc4ec90117605b296bd0b9859b961b40f Author: Huaijin <[email protected]> AuthorDate: Thu Oct 8 18:25:36 2026 +0000 bench: add benchmarks for mixed-backed RowSelection intersection and union (#11389) # Which issue does this PR close? Relates to #10423. # Rationale for this change Establish benchmarks before optimizing mixed mask/selector `intersection` and `union`. The inspected Arrow and DataFusion scan paths combine selections for the same row group, with equal logical lengths including skipped rows ([Arrow](https://github.com/apache/arrow-rs/blob/103ebe7548db35c37e8ff35fcb02438bcd182fa7/parquet/src/arrow/push_decoder/reader_builder/mod.rs#L932-L947), [DataFusion](https://github.com/apache/datafusion/blob/8248a579695b92b7ca94709eedd63a71689513ce/datafusion/datasource-parquet/src/access_plan.rs#L569-L584)). These benchmarks follow that shape; the public API also supports unequal lengths. # What changes are included in this PR? Add 28 Criterion cases covering bitmap fragmentation, selectivity, page ranges, offsets, and three-operation chains. Inputs are equal-length without precomputed RLE caches; input construction is excluded from timing. No implementation changes. # Are these changes tested? All 28 cases run successfully against main. Length assertions, formatting, and benchmark-specific Clippy checks pass. # Are there any significant user-facing changes? None. --- parquet/Cargo.toml | 5 + parquet/benches/row_selection_algebra.rs | 178 +++++++++++++++++++++++++++++++ 2 files changed, 183 insertions(+) diff --git a/parquet/Cargo.toml b/parquet/Cargo.toml index 31ca245952..ec1c869c95 100644 --- a/parquet/Cargo.toml +++ b/parquet/Cargo.toml @@ -333,6 +333,11 @@ name = "row_group_index_reader" required-features = ["arrow"] harness = false +[[bench]] +name = "row_selection_algebra" +harness = false +required-features = ["arrow"] + [[bench]] name = "row_selection_cursor" harness = false diff --git a/parquet/benches/row_selection_algebra.rs b/parquet/benches/row_selection_algebra.rs new file mode 100644 index 0000000000..f24010628d --- /dev/null +++ b/parquet/benches/row_selection_algebra.rs @@ -0,0 +1,178 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Equal-length intersection/union benchmarks without a precomputed RLE cache. +//! Timings include result allocation and destruction, but exclude input construction. + +use std::hint; + +use arrow_buffer::BooleanBuffer; +use criterion::{BenchmarkId, Criterion, Throughput, criterion_group, criterion_main}; +use parquet::arrow::arrow_reader::{RowSelection, RowSelector}; +use rand::{RngExt, SeedableRng, rngs::StdRng}; + +fn mask(rows: usize, selected: impl FnMut(usize) -> bool) -> RowSelection { + RowSelection::from_boolean_buffer(BooleanBuffer::from_iter((0..rows).map(selected))) +} + +fn selectors(rows: usize, run_rows: usize) -> RowSelection { + RowSelection::from( + (0..rows) + .step_by(run_rows) + .map(|start| RowSelector { + row_count: run_rows.min(rows - start), + skip: (start / run_rows).is_multiple_of(2), + }) + .collect::<Vec<_>>(), + ) +} + +fn page_selectors(rows: usize, selectivity: f64, rng: &mut StdRng) -> RowSelection { + let mut remaining = rows; + let mut pages = Vec::new(); + while remaining > 0 { + let row_count = rng.random_range(512..=8192).min(remaining); + pages.push(RowSelector { + row_count, + skip: !rng.random_bool(selectivity), + }); + remaining -= row_count; + } + RowSelection::from(pages) +} + +fn bench_selection_algebra(c: &mut Criterion) { + const ROWS: usize = 1_000_000; + let coarse = selectors(ROWS, 4096); + let mut rng = StdRng::seed_from_u64(42); + + let cases = [ + ("alternating_1m", mask(ROWS, |i| i % 2 == 0), coarse.clone()), + ( + "alternating_3m", + mask(3_000_000, |i| i % 2 == 0), + selectors(3_000_000, 4096), + ), + ( + "random50", + mask(ROWS, |_| rng.random_bool(0.5)), + coarse.clone(), + ), + ( + "contiguous50", + mask(ROWS, |i| (ROWS / 4..ROWS * 3 / 4).contains(&i)), + coarse.clone(), + ), + ( + "coarse50", + mask(ROWS, |i| (i / 4096) % 2 == 0), + coarse.clone(), + ), + ( + "random10_variable_pages10", + mask(ROWS, |_| rng.random_bool(0.1)), + page_selectors(ROWS, 0.1, &mut rng), + ), + ( + "random50_variable_pages50", + mask(ROWS, |_| rng.random_bool(0.5)), + page_selectors(ROWS, 0.5, &mut rng), + ), + ( + "random90_variable_pages90", + mask(ROWS, |_| rng.random_bool(0.9)), + page_selectors(ROWS, 0.9, &mut rng), + ), + ( + "compact_1m", + mask(ROWS, |i| i < ROWS / 100), + RowSelection::from(vec![RowSelector::select(ROWS)]), + ), + ( + "sparse_prefix64_1m", + mask(ROWS, |i| i < 64), + RowSelection::from(vec![RowSelector::select(ROWS)]), + ), + ( + "fragmented_selectors", + RowSelection::from_boolean_buffer(BooleanBuffer::new_set(ROWS)), + selectors(ROWS, 8), + ), + ( + "offset7_equal", + RowSelection::from_boolean_buffer( + BooleanBuffer::from_iter((0..ROWS + 7).map(|i| i % 2 == 0)).slice(7, ROWS), + ), + coarse.clone(), + ), + ( + "offset63_equal", + RowSelection::from_boolean_buffer( + BooleanBuffer::from_iter((0..ROWS + 63).map(|i| i % 2 == 0)).slice(63, ROWS), + ), + coarse.clone(), + ), + ]; + + let mut group = c.benchmark_group("row_selection_algebra"); + for (name, mask, selectors) in cases { + let rows = mask.total_row_count(); + assert_eq!(rows, selectors.total_row_count(), "{name}: unequal lengths"); + group.throughput(Throughput::Elements(rows as u64)); + group.bench_function(BenchmarkId::new("intersection", name), |b| { + b.iter(|| hint::black_box(&mask).intersection(hint::black_box(&selectors))); + }); + group.bench_function(BenchmarkId::new("union", name), |b| { + b.iter(|| hint::black_box(&mask).union(hint::black_box(&selectors))); + }); + } + + let initial = mask(ROWS, |_| rng.random_bool(0.5)); + let conditions = [ + page_selectors(ROWS, 0.5, &mut rng), + mask(ROWS, |_| rng.random_bool(0.9)), + page_selectors(ROWS, 0.9, &mut rng), + ]; + for condition in &conditions { + assert_eq!(initial.total_row_count(), condition.total_row_count()); + } + // Each iteration measures all three operations. + group.throughput(Throughput::Elements(ROWS as u64)); + group.bench_function(BenchmarkId::new("intersection", "chain_mixed_3"), |b| { + b.iter(|| { + let mut result = + hint::black_box(&initial).intersection(hint::black_box(&conditions[0])); + for condition in &conditions[1..] { + result = result.intersection(hint::black_box(condition)); + } + result + }); + }); + group.bench_function(BenchmarkId::new("union", "chain_mixed_3"), |b| { + b.iter(|| { + let mut result = hint::black_box(&initial).union(hint::black_box(&conditions[0])); + for condition in &conditions[1..] { + result = result.union(hint::black_box(condition)); + } + result + }); + }); + group.finish(); +} + +criterion_group!(benches, bench_selection_algebra); +criterion_main!(benches);
