apache / apache/datafusion

Support optional threshold parameter for levenshtein function

Open
#20,488 0 comments 0 reactions 0 assignees View on GitHub
enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.