prtkgaur opened a new pull request, #55580:
URL: https://github.com/apache/arrow/pull/55580
### Rationale for this change
Pages of values with no decimal form, such as full-precision measurements,
come out larger under
ALP than under PLAIN, because ALP stores each value as an exception. The
writer has no way out
today.
The preset sampling can also be simpler. It picks spots spread through the
page and takes a few
values at each, but it does this through fixed-size chunks, a stride derived
from a fixed
interval, a second sample inside each chunk, and a rule for short chunks.
The ALP paper samples
whole vectors directly.
### What changes are included in this PR?
- A page is written as PLAIN when its ALP encoding would be larger. The
buffered values are
already in PLAIN layout, so this costs no extra copy. `Encoder` gains a
virtual
`flushed_encoding()`, defaulting to `encoding()`, so the column writer can
record each page's
encoding in its header, the encoding stats and the column chunk's
encodings list.
- The first sampling level picks whole vectors directly, at the same spacing
as before:
```
Before: every 4th 4,096-value chunk; 256 values from the first 1,024 of each
| chunk 0 | chunk 1 | chunk 2 | chunk 3 | chunk 4 | ...
[##..] [##..]
After: 8 vectors spread evenly per 131,072 values (128 vectors);
32 values from each, at fixed-seed pseudo-random positions
| v0 | v1 | ... | v16 | ... | v32 | ... | v112 | ... | v127 |
^ ^ ^ ^
```
Pages smaller than 131,072 values get up to 8 sampled vectors. The
pseudo-random positions keep
the sample from lining up with data that repeats, and the fixed seed keeps
the output
deterministic.
- The per-vector search tries every candidate in the preset. Its early exit
never triggered with
a five-candidate preset, so output is unchanged.
The file format and the decoder do not change.
Measured on real-world double columns, main against this PR, through the
Parquet writer with every
page read back (aarch64, `-O3`):
| Data | Values per page | Size | Encode time |
|---|---:|---:|---:|
| parquet-testing floating-point set, 42 columns | 15,000 | -15.7% | +15% |
| Public BI, 28 columns | 20,000 | -2.3% | -28% |
| Public BI, 28 columns | 50,000 | -1.2% | -41% |
| Public BI, 28 columns | 262,144 | -0.4% | -43% |
Most of the parquet-testing gain is the PLAIN fallback, since several of
those columns are larger
than PLAIN under ALP. Encoding is slower there because main always ended up
with a one-pair
preset on those pages and skipped the per-vector search, which now runs. On
larger pages the new
sampler reads fewer values and encoding gets faster.
Left for later: the per-vector search still uses 256 evenly spaced values,
which kept output
smaller than using 32; only doubles were measured on real data; and the
fallback could skip the
full ALP encode by deciding from the sample.
### Are these changes tested?
Yes.
### Are there any user-facing changes?
ALP column chunks may now contain PLAIN pages. `Encoder` gains a virtual
`flushed_encoding()` with
a default implementation; nothing breaks.
* GitHub Issue: #55579
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
