[Someone]

I guess it would be more like 10000x or more.

Standard search works because any search will contain words that decrease the target space by several orders of magnitude (and of it does not, nobody Will notice if the search engine returns almost-random documents)

For the regexes that people would want to search with, decreasing the search space is infeasible. So, you would, effectively, have to grep large parts of the Internet. Even at Google, that would take serious time. It also would be expensive.

It is possible to limit the regex space and get reasonable run times, for example by requiring the regex to contain sufficiently infrequent character sequences with \w boundary delimiters. However, I expect any such limited set would be equally well served by a Google search followed by a client-side grep.

If you disagree, I would be interested in what regexes you would allow and how you would implement searching fotpr them.