Support optional threshold parameter for levenshtein function
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
## Is your feature request related to a problem or challenge?
DataFusion's `levenshtein` function currently only supports the 2-argument form `levenshtein(str1, str2)`. Apache Spark supports a 3-argument form `levenshtein(str1, str2, threshold)` that returns -1 if the edit distance exceeds the threshold, with early termination for better performance.
This missing feature causes downstream projects like [Apache DataFusion Comet](https://github.com/apache/datafusion-comet) to fall back to Spark for queries using the threshold form (see [Comet #3084](https://github.com/apache/datafusion-comet/issues/3084)).
## Describe the solution you'd like
Add an optional third `Int32` argument to `levenshtein`:
```sql
SELECT levenshtein('kitten', 'sitting', 2); -- -1 (distance 3 > threshold 2)
SELECT levenshtein('kitten', 'sitting', 5); -- 3 (distance 3 <= threshold 5)
SELECT levenshtein('kitten', 'sitting', NULL); -- NULL
```
The threshold variant should use a banded DP algorithm with early termination for better performance when the threshold is small relative to string lengths.
### Additional context
Spark's implementation is in UTF8String.levenshteinDistance, based on Apache Commons Text LevenshteinDistance.limitedCompare.
Contributor guide
Research direction
Start by locating DataFusion's existing levenshtein function entry point and its current two-argument behavior. Compare the requested SQL examples with Spark's UTF8String.levenshteinDistance and Apache Commons Text's limitedCompare, then verify that the third Int32 argument handles NULL, returns -1 above the threshold, and uses early termination.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust, sql
- Domain
- databases
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100