xiangfu0 opened a new pull request, #18754: URL: https://github.com/apache/pinot/pull/18754
## Problem `REGEXP_LIKE` backed by an **FST index** resolves matches by walking the query automaton over the FST, in `RegexpMatcher` (case-sensitive) and `RegexpMatcherCaseInsensitive` (the IFST variant). On a high-cardinality, long-string column, a broad regexp — anything containing `.*` — visits a huge number of paths because the `.*`-prefixed automaton forces a walk of essentially the whole FST regardless of how few entries actually match. Three issues in that traversal combined to turn this memory pressure into **server-wide heap OOMs** (observed in production: ~30 such queries within a second saturated server heap, all query threads pinned in the loop, JVM killed): 1. **Dead per-path prefix copy.** Every pushed path allocated a fresh `IntsRefBuilder` and copied the entire accumulated input prefix into it (`newInput.copyInts(...)` per arc) — an `O(paths × key-length)` allocation. The prefix was **write-only**: it was never read to produce the result (only the FST output / dict id is). It was vestigial from Lucene's suggester-oriented `FSTUtil.intersectPrefixPaths`, which Pinot's matcher was adapted from. 2. **Whole result set retained on heap.** Matches were accumulated as `Path` objects in an `endNodes` list until the traversal finished, then materialized into a boxed `List<Long>`, then copied again into the result bitmap — holding every match (plus copied FST arcs) live before anything was returned. 3. **Uninterruptible loop.** The `while` loop never checked for query termination, so OOM protection, the query deadline, and thread interrupt could not stop it. The JVM died instead of the offending query. ## Changes - Removed the unused `_input` prefix tracking from both matchers (fixes #1). - `regexMatch` now takes an `IntConsumer` and emits each matched dict id as soon as a final state is reached; `LuceneFSTIndexReader` / `LuceneIFSTIndexReader` pass `bitmap::add`, so matches go straight into the `MutableRoaringBitmap` with no intermediate `List`/`Path` retention (fixes #2). - The traversal loop calls `QueryThreadContext.checkTerminationAndSampleUsagePeriodically(...)`, and the readers rethrow `QueryException` unwrapped so a kill/timeout/interrupt is honored instead of being swallowed into a logged `RuntimeException` (fixes #3). No on-disk format change — this is purely the query-time walker. Public `getDictIds(String)` signature is unchanged. ## Benchmark New `BenchmarkFSTRegexpMatcher` (pinot-perf), 500k keys × 40-char column, `-prof gc`. `gc.alloc.rate.norm` (bytes/op, deterministic, ±0.01% error) is the headline: | Path | regex | alloc before | alloc after | Δ alloc | time before | time after | |---|---|---|---|---|---|---| | FST | `.*` | 206 MB/op | 67 MB/op | **−67%** | 62.7 ms | 18.7 ms | | FST | `.*9999` | 193 MB/op | 67 MB/op | **−66%** | 27.2 ms | 19.7 ms | | FST | `key0001.*` (selective) | 43.0 KB/op | 42.4 KB/op | −1% | 0.015 ms | 0.014 ms | | IFST | `.*` | 299 MB/op | 134 MB/op | **−55%** | 74.8 ms | 30.0 ms | | IFST | `.*9999` | 234 MB/op | 108 MB/op | **−54%** | 33.1 ms | 29.5 ms | | IFST | `key0001.*` (selective) | 43.1 KB/op | 42.5 KB/op | −1% | 0.015 ms | 0.015 ms | Broad regexes allocate **55–67% less**; selective queries are unchanged. ## Testing - Existing `FSTBuilderTest`, `IFSTBuilderTest`, `LuceneFSTIndexCreatorTest` pass. - Existing end-to-end `FSTBasedRegexpLikeQueriesTest` / `IFSTBasedRegexpLikeQueriesTest` (pinot-core) pass. - Added regression tests: full `.*` enumeration through the new consumer path, and an interrupt mid-match surfaces `EarlyTerminationException` both from the matcher directly and through `LuceneFSTIndexReader` / `LuceneIFSTIndexReader#getDictIds`. -- 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]
