The magic known as MySQL FULLTEXT index.
How a solution that I was not that confident that would work solved the problem spectacularly. 
Tags: mysql, java, search, dev