Skip to content

Commit cd91f89

Browse files
authored
bench(parquet): add level encoding and nested writer cases (#12213)
# Which issue does this PR close? - Part of #12194. # Rationale for this change Adds benchmarks for definition/repetition level encoding and more nested-column writer cases, so the change proposed in #12194 can be measured against main. # What changes are included in this PR? - `parquet/benches/level_encoding.rs`: level encoding benchmarks (mixed, uniform and fragmented levels). - `parquet/benches/arrow_writer.rs`: two nested cases, `list_short` (short lists with nulls) and `map`. # Are these changes tested? Benchmarks only; they build with cargo bench on main. # Are there any user-facing changes? No. Code drafted by both human and AI, and reviewed by human. Co-authored-by: JonSnow1807 <[email protected]>
1 parent da51f14 commit cd91f89

3 files changed

Lines changed: 223 additions & 1 deletion

File tree

‎parquet/Cargo.toml‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -307,6 +307,11 @@ name = "bit_packing"
307307
required-features = ["experimental", "default"]
308308
harness = false
309309

310+
[[bench]]
311+
name = "level_encoding"
312+
required-features = ["experimental", "default"]
313+
harness = false
314+
310315
[[bench]]
311316
name = "metadata"
312317
harness = false

‎parquet/benches/arrow_writer.rs‎

Lines changed: 51 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -25,7 +25,7 @@ use arrow::datatypes::*;
2525
use arrow::util::bench_util::{create_f16_array, create_f32_array, create_f64_array};
2626
use arrow::util::test_util::seedable_rng;
2727
use arrow::{record_batch::RecordBatch, util::data_gen::*};
28-
use arrow_array::builder::{FixedSizeBinaryBuilder, ListBuilder, StringBuilder};
28+
use arrow_array::builder::{FixedSizeBinaryBuilder, Int32Builder, ListBuilder, StringBuilder};
2929
use arrow_array::{
3030
Array, ArrayRef, BooleanArray, Decimal128Array, DictionaryArray, FixedSizeBinaryArray,
3131
Float64Array, Int8Array, Int32Array, Int64Array, LargeBinaryArray, ListArray,
@@ -968,6 +968,52 @@ fn create_list_struct_with_list_batch(size: usize, null_density: f32) -> Result<
968968
)?)
969969
}
970970

971+
/// `List<Int32>` with 0..=9 elements per row, 10% null lists and 10% null
972+
/// elements: definition and repetition levels change every few values.
973+
fn create_short_list_bench_batch(size: usize) -> RecordBatch {
974+
let mut rng = seedable_rng();
975+
let mut builder = ListBuilder::new(Int32Builder::new());
976+
for _ in 0..size {
977+
if rng.random_range(0..10) == 0 {
978+
builder.append_null();
979+
continue;
980+
}
981+
for _ in 0..rng.random_range(0..=9) {
982+
if rng.random_range(0..10) == 0 {
983+
builder.values().append_null();
984+
} else {
985+
builder.values().append_value(rng.random_range(0..1000));
986+
}
987+
}
988+
builder.append(true);
989+
}
990+
let array: ArrayRef = Arc::new(builder.finish());
991+
RecordBatch::try_from_iter([("_1", array)]).unwrap()
992+
}
993+
994+
fn create_map_bench_batch(size: usize, null_density: f32) -> Result<RecordBatch> {
995+
let entries = Field::new(
996+
"entries",
997+
DataType::Struct(Fields::from(vec![
998+
Field::new("keys", DataType::Utf8, false),
999+
Field::new("values", DataType::Int32, true),
1000+
])),
1001+
false,
1002+
);
1003+
let fields = vec![Field::new(
1004+
"_1",
1005+
DataType::Map(Arc::new(entries), false),
1006+
true,
1007+
)];
1008+
let schema = Schema::new(fields);
1009+
Ok(create_random_batch(
1010+
Arc::new(schema),
1011+
size,
1012+
null_density,
1013+
0.75,
1014+
)?)
1015+
}
1016+
9711017
fn _create_nested_bench_batch(
9721018
size: usize,
9731019
null_density: f32,
@@ -1518,6 +1564,10 @@ fn create_batches() -> Vec<BatchBenchmark> {
15181564
create_list_struct_with_list_batch(BATCH_SIZE, 0.25).unwrap()
15191565
);
15201566

1567+
push_batch!("list_short", create_short_list_bench_batch(BATCH_SIZE));
1568+
1569+
push_batch!("map", create_map_bench_batch(BATCH_SIZE, 0.25).unwrap());
1570+
15211571
push_batch!(
15221572
"byte_array_sparse_99pct_null",
15231573
create_byte_array_sparse_bench_batch(BATCH_SIZE, 0.99).unwrap()

‎parquet/benches/level_encoding.rs‎

Lines changed: 167 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,167 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3+
// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4+
5+
//! Definition / repetition level encoding in isolation, fed the way the column
6+
//! writer feeds it: one `put_with_observer` call per mini-batch, with an
7+
//! observer that counts values and updates a level histogram.
8+
9+
use std::hint::black_box;
10+
11+
use criterion::{Criterion, Throughput, criterion_group, criterion_main};
12+
use parquet::encodings::levels::LevelEncoder;
13+
use rand::prelude::*;
14+
15+
const NUM_LEVELS: usize = 64 * 1024;
16+
const MINI_BATCH: usize = 1024;
17+
18+
/// Levels for `List<T>` with nullable list and element: lists of `0..=max_len`
19+
/// elements, `null_pct` percent null lists and null elements.
20+
/// Returns `(def, rep)` with max def 3 and max rep 1.
21+
fn list_levels(rng: &mut StdRng, max_len: usize, null_pct: u32) -> (Vec<i16>, Vec<i16>) {
22+
let mut def = Vec::with_capacity(NUM_LEVELS);
23+
let mut rep = Vec::with_capacity(NUM_LEVELS);
24+
while def.len() < NUM_LEVELS {
25+
if rng.random_range(0..100) < null_pct {
26+
def.push(0);
27+
rep.push(0);
28+
continue;
29+
}
30+
let len = rng.random_range(0..=max_len);
31+
if len == 0 {
32+
def.push(1);
33+
rep.push(0);
34+
continue;
35+
}
36+
for i in 0..len {
37+
def.push(if rng.random_range(0..100) < null_pct {
38+
2
39+
} else {
40+
3
41+
});
42+
rep.push((i != 0) as i16);
43+
}
44+
}
45+
def.truncate(NUM_LEVELS);
46+
rep.truncate(NUM_LEVELS);
47+
(def, rep)
48+
}
49+
50+
/// Levels for `List<List<T>>`, all nullable: max def 5, max rep 2.
51+
fn nested_list_levels(rng: &mut StdRng) -> (Vec<i16>, Vec<i16>) {
52+
let mut def = Vec::with_capacity(NUM_LEVELS);
53+
let mut rep = Vec::with_capacity(NUM_LEVELS);
54+
while def.len() < NUM_LEVELS {
55+
let outer = rng.random_range(0..=4);
56+
if outer == 0 {
57+
def.push(rng.random_range(0..=1));
58+
rep.push(0);
59+
continue;
60+
}
61+
for o in 0..outer {
62+
let first_rep = i16::from(o != 0);
63+
let inner = rng.random_range(0..=4);
64+
if inner == 0 {
65+
def.push(rng.random_range(2..=3));
66+
rep.push(first_rep);
67+
continue;
68+
}
69+
for i in 0..inner {
70+
def.push(rng.random_range(4..=5));
71+
rep.push(if i == 0 { first_rep } else { 2 });
72+
}
73+
}
74+
}
75+
def.truncate(NUM_LEVELS);
76+
rep.truncate(NUM_LEVELS);
77+
(def, rep)
78+
}
79+
80+
/// Runs of random length in `min_run..=max_run`, each a random level in `0..=max_level`.
81+
fn runs(rng: &mut StdRng, max_level: i16, min_run: usize, max_run: usize) -> Vec<i16> {
82+
let mut out = Vec::with_capacity(NUM_LEVELS);
83+
while out.len() < NUM_LEVELS {
84+
let v = rng.random_range(0..=max_level);
85+
let n = rng.random_range(min_run..=max_run);
86+
out.extend(std::iter::repeat_n(v, n));
87+
}
88+
out.truncate(NUM_LEVELS);
89+
out
90+
}
91+
92+
fn shapes() -> Vec<(String, i16, Vec<i16>)> {
93+
let mut rng = StdRng::seed_from_u64(42);
94+
let mut shapes = vec![];
95+
for max_level in [1, 3, 7] {
96+
let levels = (0..NUM_LEVELS)
97+
.map(|_| rng.random_range(0..=max_level))
98+
.collect();
99+
shapes.push((format!("random/max{max_level}"), max_level, levels));
100+
}
101+
shapes.push((
102+
"alternating/max1".to_string(),
103+
1,
104+
(0..NUM_LEVELS).map(|i| (i % 2) as i16).collect(),
105+
));
106+
shapes.push(("mixed_runs/max3".to_string(), 3, runs(&mut rng, 3, 1, 40)));
107+
shapes.push((
108+
"long_runs/max3".to_string(),
109+
3,
110+
runs(&mut rng, 3, 1000, 5000),
111+
));
112+
shapes.push(("uniform/max1".to_string(), 1, vec![1; NUM_LEVELS]));
113+
// 75% valid: mostly short runs of 1 with occasional nulls
114+
shapes.push((
115+
"nullable_25pct/max1".to_string(),
116+
1,
117+
(0..NUM_LEVELS)
118+
.map(|_| (rng.random_range(0..4) != 0) as i16)
119+
.collect(),
120+
));
121+
shapes.push((
122+
"sparse_99pct_null/max1".to_string(),
123+
1,
124+
(0..NUM_LEVELS)
125+
.map(|_| (rng.random_range(0..100) == 0) as i16)
126+
.collect(),
127+
));
128+
let (def, rep) = list_levels(&mut rng, 9, 10);
129+
shapes.push(("list_0_9/def_max3".to_string(), 3, def));
130+
shapes.push(("list_0_9/rep_max1".to_string(), 1, rep));
131+
let (def, rep) = list_levels(&mut rng, 4, 25);
132+
shapes.push(("list_0_4_25pct_null/def_max3".to_string(), 3, def));
133+
shapes.push(("list_0_4_25pct_null/rep_max1".to_string(), 1, rep));
134+
let (def, rep) = nested_list_levels(&mut rng);
135+
shapes.push(("list_list/def_max5".to_string(), 5, def));
136+
shapes.push(("list_list/rep_max2".to_string(), 2, rep));
137+
shapes
138+
}
139+
140+
fn bench_levels(c: &mut Criterion) {
141+
let mut group = c.benchmark_group("level_encoding");
142+
group.throughput(Throughput::Elements(NUM_LEVELS as u64));
143+
for (name, max_level, levels) in shapes() {
144+
// What the column writer does per mini-batch: count values at max level
145+
// and update the page's level histogram
146+
group.bench_function(&name, |b| {
147+
let mut encoder = LevelEncoder::v2_streaming(max_level);
148+
let mut histogram = vec![0i64; max_level as usize + 1];
149+
b.iter(|| {
150+
let mut at_max = 0usize;
151+
for chunk in black_box(levels.as_slice()).chunks(MINI_BATCH) {
152+
encoder.put_with_observer(chunk, |level, count| {
153+
at_max += count * (level == max_level) as usize;
154+
histogram[level as usize] += count as i64;
155+
});
156+
}
157+
black_box(at_max);
158+
encoder.flush_to(|bytes| black_box(bytes.len()))
159+
});
160+
black_box(&histogram);
161+
});
162+
}
163+
group.finish();
164+
}
165+
166+
criterion_group!(benches, bench_levels);
167+
criterion_main!(benches);

0 commit comments

Comments
 (0)