Does there exist a data structure with the following properties. Given a string $s$, it performs some polynomial amount of precomputation to construct the data structure. After construction, it allows searching $s$ for arbitrary regular expression patterns in time sublinear in the length of $s$, ideally constant or logarithmic. Ideally, the runtime would only depend polynomially on the length of the regex pattern being searched. Is anything known about this? If not, what is the closest one can come?
Consider the following setup. Let $s$ be a string in the pattern
<w1><w2>... for words $w_1, w_2, \dots$ that don't include
<> in their alphabet. Now with the regex
.*<w>.* we can check the existence of a word in the 'database' $s$. Better yet, we can substitute arbitrary characters of $w$ with a wildcard symbol
This gives a reduction from Lower bounds for high dimensional nearest neighbor search and related problems by Borodin et. al. where it's shown that constant time queries with polynomial space is impossible.
A stronger conjecture is provided, which would answer your question negatively altogether:
The common “wisdom” among researchers is that simultaneously getting $poly(nd)$ storage and $poly(d)$ search time is impossible. Moreover, it has been conjectured that either storage or search time must grow exponentially in $d$ (at least for certain values of $n$). This conjecture is known as the curse of dimensionality.
 K. Clarkson. An algorithm for approximate closest-point queries. In Proc. of 10th SCG, pp.160–164, 1994.
Here $n$ is the number of strings and $d$ is the size of each string, thus $nd \sim |s|$.
It seems to me that your problem is very close to pattern matching in compressed text, which is an active area of research. It consists in searching given patterns in compressed strings, without decompressing them. It is then faster than parsing the strings.
I am not an expert, but the following seems to be a good reference: Practical and flexible pattern matching over Ziv–Lempel compressed text by Gonzalo Navarro and Mathieu Raffinot.