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]

Reply via email to