How does MongoDB pagination work and why is skip/limit inefficient at scale?

Expected Interview Answer

Step-by-Step Explanation

1. Step 1

   Understand the naive approach

   db.coll.find(query).sort({_id:1}).skip((page-1)*size).limit(size) returns a page but re-scans all skipped documents each call.

2. Step 2

   Measure the cost

   Run explain() and note that totalDocsExamined grows with the skip value while limit stays fixed — the deeper the page, the more waste.

3. Step 3

   Pick a stable sort key

   Choose an indexed, unique, monotonic field (often _id or a compound of timestamp + _id) to define a strict ordering.

4. Step 4

   Track the boundary cursor

   Return the last document's sort value to the client and use it as the starting point for the next request.

5. Step 5

   Query by range

   Fetch the next page with find({ _id: { $gt: lastId } }).sort({_id:1}).limit(size), which seeks the index directly to the boundary.

6. Step 6

   Ensure an index covers the sort

   Confirm the sort/filter fields are backed by an index so the query is an efficient index range scan, not an in-memory sort.

Code Example

const pageSize = 20;
const page = 500; // deep page

const results = await db.collection('orders')
  .find({ status: 'shipped' })
  .sort({ _id: 1 })
  .skip((page - 1) * pageSize) // scans 9,980 docs just to discard them
  .limit(pageSize)
  .toArray();

const pageSize = 20;
// lastId comes from the last document of the previous page
async function nextPage(lastId) {
  const filter = { status: 'shipped' };
  if (lastId) filter._id = { $gt: lastId };

  const results = await db.collection('orders')
    .find(filter)
    .sort({ _id: 1 })
    .limit(pageSize)
    .toArray();

  const nextCursor = results.length ? results[results.length - 1]._id : null;
  return { results, nextCursor };
}

// Index that backs both the filter and the sort:
// db.orders.createIndex({ status: 1, _id: 1 })

Follow-up Questions

• How would you paginate by a non-unique field like createdAt?
• Why can keyset pagination not jump directly to an arbitrary page number?
• How does explain() reveal the cost of a deep skip?
• What compound index would you create for range pagination?
• How do cursor-based APIs (like GraphQL Relay) map onto keyset pagination?