You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/05/23 01:19:24 UTC

(datafusion) branch gh-readonly-queue/main/pr-22182-4a41173ba3df9b5d47638599c819a1e6e46ad92b created (now ba240b243f)

This is an automated email from the ASF dual-hosted git repository.

github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-22182-4a41173ba3df9b5d47638599c819a1e6e46ad92b
in repository https://gitbox.apache.org/repos/asf/datafusion.git


      at ba240b243f perf: Optimize `overlay` with new string builder (#22182)

This branch includes the following new commits:

     new ba240b243f perf: Optimize `overlay` with new string builder (#22182)

The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails.  The revisions
listed as "add" were already present in the repository and have only
been added to this reference.



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


(datafusion) 01/01: perf: Optimize `overlay` with new string builder (#22182)

Posted by gi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.

github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-22182-4a41173ba3df9b5d47638599c819a1e6e46ad92b
in repository https://gitbox.apache.org/repos/asf/datafusion.git

commit ba240b243fd942107733ccaff5b2221c342bd5ed
Author: Neil Conway <ne...@gmail.com>
AuthorDate: Fri May 22 21:19:04 2026 -0400

    perf: Optimize `overlay` with new string builder (#22182)
    
    ## Which issue does this PR close?
    
    - Closes #22181.
    
    ## Rationale for this change
    
    This PR optimizes `overlay` by switching to the new bulk-NULL string
    builders, and also taking advantage of `append_with` to avoid copying
    into an intermediate `String`. Along the way, we also optimize character
    counting for Unicode inputs, reducing the number of times we need to
    walk the input string.
    
    Benchmarks (Arm64):
    
    StringArray
    
      - all_utf8: 3.6 ms → 1.85 ms (-48.6%)
      - ascii: 319.8 µs → 134.9 µs (-57.8%)
      - high_nulls: 400.7 µs → 75.1 µs (-81.3%)
      - low_nulls: 2.0 ms → 1.03 ms (-48.3%)
      - no_for: 2.1 ms → 1.12 ms (-46.8%)
      - no_nulls: 2.0 ms → 1.05 ms (-48.4%)
    
    StringViewArray
    
      - all_utf8: 3.6 ms → 1.86 ms (-48.4%)
      - ascii: 313.8 µs → 133.8 µs (-57.4%)
      - low_nulls: 2.0 ms → 1.05 ms (-47.4%)
      - no_for: 2.1 ms → 1.12 ms (-46.7%)
    
    ## What changes are included in this PR?
    
    * Switch to `BulkNullStringArrayBuilder` to build the result set, and
    `NullBuffer::union_many` to compute NULLs in bulk
    * Use `append_with` to avoid an intermediate string copy
    * For Unicode inputs, replace three `char_indices` walks with a single
    string traversal
    * More comprehensive benchmark coverage
    * Fix a misleading/inaccurate error message
    
    ## Are these changes tested?
    
    Yes, covered by existing tests.
    
    ## Are there any user-facing changes?
    
    No.
---
 datafusion/functions/benches/overlay.rs          | 158 +++++++++++--
 datafusion/functions/src/core/overlay.rs         | 286 ++++++++++++++---------
 datafusion/sqllogictest/test_files/functions.slt |   4 +-
 3 files changed, 318 insertions(+), 130 deletions(-)

diff --git a/datafusion/functions/benches/overlay.rs b/datafusion/functions/benches/overlay.rs
index 4554cc435e..0b7fff5989 100644
--- a/datafusion/functions/benches/overlay.rs
+++ b/datafusion/functions/benches/overlay.rs
@@ -21,24 +21,39 @@ use arrow::datatypes::{DataType, Field};
 use criterion::{Criterion, criterion_group, criterion_main};
 use datafusion_common::ScalarValue;
 use datafusion_common::config::ConfigOptions;
-use datafusion_expr::{ColumnarValue, ScalarFunctionArgs};
+use datafusion_expr::{ColumnarValue, ScalarFunctionArgs, ScalarUDF};
 use helper::gen_string_array;
 use std::hint::black_box;
 use std::sync::Arc;
 
-fn criterion_benchmark(c: &mut Criterion) {
-    const N_ROWS: usize = 8192;
+#[expect(clippy::too_many_arguments)]
+fn bench_overlay(
+    c: &mut Criterion,
+    name: &str,
+    overlay: &ScalarUDF,
+    n_rows: usize,
+    null_density: f32,
+    utf8_density: f32,
+    is_string_view: bool,
+    with_for: bool,
+) {
     const STR_LEN: usize = 128;
 
-    let overlay = datafusion_functions::core::overlay();
-    let config_options = Arc::new(ConfigOptions::default());
-
-    let mut args = gen_string_array(N_ROWS, STR_LEN, 0.1, 0.5, false);
-    args.push(ColumnarValue::Scalar(ScalarValue::Utf8(Some(
-        "DataFusion".to_string(),
-    ))));
+    let mut args =
+        gen_string_array(n_rows, STR_LEN, null_density, utf8_density, is_string_view);
+    // The substring scalar's type must match the string column's type (the
+    // function dispatches per-type without coercion).
+    let substr = "DataFusion".to_string();
+    let substr_scalar = if is_string_view {
+        ScalarValue::Utf8View(Some(substr))
+    } else {
+        ScalarValue::Utf8(Some(substr))
+    };
+    args.push(ColumnarValue::Scalar(substr_scalar));
     args.push(ColumnarValue::Scalar(ScalarValue::Int64(Some(32))));
-    args.push(ColumnarValue::Scalar(ScalarValue::Int64(Some(8))));
+    if with_for {
+        args.push(ColumnarValue::Scalar(ScalarValue::Int64(Some(8))));
+    }
 
     let arg_fields = args
         .iter()
@@ -46,15 +61,16 @@ fn criterion_benchmark(c: &mut Criterion) {
         .map(|(idx, arg)| Field::new(format!("arg_{idx}"), arg.data_type(), true).into())
         .collect::<Vec<_>>();
     let return_field = Arc::new(Field::new("f", DataType::Utf8, true));
+    let config_options = Arc::new(ConfigOptions::default());
 
-    c.bench_function("overlay_StringArray_utf8_scalar_args", |b| {
+    c.bench_function(name, |b| {
         b.iter(|| {
             black_box(
                 overlay
                     .invoke_with_args(ScalarFunctionArgs {
                         args: args.clone(),
                         arg_fields: arg_fields.clone(),
-                        number_rows: N_ROWS,
+                        number_rows: n_rows,
                         return_field: Arc::clone(&return_field),
                         config_options: Arc::clone(&config_options),
                     })
@@ -64,5 +80,121 @@ fn criterion_benchmark(c: &mut Criterion) {
     });
 }
 
+fn criterion_benchmark(c: &mut Criterion) {
+    const N_ROWS: usize = 8192;
+    const MIXED_UTF8: f32 = 0.5;
+    let overlay = datafusion_functions::core::overlay();
+
+    // Null-density variants on StringArray (mixed ASCII/UTF-8, 4-arg form).
+    bench_overlay(
+        c,
+        "overlay_StringArray_low_nulls",
+        &overlay,
+        N_ROWS,
+        0.1,
+        MIXED_UTF8,
+        false,
+        true,
+    );
+    bench_overlay(
+        c,
+        "overlay_StringArray_high_nulls",
+        &overlay,
+        N_ROWS,
+        0.9,
+        MIXED_UTF8,
+        false,
+        true,
+    );
+    bench_overlay(
+        c,
+        "overlay_StringArray_no_nulls",
+        &overlay,
+        N_ROWS,
+        0.0,
+        MIXED_UTF8,
+        false,
+        true,
+    );
+
+    // Content variants on StringArray (no nulls, 4-arg form). Pair against
+    // `overlay_StringArray_no_nulls` to isolate the impact of UTF-8 density.
+    bench_overlay(
+        c,
+        "overlay_StringArray_ascii",
+        &overlay,
+        N_ROWS,
+        0.0,
+        0.0,
+        false,
+        true,
+    );
+    bench_overlay(
+        c,
+        "overlay_StringArray_all_utf8",
+        &overlay,
+        N_ROWS,
+        0.0,
+        1.0,
+        false,
+        true,
+    );
+
+    // 3-arg form (no FOR clause), where the replace length is derived from
+    // the substring per row.
+    bench_overlay(
+        c,
+        "overlay_StringArray_no_for",
+        &overlay,
+        N_ROWS,
+        0.0,
+        MIXED_UTF8,
+        false,
+        false,
+    );
+
+    // StringViewArray counterparts.
+    bench_overlay(
+        c,
+        "overlay_StringViewArray_low_nulls",
+        &overlay,
+        N_ROWS,
+        0.1,
+        MIXED_UTF8,
+        true,
+        true,
+    );
+    bench_overlay(
+        c,
+        "overlay_StringViewArray_ascii",
+        &overlay,
+        N_ROWS,
+        0.0,
+        0.0,
+        true,
+        true,
+    );
+    bench_overlay(
+        c,
+        "overlay_StringViewArray_all_utf8",
+        &overlay,
+        N_ROWS,
+        0.0,
+        1.0,
+        true,
+        true,
+    );
+    bench_overlay(
+        c,
+        "overlay_StringViewArray_no_for",
+        &overlay,
+        N_ROWS,
+        0.0,
+        MIXED_UTF8,
+        true,
+        false,
+    );
+}
+
 criterion_group!(benches, criterion_benchmark);
 criterion_main!(benches);
diff --git a/datafusion/functions/src/core/overlay.rs b/datafusion/functions/src/core/overlay.rs
index 2d99af9e78..c1f3353a8f 100644
--- a/datafusion/functions/src/core/overlay.rs
+++ b/datafusion/functions/src/core/overlay.rs
@@ -15,11 +15,16 @@
 // specific language governing permissions and limitations
 // under the License.
 
-use std::sync::Arc;
-
-use arrow::array::{ArrayRef, GenericStringArray, OffsetSizeTrait};
+use arrow::array::{
+    Array, ArrayRef, GenericStringArray, Int64Array, OffsetSizeTrait, StringArrayType,
+    StringViewArray,
+};
+use arrow::buffer::NullBuffer;
 use arrow::datatypes::DataType;
 
+use crate::strings::{
+    BulkNullStringArrayBuilder, GenericStringArrayBuilder, StringWriter,
+};
 use crate::utils::{make_scalar_function, utf8_to_str_type};
 use datafusion_common::cast::{
     as_generic_string_array, as_int64_array, as_string_view_array,
@@ -112,106 +117,79 @@ impl ScalarUDFImpl for OverlayFunc {
     }
 }
 
-/// Converts a 0-based character index into a byte index suitable for UTF-8
-/// slicing.
-fn byte_index_for_char(string: &str, char_idx: usize, is_ascii: bool) -> usize {
-    if is_ascii {
-        char_idx.min(string.len())
-    } else {
-        string
-            .char_indices()
-            .nth(char_idx)
-            .map_or(string.len(), |(byte_idx, _)| byte_idx)
+/// Computes the byte ranges of `string` to keep around the replaced span: the
+/// prefix is `string[..prefix_end]` and the suffix is `string[suffix_start..]`.
+///
+/// `start_pos` is a 1-based character position; the caller must ensure it is
+/// `>= 1`. `replace_len` is the number of characters of `string` to replace,
+/// and may be negative (in which case `suffix_start <= prefix_end` and the
+/// result re-emits part of the original string).
+///
+/// Matches PostgreSQL semantics for codepoint indices past the end of
+/// `string`: `prefix_end` and `suffix_start` clamp to `string.len()`.
+fn overlay_bounds(string: &str, start_pos: i64, replace_len: i64) -> (usize, usize) {
+    let start_char_idx = start_pos - 1;
+    let end_char_idx = start_char_idx.saturating_add(replace_len);
+
+    if string.is_ascii() {
+        // ASCII fast path: byte index == codepoint index.
+        let len = string.len() as i64;
+        let prefix_end = start_char_idx.clamp(0, len) as usize;
+        let suffix_start = end_char_idx.clamp(0, len) as usize;
+        return (prefix_end, suffix_start);
+    }
+
+    let prefix_target = usize::try_from(start_char_idx).unwrap_or(usize::MAX);
+    let suffix_target = usize::try_from(end_char_idx.max(0)).unwrap_or(usize::MAX);
+    let target_max = prefix_target.max(suffix_target);
+
+    // Single forward pass over codepoint boundaries records both targets.
+    // Either target falls through to `string.len()` if past the codepoint
+    // count.
+    let mut prefix_byte = string.len();
+    let mut suffix_byte = string.len();
+    for (count, (byte_idx, _)) in string.char_indices().enumerate() {
+        if count == prefix_target {
+            prefix_byte = byte_idx;
+        }
+        if count == suffix_target {
+            suffix_byte = byte_idx;
+        }
+        if count == target_max {
+            break;
+        }
     }
+    (prefix_byte, suffix_byte)
 }
 
-/// Builds the OVERLAY result for a single (non-null) row.
-///
-/// `start_pos` is a 1-based character position; `replace_len` is the number
-/// of characters of `string` to replace with `characters`.
-fn overlay_one(
+/// Appends the overlay result for one non-null row into `builder`.
+#[inline]
+fn apply_overlay<B: BulkNullStringArrayBuilder>(
     string: &str,
     characters: &str,
     start_pos: i64,
     replace_len: i64,
-) -> Result<String> {
+    builder: &mut B,
+) -> Result<()> {
     if start_pos < 1 {
-        return exec_err!("negative substring length not allowed");
+        return exec_err!("overlay start position must be at least 1: {start_pos}");
     }
+    let (prefix_end, suffix_start) = overlay_bounds(string, start_pos, replace_len);
+    builder.append_with(|w| {
+        w.write_str(&string[..prefix_end]);
+        w.write_str(characters);
+        w.write_str(&string[suffix_start..]);
+    });
+    Ok(())
+}
 
-    let is_ascii = string.is_ascii();
-    let string_char_len = if is_ascii {
-        string.len() as i64
+#[inline]
+fn char_count(characters: &str) -> i64 {
+    if characters.is_ascii() {
+        characters.len() as i64
     } else {
-        string.chars().count() as i64
-    };
-
-    // Convert SQL's 1-based character position into 0-based character indexes.
-    // `start_char_idx` is the first replaced character; `end_char_idx` is the
-    // first character after the replaced span.
-    //
-    // No upper-bound check on `start_char_idx`: when it exceeds `string_char_len`
-    // we want the whole string as the prefix (PostgreSQL-compatible "insert past
-    // end" semantics).
-    let start_char_idx = start_pos - 1;
-    let end_char_idx = start_char_idx.saturating_add(replace_len);
-
-    let prefix_char_idx = usize::try_from(start_char_idx).unwrap_or(usize::MAX);
-    let prefix_end_byte = byte_index_for_char(string, prefix_char_idx, is_ascii);
-
-    let mut res = String::with_capacity(string.len() + characters.len());
-    res.push_str(&string[..prefix_end_byte]);
-    res.push_str(characters);
-
-    if end_char_idx < string_char_len {
-        let suffix_char_idx = usize::try_from(end_char_idx.max(0)).unwrap_or(usize::MAX);
-        let suffix_start_byte = byte_index_for_char(string, suffix_char_idx, is_ascii);
-        res.push_str(&string[suffix_start_byte..]);
+        characters.chars().count() as i64
     }
-    Ok(res)
-}
-
-macro_rules! process_overlay {
-    // Three argument case
-    ($string_array:expr, $characters_array:expr, $pos_array:expr) => {{
-        $string_array
-            .iter()
-            .zip($characters_array.iter())
-            .zip($pos_array.iter())
-            .map(|((string, characters), start_pos)| {
-                match (string, characters, start_pos) {
-                    (Some(string), Some(characters), Some(start_pos)) => {
-                        let replace_len = characters.chars().count() as i64;
-                        overlay_one(string, characters, start_pos, replace_len).map(Some)
-                    }
-                    _ => Ok(None),
-                }
-            })
-            .collect::<Result<GenericStringArray<T>>>()
-    }};
-
-    // Four argument case
-    ($string_array:expr, $characters_array:expr, $pos_array:expr, $len_array:expr) => {{
-        $string_array
-            .iter()
-            .zip($characters_array.iter())
-            .zip($pos_array.iter())
-            .zip($len_array.iter())
-            .map(|(((string, characters), start_pos), replace_len)| {
-                match (string, characters, start_pos, replace_len) {
-                    (
-                        Some(string),
-                        Some(characters),
-                        Some(start_pos),
-                        Some(replace_len),
-                    ) => {
-                        overlay_one(string, characters, start_pos, replace_len).map(Some)
-                    }
-                    _ => Ok(None),
-                }
-            })
-            .collect::<Result<GenericStringArray<T>>>()
-    }};
 }
 
 /// `OVERLAY(string PLACING substring FROM start [FOR count])`
@@ -232,44 +210,122 @@ fn overlay<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
             args.len()
         );
     }
+    let pos_array = as_int64_array(&args[2])?;
+    let len_array = if args.len() == 4 {
+        Some(as_int64_array(&args[3])?)
+    } else {
+        None
+    };
+
     if args[0].data_type() == &DataType::Utf8View {
-        string_view_overlay::<T>(args)
+        let string_array = as_string_view_array(&args[0])?;
+        let characters_array = as_string_view_array(&args[1])?;
+        let data_capacity = visible_view_bytes(string_array)
+            .saturating_add(visible_view_bytes(characters_array));
+        let builder = GenericStringArrayBuilder::<i32>::with_capacity(
+            string_array.len(),
+            data_capacity,
+        );
+        overlay_inner(
+            string_array,
+            characters_array,
+            pos_array,
+            len_array,
+            builder,
+        )
     } else {
-        string_overlay::<T>(args)
+        let string_array = as_generic_string_array::<T>(&args[0])?;
+        let characters_array = as_generic_string_array::<T>(&args[1])?;
+        let data_capacity = visible_offset_bytes(string_array)
+            .saturating_add(visible_offset_bytes(characters_array));
+        let builder = GenericStringArrayBuilder::<T>::with_capacity(
+            string_array.len(),
+            data_capacity,
+        );
+        overlay_inner(
+            string_array,
+            characters_array,
+            pos_array,
+            len_array,
+            builder,
+        )
     }
 }
 
-fn string_overlay<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
-    let string_array = as_generic_string_array::<T>(&args[0])?;
-    let characters_array = as_generic_string_array::<T>(&args[1])?;
-    let pos_array = as_int64_array(&args[2])?;
+/// Drives the per-row OVERLAY computation. A null in any input array
+/// produces a null output.
+fn overlay_inner<'a, V, B>(
+    string_array: V,
+    characters_array: V,
+    pos_array: &Int64Array,
+    len_array: Option<&Int64Array>,
+    mut builder: B,
+) -> Result<ArrayRef>
+where
+    V: StringArrayType<'a, Item = &'a str> + Copy,
+    B: BulkNullStringArrayBuilder,
+{
+    let len = string_array.len();
+    let nulls = NullBuffer::union_many([
+        string_array.nulls(),
+        characters_array.nulls(),
+        pos_array.nulls(),
+        len_array.and_then(|a| a.nulls()),
+    ]);
 
-    let result = if args.len() == 4 {
-        let len_array = as_int64_array(&args[3])?;
-        process_overlay!(string_array, characters_array, pos_array, len_array)?
+    if let Some(nulls_ref) = nulls.as_ref() {
+        for i in 0..len {
+            if nulls_ref.is_null(i) {
+                builder.append_placeholder();
+                continue;
+            }
+            // SAFETY: `i < len`, and null bitmap check implies not-null
+            let string = unsafe { string_array.value_unchecked(i) };
+            let characters = unsafe { characters_array.value_unchecked(i) };
+            let start_pos = unsafe { pos_array.value_unchecked(i) };
+            let replace_len = match len_array {
+                Some(arr) => unsafe { arr.value_unchecked(i) },
+                None => char_count(characters),
+            };
+            apply_overlay(string, characters, start_pos, replace_len, &mut builder)?;
+        }
     } else {
-        process_overlay!(string_array, characters_array, pos_array)?
-    };
-    Ok(Arc::new(result) as ArrayRef)
+        for i in 0..len {
+            // SAFETY: `i < len`, and no null bitmap means no nulls
+            let string = unsafe { string_array.value_unchecked(i) };
+            let characters = unsafe { characters_array.value_unchecked(i) };
+            let start_pos = unsafe { pos_array.value_unchecked(i) };
+            let replace_len = match len_array {
+                Some(arr) => unsafe { arr.value_unchecked(i) },
+                None => char_count(characters),
+            };
+            apply_overlay(string, characters, start_pos, replace_len, &mut builder)?;
+        }
+    }
+    builder.finish(nulls)
 }
 
-fn string_view_overlay<T: OffsetSizeTrait>(args: &[ArrayRef]) -> Result<ArrayRef> {
-    let string_array = as_string_view_array(&args[0])?;
-    let characters_array = as_string_view_array(&args[1])?;
-    let pos_array = as_int64_array(&args[2])?;
+/// Bytes referenced by the visible window of `array`, computed from the
+/// per-view lengths.
+fn visible_view_bytes(array: &StringViewArray) -> usize {
+    array.lengths().map(|l| l as usize).sum()
+}
 
-    let result = if args.len() == 4 {
-        let len_array = as_int64_array(&args[3])?;
-        process_overlay!(string_array, characters_array, pos_array, len_array)?
-    } else {
-        process_overlay!(string_array, characters_array, pos_array)?
-    };
-    Ok(Arc::new(result) as ArrayRef)
+/// Bytes referenced by the visible window of `array`, derived from the offset
+/// buffer.
+fn visible_offset_bytes<T: OffsetSizeTrait>(array: &GenericStringArray<T>) -> usize {
+    let offsets = array.value_offsets();
+    // `value_offsets()` always has `array.len() + 1` entries (≥1).
+    let first = offsets.first().copied().unwrap_or_default();
+    let last = offsets.last().copied().unwrap_or_default();
+    last.as_usize() - first.as_usize()
 }
 
 #[cfg(test)]
 mod tests {
-    use arrow::array::{Int64Array, StringArray};
+    use std::sync::Arc;
+
+    use arrow::array::StringArray;
 
     use super::*;
 
diff --git a/datafusion/sqllogictest/test_files/functions.slt b/datafusion/sqllogictest/test_files/functions.slt
index ea3cd6eb4b..2b393f1a26 100644
--- a/datafusion/sqllogictest/test_files/functions.slt
+++ b/datafusion/sqllogictest/test_files/functions.slt
@@ -805,10 +805,10 @@ SELECT overlay('abc' placing 'X' from 5 for 1)
 abcX
 
 # Start positions must be positive.
-statement error negative substring length not allowed
+statement error overlay start position must be at least 1: 0
 SELECT overlay('abc' placing 'X' from 0 for 1)
 
-statement error negative substring length not allowed
+statement error overlay start position must be at least 1: -1
 SELECT overlay('abc' placing 'X' from -1 for 1)
 
 # Negative count keeps the suffix from before the start position.


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