xiangfu0 commented on PR #18759: URL: https://github.com/apache/pinot/pull/18759#issuecomment-4705550154
### CI fix `FilterPlanNodeTest` mocked `TextIndexReader.getDictIds(String)`, but the FST/IFST evaluators now call the bounded `getDictIds(String, int)` overload — the mock returned `null` for the new method, NPE-ing the evaluator. Stubbed the bounded overload in the test's `mockTextIndexReader()`. (All 9 `FilterPlanNodeTest` cases pass locally.) ### How the default (100,000) was chosen Added `FstTraversalLimitExperiment` (pinot-perf) which, across cardinalities, reports the exact number of FST paths each pattern visits (the unit the cap is in) alongside FST vs scan latency. 40-char keys, default `java.util.regex`: | cardinality | pattern | matches | paths visited | fst (ms) | scan (ms) | |---|---|---|---|---|---| | 10K | selectivePrefix | 100 | 149 | 0.24 | 0.73 | | 10K | matchAll `.*` | 10,000 | 11,147 | 0.93 | 0.95 | | 100K | selectivePrefix | 100 | 149 | 0.13 | 0.93 | | 100K | matchAll `.*` | 100,000 | 111,146 | 5.07 | 5.29 | | 1M | exact | 1 | 41 | 0.01 | 14.1 | | 1M | selectivePrefix | 100 | 149 | 0.15 | 13.5 | | 1M | broadSuffix (leading `.*`) | 100 | 1,111,145 | 38.2 | 75.7 | | 1M | matchAll `.*` | 1,000,000 | 1,111,145 | 40.4 | 52.3 | Takeaways that justify **100,000**: - A selective query's path count tracks its **match count**, not column cardinality (~150 paths for 100 matches at every cardinality) — so 100K leaves a ~1000× margin and never trips selective prefix/fuzzy queries. - A full/leading-`.*` walk visits **~1.1× cardinality** paths (note `broadSuffix` with 100 matches visits the same as `matchAll` — a leading `.*` always walks the whole FST). 100K trips these once cardinality exceeds ~90K, exactly where the FST walk stops being cheaper than a scan. - The transient allocation of a capped walk is bounded to ~15 MB. Caveat: the fallback's latency depends on the scan regex engine. `broadSuffix` here ended in `0000`, which java.util.regex finds instantly; a leading-`.*` matching a *rare* substring backtracks much harder and the scan fallback can be several× slower than the FST walk. Envs that rely on broad rare-substring regex should enable RE2J (`pinot.server.query.regex.class`) to keep the fallback fast. -- 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]
