xiangfu0 commented on code in PR #18759:
URL: https://github.com/apache/pinot/pull/18759#discussion_r3411951607
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/utils/fst/RegexpMatcher.java:
##########
@@ -59,97 +70,90 @@ public boolean match(String input) {
return characterRunAutomaton.run(input);
}
- /**
- * This function runs matching on automaton built from regexQuery and the
FST.
- * FST stores key (string) to a value (Long). Both are state machines and
state transition is based on
- * a input character.
- *
- * This algorithm starts with Queue containing (Automaton Start Node, FST
Start Node).
- * Each step an entry is popped from the queue:
- * 1) if the automaton state is accept and the FST Node is final (i.e.
end node) then the value stored for that FST
- * is added to the set of result.
- * 2) Else next set of transitions on automaton are gathered and for each
transition target node for that character
- * is figured out in FST Node, resulting pair of (automaton state, fst
node) are added to the queue.
- * 3) This process is bound to complete since we are making progression
on the FST (which is a DAG) towards final
- * nodes.
- * @return
- * @throws IOException
- */
- public List<Long> regexMatchOnFST()
+ /// This function runs matching on automaton built from regexQuery and the
FST.
+ /// FST stores key (string) to a value (Long). Both are state machines and
state transition is based on an input
+ /// character.
+ ///
+ /// This algorithm starts with a stack containing (Automaton Start Node, FST
Start Node).
+ /// Each step an entry is popped from the stack (DFS order to bound the
frontier size):
+ /// 1) if the automaton state is accept and the FST Node is final (i.e.
end node) then the value stored for that
+ /// FST node is emitted to the consumer.
+ /// 2) Else next set of transitions on automaton are gathered and for each
transition target node for that
+ /// character is figured out in FST Node, resulting pair of (automaton
state, fst node) are added to the stack.
+ /// 3) This process is bound to complete since we are making progression
on the FST (which is a DAG) towards final
+ /// nodes.
+ ///
+ /// A broad regexp on a high-cardinality column can visit a huge number of
paths, so the loop periodically checks
+ /// for query termination (timeout or OOM-protection kill) to remain
interruptible.
+ public void regexMatchOnFST(IntConsumer dictIdConsumer)
+ throws IOException {
+ regexMatchOnFST(dictIdConsumer, Integer.MAX_VALUE);
+ }
+
+ /// Same as [#regexMatchOnFST(IntConsumer)] but throws
[FSTTraversalLimitExceededException] once `maxPaths` FST
+ /// paths have been visited.
+ public void regexMatchOnFST(IntConsumer dictIdConsumer, int maxPaths)
throws IOException {
- final List<Path<Long>> queue = new ArrayList<>();
- final List<Path<Long>> endNodes = new ArrayList<>();
if (_automaton.getNumStates() == 0) {
- return Collections.emptyList();
+ return;
}
- // Automaton start state and FST start node is added to the queue.
- queue.add(new Path<>(0, _fst.getFirstArc(new FST.Arc<Long>()),
_fst.outputs.getNoOutput(), new IntsRefBuilder()));
+ // Automaton start state and FST start node is added to the stack.
+ List<Path<Long>> stack = new ArrayList<>();
+ stack.add(new Path<>(0, _fst.getFirstArc(new FST.Arc<>()),
_fst.outputs.getNoOutput()));
- final FST.Arc<Long> scratchArc = new FST.Arc<>();
- final FST.BytesReader fstReader = _fst.getBytesReader();
+ FST.Arc<Long> scratchArc = new FST.Arc<>();
+ FST.BytesReader fstReader = _fst.getBytesReader();
Transition t = new Transition();
- while (!queue.isEmpty()) {
- final Path<Long> path = queue.remove(queue.size() - 1);
-
- // If automaton is in accept state and the fstNode is final (i.e. end
node) then add the entry to endNodes which
- // contains the result set.
- if (_automaton.isAccept(path._state)) {
- if (path._fstNode.isFinal()) {
- endNodes.add(path);
- }
+ int numPathsProcessed = 0;
+ while (!stack.isEmpty()) {
+ if (numPathsProcessed >= maxPaths) {
+ throw new FSTTraversalLimitExceededException(
+ "FST regexp traversal exceeded the limit of " + maxPaths + "
paths");
+ }
+
QueryThreadContext.checkTerminationAndSampleUsagePeriodically(numPathsProcessed++,
+ "RegexpMatcher#regexMatchOnFST");
Review Comment:
Fixed: both matchers now normalize `maxPaths <= 0` to unbounded
(`Integer.MAX_VALUE`) before the loop, so a non-positive value disables the cap
instead of throwing on the first node. Added FST+IFST tests asserting
`getDictIds(".*", 0)` and `-1` return all entries, and simplified the provider
so the matcher is the single source of truth.
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/predicate/PredicateEvaluatorProvider.java:
##########
@@ -27,14 +27,17 @@
import org.apache.pinot.common.request.context.predicate.Predicate;
import org.apache.pinot.common.request.context.predicate.RangePredicate;
import org.apache.pinot.common.request.context.predicate.RegexpLikePredicate;
+import org.apache.pinot.common.utils.config.QueryOptionsUtils;
import org.apache.pinot.core.query.request.context.QueryContext;
+import
org.apache.pinot.segment.local.utils.fst.FSTTraversalLimitExceededException;
Review Comment:
Fixed: moved `FSTTraversalLimitExceededException` to `pinot-segment-spi`
(`org.apache.pinot.segment.spi.index.reader`, next to `TextIndexReader`). It's
now part of the SPI contract and `pinot-core` no longer depends on a
`pinot-segment-local` type.
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/utils/fst/RegexpMatcher.java:
##########
@@ -20,25 +20,25 @@
import java.io.IOException;
import java.util.ArrayList;
-import java.util.Collections;
import java.util.List;
-import org.apache.lucene.util.IntsRefBuilder;
+import java.util.function.IntConsumer;
import org.apache.lucene.util.automaton.Automaton;
import org.apache.lucene.util.automaton.CharacterRunAutomaton;
import org.apache.lucene.util.automaton.RegExp;
import org.apache.lucene.util.automaton.Transition;
import org.apache.lucene.util.fst.FST;
import org.apache.lucene.util.fst.Util;
+import org.apache.pinot.spi.query.QueryThreadContext;
-/**
- * RegexpMatcher is a helper to retrieve matching values for a given regexp
query.
- * Regexp query is converted into an automaton and we run the matching
algorithm on FST.
- *
- * Two main functions of this class are
- * regexMatchOnFST() Function runs matching on FST (See function comments
for more details)
- * match(input) Function builds the automaton and matches given input.
- */
+/// RegexpMatcher is a helper to retrieve matching values for a given regexp
query.
+/// Regexp query is converted into an automaton, and we run the matching
algorithm on FST.
+///
+/// Two main functions of this class are
+/// regexMatchOnFST() Function runs matching on FST (See function comments
for more details)
+/// match(input) Function builds the automaton and matches given input.
+///
+/// This class is not thread-safe. Create a new instance (or use the static
helper) per query.
Review Comment:
`///` is JEP 467 markdown Javadoc, valid on Java 21 (which Pinot service
code targets) and used throughout the codebase; `mvn checkstyle:check` passes
on these files and they render in javadoc. Keeping for consistency with the
surrounding code.
##########
pinot-common/src/main/java/org/apache/pinot/common/utils/config/QueryOptionsUtils.java:
##########
@@ -711,6 +711,15 @@ public static Integer
getRegexDictSizeThreshold(Map<String, String> queryOptions
return uncheckedParseInt(QueryOptionKey.REGEX_DICT_SIZE_THRESHOLD,
regexDictSizeThreshold);
}
+ /// Cap on the number of FST paths visited per FST/IFST-backed REGEXP_LIKE
evaluation before falling back to the
+ /// dictionary-scan evaluator. Returns `null` if the query option is not
set, in which case
+ ///
[CommonConstants.Broker.Request.QueryOptionValue#DEFAULT_FST_REGEXP_TRAVERSAL_LIMIT]
applies.
+ @Nullable
+ public static Integer getFstRegexpTraversalLimit(Map<String, String>
queryOptions) {
+ String fstRegexpTraversalLimit =
queryOptions.get(QueryOptionKey.FST_REGEXP_TRAVERSAL_LIMIT);
+ return uncheckedParseInt(QueryOptionKey.FST_REGEXP_TRAVERSAL_LIMIT,
fstRegexpTraversalLimit);
+ }
Review Comment:
`///` is JEP 467 markdown Javadoc and is already used in this same file
(e.g. `isMaterializedViewRewriteEnabled`); `checkstyle:check` passes. Keeping
for consistency.
##########
pinot-segment-local/src/main/java/org/apache/pinot/segment/local/utils/fst/RegexpMatcher.java:
##########
@@ -48,9 +48,20 @@ public RegexpMatcher(String regexQuery, FST<Long> fst) {
_automaton = (new RegExp(regexQuery)).toAutomaton();
}
- public static List<Long> regexMatch(String regexQuery, FST<Long> fst)
+ /// Runs matching of the given regexp query on the FST, emitting the value
(dict id) of each matched entry to the
+ /// given consumer. Values are emitted as the traversal hits final states,
so the caller can collect them without
+ /// this class materializing the full result set in memory.
+ public static void regexMatch(String regexQuery, FST<Long> fst, IntConsumer
dictIdConsumer)
throws IOException {
- return new RegexpMatcher(regexQuery, fst).regexMatchOnFST();
+ regexMatch(regexQuery, fst, dictIdConsumer, Integer.MAX_VALUE);
+ }
Review Comment:
The `List<Long>` -> `IntConsumer` change already landed in merged #18754;
this PR only adds the bounded overload.
`RegexpMatcher`/`RegexpMatcherCaseInsensitive` are internal
`pinot-segment-local` utilities (not an SPI/public surface), and re-adding a
list-returning wrapper would reintroduce the unbounded allocation that change
removed. Leaving as-is, but happy to revisit if a maintainer wants a compat
shim.
--
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]
