Achieving Stable Pagination: A Deep Dive into SQL Ordering

In the world of application development, presenting large datasets to users is a fundamental challenge. Whether it's a social media feed, a list of e-commerce products, or a history of financial transactions, overwhelming the user with thousands of rows at once is a recipe for poor performance and a frustrating user experience. The standard solution is pagination: breaking the data into manageable, digestible "pages." While seemingly straightforward, this common technique hides a subtle but critical pitfall that can lead to baffling bugs, including duplicate records appearing across pages or, conversely, records being skipped entirely. This behavior is not a random glitch; it's a direct consequence of a misunderstanding of how SQL databases handle ordering.

This article delves into the root cause of these common pagination problems, exploring the concept of deterministic versus non-deterministic ordering in SQL. We will dissect why a seemingly correct query can produce inconsistent results and provide robust, reliable solutions. Moving beyond simple fixes, we will also explore advanced, high-performance pagination strategies like keyset pagination (also known as the "seek method") that not only solve the data duplication issue but also offer significant performance benefits for large-scale applications.

The Anatomy of a Common Pagination Failure

Let's begin by examining the most common method for implementing pagination: using `LIMIT` and `OFFSET`. This approach is intuitive and widely taught. The idea is simple: for a page size of 10, page 1 retrieves records 1-10, page 2 retrieves 11-20, and so on. In SQL, this is typically translated using an `OFFSET` to skip a certain number of rows and a `LIMIT` to fetch the next set.

Consider a table named `ARTICLE`, which stores blog posts. A common requirement is to display these articles in reverse chronological order based on their publication time, stored in a `posted` column.

A query to fetch the second page of articles, with a page size of 10, would look like this:

-- Fetching Page 2 (articles 11 through 20)
SELECT
    id,
    title,
    posted
FROM
    ARTICLE
ORDER BY
    posted DESC
LIMIT 10 OFFSET 10;

On the surface, this query appears flawless. It sorts all articles by their `posted` timestamp in descending order and then skips the first 10 to retrieve the next 10. For many scenarios, this works perfectly. However, the problem arises when the sorting column—in this case, `posted`—contains non-unique values. Imagine a busy publishing system where multiple articles could be published or scheduled for the exact same second.

Visualizing the Instability

Let's illustrate this with a small sample of data from our `ARTICLE` table. Pay close attention to the articles with identical `posted` timestamps.

id (PK)	title	posted
105	'The Future of AI'	2023-11-15 10:30:05
104	'Quantum Computing Explained'	2023-11-15 10:30:00
103	'A Guide to Modern JavaScript'	2023-11-15 10:30:00
102	'Database Optimization Tips'	2023-11-15 10:30:00
101	'Introduction to Rust'	2023-11-15 09:00:00
100	'Getting Started with Docker'	2023-11-14 17:00:00

Now, let's run a paginated query with a page size of 2.

Query for Page 1:

SELECT id, title, posted FROM ARTICLE ORDER BY posted DESC LIMIT 2 OFFSET 0;

The database first sorts by `posted`. It sees ID 105 is the newest. Then it sees a three-way tie between IDs 104, 103, and 102. The SQL standard does not specify the order in which these tied rows should be returned. The database engine's query planner is free to return them in any order it deems most efficient at that moment. This could be based on the physical order on disk, the order they were inserted, or the result of a parallel query execution plan. Let's say for this first execution, it returns them in descending ID order.

Result for Page 1 (Execution A):

1. (105, 'The Future of AI', 2023-11-15 10:30:05)
2. (104, 'Quantum Computing Explained', 2023-11-15 10:30:00)

The user clicks "Next Page," and our application executes the query for page 2.

Query for Page 2:

SELECT id, title, posted FROM ARTICLE ORDER BY posted DESC LIMIT 2 OFFSET 2;

This is a completely new query execution. The database once again sorts by `posted`. Again, it finds the three-way tie. But this time, due to some internal factor (e.g., a different execution plan, data being moved in memory), the query planner decides to return the tied rows in a different order, perhaps by ascending ID.

The full, unstable order inside the database for this second execution might look like this:

1. (105, 'The Future of AI', 2023-11-15 10:30:05)
2. (102, 'Database Optimization Tips', 2023-11-15 10:30:00) <-- Order changed!
3. (103, 'A Guide to Modern JavaScript', 2023-11-15 10:30:00) <-- Order changed!
4. (104, 'Quantum Computing Explained', 2023-11-15 10:30:00) <-- Order changed!
5. (101, 'Introduction to Rust', 2023-11-15 09:00:00)
6. (100, 'Getting Started with Docker', 2023-11-14 17:00:00)

The query asks to `OFFSET 2` (skip the first two) and `LIMIT 2` (take the next two). Based on this new internal ordering, the result is:

Result for Page 2 (Execution B):

1. (103, 'A Guide to Modern JavaScript', 2023-11-15 10:30:00)
2. (104, 'Quantum Computing Explained', 2023-11-15 10:30:00) <-- DUPLICATE!

The user sees article with ID 104 on both page 1 and page 2. Furthermore, the article with ID 102 was skipped entirely. This is the essence of non-deterministic ordering, and it's a silent killer of reliable pagination.

The Core of the Problem: Deterministic vs. Non-Deterministic Sorting

To truly solve this issue, we must understand the underlying principle. A sorting operation is deterministic if, given the same input dataset and the same sorting criteria, it always produces the exact same output order. A sorting operation is non-deterministic if it can produce different output orders for the same input and criteria.

In SQL, an `ORDER BY` clause only guarantees a deterministic sort if the combination of columns in the clause is unique for every row in the result set. When the `ORDER BY` clause contains columns with duplicate values (a "tie"), the relative order of those tied rows is undefined. The database prioritizes performance and efficiency over providing a stable sort for these ties. It will pick whichever ordering is fastest to produce at the moment of execution.

This behavior is not a bug; it's a feature of relational database design that allows for significant performance optimizations. Forcing a stable sort on every query, even when not explicitly required, would add unnecessary overhead. The responsibility lies with the developer to provide the database with enough information to produce a fully stable, deterministic order when one is required, as is the case with pagination.

The Universal Solution: The Tie-Breaker

The solution is elegant in its simplicity: we must make the sorting criteria unique. We achieve this by adding a secondary sorting column to the `ORDER BY` clause—a column that is guaranteed to be unique across the entire table. This second column acts as a "tie-breaker." When the primary sorting column (`posted`) has identical values, the database will then use the tie-breaker column to determine the order, resulting in a fully stable and predictable sort.

The best candidate for a tie-breaker is almost always the table's primary key (`id` in our example), as it is, by definition, unique and non-null.

Let's modify our original query to include the `id` column as a tie-breaker:

SELECT
    id,
    title,
    posted
FROM
    ARTICLE
ORDER BY
    posted DESC, id DESC
LIMIT 10 OFFSET 10;

Let's trace the logic with this new query and our sample data. The database's sorting process now follows two rules:

1. First, sort all rows by `posted` in descending order.
2. If any rows have the same `posted` value, sort that subset of rows by `id` in descending order.

Applying this to our data, the internal, sorted list will always be:

id (PK)	title	posted	Reason for Order
105	'The Future of AI'	2023-11-15 10:30:05	Highest `posted` value.
104	'Quantum Computing Explained'	2023-11-15 10:30:00	Tied `posted`, highest `id` in tie.
103	'A Guide to Modern JavaScript'	2023-11-15 10:30:00	Tied `posted`, second-highest `id` in tie.
102	'Database Optimization Tips'	2023-11-15 10:30:00	Tied `posted`, lowest `id` in tie.
101	'Introduction to Rust'	2023-11-15 09:00:00	Next `posted` value.
100	'Getting Started with Docker'	2023-11-14 17:00:00	Lowest `posted` value.

This order is now fully deterministic. It will be identical every single time the query is run. Now, let's re-run our pagination queries with a page size of 2.

Query for Page 1 (Stable):

SELECT id, title, posted FROM ARTICLE ORDER BY posted DESC, id DESC LIMIT 2 OFFSET 0;

Result:

1. (105, 'The Future of AI', ...)
2. (104, 'Quantum Computing Explained', ...)

Query for Page 2 (Stable):

SELECT id, title, posted FROM ARTICLE ORDER BY posted DESC, id DESC LIMIT 2 OFFSET 2;

Result:

1. (103, 'A Guide to Modern JavaScript', ...)
2. (102, 'Database Optimization Tips', ...)

The results are now correct and consistent. No duplicates, no skipped records. The user experience is preserved, and the application behaves predictably. This simple addition of a unique tie-breaker to the `ORDER BY` clause is the fundamental solution to `LIMIT`/`OFFSET` pagination instability.

Database-Specific Tie-Breakers

While using a primary key is the most portable and recommended approach, some database systems offer internal, system-managed row identifiers that can also serve as a unique tie-breaker.

A notable example is SQLite's `ROWID`. By default, every table in SQLite has a hidden `ROWID` column which is a unique 64-bit signed integer that identifies the row. You can use it explicitly in your queries.

-- Stable pagination query in SQLite using ROWID
SELECT * FROM ARTICLE
ORDER BY posted DESC, ROWID DESC
LIMIT 10 OFFSET 10;

This works reliably in SQLite because the `ROWID` is guaranteed to be unique within the table. However, it's important to be cautious when using such database-specific features. Other systems have similar concepts (`ctid` in PostgreSQL, `ROWID` in Oracle), but their stability guarantees can be weaker; for instance, they might change after database maintenance operations like `VACUUM`. For cross-database compatibility and clarity of intent, explicitly using your own primary key (`id`) remains the superior strategy.

Beyond `OFFSET`: Keyset Pagination (The Seek Method)

Fixing the ordering stability is a crucial first step. However, the `LIMIT`/`OFFSET` method itself has a significant performance drawback that becomes severe with large datasets. When you request a deep page, for example `OFFSET 1000000`, the database still has to fetch, sort, and process all 1,000,010 rows before it can discard the first million and return your 10. This work increases linearly with the offset, making deep pagination extremely slow.

A more advanced and performant technique is Keyset Pagination, often called the "seek method" or "cursor-based pagination." Instead of telling the database how many rows to *skip* (an offset), you tell it *where* to start fetching from, using the values of the last row from the previous page as a "key."

This method completely avoids the `OFFSET` clause. The key requirements are:

1. A stable, deterministic sort order (which we've already established with a tie-breaker).
2. An index on the columns used in the `ORDER BY` clause for performance.

How Keyset Pagination Works

Let's walk through an example using our stable `ORDER BY posted DESC, id DESC` clause.

Step 1: Fetch the first page.

The query for the first page is simple. It doesn't need a `WHERE` clause related to pagination.

-- Fetching Page 1
SELECT id, title, posted
FROM ARTICLE
ORDER BY posted DESC, id DESC
LIMIT 10;

Let's assume the 10th (last) record returned from this query has `posted = '2023-11-10 12:00:00'` and `id = 542`.

Step 2: Fetch the next page.

To get the next page, we pass these two values (`2023-11-10 12:00:00` and `542`) to the application. The query for the second page uses these values in the `WHERE` clause to find the next set of rows. We want to find all articles that are "older" than this last one.

The logic is: find rows where the `posted` time is earlier, OR where the `posted` time is the same but the `id` is smaller.

-- Fetching Page 2 using Keyset Pagination
SELECT id, title, posted
FROM ARTICLE
WHERE
    -- Condition for the composite sort key (posted, id)
    posted < '2023-11-10 12:00:00'
    OR (posted = '2023-11-10 12:00:00' AND id < 542)
ORDER BY
    posted DESC, id DESC
LIMIT 10;

Many modern databases support a more concise syntax for this using row value constructors, which is easier to read and can be better optimized by the query planner:

-- Fetching Page 2 using row value constructor syntax (PostgreSQL, MySQL, etc.)
SELECT id, title, posted
FROM ARTICLE
WHERE
    (posted, id) < ('2023-11-10 12:00:00', 542)
ORDER BY
    posted DESC, id DESC
LIMIT 10;

Advantages and Disadvantages of Keyset Pagination

Advantages:

• Exceptional Performance: This method is incredibly fast, even for very deep pages. With an appropriate index on `(posted, id)`, the database can instantly "seek" to the starting point without scanning and discarding millions of rows. The query time is roughly constant, regardless of which page you're on.
• Stateless and Stable: It's inherently immune to the duplicate/skipped row problem because it doesn't rely on a fragile offset. Even if new rows are inserted while a user is paginating, their view remains consistent. A new article published at the top of the list won't shift all subsequent pages.

Disadvantages:

• No Arbitrary Page Jumps: The primary drawback is that you cannot easily jump to a specific page number (e.g., "Go to page 50"). The logic is strictly "Next" and "Previous." To get to page 50, you would have to sequentially fetch the keys from the previous 49 pages. This makes it ideal for infinite scrolling interfaces but less suitable for interfaces with numbered page links.
• More Complex Implementation: The client-side logic is slightly more complex, as it needs to store the sort key values from the last item of the current page to request the next one, rather than just incrementing a page number.

Conclusion: Building Robust Data Interfaces

What begins as a simple task—displaying a list of items—can quickly expose deep-seated issues in how we interact with our databases. The problem of duplicate or missing records in pagination is not a database bug but a design flaw in the query, stemming from a non-deterministic `ORDER BY` clause.

The key takeaways for building robust, scalable, and reliable paginated systems are clear:

1. Always Ensure a Deterministic Order: Whenever you use `ORDER BY` for pagination, you must guarantee a stable sort. The most reliable way to do this is by adding a unique column, typically the primary key, as the final tie-breaker in your `ORDER BY` clause.
2. Understand the Limitations of `OFFSET`: While easy to implement, `LIMIT`/`OFFSET` pagination suffers from significant performance degradation on large tables. Be aware of this limitation and consider it a potential performance bottleneck as your application grows.
3. Embrace Keyset Pagination for Performance: For high-performance applications, especially those with infinite scrolling or simple "Next/Previous" navigation, keyset pagination is the superior approach. It offers consistent, fast query times and enhanced data consistency, providing a much better user experience at scale.

By understanding the fundamental principles of SQL ordering and choosing the right pagination strategy for your use case, you can move from building fragile interfaces that are prone to subtle bugs to architecting resilient systems that are both correct and performant, regardless of the size of your data.