Cursor-based pagination (startAfter, endBefore) in Firebase - Time & Space Complexity

Time Complexity: Cursor-based pagination (startAfter, endBefore)

O(p)

Understanding Time Complexity

When using cursor-based pagination in Firebase, we want to know how the number of operations changes as we ask for more data pages.

We ask: How does fetching pages with cursors affect the work Firebase does?

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

const pageSize = 10;
let lastVisible = null;

// Fetch first page
const firstPage = await firestore.collection('items')
  .orderBy('createdAt')
  .limit(pageSize)
  .get();

lastVisible = firstPage.docs[firstPage.docs.length - 1];

// Fetch next page using cursor
const nextPage = await firestore.collection('items')
  .orderBy('createdAt')
  .startAfter(lastVisible)
  .limit(pageSize)
  .get();
    

This code fetches a page of items ordered by creation time, then fetches the next page starting after the last item of the previous page.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Querying Firestore with a cursor and limit to fetch a page of documents.
• How many times: Once per page requested by the user.

How Execution Grows With Input

Each page fetch asks for a fixed number of documents, so the work per page stays about the same.

Input Size (n)	Approx. Api Calls/Operations
10 (1 page)	1 query fetching 10 documents
100 (10 pages)	10 queries each fetching 10 documents
1000 (100 pages)	100 queries each fetching 10 documents

Pattern observation: The number of queries grows linearly with the number of pages requested, but each query fetches a fixed number of documents.

Final Time Complexity

Time Complexity: O(p)

This means the total work grows linearly with the number of pages fetched, but each page fetch cost stays constant.

Common Mistake

[X] Wrong: "Fetching the next page with startAfter means Firebase scans all previous documents again, so cost grows with total data size."

[OK] Correct: Firebase uses indexes and the cursor to jump directly to the start point, so each page fetch only reads the page size number of documents, not all before it.

Interview Connect

Understanding how cursor-based pagination scales helps you design smooth user experiences and efficient data fetching in real apps.

Self-Check

"What if we changed from fixed page size to fetching all documents up to the cursor each time? How would the time complexity change?"

Practice

1. What does the startAfter method do in Firebase cursor-based pagination?

easy

A. It loads all documents from the beginning.

B. It ends the query before a specific document snapshot.

C. It deletes documents after a specific snapshot.

D. It starts loading documents after a specific document snapshot.

Solution

1. Step 1: Understand the purpose of startAfter

   startAfter tells Firebase to begin loading documents after the given document snapshot, skipping that snapshot itself.

2. Step 2: Compare with other cursor methods

   endBefore stops before a snapshot, but startAfter moves forward after it.

3. Final Answer:

   It starts loading documents after a specific document snapshot. -> Option D

4. Quick Check:

   startAfter = start after snapshot [OK]

Hint: Remember: startAfter skips the given document and moves forward [OK]

Common Mistakes:

• Confusing startAfter with endBefore
• Thinking startAfter includes the given document
• Assuming startAfter loads all documents from start

2. Which of the following is the correct syntax to start a query after a document snapshot named lastDoc in Firebase?

easy

A. query.startAfter(lastDoc)

B. query.endAfter(lastDoc)

C. query.startBefore(lastDoc)

D. query.endBefore(lastDoc)

Solution

1. Step 1: Recall Firebase query cursor methods

   The correct method to start after a document is startAfter().

2. Step 2: Match method with snapshot variable

   Using startAfter(lastDoc) correctly applies the cursor after the lastDoc snapshot.

3. Final Answer:

   query.startAfter(lastDoc) -> Option A

4. Quick Check:

   Correct method is startAfter() [OK]

Hint: Use startAfter(snapshot) to move forward in pagination [OK]

Common Mistakes:

• Using non-existent methods like endAfter or startBefore
• Mixing up startAfter and endBefore
• Forgetting to pass the snapshot as argument

3. Given the following code snippet, what documents will be returned?

const firstPage = await collection.orderBy('name').limit(3).get();
const nextPage = await collection.orderBy('name').startAfter(firstPage.docs[2]).limit(3).get();

medium

A. Documents 1 to 3 on firstPage, documents 4 to 6 on nextPage

B. Documents 1 to 3 on firstPage, documents 3 to 5 on nextPage

C. Documents 1 to 2 on firstPage, documents 3 to 5 on nextPage

D. Documents 1 to 3 on firstPage, documents 1 to 3 again on nextPage

Solution

1. Step 1: Understand firstPage query

   The first query orders by 'name' and limits to 3 documents, so it returns documents 1, 2, and 3.

2. Step 2: Understand nextPage query with startAfter

   Using startAfter(firstPage.docs[2]) starts after the third document, so nextPage returns documents 4, 5, and 6.

3. Final Answer:

   Documents 1 to 3 on firstPage, documents 4 to 6 on nextPage -> Option A

4. Quick Check:

   startAfter skips last doc, nextPage continues [OK]

Hint: startAfter skips last doc, next page continues from next doc [OK]

Common Mistakes:

• Assuming startAfter includes the last document again
• Confusing document indexes (0-based vs 1-based)
• Not ordering consistently before pagination

4. You wrote this code but it throws an error:

const prevPage = await collection.orderBy('date').endBefore(lastDoc).limitToLast(3).get();

What is the likely cause?

medium

A. Using limitToLast without endBefore causes error

B. You must use startAfter instead of endBefore

C. The lastDoc snapshot is not from the same query order

D. Firebase does not support endBefore with limitToLast

Solution

1. Step 1: Check cursor snapshot origin

   The snapshot lastDoc must come from a query with the same ordering and filters.

2. Step 2: Understand error cause

   If lastDoc is from a different query or unordered, Firebase throws an error.

3. Final Answer:

   The lastDoc snapshot is not from the same query order -> Option C

4. Quick Check:

   Cursor snapshot must match query order [OK]

Hint: Cursor snapshot must come from same ordered query [OK]

Common Mistakes:

• Using snapshot from different query or order
• Mixing startAfter and endBefore incorrectly
• Ignoring need for consistent ordering

5. You want to implement backward pagination to load previous 5 documents before a known document snapshot currentDoc. Which Firebase query correctly achieves this?

hard

A. collection.orderBy('timestamp').startAfter(currentDoc).limit(5)

B. collection.orderBy('timestamp').endBefore(currentDoc).limitToLast(5)

C. collection.orderBy('timestamp').startAt(currentDoc).limit(5)

D. collection.orderBy('timestamp').endAt(currentDoc).limitToLast(5)

Solution

1. Step 1: Understand backward pagination

   To load documents before currentDoc, use endBefore(currentDoc).

2. Step 2: Use limitToLast for correct order

   Using limitToLast(5) returns the last 5 documents before currentDoc in correct order.

3. Final Answer:

   collection.orderBy('timestamp').endBefore(currentDoc).limitToLast(5) -> Option B

4. Quick Check:

   Backward pagination uses endBefore + limitToLast [OK]

Hint: Backward pagination = endBefore + limitToLast [OK]

Common Mistakes:

• Using startAfter for backward pagination
• Using limit instead of limitToLast when going backward
• Confusing endBefore with endAt