Pagination

A question about reporting data one page at a time came up on the Oracle Database Forum a couple of days ago – this variation on the “Top N” class of questions is becoming more common as more applications get web-based front-ends, but this example was a little more subtle than usual – so I spent a few minutes seeing if I could work out a quick answer, which I then posted to the forum.

After posting the answer, though, I realised that my solution was probably a lot messier than it needed to be, did more work than it needed to, and would probably make it hard for the optimizer to find an efficient execution path. So I thought I’d write up a few notes about it on the blog, and post a simpler solution to the problem.

The requirement was as follows:

• Output the result page by page – 20 rows to a page
• The query is a “union all” of two sorted results
• We want 10 rows at a time from table
• When one table is exhausted, the pages should still hold 20 rows each

Now, there is a standard strategy for paging a query – you slot it into a framework that looks like this:

select
        {list of columns}
from    (
        select  {list of columns}, rownum rn
        from
                ( {your select statement with order by} )
        where
                rownum <= N * {your pagesize}
        )       v1
where
        v1.rn > (N-1) * {your pagesize}
order by
        rn
;

To get a better idea of why this outline works, assume you have a query where you have ordered the data which you want to report across the internet with 15 rows per page. To report just the results for page 3 you have to:

select the first 45 rows (3 * 15) from your query by putting it inside an inline view, add a rownum (aliased above as rn) to the select list of the next layer out. [edit Mar 2009: see notes 9 – 12 below for an important correction]

Because you have a rownum in your select list this forces Oracle to create the result set as a non-mergeable view. So you can now put another view layer around this non-mergeable view, adding a predicate that references the selected rownum to throw away the first 30 (2 * 15) rows of data.

You’ll notice that I’ve finished with an order by clause on the selected rownum because you always need an order by if you want to guarantee that the data appears in a certain order.

If you’re lucky this approach may allow the optimizer to do clever tricks with the rownum predicates, and you’ll see a couple of COUNT STOPKEY operations appearing in the execution plan, with predicates like “ROWNUM <= N” pushed much further down into the plan than your SQL suggests.

The Special Case

That’s the general principle – but in the case of the query posted on the Oracle Database Forum, we have to select from two tables at once, reporting 10 rows at a time from each table. If we were supposed to alternate between the two tables (one row at a time) this wouldn’t be too difficult – but the batching makes it harder, especially when you have to deal with the boundary condition as one table runs out of data.

I posted a solution which used an analytic function and decode() – but then realised that I’d only used the analytic function because I’d copied and modified a couple of previous suggestions. The analytic function would make it harder for Oracle to find any short cuts in running the query; I’d used the wrong analytic function anyway (rank(), when I should have used row_number(); and just to finish it off, the decode() was an unnecessary overhead.

So here’s an improved solution, tested only on 10gR2 for the query (starting with a trial data set):

drop table table_a;
drop table table_b;

execute dbms_random.seed(0)

create table table_a (n1 number, v1 varchar2(10), x number);

insert into table_a
select
        rownum, rownum, dbms_random.value
from    all_objects
where   rownum <= 16;

create table table_b (n1 number, v1 varchar2(10), x number);

insert into table_B
select
        rownum, rownum, dbms_random.value
from    all_objects
where   rownum <= 28;

commit;

-- gather statistics at this point

With this data set, the specification requires page one to show the first 10 rows from table_a and then the first 10 rows from table_b. Page two should start with the next 6 rows from table_a and end with the next 14 rows from table_b (20 rows per page, even when one table is exhausted). Finally page 3 should show the last 4 rows from table_b.

To help explain the mechanism I used, I’ve started with a query that fetches all the data in the right order, adding some columns in anticipation of the pagination requirements, but not actually including the pagination framework.

I’ve used subquery factoring to keep the code a little tidier, I think it makes it a little bit easier to see that I’ve applied the same query to both table_a and table_b.

At the innermost level (in the factored subqueries) each query block selects rows from its table in order – and because I have to select from two tables and always fill a page I’ve included a predicate that assumes that I may have to select all the rows I want for a whole page from just one of the tables:

You’ll notice that I’ve used a variable m_last_row instead of N * m_pagesize to identify the maximum number of rows I need to select.

As well as adding the rownum to the outer select list, I’ve also added a flag column to show which table my data comes from. This will help in the “10 rows from A, 10 rows from B” logic. More significantly, perhaps, there’s also a ‘page number’ that I’ve generated by dividing (rownum – 1) by half the page size.

That ‘page number’ column is there because, for an output of 20 rows per page, I want the first 10 rows from table_a, then the first 10 rows from table_b on the first page, the second 10 rows from table_a and the second 10 rows from table_b on the second page, and so on … for as long as there are enough rows. Having a page number and table flag makes it easy to batch the data correctly.

The order by clause is a little cunning. Because of the union all, we have to order by a list of column numbers rather than column names, so we are ordering by page number, table flag, and row number within table. This means the rows for page zero appear first, and the A rows appear on that page before the B rows, and the A rows are in the order dictated by the predicate on the A table … and so on.

Of course we never query for a specific page – we are only ordering by something that initially happens to match the page numbers we want to see, so when one of the tables runs out of data, our query automatically fills subsequent pages correctly.

with
a_results as (
        select
                trunc((rownum - 1)/(&m_pagesize/2)) res_page,
                'A'                                 flag,
                rownum                              res_rn,
                a.*
        from    (select * from table_a order by x) a
        where
                rownum <= &m_last_row
),
b_results as (
        select
                trunc((rownum - 1)/(&m_pagesize/2)) res_page,
                'B'                                 flag,
                rownum                              res_rn,
                b.*
        from    (select * from table_b order by x) b
        where
                rownum <= &m_last_row
)
select * from a_results
union all
select * from b_results
order by
        1,2,3
/

Once we’ve checked that we are getting the right data in the right order (though more than we really want to see) we can now do the standard trick for pagination: introduce two inline views to introduce in a rownum, limit the total number of rows selected, and discard the rows we don’t want.

with
a_results as (
        select
                trunc((rownum - 1)/(&m_pagesize/2)) res_page,
                'A'                                 flag,
                rownum                              res_rn,
                a.*
        from    (select * from table_a order by x) a
        where
                rownum <= &m_last_row
),
b_results as (
        select
                trunc((rownum - 1)/(&m_pagesize/2)) res_page,
                'B'                                 flag,
                rownum                              res_rn,
                b.*
        from    (select * from table_b order by x) b
        where
                rownum <= &m_last_row
)
select
        p2.*
from        (
        select
                rownum        p1_rn,
                p1.*
        from        (
                        select * from a_results
                        union all
                        select * from b_results
                        order by
                                1,2,3
                )        p1
        where
                rownum <= &m_last_row
        )       p2
where
        p1_rn > &m_last_row - &m_pagesize
order by
        p1_rn
.


define m_pagesize = 20
define m_last_row = 20
/
define m_last_row = 40
/
define m_last_row = 60
/

This is what the output looks like if you run this query after creating the data and collecting stats. I’ve used the substitution variables to set the pagesize to 20, and select the first, second, and third pages in turn.
 

     P1_RN   RES_PAGE F     RES_RN         N1 V1                  X
---------- ---------- - ---------- ---------- ---------- ----------
         1          0 A          1          1 1          .063365246
         2          0 A          2          6 6          .069489261
         3          0 A          3          4 4          .218284274
         4          0 A          4          3 3          .231820312
         5          0 A          5         12 12         .269242784
         6          0 A          6          5 5          .370159676
         7          0 A          7         11 11         .454572452
         8          0 A          8          7 7          .460374649
         9          0 A          9         16 16         .470930285
        10          0 A         10         13 13         .494289647
        11          0 B          1         15 15         .006870916
        12          0 B          2         18 18         .022240529
        13          0 B          3         10 10         .031796267
        14          0 B          4         20 20         .092266948
        15          0 B          5         23 23          .09602861
        16          0 B          6          9 9          .120796717
        17          0 B          7          7 7          .127484165
        18          0 B          8         19 19         .128133488
        19          0 B          9         22 22         .132048906
        20          0 B         10          4 4           .16122616

20 rows selected.

     P1_RN   RES_PAGE F     RES_RN         N1 V1                  X
---------- ---------- - ---------- ---------- ---------- ----------
        21          1 A         11         14 14         .762612109
        22          1 A         12         10 10         .818435634
        23          1 A         13         15 15         .823666729
        24          1 A         14          2 2          .828459828
        25          1 A         15          9 9          .944040457
        26          1 A         16          8 8          .953122253
        27          1 B         11          2 2          .173659035
        28          1 B         12         24 24          .21850708
        29          1 B         13         13 13         .251512351
        30          1 B         14         28 28         .327365925
        31          1 B         15          1 1           .34581104
        32          1 B         16         27 27         .361930265
        33          1 B         17         26 26         .379273188
        34          1 B         18         11 11         .380012146
        35          1 B         19         21 21          .40247362
        36          1 B         20          8 8          .613787416
        37          2 B         21         14 14         .701614416
        38          2 B         22          6 6          .721406344
        39          2 B         23          5 5          .751985528
        40          2 B         24         25 25         .817935466

20 rows selected.

     P1_RN   RES_PAGE F     RES_RN         N1 V1                  X
---------- ---------- - ---------- ---------- ---------- ----------
        41          2 B         25         16 16         .863647981
        42          2 B         26          3 3          .935727091
        43          2 B         27         12 12         .950955777
        44          2 B         28         17 17         .996240375

4 rows selected.

The next step is to optimise the query – and for paginated queries the most important method is to find a way that lets you select the correct “first N rows” in the correct order without having to acquire the entire data set and sort it. But that’s a story for another day.

Update: There is a critical limitation to this general method – see comments 7 and 10 below for details.