andygrove opened a new issue, #3084:
URL: https://github.com/apache/datafusion-comet/issues/3084
## What is the problem the feature request solves?
> **Note:** This issue was generated with AI assistance. The specification
details have been extracted from Spark documentation and may need verification.
Comet does not currently support the Spark `levenshtein` function, causing
queries using this function to fall back to Spark's JVM execution instead of
running natively on DataFusion.
The Levenshtein expression computes the Levenshtein distance (also known as
edit distance) between two strings. This represents the minimum number of
single-character edits (insertions, deletions, or substitutions) required to
transform one string into another. An optional threshold parameter can be
provided to limit the maximum distance calculated.
Supporting this expression would allow more Spark workloads to benefit from
Comet's native acceleration.
## Describe the potential solution
### Spark Specification
**Syntax:**
```sql
LEVENSHTEIN(str1, str2)
LEVENSHTEIN(str1, str2, threshold)
```
**Arguments:**
| Argument | Type | Description |
|----------|------|-------------|
| str1 | String | The first input string for comparison |
| str2 | String | The second input string for comparison |
| threshold | Integer (optional) | Maximum distance to calculate;
computation stops early if distance exceeds this value |
**Return Type:** Integer - representing the Levenshtein distance between the
two input strings.
**Supported Data Types:**
- **Input strings**: StringType with collation support (supports trim
collation)
- **Threshold**: IntegerType
- **Output**: IntegerType
**Edge Cases:**
- **Null handling**: Returns null if any input parameter (left, right, or
threshold) is null
- **Empty strings**: Handles empty strings correctly - distance equals the
length of the non-empty string
- **Identical strings**: Returns 0 for identical input strings
- **Threshold behavior**: When threshold is provided, computation may
terminate early if distance exceeds the threshold value
- **Invalid threshold**: Negative threshold values are passed through to the
underlying implementation
**Examples:**
```sql
-- Basic usage
SELECT LEVENSHTEIN('kitten', 'sitting'); -- Returns 3
-- With threshold
SELECT LEVENSHTEIN('kitten', 'sitting', 5); -- Returns 3
-- Null handling
SELECT LEVENSHTEIN('test', NULL); -- Returns NULL
-- Empty strings
SELECT LEVENSHTEIN('', 'abc'); -- Returns 3
```
```scala
// DataFrame API usage
import org.apache.spark.sql.functions._
df.select(levenshtein(col("str1"), col("str2")))
// With threshold (using expr for SQL function)
df.select(expr("levenshtein(str1, str2, 5)"))
```
### Implementation Approach
See the [Comet guide on adding new
expressions](https://datafusion.apache.org/comet/contributor-guide/adding_a_new_expression.html)
for detailed instructions.
1. **Scala Serde**: Add expression handler in
`spark/src/main/scala/org/apache/comet/serde/`
2. **Register**: Add to appropriate map in `QueryPlanSerde.scala`
3. **Protobuf**: Add message type in `native/proto/src/proto/expr.proto` if
needed
4. **Rust**: Implement in `native/spark-expr/src/` (check if DataFusion has
built-in support first)
## Additional context
**Difficulty:** Medium
**Spark Expression Class:**
`org.apache.spark.sql.catalyst.expressions.Levenshtein`
**Related:**
- String similarity functions
- SOUNDEX for phonetic similarity
- String manipulation expressions in the string_funcs group
---
*This issue was auto-generated from Spark reference documentation.*
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
