Какой план запроса лучше?

После добавления нужного индекса, у вас должен был появиться в плане компонент Index Seek вместо Table Scan - этого не произошло..
Возможно, неверный индекс составили