Oracle Scratchpad

September 8, 2008

Pagination

Filed under: Performance,Tuning — Jonathan Lewis @ 4:48 am GMT Sep 8,2008

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.

12 Comments »

  1. Thomas Kyte has also published on this topic before. Is there any difference between his approach and yours?

    Comment by KD — September 9, 2008 @ 2:25 pm GMT Sep 9,2008 | Reply

  2. Great idea! So it is all about the right order-by-clause. :)

    I think your very first SQL (the framework) also suffer from ‘less than’ problem (and the brackets doesn’t much either).

    Comment by Todor Botev — September 11, 2008 @ 11:03 am GMT Sep 11,2008 | Reply

  3. KD,
    From memory, I don’t think Tom’s basic method is any different from mine – but you’d have to point me to an example if you wanted a definite yes or no.

    Comment by Jonathan Lewis — September 11, 2008 @ 11:23 am GMT Sep 11,2008 | Reply

  4. Todor,
    Thanks, I’ve now corrected the first example.

    Comment by Jonathan Lewis — September 11, 2008 @ 11:23 am GMT Sep 11,2008 | Reply

  5. Jonathan,

    I understand that it’s a very costly operation to get the total record count (i.e. displaying something like “Records 1 ~ 50 of 4500″). If my requirement is to display the total record count only up to 1000 records (e.g. “Records 1 ~ 50 of 355″; if the total record count is more than 1000, then display “Records 1 ~ 50 of More than 1K), is there anyway to do that efficiently?

    Comment by peter — September 16, 2008 @ 10:58 pm GMT Sep 16,2008 | Reply

  6. Peter,

    I don’t think there’s a generic way of dealing with that problem.

    The only mechanism that will get the correct answer every time is to precede your query with another (minimal) query that actually acquires the data but doesn’t pull it across the network. Fortunately you don’t have to sort the data, or look at all the columns in the counting query:

    I think something like the following should work:

    select
           count(*)
    from    (
           select null
           from {rest of your query}
           where rownum <= 1000
           )
    ;

    Comment by Jonathan Lewis — September 26, 2008 @ 1:55 pm GMT Sep 26,2008 | Reply

  7. Jonathan,

    Referring to your pagination query, you mentioned that

    “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.”

    How can ordering by the rownum guarantee that the data apepars in a certain order? Don’t we need to sort by some unique column(s) in the inner SQL?

    CREATE TABLE x (
    id NUMBER,
    numcol NUMBER,
    dateCol DATE
    );

    INSERT INTO x VALUES(1, 1, SYSDATE - 3);
    INSERT INTO x VALUES(2, 2, SYSDATE);
    INSERT INTO x VALUES(10, 10, SYSDATE);
    INSERT INTO x VALUES(11, 11, SYSDATE);
    INSERT INTO x VALUES(12, 12, SYSDATE);
    INSERT INTO x VALUES(13, 13, SYSDATE);
    INSERT INTO x VALUES(14, 14, SYSDATE);
    INSERT INTO x VALUES(3, 3, SYSDATE);
    INSERT INTO x VALUES(4, 4, SYSDATE - 1);
    INSERT INTO x VALUES(5, 5, SYSDATE - 1);
    INSERT INTO x VALUES(6, 6, SYSDATE - 2);
    INSERT INTO x VALUES(7, 7, SYSDATE);
    INSERT INTO x VALUES(8, 8, SYSDATE);
    INSERT INTO x VALUES(9, 9, SYSDATE);

    SELECT *
    FROM  (
      SELECT main.*, rownum rn
      FROM (
         SELECT *
         FROM   x
         ORDER  BY dateCol DESC
      ) main
      WHERE  rownum <= 10
    )  v1
    WHERE  rn > 5
    ORDER  BY rn;

    ID NUMCOL DATECOL RN
    ---------- ---------- ------------------- ----------
    2 2 2009-02-23 10:21:51 1
    10 10 2009-02-23 10:21:51 2
    11 11 2009-02-23 10:21:51 3
    13 13 2009-02-23 10:21:51 4
    12 12 2009-02-23 10:21:51 5

    SELECT *
    FROM  (
      SELECT main.*, rownum rn
      FROM (
         SELECT *
         FROM   x
         ORDER  BY dateCol DESC
      ) main
      WHERE  rownum <= 5
    )  v1
    WHERE  rn > 0
    ORDER  BY rn;

    ID NUMCOL DATECOL RN
    ---------- ---------- ------------------- ----------
    14 14 2009-02-23 10:21:51 6
    9 9 2009-02-23 10:21:51 7
    8 8 2009-02-23 10:21:51 8
    7 7 2009-02-23 10:21:51 9
    12 12 2009-02-23 10:21:51 10 >> This record appears twice

    Comment by peter — February 23, 2009 @ 6:35 pm GMT Feb 23,2009 | Reply

  8. Peter,
    what about getting the results for a particular page and the number of pages using one SQL statement. Using the example available on http://download.oracle.com/docs/cd/B19306_01/server.102/b14200/functions137.htm#SQLRF06100 (end of the page)
    we can construct the following one:

    SELECT a, b, round(total_rows/:page_size) AS total_pages
    FROM (SELECT a, b, row_number() over(ORDER BY a) r, COUNT(1) over() AS total_rows
    FROM my_table WHERE a>10 AND b>50)
    WHERE r BETWEEN 50 AND 99; — second page in case page_size is 50

    Hope this helps.

    Comment by Adrian Angelov — February 26, 2009 @ 2:53 pm GMT Feb 26,2009 | Reply

  9. Hi Adrian,

    Thanks for the example. However, that didn’t really answer my question though. My question is that Jonathan sorted his SQL by “rn” to ensure that there are no duplicate records across pages. I tried it and found that it really wasn’t so. The first SQL in my example shows page 1; the second shows page 2. As you can see, the record whose id is 12 appeared in both page 1 and 2.

    The example you showed would work if the column a is unique. By the way, showing total_rows/total_pages in your SQL would probably kill the performance.

    I think we can sort by + a unique key. Then we can create a concatenated index that includes both columns to help with performance. However, if the columns are not from the same table, then we won’t be able to have that index. I’m interested in how to solve this problem.

    Comment by peter — February 26, 2009 @ 4:53 pm GMT Feb 26,2009 | Reply

  10. Peter,

    You’re right – the generic mechanism doesn’t work unless the column used for the sort is either unique, or has an index on it that Oracle decides to use.

    With “sufficiently unique” data the method works – and that was what fooled me, the examples I ran had repetitive data but I got lucky and didn’t hit the pagebreak problem that you’ve found.

    The problem arises because Oracle has an optimisation method for:
    select from (select order by) where rownum <- n

    It doesn’t sort ALL the data and then pick the first N (if it did the mechanism would be completely deterministic and you wouldn’t see the problem).

    Instead Oracle scans the data, building a list of the top N values, replacing a value in the list only if it finds a higher (relative to the sort order) value as it works through the table. It then only has to sort the N rows it has kept.

    In your case, Oracle acquired the top 5 rows in the table for page 1, and sorted them – which happened to swap the order of a couple of rows. For page 2 it acquired the top 10 rows and sorted them, which happened to mix them up very thoroughly so that a row that had appeared in the top 5 was pulled down into the bottom five.

    As a generic workaround (when the ordered column is not unique) the order by clause should therefore include the rowid (or, as you suggest above, an additional column that is used to make the ordering column set unique).

    If there is an index on the ordered column (even when it is unique) and the optimizer decides to walk it, then the sort operation won’t appear and a stopkey will stop after the correct number of steps through the index – which means the result will be correct.

    Thanks for highlighting the error.

    Comment by Jonathan Lewis — March 22, 2009 @ 12:33 am GMT Mar 22,2009 | Reply

  11. On the surface of it this is a chronic oracle FAIL! Having to rewrite your query so you can do a simple LIMIT X,Y has left me speechless…

    Comment by Javawocky — September 8, 2009 @ 2:04 am GMT Sep 8,2009 | Reply

  12. Thanks the Pagination information … works well

    Comment by ASAHA — September 18, 2012 @ 8:54 pm GMT Sep 18,2012 | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Theme: Rubric. Get a free blog at WordPress.com

Follow

Get every new post delivered to your Inbox.

Join 4,422 other followers