You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by gi...@apache.org on 2026/10/08 19:22:50 UTC
(arrow-rs) branch gh-readonly-queue/main/pr-11389-42aae335ebc666a5ef52e14477a51d13be3d025e created (now a1833f2bc4)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-11389-42aae335ebc666a5ef52e14477a51d13be3d025e
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
at a1833f2bc4 bench: add benchmarks for mixed-backed RowSelection intersection and union (#11389)
This branch includes the following new commits:
new a1833f2bc4 bench: add benchmarks for mixed-backed RowSelection intersection and union (#11389)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
(arrow-rs) 01/01: bench: add benchmarks for mixed-backed RowSelection intersection and union (#11389)
Posted by gi...@apache.org.
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 <ha...@gmail.com>
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);