Feels like caching the top 1000 most common beginnings would solve this for 99% of cases?