andygrove opened a new issue, #3156:
URL: https://github.com/apache/datafusion-comet/issues/3156
## 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 `array_binary_search` function,
causing queries using this function to fall back to Spark's JVM execution
instead of running natively on DataFusion.
ArrayBinarySearch performs a binary search operation on a sorted array to
find the index of a specified value. It returns the index of the element if
found, or a negative value indicating the insertion point if not found,
following Java's Arrays.binarySearch semantics.
Supporting this expression would allow more Spark workloads to benefit from
Comet's native acceleration.
## Describe the potential solution
### Spark Specification
**Syntax:**
```sql
array_binary_search(array, value)
```
**Arguments:**
| Argument | Type | Description |
|----------|------|-------------|
| array | ArrayType | The sorted array to search in |
| value | Compatible with array element type | The value to search for in
the array |
**Return Type:** IntegerType - Returns the index of the found element or
negative insertion point.
**Supported Data Types:**
The array element type and search value must be compatible types that
support ordering operations:
- Numeric types (IntegerType, LongType, FloatType, DoubleType, etc.)
- StringType
- DateType
- TimestampType
- Any type that has a defined ordering
The expression uses type coercion to find the tightest common type between
the array element type and search value type.
**Edge Cases:**
- **Null array**: Throws DataTypeMismatch error with NULL_TYPE subclass
- **Null search value**: Throws DataTypeMismatch error with NULL_TYPE
subclass
- **Null elements in array**: Handled by custom comparator where nulls are
ordered before non-null values
- **Empty array**: Returns -1 (standard binary search behavior for empty
collections)
- **Unsorted array**: Undefined behavior as binary search requires sorted
input
- **Incompatible types**: Throws DataTypeMismatch error with
ARRAY_FUNCTION_DIFF_TYPES subclass
**Examples:**
```sql
-- Search in sorted integer array
SELECT array_binary_search(array(1, 3, 5, 7, 9), 5);
-- Returns: 2
-- Search for non-existent value
SELECT array_binary_search(array(1.0F, 2.0F, 3.0F), 1.1F);
-- Returns: -2
-- Search in string array
SELECT array_binary_search(array('apple', 'banana', 'cherry'), 'banana');
-- Returns: 1
```
```scala
// DataFrame API usage
import org.apache.spark.sql.functions._
df.select(expr("array_binary_search(sorted_array_col, search_value)"))
// With literal array
df.select(expr("array_binary_search(array(1, 3, 5, 7), 3)"))
```
### 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.ArrayBinarySearch`
**Related:**
- `array_contains` - Check if array contains a value without requiring
sorted order
- `sort_array` - Sort an array before performing binary search
- `array_position` - Find first occurrence of value in unsorted array
---
*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]
