Pagination and SQL
Almost all applications require end-users to search through information. Search results are often shown in some sort of list controls such as Grid, Listview etc. It is very often the case that the search results contain too many records to show in one page. In those cases, search results are shown one page after another, each page containing fixed number of records.
Various solutions have been tried by solution developers. They include creating temporary tables that contain the result set to caching the result set in middle-tier for faster access. There are pros and cons to each approach which I will not delving into.
This article explains another way to do pagination. This mechanism leaves most of the work to RDBMS query execution engine. It works like this.
- Presentation layer executes the initial search query based on user preferences. This query returns top <n> rows where n = pagesize.
- Presentation layer code then saves information about first row and last row fetched.
- When user triggers 'Previous' command, presentation layer goes back to SQL and fetches a page of matched records before the first row.
- When user triggers 'Next' command, PL goes back to SQL and fetches a page of matched records after the last row
Here is an example. Let's take the example of Employees table in Northwind database. This table contains following fields (Data types are not included for brevity)
EmployeeId (PK), LastName, FirstName, Title, BirthDate and other fields.
Let's say that we want to search employees by last name. The result sets should be ordered by last name.
Here is the initial query. I am assuming the page size is 20.
Select Top 20 LastName, FirstName, Title
From Employees
Where LastName like @searchpattern --passed as input
Order By LastName
After executing this, presentation layer store the values for LastName from the first row and last row in its state. This will be used in the processing of Previous and Next commands.
Previous Query
When user wants to see the previous page, presentation layer sends a query to SQL that returns a page of matched records. Search predicate should be modified as follows
Where Clause := LastName like @lastname and LastName < <Value of last name from the first row>
Now the query looks like this
Select Top 20 LastName, FirstName, Title
From Employees
Where LastName like @searchpattern and LastName < @lastnamefromfirstrow --passed as input
Order By LastName
Next query
Processing 'Next' is very similar to previous. The search predicate would look like
Where clause := LastName like @lastname and LastName > <Value of last name from the last row>
Select Top 20 LastName, FirstName, Title
From Employees
Where LastName like @searchpattern and LastName > @lastnamefromlastrow --passed as input
Order By LastName
Are we done? Not quite. These queries will work only if the LastName is unique, which we all know is not the case. So what should we do?
In these cases, we should include additional fields that make each record in the result set unique. For example, adding EmployeeId as part of projection would guarantee uniqueness of record in the result set and order the result sets based on LastName followed by EmployeeId.
Here are the modified queries
Initial query
Select Top 20 EmployeeId, LastName, FirstName, Title
From Employees
Where LastName like @lastname --passed as input
Order By LastName, EmployeeId
Prev Query
Select Top 20 LastName, FirstName, Title
From Employees
Where LastName like @searchpattern and
( (LastName < @lastnamefromfirstrow) or
((LastName=@lastnamefromfirstrow) and (EmployeeId < @empidfromfirstrow))
Order By LastName, EmployeeId
This makes sure that even if the LastName is not unique, the previous query returns correct results. Next query is very similar to previous query.
You can see that the query gets complicated due to uniqueness issue. But, it is easy to come up with a general form to frame queries appropriately. Also, one should create appropriate indices to make sure that the performance doesn't suffer. Stored procedures can also be used for faster processing.
Issues with this approach
Main issue with this approach is that there are certain scenarios where things get difficult. For example, if you want to go to LastPage, or page <n>, then you have to stroll through one page after another to go to the page. There are ways to optimize this, but it needs little bit of additional coding and of course, there is a definite perf cost associated with this.
But if your scenarios support only Prev and Next primitives, then this would work just fine.
Comments
Anonymous
December 22, 2003
Another issue is where you have to sortable paging grid. Changing the sort is like the initial query, but you have to be able to pass in the sort column as a parameter.Anonymous
December 22, 2003
I am not sure if this is an issue. But, like you have correctly said, when user changes the sort column, then your query will change.
Making this as a stored procedure will definitely be an issue if the users are allowed to change sort fields.Anonymous
December 22, 2003
bug: you order on Lastname and then on employeeid. This can cause a situation where employeeid is lower in a page after the current than last employeeid on the current page.Anonymous
December 22, 2003
Here's a similar solution that's a little bit more thorough:
http://weblogs.asp.net/pwilson/posts/31456.aspxAnonymous
December 22, 2003
Frans Bouma:
I don't see how it is a bug. The result is always ordered first on last name and then on employee id. Can you give a scenario where it breaks?
Paul:
I wanted to avoid nested queries. In essence, both are similar algorithms. And, yes, one can build a dynamic sql just like you did :) I really didn't want to get side tracked into dynamic sql vs stored procs discussion :)Anonymous
December 22, 2003
It's speculation, but row 11 has a lastname that is > lastname of row 10, but employeeid of row 11 is < than employeeid row 10, at least that's a scenario that will break with a page of 10 items I think. (it will duplicate rows)Anonymous
December 23, 2003
Frans:
OR condition takes care of it. If you look at the predicate for prev query
(LastName < @lastnamefromfirstrow) OR
((LastName=@lastnamefromfirstrow) and (EmployeeId < @empidfromfirstrow))
So if the LastName < @last name from the first row, then the row is selected.Anonymous
December 26, 2003
Paul:
I looked at your post again and your mechanism will work for a table. It is not generic enough to handle scenarios where the query may have to do join among multiple tables or views.
I will post a generic mechanism that handles all the scenarios soon. This is just a sample.Anonymous
December 29, 2003
The biggest killer with this approach that stopped us from using it was that it can't handle the situation where the number of rows in the table may change while the user is paging through it.Anonymous
December 29, 2003
Re comment 46332
I understand this issue. But there are many ways to counter this. For example, you can periodically get the count to see if it has changed (Even this is not reliable). From my experience, users are willing to tolerate certain misses. In fact, if you look at the normal user behavior: they do a initial search and if the record they are looking for is not found in first few pages, they will prune the search.
Think of airline or library system. When you call support, they ask for your last name. Then they start typing your last name. As they type, they get matched records based on partial entry. They continue to prune the search until they can actually locate the record easily.
BTW alternatives are horrible and they usually don't scale..Anonymous
June 02, 2009
PingBack from http://patiochairsite.info/story.php?id=29350Anonymous
June 16, 2009
PingBack from http://fixmycrediteasily.info/story.php?id=16158