apache / apache/datafusion

Support optional threshold parameter for levenshtein function

Aperta
#20,488 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub
enhancement
Lingua principale
Rust
Stelle
9.3k
Fork
2.4k
Merge medio
3g 11h
PR unite (30g)
360

Descrizione

## 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.

Guida per i contributori

Apri la guida per i contributori

Direzione di ricerca

Inizia individuando il punto di ingresso esistente della funzione levenshtein di DataFusion e il suo comportamento attuale con due argomenti. Confronta gli esempi SQL richiesti con Spark's UTF8String.levenshteinDistance e Apache Commons Text's limitedCompare, quindi verifica che il terzo argomento Int32 gestisca NULL, restituisca -1 oltre la soglia e utilizzi la terminazione anticipata.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Valutazione

Stack tecnologico
rust, sql
Ambito
databases
Tipo di issue
Funzionalità
Difficoltà
4/5
Tempo stimato
3-5 giorni
Stato di attività
Ferma
Chiarezza
Abbastanza chiara
Idoneità per principianti
48/100

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.