You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "yongster (via GitHub)" <gi...@apache.org> on 2026/09/19 11:38:01 UTC
[PR] perf(arrow-string): cache low-cardinality array LIKE patterns [arrow-rs]
yongster opened a new pull request, #11137:
URL: https://github.com/apache/arrow-rs/pull/11137
# Which issue does this PR close?
- Closes #11084.
# Rationale for this change
Array/array `LIKE` / `ILIKE` / `NLIKE` / `NILIKE` go through `binary_predicate`, which only reused the immediately previous pattern. Two or more complex (Regex-backed) patterns that alternate — or any low-cardinality pattern column that is not grouped — therefore re-ran `regex_like` + `RegexBuilder::build` on almost every row. Performance then depended on row order even when the logical workload had only a few distinct patterns.
Simple patterns (`x%`, `%x`, `%x%`, equality) do not compile a Regex and were already cheap. The scalar path already builds one `Predicate` and is unchanged.
# What changes are included in this PR?
- Keep the existing previous-pattern fast path so consecutive duplicates do not pay an extra lookup.
- Add a bounded cache (8 entries) of compiled **Regex** predicates, keyed by borrowed `&str` from the pattern array.
- Once the cache is full, additional patterns are evaluated without being retained, so a unique pattern per row cannot accumulate an unbounded number of `Regex` values.
- Keep `previous` even for a pattern that was not inserted into the cache, so a consecutive run of an uncached pattern does not recompile every row.
- Prefix/suffix/contains/equality predicates are not cached; rebuilding them is cheaper than cache bookkeeping.
- Tests for alternating complex patterns across LIKE/NLIKE/ILIKE/NILIKE (Utf8 / LargeUtf8 / Utf8View / Dictionary), mixed nulls, and more distinct patterns than the cache cap.
- Criterion benches for consecutive complex, alternating complex, simple alternating, and all-unique complex array/array LIKE.
# Are these changes tested?
Yes. `cargo test -p arrow-string --lib like`: 63 passed.
Independent remeasurement of the public `like` / `ilike` APIs on arm64 macOS, 1,024 rows of `"xxxxxxxx"`:
| Case | Before | After |
|---|---:|---:|
| LIKE, one complex pattern, consecutive | 52.4 µs | 40.0 µs |
| LIKE, two complex patterns, alternating | 21.18 ms | 62.1 µs (~341×) |
| ILIKE, two complex patterns, alternating | 21.64 ms | 65.6 µs (~330×) |
| LIKE, two simple patterns (`x%` / `%x`), alternating | 13.2 µs | 15.9 µs |
| LIKE, 1,024 unique complex patterns | 18.86 ms | 18.54 ms |
Criterion (`cargo bench -p arrow --features test_utils --bench comparison_kernels -- "like_utf8 array"`) after the change:
| Bench | time |
|---|---:|
| `like_utf8 array complex consecutive` | 38.4 µs |
| `like_utf8 array complex alternating` | 58.8 µs |
| `ilike_utf8 array complex alternating` | 59.6 µs |
| `like_utf8 array simple alternating` | 15.9 µs |
| `like_utf8 array complex unique` | 18.6 ms |
`cargo fmt --all -- --check` and `cargo clippy -p arrow-string --lib --all-targets -- -D warnings` pass.
# Are there any user-facing changes?
No. Logical results are unchanged; this is an internal reuse policy for compiled Regex predicates.
AI assistance: implementation and tests were drafted with AI and then reviewed, corrected (Regex-only cache so simple patterns do not regress), and remeasured locally.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-string): cache low-cardinality array LIKE patterns [arrow-rs]
Posted by "Jefffrey (via GitHub)" <gi...@apache.org>.
Jefffrey commented on PR #11137:
URL: https://github.com/apache/arrow-rs/pull/11137#issuecomment-5810861220
run benchmark comparison_kernels
env:
BENCH_FILTER: like
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-string): cache low-cardinality array LIKE patterns [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11137:
URL: https://github.com/apache/arrow-rs/pull/11137#issuecomment-5810900206
🤖 Arrow criterion benchmark running (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11137#issuecomment-5810861220)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c5810861220-2684-96wrb 6.12.94+ #1 SMP Wed Aug 19 07:47:20 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing perf/like-array-pattern-cache (1e374e319b6298bb09590f715d177002717d8998) to a7b89dd (merge-base) [diff](https://github.com/apache/arrow-rs/compare/a7b89dd34eb6bd17e99bdc61a60b37a7cc08f166..1e374e319b6298bb09590f715d177002717d8998)
<details><summary>Run configuration</summary>
```yaml
run benchmark comparison_kernels
env:
BENCH_FILTER: "like"
```
</details>
BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental,object_store --bench comparison_kernels
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-string): cache low-cardinality array LIKE patterns [arrow-rs]
Posted by "yongster (via GitHub)" <gi...@apache.org>.
yongster closed pull request #11137: perf(arrow-string): cache low-cardinality array LIKE patterns
URL: https://github.com/apache/arrow-rs/pull/11137
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-string): cache low-cardinality array LIKE patterns [arrow-rs]
Posted by "yongster (via GitHub)" <gi...@apache.org>.
yongster commented on PR #11137:
URL: https://github.com/apache/arrow-rs/pull/11137#issuecomment-5811493061
Benchmarks are split out into #11195, so this PR now only changes `arrow-string/src/like.rs`.
Once #11195 is on main I will rebase this branch and rerun the comparison_kernels benchmark, so the alternating case has a baseline.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-string): cache low-cardinality array LIKE patterns [arrow-rs]
Posted by "yongster (via GitHub)" <gi...@apache.org>.
yongster commented on PR #11137:
URL: https://github.com/apache/arrow-rs/pull/11137#issuecomment-5788032052
@Jefffrey Would you mind taking a look at this when you have a chance?
Summary:
- Closes #11084
- Caches up to 8 compiled Regex predicates for low-cardinality array/array LIKE/ILIKE/NLIKE/NILIKE patterns (keeps the existing consecutive-pattern fast path)
- Simple patterns are intentionally not cached
- CI is green; local benches show large wins on alternating complex patterns (~300×) with no meaningful regression on consecutive/simple/unique cases
Happy to address any feedback.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-string): cache low-cardinality array LIKE patterns [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11137:
URL: https://github.com/apache/arrow-rs/pull/11137#issuecomment-5811171135
🤖 Arrow criterion benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11137#issuecomment-5810861220)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
Comparing perf/like-array-pattern-cache (1e374e319b6298bb09590f715d177002717d8998) to a7b89dd (merge-base) [diff](https://github.com/apache/arrow-rs/compare/a7b89dd34eb6bd17e99bdc61a60b37a7cc08f166..1e374e319b6298bb09590f715d177002717d8998)
<details><summary>Run configuration</summary>
```yaml
run benchmark comparison_kernels
env:
BENCH_FILTER: "like"
```
</details>
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
group main perf_like-array-pattern-cache
----- ---- -----------------------------
ilike_utf8 array complex alternating 1.00 96.9±0.41µs ? ?/sec
ilike_utf8 scalar complex 1.00 2.0±0.25ms ? ?/sec 1.01 2.0±0.24ms ? ?/sec
ilike_utf8 scalar contains 1.00 4.0±0.22ms ? ?/sec 1.05 4.2±0.23ms ? ?/sec
ilike_utf8 scalar ends with 1.00 812.4±27.58µs ? ?/sec 1.21 981.1±121.24µs ? ?/sec
ilike_utf8 scalar equals 1.09 688.5±45.54µs ? ?/sec 1.00 630.9±6.08µs ? ?/sec
ilike_utf8 scalar starts with 1.00 856.0±73.36µs ? ?/sec 1.05 896.4±97.65µs ? ?/sec
ilike_utf8_scalar_dyn dictionary[10] string[4]) 1.01 32.3±0.06µs ? ?/sec 1.00 32.1±0.04µs ? ?/sec
like_utf8 array complex alternating 1.00 95.0±0.26µs ? ?/sec
like_utf8 array complex consecutive 1.00 62.0±0.14µs ? ?/sec
like_utf8 array complex unique 1.00 30.1±0.06ms ? ?/sec
like_utf8 array simple alternating 1.00 32.8±0.66µs ? ?/sec
like_utf8 scalar complex 1.00 1208.2±37.12µs ? ?/sec 1.03 1250.2±66.70µs ? ?/sec
like_utf8 scalar contains 1.09 1447.7±78.16µs ? ?/sec 1.00 1333.6±21.03µs ? ?/sec
like_utf8 scalar ends with 1.00 194.3±14.55µs ? ?/sec 1.11 214.8±21.40µs ? ?/sec
like_utf8 scalar equals 1.00 47.6±0.10µs ? ?/sec 1.00 47.8±0.03µs ? ?/sec
like_utf8 scalar starts with 1.00 171.5±15.00µs ? ?/sec 1.09 186.7±9.43µs ? ?/sec
like_utf8_scalar_dyn dictionary[10] string[4]) 1.00 31.8±0.05µs ? ?/sec 1.00 31.9±0.04µs ? ?/sec
like_utf8view scalar complex 1.00 147.5±1.85ms ? ?/sec 1.00 147.0±1.47ms ? ?/sec
like_utf8view scalar contains 1.01 140.2±0.71ms ? ?/sec 1.00 138.9±0.67ms ? ?/sec
like_utf8view scalar ends with 13 bytes 1.00 27.9±0.11ms ? ?/sec 1.05 29.4±1.03ms ? ?/sec
like_utf8view scalar ends with 4 bytes 1.07 29.3±0.67ms ? ?/sec 1.00 27.5±0.09ms ? ?/sec
like_utf8view scalar ends with 6 bytes 1.02 28.1±0.88ms ? ?/sec 1.00 27.6±0.13ms ? ?/sec
like_utf8view scalar equals 1.00 19.1±0.07ms ? ?/sec 1.02 19.5±0.37ms ? ?/sec
like_utf8view scalar starts with 13 bytes 1.00 26.1±0.15ms ? ?/sec 1.00 26.1±0.11ms ? ?/sec
like_utf8view scalar starts with 4 bytes 1.00 17.2±0.14ms ? ?/sec 1.02 17.5±0.30ms ? ?/sec
like_utf8view scalar starts with 6 bytes 1.00 25.4±0.35ms ? ?/sec 1.05 26.7±1.03ms ? ?/sec
long same prefix strings like_utf8 scalar complex 1.00 1086.2±16.77µs ? ?/sec 1.00 1088.0±14.88µs ? ?/sec
long same prefix strings like_utf8 scalar contains 1.01 3.2±0.03ms ? ?/sec 1.00 3.2±0.02ms ? ?/sec
long same prefix strings like_utf8 scalar ends with 1.02 1104.1±21.60µs ? ?/sec 1.00 1079.2±16.44µs ? ?/sec
long same prefix strings like_utf8 scalar equals 1.01 405.4±8.30µs ? ?/sec 1.00 402.7±8.18µs ? ?/sec
long same prefix strings like_utf8 scalar starts with 1.00 1442.1±14.29µs ? ?/sec 1.00 1443.4±18.75µs ? ?/sec
long same prefix strings like_utf8view scalar complex 1.00 1137.7±13.93µs ? ?/sec 1.03 1176.0±28.63µs ? ?/sec
long same prefix strings like_utf8view scalar contains 1.00 3.2±0.01ms ? ?/sec 1.00 3.2±0.02ms ? ?/sec
long same prefix strings like_utf8view scalar ends with 1.05 1186.7±38.01µs ? ?/sec 1.00 1129.2±17.08µs ? ?/sec
long same prefix strings like_utf8view scalar equals 1.00 425.8±6.66µs ? ?/sec 1.00 427.3±4.89µs ? ?/sec
long same prefix strings like_utf8view scalar starts with 1.02 1506.9±28.29µs ? ?/sec 1.00 1478.0±4.71µs ? ?/sec
nilike_utf8 scalar complex 1.04 1949.9±186.94µs ? ?/sec 1.00 1882.8±49.81µs ? ?/sec
nilike_utf8 scalar contains 1.05 4.0±0.26ms ? ?/sec 1.00 3.8±0.02ms ? ?/sec
nilike_utf8 scalar ends with 1.00 808.0±26.17µs ? ?/sec 1.22 987.3±86.85µs ? ?/sec
nilike_utf8 scalar equals 1.03 702.8±49.89µs ? ?/sec 1.00 683.7±48.39µs ? ?/sec
nilike_utf8 scalar starts with 1.00 834.9±57.59µs ? ?/sec 1.08 898.4±90.82µs ? ?/sec
nlike_utf8 scalar complex 1.07 1271.5±75.19µs ? ?/sec 1.00 1187.5±17.66µs ? ?/sec
nlike_utf8 scalar contains 1.00 1346.8±13.67µs ? ?/sec 1.09 1463.1±53.23µs ? ?/sec
nlike_utf8 scalar ends with 1.13 241.9±6.93µs ? ?/sec 1.00 213.8±20.99µs ? ?/sec
nlike_utf8 scalar equals 1.00 47.9±0.08µs ? ?/sec 1.00 47.8±0.04µs ? ?/sec
nlike_utf8 scalar starts with 1.00 167.6±1.75µs ? ?/sec 1.00 167.1±0.97µs ? ?/sec
```
</p>
</details>
<details><summary>Resource Usage</summary>
**base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 460.1s |
| Peak memory | 1.9 GiB |
| Avg memory | 1.7 GiB |
| CPU user | 453.8s |
| CPU sys | 0.5s |
| Peak spill | 0 B |
**branch**
| Metric | Value |
|--------|-------|
| Wall time | 500.1s |
| Peak memory | 2.0 GiB |
| Avg memory | 1.7 GiB |
| CPU user | 498.2s |
| CPU sys | 0.5s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org