You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "samuelcolvin (via GitHub)" <gi...@apache.org> on 2024/07/26 12:56:15 UTC
[PR] Improve `LIKE` performance for "contains" style queries [arrow-rs]
samuelcolvin opened a new pull request, #6128:
URL: https://github.com/apache/arrow-rs/pull/6128
# Which issue does this PR close?
This is will have some trivial conflicts after #6118, it's part of #6107
# Rationale for this change
Lots of context in #6107, this makes `LIKE` queries which are simply "conatins" significantly faster.
Running
```bash
cargo bench -p arrow --bench comparison_kernels -F test_utils -- 'like.*contains'
```
Gives a max of ~50% speedup, but the default haystack size is 4 characters, if you increase that to 400, the performance improvement is quite marked!
```
➤ cargo bench -p arrow --bench comparison_kernels -F test_utils -- 'like.*contains'
Compiling arrow-string v52.2.0 (/Users/samuel/code/arrow-rs/arrow-string)
Compiling arrow v52.2.0 (/Users/samuel/code/arrow-rs/arrow)
Finished `bench` profile [optimized] target(s) in 4.09s
Running benches/comparison_kernels.rs (target/release/deps/comparison_kernels-95ab196215ed59e6)
like_utf8 scalar contains
time: [888.14 µs 889.44 µs 891.07 µs]
change: [-80.213% -80.152% -80.091%] (p = 0.00 < 0.05)
Performance has improved.
Found 14 outliers among 100 measurements (14.00%)
5 (5.00%) high mild
9 (9.00%) high severe
Benchmarking like_utf8view scalar contains: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 8.9s, or reduce sample count to 50.
like_utf8view scalar contains
time: [89.263 ms 89.328 ms 89.402 ms]
change: [-50.303% -50.217% -50.124%] (p = 0.00 < 0.05)
Performance has improved.
Found 7 outliers among 100 measurements (7.00%)
4 (4.00%) high mild
3 (3.00%) high severe
nlike_utf8 scalar contains
time: [890.63 µs 895.93 µs 902.48 µs]
change: [-80.369% -80.298% -80.223%] (p = 0.00 < 0.05)
Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
2 (2.00%) high mild
6 (6.00%) high severe
ilike_utf8 scalar contains
time: [31.714 ms 31.793 ms 31.876 ms]
change: [+1.9043% +2.1414% +2.4089%] (p = 0.00 < 0.05)
Performance has regressed.
Found 1 outliers among 100 measurements (1.00%)
1 (1.00%) high mild
nilike_utf8 scalar contains
time: [31.459 ms 31.508 ms 31.560 ms]
change: [+0.8653% +1.0474% +1.2321%] (p = 0.00 < 0.05)
Change within noise threshold.
Found 1 outliers among 100 measurements (1.00%)
1 (1.00%) high mild
```
# What changes are included in this PR?
Use [`memchr`](https://docs.rs/memchr/latest/memchr/index.html) (which was already a dependency) instead of `str.contains`.
# Are there any user-facing changes?
AFAIK, no.
--
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] Improve `LIKE` performance for "contains" style queries [arrow-rs]
Posted by "samuelcolvin (via GitHub)" <gi...@apache.org>.
samuelcolvin commented on PR #6128:
URL: https://github.com/apache/arrow-rs/pull/6128#issuecomment-2254513573
The problem here I think is that the haystack length is only [4 characters](https://github.com/apache/arrow-rs/blob/5f5a82cb388094ea2a54f313b5a43249613195aa/arrow/src/util/bench_util.rs#L116)! While of course some haystacks will be that short, I personally don't think that's the only case we should consider.
Running
```bash
cargo bench -p arrow --bench comparison_kernels -F test_utils -- --save-baseline `git rev-parse --abbrev-ref HEAD` '^(like|nlike).*scalar contains'
git checkout contains-performance
cargo bench -p arrow --bench comparison_kernels -F test_utils -- --save-baseline `git rev-parse --abbrev-ref HEAD` '^(like|nlike).*scalar contains'
critcmp master contains-performance
```
With different haystack lengths gives very different results from those shown above:
### With haystack length=10
```
group contains-performance master
----- -------------------- ------
like_utf8 scalar contains 1.00 375.5±4.54µs ? ?/sec 2.43 912.8±6.32µs ? ?/sec
like_utf8view scalar contains 1.00 89.6±1.94ms ? ?/sec 2.01 179.8±1.80ms ? ?/sec
nlike_utf8 scalar contains 1.00 374.3±2.67µs ? ?/sec 2.43 911.1±1.95µs ? ?/sec
```
### With haystack length=20
```
group contains-performance master
----- -------------------- ------
like_utf8 scalar contains 1.00 229.6±1.50µs ? ?/sec 4.46 1024.3±6.95µs ? ?/sec
like_utf8view scalar contains 1.00 88.9±0.79ms ? ?/sec 2.07 184.4±2.52ms ? ?/sec
nlike_utf8 scalar contains 1.00 230.6±3.77µs ? ?/sec 4.44 1025.1±6.38µs ? ?/sec
```
### With haystack length=100
```
group contains-performance master
----- -------------------- ------
like_utf8 scalar contains 1.00 377.3±2.50µs ? ?/sec 4.51 1701.4±17.41µs ? ?/sec
like_utf8view scalar contains 1.00 89.4±0.39ms ? ?/sec 2.02 180.6±2.29ms ? ?/sec
nlike_utf8 scalar contains 1.00 376.6±1.74µs ? ?/sec 4.58 1724.9±15.14µs ? ?/sec
```
### With random haystack length=0..400
**IMHO this is by far the most representative benchmark** (happy to submit a PR to make this change permanent if you agree).
Using the following in `create_string_array_with_len`
```rs
let length = rng.gen_range(0..max_str_len);
let value = rng.sample_iter(&Alphanumeric).take(length).collect();
```
```
group contains-performance master
----- -------------------- ------
like_utf8 scalar contains 1.00 882.0±29.67µs ? ?/sec 3.33 2.9±0.08ms ? ?/sec
like_utf8view scalar contains 1.00 89.8±2.13ms ? ?/sec 2.04 182.9±3.11ms ? ?/sec
nlike_utf8 scalar contains 1.00 867.1±11.87µs ? ?/sec 3.39 2.9±0.06ms ? ?/sec
```
---
These benchmarks were all run on my M3 mac, but that's pretty consistent with the GCP VM. I ran the last benchmark ("With random haystack length=0..400") on GCP to confirm:
```
group contains-performance master
----- -------------------- ------
like_utf8 scalar contains 1.00 1661.6±16.26µs ? ?/sec 3.22 5.4±0.02ms ? ?/sec
like_utf8view scalar contains 1.00 132.4±0.21ms ? ?/sec 2.92 386.5±0.46ms ? ?/sec
nlike_utf8 scalar contains 1.00 1659.9±14.95µs ? ?/sec 3.22 5.3±0.01ms ? ?/sec
```
---
## Summary
I guess we could do some special casing in the contains logic to use `str.contains` for very short haystacks, but personally I don't think it's worth it — it would make the kernel a bit slower in all cases.
Personally I think this change is good as is and we should update the benchmark code to use more representative haystacks.
LMK what you think.
--
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] Improve `LIKE` performance for "contains" style queries [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #6128:
URL: https://github.com/apache/arrow-rs/pull/6128
--
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] Improve `LIKE` performance for "contains" style queries [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6128:
URL: https://github.com/apache/arrow-rs/pull/6128#issuecomment-2254138104
What I am hoping is that we can investigate / fix the measured regressions and then merge it in 🚀
--
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] Improve `LIKE` performance for "contains" style queries [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6128:
URL: https://github.com/apache/arrow-rs/pull/6128#issuecomment-2256628061
> Personally I think this change is good as is and we should update the benchmark code to use more representative haystacks.
I agree we should update the benchmarks (which we have done in https://github.com/apache/arrow-rs/pull/6147 -- thank you)
I took the liberty of merging up from main with this PR and will rerun the benchmarks just to be sure
--
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] Improve `LIKE` performance for "contains" style queries [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6128:
URL: https://github.com/apache/arrow-rs/pull/6128#issuecomment-2256941105
I am still messing around with benchmarks (I had some problems with my scripts which I have now fixed). I expect results to complete soon
--
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] Improve `LIKE` performance for "contains" style queries [arrow-rs]
Posted by "samuelcolvin (via GitHub)" <gi...@apache.org>.
samuelcolvin commented on PR #6128:
URL: https://github.com/apache/arrow-rs/pull/6128#issuecomment-2254497323
I can the benchmarks on the exact same spec of GCP machine (`c2-standard-8`), and got slightly different results:
```
group contains-performance master
----- -------------------- ------
ilike_utf8 scalar complex 1.00 305.2±1.28µs ? ?/sec 1.00 305.7±0.70µs ? ?/sec
ilike_utf8 scalar contains 1.11 1685.4±4.02µs ? ?/sec 1.00 1515.0±8.44µs ? ?/sec
ilike_utf8 scalar ends with 1.00 233.9±0.71µs ? ?/sec 1.00 234.3±0.31µs ? ?/sec
ilike_utf8 scalar equals 1.16 248.6±0.28µs ? ?/sec 1.00 214.2±0.27µs ? ?/sec
ilike_utf8 scalar starts with 1.11 279.6±0.95µs ? ?/sec 1.00 251.2±0.28µs ? ?/sec
ilike_utf8_scalar_dyn dictionary[10] string[4]) 1.00 49.1±0.22µs ? ?/sec 1.79 88.0±0.15µs ? ?/sec
like_utf8 scalar complex 1.00 287.3±1.08µs ? ?/sec 1.00 288.4±0.90µs ? ?/sec
like_utf8 scalar contains 1.23 458.9±11.91µs ? ?/sec 1.00 373.6±0.36µs ? ?/sec
like_utf8 scalar ends with 1.00 234.4±0.21µs ? ?/sec 1.00 234.3±0.54µs ? ?/sec
like_utf8 scalar equals 1.00 217.1±0.20µs ? ?/sec 1.00 217.1±0.20µs ? ?/sec
like_utf8 scalar starts with 1.00 234.4±0.59µs ? ?/sec 1.08 253.5±0.24µs ? ?/sec
like_utf8_scalar_dyn dictionary[10] string[4]) 1.00 49.0±0.07µs ? ?/sec 1.80 88.0±0.15µs ? ?/sec
like_utf8view scalar complex 1.01 531.2±1.22ms ? ?/sec 1.00 523.6±3.52ms ? ?/sec
like_utf8view scalar contains 1.00 134.6±0.37ms ? ?/sec 2.97 399.7±0.46ms ? ?/sec
like_utf8view scalar ends with 1.01 59.0±0.21ms ? ?/sec 1.00 58.5±0.12ms ? ?/sec
like_utf8view scalar equals 1.03 30.1±0.05ms ? ?/sec 1.00 29.4±0.09ms ? ?/sec
like_utf8view scalar starts with 1.00 54.0±0.12ms ? ?/sec 1.02 55.2±0.13ms ? ?/sec
nilike_utf8 scalar complex 1.00 304.9±0.70µs ? ?/sec 1.00 305.2±0.59µs ? ?/sec
nilike_utf8 scalar contains 1.12 1684.7±5.21µs ? ?/sec 1.00 1509.5±5.93µs ? ?/sec
nilike_utf8 scalar ends with 1.00 234.2±1.14µs ? ?/sec 1.00 234.2±0.50µs ? ?/sec
nilike_utf8 scalar equals 1.16 248.7±0.32µs ? ?/sec 1.00 214.2±0.43µs ? ?/sec
nilike_utf8 scalar starts with 1.11 279.5±0.26µs ? ?/sec 1.00 251.3±0.47µs ? ?/sec
nlike_utf8 scalar complex 1.00 285.8±0.44µs ? ?/sec 1.01 287.2±0.62µs ? ?/sec
nlike_utf8 scalar contains 1.24 461.9±10.51µs ? ?/sec 1.00 373.9±0.67µs ? ?/sec
nlike_utf8 scalar ends with 1.00 234.2±0.20µs ? ?/sec 1.00 234.3±0.25µs ? ?/sec
nlike_utf8 scalar equals 1.00 217.1±0.20µs ? ?/sec 1.00 217.0±0.25µs ? ?/sec
nlike_utf8 scalar starts with 1.00 234.3±0.22µs ? ?/sec 1.08 253.6±0.36µs ? ?/sec
```
The only cases which should have changed in this PR are:
```
group contains-performance master
----- -------------------- ------
like_utf8 scalar contains 1.23 458.9±11.91µs ? ?/sec 1.00 373.6±0.36µs ? ?/sec
like_utf8view scalar contains 1.00 134.6±0.37ms ? ?/sec 2.97 399.7±0.46ms ? ?/sec
nlike_utf8 scalar contains 1.24 461.9±10.51µs ? ?/sec 1.00 373.9±0.67µs ? ?/sec
```
I'll try to work out why the first and last are marginally slower with this PR.
--
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