Does XBase have any built in searching or indexing? I'm not familiar with it, so I don't know.

If so, I would definitely prepare a query in Perl and let the database handle it. It ought to be optimized for that sort of thing.

Regardless, there are a few places where you have things inside a loop that don't seem to need to be there. Case in point, checking the query for a certain type, then choosing which keywords to find. Unless the query changes in the middle of the search, you can compute the search elements just once, not once for each row of the database.