I'd suggest combining Text::Query or Text::Query::Advanced with Text::Query::BuildSQL.

They're not the simplest of modules to use, but they have good parsers (and a boolean one in Text::Query::Advanced) so users can query in almost the same way as they would with AltaVista/Google