Optimize Parquet PageIndex by Reusing StringView Prefix
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Is your feature request related to a problem or challenge?
As per #12092, we aim to use StringView as our default string type.
StringView has a 4-byte prefix inline, which we can leverage to calculate the min and max prefix in a page of StringViews efficiently. This approach should be efficent When writing back to the Parquet PageIndex, we can achieve more fine-grained string statistics for every StringView page.
The idea is that once we read a string (byte_array) column from Parquet, **we transfer it to StringView to accelerate queries. This strength of StringView should be maintained when writing back to Parquet.**
### Describe the solution you'd like
Currently, we write the **whole** min/max string (correct me if I'm wrong) to Parquet statistics. I think writing only the prefix for min/max strings would often effectively help us prune out pages.
https://github.com/apache/parquet-format/blob/master/PageIndex.md
> We store lower and upper bounds for the values of each page. These may be the actual minimum and maximum values found on a page, but can also be (more compact) values that do not exist on a page. For example, instead of storing ""Blart Versenwald III", a writer may set min_values[i]="B", max_values[i]="C". This allows writers to truncate large values and writers should use this to enforce some reasonable bound on the size of the index structures.
The Parquet specification also points out that there is no need to store the whole value if a prefix is sufficient to determine whether we can prune a page or not.
This is similar to suffix truncation in B-tree optimization. (If @XiangpengHao could provide some feedback, it would be awesome. I'm a big fan of both Bf-tree and your many StringView magic tricks. Your UTF-8 validation is one of the most beautiful and clear tricks I have seen. )
cc @alamb @XiangpengHao @wiedld
### Describe alternatives you've considered
I found this opportunity to optimize the Parquet PageIndex while reading the `_run_test_statistics_from_parquet_metadata `test. I changed c1 to a really long string `"foooooooooooooooooooooooo"`, and I found that the parquet statistics seem to store the whole string.
### Additional context
_No response_
Contributor guide
Research direction
Start with the _run_test_statistics_from_parquet_metadata test, especially its long-string case, and read the linked Parquet PageIndex specification. Trace how StringView values become Parquet min/max statistics and identify the relevant page-index writing path. Done means the index uses bounded prefixes where safe while preserving correct page pruning, with tests covering long string values.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- data-engineering
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100