apache / apache/arrow-rs

String search kernel optimisations

Open
#6,107 6 comments 6 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.