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:

1. Since this works by counting the number of results that have already been returned, it is possible for rows to be returned twice (or not at all) if inserts and deletes are interleaved with the page requests.
2. This makes the time complexity of retrieving the full result set O(n²), where n is the number of rows in the result.

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