Optimizing Wildcard Searches

Can anyone tell me where I might find some definitive information on how to optimize wildcard searches. I have a table which contains 300,000 records and I need to look up records based on 6 possible fields. Some of the fields can be wildcarded. In my experimentation, I have found some interesting but inexplicable timing patterns. My documentation is of no assistance. Any help would be appreciated.