Using Window Functions for Efficient Pagination


Applies to
DB2No
MySQLNo
OracleYes
PostgreSQLNo
SQL ServerYes

Window functions offer yet another way to implement pagination in SQL. This is a flexible, and above all, standards-compliant method. However, only SQL Server and the Oracle database can use them for a pipelined top-N query. DB2 and PostgreSQL do not abort the index scan after fetching enough rows and therefore executes these queries very inefficiently. MySQL does not support window functions at all.

The following example uses the window function ROW_NUMBER for a pagination query:

SELECT *
  FROM ( SELECT sales.*
              , ROW_NUMBER() OVER (ORDER BY sale_date DESC
                                          , sale_id   DESC) rn
           FROM sales
       ) tmp
 WHERE rn between 11 and 20
 ORDER BY sale_date DESC, sale_id DESC;

The ROW_NUMBER function enumerates the rows according to the sort order defined in the over clause. The outer where clause uses this enumeration to limit the result to the second page (rows 11 through 20).

There is something for everyone:
training, tuning and literature on SQL performance

The Oracle database recognizes the abort condition and uses the index on SALE_DATE and SALE_ID to produce a pipelined top-N behavior:

DB2

Explain Plan
-------------------------------------------------------------
ID | Operation                   |               Rows |  Cost
 1 | RETURN                      |                    | 65658
 2 |  FILTER                     |  100933 of 1009326 | 65658
 3 |   FETCH SALES               | 1009326 of 1009326 | 65295
 4 |    IXSCAN (REVERSE) SL_DTID | 1009326 of 1009326 |  5679

Predicate Information
 2 - RESID (11 <= Q3.$C8)
     RESID (Q3.$C8 <= 20)

Please note that DB2 LUW 10.5 does not execute this query as top-n query. Although it prevents the sort operation it still reads through the entire index—it does not abort execution after fetching 20 rows.

To get a proper top-n abort after reading 20 rows, you must double-wrap the query to first apply the top-n abort condition and then filtering away the first 10 rows:

SELECT *
  FROM (SELECT *
          FROM (SELECT sales.*
                     , ROW_NUMBER() OVER (ORDER BY sale_date DESC
                                                 , sale_id   DESC) rn
                 FROM sales
               ) tmp
         WHERE rn <= 20
       ) tmp2
 WHERE rn > 10
 ORDER BY sale_date DESC, sale_id DESC;
Explain Plan
-----------------------------------------------------------------
ID | Operation                       |               Rows |  Cost
 1 | RETURN                          |                    |    21
 2 |  FILTER                         |            7 of 20 |    21
 3 |   FETCH SALES                   |      20 of 1009326 | 65352
 4 |    IXSCAN (REVERSE) SALES_DT_ID | 1009326 of 1009326 |  5736

Predicate Information
 2 - RESID (10 < Q3.$C8)

Note that the filter rn <= 20 does not appear in the Predicate Information section, yet the row count estimate reflects it.

Oracle

---------------------------------------------------------------
|Id | Operation                      | Name    | Rows |  Cost |
---------------------------------------------------------------
| 0 | SELECT STATEMENT               |         | 1004K| 36877 |
|*1 |  VIEW                          |         | 1004K| 36877 |
|*2 |   WINDOW NOSORT STOPKEY        |         | 1004K| 36877 |
| 3 |    TABLE ACCESS BY INDEX ROWID | SALES   | 1004K| 36877 |
| 4 |     INDEX FULL SCAN DESCENDING | SL_DTID | 1004K|  2955 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter("RN">=11 AND "RN"<=20)
2 - filter(ROW_NUMBER() OVER (
           ORDER BY "SALE_DATE" DESC, "SALE_ID" DESC )<=20)

The WINDOW NOSORT STOPKEY operation indicates that there is no sort operation (NOSORT) and that the database aborts the execution when reaching the upper threshold (STOPKEY). Considering that the aborted operations are executed in a pipelined manner, it means that this query is as efficient as the offset method explained in the previous section.

The strength of window functions is not pagination, however, but analytical calculations. If you have never used window functions before, you should definitely spend a few hours studying the respective documentation.

If you like my way of explaining things, you’ll love my book.

About the Author

Photo of Markus Winand
Markus Winand tunes developers for high SQL performance. He also published the book SQL Performance Explained and offers in-house training as well as remote coaching at http://winand.at/

?Recent questions at
Ask.Use-The-Index-Luke.com

0
votes
1
answer
167
views

PostgreSQL Scripts: Performance Testing and Scalability problem and question

Nov 12 at 14:53 Markus Winand ♦♦ 936
testing postgresql scalability
0
votes
1
answer
570
views

PostgreSQL Bitmap Heap Scan on index is very slow but Index Only Scan is fast

Oct 31 at 11:31 Markus Winand ♦♦ 936
index postgresql postgres sql
3
votes
2
answers
592
views

pagination with nulls

Oct 29 at 22:39 Rocky 46
pagination