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/07/10 19:10:24 UTC
[PR] perf: optimize find_in_set in datafusion-functions [datafusion]
andygrove opened a new pull request, #23460:
URL: https://github.com/apache/datafusion/pull/23460
> This PR was created by an LLM as a draft PR. I will mark it as ready for review after human review.
## Which issue does this PR close?
N/A — autonomous exploratory PR.
## Rationale for this change
Replace per-row O(set_len) linear scan in find_in_set's constant-list path with a one-time HashMap lookup (threshold-guarded so short lists keep the linear scan), giving O(1) per-row probing for large sets.
## What changes are included in this PR?
Replace per-row O(set_len) linear scan in find_in_set's constant-list path with a one-time HashMap lookup (threshold-guarded so short lists keep the linear scan), giving O(1) per-row probing for large sets.
## Are these changes tested?
Correctness: unit tests + seeded differential fuzz (bit-identical Arrow output vs `main`).
Benchmark (criterion):
- long_list_256: 95.827% faster (base 1246412ns -> cand 52009ns)
- short_list_4: 2.13% faster (base 64343ns -> cand 62972ns)
- long_list_64: 88.562% faster (base 422083ns -> cand 48276ns)
## 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] perf: optimize `find_in_set` (up to 24x faster) [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #23460:
URL: https://github.com/apache/datafusion/pull/23460#issuecomment-5065312087
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/23460?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:white_check_mark: All modified and coverable lines are covered by tests.
:white_check_mark: Project coverage is 80.71%. Comparing base ([`1763417`](https://app.codecov.io/gh/apache/datafusion/commit/17634176a4f406a50b31a3711514831c9d3ecfa0?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`086ce5c`](https://app.codecov.io/gh/apache/datafusion/commit/086ce5c30595df6e21c3c8cb6875edb0a2ef33b2?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 2 commits behind head on main.
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #23460 +/- ##
==========================================
- Coverage 80.71% 80.71% -0.01%
==========================================
Files 1090 1090
Lines 369398 369436 +38
Branches 369398 369436 +38
==========================================
+ Hits 298170 298194 +24
- Misses 53458 53468 +10
- Partials 17770 17774 +4
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/23460?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
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: optimize `find_in_set` (up to 24x faster) [datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on code in PR #23460:
URL: https://github.com/apache/datafusion/pull/23460#discussion_r3642506454
##########
datafusion/functions/src/unicode/find_in_set.rs:
##########
@@ -329,16 +334,34 @@ where
let nulls = string_array.nulls().cloned();
let zero = T::Native::from_usize(0).unwrap();
+ // The set (`str_list`) is constant across all rows. For a large set, the
+ // per-row `position` linear scan is O(set_len). Building a lookup from each
+ // distinct entry to its 1-based position once turns each row into an O(1)
+ // probe (first occurrence wins, exactly matching `position`). Below the
+ // threshold the linear scan's small constant factor is faster, so the map is
+ // built at most once here rather than per row.
+ let map: Option<HashMap<&str, usize>> =
+ (str_list.len() >= FIND_IN_SET_LOOKUP_THRESHOLD).then(|| {
+ let mut map = HashMap::with_capacity(str_list.len());
+ for (idx, entry) in str_list.iter().enumerate() {
+ map.entry(*entry).or_insert(idx + 1);
+ }
+ map
+ });
+
let values: Vec<T::Native> = (0..len)
.map(|i| {
if nulls.as_ref().is_some_and(|n| n.is_null(i)) {
return zero;
}
let string = string_array.value(i);
- let position = str_list
- .iter()
- .position(|s| *s == string)
- .map_or(0, |idx| idx + 1);
+ let position = match &map {
Review Comment:
a possible microoptimization if we can match through some bool expression, rather than Option<Map>
--
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: optimize `find_in_set` (up to 24x faster) [datafusion]
Posted by "Jefffrey (via GitHub)" <gi...@apache.org>.
Jefffrey commented on code in PR #23460:
URL: https://github.com/apache/datafusion/pull/23460#discussion_r3578270631
##########
datafusion/functions/src/unicode/find_in_set.rs:
##########
@@ -329,16 +334,34 @@ where
let nulls = string_array.nulls().cloned();
let zero = T::Native::from_usize(0).unwrap();
+ // The set (`str_list`) is constant across all rows. For a large set, the
+ // per-row `position` linear scan is O(set_len). Building a lookup from each
+ // distinct entry to its 1-based position once turns each row into an O(1)
+ // probe (first occurrence wins, exactly matching `position`). Below the
+ // threshold the linear scan's small constant factor is faster, so the map is
+ // built at most once here rather than per row.
+ let map: Option<HashMap<&str, usize>> =
+ (str_list.len() >= FIND_IN_SET_LOOKUP_THRESHOLD).then(|| {
+ let mut map = HashMap::with_capacity(str_list.len());
+ for (idx, entry) in str_list.iter().enumerate() {
+ map.entry(*entry).or_insert(idx + 1);
+ }
+ map
+ });
+
let values: Vec<T::Native> = (0..len)
.map(|i| {
if nulls.as_ref().is_some_and(|n| n.is_null(i)) {
return zero;
}
let string = string_array.value(i);
- let position = str_list
- .iter()
- .position(|s| *s == string)
- .map_or(0, |idx| idx + 1);
+ let position = match &map {
Review Comment:
should we pull the match on the map outside the loop or doesnt make too much of a difference?
--
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: optimize find_in_set in datafusion-functions [datafusion]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on code in PR #23460:
URL: https://github.com/apache/datafusion/pull/23460#discussion_r3562165921
##########
datafusion/functions/src/unicode/find_in_set.rs:
##########
@@ -329,16 +334,34 @@ where
let nulls = string_array.nulls().cloned();
let zero = T::Native::from_usize(0).unwrap();
+ // The set (`str_list`) is constant across all rows. For a large set, the
+ // per-row `position` linear scan is O(set_len). Building a lookup from each
+ // distinct entry to its 1-based position once turns each row into an O(1)
+ // probe (first occurrence wins, exactly matching `position`). Below the
+ // threshold the linear scan's small constant factor is faster, so the map is
+ // built at most once here rather than per row.
+ let map: Option<HashMap<&str, usize>> =
+ (str_list.len() >= FIND_IN_SET_LOOKUP_THRESHOLD).then(|| {
+ let mut map = HashMap::with_capacity(str_list.len());
Review Comment:
I looked into this, and it doesn't seem like it would improve performance much, and would be a significant change.
--
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: optimize find_in_set in datafusion-functions [datafusion]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on code in PR #23460:
URL: https://github.com/apache/datafusion/pull/23460#discussion_r3561971035
##########
datafusion/functions/src/unicode/find_in_set.rs:
##########
@@ -329,16 +334,34 @@ where
let nulls = string_array.nulls().cloned();
let zero = T::Native::from_usize(0).unwrap();
+ // The set (`str_list`) is constant across all rows. For a large set, the
+ // per-row `position` linear scan is O(set_len). Building a lookup from each
+ // distinct entry to its 1-based position once turns each row into an O(1)
+ // probe (first occurrence wins, exactly matching `position`). Below the
+ // threshold the linear scan's small constant factor is faster, so the map is
+ // built at most once here rather than per row.
+ let map: Option<HashMap<&str, usize>> =
+ (str_list.len() >= FIND_IN_SET_LOOKUP_THRESHOLD).then(|| {
+ let mut map = HashMap::with_capacity(str_list.len());
Review Comment:
This map is reconstructed for each batch being processed. Would be better to reuse across batches.
--
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: optimize `find_in_set` (up to 24x faster) [datafusion]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on code in PR #23460:
URL: https://github.com/apache/datafusion/pull/23460#discussion_r3604513315
##########
datafusion/functions/src/unicode/find_in_set.rs:
##########
@@ -329,16 +334,34 @@ where
let nulls = string_array.nulls().cloned();
let zero = T::Native::from_usize(0).unwrap();
+ // The set (`str_list`) is constant across all rows. For a large set, the
+ // per-row `position` linear scan is O(set_len). Building a lookup from each
+ // distinct entry to its 1-based position once turns each row into an O(1)
+ // probe (first occurrence wins, exactly matching `position`). Below the
+ // threshold the linear scan's small constant factor is faster, so the map is
+ // built at most once here rather than per row.
+ let map: Option<HashMap<&str, usize>> =
+ (str_list.len() >= FIND_IN_SET_LOOKUP_THRESHOLD).then(|| {
+ let mut map = HashMap::with_capacity(str_list.len());
+ for (idx, entry) in str_list.iter().enumerate() {
+ map.entry(*entry).or_insert(idx + 1);
+ }
+ map
+ });
+
let values: Vec<T::Native> = (0..len)
.map(|i| {
if nulls.as_ref().is_some_and(|n| n.is_null(i)) {
return zero;
}
let string = string_array.value(i);
- let position = str_list
- .iter()
- .position(|s| *s == string)
- .map_or(0, |idx| idx + 1);
+ let position = match &map {
Review Comment:
Good question — I benchmarked it. Hoisting the match into two loops is a tradeoff rather than a win: the map path gets ~5–7% faster (`long_list_64` −5.0%, `long_list_256` −7.2%), but the short-list linear-scan path regresses ~8% (`short_list_4` +7.7%). Since lists below the threshold stay on the linear scan and short lists are the common case for `find_in_set`, I would rather not regress them for a gain on the path that is already HashMap-optimized. Keeping the single loop. Results were stable across three runs and two builds.
(Disclosure: I used an LLM-based coding assistant to run these benchmarks and help draft this reply.)
--
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: optimize `find_in_set` (up to 24x faster) [datafusion]
Posted by "Jefffrey (via GitHub)" <gi...@apache.org>.
Jefffrey commented on code in PR #23460:
URL: https://github.com/apache/datafusion/pull/23460#discussion_r3607363278
##########
datafusion/functions/src/unicode/find_in_set.rs:
##########
@@ -329,16 +334,34 @@ where
let nulls = string_array.nulls().cloned();
let zero = T::Native::from_usize(0).unwrap();
+ // The set (`str_list`) is constant across all rows. For a large set, the
+ // per-row `position` linear scan is O(set_len). Building a lookup from each
+ // distinct entry to its 1-based position once turns each row into an O(1)
+ // probe (first occurrence wins, exactly matching `position`). Below the
+ // threshold the linear scan's small constant factor is faster, so the map is
+ // built at most once here rather than per row.
+ let map: Option<HashMap<&str, usize>> =
+ (str_list.len() >= FIND_IN_SET_LOOKUP_THRESHOLD).then(|| {
+ let mut map = HashMap::with_capacity(str_list.len());
+ for (idx, entry) in str_list.iter().enumerate() {
+ map.entry(*entry).or_insert(idx + 1);
+ }
+ map
+ });
+
let values: Vec<T::Native> = (0..len)
.map(|i| {
if nulls.as_ref().is_some_and(|n| n.is_null(i)) {
return zero;
}
let string = string_array.value(i);
- let position = str_list
- .iter()
- .position(|s| *s == string)
- .map_or(0, |idx| idx + 1);
+ let position = match &map {
Review Comment:
kinda interesting how it causes a regression, woulda thought with less branching it at least be the same 🤔
--
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: optimize `find_in_set` (up to 24x faster) [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan merged PR #23460:
URL: https://github.com/apache/datafusion/pull/23460
--
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