Firestore queries and indexes in GCP - Time & Space Complexity

Time Complexity: Firestore queries and indexes

O(k)

Understanding Time Complexity

When using Firestore, queries rely on indexes to find data quickly. Understanding how query time grows helps us design better databases.

We want to know: how does the number of documents or indexes affect query speed?

Scenario Under Consideration

Analyze the time complexity of this Firestore query with indexes.

const query = firestore.collection('users')
  .where('age', '>=', 18)
  .where('city', '==', 'Seattle')
  .orderBy('lastName')
  .limit(20);
const results = await query.get();
    

This query fetches up to 20 users aged 18 or older living in Seattle, ordered by last name, using Firestore indexes.

Identify Repeating Operations

Look at what Firestore does behind the scenes for this query.

• Primary operation: Firestore uses an index to find matching documents.
• How many times: The index lookup happens once per query, scanning only relevant entries.

How Execution Grows With Input

As the number of matching documents grows, Firestore reads more index entries but stops after the limit.

Input Size (n)	Approx. Index Reads
10	10 or fewer (stops at limit)
100	20 (due to limit)
1000	20 (still limited)

Pattern observation: The query reads up to the limit number of index entries, so time grows with the limit, not total data size.

Final Time Complexity

Time Complexity: O(k)

This means query time grows with the number of results requested, not the total documents in the collection.

Common Mistake

[X] Wrong: "Query time grows with the total number of documents in the collection."

[OK] Correct: Firestore uses indexes to jump directly to matching entries, so it does not scan all documents.

Interview Connect

Knowing how Firestore queries scale helps you design fast, efficient apps and shows you understand cloud database performance.

Self-Check

"What if we remove the limit clause? How would the time complexity change?"