String search kernel optimisations
- Dominant language
- Rust
- Stars
- 3.6k
- Forks
- 1.3k
- Avg merge
- 2d 16h
- Merged PRs (30d)
- 168
Description
The main context for this is well described by https://github.com/BurntSushi/memchr/pull/156.
I think (in rough order of impact) we should:
* [x] switch from `str.contains` to [memchr](https://docs.rs/memchr/latest/memchr/)
* [ ] switch from `str.starts_with` to to hopefully `memchr`, otherwise [`quick_strings::starts_with`](https://github.com/samuelcolvin/quick-strings/blob/d4c6d9567c35361cd66e5c1c3877f1b9a73751f9/src/lib.rs#L15) - there's no "what if the haystack is very long" concern since we're looking at the start of the string, so the difference between `memchr` and `quick_strings` won't be as big, or even might be negative
* [ ] switch from using `starts_with_ignore_ascii_case` to [`quick_strings::istarts_with`](https://github.com/samuelcolvin/quick-strings/blob/d4c6d9567c35361cd66e5c1c3877f1b9a73751f9/src/lib.rs#L24)
* [ ] same for `*ends_with`
* [ ] switch from Regex to use [`quick_strings::icontains`](https://github.com/samuelcolvin/quick-strings/blob/d4c6d9567c35361cd66e5c1c3877f1b9a73751f9/src/lib.rs#L9) (copying the code) for `ILIKE` - maybe we have to check it's actually faster for large haystacks? - this might have the biggest impact in some scenarois, but me should be careful
* [ ] to use those improvements, switch from [some direct use of `str.contains` etc in `like.rs`](https://github.com/apache/arrow-rs/blob/af40ea382275dba967bfabc1632fded07d2129b9/arrow-string/src/like.rs#L276-L278) to use `Predicate`
(I'm not suggesting that we make `quick_strings` a dependency, it was just a scratch experiment, if we use any of that code we should copy it.
Contributor guide
Research direction
Start with arrow-string/src/like.rs, especially the direct str.contains and related calls referenced in the issue, then read the Predicate implementation and the linked memchr and quick_strings examples. Work through the unchecked contains, starts_with, ends_with, case-insensitive, and ILIKE items, checking performance where the issue calls for it. Done means the relevant paths use the optimized string operations without adding quick_strings as a dependency.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- performance
- Issue type
- Refactor
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 55/100