select distinct with a limit of say k means you only need k distinct rows. Not necessarily in any order so a side index helps there too. And you can early out. Distinct plus order by and limit makes that a little harder but you can still do it in one pass with n lg k as you say. For sufficiently small k you could avoid disk writes too.