yongster opened a new issue, #11084: URL: https://github.com/apache/arrow-rs/issues/11084
### Is your feature request related to a problem or challenge? Array/array `LIKE` / `ILIKE` / `NLIKE` / `NILIKE` go through `binary_predicate`, which only caches the **immediately previous** pattern: https://github.com/apache/arrow-rs/blob/master/arrow-string/src/like.rs Consecutive identical patterns reuse the compiled `Predicate`. Two or more complex (Regex-backed) patterns that alternate — or any low-cardinality pattern column that is not grouped — re-run `regex_like` + `RegexBuilder::build` on almost every row. That makes performance depend on row order even when the logical workload has only a few distinct patterns. Dictionary-encoded pattern columns do not help today: `string_apply` unpacks dictionary values and still goes through `binary_predicate` with the decoded `&str`. The scalar path already builds one `Predicate` and is fine. Simple patterns (`%foo`, `foo%`, `%foo%`, exact match) do not compile a Regex, so they are not the problem. `Predicate::like` only uses `Regex` when the pattern is not a pure prefix/suffix/contains/equality form (`%x_x%x` and `x%_x%` both take that path). ### Describe the solution you'd like - Keep the current previous-pattern fast path so consecutive duplicates do not pay an extra lookup. - Add a small **bounded** cache of compiled `Predicate`s keyed by borrowed `&str` from the pattern array (no string copies). - Once the cache is full, evaluate additional patterns without retaining them, so a fully unique column cannot accumulate an unbounded number of `Regex` values. - The previous-pattern slot should remain valid even for a pattern that was not inserted into the bounded cache (otherwise a consecutive run of an uncached pattern would recompile every row). - Apply to `like` / `nlike` / `ilike` / `nilike` array/array only. Do not change the scalar path. - Tests across LIKE/NLIKE/ILIKE/NILIKE, Utf8 / LargeUtf8 / Utf8View, dictionary, nulls, and invalid patterns. - Benchmarks for: consecutive complex, alternating low-cardinality complex, simple alternating, and all-unique complex. Cache capacity should be chosen from those (2/4/8/16), not guessed. Independent remeasurement of the **current** kernel on arm64 macOS against `381eea177`, 1,024 rows of `"xxxxxxxx"`: | Case | Current time | |---|---:| | LIKE, one complex pattern, consecutive | 40.8 µs | | LIKE, two complex patterns, alternating | 22.55 ms | | ILIKE, two complex patterns, alternating | 22.91 ms | | LIKE, two simple patterns (`x%` / `%x`), alternating | 13.2 µs | | LIKE, 1,024 unique complex patterns | 19.67 ms | | LIKE, dictionary-encoded two complex patterns, alternating | 22.22 ms | The two-pattern alternating case is ~550× slower than the same two patterns laid out consecutively. That gap is almost entirely repeated Regex compilation; a bounded cache of size ≥ 2 recovers it. Simple patterns are already fast. All-unique stays ~20 ms, so a bounded cache must not try to remember every pattern. ### Describe alternatives you've considered - Unbounded `HashMap<&str, Predicate>`. Simple, but a unique pattern per row would hold 1,024 compiled Regex values for the duration of the call. - Using dictionary keys as cache indices when the pattern array is a dictionary. That would be even better for the dictionary case, but it does not help a plain `StringArray` with low cardinality, and `binary_predicate` currently never sees the keys. Can be a follow-up. - Sorting or grouping the pattern column first. That is a caller concern and not acceptable as the kernel's only defense. - Changing `Predicate::like` itself. The scalar path is already one compile; the bug is the array/array reuse policy. ### Additional context #5951 (StringView prefix specialization) and #6107 (memchr / `starts_with` / `icontains`) are related string-search work but do not cache array/array LIKE patterns. The in-tree `comparison_kernels` bench covers scalar LIKE/ILIKE, not array/array with repeating patterns. A PR should add those cases. I can open a focused PR for `binary_predicate`. -- 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]
