david-mollitor-db opened a new pull request, #59222:
URL: https://github.com/apache/spark/pull/59222
### What changes were proposed in this pull request?
This adds `ByteArrayMethods.contains(base, offset, length, subBase,
subOffset, subLength)`, a substring search over raw memory, and makes both
`UTF8String.contains` and `ByteArrayMethods.contains(byte[], byte[])` call it.
On platforms with unaligned access, the new search checks 8 candidate
positions per step:
- It XORs the 8-byte word at position `i` with the needle's first byte
repeated, and the word at `i + subLength - 1` with the needle's last byte
repeated.
- An exact zero-byte mask over the OR of the two marks the positions where
both the first and the last byte match. Only those positions compare the
remaining bytes. The mask uses `~(((x & 0x7F..7F) + 0x7F..7F) | x | 0x7F..7F)`
rather than the shorter `(x - 0x01..01) & ~x & 0x80..80`, because the shorter
form also flags a `0x01` byte just above a zero byte.
- The final word is moved back so that it ends at the last possible start
position, overlapping the previous word, so there is no byte-at-a-time tail.
Platforms without unaligned access use a byte loop that checks the first and
last bytes before the inner ones. Big-endian platforms reverse the candidate
mask so that positions are still tested in address order.
### Why are the changes needed?
`UTF8String.contains` backs `contains()` on strings and `LIKE '%...%'`,
which `LikeSimplification` rewrites to `Contains`.
`ByteArrayMethods.contains(byte[], byte[])` backs `contains()` on binary,
through `BinaryPredicate`. Both searched one byte at a time. Every position did
a bounds-checked `getByte`, and every position that matched the needle's first
byte paid a full `matchAt` / `arrayEquals` call. In profiles of scan queries
that filter strings, `getByte`, `matchAt` and `contains` took about 25-30% of
CPU.
Local JMH results (JDK 17, ns per row; JDK 25 showed the same pattern):
| Rows | Needle | master | this PR | Speedup |
|---|---|---|---|---|
| 128 bytes | not present | 129 | 24 | 5.5x |
| 128 bytes | starts with a space (frequent first byte) | 325 | 24 | 13.9x |
| 128 bytes | found in the middle | 99 | 23 | 4.2x |
| 1024 bytes | not present | ~1055 | 188 | ~5.6x |
| 16 bytes | not present | 10.2 | 4.7 | 2.2x |
| 128 bytes | rows of all `a`, needle `aQa` (every position a candidate) |
621 | 206 | 3.0x |
| 16 bytes | needle as long as the row (one position to check) | 3.1 | 3.2 |
unchanged |
The GitHub Actions benchmark workflow commits the results for the new `byte
array contains` section of `ByteArrayBenchmark` to this PR, in
`sql/core/benchmarks/ByteArrayBenchmark-*results.txt` (JDK 17, 21 and 25).
### Does this PR introduce _any_ user-facing change?
No. Only performance changes.
### How was this patch tested?
- New `ByteArrayMethodsSuite` compares `contains` with a naive search:
- It covers a match in every position of a word and in the overlapping
final word, near misses whose first and last bytes match, 20,000 random cases
over bytes such as `0x00`, `0x7F`, `0x80` and `0xFF`, and a fixed case that the
shorter zero-byte test gets wrong.
- Each case runs on heap at a non-zero offset, off heap, and through the
`byte[]` overload. Copies of the needle are placed right before and after the
haystack, so a read past either end would show up as a false match.
- The suite fails if the overlapping final word is dropped or if the
shorter zero-byte test is used instead.
- Existing `UTF8StringSuite`, `UTF8StringPropertyCheckSuite` (which checks
`contains` against `java.lang.String.contains`) and `ByteArraySuite` pass.
- Added a `byte array contains` section to `ByteArrayBenchmark`, with its
results regenerated by the GitHub Actions benchmark workflow for JDK 17, 21 and
25.
### Was this patch authored or co-authored using generative AI tooling?
Generated-by: Isaac (Claude Code, Claude Opus 5.5)
This pull request and its description were written by Isaac.
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
