With large ORDER BY ... LIMIT ... queries, at some point, it becomes better to fully sort the data and apply a limit instead of computing a heap. I think @Tmonster is addressing this in a separate PR in the optimizer.

Nonetheless, I looked at the PhysicalTopN operator and found that some things could be improved, mostly the merging of heaps, which is inefficient if you iterate and do pop_heap and push_heap. Instead, we are better off just sorting the heap. I also parallelized scanning.

I ran this little benchmark to check the performance. Create some data:

create table test25 as select range i from range(25_000_000) order by hash(i);
create table test50 as select range i from range(50_000_000) order by hash(i);

Query:

select any_value(columns(*)) from (from test25 order by i limit 5_000_000);
select any_value(columns(*)) from (from test50 order by i limit 5_000_000);

Current main: ~5.5s and ~7.6s
This PR: ~2.7s and ~3.8s
Without TopN optimization: ~0.25s and ~0.43s

There is still a lot of room for improvement in the PhysicalTopN operator for large inputs, but I'm not sure if we should spend too much time on this because we can just use the optimizer to avoid using a TopN and sort the data if N is large, but I figured this was worth the effort. With this input data, I found that the Top N was only better than sorting for limits less than 250k.