You are viewing a plain text version of this content. The canonical link for it is here.

Posted to github@datafusion.apache.org by "Dandandan (via GitHub)" <gi...@apache.org> on 2026/05/19 06:51:35 UTC

[PR] perf: generic literal-prefix fast path for regexp_replace `${1}` [datafusion]

Dandandan opened a new pull request, #22354:
URL: https://github.com/apache/datafusion/pull/22354

   ## Which issue does this PR close?
   
   <!-- No issue yet; happy to file one if preferred. -->
   
   - Closes #.
   
   ## Rationale for this change
   
   `OptimizedRegex` (introduced for ClickBench Q28-style patterns) already handles `^...(capture).*$` → `${1}` by stripping the trailing `.*$` and running the shortened regex with reusable `CaptureLocations`. That avoids `expand()` and string allocation, but still pays for full regex matching on every row.
   
   For the common subset where the regex up to the capture reduces to a **finite set of literal byte prefixes** and the capture has the form `([^X]+)X` for a single ASCII byte `X`, we can do strictly better: parse the pattern's HIR once at planning time, enumerate the literal prefix variants, and dispatch each row to a `memchr`-based extractor — no regex engine involvement per row.
   
   Patterns that fit this shape:
   
   | Pattern | Prefix variants | Terminator |
   |---|---|---|
   | `^https?://(?:www\.)?([^/]+)/.*$` (ClickBench Q28) | `https://www.`, `http://www.`, `https://`, `http://` | `/` |
   | `^foo:([^,]+),.*$` | `foo:` | `,` |
   | `^(?:foo\|bar\|baz):([^/]+)/.*$` | `bar:`, `baz:`, `foo:` | `/` |
   
   Any pattern that doesn't fit (case-insensitive, multiline, non-ASCII terminator, unbounded prefix) falls back to the existing `ShortenedRegex` path with no change.
   
   ## Performance
   
   Measured on ClickBench Q28 (`REGEXP_REPLACE(\"Referer\", '^https?://(?:www\.)?([^/]+)/.*\$', '\1')`, partitioned dataset, `dfbench --iterations 5 --query 28`, same machine):
   
   | Build | Avg ms | Delta |
   |---|---:|---:|
   | Upstream main (shortened-regex only) | 4577.52 | baseline |
   | Literal-prefix fast path | 2225.00 | **-51.4%** |
   
   Per-iteration:
   
   - Upstream:        4294.1, 4426.0, 4431.4, 5035.1, 4701.0
   - Literal-prefix:  2417.5, 2178.1, 2244.0, 2154.8, 2130.6
   
   ## What changes are included in this PR?
   
   - New `LiteralPrefixCaptureSpec` variant of the internal `ShortRegex` enum, holding a deduplicated longest-first list of literal prefixes plus a single-byte terminator.
   - `try_recognize_literal_prefix_capture(pattern)` parses the pattern with `regex-syntax::parse`, walks the HIR, enumerates prefix variants (bounded by `MAX_PREFIX_VARIANTS = 32`), and verifies the capture is greedy `[^X]+` followed by a literal `X`, `.*`, `\$`.
   - Runtime extractor probes prefixes longest-first; on empty-capture failure (the longest prefix consumes bytes the capture needs) it falls back to shorter prefixes. That preserves the full regex's backtracking semantics for cases like `http://www./path` against the Q28 pattern, where the regex prefers to leave `www.` outside the optional so the capture is non-empty.
   - New transitive direct dep: `regex-syntax` (already pulled in via `regex`, version pinned to `0.8`). Wired through the `regex_expressions` feature so it's only compiled when `regex` is.
   
   ## Are these changes tested?
   
   New unit tests in `datafusion-functions::regex::regexpreplace::tests`:
   
   - `literal_prefix_recognizer_accepts_clickbench_q28` — exact prefix list and terminator for the Q28 pattern.
   - `literal_prefix_recognizer_accepts_single_literal` and `_accepts_alternation` — basic shapes.
   - `literal_prefix_recognizer_rejects_non_anchored`, `_rejects_unbounded_prefix`, `_rejects_non_ascii_terminator`, `_rejects_case_insensitive` — guardrails on what the recognizer will and won't accept.
   - `literal_prefix_fast_path_matches_full_regex_for_q28_pattern` and `_for_alternation_pattern` — differential tests that run the optimized path and the full `regex::Regex` on the same inputs (including edge cases like `http://www./path`, embedded `\n`, empty captures, and non-matching inputs) and assert byte-equal output.
   
   ```
   cargo test -p datafusion-functions --lib regex::regexpreplace
   cargo clippy -p datafusion-functions --all-targets --all-features -- -D warnings
   ```
   
   All 22 tests in this module pass (13 pre-existing + 9 new).
   
   ## Are there any user-facing changes?
   
   No. `regexp_replace` semantics are unchanged — any input that wouldn't go through the fast path follows the exact same code as before, and inputs that do go through the fast path are differentially tested against the full regex.


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org