You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "2010YOUY01 (via GitHub)" <gi...@apache.org> on 2024/09/12 13:39:07 UTC
[PR] Specialize ASCII case for substr() [datafusion]
2010YOUY01 opened a new pull request, #12444:
URL: https://github.com/apache/datafusion/pull/12444
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
Part of #12306
## Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
See the issue for the background
One tricky condition for this function is: taking a small prefix of a long string (`e.g. substr(long_str_with_1k_chars, 1, 20)`).In this case the ASCII validation overhead can be greater than decoding a small number of characters. As a result, in some micro benchmarks (taking the first 6 bytes from 128 bytes string), this PR introduced ~5% slowdown.
To avoid big regression for similar patterns, the implementation will check the approximate string length, and skip ASCII validation if strings are too long (See code comment for more detail)
The micro-benchmark result:
`substr_baseline` - No optimization
`substr_before` - StringView optimization (take substr by only modifying views and avoid copy the whole string), introduced by https://github.com/apache/datafusion/pull/12044
`substr_after` - StringView optimization + (this PR)ASCII fast path
## What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
## Are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
-->
## Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please add the `api change` label.
-->
--
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] Specialize ASCII case for substr() [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #12444:
URL: https://github.com/apache/datafusion/pull/12444
--
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] Specialize ASCII case for substr() [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #12444:
URL: https://github.com/apache/datafusion/pull/12444#issuecomment-2350899067
> I am in general somewhat lukewarm on adding optimizations that make some queries faster and some slower (as it then becomes a tradeoff, and different users might have different tradeoffs).
>
> It would be great to figure out how to avoid this tradeoff (I left one suggestion)
I think this regression is fixable in the long term (by making ASCII check more efficient, currently especially for `StringView` ASCII check is not the most efficient way), but it's a good idea to be more conservative and skip ASCII validation for small prefix for now.
I applied this suggestion and benched again and I think there is no noticeable ASCII check overhead:
Result:
`substr_before` is current main already with `StringView` optimization to avoid copy
`susbtr_after` is this PR with additional ASCII fast path
```
group substr_after substr_before
----- ------------ -------------
LONGER THAN 12/substr_large_string [size=1024, count=64, strlen=128] 1.00 74.1±1.13µs ? ?/sec 2.65 196.4±1.32µs ? ?/sec
LONGER THAN 12/substr_large_string [size=4096, count=64, strlen=128] 1.00 290.6±1.16µs ? ?/sec 2.68 779.1±17.07µs ? ?/sec
LONGER THAN 12/substr_string [size=1024, count=64, strlen=128] 1.00 72.9±0.25µs ? ?/sec 2.91 212.2±13.48µs ? ?/sec
LONGER THAN 12/substr_string [size=4096, count=64, strlen=128] 1.00 285.0±1.72µs ? ?/sec 2.99 852.6±67.06µs ? ?/sec
LONGER THAN 12/substr_string_view [size=1024, count=64, strlen=128] 1.00 29.7±0.17µs ? ?/sec 5.61 166.5±24.98µs ? ?/sec
LONGER THAN 12/substr_string_view [size=4096, count=64, strlen=128] 1.00 117.8±0.92µs ? ?/sec 5.29 623.4±29.53µs ? ?/sec
SHORTER THAN 12/substr_large_string [size=1024, strlen=12] 1.00 59.0±0.67µs ? ?/sec 1.15 67.8±1.30µs ? ?/sec
SHORTER THAN 12/substr_large_string [size=4096, strlen=12] 1.00 228.5±2.10µs ? ?/sec 1.26 289.0±25.86µs ? ?/sec
SHORTER THAN 12/substr_string [size=1024, strlen=12] 1.00 55.3±0.46µs ? ?/sec 1.06 58.5±3.18µs ? ?/sec
SHORTER THAN 12/substr_string [size=4096, strlen=12] 1.00 214.8±1.59µs ? ?/sec 1.04 222.4±4.55µs ? ?/sec
SHORTER THAN 12/substr_string_view [size=1024, strlen=12] 1.00 18.2±0.09µs ? ?/sec 1.27 23.0±0.49µs ? ?/sec
SHORTER THAN 12/substr_string_view [size=4096, strlen=12] 1.00 73.5±1.79µs ? ?/sec 1.44 105.8±11.82µs ? ?/sec
SRC_LEN > 12, SUB_LEN < 12/substr_large_string [size=1024, count=6, strlen=128] 1.00 75.9±0.40µs ? ?/sec 1.04 78.8±3.79µs ? ?/sec
SRC_LEN > 12, SUB_LEN < 12/substr_large_string [size=4096, count=6, strlen=128] 1.00 297.4±2.70µs ? ?/sec 1.01 299.3±8.54µs ? ?/sec
SRC_LEN > 12, SUB_LEN < 12/substr_string [size=1024, count=6, strlen=128] 1.00 77.8±0.24µs ? ?/sec 1.07 83.4±10.36µs ? ?/sec
SRC_LEN > 12, SUB_LEN < 12/substr_string [size=4096, count=6, strlen=128] 1.04 300.9±1.48µs ? ?/sec 1.00 289.1±3.56µs ? ?/sec
SRC_LEN > 12, SUB_LEN < 12/substr_string_view [size=1024, count=6, strlen=128] 1.06 33.3±0.63µs ? ?/sec 1.00 31.5±0.15µs ? ?/sec
SRC_LEN > 12, SUB_LEN < 12/substr_string_view [size=4096, count=6, strlen=128] 1.00 129.8±2.23µs ? ?/sec 1.01 130.8±13.20µs ? ?/sec
```
> The other thing I keep thinking is how can we avoid this 'is_ascii' check at runtime (so things get faster regardless). Maybe it is time to consider starting to propage the is_ascii flag on the arrays themselves
>
> The parquet reader, for example, knows when it has only ascii data
I think it's a good idea.
I'm curious (and also to justify the extra complexity), is your (InfluxDB) real workload dominated by String data? I saw somewhere Databricks and Tableau said their production workload has >50% string data, many are the substitute for UDT, and also uncleaned raw data, for such case it should be worth the effort
--
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] Specialize ASCII case for substr() [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #12444:
URL: https://github.com/apache/datafusion/pull/12444#discussion_r1761725094
##########
datafusion/functions/src/unicode/substr.rs:
##########
@@ -186,6 +202,53 @@ fn make_and_append_view(
null_builder.append_non_null();
}
+// String characters are variable length encoded in UTF-8, `substr()` function's
+// arguments are character-based, converting them into byte-based indices
+// requires expensive decoding.
+// However, checking if a string is ASCII-only is relatively cheap.
+// If strings are ASCII only, use byte-based indices instead.
+//
+// A common pattern to call `substr()` is taking a small prefix of a long
Review Comment:
👍
##########
datafusion/functions/src/unicode/substr.rs:
##########
@@ -186,6 +202,53 @@ fn make_and_append_view(
null_builder.append_non_null();
}
+// String characters are variable length encoded in UTF-8, `substr()` function's
+// arguments are character-based, converting them into byte-based indices
+// requires expensive decoding.
+// However, checking if a string is ASCII-only is relatively cheap.
+// If strings are ASCII only, use byte-based indices instead.
+//
+// A common pattern to call `substr()` is taking a small prefix of a long
+// string, such as `substr(long_str_with_1k_chars, 1, 32)`.
+// In such case the overhead of ASCII-validation may not be worth it, so
+// skip the validation for short prefix for now.
+fn enable_ascii_fast_path<'a, V: StringArrayType<'a>>(
+ string_array: &V,
+ start: &Int64Array,
+ count: Option<&Int64Array>,
+) -> bool {
+ let is_short_prefix = match count {
+ Some(count) => {
+ let short_prefix_threshold = 32.0;
+ let n_sample = 10;
+
+ // HACK: can be simplified if function has specialized
Review Comment:
its a good point this could be faster if it had a specialization for `ScalarValue`
Any chance you can file a ticket for this?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: 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] Specialize ASCII case for substr() [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #12444:
URL: https://github.com/apache/datafusion/pull/12444#discussion_r1759454152
##########
datafusion/functions/src/unicode/substr.rs:
##########
@@ -197,6 +213,29 @@ fn string_view_substr(
let start_array = as_int64_array(&args[0])?;
+ // Notes for ASCII-only optimization:
+ //
+ // String characters are variable length encoded in UTF-8, `substr()` function's
+ // arguments are character-based, converting them into byte-based indices
+ // requires expensive decoding.
+ // However, checking if a string is ASCII-only is relatively cheap.
+ // If strings are ASCII only, use byte-based indices instead.
+ //
+ // A common pattern to call `substr()` is taking a small prefix of a long
+ // string, such as `substr(long_str_with_1k_chars, 1, 32)`.
+ // In such case the overhead of ASCII-validation may not be worth it, so
+ // skip the validation for long strings for now.
+ // TODO: A better heuristic is to use the ratio to decide whether to validate
+ // like `(start + count) / estimate_avg_strlen > threshold`, but it requires
+ // specialized implementation for `ScalarValue` input.
+ let estimate_avg_strlen =
Review Comment:
Can we please pull this check into its own method (so it is easier to find), perhaps something like
```rust
fn enable_ascii_fast_path(arr: &StringViewArray) -> bool {
...
}
```
##########
datafusion/functions/src/unicode/substr.rs:
##########
@@ -197,6 +213,29 @@ fn string_view_substr(
let start_array = as_int64_array(&args[0])?;
+ // Notes for ASCII-only optimization:
+ //
+ // String characters are variable length encoded in UTF-8, `substr()` function's
+ // arguments are character-based, converting them into byte-based indices
+ // requires expensive decoding.
+ // However, checking if a string is ASCII-only is relatively cheap.
+ // If strings are ASCII only, use byte-based indices instead.
+ //
+ // A common pattern to call `substr()` is taking a small prefix of a long
+ // string, such as `substr(long_str_with_1k_chars, 1, 32)`.
+ // In such case the overhead of ASCII-validation may not be worth it, so
+ // skip the validation for long strings for now.
Review Comment:
I am not quite sure if it is the same question that @findepi is asking, but I wonder if we could get back the performance loss by also using the information on the # bytes are we requesting? Like if the prefix length is less than 32 say, don't bother checking for ascii. 🤔
I thinking short prefixes are likely common (looking for `http://` as a url prefix, for example). 🤔
--
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] Specialize ASCII case for substr() [datafusion]
Posted by "findepi (via GitHub)" <gi...@apache.org>.
findepi commented on code in PR #12444:
URL: https://github.com/apache/datafusion/pull/12444#discussion_r1759057882
##########
datafusion/functions/src/unicode/substr.rs:
##########
@@ -197,6 +213,29 @@ fn string_view_substr(
let start_array = as_int64_array(&args[0])?;
+ // Notes for ASCII-only optimization:
+ //
+ // String characters are variable length encoded in UTF-8, `substr()` function's
+ // arguments are character-based, converting them into byte-based indices
+ // requires expensive decoding.
+ // However, checking if a string is ASCII-only is relatively cheap.
+ // If strings are ASCII only, use byte-based indices instead.
+ //
+ // A common pattern to call `substr()` is taking a small prefix of a long
+ // string, such as `substr(long_str_with_1k_chars, 1, 32)`.
+ // In such case the overhead of ASCII-validation may not be worth it, so
+ // skip the validation for long strings for now.
Review Comment:
Why not check only the requested string prefix for being ascii?
could `string_view_array.is_ascii` variant validate string prefixes of given length why still being vectorized?
--
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] Specialize ASCII case for substr() [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #12444:
URL: https://github.com/apache/datafusion/pull/12444#discussion_r1759687997
##########
datafusion/functions/src/unicode/substr.rs:
##########
@@ -197,6 +213,29 @@ fn string_view_substr(
let start_array = as_int64_array(&args[0])?;
+ // Notes for ASCII-only optimization:
+ //
+ // String characters are variable length encoded in UTF-8, `substr()` function's
+ // arguments are character-based, converting them into byte-based indices
+ // requires expensive decoding.
+ // However, checking if a string is ASCII-only is relatively cheap.
+ // If strings are ASCII only, use byte-based indices instead.
+ //
+ // A common pattern to call `substr()` is taking a small prefix of a long
+ // string, such as `substr(long_str_with_1k_chars, 1, 32)`.
+ // In such case the overhead of ASCII-validation may not be worth it, so
+ // skip the validation for long strings for now.
Review Comment:
> Why not check only the requested string prefix for being ascii? could `string_view_array.is_ascii` variant validate string prefixes of given length why still being vectorized?
I think it's a good idea for the current situation
However in the long term we might use an alternative approach: do validation when reading arrays from storage to memory, and cache this `is_ascii` property within the arrow array (as suggested by @alamb https://github.com/apache/datafusion/pull/12444#pullrequestreview-2304056515)
--
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