Searching 500 million records of binary data
You should consider using a real indexed search engine such as elasticsearch with runs on Java, uses a REST interface with json and so is exceedingly easy to program to, is free and open source, with a good community behind it.

www.elasticsearch.org

You could have it running on the same server as your application as long as you have a decent enough machine and it's built specifically for searching hundreds of millions of documents in near real time. 

Pretty easy to install and setup and extremely easy to customize.  It also has the added benefit of being built to run in the cloud (though not a requirement) and can cluster out very easily when your application begins to grow in popularity.