apache / apache/datafusion

Further improve performance of IN list evaluation

Open
#19,241 8 comments 5 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

## Summary

`IN LIST` evaluates expressions such as:

```sql
x IN (1, 3, 7)
```

When the right-hand list is constant, DataFusion can build a membership filter once and reuse it for every input row. Dynamic-filter pushdown can apply the same check millions of times during a scan.

This epic adds exact lookup strategies selected by physical representation and non-null list length. If none applies, DataFusion uses the generic static filter.

All strategies share the same result construction, so this work does not change SQL behavior for `IN`, `NOT IN`, input nulls, nulls in the list, dictionaries, or sliced arrays.

## Stack

The PRs should be read in this order.

### Landed

- [x] #21927 — clean up and optimize the generic static-filter fallback
- [x] #23011 — add bitmap lookup for `UInt8`
- [x] #23012 — add bitmap lookup for `UInt16`
- [x] #23035 — unify the bitmap implementations
- [x] #23299 — add direct bitmap lookup for `Int8` and `Int16`
- [x] #23311 — add direct bitmap lookup for `Float16`
- [x] #23014 — use direct comparisons for very small primitive lists
- [x] #24283 — centralize primitive filter selection and use the shared hash-set path for larger `Decimal128` lists
- [x] #24102 — reuse primitive filters for supported `FixedSizeBinary` widths
- [x] #24662 — handle dictionary inputs once

### Remaining

- [ ] #24088 — optimize all-inline `Utf8View` and `BinaryView` lists
- [ ] #25187 — retain short lists with specialized filters

## How the strategies work

### Generic fallback

#21927 improves the path available to every supported type. It precomputes Arrow hashes for the constant list, stores list indexes in a compact hash table, and uses Arrow's exact comparator to confirm equality. Membership is produced as a bitmap and then combined with input validity, list nulls, and `NOT IN` semantics by shared result-building code.

### Bitmap lookup for small fixed domains

A one- or two-byte value has only 256 or 65,536 possible bit patterns. That entire domain can be represented by one bit per pattern:

- `UInt8` and `Int8` use a 256-bit (32-byte) bitmap.
- `UInt16`, `Int16`, and `Float16` use a 65,536-bit (8 KiB) bitmap.

Building the filter sets the bit corresponding to each non-null list value. Probing a row is then one indexed bit test, with no hashing and no scan of the list. Signed integers and `Float16` map their native bit patterns directly into the same finite bitmap domain.

### Direct comparisons for very small primitive lists

For a tiny fixed-width list, a hash lookup can cost more than comparing the input directly with every constant. #23014 stores the constants in a fixed-size array and combines all equality checks into a predictable comparison chain.

The maximum non-null list sizes are:

| Physical width | Direct comparisons through |
|---:|---:|
| 1 byte | 16 values |
| 2 bytes | 8 values |
| 4 bytes | 32 values |
| 8 bytes | 16 values |
| 16 bytes | 4 values |

Larger one- and two-byte lists use the bitmap strategy. Larger native 32- and 64-bit integer lists use primitive hash sets; #24283 extends that same shared fallback to `Decimal128`. Other unsupported primitive types continue through their existing exact filter or the generic fallback.

### Shared primitive selection and `Decimal128`

#24283 puts the direct-comparison thresholds and larger-list choices in one primitive selector. Native arrays and representation adapters call that selector, so there is no second dispatch table.

For native `Decimal128`, up to four non-null list values use direct comparisons. Larger lists store and probe the native unscaled `i128` values in the shared primitive hash-set filter instead of using the generic Arrow array filter. Only membership storage changes; decimal expression typing, precision/scale compatibility, null behavior, and exact native-value equality remain unchanged.

### `FixedSizeBinary`

#24102 recognizes `FixedSizeBinary` widths that exactly match an existing primitive representation. The list and input are converted in the same way, so primitive equality and hashing are exact equality over the original fixed-width bytes; no numeric or decimal operations are involved.

| `FixedSizeBinary` width | Internal key | Small lists | Larger lists |
|---:|---|---|---|
| 1 byte | `UInt8` | direct comparisons through 16 values | bitmap |
| 2 bytes | `UInt16` | direct comparisons through 8 values | bitmap |
| 4 bytes | `UInt32` | direct comparisons through 32 values | shared primitive hash-set filter |
| 8 bytes | `UInt64` | direct comparisons through 16 values | shared primitive hash-set filter |
| 16 bytes | 128-bit primitive | direct comparisons through 4 values | shared primitive hash-set filter |

Other widths keep using the generic filter.

Aligned Arrow buffers are reused directly. If a valid array has an unaligned buffer, the adapter copies its values into aligned primitive storage first. Alignment affects whether a copy is needed, not correctness.

### Inline `Utf8View` and `BinaryView`

Arrow stores a `Utf8View` or `BinaryView` value of at most 12 bytes completely inside its 128-bit view: the view contains the length and the zero-padded bytes. For these values, the view holds the full value, so view equality is exact and needs no backing-buffer read.

#24088 uses this representation only when every non-null value in the constant list is inline:

- up to four non-null values use the existing 128-bit direct-comparison filter;
- larger lists reuse the `Decimal128` hash-set filter over the same 128-bit key; and
- if any list value is longer than 12 bytes, the whole list uses the generic filter.

Input arrays may still contain long values. Their encoded length distinguishes them from every inline list key, so they produce a miss without reading their backing bytes. `Utf8View` and `BinaryView` remain separate typed paths, and dictionary inputs continue through the shared dictionary handling.

## Expected impact

| Case | Lookup used |
|---|---|
| Generic constant lists | precomputed Arrow hash table with exact comparison |
| One- and two-byte primitive domains | one bitmap bit test per row |
| Very small primitive lists | fixed direct-comparison chain |
| Larger native `Decimal128` lists | shared primitive hash-set lookup |
| Supported `FixedSizeBinary` widths | reused primitive direct, bitmap, or hash-set lookup |
| All-inline `Utf8View` / `BinaryView` lists | exact 128-bit direct or hash-set lookup |

Contributor guide

Open the contributing guide

Research direction

Start with the remaining work items #24088 and #25187, then read the landed PRs in the order listed to understand the existing IN LIST strategy selection and shared result construction. The work is done when both remaining optimizations are implemented and the documented IN, NOT IN, null, dictionary, and sliced-array behavior remains unchanged.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust, sql
Domain
databases, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.