Making use of sorted output

B-tree indexes are not only used to find rows; they are also used to feed sorted data to the next stage in the process:

test=# EXPLAIN SELECT * 
               FROM  t_test 
               ORDER BY id DESC  
               LIMIT 10;  
                            QUERY PLAN 
--------------------------------------------------------------- 
 Limit (cost=0.43..0.74 rows=10 width=9) 
   -> Index Scan Backward using idx_id on t_test 
         (cost=0.43..125505.43 rows=4000000 width=9) 
(2 rows)

In this case, the index already returns data in the right sort order, and therefore there is no need to sort the entire set of data. Reading the last 10 rows of the index will be enough to answer this query. Practically, this means that it is possible to find the top N rows of a table in a fraction of a millisecond.

However, ORDER BY is not the only operation that requires sorted output. The min and max functions are also all about sorted output, so an index can be used to speed up these two operations as well. Here is an example:

test=# explain SELECT min(id), max(id) FROM t_test; 
                             QUERY PLAN 
---------------------------------------------------------------- 
 Result (cost=0.93..0.94 rows=1 width=8) 
  InitPlan 1 (returns $0) 
   -> Limit (cost=0.43..0.46 rows=1 width=4) 
       -> Index Only Scan using idx_id on t_test 
                (cost=0.43..135505.43 rows=4000000 width=4) 
                 Index Cond: (id IS NOT NULL) 
 InitPlan 2 (returns $1) 
  -> Limit (cost=0.43..0.46 rows=1 width=4) 
      -> Index Only Scan Backward using idx_id on t_test t_test_1 
              (cost=0.43..135505.43 rows=4000000 width=4)
                Index Cond: (id IS NOT NULL) 
(9 rows) 

In PostgreSQL, an index (a B-tree, to be more precise) can be read in normal order or backward. The thing now is that a B-tree can be seen as a sorted list. So, naturally, the lowest value is at the beginning and the highest value is at the end. Therefore, min and max are perfect candidates for a speedup. What is also worth noting is that, in this case, the main table doesn't need to be referenced at all.

In SQL, many operations rely on sorted input; therefore, understanding these operations is essential because there are serious implications on the indexing side.