You can build an index IF you know the regexes to index in advance. You can't build an index that will work for any random regex that comes along.

If you want to do it, just look up information on building an inverted word index, but use regexes instead of words. (In short, you run every regex against every record and build a hash from regexes to a list of records that match them.) You could probably even adapt some of the text search tools on CPAN if you chose to.