You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "andygrove (via GitHub)" <gi...@apache.org> on 2026/10/13 17:08:56 UTC

[PR] perf: make the native Iceberg writer's dictionary pre-pass 1.6x to 3.1x faster [datafusion-comet]

andygrove opened a new pull request, #6937:
URL: https://github.com/apache/datafusion-comet/pull/6937

   ## Which issue does this PR close?
   
   Closes #6914.
   
   Part of #6911.
   
   ## Rationale for this change
   
   Before a partition's first rows reach the native Iceberg writer, `DictionaryChooser` replays parquet-mr's first-page dictionary decision for every column. In the profile of the end-to-end Iceberg benchmark (#6910) that pre-pass is 1.7% of all CPU for nested types and 2.4% for primitives, and a fanout write pays it once per partition. Most of it was overhead around the accounting rather than the accounting itself:
   
   - every value went through a boxed `dyn Fn` to get its bytes, and every nested entry through a chain of boxed iterators (about a third of the pre-pass for nested types);
   - every value, fixed-width ones included, was hashed and compared as a byte slice;
   - each column built its set from empty, so the set rehashed its way up again for every column (7% of the pre-pass for nested types, 22% for primitives).
   
   ## What changes are included in this PR?
   
   The decision logic (`FirstPage::add`, `keeps_dictionary`, `HybridRuns`) is unchanged; how values reach it is rewritten:
   
   - **Typed keys.** The column's Arrow type, known from the schema, picks the key once per column. Fixed-width values of up to 8 bytes become a `u64` of their bits, 16-byte values such as decimals a `u128`, and strings, binaries and wider values a byte slice that carries its hash. Byte keys are hashed once, with the set's own randomly seeded hasher as before, and two values whose hashes differ are told apart without comparing their bytes.
   - **No boxed iterators.** `Leaf::path` resolves, per batch, the arrays on the way to the leaf. Rows are then visited one at a time by a small recursive walk that iterates the last level's range directly, so the page still reads nothing past where it ends.
   - **Sized, reused sets.** One set per kind of key, emptied for each column and reused. Each is sized up front from the leaf entries under the rows the page can take (an `O(levels)` walk over offsets per batch), capped at the most values the column's dictionary limit lets it hold and at 65,536, past which a set grows only as distinct values arrive.
   - **Repeats skip the set.** A value equal to the one before it is already in the dictionary, so it skips the hash insert.
   - A criterion benchmark, `native/core/benches/iceberg_dictionary_chooser.rs`, times one partition's choice over the column groups of `CometIcebergEndToEndBenchmark`: 20,000-row samples in 8192-row batches at Iceberg's default page and dictionary sizes, plus a 1000-row primitives sample for the small partitions of a fanout write. `DictionaryChooser` is re-exported `#[doc(hidden)]` for it, as the shuffle crate does with `bench_support`.
   
   Results on an Apple M3 Ultra, criterion against a baseline saved from unmodified `main`:
   
   | Shape           | `main`   | This PR | Speedup |
   | --------------- | -------- | ------- | ------- |
   | `primitives`    | 3.55 ms  | 1.42 ms | 2.5x    |
   | `primitives_1k` | 192 µs   | 63 µs   | 3.1x    |
   | `structs`       | 3.14 ms  | 1.33 ms | 2.4x    |
   | `arrays`        | 5.58 ms  | 2.48 ms | 2.3x    |
   | `maps`          | 5.24 ms  | 3.12 ms | 1.7x    |
   | `nested`        | 11.37 ms | 7.24 ms | 1.6x    |
   
   With the pre-pass at 1.7% (nested) to 2.4% (primitives) of the end-to-end benchmark's CPU, that should take roughly 0.6% to 1.4% off its total. That is an estimate from the profile, not an end-to-end measurement.
   
   The method follows the `optimize-comet-expression` skill: baseline from unmodified source, decisions identical to `main`, and every shape faster.
   
   ## How are these changes tested?
   
   The existing tests pass, including the ones that pin answers recorded from parquet-mr. Two of them changed:
   
   - `a_column_is_read_only_as_far_as_its_first_page` counted the top-level iterator's rows, which no longer exists. It now counts the values the page reads: exactly the 819,200 of its first 100 rows.
   - `values_under_a_null_list_are_not_counted` put its null list in row 0. A column whose dictionary overflows within its first row has a page of no rows and is left as configured, on `main` as here, so the test passed even when the values under a null list were counted. A valid row now comes first, and the test fails if the null check on an intermediate level is removed.
   
   New test `reads_every_leaf_type` covers every leaf type the dispatch handles (ints, longs, floats, doubles, dates, times, timestamps, `Decimal128` at both physical widths, `Decimal256`, and the string, binary and view types), flat and under large and fixed-size lists, in each of which ten values keep their dictionary and distinct values do not.
   
   To check that the rewrite makes the same decisions as `main`, I also ran a differential test, not included here, that compared this implementation with `main`'s over 50,000 random cases: random nestings of structs, lists, large lists, fixed-size lists and maps over every leaf type, random cardinalities, run lengths and null densities at every level (including null lists that span child values), samples sliced at an offset and cut into random batches (some empty), and random page row, page size and dictionary limits. Every column got the same answer (130,742 kept their dictionary, 62,538 did not), and removing the intermediate null check made it fail.
   


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] perf: make the native Iceberg writer's dictionary pre-pass 1.8x to 3.9x faster [datafusion-comet]

Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove merged PR #6937:
URL: https://github.com/apache/datafusion-comet/pull/6937


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] perf: make the native Iceberg writer's dictionary pre-pass 1.8x to 3.9x faster [datafusion-comet]

Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on code in PR #6937:
URL: https://github.com/apache/datafusion-comet/pull/6937#discussion_r4296031415


##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -1253,6 +1677,26 @@ mod tests {
         );
     }
 
+    /// The fields of a null struct are not part of the column chunk either.
+    #[test]
+    fn values_under_a_null_struct_are_not_counted() {

Review Comment:
   > I read the code to check this and did not run a mutation.
   
   I ran the mutations on c2f688c4a8. `a_sliced_batch_is_read_only_within_its_slice` fails on each of these, and no other chooser test does:
   
   - large-list offsets taken relative to the slice in [`Children::start`](https://github.com/apache/datafusion-comet/blob/c2f688c4a8802e88d18e155f25a8b04f704e145b/native/core/src/execution/operators/iceberg_dictionary.rs#L449)
   - the fixed-size-list start shifted by one element in [`Children::start`](https://github.com/apache/datafusion-comet/blob/c2f688c4a8802e88d18e155f25a8b04f704e145b/native/core/src/execution/operators/iceberg_dictionary.rs#L450)
   - the large list's null buffer ignored in [`Leaf::path`](https://github.com/apache/datafusion-comet/blob/c2f688c4a8802e88d18e155f25a8b04f704e145b/native/core/src/execution/operators/iceberg_dictionary.rs#L379-L382)
   - the fixed-size list's null buffer ignored in [`Leaf::path`](https://github.com/apache/datafusion-comet/blob/c2f688c4a8802e88d18e155f25a8b04f704e145b/native/core/src/execution/operators/iceberg_dictionary.rs#L383-L386)
   - either arm returning `None`, which leaves every column as configured
   
   So `ll` and `fl` cover everything the removed half of `reads_every_leaf_type` checked.



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] perf: make the native Iceberg writer's dictionary pre-pass 1.8x to 3.9x faster [datafusion-comet]

Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on code in PR #6937:
URL: https://github.com/apache/datafusion-comet/pull/6937#discussion_r4286328097


##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -254,139 +343,234 @@ fn collect_leaves(data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>)
                 descend(Step::Key, fields[0].data_type(), leaf, leaves);
                 descend(Step::Value, fields[1].data_type(), leaf, leaves);
             }
-            _ => leaves.push(leaf.clone()),
+            _ => leaves.push((leaf.clone(), data_type.clone())),
         },
-        _ => leaves.push(leaf.clone()),
+        _ => leaves.push((leaf.clone(), data_type.clone())),
     }
 }
 
-fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>) {
+fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<(Leaf, DataType)>) {
     leaf.steps.push(step);
     collect_leaves(data_type, leaf, leaves);
     leaf.steps.pop();
 }
 
-/// `(row, index)` pairs, one per entry of an array that the column chunk stores: its row of the
-/// batch, and its index into the array.
-type Entries<'a> = Box<dyn Iterator<Item = (u32, usize)> + 'a>;
-
 impl Leaf {
-    /// The leaf's array in `batch`, with the entries of it that lie under the rows `top` yields and
-    /// whose ancestors are all present, in the order the column chunk stores them. Nothing is
-    /// expanded ahead: each entry is produced when the page asks for it. `None` when `batch` does
-    /// not have the shape the schema promised.
-    fn entries<'a>(
-        &self,
-        batch: &'a RecordBatch,
-        top: Entries<'a>,
-    ) -> Option<(&'a dyn Array, Entries<'a>)> {
+    /// The arrays of `batch` the way to the leaf passes through, or `None` when `batch` does not
+    /// have the shape the schema promised.
+    fn path<'a>(&self, batch: &'a RecordBatch) -> Option<Path<'a>> {
         let mut array = batch.columns().get(self.column)?.as_ref();
-        let mut entries = top;
+        let mut levels = Vec::with_capacity(self.steps.len());
         for step in &self.steps {
-            let present = present(array, entries);
-            (array, entries) = match (step, array.data_type()) {
+            let (children, next) = match (step, array.data_type()) {
                 (Step::Field(field), DataType::Struct(_)) => {
-                    (array.as_struct().columns().get(*field)?.as_ref(), present)
+                    (Children::Same, array.as_struct().columns().get(*field)?)
                 }
                 (Step::Element, DataType::List(_)) => {
                     let list = array.as_list::<i32>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
+                    (Children::Offsets(list.value_offsets()), list.values())
                 }
                 (Step::Element, DataType::LargeList(_)) => {
                     let list = array.as_list::<i64>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
-                }
-                (Step::Element, DataType::FixedSizeList(_, size)) => {
-                    let size = *size as usize;
-                    let elements: Entries<'a> = Box::new(present.flat_map(move |(row, index)| {
-                        (index * size..(index + 1) * size).map(move |element| (row, element))
-                    }));
-                    (array.as_fixed_size_list().values().as_ref(), elements)
+                    (Children::LargeOffsets(list.value_offsets()), list.values())
                 }
+                (Step::Element, DataType::FixedSizeList(_, size)) => (
+                    Children::Fixed(*size as usize),
+                    array.as_fixed_size_list().values(),
+                ),
                 (Step::Key, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (map.keys().as_ref(), children(present, map.value_offsets()))
+                    (Children::Offsets(map.value_offsets()), map.keys())
                 }
                 (Step::Value, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (
-                        map.values().as_ref(),
-                        children(present, map.value_offsets()),
-                    )
+                    (Children::Offsets(map.value_offsets()), map.values())
                 }
                 _ => return None,
             };
+            // A null buffer with no nulls in it is as good as none, and a struct without nulls
+            // leads every entry straight to its field's, so neither needs a level.
+            let nulls = present_nulls(array);
+            if nulls.is_some() || !matches!(children, Children::Same) {
+                levels.push(Level { nulls, children });
+            }
+            array = next.as_ref();
         }
-        Some((array, entries))
+        Some(Path {
+            levels,
+            leaf: array,
+        })
     }
 }
 
-/// The entries whose value in `array` is not null.
-fn present<'a>(array: &'a dyn Array, entries: Entries<'a>) -> Entries<'a> {
-    match array.nulls() {
-        Some(nulls) => Box::new(entries.filter(move |&(_, index)| nulls.is_valid(index))),
-        None => entries,
-    }
+/// The arrays the way from a batch's column down to one leaf column passes through.
+struct Path<'a> {
+    /// One for each step, from the batch's column down.
+    levels: Vec<Level<'a>>,
+    /// The leaf column's array.
+    leaf: &'a dyn Array,
 }
 
-/// The entries of the children of every list or map entry in `entries`.
-fn children<'a, O: OffsetSizeTrait>(entries: Entries<'a>, offsets: &'a [O]) -> Entries<'a> {
-    Box::new(entries.flat_map(move |(row, index)| {
-        (offsets[index].as_usize()..offsets[index + 1].as_usize()).map(move |child| (row, child))
-    }))
+/// An array on the way to a leaf, and how its entries lead into the next one.
+struct Level<'a> {
+    /// A null entry has nothing under it in the column chunk, even where a null list spans child
+    /// values.
+    nulls: Option<&'a NullBuffer>,
+    children: Children<'a>,
 }
 
-type ValueBytes<'a> = Box<dyn Fn(usize) -> &'a [u8] + 'a>;
+/// The entries of the next array that lie under entry `i` of a level.
+#[derive(Clone, Copy)]
+enum Children<'a> {
+    /// A struct's: entry `i` of its field.
+    Same,
+    /// A list's or a map's: entries `offsets[i]` up to `offsets[i + 1]` of its elements, keys or
+    /// values.
+    Offsets(&'a [i32]),
+    /// A large list's.
+    LargeOffsets(&'a [i64]),
+    /// A fixed-size list's: the `size` elements from `i * size`.
+    Fixed(usize),
+}
 
-/// The bytes that tell `array`'s values apart: a fixed-width value's native bytes, or a string's or
-/// binary's content. `None` for a type an Iceberg schema cannot produce.
-fn value_bytes<'a>(array: &'a dyn Array) -> Option<ValueBytes<'a>> {
-    let bytes: ValueBytes<'a> = downcast_primitive_array!(
-        array => Box::new(move |i| array.values()[i].to_byte_slice()),
-        DataType::Utf8 => {
-            let array = array.as_string::<i32>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::LargeUtf8 => {
-            let array = array.as_string::<i64>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Utf8View => {
-            let array = array.as_string_view();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Binary => {
-            let array = array.as_binary::<i32>();
-            Box::new(move |i| array.value(i))
-        }
-        DataType::LargeBinary => {
-            let array = array.as_binary::<i64>();
-            Box::new(move |i| array.value(i))
+impl Children<'_> {
+    /// Where the entries under entry `index` start in the next array. Those under the entries
+    /// before `index` end there too, so this also holds for one past the last entry.
+    fn start(self, index: usize) -> usize {
+        match self {
+            Children::Same => index,
+            Children::Offsets(offsets) => offsets[index] as usize,
+            Children::LargeOffsets(offsets) => offsets[index] as usize,
+            Children::Fixed(size) => index * size,
         }
-        DataType::BinaryView => {
-            let array = array.as_binary_view();
-            Box::new(move |i| array.value(i))
+    }
+}
+
+impl Path<'_> {
+    /// How many entries of the leaf array lie under the batch's first `rows` rows, null or not.
+    fn entries(&self, rows: usize) -> usize {
+        let (start, end) = self.levels.iter().fold((0, rows), |(start, end), level| {
+            (level.children.start(start), level.children.start(end))
+        });
+        end - start
+    }
+
+    /// Calls `f` with the leaf index of every entry under the batch's row `row` whose ancestors
+    /// are all present, in the order the column chunk stores them, until `f` returns `false`.
+    /// Returns whether every entry was visited. Nothing is expanded ahead, so a page that ends
+    /// partway through a batch reads no further.
+    fn visit(&self, row: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+        // A leaf with no levels above it has one entry per row: the row itself.
+        if self.levels.is_empty() {
+            return f(row);
         }
-        _ => return None,
-    );
-    Some(bytes)
+        visit(&self.levels, row, f)
+    }
+}
+
+/// `array`'s nulls, or `None` when it has none.
+fn present_nulls(array: &dyn Array) -> Option<&NullBuffer> {
+    array.nulls().filter(|nulls| nulls.null_count() > 0)
+}
+
+fn visit(levels: &[Level], index: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+    let Some((level, below)) = levels.split_first() else {
+        return f(index);
+    };
+    if level.nulls.is_some_and(|nulls| nulls.is_null(index)) {
+        return true;
+    }
+    let mut children = level.children.start(index)..level.children.start(index + 1);
+    // The leaf's entries are visited here rather than one call deeper each.
+    if below.is_empty() {
+        children.all(f)
+    } else {
+        children.all(|child| visit(below, child, &mut *f))
+    }
+}
+
+/// Reads fixed-width values by their bits, zero-extended to `K`, which is at least as wide.
+fn bits<T: ArrowNativeType, K: Bits>(values: &[T]) -> impl Fn(usize) -> (K, usize) + '_ {
+    move |index| (K::of(values[index]), size_of::<T>())
+}
+
+/// Reads fixed-width values too wide for [`bits`] by their native bytes.
+fn native_bytes<'a, T: ArrowNativeType>(values: &'a [T]) -> impl Fn(usize) -> (Bytes<'a>, usize) {
+    move |index| Bytes::of(values[index].to_byte_slice())

Review Comment:
   Done in c2f688c4a8. The readers now return the plain size: the candidate's `width` for fixed-width values and `4 + len` for byte arrays. `FirstPage::width` is gone and `add` takes the size directly. `Bytes::of` went with it, since nothing else used it. `judge_primitive` takes the width from the candidate and makes no choice if it is somehow missing.



##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -1253,6 +1677,26 @@ mod tests {
         );
     }
 
+    /// The fields of a null struct are not part of the column chunk either.
+    #[test]
+    fn values_under_a_null_struct_are_not_counted() {

Review Comment:
   I kept `values_under_a_null_struct_are_not_counted`, for the reason viirya gives: it is small and pins the struct-null check on its own. I did drop the large-list and fixed-size-list half of `reads_every_leaf_type`, since `ll` and `fl` in the sliced test cover those types with nulls and a slice on top. That is in c2f688c4a8. I read the code to check this and did not run a mutation.



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] perf: make the native Iceberg writer's dictionary pre-pass 1.8x to 3.9x faster [datafusion-comet]

Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on PR #6937:
URL: https://github.com/apache/datafusion-comet/pull/6937#issuecomment-6217807053

   @comphead @mbutrovich could you take another look?


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] perf: make the native Iceberg writer's dictionary pre-pass 1.8x to 3.9x faster [datafusion-comet]

Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on PR #6937:
URL: https://github.com/apache/datafusion-comet/pull/6937#issuecomment-6175840728

   @viirya here are end-to-end numbers. I ran `CometIcebergEndToEndBenchmark`'s corpus, session and statement with release builds of `main` and of this PR, two alternating runs of each on an M3 Max. The PR has no JVM changes, so only libcomet differed. Besides the benchmark's unpartitioned target, I added a fanout case that writes a target partitioned by `bucket(16, id)` with the fanout writer. Each task's 210,000 or so rows split into 16 partitions of about 13,000, so every row goes through the pre-pass: 160 pre-passes per statement, against 10 for the unpartitioned target.
   
   Whole-statement times were noisy on a shared machine. The iceberg-java writer, which doesn't run the chooser, moved by up to 7% between runs. So I also logged the CPU time of every pre-pass inside the pipeline, summed it per statement, and took the median of 14 statements per build. The pre-pass's share of a statement's CPU time:
   
   | Types        | Unpartitioned, `main` | This PR | Fanout, `main` | This PR |
   | ------------ | --------------------- | ------- | -------------- | ------- |
   | `primitives` | 2.1%                  | 0.6%    | 13.8%          | 5.6%    |
   | `structs`    | 2.8%                  | 1.1%    | 17.8%          | 9.1%    |
   | `arrays`     | 2.6%                  | 1.0%    | 19.0%          | 9.0%    |
   | `maps`       | 2.3%                  | 1.4%    | 17.2%          | 11.1%   |
   | `nested`     | 2.2%                  | 1.3%    | 17.8%          | 11.0%   |
   
   For the stock, unpartitioned benchmark that saves 0.9% to 1.8% of the CPU. That matches the estimate, and it's too small for wall time to resolve here. For the fanout write it saves 7.5% to 11.4%, and median statement CPU fell 6% to 16% and wall time 1% to 8%. So the change matters mostly for fanout writes into many partitions, where every row is sampled. I've put these numbers in the description in place of the estimate.
   


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] perf: make the native Iceberg writer's dictionary pre-pass 1.8x to 3.9x faster [datafusion-comet]

Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #6937:
URL: https://github.com/apache/datafusion-comet/pull/6937#discussion_r4275911379


##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -254,139 +343,230 @@ fn collect_leaves(data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>)
                 descend(Step::Key, fields[0].data_type(), leaf, leaves);
                 descend(Step::Value, fields[1].data_type(), leaf, leaves);
             }
-            _ => leaves.push(leaf.clone()),
+            _ => leaves.push((leaf.clone(), data_type.clone())),
         },
-        _ => leaves.push(leaf.clone()),
+        _ => leaves.push((leaf.clone(), data_type.clone())),
     }
 }
 
-fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>) {
+fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<(Leaf, DataType)>) {
     leaf.steps.push(step);
     collect_leaves(data_type, leaf, leaves);
     leaf.steps.pop();
 }
 
-/// `(row, index)` pairs, one per entry of an array that the column chunk stores: its row of the
-/// batch, and its index into the array.
-type Entries<'a> = Box<dyn Iterator<Item = (u32, usize)> + 'a>;
-
 impl Leaf {
-    /// The leaf's array in `batch`, with the entries of it that lie under the rows `top` yields and
-    /// whose ancestors are all present, in the order the column chunk stores them. Nothing is
-    /// expanded ahead: each entry is produced when the page asks for it. `None` when `batch` does
-    /// not have the shape the schema promised.
-    fn entries<'a>(
-        &self,
-        batch: &'a RecordBatch,
-        top: Entries<'a>,
-    ) -> Option<(&'a dyn Array, Entries<'a>)> {
+    /// The arrays of `batch` the way to the leaf passes through, or `None` when `batch` does not
+    /// have the shape the schema promised.
+    fn path<'a>(&self, batch: &'a RecordBatch) -> Option<Path<'a>> {
         let mut array = batch.columns().get(self.column)?.as_ref();
-        let mut entries = top;
+        let mut levels = Vec::with_capacity(self.steps.len());
         for step in &self.steps {
-            let present = present(array, entries);
-            (array, entries) = match (step, array.data_type()) {
+            let (children, next) = match (step, array.data_type()) {
                 (Step::Field(field), DataType::Struct(_)) => {
-                    (array.as_struct().columns().get(*field)?.as_ref(), present)
+                    (Children::Same, array.as_struct().columns().get(*field)?)
                 }
                 (Step::Element, DataType::List(_)) => {
                     let list = array.as_list::<i32>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
+                    (Children::Offsets(list.value_offsets()), list.values())
                 }
                 (Step::Element, DataType::LargeList(_)) => {
                     let list = array.as_list::<i64>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
-                }
-                (Step::Element, DataType::FixedSizeList(_, size)) => {
-                    let size = *size as usize;
-                    let elements: Entries<'a> = Box::new(present.flat_map(move |(row, index)| {
-                        (index * size..(index + 1) * size).map(move |element| (row, element))
-                    }));
-                    (array.as_fixed_size_list().values().as_ref(), elements)
+                    (Children::LargeOffsets(list.value_offsets()), list.values())
                 }
+                (Step::Element, DataType::FixedSizeList(_, size)) => (
+                    Children::Fixed(*size as usize),
+                    array.as_fixed_size_list().values(),
+                ),
                 (Step::Key, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (map.keys().as_ref(), children(present, map.value_offsets()))
+                    (Children::Offsets(map.value_offsets()), map.keys())
                 }
                 (Step::Value, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (
-                        map.values().as_ref(),
-                        children(present, map.value_offsets()),
-                    )
+                    (Children::Offsets(map.value_offsets()), map.values())
                 }
                 _ => return None,
             };
+            // A null buffer with no nulls in it is as good as none, and a struct without nulls
+            // leads every entry straight to its field's, so neither needs a level.
+            let nulls = present_nulls(array);
+            if nulls.is_some() || !matches!(children, Children::Same) {
+                levels.push(Level { nulls, children });
+            }
+            array = next.as_ref();
         }
-        Some((array, entries))
+        Some(Path {
+            levels,
+            leaf: array,
+        })
     }
 }
 
-/// The entries whose value in `array` is not null.
-fn present<'a>(array: &'a dyn Array, entries: Entries<'a>) -> Entries<'a> {
-    match array.nulls() {
-        Some(nulls) => Box::new(entries.filter(move |&(_, index)| nulls.is_valid(index))),
-        None => entries,
-    }
+/// The arrays the way from a batch's column down to one leaf column passes through.
+struct Path<'a> {
+    /// One for each step, from the batch's column down.
+    levels: Vec<Level<'a>>,
+    /// The leaf column's array.
+    leaf: &'a dyn Array,
 }
 
-/// The entries of the children of every list or map entry in `entries`.
-fn children<'a, O: OffsetSizeTrait>(entries: Entries<'a>, offsets: &'a [O]) -> Entries<'a> {
-    Box::new(entries.flat_map(move |(row, index)| {
-        (offsets[index].as_usize()..offsets[index + 1].as_usize()).map(move |child| (row, child))
-    }))
+/// An array on the way to a leaf, and how its entries lead into the next one.
+struct Level<'a> {
+    /// A null entry has nothing under it in the column chunk, even where a null list spans child
+    /// values.
+    nulls: Option<&'a NullBuffer>,
+    children: Children<'a>,
 }
 
-type ValueBytes<'a> = Box<dyn Fn(usize) -> &'a [u8] + 'a>;
+/// The entries of the next array that lie under entry `i` of a level.
+#[derive(Clone, Copy)]
+enum Children<'a> {
+    /// A struct's: entry `i` of its field.
+    Same,
+    /// A list's or a map's: entries `offsets[i]` up to `offsets[i + 1]` of its elements, keys or
+    /// values.
+    Offsets(&'a [i32]),
+    /// A large list's.
+    LargeOffsets(&'a [i64]),
+    /// A fixed-size list's: the `size` elements from `i * size`.
+    Fixed(usize),
+}
 
-/// The bytes that tell `array`'s values apart: a fixed-width value's native bytes, or a string's or
-/// binary's content. `None` for a type an Iceberg schema cannot produce.
-fn value_bytes<'a>(array: &'a dyn Array) -> Option<ValueBytes<'a>> {
-    let bytes: ValueBytes<'a> = downcast_primitive_array!(
-        array => Box::new(move |i| array.values()[i].to_byte_slice()),
-        DataType::Utf8 => {
-            let array = array.as_string::<i32>();
-            Box::new(move |i| array.value(i).as_bytes())
+impl Children<'_> {
+    /// Where the entries under entry `index` start in the next array. Those under the entries
+    /// before `index` end there too, so this also holds for one past the last entry.
+    fn start(self, index: usize) -> usize {

Review Comment:
   Thanks, and good catch on `concat_batches`. I hadn't noticed it returns the input slice for a single batch, so `take_record_batch` is the right comparison. The mutation checks make this convincing.



##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -254,139 +343,230 @@ fn collect_leaves(data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>)
                 descend(Step::Key, fields[0].data_type(), leaf, leaves);
                 descend(Step::Value, fields[1].data_type(), leaf, leaves);
             }
-            _ => leaves.push(leaf.clone()),
+            _ => leaves.push((leaf.clone(), data_type.clone())),
         },
-        _ => leaves.push(leaf.clone()),
+        _ => leaves.push((leaf.clone(), data_type.clone())),
     }
 }
 
-fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>) {
+fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<(Leaf, DataType)>) {
     leaf.steps.push(step);
     collect_leaves(data_type, leaf, leaves);
     leaf.steps.pop();
 }
 
-/// `(row, index)` pairs, one per entry of an array that the column chunk stores: its row of the
-/// batch, and its index into the array.
-type Entries<'a> = Box<dyn Iterator<Item = (u32, usize)> + 'a>;
-
 impl Leaf {
-    /// The leaf's array in `batch`, with the entries of it that lie under the rows `top` yields and
-    /// whose ancestors are all present, in the order the column chunk stores them. Nothing is
-    /// expanded ahead: each entry is produced when the page asks for it. `None` when `batch` does
-    /// not have the shape the schema promised.
-    fn entries<'a>(
-        &self,
-        batch: &'a RecordBatch,
-        top: Entries<'a>,
-    ) -> Option<(&'a dyn Array, Entries<'a>)> {
+    /// The arrays of `batch` the way to the leaf passes through, or `None` when `batch` does not
+    /// have the shape the schema promised.
+    fn path<'a>(&self, batch: &'a RecordBatch) -> Option<Path<'a>> {
         let mut array = batch.columns().get(self.column)?.as_ref();
-        let mut entries = top;
+        let mut levels = Vec::with_capacity(self.steps.len());
         for step in &self.steps {
-            let present = present(array, entries);
-            (array, entries) = match (step, array.data_type()) {
+            let (children, next) = match (step, array.data_type()) {
                 (Step::Field(field), DataType::Struct(_)) => {
-                    (array.as_struct().columns().get(*field)?.as_ref(), present)
+                    (Children::Same, array.as_struct().columns().get(*field)?)
                 }
                 (Step::Element, DataType::List(_)) => {
                     let list = array.as_list::<i32>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
+                    (Children::Offsets(list.value_offsets()), list.values())
                 }
                 (Step::Element, DataType::LargeList(_)) => {
                     let list = array.as_list::<i64>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
-                }
-                (Step::Element, DataType::FixedSizeList(_, size)) => {
-                    let size = *size as usize;
-                    let elements: Entries<'a> = Box::new(present.flat_map(move |(row, index)| {
-                        (index * size..(index + 1) * size).map(move |element| (row, element))
-                    }));
-                    (array.as_fixed_size_list().values().as_ref(), elements)
+                    (Children::LargeOffsets(list.value_offsets()), list.values())
                 }
+                (Step::Element, DataType::FixedSizeList(_, size)) => (
+                    Children::Fixed(*size as usize),
+                    array.as_fixed_size_list().values(),
+                ),
                 (Step::Key, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (map.keys().as_ref(), children(present, map.value_offsets()))
+                    (Children::Offsets(map.value_offsets()), map.keys())
                 }
                 (Step::Value, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (
-                        map.values().as_ref(),
-                        children(present, map.value_offsets()),
-                    )
+                    (Children::Offsets(map.value_offsets()), map.values())
                 }
                 _ => return None,
             };
+            // A null buffer with no nulls in it is as good as none, and a struct without nulls
+            // leads every entry straight to its field's, so neither needs a level.
+            let nulls = present_nulls(array);
+            if nulls.is_some() || !matches!(children, Children::Same) {
+                levels.push(Level { nulls, children });
+            }
+            array = next.as_ref();
         }
-        Some((array, entries))
+        Some(Path {
+            levels,
+            leaf: array,
+        })
     }
 }
 
-/// The entries whose value in `array` is not null.
-fn present<'a>(array: &'a dyn Array, entries: Entries<'a>) -> Entries<'a> {
-    match array.nulls() {
-        Some(nulls) => Box::new(entries.filter(move |&(_, index)| nulls.is_valid(index))),
-        None => entries,
-    }
+/// The arrays the way from a batch's column down to one leaf column passes through.
+struct Path<'a> {
+    /// One for each step, from the batch's column down.
+    levels: Vec<Level<'a>>,
+    /// The leaf column's array.
+    leaf: &'a dyn Array,
 }
 
-/// The entries of the children of every list or map entry in `entries`.
-fn children<'a, O: OffsetSizeTrait>(entries: Entries<'a>, offsets: &'a [O]) -> Entries<'a> {
-    Box::new(entries.flat_map(move |(row, index)| {
-        (offsets[index].as_usize()..offsets[index + 1].as_usize()).map(move |child| (row, child))
-    }))
+/// An array on the way to a leaf, and how its entries lead into the next one.
+struct Level<'a> {
+    /// A null entry has nothing under it in the column chunk, even where a null list spans child
+    /// values.
+    nulls: Option<&'a NullBuffer>,
+    children: Children<'a>,
 }
 
-type ValueBytes<'a> = Box<dyn Fn(usize) -> &'a [u8] + 'a>;
+/// The entries of the next array that lie under entry `i` of a level.
+#[derive(Clone, Copy)]
+enum Children<'a> {
+    /// A struct's: entry `i` of its field.
+    Same,
+    /// A list's or a map's: entries `offsets[i]` up to `offsets[i + 1]` of its elements, keys or
+    /// values.
+    Offsets(&'a [i32]),
+    /// A large list's.
+    LargeOffsets(&'a [i64]),
+    /// A fixed-size list's: the `size` elements from `i * size`.
+    Fixed(usize),
+}
 
-/// The bytes that tell `array`'s values apart: a fixed-width value's native bytes, or a string's or
-/// binary's content. `None` for a type an Iceberg schema cannot produce.
-fn value_bytes<'a>(array: &'a dyn Array) -> Option<ValueBytes<'a>> {
-    let bytes: ValueBytes<'a> = downcast_primitive_array!(
-        array => Box::new(move |i| array.values()[i].to_byte_slice()),
-        DataType::Utf8 => {
-            let array = array.as_string::<i32>();
-            Box::new(move |i| array.value(i).as_bytes())
+impl Children<'_> {
+    /// Where the entries under entry `index` start in the next array. Those under the entries
+    /// before `index` end there too, so this also holds for one past the last entry.
+    fn start(self, index: usize) -> usize {
+        match self {
+            Children::Same => index,
+            Children::Offsets(offsets) => offsets[index] as usize,
+            Children::LargeOffsets(offsets) => offsets[index] as usize,
+            Children::Fixed(size) => index * size,
         }
-        DataType::LargeUtf8 => {
-            let array = array.as_string::<i64>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Utf8View => {
-            let array = array.as_string_view();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Binary => {
-            let array = array.as_binary::<i32>();
-            Box::new(move |i| array.value(i))
-        }
-        DataType::LargeBinary => {
-            let array = array.as_binary::<i64>();
-            Box::new(move |i| array.value(i))
-        }
-        DataType::BinaryView => {
-            let array = array.as_binary_view();
-            Box::new(move |i| array.value(i))
+    }
+}
+
+impl Path<'_> {
+    /// How many entries of the leaf array lie under the batch's first `rows` rows, null or not.
+    fn entries(&self, rows: usize) -> usize {
+        let (start, end) = self.levels.iter().fold((0, rows), |(start, end), level| {
+            (level.children.start(start), level.children.start(end))
+        });
+        end - start
+    }
+
+    /// Calls `f` with the leaf index of every entry under the batch's row `row` whose ancestors
+    /// are all present, in the order the column chunk stores them, until `f` returns `false`.
+    /// Returns whether every entry was visited. Nothing is expanded ahead, so a page that ends
+    /// partway through a batch reads no further.
+    fn visit(&self, row: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+        // A leaf with no levels above it has one entry per row: the row itself.
+        if self.levels.is_empty() {
+            return f(row);
         }
-        _ => return None,
-    );
-    Some(bytes)
+        visit(&self.levels, row, f)
+    }
+}
+
+/// `array`'s nulls, or `None` when it has none.
+fn present_nulls(array: &dyn Array) -> Option<&NullBuffer> {
+    array.nulls().filter(|nulls| nulls.null_count() > 0)
+}
+
+fn visit(levels: &[Level], index: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+    let Some((level, below)) = levels.split_first() else {
+        return f(index);
+    };
+    if level.nulls.is_some_and(|nulls| nulls.is_null(index)) {
+        return true;
+    }
+    let mut children = level.children.start(index)..level.children.start(index + 1);
+    // The leaf's entries are visited here rather than one call deeper each.
+    if below.is_empty() {
+        children.all(f)
+    } else {
+        children.all(|child| visit(below, child, &mut *f))
+    }
+}
+
+/// Reads fixed-width values by their bits, zero-extended to `K`, which is at least as wide.
+fn bits<T: ArrowNativeType, K: Bits>(values: &[T]) -> impl Fn(usize) -> (K, usize) + '_ {
+    move |index| (K::of(values[index]), size_of::<T>())
+}
+
+/// Reads fixed-width values too wide for [`bits`] by their native bytes.
+fn native_bytes<'a, T: ArrowNativeType>(values: &'a [T]) -> impl Fn(usize) -> (Bytes<'a>, usize) {
+    move |index| Bytes::of(values[index].to_byte_slice())
+}
+
+/// Reads a string or binary array's values by their content.
+fn bytes<'a, A, V>(array: A) -> impl Fn(usize) -> (Bytes<'a>, usize)
+where
+    A: ArrayAccessor<Item = &'a V>,
+    V: AsRef<[u8]> + ?Sized + 'a,
+{
+    move |index| Bytes::of(array.value(index).as_ref())
+}
+
+/// The bits of a fixed-width value, zero-extended to fill this type.
+trait Bits: Copy + Eq + Hash {
+    fn of<T: ArrowNativeType>(value: T) -> Self;
+}
+
+impl Bits for u64 {
+    fn of<T: ArrowNativeType>(value: T) -> Self {
+        let mut bits = [0; 8];
+        let bytes = value.to_byte_slice();
+        bits[..bytes.len()].copy_from_slice(bytes);
+        u64::from_ne_bytes(bits)
+    }
+}
+
+impl Bits for u128 {
+    fn of<T: ArrowNativeType>(value: T) -> Self {
+        let mut bits = [0; 16];
+        let bytes = value.to_byte_slice();
+        bits[..bytes.len()].copy_from_slice(bytes);
+        u128::from_ne_bytes(bits)
+    }
+}
+
+/// A value's bytes. Two of the same length whose last bytes differ are told apart without
+/// comparing the rest, which spares comparing most distinct values with the one before them.
+#[derive(Clone, Copy)]
+struct Bytes<'a>(&'a [u8]);
+
+impl<'a> Bytes<'a> {
+    /// `bytes` as a value, and how many there are.
+    fn of(bytes: &'a [u8]) -> (Self, usize) {
+        (Self(bytes), bytes.len())
+    }
+}
+
+impl PartialEq for Bytes<'_> {
+    fn eq(&self, other: &Self) -> bool {
+        self.0.len() == other.0.len() && self.0.last() == other.0.last() && self.0 == other.0

Review Comment:
   Thanks for measuring it. Those numbers justify keeping `Bytes`, and having them in the doc comment helps.



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] perf: make the native Iceberg writer's dictionary pre-pass 1.8x to 3.9x faster [datafusion-comet]

Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on code in PR #6937:
URL: https://github.com/apache/datafusion-comet/pull/6937#discussion_r4285216229


##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -1253,6 +1677,26 @@ mod tests {
         );
     }
 
+    /// The fields of a null struct are not part of the column chunk either.
+    #[test]
+    fn values_under_a_null_struct_are_not_counted() {

Review Comment:
   It looks like `a_sliced_batch_is_read_only_within_its_slice`, added in the last commit, covers this test now. Its `s` is null on odd rows over values of their own, and `s.n` is valid on those rows. So a walk that leaves out a struct level with nulls overflows `s.n`'s 1 KiB dictionary and drops it from `expected`. `ls` checks the same one level under a list. The `_large_list` and `_fixed_list` columns of `reads_every_leaf_type` are covered the same way by `ll` and `fl`, which add nulls and a slice on top.
   
   I traced this by reading the code and have not run the mutation. If it holds, could this test and the list half of `reads_every_leaf_type` go?



##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -254,139 +343,234 @@ fn collect_leaves(data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>)
                 descend(Step::Key, fields[0].data_type(), leaf, leaves);
                 descend(Step::Value, fields[1].data_type(), leaf, leaves);
             }
-            _ => leaves.push(leaf.clone()),
+            _ => leaves.push((leaf.clone(), data_type.clone())),
         },
-        _ => leaves.push(leaf.clone()),
+        _ => leaves.push((leaf.clone(), data_type.clone())),
     }
 }
 
-fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>) {
+fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<(Leaf, DataType)>) {
     leaf.steps.push(step);
     collect_leaves(data_type, leaf, leaves);
     leaf.steps.pop();
 }
 
-/// `(row, index)` pairs, one per entry of an array that the column chunk stores: its row of the
-/// batch, and its index into the array.
-type Entries<'a> = Box<dyn Iterator<Item = (u32, usize)> + 'a>;
-
 impl Leaf {
-    /// The leaf's array in `batch`, with the entries of it that lie under the rows `top` yields and
-    /// whose ancestors are all present, in the order the column chunk stores them. Nothing is
-    /// expanded ahead: each entry is produced when the page asks for it. `None` when `batch` does
-    /// not have the shape the schema promised.
-    fn entries<'a>(
-        &self,
-        batch: &'a RecordBatch,
-        top: Entries<'a>,
-    ) -> Option<(&'a dyn Array, Entries<'a>)> {
+    /// The arrays of `batch` the way to the leaf passes through, or `None` when `batch` does not
+    /// have the shape the schema promised.
+    fn path<'a>(&self, batch: &'a RecordBatch) -> Option<Path<'a>> {
         let mut array = batch.columns().get(self.column)?.as_ref();
-        let mut entries = top;
+        let mut levels = Vec::with_capacity(self.steps.len());
         for step in &self.steps {
-            let present = present(array, entries);
-            (array, entries) = match (step, array.data_type()) {
+            let (children, next) = match (step, array.data_type()) {
                 (Step::Field(field), DataType::Struct(_)) => {
-                    (array.as_struct().columns().get(*field)?.as_ref(), present)
+                    (Children::Same, array.as_struct().columns().get(*field)?)
                 }
                 (Step::Element, DataType::List(_)) => {
                     let list = array.as_list::<i32>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
+                    (Children::Offsets(list.value_offsets()), list.values())
                 }
                 (Step::Element, DataType::LargeList(_)) => {
                     let list = array.as_list::<i64>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
-                }
-                (Step::Element, DataType::FixedSizeList(_, size)) => {
-                    let size = *size as usize;
-                    let elements: Entries<'a> = Box::new(present.flat_map(move |(row, index)| {
-                        (index * size..(index + 1) * size).map(move |element| (row, element))
-                    }));
-                    (array.as_fixed_size_list().values().as_ref(), elements)
+                    (Children::LargeOffsets(list.value_offsets()), list.values())
                 }
+                (Step::Element, DataType::FixedSizeList(_, size)) => (
+                    Children::Fixed(*size as usize),
+                    array.as_fixed_size_list().values(),
+                ),
                 (Step::Key, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (map.keys().as_ref(), children(present, map.value_offsets()))
+                    (Children::Offsets(map.value_offsets()), map.keys())
                 }
                 (Step::Value, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (
-                        map.values().as_ref(),
-                        children(present, map.value_offsets()),
-                    )
+                    (Children::Offsets(map.value_offsets()), map.values())
                 }
                 _ => return None,
             };
+            // A null buffer with no nulls in it is as good as none, and a struct without nulls
+            // leads every entry straight to its field's, so neither needs a level.
+            let nulls = present_nulls(array);
+            if nulls.is_some() || !matches!(children, Children::Same) {
+                levels.push(Level { nulls, children });
+            }
+            array = next.as_ref();
         }
-        Some((array, entries))
+        Some(Path {
+            levels,
+            leaf: array,
+        })
     }
 }
 
-/// The entries whose value in `array` is not null.
-fn present<'a>(array: &'a dyn Array, entries: Entries<'a>) -> Entries<'a> {
-    match array.nulls() {
-        Some(nulls) => Box::new(entries.filter(move |&(_, index)| nulls.is_valid(index))),
-        None => entries,
-    }
+/// The arrays the way from a batch's column down to one leaf column passes through.
+struct Path<'a> {
+    /// One for each step, from the batch's column down.
+    levels: Vec<Level<'a>>,
+    /// The leaf column's array.
+    leaf: &'a dyn Array,
 }
 
-/// The entries of the children of every list or map entry in `entries`.
-fn children<'a, O: OffsetSizeTrait>(entries: Entries<'a>, offsets: &'a [O]) -> Entries<'a> {
-    Box::new(entries.flat_map(move |(row, index)| {
-        (offsets[index].as_usize()..offsets[index + 1].as_usize()).map(move |child| (row, child))
-    }))
+/// An array on the way to a leaf, and how its entries lead into the next one.
+struct Level<'a> {
+    /// A null entry has nothing under it in the column chunk, even where a null list spans child
+    /// values.
+    nulls: Option<&'a NullBuffer>,
+    children: Children<'a>,
 }
 
-type ValueBytes<'a> = Box<dyn Fn(usize) -> &'a [u8] + 'a>;
+/// The entries of the next array that lie under entry `i` of a level.
+#[derive(Clone, Copy)]
+enum Children<'a> {
+    /// A struct's: entry `i` of its field.
+    Same,
+    /// A list's or a map's: entries `offsets[i]` up to `offsets[i + 1]` of its elements, keys or
+    /// values.
+    Offsets(&'a [i32]),
+    /// A large list's.
+    LargeOffsets(&'a [i64]),
+    /// A fixed-size list's: the `size` elements from `i * size`.
+    Fixed(usize),
+}
 
-/// The bytes that tell `array`'s values apart: a fixed-width value's native bytes, or a string's or
-/// binary's content. `None` for a type an Iceberg schema cannot produce.
-fn value_bytes<'a>(array: &'a dyn Array) -> Option<ValueBytes<'a>> {
-    let bytes: ValueBytes<'a> = downcast_primitive_array!(
-        array => Box::new(move |i| array.values()[i].to_byte_slice()),
-        DataType::Utf8 => {
-            let array = array.as_string::<i32>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::LargeUtf8 => {
-            let array = array.as_string::<i64>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Utf8View => {
-            let array = array.as_string_view();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Binary => {
-            let array = array.as_binary::<i32>();
-            Box::new(move |i| array.value(i))
-        }
-        DataType::LargeBinary => {
-            let array = array.as_binary::<i64>();
-            Box::new(move |i| array.value(i))
+impl Children<'_> {
+    /// Where the entries under entry `index` start in the next array. Those under the entries
+    /// before `index` end there too, so this also holds for one past the last entry.
+    fn start(self, index: usize) -> usize {
+        match self {
+            Children::Same => index,
+            Children::Offsets(offsets) => offsets[index] as usize,
+            Children::LargeOffsets(offsets) => offsets[index] as usize,
+            Children::Fixed(size) => index * size,
         }
-        DataType::BinaryView => {
-            let array = array.as_binary_view();
-            Box::new(move |i| array.value(i))
+    }
+}
+
+impl Path<'_> {
+    /// How many entries of the leaf array lie under the batch's first `rows` rows, null or not.
+    fn entries(&self, rows: usize) -> usize {
+        let (start, end) = self.levels.iter().fold((0, rows), |(start, end), level| {
+            (level.children.start(start), level.children.start(end))
+        });
+        end - start
+    }
+
+    /// Calls `f` with the leaf index of every entry under the batch's row `row` whose ancestors
+    /// are all present, in the order the column chunk stores them, until `f` returns `false`.
+    /// Returns whether every entry was visited. Nothing is expanded ahead, so a page that ends
+    /// partway through a batch reads no further.
+    fn visit(&self, row: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+        // A leaf with no levels above it has one entry per row: the row itself.
+        if self.levels.is_empty() {
+            return f(row);
         }
-        _ => return None,
-    );
-    Some(bytes)
+        visit(&self.levels, row, f)
+    }
+}
+
+/// `array`'s nulls, or `None` when it has none.
+fn present_nulls(array: &dyn Array) -> Option<&NullBuffer> {
+    array.nulls().filter(|nulls| nulls.null_count() > 0)
+}
+
+fn visit(levels: &[Level], index: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+    let Some((level, below)) = levels.split_first() else {
+        return f(index);
+    };

Review Comment:
   This `else` branch never runs. `Path::visit` returns early when there are no levels, and `visit` only recurses when `below` is not empty, so `levels` is never empty here. Could the empty check live in one place? For example, `Path::visit` could call `split_first` itself and pass `level` and `below` in.



##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -254,139 +343,234 @@ fn collect_leaves(data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>)
                 descend(Step::Key, fields[0].data_type(), leaf, leaves);
                 descend(Step::Value, fields[1].data_type(), leaf, leaves);
             }
-            _ => leaves.push(leaf.clone()),
+            _ => leaves.push((leaf.clone(), data_type.clone())),
         },
-        _ => leaves.push(leaf.clone()),
+        _ => leaves.push((leaf.clone(), data_type.clone())),
     }
 }
 
-fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>) {
+fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<(Leaf, DataType)>) {
     leaf.steps.push(step);
     collect_leaves(data_type, leaf, leaves);
     leaf.steps.pop();
 }
 
-/// `(row, index)` pairs, one per entry of an array that the column chunk stores: its row of the
-/// batch, and its index into the array.
-type Entries<'a> = Box<dyn Iterator<Item = (u32, usize)> + 'a>;
-
 impl Leaf {
-    /// The leaf's array in `batch`, with the entries of it that lie under the rows `top` yields and
-    /// whose ancestors are all present, in the order the column chunk stores them. Nothing is
-    /// expanded ahead: each entry is produced when the page asks for it. `None` when `batch` does
-    /// not have the shape the schema promised.
-    fn entries<'a>(
-        &self,
-        batch: &'a RecordBatch,
-        top: Entries<'a>,
-    ) -> Option<(&'a dyn Array, Entries<'a>)> {
+    /// The arrays of `batch` the way to the leaf passes through, or `None` when `batch` does not
+    /// have the shape the schema promised.
+    fn path<'a>(&self, batch: &'a RecordBatch) -> Option<Path<'a>> {
         let mut array = batch.columns().get(self.column)?.as_ref();
-        let mut entries = top;
+        let mut levels = Vec::with_capacity(self.steps.len());
         for step in &self.steps {
-            let present = present(array, entries);
-            (array, entries) = match (step, array.data_type()) {
+            let (children, next) = match (step, array.data_type()) {
                 (Step::Field(field), DataType::Struct(_)) => {
-                    (array.as_struct().columns().get(*field)?.as_ref(), present)
+                    (Children::Same, array.as_struct().columns().get(*field)?)
                 }
                 (Step::Element, DataType::List(_)) => {
                     let list = array.as_list::<i32>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
+                    (Children::Offsets(list.value_offsets()), list.values())
                 }
                 (Step::Element, DataType::LargeList(_)) => {
                     let list = array.as_list::<i64>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
-                }
-                (Step::Element, DataType::FixedSizeList(_, size)) => {
-                    let size = *size as usize;
-                    let elements: Entries<'a> = Box::new(present.flat_map(move |(row, index)| {
-                        (index * size..(index + 1) * size).map(move |element| (row, element))
-                    }));
-                    (array.as_fixed_size_list().values().as_ref(), elements)
+                    (Children::LargeOffsets(list.value_offsets()), list.values())
                 }
+                (Step::Element, DataType::FixedSizeList(_, size)) => (
+                    Children::Fixed(*size as usize),
+                    array.as_fixed_size_list().values(),
+                ),
                 (Step::Key, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (map.keys().as_ref(), children(present, map.value_offsets()))
+                    (Children::Offsets(map.value_offsets()), map.keys())
                 }
                 (Step::Value, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (
-                        map.values().as_ref(),
-                        children(present, map.value_offsets()),
-                    )
+                    (Children::Offsets(map.value_offsets()), map.values())
                 }
                 _ => return None,
             };
+            // A null buffer with no nulls in it is as good as none, and a struct without nulls
+            // leads every entry straight to its field's, so neither needs a level.
+            let nulls = present_nulls(array);
+            if nulls.is_some() || !matches!(children, Children::Same) {
+                levels.push(Level { nulls, children });
+            }
+            array = next.as_ref();
         }
-        Some((array, entries))
+        Some(Path {
+            levels,
+            leaf: array,
+        })
     }
 }
 
-/// The entries whose value in `array` is not null.
-fn present<'a>(array: &'a dyn Array, entries: Entries<'a>) -> Entries<'a> {
-    match array.nulls() {
-        Some(nulls) => Box::new(entries.filter(move |&(_, index)| nulls.is_valid(index))),
-        None => entries,
-    }
+/// The arrays the way from a batch's column down to one leaf column passes through.
+struct Path<'a> {
+    /// One for each step, from the batch's column down.
+    levels: Vec<Level<'a>>,
+    /// The leaf column's array.
+    leaf: &'a dyn Array,
 }
 
-/// The entries of the children of every list or map entry in `entries`.
-fn children<'a, O: OffsetSizeTrait>(entries: Entries<'a>, offsets: &'a [O]) -> Entries<'a> {
-    Box::new(entries.flat_map(move |(row, index)| {
-        (offsets[index].as_usize()..offsets[index + 1].as_usize()).map(move |child| (row, child))
-    }))
+/// An array on the way to a leaf, and how its entries lead into the next one.
+struct Level<'a> {
+    /// A null entry has nothing under it in the column chunk, even where a null list spans child
+    /// values.
+    nulls: Option<&'a NullBuffer>,
+    children: Children<'a>,
 }
 
-type ValueBytes<'a> = Box<dyn Fn(usize) -> &'a [u8] + 'a>;
+/// The entries of the next array that lie under entry `i` of a level.
+#[derive(Clone, Copy)]
+enum Children<'a> {
+    /// A struct's: entry `i` of its field.
+    Same,
+    /// A list's or a map's: entries `offsets[i]` up to `offsets[i + 1]` of its elements, keys or
+    /// values.
+    Offsets(&'a [i32]),
+    /// A large list's.
+    LargeOffsets(&'a [i64]),
+    /// A fixed-size list's: the `size` elements from `i * size`.
+    Fixed(usize),
+}
 
-/// The bytes that tell `array`'s values apart: a fixed-width value's native bytes, or a string's or
-/// binary's content. `None` for a type an Iceberg schema cannot produce.
-fn value_bytes<'a>(array: &'a dyn Array) -> Option<ValueBytes<'a>> {
-    let bytes: ValueBytes<'a> = downcast_primitive_array!(
-        array => Box::new(move |i| array.values()[i].to_byte_slice()),
-        DataType::Utf8 => {
-            let array = array.as_string::<i32>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::LargeUtf8 => {
-            let array = array.as_string::<i64>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Utf8View => {
-            let array = array.as_string_view();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Binary => {
-            let array = array.as_binary::<i32>();
-            Box::new(move |i| array.value(i))
-        }
-        DataType::LargeBinary => {
-            let array = array.as_binary::<i64>();
-            Box::new(move |i| array.value(i))
+impl Children<'_> {
+    /// Where the entries under entry `index` start in the next array. Those under the entries
+    /// before `index` end there too, so this also holds for one past the last entry.
+    fn start(self, index: usize) -> usize {
+        match self {
+            Children::Same => index,
+            Children::Offsets(offsets) => offsets[index] as usize,
+            Children::LargeOffsets(offsets) => offsets[index] as usize,
+            Children::Fixed(size) => index * size,
         }
-        DataType::BinaryView => {
-            let array = array.as_binary_view();
-            Box::new(move |i| array.value(i))
+    }
+}
+
+impl Path<'_> {
+    /// How many entries of the leaf array lie under the batch's first `rows` rows, null or not.
+    fn entries(&self, rows: usize) -> usize {
+        let (start, end) = self.levels.iter().fold((0, rows), |(start, end), level| {
+            (level.children.start(start), level.children.start(end))
+        });
+        end - start
+    }
+
+    /// Calls `f` with the leaf index of every entry under the batch's row `row` whose ancestors
+    /// are all present, in the order the column chunk stores them, until `f` returns `false`.
+    /// Returns whether every entry was visited. Nothing is expanded ahead, so a page that ends
+    /// partway through a batch reads no further.
+    fn visit(&self, row: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+        // A leaf with no levels above it has one entry per row: the row itself.
+        if self.levels.is_empty() {
+            return f(row);
         }
-        _ => return None,
-    );
-    Some(bytes)
+        visit(&self.levels, row, f)
+    }
+}
+
+/// `array`'s nulls, or `None` when it has none.
+fn present_nulls(array: &dyn Array) -> Option<&NullBuffer> {
+    array.nulls().filter(|nulls| nulls.null_count() > 0)
+}
+
+fn visit(levels: &[Level], index: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+    let Some((level, below)) = levels.split_first() else {
+        return f(index);
+    };
+    if level.nulls.is_some_and(|nulls| nulls.is_null(index)) {
+        return true;
+    }
+    let mut children = level.children.start(index)..level.children.start(index + 1);
+    // The leaf's entries are visited here rather than one call deeper each.
+    if below.is_empty() {
+        children.all(f)
+    } else {
+        children.all(|child| visit(below, child, &mut *f))
+    }
+}
+
+/// Reads fixed-width values by their bits, zero-extended to `K`, which is at least as wide.
+fn bits<T: ArrowNativeType, K: Bits>(values: &[T]) -> impl Fn(usize) -> (K, usize) + '_ {
+    move |index| (K::of(values[index]), size_of::<T>())
+}
+
+/// Reads fixed-width values too wide for [`bits`] by their native bytes.
+fn native_bytes<'a, T: ArrowNativeType>(values: &'a [T]) -> impl Fn(usize) -> (Bytes<'a>, usize) {
+    move |index| Bytes::of(values[index].to_byte_slice())

Review Comment:
   The length `bits` and `native_bytes` return is never read. Every fixed-width candidate has `width: Some(..)`, so `add` ignores `len` for them. It is not the plain width either: a `Decimal128(9, 2)` value reports 16 here and is written as a 4-byte INT32. Could the readers return the plain size instead, the candidate's `width` for fixed-width values and `4 + len` for byte arrays? Then `add` would not need `FirstPage::width`, and no reader would return a number nobody reads.



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] perf: make the native Iceberg writer's dictionary pre-pass 1.8x to 3.9x faster [datafusion-comet]

Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #6937:
URL: https://github.com/apache/datafusion-comet/pull/6937#discussion_r4264100481


##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -254,139 +343,230 @@ fn collect_leaves(data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>)
                 descend(Step::Key, fields[0].data_type(), leaf, leaves);
                 descend(Step::Value, fields[1].data_type(), leaf, leaves);
             }
-            _ => leaves.push(leaf.clone()),
+            _ => leaves.push((leaf.clone(), data_type.clone())),
         },
-        _ => leaves.push(leaf.clone()),
+        _ => leaves.push((leaf.clone(), data_type.clone())),
     }
 }
 
-fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>) {
+fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<(Leaf, DataType)>) {
     leaf.steps.push(step);
     collect_leaves(data_type, leaf, leaves);
     leaf.steps.pop();
 }
 
-/// `(row, index)` pairs, one per entry of an array that the column chunk stores: its row of the
-/// batch, and its index into the array.
-type Entries<'a> = Box<dyn Iterator<Item = (u32, usize)> + 'a>;
-
 impl Leaf {
-    /// The leaf's array in `batch`, with the entries of it that lie under the rows `top` yields and
-    /// whose ancestors are all present, in the order the column chunk stores them. Nothing is
-    /// expanded ahead: each entry is produced when the page asks for it. `None` when `batch` does
-    /// not have the shape the schema promised.
-    fn entries<'a>(
-        &self,
-        batch: &'a RecordBatch,
-        top: Entries<'a>,
-    ) -> Option<(&'a dyn Array, Entries<'a>)> {
+    /// The arrays of `batch` the way to the leaf passes through, or `None` when `batch` does not
+    /// have the shape the schema promised.
+    fn path<'a>(&self, batch: &'a RecordBatch) -> Option<Path<'a>> {
         let mut array = batch.columns().get(self.column)?.as_ref();
-        let mut entries = top;
+        let mut levels = Vec::with_capacity(self.steps.len());
         for step in &self.steps {
-            let present = present(array, entries);
-            (array, entries) = match (step, array.data_type()) {
+            let (children, next) = match (step, array.data_type()) {
                 (Step::Field(field), DataType::Struct(_)) => {
-                    (array.as_struct().columns().get(*field)?.as_ref(), present)
+                    (Children::Same, array.as_struct().columns().get(*field)?)
                 }
                 (Step::Element, DataType::List(_)) => {
                     let list = array.as_list::<i32>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
+                    (Children::Offsets(list.value_offsets()), list.values())
                 }
                 (Step::Element, DataType::LargeList(_)) => {
                     let list = array.as_list::<i64>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
-                }
-                (Step::Element, DataType::FixedSizeList(_, size)) => {
-                    let size = *size as usize;
-                    let elements: Entries<'a> = Box::new(present.flat_map(move |(row, index)| {
-                        (index * size..(index + 1) * size).map(move |element| (row, element))
-                    }));
-                    (array.as_fixed_size_list().values().as_ref(), elements)
+                    (Children::LargeOffsets(list.value_offsets()), list.values())
                 }
+                (Step::Element, DataType::FixedSizeList(_, size)) => (
+                    Children::Fixed(*size as usize),
+                    array.as_fixed_size_list().values(),
+                ),
                 (Step::Key, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (map.keys().as_ref(), children(present, map.value_offsets()))
+                    (Children::Offsets(map.value_offsets()), map.keys())
                 }
                 (Step::Value, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (
-                        map.values().as_ref(),
-                        children(present, map.value_offsets()),
-                    )
+                    (Children::Offsets(map.value_offsets()), map.values())
                 }
                 _ => return None,
             };
+            // A null buffer with no nulls in it is as good as none, and a struct without nulls
+            // leads every entry straight to its field's, so neither needs a level.
+            let nulls = present_nulls(array);
+            if nulls.is_some() || !matches!(children, Children::Same) {
+                levels.push(Level { nulls, children });
+            }
+            array = next.as_ref();
         }
-        Some((array, entries))
+        Some(Path {
+            levels,
+            leaf: array,
+        })
     }
 }
 
-/// The entries whose value in `array` is not null.
-fn present<'a>(array: &'a dyn Array, entries: Entries<'a>) -> Entries<'a> {
-    match array.nulls() {
-        Some(nulls) => Box::new(entries.filter(move |&(_, index)| nulls.is_valid(index))),
-        None => entries,
-    }
+/// The arrays the way from a batch's column down to one leaf column passes through.
+struct Path<'a> {
+    /// One for each step, from the batch's column down.
+    levels: Vec<Level<'a>>,
+    /// The leaf column's array.
+    leaf: &'a dyn Array,
 }
 
-/// The entries of the children of every list or map entry in `entries`.
-fn children<'a, O: OffsetSizeTrait>(entries: Entries<'a>, offsets: &'a [O]) -> Entries<'a> {
-    Box::new(entries.flat_map(move |(row, index)| {
-        (offsets[index].as_usize()..offsets[index + 1].as_usize()).map(move |child| (row, child))
-    }))
+/// An array on the way to a leaf, and how its entries lead into the next one.
+struct Level<'a> {
+    /// A null entry has nothing under it in the column chunk, even where a null list spans child
+    /// values.
+    nulls: Option<&'a NullBuffer>,
+    children: Children<'a>,
 }
 
-type ValueBytes<'a> = Box<dyn Fn(usize) -> &'a [u8] + 'a>;
+/// The entries of the next array that lie under entry `i` of a level.
+#[derive(Clone, Copy)]
+enum Children<'a> {
+    /// A struct's: entry `i` of its field.
+    Same,
+    /// A list's or a map's: entries `offsets[i]` up to `offsets[i + 1]` of its elements, keys or
+    /// values.
+    Offsets(&'a [i32]),
+    /// A large list's.
+    LargeOffsets(&'a [i64]),
+    /// A fixed-size list's: the `size` elements from `i * size`.
+    Fixed(usize),
+}
 
-/// The bytes that tell `array`'s values apart: a fixed-width value's native bytes, or a string's or
-/// binary's content. `None` for a type an Iceberg schema cannot produce.
-fn value_bytes<'a>(array: &'a dyn Array) -> Option<ValueBytes<'a>> {
-    let bytes: ValueBytes<'a> = downcast_primitive_array!(
-        array => Box::new(move |i| array.values()[i].to_byte_slice()),
-        DataType::Utf8 => {
-            let array = array.as_string::<i32>();
-            Box::new(move |i| array.value(i).as_bytes())
+impl Children<'_> {
+    /// Where the entries under entry `index` start in the next array. Those under the entries
+    /// before `index` end there too, so this also holds for one past the last entry.
+    fn start(self, index: usize) -> usize {
+        match self {
+            Children::Same => index,
+            Children::Offsets(offsets) => offsets[index] as usize,
+            Children::LargeOffsets(offsets) => offsets[index] as usize,
+            Children::Fixed(size) => index * size,
         }
-        DataType::LargeUtf8 => {
-            let array = array.as_string::<i64>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Utf8View => {
-            let array = array.as_string_view();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Binary => {
-            let array = array.as_binary::<i32>();
-            Box::new(move |i| array.value(i))
-        }
-        DataType::LargeBinary => {
-            let array = array.as_binary::<i64>();
-            Box::new(move |i| array.value(i))
-        }
-        DataType::BinaryView => {
-            let array = array.as_binary_view();
-            Box::new(move |i| array.value(i))
+    }
+}
+
+impl Path<'_> {
+    /// How many entries of the leaf array lie under the batch's first `rows` rows, null or not.
+    fn entries(&self, rows: usize) -> usize {
+        let (start, end) = self.levels.iter().fold((0, rows), |(start, end), level| {
+            (level.children.start(start), level.children.start(end))
+        });
+        end - start
+    }
+
+    /// Calls `f` with the leaf index of every entry under the batch's row `row` whose ancestors
+    /// are all present, in the order the column chunk stores them, until `f` returns `false`.
+    /// Returns whether every entry was visited. Nothing is expanded ahead, so a page that ends
+    /// partway through a batch reads no further.
+    fn visit(&self, row: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+        // A leaf with no levels above it has one entry per row: the row itself.
+        if self.levels.is_empty() {
+            return f(row);
         }
-        _ => return None,
-    );
-    Some(bytes)
+        visit(&self.levels, row, f)
+    }
+}
+
+/// `array`'s nulls, or `None` when it has none.
+fn present_nulls(array: &dyn Array) -> Option<&NullBuffer> {
+    array.nulls().filter(|nulls| nulls.null_count() > 0)
+}
+
+fn visit(levels: &[Level], index: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+    let Some((level, below)) = levels.split_first() else {
+        return f(index);
+    };
+    if level.nulls.is_some_and(|nulls| nulls.is_null(index)) {
+        return true;
+    }
+    let mut children = level.children.start(index)..level.children.start(index + 1);
+    // The leaf's entries are visited here rather than one call deeper each.
+    if below.is_empty() {
+        children.all(f)
+    } else {
+        children.all(|child| visit(below, child, &mut *f))
+    }
+}
+
+/// Reads fixed-width values by their bits, zero-extended to `K`, which is at least as wide.
+fn bits<T: ArrowNativeType, K: Bits>(values: &[T]) -> impl Fn(usize) -> (K, usize) + '_ {
+    move |index| (K::of(values[index]), size_of::<T>())
+}
+
+/// Reads fixed-width values too wide for [`bits`] by their native bytes.
+fn native_bytes<'a, T: ArrowNativeType>(values: &'a [T]) -> impl Fn(usize) -> (Bytes<'a>, usize) {
+    move |index| Bytes::of(values[index].to_byte_slice())
+}
+
+/// Reads a string or binary array's values by their content.
+fn bytes<'a, A, V>(array: A) -> impl Fn(usize) -> (Bytes<'a>, usize)
+where
+    A: ArrayAccessor<Item = &'a V>,
+    V: AsRef<[u8]> + ?Sized + 'a,
+{
+    move |index| Bytes::of(array.value(index).as_ref())
+}
+
+/// The bits of a fixed-width value, zero-extended to fill this type.
+trait Bits: Copy + Eq + Hash {
+    fn of<T: ArrowNativeType>(value: T) -> Self;
+}
+
+impl Bits for u64 {
+    fn of<T: ArrowNativeType>(value: T) -> Self {
+        let mut bits = [0; 8];
+        let bytes = value.to_byte_slice();
+        bits[..bytes.len()].copy_from_slice(bytes);
+        u64::from_ne_bytes(bits)
+    }
+}
+
+impl Bits for u128 {
+    fn of<T: ArrowNativeType>(value: T) -> Self {
+        let mut bits = [0; 16];
+        let bytes = value.to_byte_slice();
+        bits[..bytes.len()].copy_from_slice(bytes);
+        u128::from_ne_bytes(bits)
+    }
+}
+
+/// A value's bytes. Two of the same length whose last bytes differ are told apart without
+/// comparing the rest, which spares comparing most distinct values with the one before them.
+#[derive(Clone, Copy)]
+struct Bytes<'a>(&'a [u8]);
+
+impl<'a> Bytes<'a> {
+    /// `bytes` as a value, and how many there are.
+    fn of(bytes: &'a [u8]) -> (Self, usize) {
+        (Self(bytes), bytes.len())
+    }
+}
+
+impl PartialEq for Bytes<'_> {
+    fn eq(&self, other: &Self) -> bool {
+        self.0.len() == other.0.len() && self.0.last() == other.0.last() && self.0 == other.0

Review Comment:
   Does this check of the length and last byte, together with the length-free `Hash` below, measurably help on its own? Slice equality already compares lengths first. The set only calls `eq` when the tags match, so most of the gain would have to come from the comparison with `previous`.
   
   If keying strings and binaries by plain `&[u8]` costs little or nothing on the `primitives` and `sorted` shapes, I'd drop the newtype. Then there's one less custom `Eq` and `Hash` pair to keep consistent. If it does pay off, a sentence with the numbers in the doc comment would help the next reader.



##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -254,139 +343,230 @@ fn collect_leaves(data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>)
                 descend(Step::Key, fields[0].data_type(), leaf, leaves);
                 descend(Step::Value, fields[1].data_type(), leaf, leaves);
             }
-            _ => leaves.push(leaf.clone()),
+            _ => leaves.push((leaf.clone(), data_type.clone())),
         },
-        _ => leaves.push(leaf.clone()),
+        _ => leaves.push((leaf.clone(), data_type.clone())),
     }
 }
 
-fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>) {
+fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<(Leaf, DataType)>) {
     leaf.steps.push(step);
     collect_leaves(data_type, leaf, leaves);
     leaf.steps.pop();
 }
 
-/// `(row, index)` pairs, one per entry of an array that the column chunk stores: its row of the
-/// batch, and its index into the array.
-type Entries<'a> = Box<dyn Iterator<Item = (u32, usize)> + 'a>;
-
 impl Leaf {
-    /// The leaf's array in `batch`, with the entries of it that lie under the rows `top` yields and
-    /// whose ancestors are all present, in the order the column chunk stores them. Nothing is
-    /// expanded ahead: each entry is produced when the page asks for it. `None` when `batch` does
-    /// not have the shape the schema promised.
-    fn entries<'a>(
-        &self,
-        batch: &'a RecordBatch,
-        top: Entries<'a>,
-    ) -> Option<(&'a dyn Array, Entries<'a>)> {
+    /// The arrays of `batch` the way to the leaf passes through, or `None` when `batch` does not
+    /// have the shape the schema promised.
+    fn path<'a>(&self, batch: &'a RecordBatch) -> Option<Path<'a>> {
         let mut array = batch.columns().get(self.column)?.as_ref();
-        let mut entries = top;
+        let mut levels = Vec::with_capacity(self.steps.len());
         for step in &self.steps {
-            let present = present(array, entries);
-            (array, entries) = match (step, array.data_type()) {
+            let (children, next) = match (step, array.data_type()) {
                 (Step::Field(field), DataType::Struct(_)) => {
-                    (array.as_struct().columns().get(*field)?.as_ref(), present)
+                    (Children::Same, array.as_struct().columns().get(*field)?)
                 }
                 (Step::Element, DataType::List(_)) => {
                     let list = array.as_list::<i32>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
+                    (Children::Offsets(list.value_offsets()), list.values())
                 }
                 (Step::Element, DataType::LargeList(_)) => {
                     let list = array.as_list::<i64>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
-                }
-                (Step::Element, DataType::FixedSizeList(_, size)) => {
-                    let size = *size as usize;
-                    let elements: Entries<'a> = Box::new(present.flat_map(move |(row, index)| {
-                        (index * size..(index + 1) * size).map(move |element| (row, element))
-                    }));
-                    (array.as_fixed_size_list().values().as_ref(), elements)
+                    (Children::LargeOffsets(list.value_offsets()), list.values())
                 }
+                (Step::Element, DataType::FixedSizeList(_, size)) => (
+                    Children::Fixed(*size as usize),
+                    array.as_fixed_size_list().values(),
+                ),
                 (Step::Key, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (map.keys().as_ref(), children(present, map.value_offsets()))
+                    (Children::Offsets(map.value_offsets()), map.keys())
                 }
                 (Step::Value, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (
-                        map.values().as_ref(),
-                        children(present, map.value_offsets()),
-                    )
+                    (Children::Offsets(map.value_offsets()), map.values())
                 }
                 _ => return None,
             };
+            // A null buffer with no nulls in it is as good as none, and a struct without nulls
+            // leads every entry straight to its field's, so neither needs a level.
+            let nulls = present_nulls(array);
+            if nulls.is_some() || !matches!(children, Children::Same) {
+                levels.push(Level { nulls, children });
+            }
+            array = next.as_ref();
         }
-        Some((array, entries))
+        Some(Path {
+            levels,
+            leaf: array,
+        })
     }
 }
 
-/// The entries whose value in `array` is not null.
-fn present<'a>(array: &'a dyn Array, entries: Entries<'a>) -> Entries<'a> {
-    match array.nulls() {
-        Some(nulls) => Box::new(entries.filter(move |&(_, index)| nulls.is_valid(index))),
-        None => entries,
-    }
+/// The arrays the way from a batch's column down to one leaf column passes through.
+struct Path<'a> {
+    /// One for each step, from the batch's column down.
+    levels: Vec<Level<'a>>,
+    /// The leaf column's array.
+    leaf: &'a dyn Array,
 }
 
-/// The entries of the children of every list or map entry in `entries`.
-fn children<'a, O: OffsetSizeTrait>(entries: Entries<'a>, offsets: &'a [O]) -> Entries<'a> {
-    Box::new(entries.flat_map(move |(row, index)| {
-        (offsets[index].as_usize()..offsets[index + 1].as_usize()).map(move |child| (row, child))
-    }))
+/// An array on the way to a leaf, and how its entries lead into the next one.
+struct Level<'a> {
+    /// A null entry has nothing under it in the column chunk, even where a null list spans child
+    /// values.
+    nulls: Option<&'a NullBuffer>,
+    children: Children<'a>,
 }
 
-type ValueBytes<'a> = Box<dyn Fn(usize) -> &'a [u8] + 'a>;
+/// The entries of the next array that lie under entry `i` of a level.
+#[derive(Clone, Copy)]
+enum Children<'a> {
+    /// A struct's: entry `i` of its field.
+    Same,
+    /// A list's or a map's: entries `offsets[i]` up to `offsets[i + 1]` of its elements, keys or
+    /// values.
+    Offsets(&'a [i32]),
+    /// A large list's.
+    LargeOffsets(&'a [i64]),
+    /// A fixed-size list's: the `size` elements from `i * size`.
+    Fixed(usize),
+}
 
-/// The bytes that tell `array`'s values apart: a fixed-width value's native bytes, or a string's or
-/// binary's content. `None` for a type an Iceberg schema cannot produce.
-fn value_bytes<'a>(array: &'a dyn Array) -> Option<ValueBytes<'a>> {
-    let bytes: ValueBytes<'a> = downcast_primitive_array!(
-        array => Box::new(move |i| array.values()[i].to_byte_slice()),
-        DataType::Utf8 => {
-            let array = array.as_string::<i32>();
-            Box::new(move |i| array.value(i).as_bytes())
+impl Children<'_> {
+    /// Where the entries under entry `index` start in the next array. Those under the entries
+    /// before `index` end there too, so this also holds for one past the last entry.
+    fn start(self, index: usize) -> usize {

Review Comment:
   Sliced batches reach `choose` on a real path. When `BatchSlicer::slice` in `iceberg_write.rs` isn't gathering, it hands the clustered arm `batch.slice(offset, len)`. This rewrite redoes all of the index arithmetic: `Children::start`, `Path::entries`, and the sliced null buffers through `present_nulls`. None of the in-tree chooser tests use a batch with a non-zero offset, though. `batch_boundaries_do_not_change_the_choice` builds fresh batches, and the differential run that did cover slicing isn't checked in.
   
   Could `batch_boundaries_do_not_change_the_choice` also cut `corpus(0..20_000)` with `RecordBatch::slice` at a few offsets? It would also help to add one nested case with null lists and null structs sliced at an odd offset, compared against the same rows materialized with `concat_batches`. I tried both locally and they pass. They would keep this path pinned going forward.



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] perf: make the native Iceberg writer's dictionary pre-pass 1.8x to 3.9x faster [datafusion-comet]

Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on code in PR #6937:
URL: https://github.com/apache/datafusion-comet/pull/6937#discussion_r4274915000


##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -254,139 +343,230 @@ fn collect_leaves(data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>)
                 descend(Step::Key, fields[0].data_type(), leaf, leaves);
                 descend(Step::Value, fields[1].data_type(), leaf, leaves);
             }
-            _ => leaves.push(leaf.clone()),
+            _ => leaves.push((leaf.clone(), data_type.clone())),
         },
-        _ => leaves.push(leaf.clone()),
+        _ => leaves.push((leaf.clone(), data_type.clone())),
     }
 }
 
-fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>) {
+fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<(Leaf, DataType)>) {
     leaf.steps.push(step);
     collect_leaves(data_type, leaf, leaves);
     leaf.steps.pop();
 }
 
-/// `(row, index)` pairs, one per entry of an array that the column chunk stores: its row of the
-/// batch, and its index into the array.
-type Entries<'a> = Box<dyn Iterator<Item = (u32, usize)> + 'a>;
-
 impl Leaf {
-    /// The leaf's array in `batch`, with the entries of it that lie under the rows `top` yields and
-    /// whose ancestors are all present, in the order the column chunk stores them. Nothing is
-    /// expanded ahead: each entry is produced when the page asks for it. `None` when `batch` does
-    /// not have the shape the schema promised.
-    fn entries<'a>(
-        &self,
-        batch: &'a RecordBatch,
-        top: Entries<'a>,
-    ) -> Option<(&'a dyn Array, Entries<'a>)> {
+    /// The arrays of `batch` the way to the leaf passes through, or `None` when `batch` does not
+    /// have the shape the schema promised.
+    fn path<'a>(&self, batch: &'a RecordBatch) -> Option<Path<'a>> {
         let mut array = batch.columns().get(self.column)?.as_ref();
-        let mut entries = top;
+        let mut levels = Vec::with_capacity(self.steps.len());
         for step in &self.steps {
-            let present = present(array, entries);
-            (array, entries) = match (step, array.data_type()) {
+            let (children, next) = match (step, array.data_type()) {
                 (Step::Field(field), DataType::Struct(_)) => {
-                    (array.as_struct().columns().get(*field)?.as_ref(), present)
+                    (Children::Same, array.as_struct().columns().get(*field)?)
                 }
                 (Step::Element, DataType::List(_)) => {
                     let list = array.as_list::<i32>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
+                    (Children::Offsets(list.value_offsets()), list.values())
                 }
                 (Step::Element, DataType::LargeList(_)) => {
                     let list = array.as_list::<i64>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
-                }
-                (Step::Element, DataType::FixedSizeList(_, size)) => {
-                    let size = *size as usize;
-                    let elements: Entries<'a> = Box::new(present.flat_map(move |(row, index)| {
-                        (index * size..(index + 1) * size).map(move |element| (row, element))
-                    }));
-                    (array.as_fixed_size_list().values().as_ref(), elements)
+                    (Children::LargeOffsets(list.value_offsets()), list.values())
                 }
+                (Step::Element, DataType::FixedSizeList(_, size)) => (
+                    Children::Fixed(*size as usize),
+                    array.as_fixed_size_list().values(),
+                ),
                 (Step::Key, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (map.keys().as_ref(), children(present, map.value_offsets()))
+                    (Children::Offsets(map.value_offsets()), map.keys())
                 }
                 (Step::Value, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (
-                        map.values().as_ref(),
-                        children(present, map.value_offsets()),
-                    )
+                    (Children::Offsets(map.value_offsets()), map.values())
                 }
                 _ => return None,
             };
+            // A null buffer with no nulls in it is as good as none, and a struct without nulls
+            // leads every entry straight to its field's, so neither needs a level.
+            let nulls = present_nulls(array);
+            if nulls.is_some() || !matches!(children, Children::Same) {
+                levels.push(Level { nulls, children });
+            }
+            array = next.as_ref();
         }
-        Some((array, entries))
+        Some(Path {
+            levels,
+            leaf: array,
+        })
     }
 }
 
-/// The entries whose value in `array` is not null.
-fn present<'a>(array: &'a dyn Array, entries: Entries<'a>) -> Entries<'a> {
-    match array.nulls() {
-        Some(nulls) => Box::new(entries.filter(move |&(_, index)| nulls.is_valid(index))),
-        None => entries,
-    }
+/// The arrays the way from a batch's column down to one leaf column passes through.
+struct Path<'a> {
+    /// One for each step, from the batch's column down.
+    levels: Vec<Level<'a>>,
+    /// The leaf column's array.
+    leaf: &'a dyn Array,
 }
 
-/// The entries of the children of every list or map entry in `entries`.
-fn children<'a, O: OffsetSizeTrait>(entries: Entries<'a>, offsets: &'a [O]) -> Entries<'a> {
-    Box::new(entries.flat_map(move |(row, index)| {
-        (offsets[index].as_usize()..offsets[index + 1].as_usize()).map(move |child| (row, child))
-    }))
+/// An array on the way to a leaf, and how its entries lead into the next one.
+struct Level<'a> {
+    /// A null entry has nothing under it in the column chunk, even where a null list spans child
+    /// values.
+    nulls: Option<&'a NullBuffer>,
+    children: Children<'a>,
 }
 
-type ValueBytes<'a> = Box<dyn Fn(usize) -> &'a [u8] + 'a>;
+/// The entries of the next array that lie under entry `i` of a level.
+#[derive(Clone, Copy)]
+enum Children<'a> {
+    /// A struct's: entry `i` of its field.
+    Same,
+    /// A list's or a map's: entries `offsets[i]` up to `offsets[i + 1]` of its elements, keys or
+    /// values.
+    Offsets(&'a [i32]),
+    /// A large list's.
+    LargeOffsets(&'a [i64]),
+    /// A fixed-size list's: the `size` elements from `i * size`.
+    Fixed(usize),
+}
 
-/// The bytes that tell `array`'s values apart: a fixed-width value's native bytes, or a string's or
-/// binary's content. `None` for a type an Iceberg schema cannot produce.
-fn value_bytes<'a>(array: &'a dyn Array) -> Option<ValueBytes<'a>> {
-    let bytes: ValueBytes<'a> = downcast_primitive_array!(
-        array => Box::new(move |i| array.values()[i].to_byte_slice()),
-        DataType::Utf8 => {
-            let array = array.as_string::<i32>();
-            Box::new(move |i| array.value(i).as_bytes())
+impl Children<'_> {
+    /// Where the entries under entry `index` start in the next array. Those under the entries
+    /// before `index` end there too, so this also holds for one past the last entry.
+    fn start(self, index: usize) -> usize {

Review Comment:
   Added both in f67eab9ef8. `batch_boundaries_do_not_change_the_choice` now also cuts `corpus(0..20_000)` with `RecordBatch::slice` at the same three batch sizes. The new `a_sliced_batch_is_read_only_within_its_slice` slices a batch of a list, a large list, a fixed-size list, a map, nested structs and a list of structs at offset 1001, with nulls at every level, and checks it against the same rows materialized.
   
   For the materialized copy I used `take_record_batch` rather than `concat_batches`. Given a single batch, arrow's `concat` returns `array.slice(0, len)`, so `concat_batches` would have handed back the same sliced arrays and the test would have compared the slice with itself. `take_record_batch` copies the rows into fresh arrays, which is also how the fanout arm cuts its parts.
   
   Every value outside the slice or under a null is distinct, so reading any of them overflows the 1 KiB dictionary. I checked the tests against three mutations: list offsets taken relative to the slice, and null checks that ignore the null buffer's offset, once at an intermediate level and once at the leaf. The new test fails on all three, and none of the existing tests caught any of them.
   



##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -254,139 +343,230 @@ fn collect_leaves(data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>)
                 descend(Step::Key, fields[0].data_type(), leaf, leaves);
                 descend(Step::Value, fields[1].data_type(), leaf, leaves);
             }
-            _ => leaves.push(leaf.clone()),
+            _ => leaves.push((leaf.clone(), data_type.clone())),
         },
-        _ => leaves.push(leaf.clone()),
+        _ => leaves.push((leaf.clone(), data_type.clone())),
     }
 }
 
-fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>) {
+fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<(Leaf, DataType)>) {
     leaf.steps.push(step);
     collect_leaves(data_type, leaf, leaves);
     leaf.steps.pop();
 }
 
-/// `(row, index)` pairs, one per entry of an array that the column chunk stores: its row of the
-/// batch, and its index into the array.
-type Entries<'a> = Box<dyn Iterator<Item = (u32, usize)> + 'a>;
-
 impl Leaf {
-    /// The leaf's array in `batch`, with the entries of it that lie under the rows `top` yields and
-    /// whose ancestors are all present, in the order the column chunk stores them. Nothing is
-    /// expanded ahead: each entry is produced when the page asks for it. `None` when `batch` does
-    /// not have the shape the schema promised.
-    fn entries<'a>(
-        &self,
-        batch: &'a RecordBatch,
-        top: Entries<'a>,
-    ) -> Option<(&'a dyn Array, Entries<'a>)> {
+    /// The arrays of `batch` the way to the leaf passes through, or `None` when `batch` does not
+    /// have the shape the schema promised.
+    fn path<'a>(&self, batch: &'a RecordBatch) -> Option<Path<'a>> {
         let mut array = batch.columns().get(self.column)?.as_ref();
-        let mut entries = top;
+        let mut levels = Vec::with_capacity(self.steps.len());
         for step in &self.steps {
-            let present = present(array, entries);
-            (array, entries) = match (step, array.data_type()) {
+            let (children, next) = match (step, array.data_type()) {
                 (Step::Field(field), DataType::Struct(_)) => {
-                    (array.as_struct().columns().get(*field)?.as_ref(), present)
+                    (Children::Same, array.as_struct().columns().get(*field)?)
                 }
                 (Step::Element, DataType::List(_)) => {
                     let list = array.as_list::<i32>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
+                    (Children::Offsets(list.value_offsets()), list.values())
                 }
                 (Step::Element, DataType::LargeList(_)) => {
                     let list = array.as_list::<i64>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
-                }
-                (Step::Element, DataType::FixedSizeList(_, size)) => {
-                    let size = *size as usize;
-                    let elements: Entries<'a> = Box::new(present.flat_map(move |(row, index)| {
-                        (index * size..(index + 1) * size).map(move |element| (row, element))
-                    }));
-                    (array.as_fixed_size_list().values().as_ref(), elements)
+                    (Children::LargeOffsets(list.value_offsets()), list.values())
                 }
+                (Step::Element, DataType::FixedSizeList(_, size)) => (
+                    Children::Fixed(*size as usize),
+                    array.as_fixed_size_list().values(),
+                ),
                 (Step::Key, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (map.keys().as_ref(), children(present, map.value_offsets()))
+                    (Children::Offsets(map.value_offsets()), map.keys())
                 }
                 (Step::Value, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (
-                        map.values().as_ref(),
-                        children(present, map.value_offsets()),
-                    )
+                    (Children::Offsets(map.value_offsets()), map.values())
                 }
                 _ => return None,
             };
+            // A null buffer with no nulls in it is as good as none, and a struct without nulls
+            // leads every entry straight to its field's, so neither needs a level.
+            let nulls = present_nulls(array);
+            if nulls.is_some() || !matches!(children, Children::Same) {
+                levels.push(Level { nulls, children });
+            }
+            array = next.as_ref();
         }
-        Some((array, entries))
+        Some(Path {
+            levels,
+            leaf: array,
+        })
     }
 }
 
-/// The entries whose value in `array` is not null.
-fn present<'a>(array: &'a dyn Array, entries: Entries<'a>) -> Entries<'a> {
-    match array.nulls() {
-        Some(nulls) => Box::new(entries.filter(move |&(_, index)| nulls.is_valid(index))),
-        None => entries,
-    }
+/// The arrays the way from a batch's column down to one leaf column passes through.
+struct Path<'a> {
+    /// One for each step, from the batch's column down.
+    levels: Vec<Level<'a>>,
+    /// The leaf column's array.
+    leaf: &'a dyn Array,
 }
 
-/// The entries of the children of every list or map entry in `entries`.
-fn children<'a, O: OffsetSizeTrait>(entries: Entries<'a>, offsets: &'a [O]) -> Entries<'a> {
-    Box::new(entries.flat_map(move |(row, index)| {
-        (offsets[index].as_usize()..offsets[index + 1].as_usize()).map(move |child| (row, child))
-    }))
+/// An array on the way to a leaf, and how its entries lead into the next one.
+struct Level<'a> {
+    /// A null entry has nothing under it in the column chunk, even where a null list spans child
+    /// values.
+    nulls: Option<&'a NullBuffer>,
+    children: Children<'a>,
 }
 
-type ValueBytes<'a> = Box<dyn Fn(usize) -> &'a [u8] + 'a>;
+/// The entries of the next array that lie under entry `i` of a level.
+#[derive(Clone, Copy)]
+enum Children<'a> {
+    /// A struct's: entry `i` of its field.
+    Same,
+    /// A list's or a map's: entries `offsets[i]` up to `offsets[i + 1]` of its elements, keys or
+    /// values.
+    Offsets(&'a [i32]),
+    /// A large list's.
+    LargeOffsets(&'a [i64]),
+    /// A fixed-size list's: the `size` elements from `i * size`.
+    Fixed(usize),
+}
 
-/// The bytes that tell `array`'s values apart: a fixed-width value's native bytes, or a string's or
-/// binary's content. `None` for a type an Iceberg schema cannot produce.
-fn value_bytes<'a>(array: &'a dyn Array) -> Option<ValueBytes<'a>> {
-    let bytes: ValueBytes<'a> = downcast_primitive_array!(
-        array => Box::new(move |i| array.values()[i].to_byte_slice()),
-        DataType::Utf8 => {
-            let array = array.as_string::<i32>();
-            Box::new(move |i| array.value(i).as_bytes())
+impl Children<'_> {
+    /// Where the entries under entry `index` start in the next array. Those under the entries
+    /// before `index` end there too, so this also holds for one past the last entry.
+    fn start(self, index: usize) -> usize {
+        match self {
+            Children::Same => index,
+            Children::Offsets(offsets) => offsets[index] as usize,
+            Children::LargeOffsets(offsets) => offsets[index] as usize,
+            Children::Fixed(size) => index * size,
         }
-        DataType::LargeUtf8 => {
-            let array = array.as_string::<i64>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Utf8View => {
-            let array = array.as_string_view();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Binary => {
-            let array = array.as_binary::<i32>();
-            Box::new(move |i| array.value(i))
-        }
-        DataType::LargeBinary => {
-            let array = array.as_binary::<i64>();
-            Box::new(move |i| array.value(i))
-        }
-        DataType::BinaryView => {
-            let array = array.as_binary_view();
-            Box::new(move |i| array.value(i))
+    }
+}
+
+impl Path<'_> {
+    /// How many entries of the leaf array lie under the batch's first `rows` rows, null or not.
+    fn entries(&self, rows: usize) -> usize {
+        let (start, end) = self.levels.iter().fold((0, rows), |(start, end), level| {
+            (level.children.start(start), level.children.start(end))
+        });
+        end - start
+    }
+
+    /// Calls `f` with the leaf index of every entry under the batch's row `row` whose ancestors
+    /// are all present, in the order the column chunk stores them, until `f` returns `false`.
+    /// Returns whether every entry was visited. Nothing is expanded ahead, so a page that ends
+    /// partway through a batch reads no further.
+    fn visit(&self, row: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+        // A leaf with no levels above it has one entry per row: the row itself.
+        if self.levels.is_empty() {
+            return f(row);
         }
-        _ => return None,
-    );
-    Some(bytes)
+        visit(&self.levels, row, f)
+    }
+}
+
+/// `array`'s nulls, or `None` when it has none.
+fn present_nulls(array: &dyn Array) -> Option<&NullBuffer> {
+    array.nulls().filter(|nulls| nulls.null_count() > 0)
+}
+
+fn visit(levels: &[Level], index: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+    let Some((level, below)) = levels.split_first() else {
+        return f(index);
+    };
+    if level.nulls.is_some_and(|nulls| nulls.is_null(index)) {
+        return true;
+    }
+    let mut children = level.children.start(index)..level.children.start(index + 1);
+    // The leaf's entries are visited here rather than one call deeper each.
+    if below.is_empty() {
+        children.all(f)
+    } else {
+        children.all(|child| visit(below, child, &mut *f))
+    }
+}
+
+/// Reads fixed-width values by their bits, zero-extended to `K`, which is at least as wide.
+fn bits<T: ArrowNativeType, K: Bits>(values: &[T]) -> impl Fn(usize) -> (K, usize) + '_ {
+    move |index| (K::of(values[index]), size_of::<T>())
+}
+
+/// Reads fixed-width values too wide for [`bits`] by their native bytes.
+fn native_bytes<'a, T: ArrowNativeType>(values: &'a [T]) -> impl Fn(usize) -> (Bytes<'a>, usize) {
+    move |index| Bytes::of(values[index].to_byte_slice())
+}
+
+/// Reads a string or binary array's values by their content.
+fn bytes<'a, A, V>(array: A) -> impl Fn(usize) -> (Bytes<'a>, usize)
+where
+    A: ArrayAccessor<Item = &'a V>,
+    V: AsRef<[u8]> + ?Sized + 'a,
+{
+    move |index| Bytes::of(array.value(index).as_ref())
+}
+
+/// The bits of a fixed-width value, zero-extended to fill this type.
+trait Bits: Copy + Eq + Hash {
+    fn of<T: ArrowNativeType>(value: T) -> Self;
+}
+
+impl Bits for u64 {
+    fn of<T: ArrowNativeType>(value: T) -> Self {
+        let mut bits = [0; 8];
+        let bytes = value.to_byte_slice();
+        bits[..bytes.len()].copy_from_slice(bytes);
+        u64::from_ne_bytes(bits)
+    }
+}
+
+impl Bits for u128 {
+    fn of<T: ArrowNativeType>(value: T) -> Self {
+        let mut bits = [0; 16];
+        let bytes = value.to_byte_slice();
+        bits[..bytes.len()].copy_from_slice(bytes);
+        u128::from_ne_bytes(bits)
+    }
+}
+
+/// A value's bytes. Two of the same length whose last bytes differ are told apart without
+/// comparing the rest, which spares comparing most distinct values with the one before them.
+#[derive(Clone, Copy)]
+struct Bytes<'a>(&'a [u8]);
+
+impl<'a> Bytes<'a> {
+    /// `bytes` as a value, and how many there are.
+    fn of(bytes: &'a [u8]) -> (Self, usize) {
+        (Self(bytes), bytes.len())
+    }
+}
+
+impl PartialEq for Bytes<'_> {
+    fn eq(&self, other: &Self) -> bool {
+        self.0.len() == other.0.len() && self.0.last() == other.0.last() && self.0 == other.0

Review Comment:
   It does pay off, so I kept it and put the numbers in its doc comment in f67eab9ef8. I timed `choose` on the benchmark's shapes in one process, alternating between `Bytes`, plain `&[u8]` keys, and each half of `Bytes` on its own, for 150 rounds per shape. All of them made the same choices. With plain slices `maps` took 27% longer, `nested` 24%, `primitives` 12%, `arrays` 11%, `primitives_1k` 9% and `structs` 3%, while `sorted`, where most values repeat the one before, took 2% less.
   
   Most of it is the length and last-byte check, through the comparison with `previous` as you guessed: dropping only that cost 16% on `maps` and `nested`. Their keys, like `k0` and `k1`, mostly have the same length as the key before them, and slice equality calls `bcmp` whenever the lengths match. Hashing without the length is worth up to 3%.
   



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] perf: make the native Iceberg writer's dictionary pre-pass 1.8x to 3.9x faster [datafusion-comet]

Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on code in PR #6937:
URL: https://github.com/apache/datafusion-comet/pull/6937#discussion_r4286201701


##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -1253,6 +1677,26 @@ mod tests {
         );
     }
 
+    /// The fields of a null struct are not part of the column chunk either.
+    #[test]
+    fn values_under_a_null_struct_are_not_counted() {

Review Comment:
   I'd lean toward keeping `values_under_a_null_struct_are_not_counted`. It is small and pins one property, so a failure points straight at the struct-null check, where the sliced test would only show a different column list. It also pairs with `values_under_a_null_list_are_not_counted`, which the sliced test covers just as much.



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] perf: make the native Iceberg writer's dictionary pre-pass 1.8x to 3.9x faster [datafusion-comet]

Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on code in PR #6937:
URL: https://github.com/apache/datafusion-comet/pull/6937#discussion_r4286327808


##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -254,139 +343,234 @@ fn collect_leaves(data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>)
                 descend(Step::Key, fields[0].data_type(), leaf, leaves);
                 descend(Step::Value, fields[1].data_type(), leaf, leaves);
             }
-            _ => leaves.push(leaf.clone()),
+            _ => leaves.push((leaf.clone(), data_type.clone())),
         },
-        _ => leaves.push(leaf.clone()),
+        _ => leaves.push((leaf.clone(), data_type.clone())),
     }
 }
 
-fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>) {
+fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<(Leaf, DataType)>) {
     leaf.steps.push(step);
     collect_leaves(data_type, leaf, leaves);
     leaf.steps.pop();
 }
 
-/// `(row, index)` pairs, one per entry of an array that the column chunk stores: its row of the
-/// batch, and its index into the array.
-type Entries<'a> = Box<dyn Iterator<Item = (u32, usize)> + 'a>;
-
 impl Leaf {
-    /// The leaf's array in `batch`, with the entries of it that lie under the rows `top` yields and
-    /// whose ancestors are all present, in the order the column chunk stores them. Nothing is
-    /// expanded ahead: each entry is produced when the page asks for it. `None` when `batch` does
-    /// not have the shape the schema promised.
-    fn entries<'a>(
-        &self,
-        batch: &'a RecordBatch,
-        top: Entries<'a>,
-    ) -> Option<(&'a dyn Array, Entries<'a>)> {
+    /// The arrays of `batch` the way to the leaf passes through, or `None` when `batch` does not
+    /// have the shape the schema promised.
+    fn path<'a>(&self, batch: &'a RecordBatch) -> Option<Path<'a>> {
         let mut array = batch.columns().get(self.column)?.as_ref();
-        let mut entries = top;
+        let mut levels = Vec::with_capacity(self.steps.len());
         for step in &self.steps {
-            let present = present(array, entries);
-            (array, entries) = match (step, array.data_type()) {
+            let (children, next) = match (step, array.data_type()) {
                 (Step::Field(field), DataType::Struct(_)) => {
-                    (array.as_struct().columns().get(*field)?.as_ref(), present)
+                    (Children::Same, array.as_struct().columns().get(*field)?)
                 }
                 (Step::Element, DataType::List(_)) => {
                     let list = array.as_list::<i32>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
+                    (Children::Offsets(list.value_offsets()), list.values())
                 }
                 (Step::Element, DataType::LargeList(_)) => {
                     let list = array.as_list::<i64>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
-                }
-                (Step::Element, DataType::FixedSizeList(_, size)) => {
-                    let size = *size as usize;
-                    let elements: Entries<'a> = Box::new(present.flat_map(move |(row, index)| {
-                        (index * size..(index + 1) * size).map(move |element| (row, element))
-                    }));
-                    (array.as_fixed_size_list().values().as_ref(), elements)
+                    (Children::LargeOffsets(list.value_offsets()), list.values())
                 }
+                (Step::Element, DataType::FixedSizeList(_, size)) => (
+                    Children::Fixed(*size as usize),
+                    array.as_fixed_size_list().values(),
+                ),
                 (Step::Key, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (map.keys().as_ref(), children(present, map.value_offsets()))
+                    (Children::Offsets(map.value_offsets()), map.keys())
                 }
                 (Step::Value, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (
-                        map.values().as_ref(),
-                        children(present, map.value_offsets()),
-                    )
+                    (Children::Offsets(map.value_offsets()), map.values())
                 }
                 _ => return None,
             };
+            // A null buffer with no nulls in it is as good as none, and a struct without nulls
+            // leads every entry straight to its field's, so neither needs a level.
+            let nulls = present_nulls(array);
+            if nulls.is_some() || !matches!(children, Children::Same) {
+                levels.push(Level { nulls, children });
+            }
+            array = next.as_ref();
         }
-        Some((array, entries))
+        Some(Path {
+            levels,
+            leaf: array,
+        })
     }
 }
 
-/// The entries whose value in `array` is not null.
-fn present<'a>(array: &'a dyn Array, entries: Entries<'a>) -> Entries<'a> {
-    match array.nulls() {
-        Some(nulls) => Box::new(entries.filter(move |&(_, index)| nulls.is_valid(index))),
-        None => entries,
-    }
+/// The arrays the way from a batch's column down to one leaf column passes through.
+struct Path<'a> {
+    /// One for each step, from the batch's column down.
+    levels: Vec<Level<'a>>,
+    /// The leaf column's array.
+    leaf: &'a dyn Array,
 }
 
-/// The entries of the children of every list or map entry in `entries`.
-fn children<'a, O: OffsetSizeTrait>(entries: Entries<'a>, offsets: &'a [O]) -> Entries<'a> {
-    Box::new(entries.flat_map(move |(row, index)| {
-        (offsets[index].as_usize()..offsets[index + 1].as_usize()).map(move |child| (row, child))
-    }))
+/// An array on the way to a leaf, and how its entries lead into the next one.
+struct Level<'a> {
+    /// A null entry has nothing under it in the column chunk, even where a null list spans child
+    /// values.
+    nulls: Option<&'a NullBuffer>,
+    children: Children<'a>,
 }
 
-type ValueBytes<'a> = Box<dyn Fn(usize) -> &'a [u8] + 'a>;
+/// The entries of the next array that lie under entry `i` of a level.
+#[derive(Clone, Copy)]
+enum Children<'a> {
+    /// A struct's: entry `i` of its field.
+    Same,
+    /// A list's or a map's: entries `offsets[i]` up to `offsets[i + 1]` of its elements, keys or
+    /// values.
+    Offsets(&'a [i32]),
+    /// A large list's.
+    LargeOffsets(&'a [i64]),
+    /// A fixed-size list's: the `size` elements from `i * size`.
+    Fixed(usize),
+}
 
-/// The bytes that tell `array`'s values apart: a fixed-width value's native bytes, or a string's or
-/// binary's content. `None` for a type an Iceberg schema cannot produce.
-fn value_bytes<'a>(array: &'a dyn Array) -> Option<ValueBytes<'a>> {
-    let bytes: ValueBytes<'a> = downcast_primitive_array!(
-        array => Box::new(move |i| array.values()[i].to_byte_slice()),
-        DataType::Utf8 => {
-            let array = array.as_string::<i32>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::LargeUtf8 => {
-            let array = array.as_string::<i64>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Utf8View => {
-            let array = array.as_string_view();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Binary => {
-            let array = array.as_binary::<i32>();
-            Box::new(move |i| array.value(i))
-        }
-        DataType::LargeBinary => {
-            let array = array.as_binary::<i64>();
-            Box::new(move |i| array.value(i))
+impl Children<'_> {
+    /// Where the entries under entry `index` start in the next array. Those under the entries
+    /// before `index` end there too, so this also holds for one past the last entry.
+    fn start(self, index: usize) -> usize {
+        match self {
+            Children::Same => index,
+            Children::Offsets(offsets) => offsets[index] as usize,
+            Children::LargeOffsets(offsets) => offsets[index] as usize,
+            Children::Fixed(size) => index * size,
         }
-        DataType::BinaryView => {
-            let array = array.as_binary_view();
-            Box::new(move |i| array.value(i))
+    }
+}
+
+impl Path<'_> {
+    /// How many entries of the leaf array lie under the batch's first `rows` rows, null or not.
+    fn entries(&self, rows: usize) -> usize {
+        let (start, end) = self.levels.iter().fold((0, rows), |(start, end), level| {
+            (level.children.start(start), level.children.start(end))
+        });
+        end - start
+    }
+
+    /// Calls `f` with the leaf index of every entry under the batch's row `row` whose ancestors
+    /// are all present, in the order the column chunk stores them, until `f` returns `false`.
+    /// Returns whether every entry was visited. Nothing is expanded ahead, so a page that ends
+    /// partway through a batch reads no further.
+    fn visit(&self, row: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+        // A leaf with no levels above it has one entry per row: the row itself.
+        if self.levels.is_empty() {
+            return f(row);
         }
-        _ => return None,
-    );
-    Some(bytes)
+        visit(&self.levels, row, f)
+    }
+}
+
+/// `array`'s nulls, or `None` when it has none.
+fn present_nulls(array: &dyn Array) -> Option<&NullBuffer> {
+    array.nulls().filter(|nulls| nulls.null_count() > 0)
+}
+
+fn visit(levels: &[Level], index: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+    let Some((level, below)) = levels.split_first() else {
+        return f(index);
+    };

Review Comment:
   Good catch. `Path::visit` now calls `split_first` itself and hands `level` and `below` to `visit`, which no longer checks for an empty slice. Done in 5a832dd579.



##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -254,139 +343,234 @@ fn collect_leaves(data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>)
                 descend(Step::Key, fields[0].data_type(), leaf, leaves);
                 descend(Step::Value, fields[1].data_type(), leaf, leaves);
             }
-            _ => leaves.push(leaf.clone()),
+            _ => leaves.push((leaf.clone(), data_type.clone())),
         },
-        _ => leaves.push(leaf.clone()),
+        _ => leaves.push((leaf.clone(), data_type.clone())),
     }
 }
 
-fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>) {
+fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<(Leaf, DataType)>) {
     leaf.steps.push(step);
     collect_leaves(data_type, leaf, leaves);
     leaf.steps.pop();
 }
 
-/// `(row, index)` pairs, one per entry of an array that the column chunk stores: its row of the
-/// batch, and its index into the array.
-type Entries<'a> = Box<dyn Iterator<Item = (u32, usize)> + 'a>;
-
 impl Leaf {
-    /// The leaf's array in `batch`, with the entries of it that lie under the rows `top` yields and
-    /// whose ancestors are all present, in the order the column chunk stores them. Nothing is
-    /// expanded ahead: each entry is produced when the page asks for it. `None` when `batch` does
-    /// not have the shape the schema promised.
-    fn entries<'a>(
-        &self,
-        batch: &'a RecordBatch,
-        top: Entries<'a>,
-    ) -> Option<(&'a dyn Array, Entries<'a>)> {
+    /// The arrays of `batch` the way to the leaf passes through, or `None` when `batch` does not
+    /// have the shape the schema promised.
+    fn path<'a>(&self, batch: &'a RecordBatch) -> Option<Path<'a>> {
         let mut array = batch.columns().get(self.column)?.as_ref();
-        let mut entries = top;
+        let mut levels = Vec::with_capacity(self.steps.len());
         for step in &self.steps {
-            let present = present(array, entries);
-            (array, entries) = match (step, array.data_type()) {
+            let (children, next) = match (step, array.data_type()) {
                 (Step::Field(field), DataType::Struct(_)) => {
-                    (array.as_struct().columns().get(*field)?.as_ref(), present)
+                    (Children::Same, array.as_struct().columns().get(*field)?)
                 }
                 (Step::Element, DataType::List(_)) => {
                     let list = array.as_list::<i32>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
+                    (Children::Offsets(list.value_offsets()), list.values())
                 }
                 (Step::Element, DataType::LargeList(_)) => {
                     let list = array.as_list::<i64>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
-                }
-                (Step::Element, DataType::FixedSizeList(_, size)) => {
-                    let size = *size as usize;
-                    let elements: Entries<'a> = Box::new(present.flat_map(move |(row, index)| {
-                        (index * size..(index + 1) * size).map(move |element| (row, element))
-                    }));
-                    (array.as_fixed_size_list().values().as_ref(), elements)
+                    (Children::LargeOffsets(list.value_offsets()), list.values())
                 }
+                (Step::Element, DataType::FixedSizeList(_, size)) => (
+                    Children::Fixed(*size as usize),
+                    array.as_fixed_size_list().values(),
+                ),
                 (Step::Key, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (map.keys().as_ref(), children(present, map.value_offsets()))
+                    (Children::Offsets(map.value_offsets()), map.keys())
                 }
                 (Step::Value, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (
-                        map.values().as_ref(),
-                        children(present, map.value_offsets()),
-                    )
+                    (Children::Offsets(map.value_offsets()), map.values())
                 }
                 _ => return None,
             };
+            // A null buffer with no nulls in it is as good as none, and a struct without nulls
+            // leads every entry straight to its field's, so neither needs a level.
+            let nulls = present_nulls(array);
+            if nulls.is_some() || !matches!(children, Children::Same) {
+                levels.push(Level { nulls, children });
+            }
+            array = next.as_ref();
         }
-        Some((array, entries))
+        Some(Path {
+            levels,
+            leaf: array,
+        })
     }
 }
 
-/// The entries whose value in `array` is not null.
-fn present<'a>(array: &'a dyn Array, entries: Entries<'a>) -> Entries<'a> {
-    match array.nulls() {
-        Some(nulls) => Box::new(entries.filter(move |&(_, index)| nulls.is_valid(index))),
-        None => entries,
-    }
+/// The arrays the way from a batch's column down to one leaf column passes through.
+struct Path<'a> {
+    /// One for each step, from the batch's column down.
+    levels: Vec<Level<'a>>,
+    /// The leaf column's array.
+    leaf: &'a dyn Array,
 }
 
-/// The entries of the children of every list or map entry in `entries`.
-fn children<'a, O: OffsetSizeTrait>(entries: Entries<'a>, offsets: &'a [O]) -> Entries<'a> {
-    Box::new(entries.flat_map(move |(row, index)| {
-        (offsets[index].as_usize()..offsets[index + 1].as_usize()).map(move |child| (row, child))
-    }))
+/// An array on the way to a leaf, and how its entries lead into the next one.
+struct Level<'a> {
+    /// A null entry has nothing under it in the column chunk, even where a null list spans child
+    /// values.
+    nulls: Option<&'a NullBuffer>,
+    children: Children<'a>,
 }
 
-type ValueBytes<'a> = Box<dyn Fn(usize) -> &'a [u8] + 'a>;
+/// The entries of the next array that lie under entry `i` of a level.
+#[derive(Clone, Copy)]
+enum Children<'a> {
+    /// A struct's: entry `i` of its field.
+    Same,
+    /// A list's or a map's: entries `offsets[i]` up to `offsets[i + 1]` of its elements, keys or
+    /// values.
+    Offsets(&'a [i32]),
+    /// A large list's.
+    LargeOffsets(&'a [i64]),
+    /// A fixed-size list's: the `size` elements from `i * size`.
+    Fixed(usize),
+}
 
-/// The bytes that tell `array`'s values apart: a fixed-width value's native bytes, or a string's or
-/// binary's content. `None` for a type an Iceberg schema cannot produce.
-fn value_bytes<'a>(array: &'a dyn Array) -> Option<ValueBytes<'a>> {
-    let bytes: ValueBytes<'a> = downcast_primitive_array!(
-        array => Box::new(move |i| array.values()[i].to_byte_slice()),
-        DataType::Utf8 => {
-            let array = array.as_string::<i32>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::LargeUtf8 => {
-            let array = array.as_string::<i64>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Utf8View => {
-            let array = array.as_string_view();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Binary => {
-            let array = array.as_binary::<i32>();
-            Box::new(move |i| array.value(i))
-        }
-        DataType::LargeBinary => {
-            let array = array.as_binary::<i64>();
-            Box::new(move |i| array.value(i))
+impl Children<'_> {
+    /// Where the entries under entry `index` start in the next array. Those under the entries
+    /// before `index` end there too, so this also holds for one past the last entry.
+    fn start(self, index: usize) -> usize {
+        match self {
+            Children::Same => index,
+            Children::Offsets(offsets) => offsets[index] as usize,
+            Children::LargeOffsets(offsets) => offsets[index] as usize,
+            Children::Fixed(size) => index * size,
         }
-        DataType::BinaryView => {
-            let array = array.as_binary_view();
-            Box::new(move |i| array.value(i))
+    }
+}
+
+impl Path<'_> {
+    /// How many entries of the leaf array lie under the batch's first `rows` rows, null or not.
+    fn entries(&self, rows: usize) -> usize {
+        let (start, end) = self.levels.iter().fold((0, rows), |(start, end), level| {
+            (level.children.start(start), level.children.start(end))
+        });
+        end - start
+    }
+
+    /// Calls `f` with the leaf index of every entry under the batch's row `row` whose ancestors
+    /// are all present, in the order the column chunk stores them, until `f` returns `false`.
+    /// Returns whether every entry was visited. Nothing is expanded ahead, so a page that ends
+    /// partway through a batch reads no further.
+    fn visit(&self, row: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+        // A leaf with no levels above it has one entry per row: the row itself.
+        if self.levels.is_empty() {
+            return f(row);
         }
-        _ => return None,
-    );
-    Some(bytes)
+        visit(&self.levels, row, f)
+    }
+}
+
+/// `array`'s nulls, or `None` when it has none.
+fn present_nulls(array: &dyn Array) -> Option<&NullBuffer> {
+    array.nulls().filter(|nulls| nulls.null_count() > 0)
+}
+
+fn visit(levels: &[Level], index: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+    let Some((level, below)) = levels.split_first() else {
+        return f(index);
+    };
+    if level.nulls.is_some_and(|nulls| nulls.is_null(index)) {
+        return true;
+    }
+    let mut children = level.children.start(index)..level.children.start(index + 1);
+    // The leaf's entries are visited here rather than one call deeper each.
+    if below.is_empty() {
+        children.all(f)
+    } else {
+        children.all(|child| visit(below, child, &mut *f))
+    }
+}
+
+/// Reads fixed-width values by their bits, zero-extended to `K`, which is at least as wide.
+fn bits<T: ArrowNativeType, K: Bits>(values: &[T]) -> impl Fn(usize) -> (K, usize) + '_ {
+    move |index| (K::of(values[index]), size_of::<T>())
+}
+
+/// Reads fixed-width values too wide for [`bits`] by their native bytes.
+fn native_bytes<'a, T: ArrowNativeType>(values: &'a [T]) -> impl Fn(usize) -> (Bytes<'a>, usize) {
+    move |index| Bytes::of(values[index].to_byte_slice())

Review Comment:
   Done in 5a832dd579. The readers now return the plain size: the candidate's `width` for fixed-width values and `4 + len` for byte arrays. `FirstPage::width` is gone and `add` takes the size directly. `Bytes::of` went with it, since nothing else used it. `judge_primitive` takes the width from the candidate and makes no choice if it is somehow missing.



##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -1253,6 +1677,26 @@ mod tests {
         );
     }
 
+    /// The fields of a null struct are not part of the column chunk either.
+    #[test]
+    fn values_under_a_null_struct_are_not_counted() {

Review Comment:
   I kept `values_under_a_null_struct_are_not_counted`, for the reason viirya gives: it is small and pins the struct-null check on its own. I did drop the large-list and fixed-size-list half of `reads_every_leaf_type`, since `ll` and `fl` in the sliced test cover those types with nulls and a slice on top. That is in 5a832dd579. I read the code to check this and did not run a mutation.



##########
native/core/src/execution/operators/iceberg_dictionary.rs:
##########
@@ -254,139 +343,234 @@ fn collect_leaves(data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>)
                 descend(Step::Key, fields[0].data_type(), leaf, leaves);
                 descend(Step::Value, fields[1].data_type(), leaf, leaves);
             }
-            _ => leaves.push(leaf.clone()),
+            _ => leaves.push((leaf.clone(), data_type.clone())),
         },
-        _ => leaves.push(leaf.clone()),
+        _ => leaves.push((leaf.clone(), data_type.clone())),
     }
 }
 
-fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<Leaf>) {
+fn descend(step: Step, data_type: &DataType, leaf: &mut Leaf, leaves: &mut Vec<(Leaf, DataType)>) {
     leaf.steps.push(step);
     collect_leaves(data_type, leaf, leaves);
     leaf.steps.pop();
 }
 
-/// `(row, index)` pairs, one per entry of an array that the column chunk stores: its row of the
-/// batch, and its index into the array.
-type Entries<'a> = Box<dyn Iterator<Item = (u32, usize)> + 'a>;
-
 impl Leaf {
-    /// The leaf's array in `batch`, with the entries of it that lie under the rows `top` yields and
-    /// whose ancestors are all present, in the order the column chunk stores them. Nothing is
-    /// expanded ahead: each entry is produced when the page asks for it. `None` when `batch` does
-    /// not have the shape the schema promised.
-    fn entries<'a>(
-        &self,
-        batch: &'a RecordBatch,
-        top: Entries<'a>,
-    ) -> Option<(&'a dyn Array, Entries<'a>)> {
+    /// The arrays of `batch` the way to the leaf passes through, or `None` when `batch` does not
+    /// have the shape the schema promised.
+    fn path<'a>(&self, batch: &'a RecordBatch) -> Option<Path<'a>> {
         let mut array = batch.columns().get(self.column)?.as_ref();
-        let mut entries = top;
+        let mut levels = Vec::with_capacity(self.steps.len());
         for step in &self.steps {
-            let present = present(array, entries);
-            (array, entries) = match (step, array.data_type()) {
+            let (children, next) = match (step, array.data_type()) {
                 (Step::Field(field), DataType::Struct(_)) => {
-                    (array.as_struct().columns().get(*field)?.as_ref(), present)
+                    (Children::Same, array.as_struct().columns().get(*field)?)
                 }
                 (Step::Element, DataType::List(_)) => {
                     let list = array.as_list::<i32>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
+                    (Children::Offsets(list.value_offsets()), list.values())
                 }
                 (Step::Element, DataType::LargeList(_)) => {
                     let list = array.as_list::<i64>();
-                    (
-                        list.values().as_ref(),
-                        children(present, list.value_offsets()),
-                    )
-                }
-                (Step::Element, DataType::FixedSizeList(_, size)) => {
-                    let size = *size as usize;
-                    let elements: Entries<'a> = Box::new(present.flat_map(move |(row, index)| {
-                        (index * size..(index + 1) * size).map(move |element| (row, element))
-                    }));
-                    (array.as_fixed_size_list().values().as_ref(), elements)
+                    (Children::LargeOffsets(list.value_offsets()), list.values())
                 }
+                (Step::Element, DataType::FixedSizeList(_, size)) => (
+                    Children::Fixed(*size as usize),
+                    array.as_fixed_size_list().values(),
+                ),
                 (Step::Key, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (map.keys().as_ref(), children(present, map.value_offsets()))
+                    (Children::Offsets(map.value_offsets()), map.keys())
                 }
                 (Step::Value, DataType::Map(_, _)) => {
                     let map = array.as_map();
-                    (
-                        map.values().as_ref(),
-                        children(present, map.value_offsets()),
-                    )
+                    (Children::Offsets(map.value_offsets()), map.values())
                 }
                 _ => return None,
             };
+            // A null buffer with no nulls in it is as good as none, and a struct without nulls
+            // leads every entry straight to its field's, so neither needs a level.
+            let nulls = present_nulls(array);
+            if nulls.is_some() || !matches!(children, Children::Same) {
+                levels.push(Level { nulls, children });
+            }
+            array = next.as_ref();
         }
-        Some((array, entries))
+        Some(Path {
+            levels,
+            leaf: array,
+        })
     }
 }
 
-/// The entries whose value in `array` is not null.
-fn present<'a>(array: &'a dyn Array, entries: Entries<'a>) -> Entries<'a> {
-    match array.nulls() {
-        Some(nulls) => Box::new(entries.filter(move |&(_, index)| nulls.is_valid(index))),
-        None => entries,
-    }
+/// The arrays the way from a batch's column down to one leaf column passes through.
+struct Path<'a> {
+    /// One for each step, from the batch's column down.
+    levels: Vec<Level<'a>>,
+    /// The leaf column's array.
+    leaf: &'a dyn Array,
 }
 
-/// The entries of the children of every list or map entry in `entries`.
-fn children<'a, O: OffsetSizeTrait>(entries: Entries<'a>, offsets: &'a [O]) -> Entries<'a> {
-    Box::new(entries.flat_map(move |(row, index)| {
-        (offsets[index].as_usize()..offsets[index + 1].as_usize()).map(move |child| (row, child))
-    }))
+/// An array on the way to a leaf, and how its entries lead into the next one.
+struct Level<'a> {
+    /// A null entry has nothing under it in the column chunk, even where a null list spans child
+    /// values.
+    nulls: Option<&'a NullBuffer>,
+    children: Children<'a>,
 }
 
-type ValueBytes<'a> = Box<dyn Fn(usize) -> &'a [u8] + 'a>;
+/// The entries of the next array that lie under entry `i` of a level.
+#[derive(Clone, Copy)]
+enum Children<'a> {
+    /// A struct's: entry `i` of its field.
+    Same,
+    /// A list's or a map's: entries `offsets[i]` up to `offsets[i + 1]` of its elements, keys or
+    /// values.
+    Offsets(&'a [i32]),
+    /// A large list's.
+    LargeOffsets(&'a [i64]),
+    /// A fixed-size list's: the `size` elements from `i * size`.
+    Fixed(usize),
+}
 
-/// The bytes that tell `array`'s values apart: a fixed-width value's native bytes, or a string's or
-/// binary's content. `None` for a type an Iceberg schema cannot produce.
-fn value_bytes<'a>(array: &'a dyn Array) -> Option<ValueBytes<'a>> {
-    let bytes: ValueBytes<'a> = downcast_primitive_array!(
-        array => Box::new(move |i| array.values()[i].to_byte_slice()),
-        DataType::Utf8 => {
-            let array = array.as_string::<i32>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::LargeUtf8 => {
-            let array = array.as_string::<i64>();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Utf8View => {
-            let array = array.as_string_view();
-            Box::new(move |i| array.value(i).as_bytes())
-        }
-        DataType::Binary => {
-            let array = array.as_binary::<i32>();
-            Box::new(move |i| array.value(i))
-        }
-        DataType::LargeBinary => {
-            let array = array.as_binary::<i64>();
-            Box::new(move |i| array.value(i))
+impl Children<'_> {
+    /// Where the entries under entry `index` start in the next array. Those under the entries
+    /// before `index` end there too, so this also holds for one past the last entry.
+    fn start(self, index: usize) -> usize {
+        match self {
+            Children::Same => index,
+            Children::Offsets(offsets) => offsets[index] as usize,
+            Children::LargeOffsets(offsets) => offsets[index] as usize,
+            Children::Fixed(size) => index * size,
         }
-        DataType::BinaryView => {
-            let array = array.as_binary_view();
-            Box::new(move |i| array.value(i))
+    }
+}
+
+impl Path<'_> {
+    /// How many entries of the leaf array lie under the batch's first `rows` rows, null or not.
+    fn entries(&self, rows: usize) -> usize {
+        let (start, end) = self.levels.iter().fold((0, rows), |(start, end), level| {
+            (level.children.start(start), level.children.start(end))
+        });
+        end - start
+    }
+
+    /// Calls `f` with the leaf index of every entry under the batch's row `row` whose ancestors
+    /// are all present, in the order the column chunk stores them, until `f` returns `false`.
+    /// Returns whether every entry was visited. Nothing is expanded ahead, so a page that ends
+    /// partway through a batch reads no further.
+    fn visit(&self, row: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+        // A leaf with no levels above it has one entry per row: the row itself.
+        if self.levels.is_empty() {
+            return f(row);
         }
-        _ => return None,
-    );
-    Some(bytes)
+        visit(&self.levels, row, f)
+    }
+}
+
+/// `array`'s nulls, or `None` when it has none.
+fn present_nulls(array: &dyn Array) -> Option<&NullBuffer> {
+    array.nulls().filter(|nulls| nulls.null_count() > 0)
+}
+
+fn visit(levels: &[Level], index: usize, f: &mut impl FnMut(usize) -> bool) -> bool {
+    let Some((level, below)) = levels.split_first() else {
+        return f(index);
+    };

Review Comment:
   Good catch. `Path::visit` now calls `split_first` itself and hands `level` and `below` to `visit`, which no longer checks for an empty slice. Done in c2f688c4a8.



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org