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

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]

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

Component(s)

C++

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

I'd like to work on this issue

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

arrow 16

@jiangshifu

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

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

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.

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 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

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.

fair point, I was wrong about RLE. still think it's a ~4% easy win for files with CRC enabled, but I don't have a strong opinion. happy to revert or adjust however you prefer.

@emkornfield

For the record, the min-max check was added by @emkornfield in https://github.com/apache/arrow/pull/8177/changes#diff-05802abb678d7f865de06497651d9ca057bf0b44ec37ceeae2a5d720ffe98e28R160-R168

I think we have 3-4 options here:

determine that the check is unnecessary and remove it entirely
determine that the check is necessary and:
a) decide it's cheap enough and not worth optimizing
b) consider it too expensive, optimize the non-AVX2 version to be better autovectorizable (or hand-optimize it using xsimd)
c) consider it too expensive, fold the min-max checking into the decoding itself (which would be a win for large RLE runs)

However, the approach of only checking the first and last values does not make sense, IMHO :-)

cc @AntoinePrv for opinions

I have some issue understanding the scope here.

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

What is 6w int?

1. for a batch(1024), call FindMinMax, will compute 2048 times(1024 min, 1024 max)

Where does 1024 comes from here?

Also what version of Arrow is this on? We recently made changes here so I am wondering if this is referring to a regression, or if this was existing behavior.

I have some issue understanding the scope here.

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

What is 6w int?
1. for a batch(1024), call FindMinMax, will compute 2048 times(1024 min, 1024 max)
Where does 1024 comes from here?

Also what version of Arrow is this on? We recently made changes here so I am wondering if this is referring to a regression, or if this was existing behavior.

6w is 60000 rows int
1024 is constexpr int64_t kSkipScratchBatchSize = 1024;

@emkornfield

For the record, the min-max check was added by @emkornfield in https://github.com/apache/arrow/pull/8177/changes#diff-05802abb678d7f865de06497651d9ca057bf0b44ec37ceeae2a5d720ffe98e28R160-R168

I believe this replaced existing checks: https://github.com/apache/arrow/pull/8177/changes#diff-05802abb678d7f865de06497651d9ca057bf0b44ec37ceeae2a5d720ffe98e28L1173

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.

I would need to double check but I think negative values might be impossible, so we could at least get rid of that check.

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.

This isn't just about corruption necessarily but making sure the reader is hardened against bugs, or malicious values.

Valid optimization I can see:

Push down the check for at least RLE runs
If we guarantee only non-negative values are possible in decoding, remove the min check.
remove the check if max repetition/max definition level is out a power of 2 or zero.

This isn't just about corruption necessarily but making sure the reader is hardened against bugs, or malicious values.

Could we make this check optional and toggled by a property? In some cases, users can trust their data and thus be free of integrity check.

Could we make this check optional and toggled by a property? In some cases, users can trust their data and thus be free of integrity check.

Maybe we special case for skip records specifically? It seems like it might be more of a maintence burden/confusion to actually make it generally toggleable?

@jiangshifu

Also what version of Arrow is this on? We recently made changes here so I am wondering if this is referring to a regression, or if this was existing behavior.

@jiangshifu would you mind checking the version you are running. We recently shipped a improvement to LevelDecoder::Skip in GH-50422 (not reased yet), so perhaps this could fit your needs.

Also what version of Arrow is this on? We recently made changes here so I am wondering if this is referring to a regression, or if this was existing behavior.

@jiangshifu would you mind checking the version you are running. We recently shipped a improvement to LevelDecoder::Skip in GH-50422 (not reased yet), so perhaps this could fit your needs.

my test is based on 16.0.0 debug version

my test is based on 16.0.0 debug version

FTR, performance results are only relevant on optimized builds.

Navigation Menu

Repository navigation

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

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

Component(s)

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

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

Description

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

Component(s)

Activity

jiangshifu commented on Jul 20, 2026

parthpathak1201 commented on Jul 20, 2026

jiangshifu commented on Jul 20, 2026

jiangshifu commented on Jul 20, 2026

pitrou commented on Jul 20, 2026

parthpathak1201 commented on Jul 20, 2026

pitrou commented on Jul 20, 2026

parthpathak1201 commented on Jul 20, 2026

jiangshifu commented on Jul 20, 2026

pitrou commented on Jul 20, 2026

parthpathak1201 commented on Jul 20, 2026

pitrou commented on Jul 20, 2026

AntoinePrv commented on Jul 20, 2026

jiangshifu commented on Jul 21, 2026

emkornfield commented on Jul 21, 2026

wgtmac commented on Jul 24, 2026

emkornfield commented on Jul 24, 2026

AntoinePrv commented on Jul 24, 2026

jiangshifu commented on Jul 29, 2026

pitrou commented on Jul 29, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions