Also, see the follow-up post:

http://blog.scalyr.com/2014/07/impossible-problems-often-are...

In the end, they did have to do some pre-computes (which is better than indexing, but still not 100% on-the-fly resolution).