Limit and pagination in Firebase - Time & Space Complexity

Time Complexity: Limit and pagination

O(n)

Understanding Time Complexity

When fetching data from Firebase, using limits and pagination helps control how much data you get at once.

We want to understand how the number of data fetches grows as we ask for more pages.

Scenario Under Consideration

Analyze the time complexity of fetching paged data with limits.

const pageSize = 10;
let lastVisible = null;

async function fetchNextPage() {
  let query = firestore.collection('items').orderBy('name').limit(pageSize);
  if (lastVisible) {
    query = query.startAfter(lastVisible);
  }
  const snapshot = await query.get();
  lastVisible = snapshot.docs[snapshot.docs.length - 1];
  return snapshot.docs.map(doc => doc.data());
}
    

This code fetches items in pages of 10, starting after the last item from the previous page.

Identify Repeating Operations

• Primary operation: Firestore query with limit and startAfter to fetch a page.
• How many times: Once per page requested by the user.

How Execution Grows With Input

Each page fetch makes one query call that returns a fixed number of items.

Input Size (pages requested)	Approx. Api Calls/Operations
1	1 query call
10	10 query calls
100	100 query calls

Pattern observation: The number of query calls grows linearly with the number of pages requested.

Final Time Complexity

Time Complexity: O(n)

This means if you want to see more pages, the number of queries grows directly with how many pages you fetch.

Common Mistake

[X] Wrong: "Fetching page 10 is just one query, so it takes the same time as page 1 regardless of previous pages."

[OK] Correct: Each page requires a separate query call, so fetching page 10 means you have made 10 queries in total, one for each page.

Interview Connect

Understanding how pagination affects query calls helps you design apps that load data smoothly and efficiently.

Self-Check

What if we changed the page size from 10 to 100? How would the time complexity change?

Practice

1. What does the limit() function do in Firebase queries?

easy

A. It restricts the number of documents returned by the query.

B. It sorts the documents in ascending order.

C. It filters documents based on a condition.

D. It deletes documents from the collection.

Solution

1. Step 1: Understand the purpose of limit()

   The limit() function is used to control how many documents are returned in a query result.

2. Step 2: Compare options with limit() behavior

   Only It restricts the number of documents returned by the query. correctly describes that limit() restricts the number of documents returned.

3. Final Answer:

   It restricts the number of documents returned by the query. -> Option A

4. Quick Check:

   limit() controls result count = B [OK]

Hint: Limit sets max items returned in query [OK]

Common Mistakes:

• Confusing limit() with orderBy()
• Thinking limit() filters data
• Assuming limit() deletes data

2. Which of the following is the correct syntax to get the first 5 documents ordered by 'timestamp' in Firebase?

easy

A. db.collection('posts').limit(5).orderBy('timestamp')

B. db.collection('posts').orderBy('timestamp').limit(5)

C. db.collection('posts').limit(5, 'timestamp')

D. db.collection('posts').orderBy('timestamp', 5)

Solution

1. Step 1: Recall correct method chaining order

   In Firebase, orderBy() must come before limit() to sort then limit results.

2. Step 2: Check each option's method order and parameters

   db.collection('posts').orderBy('timestamp').limit(5) correctly orders by 'timestamp' then limits to 5 documents. Others have wrong order or invalid parameters.

3. Final Answer:

   db.collection('posts').orderBy('timestamp').limit(5) -> Option B

4. Quick Check:

   orderBy before limit = C [OK]

Hint: Always orderBy before limit in Firebase queries [OK]

Common Mistakes:

• Placing limit() before orderBy()
• Passing limit a field name
• Using orderBy with a number parameter

3. Given this Firebase query code:

const firstPage = await db.collection('items').orderBy('name').limit(3).get();
const lastVisible = firstPage.docs[firstPage.docs.length - 1];
const nextPage = await db.collection('items').orderBy('name').startAfter(lastVisible).limit(3).get();
console.log(nextPage.docs.length);

What will be printed if the collection has 7 documents?

medium

A. 3

B. 4

C. 7

D. 0

Solution

1. Step 1: Analyze first page query

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

2. Step 2: Analyze next page query

   The next query starts after the last document of the first page and limits to 3 documents. Since total is 7, remaining documents are 4 (docs 4 to 7), but limit(3) returns 3 documents.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   7 total - 3 first page = 4 remaining, limit(3) = 3 [OK]

Hint: Subtract first page count from total for next page size [OK]

Common Mistakes:

• Assuming next page always has same limit count
• Ignoring startAfter effect
• Counting all documents again

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

const firstPage = await db.collection('users').limit(5).orderBy('age').get();

What is the error and how to fix it?

medium

A. Error: get() must be called before limit(); call get() first.

B. Error: limit() requires a field name; add 'age' as parameter.

C. Error: orderBy must come before limit; fix by swapping the methods.

D. No error; code works fine.

Solution

1. Step 1: Identify method order error

   Firebase requires orderBy() before limit() to sort data before limiting.

2. Step 2: Fix by swapping method calls

   Change code to db.collection('users').orderBy('age').limit(5).get() to fix the error.

3. Final Answer:

   Error: orderBy must come before limit; fix by swapping the methods. -> Option C

4. Quick Check:

   orderBy before limit fixes error = A [OK]

Hint: Always call orderBy before limit to avoid errors [OK]

Common Mistakes:

• Calling limit before orderBy
• Passing field name to limit
• Calling get() too early

5. You want to paginate through a Firebase collection with 12 documents, showing 5 per page. After fetching the first two pages, how many documents will the third page query return?

hard

A. 0

B. 3

C. 5

D. 2

Solution

1. Step 1: Calculate documents fetched in first two pages

   Each page shows 5 documents, so first two pages fetch 5 + 5 = 10 documents.

2. Step 2: Calculate remaining documents for third page

   Total documents are 12, so remaining are 12 - 10 = 2 documents.

3. Step 3: Consider limit on third page

   Limit is 5, but only 2 documents remain, so third page returns 2 documents.

4. Final Answer:

   2 -> Option D

5. Quick Check:

   12 - 10 = 2 documents left for page 3 [OK]

Hint: Subtract fetched docs from total to find last page size [OK]

Common Mistakes:

• Assuming all pages have full 5 documents
• Ignoring total document count
• Confusing page number with document count