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?"

Practice

1. What is the main purpose of indexes in Firestore queries?

easy

A. To make queries faster and more efficient

B. To store large files like images

C. To backup data automatically

D. To encrypt data for security

Solution

1. Step 1: Understand what indexes do in Firestore

   Indexes help Firestore find data quickly without scanning all documents.

2. Step 2: Relate indexes to query performance

   By using indexes, queries run faster and use less resources.

3. Final Answer:

   To make queries faster and more efficient -> Option A

4. Quick Check:

   Indexes speed up queries = D [OK]

Hint: Indexes speed up data search in Firestore queries [OK]

Common Mistakes:

• Thinking indexes store files
• Confusing indexes with backups
• Assuming indexes encrypt data

2. Which of the following is the correct syntax to create a simple Firestore query filtering by a field age equal to 30?

easy

A. db.collection('users').filter('age', '=', 30)

B. db.collection('users').where('age', '==', 30)

C. db.collection('users').query('age' == 30)

D. db.collection('users').find('age', 30)

Solution

1. Step 1: Recall Firestore query syntax

   Firestore uses where(field, operator, value) to filter data.

2. Step 2: Match syntax with options

   db.collection('users').where('age', '==', 30) uses where('age', '==', 30), which is correct syntax.

3. Final Answer:

   db.collection('users').where('age', '==', 30) -> Option B

4. Quick Check:

   Correct Firestore filter syntax = B [OK]

Hint: Use .where(field, '==', value) for filtering in Firestore [OK]

Common Mistakes:

• Using .filter instead of .where
• Using == inside query string
• Using .find which is not Firestore syntax

3. Given this Firestore query:

db.collection('orders').where('status', '==', 'shipped').orderBy('date', 'desc')

What must you do to avoid an error when running this query?

medium

A. Remove the orderBy clause

B. Create a single-field index on date only

C. No index needed, Firestore handles it automatically

D. Create a composite index on status and date

Solution

1. Step 1: Understand query with multiple filters and sorting

   This query filters by status and sorts by date.

2. Step 2: Know Firestore index requirements

   Firestore requires a composite index for queries with multiple filters or sorting on different fields.

3. Final Answer:

   Create a composite index on status and date -> Option D

4. Quick Check:

   Composite index needed for multiple filters + orderBy = A [OK]

Hint: Use composite indexes for queries with filters and sorting [OK]

Common Mistakes:

• Assuming single-field index is enough
• Thinking Firestore auto-creates all indexes
• Removing orderBy to fix error

4. You wrote this Firestore query:

db.collection('products').where('price', '>', 100).orderBy('name')

But it gives an error about missing index. What is the best fix?

medium

A. Change price filter to ==

B. Remove the orderBy clause

C. Create a composite index on price (ascending) and name (ascending)

D. Create a single-field index on name only

Solution

1. Step 1: Identify query components causing index error

   The query filters by price > 100 and orders by name.

2. Step 2: Understand Firestore index needs for range filter + orderBy

   Firestore requires a composite index on both fields with correct sort order.

3. Final Answer:

   Create a composite index on price (ascending) and name (ascending) -> Option C

4. Quick Check:

   Composite index needed for range filter + orderBy = C [OK]

Hint: Create composite index matching filter and orderBy fields [OK]

Common Mistakes:

• Removing orderBy instead of indexing
• Changing filter operator incorrectly
• Creating only single-field index

5. You want to query a Firestore collection events to find documents where type is 'conference' and attendees is greater than 100, sorted by date ascending. Which index should you create to support this query?

hard

A. Composite index on type (ascending), attendees (ascending), and date (ascending)

B. Single-field index on date only

C. Composite index on type (descending) and date (ascending)

D. No index needed, Firestore supports this query by default

Solution

1. Step 1: Analyze query filters and sorting

   The query filters by type == 'conference' and attendees > 100, and sorts by date ascending.

2. Step 2: Determine required index type

   Multiple filters plus sorting require a composite index including all these fields with correct order.

3. Final Answer:

   Composite index on type (ascending), attendees (ascending), and date (ascending) -> Option A

4. Quick Check:

   Composite index covers all filters and orderBy fields = A [OK]

Hint: Include all filter and orderBy fields in composite index [OK]

Common Mistakes:

• Creating only single-field index
• Using wrong sort order in index
• Assuming no index needed