This sounds like what I described yesterday: https://news.ycombinator.com/item?id=39713239
In addition to what I described there, the way you described it, it sounds like you don't have a single index that covers both columns. That may also help if I understood right.