title: Understanding Order by using top-N heapsort in postgres
body: <p>In a theoretical scenario in the absence of indexes, an order by with limit has to scan all the data, then apply the order by and then only apply the limit since we can get the top 10 rows(for example) only after sorting.</p>
  
  <p>But postgres is little smarter here and the plans below give the story.</p>
  
  <p>Order by with limit</p>
  
  <pre><code>learning=# explain (analyze,buffers) select * from temp order by userid limit 10;
                                                            QUERY PLAN
  -------------------------------------------------------------------------------------------------------------------------------
   Limit  (cost=81745.51..81745.54 rows=10 width=41) (actual time=2064.275..2064.278 rows=10 loops=1)
     Buffers: shared hit=13 read=18644
     -&gt;  Sort  (cost=81745.51..86735.41 rows=1995958 width=41) (actual time=2064.273..2064.274 rows=10 loops=1)
           Sort Key: userid
           Sort Method: top-N heapsort  Memory: 25kB
           Buffers: shared hit=13 read=18644
           -&gt;  Seq Scan on temp  (cost=0.00..38613.58 rows=1995958 width=41) (actual time=35.053..1652.660 rows=1995958 loops=1)
                 Buffers: shared hit=10 read=18644
   Planning time: 0.167 ms
   Execution time: 2064.335 ms
  (10 rows)
  </code></pre>
  
  <p>Order by without limit</p>
  
  <pre><code>learning=# explain (analyze,buffers) select * from temp order by userid;
                                                        QUERY PLAN
  -----------------------------------------------------------------------------------------------------------------------
   Sort  (cost=308877.61..313867.51 rows=1995958 width=41) (actual time=2685.680..3293.698 rows=1995958 loops=1)
     Sort Key: userid
     Sort Method: external merge  Disk: 99504kB
     Buffers: shared hit=42 read=18612, temp read=12440 written=12440
     -&gt;  Seq Scan on temp  (cost=0.00..38613.58 rows=1995958 width=41) (actual time=0.069..286.556 rows=1995958 loops=1)
           Buffers: shared hit=42 read=18612
   Planning time: 0.066 ms
   Execution time: 3540.545 ms
  (8 rows)
  </code></pre>
  
  <p>What my assumption from this is postgres uses an algorithm called heap sort (pretty well known) and stops when the first N (limit) rows are obtained.</p>
  
  <p>From <a href="https://www.cs.usfca.edu/~galles/visualization/HeapSort.html" rel="nofollow">this</a> visualization, I am unable to understand how this works ? Can anybody throw some light on understanding this.Is my assumption above correct ?</p>