You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "andygrove (via GitHub)" <gi...@apache.org> on 2026/01/14 19:29:47 UTC
[I] [Feature] Support Spark expression: levenshtein [datafusion-comet]
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: github-unsubscribe@datafusion.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] [Feature] Support Spark expression: levenshtein [datafusion-comet]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove closed issue #3084: [Feature] Support Spark expression: levenshtein
URL: https://github.com/apache/datafusion-comet/issues/3084
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] [Feature] Support Spark expression: levenshtein [datafusion-comet]
Posted by "Myx778 (via GitHub)" <gi...@apache.org>.
Myx778 commented on issue #3084:
URL: https://github.com/apache/datafusion-comet/issues/3084#issuecomment-4324785657
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.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] [Feature] Support Spark expression: levenshtein [datafusion-comet]
Posted by "rishabhjain1712 (via GitHub)" <gi...@apache.org>.
rishabhjain1712 commented on issue #3084:
URL: https://github.com/apache/datafusion-comet/issues/3084#issuecomment-3772767261
I @rishabhjain1712 am interested to contribute to this issue
@andygrove
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] [Feature] Support Spark expression: levenshtein [datafusion-comet]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on issue #3084:
URL: https://github.com/apache/datafusion-comet/issues/3084#issuecomment-4802002786
Closing as resolved. Comet now executes this expression within the native pipeline by routing it through the JVM codegen dispatcher (`spark.comet.exec.scalaUDF.codegen.enabled`, enabled by default), which Janino-compiles Spark's own code generation into a per-batch Arrow kernel. The expression no longer falls back to Spark, so a dedicated native (Rust) implementation is not required for coverage.
We can revisit a native implementation in the future where there is a proven performance benefit. Please reopen or file a follow-up if you hit a correctness or performance gap with the current path.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org