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 requiring 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 backwards. 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 speed up. What is also worth noticing is that in this case, the main table needs not 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.