These work fine and return instantly:
python -c "import re;  re.compile('.*x').match('y'*(1000*100))"
python -c "import re;  re.compile('x').search('y'*(1000*100))"
python -c "import re;  re.compile('.*x').search('y'*(1000*10))"

This hangs / freezes / livelocks indefinitely, with lots of CPU usage:
python -c "import re;  re.compile('.*x').search('y'*(1000*100))"

Admittedly performing a search() with a pattern starting .* isn't useful, however it's worth fixing as:
- it's easily done by inexperienced developers, or users interacting with code that's far removed from the actual regex call
- the failure mode of hanging forever (with the GIL held, of course) is quite severe (took us a lot of debugging with gdb before we figured out where our complex multi-threaded python program was hanging!), and 
- the fact that the behaviour is different based on the length of the string being matched suggests there is some kind of underlying bug in how the buffer is handled whcih might also affect other, more reasonable regex use cases

Correction to original report - it doesn't hang indefinitely, it just takes a really long time. Specifically, looks like it's quadratic in the length of the input string. Increase the size of the input string to 1000*1000 and it's really really slow. 

I don't know for sure if it's possible to implement regexes in a way that avoids this pathological behaviour, but it's certainly quite risky that an otherwise working bit of code using a pattern containing .* can hang/livelock an application for an arbitrary  amount of time if passed a larger-than-expected (but actually not that big) input string.

Running this command:
time python -c "import re;  re.compile('y.*x').search('y'*(N))"

It's clearly quadratic:
N=100,000 time=7s
N=200,000 time=18s
N=400,000 time=110s
N=1,000,000 time=690s

This illustrates how a simple program that's working correctly can quickly degrade to a very long period of unresponsiveness after some fairly modest increases in size of input string.

Yes, it's quadratic time.  If the string being searched has N characters, first it fails to find "x" in all N of 'em, then `.*` advances by one and it fails to find "x" in the trailing N-1 characters, then again in the trailing N-2, and so on.  N + N-1 + N-2 + ... + 1 is quadratic in N.

That's how this kind of regexp engine works.  And it's mild, as such things go:  you can also create poor regexps that take time _exponential_ in N that fail to match certain strings.

It's unlikely this will change without replacing Python's regexp implementation entirely.  For why, see Jeffrey Friedl's book "Mastering Regular Expressions" (published by O'Reilly).  That book also spells out techniques for crafting regexps that don't suck ;-)  It's not a small topic, alas.