[Feature] Support Spark expression: levenshtein

[andygrove]

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:

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:

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

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

[rishabhjain1712]

I @rishabhjain1712 am interested to contribute to this issue

@andygrove

[Myx778]

Hi, I'd like to work on this issue. I have a working implementation using the ScalarFunc pathway (CometScalarFunction + custom Rust UDF). Will submit a PR shortly.