Temos uma tabela com mais de dois milhões de linhas, em que todas as consultas são uma pesquisa entre usandoColumn1 eColumn2. Além disso, haverá apenas um resultado possível. Por exemplo...

Col1     Col2
1        5
6        10
11       15

select * from table1 where 8 between Col1 and Col2

Atualmente, tenho um índice clusterizado exclusivo emCol1 eCol2. Até agora, não consegui descobrir como ajustar ainda mais a consulta e os índices para minimizar as linhas tratadas. O plano de execução relata atualmente o custo de quase 0,5 e 113k linhas tratadas ao localizar a primeira e única resposta correta.

Quais opções eu posso estar negligenciando?

Conforme solicitado, alguns detalhes do plano de execução atual:

Operation
 Clustered Index Seek
Predicate
 CONVERT_IMPLICIT(bigint,[@2],0)<=[Col2]
Seek Predicate
 Seek Keys[1]: End: Col1 <= Scalar Operator(CONVERT_IMPLICIT(bigint,[@1],0))