apache / apache/datafusion-comet
Run rlike natively by default for patterns that are provably Java-regex equivalent
- Dominant language
- Scala
- Stars
- 1.3k
- Forks
- 373
- Avg merge
- 2d 4h
- Merged PRs (30d)
- 198
Description
## Summary
`rlike` has a native Rust kernel already, but it is `Incompatible` and therefore off by default, so
every `rlike` predicate runs on the JVM codegen dispatcher. Measured from the emitted kernel, that
costs **seven heap allocation sites per non-null row**, four of them inside a single
`Pattern.matcher()` call.
The blocker is not the kernel, it is that the compatibility decision is made **per engine** rather
than **per pattern**. Comet already knows the pattern at plan time in the common case (it must be a
`Literal` for the native path to apply at all), and this repo's own
[regex compatibility guide](https://github.com/apache/datafusion-comet/blob/main/docs/source/user-guide/latest/compatibility/regex.md)
already enumerates exactly which constructs diverge. Encoding that enumeration as a plan-time
analyzer would let the provably-equivalent subset run natively **by default**, with everything else
staying on the dispatcher.
Assessed with the `suggest-native-expression` skill: **compatibility confidence Medium** (with a
plan-time guard), **native upside High** (measured). This is the cheapest High-upside item assessed so
far, because no native kernel needs writing.
### Relationship to #4310
[#4310](https://github.com/apache/datafusion-comet/issues/4310) concluded that "the Rust regex engine
**can never be fully Spark/Java-regex compatible**", and that is correct as stated: no blanket
engine-level flip is possible. This issue proposes a different axis. A *specific literal pattern* can
often be proven equivalent even when the *engine* cannot. #4310 discussed the config surface
(engine-level versus per-expression opt-in) and did not consider per-pattern analysis, so this is not
a re-litigation of that decision.
## How it runs today
`object CometRLike extends CometExpressionSerde[RLike] with NativeOptInAvailable`
(`spark/src/main/scala/org/apache/comet/serde/strings.scala:368`).
- `getSupportLevel` returns `Compatible(nativeOptIn = Some(...))` when the pattern is a literal and
the user has not opted in, so the dispatcher runs and EXPLAIN advertises the opt-in.
- `getIncompatibleReasons()` is a single blanket string: "Uses Rust regexp engine, which has different
behavior to Java regexp engine".
- `nativeApplicable` checks only **whether the pattern is a literal**, never what the pattern
contains. So a pattern of `^abc[0-9]+$`, which both engines agree on, is treated exactly like
`(?<=foo)bar`, which Rust cannot compile at all.
Gated by `spark.comet.expression.RLike.allowIncompatible` (default false) and
`spark.comet.exec.scalaUDF.codegen.enabled` (default true).
## Native upside: High (measured)
Dumped the real kernel for `RLike(BoundReference(0, StringType), Literal("^abc[0-9]+"))` over a
nullable `VarCharVector` via `CometBatchKernelCodegen.generateSource`. The emitted hot loop:
```java
private java.util.regex.Pattern[] mutableStateArray_0 = new java.util.regex.Pattern[1];
...
for (int i = 0; i < numRows; i++) {
...
UTF8String value_1 = ...; // zero-copy, UTF8String.fromAddress
value_0 = mutableStateArray_0[0].matcher(value_1.toString()).find(0);
...
}
```
To be clear about what is **not** a cost: the `Pattern` is compiled once into mutable state, not per
row, and the input string read is zero-copy. The per-row cost is entirely in `toString()` and
`matcher()`:
| Source | Allocation |
| --- | --- |
| `UTF8String.toString()` → `getBytes()` (copying branch, since the dispatcher hands it an off-heap `fromAddress` string) | `byte[]` |
| `new String(bytes, UTF_8)` | `String` header |
| ″ | the String's internal `byte[]` |
| `Pattern.matcher(...)` | `Matcher` object |
| `Matcher` ctor (`Matcher.java`, JDK 17) | `groups = new int[max(capturingGroupCount,10)*2]`, so `int[20]` minimum |
| ″ | `locals = new int[parent.localCount]` |
| ″ | `localsPos = new IntHashSet[parent.localTCNCount]` |
Seven allocation sites per non-null row. Escape analysis can scalar-replace some of the short-lived
ones, so treat seven as the upper bound on object churn rather than a guaranteed count. The native
path allocates none of it: the match runs over the Arrow values buffer directly.
`rlike` is also among the most common predicates in real analytics SQL, and unlike the other
candidates assessed so far there is a **multiplier**: the same analyzer immediately unlocks
`regexp_replace`, `split`, `regexp_extract`, and `regexp_extract_all`, which are all
`NativeOptInAvailable` for exactly the same reason.
Honest limits:
- No `rlike` usage in `benchmarks/tpc/queries/`, so workload presence is a judgment call.
- The end-to-end dispatcher-versus-native A/B is **not** measured here, because it needs a release
build of the native library. It is cheap for whoever picks this up, since both paths already exist:
run `CometRegExpBenchmark` with and without `spark.comet.expression.RLike.allowIncompatible=true`.
That measurement belongs in the implementing PR.
## Compatibility assessment: Medium (plan-time pattern analyzer as the guard)
### Spark versions
`RLike` is identical on 3.4.3 and 3.5.9. Spark 4.0.4 adds `collationRegexFlags` to both
`Pattern.compile` call sites, and 4.0.4, 4.1.3, and 4.2.0 are identical to each other. So the only
cross-version change is collation-driven, which the analyzer must account for (below).
### The divergence list is already written down
`docs/source/user-guide/latest/compatibility/regex.md` enumerates it. Every item is detectable by
inspecting the literal pattern:
**Rust cannot compile these at all** (reject):
- Backreferences (`\1`, `\k`)
- Lookahead / lookbehind (`(?=`, `(?!`, `(?<=`, `(?`)
- Possessive quantifiers (`*+`, `++`, `?+`, `{n,m}+`)
- Embedded code, conditionals, recursion (`(?(cond)`, `(?R)`)
**Both compile but semantics differ** (reject, or normalize):
- `\d`, `\w`, `\s`, `.` are Unicode-aware by default in Rust and ASCII-only in Java. Rejecting is the
safe first move; a follow-up could normalize by emitting `(?-u)` for the Rust engine, which is
exactly Java's default, but that needs its own correctness work and should not be in the first PR.
- Multiline mode `(?m)`: Java treats `\r`, `\r\n`, and extra Unicode separators as line boundaries,
Rust only `\n`.
- `(?i)`: Java folds ASCII by default, Rust does full Unicode simple case folding under Unicode mode.
- `\p{Alpha}`-style Java shorthand (Rust wants POSIX `[[:alpha:]]`), and `\p{...}` property sets that
do not line up.
- Java's `\uXXXX` and `\0nnn` escapes, which Rust does not accept in that form.
**Comet-specific** (reject):
- Non-default collation on Spark 4.0+, since `collationRegexFlags` can inject
`CASE_INSENSITIVE | UNICODE_CASE` into the Java pattern and the native path does not propagate
collation ([#4496](https://github.com/apache/datafusion-comet/issues/4496)).
This is why the rating is Medium rather than High: the *list* is enumerable, but "provably equivalent"
is a subtle claim and the analyzer has to be conservative by construction. The guard is sound in the
safe direction though: anything the analyzer does not positively recognize keeps today's behavior.
## Proposed approach
Mirror `CometCast`. `org.apache.comet.expressions.CometCast` is already a per-case compatibility
oracle that answers `Compatible` / `Incompatible` / `Unsupported` for each type pair, and the cast
serde consults it. Do the same for regex patterns.
1. Add `org.apache.comet.expressions.CometRegex` with
`def supportLevel(pattern: String, collationId: Int, flavor: RegexFlavor): SupportLevel`,
implementing the reject list above as a scanner over the pattern. Conservative by default: an
unrecognized construct is `Incompatible`, not `Compatible`.
2. Have `CometRLike.getSupportLevel` consult it for a literal pattern. In-subset patterns become
`Compatible(None)` and take the native path **by default**. Out-of-subset patterns keep exactly
today's behavior: `Compatible(nativeOptIn = ...)`, dispatcher by default, native on opt-in.
3. Keep the blanket `getIncompatibleReasons()` entry, since it still describes the opt-in path for
out-of-subset patterns, and add a compatible note explaining that in-subset literal patterns now
run natively.
4. Build a differential test corpus: a list of patterns crossed with inputs, asserted equal between
the dispatcher and native paths. The patterns from `regex.md` are the seed. This corpus is the real
deliverable, because it is what makes the analyzer trustworthy.
5. Once `rlike` is proven, apply the same oracle to `regexp_replace`, `split`, `regexp_extract`, and
`regexp_extract_all` in follow-ups. `split` needs one extra rule for the documented empty-match
divergence.
### Non-goals
- Normalizing patterns for the Rust engine (for example emitting `(?-u)` to force ASCII classes). The
first PR should reject rather than rewrite.
- Any collation propagation work; non-default collations are simply out of subset.
- Non-literal patterns. Those stay on the dispatcher, as today.
- Changing the `allowIncompatible` config surface, which is what #4310 covered.
## Acceptance criteria
- A pattern corpus test asserting the native and dispatcher paths agree for every pattern the analyzer
admits, including the ASCII / non-ASCII input axis.
- Patterns outside the subset demonstrably still route to the dispatcher (assert on the
`[COMET-INFO: JVM codegen dispatcher: ...]` EXPLAIN segment).
- Non-default collation on Spark 4.x is out of subset, with a test.
- `CometRegExpBenchmark` numbers for in-subset patterns, dispatcher versus native, in the PR
description.
- The `rlike` entry in `docs/source/contributor-guide/expression-audits/predicate_funcs.md` and the
engine-choice table in `compatibility/regex.md` updated to describe the new default.
---
Filed by the `suggest-native-expression` skill. Motivation:
[Native Coverage for Codegen-Dispatched Expressions](https://github.com/apache/datafusion-comet/blob/main/docs/source/contributor-guide/roadmap.md#native-coverage-for-codegen-dispatched-expressions).
Assessment recorded in `docs/source/contributor-guide/expression-audits/predicate_funcs.md` under
`## rlike`. Earlier runs of the same skill produced #5347 and #5349.
Contributor guide
Assessment
This issue has not been assessed yet.