CompiledAutomaton performance for determining common suffix [LUCENE-8102]

[asfimport]

We're using the automaton package as part of Elasticsearch for doing regexp queries. Our business requires us to process rather complex regular expressions, for example (we have more complex examples, but this one illustrates the problem):

        (¦.)*(¦?[^¦]){1,10}ab(¦.)*(¦?[^¦]){1,10}c(¦.)*(¦?[^¦]){1,10}d

With a large enough value of maxDeterminizedStates, this works. The problem we're having is that the conversion of this regular expression to a CompiledAutomaton takes very long. Almost all of the time goes into determining the common suffix for the Automaton (which is "d" in this example) - calculated with a call to Operations.getCommonSuffixBytesRef.

This suffix is only used as an optimization. Skipping the calculation of this suffix allows us to process these kinds of queries.

• Would it be possible to introduce a way to skip the calculation of this common suffix (ideally something we control from within our query to Elasticsearch)?
• Or would it be possible to take a look at this getCommonSuffixBytesRef operation, to see if it can be optimized? Most of the time goes to determinizing the reversed automaton - maybe this can be avoided somehow?

Reaction from Mike McCandless on the mailing list: This is just an optimization; maybe we should expose an option to disable it? Or maybe we can find the common suffix on an NFA instead, to avoid determinization?

---

Migrated from LUCENE-8102 by Thomas Poppe

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

The optimization speeds up leading wildcard type-queries (such as wildcard "*foo" or regex ".*foo") which are far more common e.g. on the users list than the example presented on this issue, so I really think we should keep it.

The regex here is quite obscene, maybe its the thing that should be optimized? :)

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

Also here are few more ideas:

• There is a TODO in the code regarding using found sink state... a method findSinkState was added here and is actually called, but its not used to determine whether or not common suffix should be computed, but only if this really works (there should be some tests)
• The optimization could be guarded with a state count check maybe (something absurd).

Either way, I think its really important not to regress on common "stupid simple" queries like leading wildcards.