Intenta crear un índice en (DeviceId, MessageCounter DESC)
.
Además, intente esta consulta:
select *
from "Timestamps"
where DeviceId = 1
and MessageCounter = (SELECT MAX(MessageCounter) FROM "Timestamps" WHERE DeviceID = 1)
Solo adivinando:la diferencia de rendimiento podría deberse a que DeviceId = 1
se distribuye en más páginas que DeviceId = 4
. Al ordenar, sospecho que está sacando a la luz todas las páginas coincidentes, incluso si termina seleccionando solo la fila superior.