Pagination

[Stan James]

There are frequent questions in the web app forums about pagination. When a user search yields many rows, show them page 1 with 1..10, page 2 with 2..20, etc. Nearly always somebody says this is frequently asked and suggests searching for previous replies. I did some of that, and found the number of solution roughly equals the number of replies, and found a few heated arguments as to their value. Could I invite some folks with solid experience to contribute what has really worked for them?
I'll start by trying to categorize some of what I've found:

I. Repeat the query for each new request.
   Algorithm
      Client requests page 1
      Execute the query
      Return rows for page 1
      Client requests page 2
      Execute the query
      Skip rows for page 1
      Return rows for page 2
   Pro/Con
      Pro: Stateless. Nothing is cached between requests. 
      Pro: Simple. Every request is the same.
      Pro: Up to date with any inserts or deletes in the database.
      Con: Database and time intensive. Might be repeating large, 
           expensive queries - if users really do ever page fwd.
      Con: Not guaranteed consistent. If other processes are inserting and
           deleting rows, paging fwd or bkwd might skip rows. Fwd then Bkwd
           might not give the same rows.
   Notes
      I have used this with mainframe requests where even the nastiest 
      queries were fast and the server had no options for storing state.
      We have used row number schemes for client requests, and the highest 
      key on a page for page forward only action.
II. Hold the query results on the server
   Algorithm
      Client requests page 1
      Execute query
      Cache complete result set or just PKeys
      Return rows for page 1
      Client requests page 2
      Get rows from cache or get PKeys from cache, rows from database
      Return rows for page 2
   Pros/Cons
      Pro: Does NOT repeat the query 
      Pro: Self consistent - fwd then bkwd will give identical results
      Pro: Can share cached results if two users have identical requests
      Con: Big cache in memory or someplace close to it
      Con: Complexity for cache, time-out
III. Hold a scrolling cursor on the server
   Algorithm
      Client requests page 1
      Execute query with a cursor
      Fetch & return rows for page 1
      Client requests page 2
      Fetch & return rows for page 2
   Pro/Con
      Pro: Does not repeat the query
      Pro: Very small state - just a connection & cursor
      Pro: Self consistent
      Con: More open connections. Might hold open one db connection 
           per user
      Con: What does this do to the db? Doesn't it cache rows not yet    
           fetched?
      Con: Complexity for time-out

A few notes: Some factors depend heavily on user habits - eg if they rarely page forward or only to page 2 of 100, caching may not pay off. Cached results will not reflect recent changes. That may be good for one app, bad for another, or the changes may be rare enough to ignore.
So waddya all think? Can we add more algorithms, fine tune the pros & cons to help ourselves choose in the future?

[Jeanne Boyarsky]

Stan,
This looks well researched. One thing I would add is that number two seems to have two parts. The cache could occur in the memory of the app server. It could also occur in a temporary database table (sort of like the table used to persist http sessions.)

[Bear Bibeault]

Another tactic that I've employed is only available with certain DBMS systems. PostgreSQL for example provides the LIMIT and OFFSET clauses so that you can have the DB itself "slice" the dataset into pages for you.
Pros: limits data xfer to and from 2nd tier, easy to program, efficient
Cons: SQL statements are database-dependent
bear

[David O'Meara]

Been trying to post this for a few hours...
Some other factors that effect the final decision are the number of requests returned, the likelihood viewing all results, and the behaviour of the data.
Number of requests: if (based on sample or expected queries from users) the results are reasonably small, you may decide to push the load to the server rather than the database. Consider a shopping site (a few hundred items total) versus Google (how many billions?).
Viewing all results: if you are in a situation where users are unlikely to view all results returned, only cache the ones they are likely to view. Imagine Google caching 1.7 million page results just in case you want them all. Unlikely.
Behaviour of the data: If the results are unlikely to change, it removes on of the CONs for option 1. eg Shopping sites may only change on a monthly basis.
There are also a couple of extra factors that can be looked at. One that I hinted at is that based on behaviour of your search, you might want to combine options to enhance performance. If the search size is extremely large, cache as much as you think is reasonable, then load the rest if required. You can also share the load between the server and the database by caching the primary key only and loading each item when it is required.
Note also that the search at Google is a bit fuzzy - they don't actually know how many options are returned or how many pages they fill. Have you ever gotten to the second last page of a Google search and found that the link to the last page is no longer available?
Another useful limiting factor is only allowing users to jump forward a maximum of 10 pages - this can be used to set the upper limit i you only want to cache part of the result.
As you are obviously aware any decision must be based on plenty of factors, which is why I'm not a fan of people saying 'cache the results and load them into page1...10'.
Dave

[David O'Meara]

...and what Bear said.

[Stan James]

Thanks all for jumping in. Jeanne, I was hinting at a temp db cache with the "or something close to it". There are probably a few fast cache options just off main memory. Bear, we tried some row limiting options on huge queries, but they still buried the db because an ORDER BY clause forced the db to really complete the query even when we only got a few rows. Do the LIMIT and OFFSET type options have similar problems? Is there similar syntax in other db vendors?

[Frank Carver]

Is there similar syntax in other db vendors?
I've used something similar in Oracle, although I can recall the exact syntax right now.

[David O'Meara]

I know there's a thread in the JDBC forum that has a whole list of sample SQL for a list of databases. If I get a chance later on I'll go look for it.
Dave

[steve souza]

Excellent well thought out question. I'll add a couple points.
If possible I always prefer no caching. When to refresh a cache can be complex and so I try to avoid it.
I have done a hybrid of the approaches (reexecuting the query and caching) when the query itself is expensive. For example instead of returning 1 page with my quer I return a 10 page buffer each time the query is executed. If the user goes past page 10 I reexecute the query and repopulate the buffer.
I cache ResultSets by converting them to Object[][] arrays. You can also use CachedRowSet objects, but for several reasons I prefer arrays.
1) You have access to all the array APIs such as sorting and searching. In several of my apps I allow users to sort the cached results by clicking on the column header.
2) The CachedRowSet is not available in all JDBC drivers for all DB vendors.
3) One Advantage of returning Object[][] is all JDBC can be hidden and so you can get the ResultSet more simply than when using JDBC directly. The ResultSetConverter object below is part of my FormattedDataSet API and is a thin wrapper for an array for the ResultSetMetaData and another one for the ResultSet.

  
FormattedDataSet fds=new FormattedDataSet();
// Note no JDBC calls.  JDBC is hidden as an implementation detail
ResultSetConverter rsc=fds.getResultSetConverter("select * from table");
Object[][]data=rsc.getResultSet();

[steve souza]

Also I rarely give the users the ability to go to a specific page number. Think about it this way if you have 500 pages what would ever make you want to go to page 343 directly? You would have no idea what was on that page.
Usually the user wants to go to a page with some specific data on it (salaries over $100,000 for example) and a search capability would serve them better.
The first and last pages may be exceptions, but going to numbered pages in general is usually pointless.

[Sean Sullivan]

"Value List Handler" pattern:
http://java.sun.com/blueprints/corej2eepatterns/Patterns/ValueListHandler.html

"DataListHandler" pattern
http://www.theserverside.com/resources/article.jsp?l=DataListHandler
http://www.theserverside.com/home/thread.jsp?thread_id=13939
http://www.theserverside.com/patterns/thread.jsp?thread_id=21434

article: ResultSet pagination using DB2, JDBC, and JSPs
http://www7b.boulder.ibm.com/dmdd/library/techarticle/0307balani/0307balani.html
DisplayTag (an open source JSP tag library)
The DisplayTag library provides tags for displaying large data sets.
The tag library supports: column display, sorting, paging,
cropping, grouping, exporting, and decoration.
http://displaytag.sourceforge.net/
Live demo @ http://www.displaytag.org/index.jsp
JDBC RowSet's (JSR-114)
http://jcp.org/aboutJava/communityprocess/first/jsr114/index.html

BEA's RowSetIterator
http://edocs.bea.com/workshop/docs81/doc/en/workshop/java-class/com/bea/wlw/netui/util/iterator/RowSetIterator.html
RowSetIterator in Oracle's BC4J
http://download-east.oracle.com/otn_hosted_doc/jdeveloper/904preview/bc4jjavadoc/rt/oracle/jbo/RowSetIterator.html