apache / apache/datafusion

Optimize `array_has` when the search element is a column

Open
#23,334 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

## Description of performance issue

`array_has(array, element)` returns, for each row, whether `array` contains `element`.

When `element` is a **scalar literal**, DataFusion has a fast path (added in #20374). But when `element` is an column, e.g. `array_has(t1.tags, t2.key)` used as a join filter, execution goes through `array_has_dispatch_for_array` (the `ColumnarValue::Array` needle branch in `datafusion/functions nested/src/array_has.rs`).

That branch compares each row by invoking the Arrow `eq` comparison kernel **once per row**.
Every invocation allocates a `BooleanArray` and pays downcast + dispatch overhead, so for an `N`-row batch it is `N` kernel calls and `N` allocations, the cost is dominated by fixed per-row overhead, not the element comparison itself.

This is a common shape in real workloads: matching tags/labels/keys between two tables lowers to an array-needle `array_has` join filter (e.g. a `NestedLoopJoinExec` with `filter=array_has(tags, key)`). It was a visible fraction of one such profile even after the join's deep-copy was fixed in #18070 / #18161.

Image

## Describe the solution you'd like

Performance improvement for at least primitives, non-nulls, and/or more

## Proposition/draft of improvement

PR with bench: https://github.com/apache/datafusion/pull/23335
PR with perf and bench results: https://github.com/apache/datafusion/pull/23337 (leaving on draft until get agreement that this should be optimised)

## Additional context
Related: #20374, #18070 / #18161, #18727.

Contributor guide

Open the contributing guide

Research direction

Start in datafusion/functions/nested/src/array_has.rs, especially the array-needle branch of array_has_dispatch_for_array, and review the benchmark and performance results in draft PRs #23335 and #23337. Compare the current per-row behavior with the proposed scope, then run the relevant benchmarks; done means the optimization is agreed, implemented, and supported by benchmark results.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
databases, performance
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.