Do 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.