daverigby opened a new pull request, #12081:
URL: https://github.com/apache/arrow-rs/pull/12081
# Which issue does this PR close?
Relates to #6107.
# Rationale for this change
LIKE patterns such as `%foo%bar%` currently fall back to regex matching.
They can instead be evaluated by searching for each literal in order.
In DataFusion TPC-H Q13 SF10, which filters 15 million order comments using
`NOT LIKE '%special%requests%'`, this reduced complete-query wall time by 13.2%
and process CPU time by 12.9%.
# What changes are included in this PR?
Add an `OrderedLiterals` variant to `Predicate` for case-sensitive LIKE
patterns with two or more non-empty literals separated by `%`.
It creates a `memmem::Finder` for each literal when the pattern is parsed,
then searches for them in order, preserving any start or end anchoring. This
reuses the searcher already used by `Contains`. Patterns containing `_` or
escape characters continue to use regex.
The change came from profiling DataFusion with Arm Performix and GPT 6.1
Sol. The implementation and tests were developed with LLM assistance; I have
reviewed them and take responsibility for this PR.
# Are these changes tested?
New tests compare the matcher against regex evaluation for anchored
patterns, repeated `%` wildcards, overlapping literals, Unicode and newlines.
They also cover NULLs, NOT LIKE, different string representations, and fallback
to regex for unsupported patterns.
Performance was measured using existing TPC-H and Criterion benchmarks.
### DataFusion TPC-H
Measured on an Arm Neoverse V2 VM using Rust 1.99.1, DataFusion commit
`198ab43f`, Arrow-string 60.1.0, matching `release-nonlto` builds. These
measurements used the original Arrow-string 60.1.0 integration of this change.
After two warmups, I ran five baseline/candidate pairs, alternating which
version ran first. Each process ran ten complete queries. CPU figures are
process user+sys time.
| Pair | Baseline median query time | Candidate median query time |
Wall-clock reduction | Process CPU reduction |
|---|---:|---:|---:|---:|
| 1 | 255.2 ms | 221.5 ms | 13.2% | 12.9% |
| 2 | 243.5 ms | 221.2 ms | 9.2% | 12.8% |
| 3 | 250.0 ms | 222.5 ms | 11.0% | 12.5% |
| 4 | 252.0 ms | 216.1 ms | 14.3% | 13.3% |
| 5 | 254.4 ms | 219.2 ms | 13.8% | 13.2% |
| **Median paired reduction** | | | **13.2%** | **12.9%** |
Q13 SF1 also improved: **13.8% less wall time and 14.9% less CPU time**
across three alternating pairs. The Q16 SF10 control was effectively unchanged.
### Arrow Criterion benchmarks
The existing scalar LIKE benchmarks were run on the same Neoverse V2 Linux
VM as regression checks. They cover existing predicate paths rather than the
new `OrderedLiterals` path.
The `contains` result is from a separate rerun with both binaries pinned to
the same CPU.
| Benchmark | Time change |
|---|---:|
| `like_utf8 scalar equals` | −1.28% |
| `like_utf8 scalar contains` | +0.45% |
| `like_utf8 scalar ends with` | −0.33% |
| `like_utf8 scalar starts with` | −0.27% |
| `like_utf8 scalar complex` | −0.12% |
<details>
<summary>Criterion result lines</summary>
```text
like_utf8 scalar equals time: [50.768 µs 50.775 µs 50.782 µs]
change: [−1.3475% −1.2761% −1.2010%] (p = 0.00 <
0.05)
Performance has improved.
like_utf8 scalar contains
time: [1.5100 ms 1.5109 ms 1.5118 ms]
change: [+0.3769% +0.4512% +0.5281%] (p = 0.00 <
0.05)
Change within noise threshold.
like_utf8 scalar ends with
time: [207.62 µs 207.71 µs 207.81 µs]
change: [−0.4841% −0.3339% −0.1880%] (p = 0.00 <
0.05)
Change within noise threshold.
like_utf8 scalar starts with
time: [210.07 µs 210.17 µs 210.27 µs]
change: [−0.3627% −0.2716% −0.1685%] (p = 0.00 <
0.05)
Change within noise threshold.
like_utf8 scalar complex
time: [1.1702 ms 1.1731 ms 1.1757 ms]
change: [−0.4070% −0.1227% +0.1607%] (p = 0.41 >
0.05)
No change in performance detected.
```
</details>
# Are there any significant user-facing changes?
No public API or query-result changes.
--
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]
