Comment by megalord

> No matter what indexes we threw at the table

I don't have information on how team investigated the whole problem. What table looks like? What indexes exactly? Was there any explain analyzing? 28 millions are not as many as it seems. We have similar sized table but when indexed properly, query is always quick