Skip to content

Commit 93941b1

Browse files
authored
[improvement](parquet) Fuse nested sparse selection planning (apache#66263)
Parquet V2 repeated leaves currently rebuild a parent-row filter into a level-entry filter, scan definition levels into null runs plus an ancestor-null hash set, build the leaf selection, and scan the levels again to compact surviving parent shapes. This fixed O(level entries) work is especially visible when only 1% or 10% of parent rows survive. This change adds a single-pass nested selection builder. It maps parent filters to repeated entries, classifies ancestor and leaf nulls, builds the decoder selection, appends selected nulls, and compacts repetition/definition levels in place. Ancestor-null placeholders remain in the surviving parent shape but do not consume leaf selection entries. Unfiltered and fully filtered paths keep their existing behavior.
1 parent af6dcff commit 93941b1

10 files changed

Lines changed: 789 additions & 36 deletions

File tree

‎be/benchmark/parquet/AGENTS.md‎

Lines changed: 11 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -43,10 +43,10 @@ be/output/lib/benchmark_test --benchmark_list_tests \
4343
| grep -c '^ParquetDecoder/' # currently 228
4444

4545
be/output/lib/benchmark_test --benchmark_list_tests \
46-
| grep -c '^ParquetKernel/' # currently 80
46+
| grep -c '^ParquetKernel/' # currently 92
4747

4848
be/output/lib/benchmark_test --benchmark_list_tests \
49-
| grep -c '^ParquetReader/' # currently 152
49+
| grep -c '^ParquetReader/' # currently 167
5050
```
5151

5252
When running the binary directly from `be/build_RELEASE/bin`, make sure the JVM and third-party
@@ -120,13 +120,16 @@ cache to manufacture a cold run.
120120
| DELTA_LENGTH_BYTE_ARRAY | BYTE_ARRAY |
121121
| DELTA_BYTE_ARRAY | BYTE_ARRAY |
122122

123-
`ParquetKernel` contains 80 cases across five SIMD-sensitive stages: BYTE_STREAM_SPLIT,
124-
DELTA_PREFIX_SUM, DICTIONARY_GATHER, NULLABLE_EXPAND, and RAW_PREDICATE. It covers the applicable
125-
four- and eight-byte types, three dictionary working-set sizes, 0% through 90% null rates with both
126-
placement patterns, and 0% through 100% raw-predicate selectivities.
123+
`ParquetKernel` contains 92 cases across six decode and selection stages: BYTE_STREAM_SPLIT,
124+
DELTA_PREFIX_SUM, DICTIONARY_GATHER, NULLABLE_EXPAND, RAW_PREDICATE, and NESTED_SELECTION. It covers
125+
the applicable four- and eight-byte types, three dictionary working-set sizes, 0% through 90% null
126+
rates with both placement patterns, 0% through 100% raw-predicate selectivities, and 1%, 10%, and
127+
50% nested parent-row selectivities with both placement patterns. Nested selection registers the
128+
legacy and fused implementations in the same binary and validates both against an independent
129+
source-level oracle before timing.
127130

128131
`ParquetReader` deliberately uses a single-variable matrix rather than a Cartesian product. After
129-
deduplication it contains 152 cases covering:
132+
deduplication it contains 167 cases covering:
130133

131134
- operations: open-to-first-block, full scan, predicate scan, complex residual scan, limit 1, and
132135
limit 1000;
@@ -299,7 +302,7 @@ be simulated by silently changing the local reader benchmark.
299302

300303
## Current validation record
301304

302-
The current expected registration counts are 228 decoder, 80 kernel, and 152 reader cases. A smoke
305+
The current expected registration counts are 228 decoder, 92 kernel, and 167 reader cases. A smoke
303306
run is an execution record only, not a reviewed performance baseline, because repetitions, host
304307
isolation, warmups, cache control, `perf` data, variance, and before/after comparison are not
305308
collected.

‎be/benchmark/parquet/README.md‎

Lines changed: 28 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -39,20 +39,42 @@ be/output/lib/benchmark_test \
3939

4040
## SIMD kernel cases
4141

42-
`ParquetKernel` isolates the five SIMD-sensitive stages from reader setup and virtual consumer
42+
`ParquetKernel` isolates six decode and selection stages from reader setup and virtual consumer
4343
overhead: byte-stream-split transpose, delta prefix sum, numeric dictionary gather, nullable
44-
expansion, and raw predicate evaluation. It covers the applicable 4-byte and 8-byte integer and
45-
floating-point physical types, raw-predicate selectivities from 0% through 100%, and nullable
46-
rates from 0% through 90% with clustered and alternating placement. Dictionary gather uses 32-,
47-
4,096-, and 262,144-entry working sets to separate cache-resident and cache-miss-dominated
48-
behavior.
44+
expansion, raw predicate evaluation, and repeated-level sparse selection. It covers the applicable
45+
4-byte and 8-byte integer and floating-point physical types, raw-predicate selectivities from 0%
46+
through 100%, and nullable rates from 0% through 90% with clustered and alternating placement.
47+
Nested selection covers 1%, 10%, and 50% surviving parent rows with both placement patterns.
48+
Each nested-selection scenario registers both `impl_legacy` and `impl_fused`; both paths use the
49+
same source levels and are checked against an independent oracle before timing.
50+
Dictionary gather uses 32-, 4,096-, and 262,144-entry working sets to separate cache-resident and
51+
cache-miss-dominated behavior.
4952

5053
```shell
5154
be/output/lib/benchmark_test \
5255
--benchmark_filter='^ParquetKernel/(dictionary_gather|nullable_expand)/' \
5356
--benchmark_min_time=0.1s
5457
```
5558

59+
For a reproducible nested-selection comparison, build once and run the two implementations from
60+
that same binary in ABBA order. Pin every command to the same otherwise-idle CPU:
61+
62+
```shell
63+
taskset -c 8 be/output/lib/benchmark_test \
64+
--benchmark_filter='^ParquetKernel/nested_selection/.*/impl_legacy$' \
65+
--benchmark_min_time=1s --benchmark_repetitions=10 \
66+
--benchmark_report_aggregates_only=true \
67+
--benchmark_out=nested-legacy-a1.json --benchmark_out_format=json
68+
69+
taskset -c 8 be/output/lib/benchmark_test \
70+
--benchmark_filter='^ParquetKernel/nested_selection/.*/impl_fused$' \
71+
--benchmark_min_time=1s --benchmark_repetitions=10 \
72+
--benchmark_report_aggregates_only=true \
73+
--benchmark_out=nested-fused-b1.json --benchmark_out_format=json
74+
75+
# Repeat fused as B2, then legacy as A2, changing only --benchmark_out.
76+
```
77+
5678
## Local reader cases
5779

5880
`ParquetReader` measures local open-to-first-block, full scan, predicate scan, complex residual

0 commit comments

Comments
 (0)