You might want to look into "full text search" tools. You did say regexes and I think full-text searches might be limited to substrings but it might be worth checking into.

CPAN lists the DBIx::FullTextSearch module that might be useful.