apache / apache/datafusion

Optimize Parquet PageIndex by Reusing StringView Prefix

Open
#12,755 2 comments 2 reactions 0 assignees View on GitHub
enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.