Spróbuj utworzyć indeks na (DeviceId, MessageCounter DESC) .
Spróbuj też tego zapytania:
select *
from "Timestamps"
where DeviceId = 1
and MessageCounter = (SELECT MAX(MessageCounter) FROM "Timestamps" WHERE DeviceID = 1)
Tylko zgadywanie:różnica w wydajności może wynikać z tego, że DeviceId = 1 jest rozłożony na więcej stron niż DeviceId = 4 . Podejrzewam, że sortując, wyciągasz wszystkie pasujące strony, nawet jeśli wybierzesz tylko górny wiersz.