Steve,

As GilaMonster mentioned that the optimizer "has no idea if the between is going to affect 1 row, or the entire table" , you can first try to give it...