the problem is that you are probably not using the correct index. considering that when you use a '%' at the beginning of a string you need to use at least a GIN (or was it gist?) index with string ops as far as I remember but actually using % at the beginning is not recommended. I think using a tsquery might be more recommended for contain searches. at least on postgresql