[C++] LevelDecoder::Decode，internal::FindMinMax consume lots of cpu

[jiangshifu]

Describe the bug, including details regarding any error messages, version, and platform.

[problem]
for a page with 6w int，when call record_reader->SkipRecords(59000);
it consume about 1.1ms

[why]

1. for a batch(1024), call FindMinMax, will compute 2048 times(1024 min, 1024 max)
2. 59000/1024=57 rounds

Component(s)

C++

[jiangshifu]

parquet::internal::standard::FindMinMaxImpl level_comparison_inc.h:51
parquet::internal::FindMinMax level_comparison.cc:77
parquet::LevelDecoder::Decode column_reader.cc:190
parquet::ColumnReaderImplBase::ReadDefinitionLevels column_reader.cc:1004
parquet::TypedColumnReaderImpl::ReadLevels column_reader.cc:1347
parquet::TypedColumnReaderImpl::ReadBatch column_reader.cc:1430
parquet::TypedColumnReaderImpl::Skip column_reader.cc:1553
parquet::internal::TypedRecordReader::SkipRecords column_reader.cc:1946
readCol skip_record.cpp:400
ReadPagesWithPageIndex skip_record.cpp:461
main skip_record.cpp:481
0x0000ffff91486040
__libc_start_main 0x0000ffff91486118
_start 0x00000000004219b0

[parthpathak1201]

I'd like to work on this issue

[jiangshifu]

do you have a suggestion how to optimize this
if select 100 parquet, 5 column, this check will use 550ms cpu

[jiangshifu]

arrow 16

[pitrou]

@jiangshifu Can you please make your bug report understandable? You should be writing for other people who will read you.

[parthpathak1201]

dug through the hotspot, found FindMinMax scanning every decoded level batch — pointless O(n) check for what endpoints alone can catch. Swapped it for O(1). Minor improvement but might do the trick. PR #50550.

if anyone finds something better, lmk

[pitrou]

dug through the hotspot, found FindMinMax scanning every decoded level batch — pointless O(n) check for what endpoints alone can catch.

Why "pointless"? Please explain your analysis.

[parthpathak1201]

for RLE batches, every level is the same value, so checking first & last is the same as checking all of them. for bit-packed, even the full scan can't really guarantee catching corruption... a corrupted value could still land in the valid range. and we already have page CRC for actual corruption detection. so the O(n) scan was just burning cpu without adding much real safety

just seemed like an easy perf win without losing anything meaningful

I can understand why 'pointless' could maybe sound strong here, I was going for something like ~overkill?

[jiangshifu]

@jiangshifu Can you please make your bug report understandable? You should be writing for other people who will read you.

I think parthpathak1201 has understood the problem
1）a parquet file single col(6w rows in a row Group), no compression, no dict
2）when i called record_reader->SkipRecords(59000); #which consume 1.1ms
3）using flame graph，we can see（73% cpu is this call）
parquet::internal::standard::FindMinMaxImpl level_comparison_inc.h:51
parquet::internal::FindMinMax level_comparison.cc:77
parquet::LevelDecoder::Decode column_reader.cc:190
parquet::ColumnReaderImplBase::ReadDefinitionLevels column_reader.cc:1004
parquet::TypedColumnReaderImpl::ReadLevels column_reader.cc:1347
parquet::TypedColumnReaderImpl::ReadBatch column_reader.cc:1430
parquet::TypedColumnReaderImpl::Skip column_reader.cc:1553
parquet::internal::TypedRecordReader::SkipRecords column_reader.cc:1946
readCol skip_record.cpp:400
ReadPagesWithPageIndex skip_record.cpp:461
main skip_record.cpp:481
0x0000ffff91486040
__libc_start_main 0x0000ffff91486118
_start 0x00000000004219b0

in such senario, will call FindMinMaxImpl 59000 times

[pitrou]

for RLE batches, every level is the same value

I think you may be misunderstanding how this encoding works: https://github.com/apache/parquet-format/blob/master/Encodings.md#RLE

for bit-packed, even the full scan can't really guarantee catching corruption... a corrupted value could still land in the valid range. and we already have page CRC for actual corruption detection. so the O(n) scan was just burning cpu without adding much real safety

To decide that the check was useless, you have to check whether any use of the decoded levels relies on the values lying between 0 and max_level - 1.