Fast, Stateless Paging
When the result of a database query is so large that it is impractical to return the entire thing at once, the rows can often be accessed via a paging mechanism. Paging involves iterating through the entire result set by retrieving small number of rows (called a page) at a time.
A typical implementation of a paging mechanism may impose a well-defined ordering onto the result set. For each subsequent page, the query is performed again and all rows previously returned will be skipped. There are at least two obvious drawbacks to this approach:
One could also imagine an implementation that saves server-side state and locks the table while the results are being paged. This gives O(n) performance at the cost of locking out all other processes.
This invention, published while I worked for AMI, describes an O(n) paging mechanism that requires no inter-page locking and no server-side state.
Data Store with Lock-Free Stateless Paging Capability, USPTO application 20060129540