Compound queries (multiple where) in Firebase - Time & Space Complexity

Time Complexity: Compound queries (multiple where)

O(n * k)

Understanding Time Complexity

When using compound queries with multiple conditions in Firebase, it's important to understand how the number of conditions affects the work done behind the scenes.

We want to know how the time to get results changes as we add more conditions.

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

const query = firestore.collection('users')
  .where('age', '>=', 18)
  .where('city', '==', 'New York')
  .where('active', '==', true);

const results = await query.get();
    

This sequence fetches users who are adults, live in New York, and are active.

Identify Repeating Operations

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

• Primary operation: Executing the query with multiple where conditions.
• How many times: Each condition adds one filter operation internally.

How Execution Grows With Input

Each added condition narrows down the data, but the query engine must check each condition for every relevant document.

Input Size (n)	Approx. Api Calls/Operations
10	About 3 filter checks per document, total ~30 checks
100	About 3 filter checks per document, total ~300 checks
1000	About 3 filter checks per document, total ~3000 checks

Pattern observation: The total checks grow roughly in proportion to the number of documents times the number of conditions.

Final Time Complexity

Time Complexity: O(n * k)

This means the time grows with the number of documents (n) and the number of conditions (k) in the query.

Common Mistake

[X] Wrong: "Adding more where conditions does not affect query time because the database is optimized."

[OK] Correct: Each condition adds work to check documents, so more conditions mean more checks, increasing time.

Interview Connect

Understanding how query complexity grows helps you design efficient data fetching and shows you can think about performance in real projects.

Self-Check

"What if we replaced multiple where conditions with a single composite index? How would the time complexity change?"