In and not-in queries in Firebase - Time & Space Complexity

Time Complexity: In and not-in queries

O(n)

Understanding Time Complexity

When using Firebase queries with "in" or "not-in" filters, it's important to know how the number of items you check affects the work done.

We want to understand how the query cost grows as we add more values to these filters.

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

const query = firestore.collection('products')
  .where('category', 'in', ['electronics', 'books', 'clothing']);
const snapshot = await query.get();

This code fetches all products whose category is one of the listed values using an "in" query.

Identify Repeating Operations

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

• Primary operation: One query to Firestore with an "in" filter containing multiple values.
• How many times: The query internally performs multiple lookups, one for each value in the "in" list.

How Execution Grows With Input

Each additional value in the "in" list causes Firestore to perform an extra lookup to find matching documents.

Input Size (n)	Approx. API Calls/Operations
3	3 lookups (one per category value)
5	5 lookups
10	10 lookups

Pattern observation: The number of internal lookups grows directly with the number of values in the "in" list.

Final Time Complexity

Time Complexity: O(n)

This means the work done grows linearly with the number of values you include in the "in" or "not-in" query.

Common Mistake

[X] Wrong: "Adding more values to the 'in' list does not affect query cost because it's a single query call."

[OK] Correct: Even though it looks like one query, Firestore performs separate lookups internally for each value, so cost grows with the list size.

Interview Connect

Understanding how query filters affect performance helps you design efficient data fetching in real projects and shows you think about cost and speed.

Self-Check

"What if we replaced the 'in' query with multiple separate queries, one per value? How would the time complexity change?"

Practice

1.

What does the in query do in Firebase Firestore?

easy

A. Finds documents where a field is null

B. Finds documents where a field does not exist

C. Finds documents where a field matches exactly one value only

D. Finds documents where a field matches any value in a given list

Solution

1. Step 1: Understand the purpose of in query

   The in query checks if a field's value matches any value from a list of values.

2. Step 2: Compare with other options

   Null fields and non-existent fields describe different query types, while limiting to exactly one value is incorrect for in.

3. Final Answer:

   Finds documents where a field matches any value in a given list -> Option D

4. Quick Check:

   in query = matches any value in list [OK]

Hint: Remember: 'in' means match any value from a list [OK]

Common Mistakes:

• Confusing 'in' with 'not-in' query
• Thinking 'in' matches only one value
• Assuming 'in' checks for field existence

2.

Which of the following is the correct syntax for a not-in query in Firestore?

db.collection('users').where('age', ___, [18, 21, 25])

easy

A. 'notin'

B. 'not-in'

C. 'not_in'

D. 'nin'

Solution

1. Step 1: Recall Firestore query operators

   Firestore uses exact strings for operators; the correct operator for excluding values is 'not-in'.

2. Step 2: Check each option's validity

   'notin', 'not_in', and 'nin' are invalid syntax and will cause errors.

3. Final Answer:

   'not-in' -> Option B

4. Quick Check:

   Correct operator syntax = 'not-in' [OK]

Hint: Use exact operator strings: 'not-in' with hyphen [OK]

Common Mistakes:

• Using 'notin' or 'not_in' instead of 'not-in'
• Missing quotes around operator
• Using unsupported operators like 'nin'

3.

Given this Firestore query:

db.collection('products').where('category', 'in', ['books', 'games']).get()

Which documents will be returned?

medium

A. Documents where category is either 'books' or 'games'

B. Documents where category is not 'books' or 'games'

C. Documents where category is exactly 'booksgames'

D. All documents regardless of category

Solution

1. Step 1: Understand the 'in' query behavior

   The query filters documents where the 'category' field matches any value in the list ['books', 'games'].

2. Step 2: Analyze each option

   Documents where category is either 'books' or 'games' matches the query logic. Documents where category is not 'books' or 'games' is the opposite. Documents where category is exactly 'booksgames' is a concatenation, which is incorrect. All documents regardless of category ignores the filter.

3. Final Answer:

   Documents where category is either 'books' or 'games' -> Option A

4. Quick Check:

   'in' query returns matching values in list [OK]

Hint: Think: 'in' means any value inside the list [OK]

Common Mistakes:

• Confusing 'in' with 'not-in'
• Assuming concatenation of list values
• Ignoring the filter and expecting all documents

4.

What is wrong with this Firestore query?

db.collection('orders').where('status', 'not-in', ['shipped', 'delivered', 'pending', 'cancelled', 'new', 'processing', 'confirmed', 'refunded', 'returned', 'failed', 'on_hold']).get()

It throws an error. Why?

medium

A. The 'not-in' operator cannot be used with more than 10 values in the list

B. The field 'status' does not exist in the collection

C. The 'not-in' operator is not supported in Firestore

D. The list has more than 20 values, exceeding Firestore limits

Solution

1. Step 1: Recall Firestore limits on 'not-in' queries

   Firestore limits 'not-in' and 'in' queries to a maximum of 10 values in the list.

2. Step 2: Count values in the list

   The list has 11 values, exceeding the 10-value limit for 'not-in' queries.

3. Step 3: Consider other options

   The list has more than 20 values, exceeding Firestore limits is incorrect because the list has 11 values. The 'not-in' operator is not supported in Firestore is wrong because 'not-in' is supported. The field 'status' does not exist in the collection is unrelated to the error.

4. Final Answer:

   The 'not-in' operator cannot be used with more than 10 values in the list -> Option A

5. Quick Check:

   'not-in' max 10 values limit causes errors [OK]

Hint: Check list size: 'not-in' max 10 values allowed [OK]

Common Mistakes:

• Assuming 'not-in' supports unlimited list size
• Blaming field existence without checking
• Confusing 'not-in' support in Firestore

5.

You want to find all users whose role is neither 'admin' nor 'moderator' nor 'guest'. Which Firestore query is correct?

hard

A. db.collection('users').where('role', '!=', ['admin', 'moderator', 'guest']).get()

B. db.collection('users').where('role', 'in', ['admin', 'moderator', 'guest']).get()

C. db.collection('users').where('role', 'not-in', ['admin', 'moderator', 'guest']).get()

D. db.collection('users').where('role', 'not-in', 'admin,moderator,guest').get()

Solution

1. Step 1: Understand the requirement

   You want users whose role is NOT any of the listed roles. This means excluding those roles.

2. Step 2: Choose the correct operator and syntax

   The 'not-in' operator excludes documents with any value in the list. db.collection('users').where('role', 'not-in', ['admin', 'moderator', 'guest']).get() uses correct syntax with a list. db.collection('users').where('role', 'in', ['admin', 'moderator', 'guest']).get() includes only those roles, which is opposite. db.collection('users').where('role', '!=', ['admin', 'moderator', 'guest']).get() uses '!=' which does not accept lists. db.collection('users').where('role', 'not-in', 'admin,moderator,guest').get() uses a string instead of a list, which is invalid.

3. Final Answer:

   db.collection('users').where('role', 'not-in', ['admin', 'moderator', 'guest']).get() -> Option C

4. Quick Check:

   Use 'not-in' with list to exclude multiple values [OK]

Hint: Use 'not-in' with array to exclude multiple values [OK]

Common Mistakes:

• Using '!=' with a list instead of a single value
• Passing a string instead of an array for 'not-in'
• Using 'in' instead of 'not-in' for exclusion