sql-server - この単純なケースで、時間範囲内で行をより速く取得するにはどうすればよいですか?

Question

時間範囲内で行を選択するのに時間がかかりすぎる理由を理解しようとしています。

500 万行を超えるデータベース テーブルが 1 つあります。

FooTimestamp 列には、DateTimeOffset のタイプである非一意で非クラスター化のインデックスがあります。

時間範囲内でいくつかの行を取得しようとすると、2 分以上かかります。(再度実行すると、MS-SQL Server 2008 のキャッシュ機能により、比較的高速になると思います)

DECLARE @since datetimeoffset
DECLARE @before datetimeoffset

SET @since ='2013-03-20 00:00:00 +02:00'
SET @before ='2013-03-27 00:00:00 +02:00'

SELECT *
WHERE ([FooTimestamp] >= @since AND [FooTimestamp] <= @before) 

質問: 何百万ものレコードを持つテーブルから行を取得する場合、クエリ結果をより速く取得するにはどうすればよいですか? (このような簡単なクエリに 2 分は多すぎると思います)