Abdallah-Afifi commented on code in PR #11984:
URL: https://github.com/apache/arrow-rs/pull/11984#discussion_r4575363205
##########
parquet/src/encodings/encoding/alp_encoder.rs:
##########
@@ -1125,4 +1125,151 @@ mod tests {
"a leading empty page must not affect encoding of the first
nonempty page"
);
}
+ /// Lower bound on what ALP could achieve for `values`: for every vector
+ /// independently, the best `(exponent, factor)` pair over every pair the
format
+ /// allows, chosen with full knowledge of the vector rather than from a
sample.
+ ///
+ /// Each single-vector `encode_page` carries its own header and one
offset, so that
+ /// fixed cost is subtracted per vector and the real page overhead added
once.
+ fn per_vector_exhaustive_size<F: AlpFloat>(values: &[F]) -> usize {
+ let mut scratch = Scratch::<F>::new();
+ let num_vectors = values.len().div_ceil(VECTOR_SIZE);
+ let per_vector_overhead = ALP_HEADER_SIZE + std::mem::size_of::<u32>();
+
+ let mut body = 0;
+ for vector in values.chunks(VECTOR_SIZE) {
+ let mut best = usize::MAX;
+ for exponent in 0..=F::MAX_EXPONENT {
+ for factor in 0..=exponent {
+ let params = ExponentAndFactor { exponent, factor };
+ if let Ok(page) = encode_page(vector, &[params], &mut
scratch) {
+ best = best.min(page.len() - per_vector_overhead);
+ }
+ }
+ }
+ body += best;
+ }
+ ALP_HEADER_SIZE + num_vectors * std::mem::size_of::<u32>() + body
+ }
+
+ /// What the sampling heuristic actually produces for the same input.
+ fn heuristic_size<F: AlpFloat>(values: &[F]) -> usize {
+ let mut scratch = Scratch::<F>::new();
+ let preset = build_preset(values);
+ encode_page(values, &preset, &mut scratch).unwrap().len()
+ }
+
+ /// The two-level sampling must land close to exhaustive parameter search
on
+ /// structured data, including inputs whose scale changes partway through
the page
+ /// or between vectors - cases where sampling only eight vectors, and 256
of the
+ /// 1024 values within each, could in principle mislead it.
+ #[test]
+ fn test_sampling_close_to_exhaustive_on_structured_data() {
+ let n = 8 * VECTOR_SIZE;
Review Comment:
Good catch, and you were right — I reproduced your numbers exactly: 29,769
vs 20,759 at 16 vectors.
The reason is worse than one missing case. With exactly `SAMPLE_VECTORS`
vectors, `vector_stride` is 1, so *every* heterogeneous case I wrote measured
nothing at all. That is why they all came out at 1.000x and why I wrongly
concluded the heuristic was robust to vectors being skipped. Everything is now
on 16-vector pages, and two of those cases moved:
| input | 8 vectors (stride 1) | 16 vectors (stride 2) |
| --- | --- | --- |
| scale alternates per vector | 1.002x | **4.454x** |
| single anomalous vector at an unsampled index | 1.003x | **1.434x** |
The alternating case is the bad one: at stride 2 only even vectors are
sampled, so every odd vector gets parameters picked for data it has nothing in
common with.
It is also not just a synthetic concern. A default 1 MiB data page holds 128
`f64` vectors and `build_preset` samples 8, so 120 go unsampled — I added
`test_build_preset_skips_vectors_past_the_sample_budget` to pin that, since the
gap tests rest on it.
Both gaps are pinned as ranges now, and the high-entropy case is documented
as a separate mechanism (the sampled estimate mis-ranking parameters) rather
than lumped in with skipping. Thanks for pushing on this.
--
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]