Use code points instead of grapheme clusters for string functions by Dandandan · Pull Request #3054 · apache/datafusion

Dandandan · 2022-08-06T12:48:48Z

Which issue does this PR close?

Rationale for this change

Matching PostgreSQL, Spark and improve performance. Overall simplification.

What changes are included in this PR?

Moves most functions, except rpad, lpad and translate to use code points rather than grapheme clusters.
Also code simplification & avoiding some allocations.

Are there any user-facing changes?

codecov-commenter · 2022-08-06T13:35:43Z

Codecov Report

Merging #3054 (12d7366) into master (a8ed874) will increase coverage by 0.03%.
The diff coverage is 79.31%.

@@            Coverage Diff             @@
##           master    #3054      +/-   ##
==========================================
+ Coverage   85.84%   85.88%   +0.03%     
==========================================
  Files         289      289              
  Lines       51862    51844      -18     
==========================================
+ Hits        44520    44525       +5     
+ Misses       7342     7319      -23

Impacted Files	Coverage Δ
...atafusion/physical-expr/src/unicode_expressions.rs	`77.45% <76.92%> (+4.35%)`	⬆️
datafusion/core/tests/sql/unicode.rs	`100.00% <100.00%> (ø)`
datafusion/physical-expr/src/functions.rs	`92.72% <100.00%> (ø)`
datafusion/expr/src/logical_plan/plan.rs	`77.43% <0.00%> (-0.18%)`	⬇️
datafusion/core/tests/sql/timestamp.rs	`100.00% <0.00%> (ø)`
datafusion/expr/src/window_frame.rs	`93.27% <0.00%> (+0.84%)`	⬆️

📣 Codecov can now indicate which changes are the most critical in Pull Requests. Learn more

alamb · 2022-08-06T14:37:55Z

cc @ovr

WIP

Dandandan · 2022-08-07T12:44:09Z

@alamb @andygrove this is reviewable now.

andygrove · 2022-08-07T13:10:15Z

LGTM. I assume there should be a documentation update as well as part of this PR? Perhaps the rustdoc for fn character_length should explain how this is now implemented?

alamb

Looks like a nice simplification and improvement to me ❤️ Thank you @Dandandan

cc @ovr who I think contributed the original implementation

ovr · 2022-08-08T12:47:52Z

cc @ovr who I think contributed the original implementation

LGTM, but I am not an original author 😄

Dandandan · 2022-08-08T12:48:51Z

I think this was @seddonm1

andygrove

LGTM. Thanks @Dandandan

ursabot · 2022-08-08T13:11:48Z

Benchmark runs are scheduled for baseline = a4fa44f and contender = 88f6548. 88f6548 is a master commit associated with this PR. Results will be available as each benchmark for each run completes.
Conbench compare runs links:
[Skipped ⚠️ Benchmarking of arrow-datafusion-commits is not supported on ec2-t3-xlarge-us-east-2] ec2-t3-xlarge-us-east-2
[Skipped ⚠️ Benchmarking of arrow-datafusion-commits is not supported on test-mac-arm] test-mac-arm
[Skipped ⚠️ Benchmarking of arrow-datafusion-commits is not supported on ursa-i9-9960x] ursa-i9-9960x
[Skipped ⚠️ Benchmarking of arrow-datafusion-commits is not supported on ursa-thinkcentre-m75q] ursa-thinkcentre-m75q
Buildkite builds:
Supported benchmarks:
ec2-t3-xlarge-us-east-2: Supported benchmark langs: Python, R. Runs only benchmarks with cloud = True
test-mac-arm: Supported benchmark langs: C++, Python, R
ursa-i9-9960x: Supported benchmark langs: Python, R, JavaScript
ursa-thinkcentre-m75q: Supported benchmark langs: C++, Java

devanshu0987 · 2026-01-03T14:25:48Z

Hi @Dandandan OR @alamb, is it possible to share historical reasons as to why lpad and rpad were not covered in this PR?
Should we make this contract change and make it Postgres compatible, or is this a deliberate choice?

For lpad, 3 arguments, (string, length, fill): string is split on Grapheme clusters, and fill is iterated on code points.
While, as you mentioned, Postgres has code point splits for both string and fill equivalents.

datafusion/functions/src/unicode/lpad.rs

let graphemes = string.graphemes(true).collect::<Vec<&str>>();
let fill_chars = fill.chars().collect::<Vec<char>>();

Datafusion result

> select lpad('á', 1);
+--------------------------+
| lpad(Utf8("á"),Int64(1)) |
+--------------------------+
| á                        |
+--------------------------+
1 row(s) fetched. 
Elapsed 0.075 seconds.

Postgres result

select lpad('á', 1);

"lpad"
"a"

alamb · 2026-01-05T13:41:52Z

I don't know that there was any reason not to include lpad / rpad (I don't think it was a deliberate choice)

## Which issue does this PR close? - Closes #21060. ## Rationale for this change `lpad`, `rpad`, and `translate` use grapheme segmentation. This is inconsistent with how these functions behave in Postgres and DuckDB, as well as the SQL standard -- segmentation based on Unicode codepoints is used instead. It also happens that grapheme-based segmentation is significantly more expensive than codepoint-based segmentation. In the case of `lpad` and `rpad`, graphemes and codepoints were used inconsistently: the input string was measured in code points but the fill string was measured in graphemes. #3054 switched to using codepoints for most string-related functions in DataFusion but these three functions still need to be changed. Benchmarks (M4 Max): lpad size=1024: - lpad utf8 [str_len=5, target=20]: 12.4 µs → 12.8 µs, +3.0% - lpad stringview [str_len=5, target=20]: 11.5 µs → 11.7 µs, +1.4% - lpad utf8 [str_len=20, target=50]: 11.3 µs → 11.3 µs, +0.1% - lpad stringview [str_len=20, target=50]: 11.8 µs → 12.0 µs, +1.6% - lpad utf8 unicode [target=20]: 98.4 µs → 24.4 µs, -75.1% - lpad stringview unicode [target=20]: 99.8 µs → 26.0 µs, -74.0% - lpad utf8 scalar [str_len=5, target=20, fill='x']: 8.7 µs → 8.8 µs, +1.0% - lpad stringview scalar [str_len=5, target=20, fill='x']: 10.2 µs → 10.1 µs, -0.1% - lpad utf8 scalar unicode [str_len=5, target=20, fill='é']: 44.7 µs → 10.9 µs, -75.7% - lpad utf8 scalar truncate [str_len=20, target=5, fill='é']: 152.5 µs → 11.7 µs, -92.3% lpad size=4096: - lpad utf8 [str_len=5, target=20]: 55.9 µs → 55.1 µs, -1.4% - lpad stringview [str_len=5, target=20]: 49.2 µs → 50.1 µs, +1.8% - lpad utf8 [str_len=20, target=50]: 46.6 µs → 46.4 µs, -0.5% - lpad stringview [str_len=20, target=50]: 47.5 µs → 48.5 µs, +2.1% - lpad utf8 unicode [target=20]: 401.3 µs → 100.1 µs, -75.0% - lpad stringview unicode [target=20]: 397.7 µs → 104.9 µs, -73.6% - lpad utf8 scalar [str_len=5, target=20, fill='x']: 34.2 µs → 35.0 µs, +2.4% - lpad stringview scalar [str_len=5, target=20, fill='x']: 40.1 µs → 40.4 µs, +0.6% - lpad utf8 scalar unicode [str_len=5, target=20, fill='é']: 178.3 µs → 42.9 µs, -76.0% - lpad utf8 scalar truncate [str_len=20, target=5, fill='é']: 601.3 µs → 46.2 µs, -92.3% rpad size=1024: - rpad utf8 [str_len=5, target=20]: 15.5 µs → 14.4 µs, -7.1% - rpad stringview [str_len=5, target=20]: 13.8 µs → 14.0 µs, +1.7% - rpad utf8 [str_len=20, target=50]: 12.6 µs → 12.7 µs, +1.3% - rpad stringview [str_len=20, target=50]: 13.0 µs → 13.1 µs, +0.7% - rpad utf8 unicode [target=20]: 103.5 µs → 26.0 µs, -74.8% - rpad stringview unicode [target=20]: 101.2 µs → 27.6 µs, -72.7% - rpad utf8 scalar [str_len=5, target=20, fill='x']: 11.4 µs → 10.9 µs, -3.9% - rpad stringview scalar [str_len=5, target=20, fill='x']: 12.2 µs → 12.6 µs, +2.8% - rpad utf8 scalar unicode [str_len=5, target=20, fill='é']: 46.3 µs → 12.4 µs, -73.1% - rpad utf8 scalar truncate [str_len=20, target=5, fill='é']: 155.6 µs → 11.6 µs, -92.4% rpad size=4096: - rpad utf8 [str_len=5, target=20]: 70.1 µs → 61.6 µs, -12.2% - rpad stringview [str_len=5, target=20]: 60.4 µs → 56.8 µs, -6.0% - rpad utf8 [str_len=20, target=50]: 50.6 µs → 51.2 µs, +1.2% - rpad stringview [str_len=20, target=50]: 53.7 µs → 53.3 µs, -0.8% - rpad utf8 unicode [target=20]: 407.1 µs → 104.0 µs, -74.5% - rpad stringview unicode [target=20]: 404.8 µs → 114.5 µs, -71.7% - rpad utf8 scalar [str_len=5, target=20, fill='x']: 47.5 µs → 45.6 µs, -4.0% - rpad stringview scalar [str_len=5, target=20, fill='x']: 56.4 µs → 58.5 µs, +3.6% - rpad utf8 scalar unicode [str_len=5, target=20, fill='é']: 184.1 µs → 48.1 µs, -73.9% - rpad utf8 scalar truncate [str_len=20, target=5, fill='é']: 606.4 µs → 45.6 µs, -92.5% translate size=1024: - array_from_to [str_len=8]: 140.0 µs → 37.6 µs, -73.2% - scalar_from_to [str_len=8]: 9.0 µs → 8.8 µs, -2.7% - array_from_to [str_len=32]: 371.3 µs → 65.6 µs, -82.3% - scalar_from_to [str_len=32]: 19.9 µs → 19.2 µs, -3.6% - array_from_to [str_len=128]: 1249.6 µs → 188.7 µs, -84.9% - scalar_from_to [str_len=128]: 70.2 µs → 64.7 µs, -7.9% - array_from_to [str_len=1024]: 9349.4 µs → 1378.1 µs, -85.3% - scalar_from_to [str_len=1024]: 506.5 µs → 445.8 µs, -12.0% translate size=4096: - array_from_to [str_len=8]: 548.0 µs → 147.1 µs, -73.2% - scalar_from_to [str_len=8]: 33.9 µs → 32.8 µs, -3.1% - array_from_to [str_len=32]: 1457.2 µs → 266.0 µs, -81.7% - scalar_from_to [str_len=32]: 78.0 µs → 75.5 µs, -3.2% - array_from_to [str_len=128]: 4935.0 µs → 791.1 µs, -84.0% - scalar_from_to [str_len=128]: 278.2 µs → 260.7 µs, -6.3% - array_from_to [str_len=1024]: 37496 µs → 5591 µs, -85.1% - scalar_from_to [str_len=1024]: 2058.0 µs → 1770 µs, -14.0% ## What changes are included in this PR? * Switch from grapheme segmentation to codepoint segmentation for `lpad`, `rpad`, and `translate` * Add SLT tests * Refactor a few helper functions * Remove dependency on `unicode_segmentation` crate as it is no longer used ## Are these changes tested? Yes. The new SLT tests were also run against DuckDB and Postgres to confirm the behavior is consistent. ## Are there any user-facing changes? Yes. This PR changes the behavior of `lpad`, `rpad`, and `translate`, although the new behavior is more consistent with the SQL standard and with other SQL implementations.

## Which issue does this PR close? - Closes apache#21060. ## Rationale for this change `lpad`, `rpad`, and `translate` use grapheme segmentation. This is inconsistent with how these functions behave in Postgres and DuckDB, as well as the SQL standard -- segmentation based on Unicode codepoints is used instead. It also happens that grapheme-based segmentation is significantly more expensive than codepoint-based segmentation. In the case of `lpad` and `rpad`, graphemes and codepoints were used inconsistently: the input string was measured in code points but the fill string was measured in graphemes. apache#3054 switched to using codepoints for most string-related functions in DataFusion but these three functions still need to be changed. Benchmarks (M4 Max): lpad size=1024: - lpad utf8 [str_len=5, target=20]: 12.4 µs → 12.8 µs, +3.0% - lpad stringview [str_len=5, target=20]: 11.5 µs → 11.7 µs, +1.4% - lpad utf8 [str_len=20, target=50]: 11.3 µs → 11.3 µs, +0.1% - lpad stringview [str_len=20, target=50]: 11.8 µs → 12.0 µs, +1.6% - lpad utf8 unicode [target=20]: 98.4 µs → 24.4 µs, -75.1% - lpad stringview unicode [target=20]: 99.8 µs → 26.0 µs, -74.0% - lpad utf8 scalar [str_len=5, target=20, fill='x']: 8.7 µs → 8.8 µs, +1.0% - lpad stringview scalar [str_len=5, target=20, fill='x']: 10.2 µs → 10.1 µs, -0.1% - lpad utf8 scalar unicode [str_len=5, target=20, fill='é']: 44.7 µs → 10.9 µs, -75.7% - lpad utf8 scalar truncate [str_len=20, target=5, fill='é']: 152.5 µs → 11.7 µs, -92.3% lpad size=4096: - lpad utf8 [str_len=5, target=20]: 55.9 µs → 55.1 µs, -1.4% - lpad stringview [str_len=5, target=20]: 49.2 µs → 50.1 µs, +1.8% - lpad utf8 [str_len=20, target=50]: 46.6 µs → 46.4 µs, -0.5% - lpad stringview [str_len=20, target=50]: 47.5 µs → 48.5 µs, +2.1% - lpad utf8 unicode [target=20]: 401.3 µs → 100.1 µs, -75.0% - lpad stringview unicode [target=20]: 397.7 µs → 104.9 µs, -73.6% - lpad utf8 scalar [str_len=5, target=20, fill='x']: 34.2 µs → 35.0 µs, +2.4% - lpad stringview scalar [str_len=5, target=20, fill='x']: 40.1 µs → 40.4 µs, +0.6% - lpad utf8 scalar unicode [str_len=5, target=20, fill='é']: 178.3 µs → 42.9 µs, -76.0% - lpad utf8 scalar truncate [str_len=20, target=5, fill='é']: 601.3 µs → 46.2 µs, -92.3% rpad size=1024: - rpad utf8 [str_len=5, target=20]: 15.5 µs → 14.4 µs, -7.1% - rpad stringview [str_len=5, target=20]: 13.8 µs → 14.0 µs, +1.7% - rpad utf8 [str_len=20, target=50]: 12.6 µs → 12.7 µs, +1.3% - rpad stringview [str_len=20, target=50]: 13.0 µs → 13.1 µs, +0.7% - rpad utf8 unicode [target=20]: 103.5 µs → 26.0 µs, -74.8% - rpad stringview unicode [target=20]: 101.2 µs → 27.6 µs, -72.7% - rpad utf8 scalar [str_len=5, target=20, fill='x']: 11.4 µs → 10.9 µs, -3.9% - rpad stringview scalar [str_len=5, target=20, fill='x']: 12.2 µs → 12.6 µs, +2.8% - rpad utf8 scalar unicode [str_len=5, target=20, fill='é']: 46.3 µs → 12.4 µs, -73.1% - rpad utf8 scalar truncate [str_len=20, target=5, fill='é']: 155.6 µs → 11.6 µs, -92.4% rpad size=4096: - rpad utf8 [str_len=5, target=20]: 70.1 µs → 61.6 µs, -12.2% - rpad stringview [str_len=5, target=20]: 60.4 µs → 56.8 µs, -6.0% - rpad utf8 [str_len=20, target=50]: 50.6 µs → 51.2 µs, +1.2% - rpad stringview [str_len=20, target=50]: 53.7 µs → 53.3 µs, -0.8% - rpad utf8 unicode [target=20]: 407.1 µs → 104.0 µs, -74.5% - rpad stringview unicode [target=20]: 404.8 µs → 114.5 µs, -71.7% - rpad utf8 scalar [str_len=5, target=20, fill='x']: 47.5 µs → 45.6 µs, -4.0% - rpad stringview scalar [str_len=5, target=20, fill='x']: 56.4 µs → 58.5 µs, +3.6% - rpad utf8 scalar unicode [str_len=5, target=20, fill='é']: 184.1 µs → 48.1 µs, -73.9% - rpad utf8 scalar truncate [str_len=20, target=5, fill='é']: 606.4 µs → 45.6 µs, -92.5% translate size=1024: - array_from_to [str_len=8]: 140.0 µs → 37.6 µs, -73.2% - scalar_from_to [str_len=8]: 9.0 µs → 8.8 µs, -2.7% - array_from_to [str_len=32]: 371.3 µs → 65.6 µs, -82.3% - scalar_from_to [str_len=32]: 19.9 µs → 19.2 µs, -3.6% - array_from_to [str_len=128]: 1249.6 µs → 188.7 µs, -84.9% - scalar_from_to [str_len=128]: 70.2 µs → 64.7 µs, -7.9% - array_from_to [str_len=1024]: 9349.4 µs → 1378.1 µs, -85.3% - scalar_from_to [str_len=1024]: 506.5 µs → 445.8 µs, -12.0% translate size=4096: - array_from_to [str_len=8]: 548.0 µs → 147.1 µs, -73.2% - scalar_from_to [str_len=8]: 33.9 µs → 32.8 µs, -3.1% - array_from_to [str_len=32]: 1457.2 µs → 266.0 µs, -81.7% - scalar_from_to [str_len=32]: 78.0 µs → 75.5 µs, -3.2% - array_from_to [str_len=128]: 4935.0 µs → 791.1 µs, -84.0% - scalar_from_to [str_len=128]: 278.2 µs → 260.7 µs, -6.3% - array_from_to [str_len=1024]: 37496 µs → 5591 µs, -85.1% - scalar_from_to [str_len=1024]: 2058.0 µs → 1770 µs, -14.0% ## What changes are included in this PR? * Switch from grapheme segmentation to codepoint segmentation for `lpad`, `rpad`, and `translate` * Add SLT tests * Refactor a few helper functions * Remove dependency on `unicode_segmentation` crate as it is no longer used ## Are these changes tested? Yes. The new SLT tests were also run against DuckDB and Postgres to confirm the behavior is consistent. ## Are there any user-facing changes? Yes. This PR changes the behavior of `lpad`, `rpad`, and `translate`, although the new behavior is more consistent with the SQL standard and with other SQL implementations.

Calculate string length based on code points

ac003ec

Dandandan marked this pull request as ready for review August 6, 2022 12:48

github-actions Bot added the physical-expr Changes to the physical-expr crates label Aug 6, 2022

Dandandan changed the title ~~Calculate string length based on code points~~ [WIP] Calculate string length based on code points Aug 6, 2022

Fix test count check

fc56b58

Dandandan changed the title ~~[WIP] Calculate string length based on code points~~ Calculate string length based on code points Aug 6, 2022

Migrate to use chars()

f95bb6b

Dandandan changed the title ~~Calculate string length based on code points~~ Use code points instead of grapheme clusters for string functions Aug 6, 2022

Simplify

0c2b123

Dandandan changed the title ~~Use code points instead of grapheme clusters for string functions~~ [WIP] Use code points instead of grapheme clusters for string functions Aug 6, 2022

WIP

42832a6

Dandandan added 11 commits August 6, 2022 21:16

WIP

fdb072e

WIP

bf30c7a

Fmt

153dce4

WIP

173988b

WIP

bdcd646

WIP

29759aa

WIP

130c8bc

WIP

WIP

9489888

WIP

c689b4e

WIP

577a48f

PostgreSQL compat

d2cd6c5

github-actions Bot added the core Core DataFusion crate label Aug 7, 2022

Dandandan added 2 commits August 7, 2022 12:08

Fixes

b8016c2

Test added

bf9b621

Dandandan changed the title ~~[WIP] Use code points instead of grapheme clusters for string functions~~ Use code points instead of grapheme clusters for string functions Aug 7, 2022

Dandandan added 2 commits August 7, 2022 12:31

Clippy

1272128

WIP

a012f8e

Dandandan added 2 commits August 7, 2022 13:20

Fix

4cf0764

Remove integration test

db6e2af

Dandandan added the performance Make DataFusion faster label Aug 7, 2022

Add docs

12d7366

alamb approved these changes Aug 8, 2022

View reviewed changes

andygrove approved these changes Aug 8, 2022

View reviewed changes

andygrove merged commit 88f6548 into apache:master Aug 8, 2022

This was referenced Mar 19, 2026

lpad, rpad, translate should use codepoints, not graphemes #21060

Closed

perf: Optimize lpad(), rpad() for scalar args #20657

Merged

neilconway mentioned this pull request Apr 6, 2026

fix: Use codepoints in lpad, rpad, translate #21405

Merged

Navigation Menu

Repository navigation

Use code points instead of grapheme clusters for string functions - #3054

Use code points instead of grapheme clusters for string functions#3054
andygrove merged 23 commits into
apache:masterfrom
Dandandan:character_length

Dandandan commented Aug 6, 2022 •

edited

Loading

Uh oh!

codecov-commenter commented Aug 6, 2022 •

edited

Loading

Uh oh!

alamb commented Aug 6, 2022

Uh oh!

Dandandan commented Aug 7, 2022

Uh oh!

andygrove commented Aug 7, 2022

Uh oh!

alamb left a comment

Uh oh!

ovr commented Aug 8, 2022

Uh oh!

Dandandan commented Aug 8, 2022

Uh oh!

andygrove left a comment

Uh oh!

ursabot commented Aug 8, 2022

Uh oh!

devanshu0987 commented Jan 3, 2026 •

edited

Loading

Uh oh!

alamb commented Jan 5, 2026

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

Conversation

Dandandan commented Aug 6, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Which issue does this PR close?

Rationale for this change

What changes are included in this PR?

Are there any user-facing changes?

Uh oh!

codecov-commenter commented Aug 6, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

alamb commented Aug 6, 2022

Uh oh!

Dandandan commented Aug 7, 2022

Uh oh!

andygrove commented Aug 7, 2022

Uh oh!

alamb left a comment

Choose a reason for hiding this comment

Uh oh!

ovr commented Aug 8, 2022

Uh oh!

Dandandan commented Aug 8, 2022

Uh oh!

andygrove left a comment

Choose a reason for hiding this comment

Uh oh!

ursabot commented Aug 8, 2022

Uh oh!

devanshu0987 commented Jan 3, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

alamb commented Jan 5, 2026

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

Dandandan commented Aug 6, 2022 •

edited

Loading

codecov-commenter commented Aug 6, 2022 •

edited

Loading

devanshu0987 commented Jan 3, 2026 •

edited

Loading