alt Hacker NewsDo any RE implementations do anything like the query planning that databases do or the rewrites that compilers do that can replace the RE with a different sequence of REs or string searches that might execute faster?
For example in the expression in your example (I'm assuming based on your description of the test data that /d+s+/ means the same as /\d+\s+/ in the RE engines I've used) any match must contain a digit followed by a space.
A scan for all places where a digit is followed by whitespace with each such place then being checked to find the length of the string of whitespace starting there and the length of the string of digits ending there should be linear time and constant heap space.
Replies
You're correct, I accidentally omitted backslashes on \d and \s. I checked and the pattern was correct during the test.
Not an answer, but related, I was looking at Memgraph (graph db) query planning for Cypher, which is similar (ish) to what you are asking about:
https://memgraph.com/docs/querying/query-plan
The reason why I was looking was to do query planning for a declarative pattern-finding in atomic structures (hierarchical labelled graphs, I suppose) although I'm slowly realising just how insanely hard it might be to get it to work efficiently!