Querying and filtering in Firebase - Time & Space Complexity

Time Complexity: Querying and filtering

O(log n)

Understanding Time Complexity

When we ask Firebase to find data by filtering, we want to know how long it takes as data grows.

We ask: How does the time to get filtered results change when there are more items?

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

const query = firestore.collection('users')
  .where('age', '>=', 18)
  .where('status', '==', 'active')
  .orderBy('age')
  .limit(50);
const snapshot = await query.get();

This code asks Firebase to find up to 50 users who are adults and active, sorted by age.

Identify Repeating Operations

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

• Primary operation: The query request sent to Firebase to filter and sort data.
• How many times: This happens once per query, but internally Firebase scans matching records.

How Execution Grows With Input

As the number of users grows, Firebase uses indexes to quickly find matches without scanning all data.

Input Size (n)	Approx. Api Calls/Operations
10	Few operations, quick response
100	Still few operations, fast due to indexing
1000	Operations grow slowly, still efficient with indexes

Pattern observation: Thanks to indexes, the work grows slowly, not directly with total data size.

Final Time Complexity

Time Complexity: O(log n)

This means the time to get filtered results grows slowly as data grows, because Firebase uses indexes.

Common Mistake

[X] Wrong: "Querying with filters always scans all data, so time grows linearly with data size."

[OK] Correct: Firebase uses indexes to jump directly to matching data, so it does not scan everything.

Interview Connect

Understanding how queries scale shows you know how cloud databases handle data efficiently, a useful skill in many jobs.

Self-Check

"What if we removed the index on 'age'? How would the time complexity change?"

Practice

1. What does the where method do in a Firestore query?

easy

A. Limits the number of documents returned

B. Sorts documents in ascending order

C. Filters documents based on a condition

D. Deletes documents matching a condition

Solution

1. Step 1: Understand the purpose of where

   The where method is used to filter documents by specifying a condition on a field.

2. Step 2: Compare with other query methods

   orderBy sorts documents, limit restricts count, and deletion is unrelated.

3. Final Answer:

   Filters documents based on a condition -> Option C

4. Quick Check:

   where = filter condition [OK]

Hint: Remember: where filters, orderBy sorts, limit restricts [OK]

Common Mistakes:

• Confusing where with orderBy
• Thinking where limits results
• Assuming where deletes data

2. Which of the following is the correct syntax to filter documents where the field age is greater than 18 in Firestore?

easy

A. query.where('age', '>', 18)

B. query.where('age' > 18)

C. query.where('age', 'greater', 18)

D. query.where('age', '>=', '18')

Solution

1. Step 1: Check Firestore where syntax

   The correct syntax uses three arguments: field name, operator as string, and value.

2. Step 2: Validate each option

   query.where('age', '>', 18) matches correct syntax. query.where('age' > 18) misses quotes and arguments. query.where('age', 'greater', 18) uses invalid operator. query.where('age', '>=', '18') compares number to string.

3. Final Answer:

   query.where('age', '>', 18) -> Option A

4. Quick Check:

   where(field, operator, value) correct format [OK]

Hint: Use quotes around operator and field name [OK]

Common Mistakes:

• Omitting quotes around operator
• Using invalid operators like 'greater'
• Comparing number to string

3. Given this Firestore query code:

const query = collection.where('score', '>=', 50).orderBy('score').limit(3);

What will this query return?

medium

A. Top 3 documents with score less than 50

B. 3 documents with the lowest scores 50 or above

C. 3 documents with the highest scores 50 or above

D. All documents with score exactly 50

Solution

1. Step 1: Analyze the where condition

   The query filters documents with score greater than or equal to 50.

2. Step 2: Understand orderBy and limit

   Ordering by score defaults to ascending order, so lowest scores come first. Limit(3) returns first 3 documents in that order.

3. Final Answer:

   3 documents with the lowest scores 50 or above -> Option B

4. Quick Check:

   where >= 50 + orderBy ascending + limit 3 = lowest 3 scores ≥ 50 [OK]

Hint: orderBy defaults ascending unless specified [OK]

Common Mistakes:

• Assuming orderBy sorts descending by default
• Ignoring the where filter
• Thinking limit returns highest scores

4. You wrote this Firestore query:

collection.where('status', '==', 'active').orderBy('createdAt')

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

medium

A. Add a composite index for status and createdAt

B. Remove the orderBy clause

C. Change where to filter

D. Use limit(1) to avoid indexing

Solution

1. Step 1: Understand Firestore indexing rules

   Queries with multiple conditions on different fields require composite indexes.

2. Step 2: Identify the error cause

   The query filters by status and orders by createdAt, needing a composite index.

3. Final Answer:

   Add a composite index for status and createdAt -> Option A

4. Quick Check:

   Composite index needed for where + orderBy [OK]

Hint: Create composite index for multiple fields in query [OK]

Common Mistakes:

• Removing orderBy instead of indexing
• Using invalid method 'filter'
• Thinking limit avoids index errors

5. You want to find users who are either under 18 or have a premium subscription. Which Firestore query approach is correct?

hard

A. Use a single query with where('age', '<', 18).orWhere('subscription', '==', 'premium')

B. Use orderBy on age and subscription fields

C. Use whereIn with both conditions combined

D. Use two separate queries with where and combine results in code

Solution

1. Step 1: Understand Firestore query limitations

   Firestore does not support OR queries directly in a single query.

2. Step 2: Choose correct workaround

   Run two queries separately: one for age < 18, another for subscription == premium, then merge results in code.

3. Final Answer:

   Use two separate queries with where and combine results in code -> Option D

4. Quick Check:

   Firestore lacks OR; combine queries manually [OK]

Hint: Firestore OR queries need multiple queries combined [OK]

Common Mistakes:

• Trying to use non-existent orWhere method
• Using whereIn incorrectly for OR logic
• Assuming orderBy filters data