Rich-T-kid commented on code in PR #11984:
URL: https://github.com/apache/arrow-rs/pull/11984#discussion_r4571204088


##########
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:
   Could we make one of these cases longer than `SAMPLE_VECTORS` so the 
changed-scale vector is actually skipped by `build_preset`? With exactly eight 
vectors, `vector_stride` is 1, so every vector including the last one is 
sampled. I tried the same last-vector case with 16 vectors; the last vector is 
then skipped and the heuristic came out 1.434x larger than the exhaustive 
result (29,769 vs 20,759 bytes). That seems worth capturing here, the same way 
the high-entropy gap is pinned below.



-- 
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