Composite index requirements in Firebase - Time & Space Complexity

Time Complexity: Composite index requirements

O(k)

Understanding Time Complexity

When using composite indexes in Firebase, it is important to understand how the number of fields in the index affects query speed.

We want to know how query time changes as we add more fields to the composite index.

Scenario Under Consideration

Analyze the time complexity of this Firebase query using a composite index.

const query = firestore.collection('orders')
  .where('status', '==', 'shipped')
  .where('customerId', '==', '12345')
  .orderBy('orderDate', 'desc')
  .limit(20);

const snapshot = await query.get();

This code queries orders filtered by status and customerId, ordered by orderDate, using a composite index.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Searching the composite index entries matching the filters.
• How many times: The database scans entries matching the combined fields in the index.

How Execution Grows With Input

The query uses the composite index to quickly find matching entries.

Input Size (k)	Approx. Operations
10	About 10 or fewer index lookups
100	About 100 or fewer index lookups
1000	About 1000 or fewer index lookups

Pattern observation: The number of operations grows roughly in proportion to the number of matching entries, not the total data size.

Final Time Complexity

Time Complexity: O(k)

This means the query time grows linearly with the number of matching entries k, thanks to the composite index.

Common Mistake

[X] Wrong: "Adding more fields to the composite index always makes queries slower."

[OK] Correct: Composite indexes help narrow down results faster, so adding relevant fields can make queries faster, not slower.

Interview Connect

Understanding how composite indexes affect query speed shows you know how databases handle filtering and sorting efficiently.

Self-Check

"What if we removed the composite index and only had single-field indexes? How would the time complexity change?"

Practice

1. What is the main reason Firebase requires a composite index?

easy

A. To encrypt data for security

B. To store data in multiple locations

C. To backup data automatically

D. To efficiently query data using multiple fields together

Solution

1. Step 1: Understand composite index purpose

   Composite indexes allow Firebase to quickly search using more than one field at the same time.

2. Step 2: Compare options to purpose

   Only To efficiently query data using multiple fields together matches this purpose; others describe unrelated features.

3. Final Answer:

   To efficiently query data using multiple fields together -> Option D

4. Quick Check:

   Composite index = multi-field query speed [OK]

Hint: Composite indexes speed up queries with multiple fields [OK]

Common Mistakes:

• Confusing composite indexes with data backup
• Thinking composite indexes encrypt data
• Believing composite indexes store data in multiple places

2. Which of the following is the correct way to define a composite index in Firebase JSON?

easy

A. "indexes": [{"collectionGroup": "users", "queryScope": "COLLECTION", "fields": [{"fieldPath": "age", "order": "ASCENDING"}, {"fieldPath": "name", "order": "DESCENDING"}]}]

B. "indexes": [{"collection": "users", "fields": ["age", "name"]}]

C. "indexes": [{"collectionGroup": "users", "fields": [{"fieldPath": "age"}, {"fieldPath": "name"}]}]

D. "indexes": [{"collectionGroup": "users", "queryScope": "COLLECTION", "fields": ["age", "name"]}]

Solution

1. Step 1: Check JSON structure for composite index

   Correct composite index JSON includes collectionGroup, queryScope, and fields with fieldPath and order.

2. Step 2: Validate each option

   Only "indexes": [{"collectionGroup": "users", "queryScope": "COLLECTION", "fields": [{"fieldPath": "age", "order": "ASCENDING"}, {"fieldPath": "name", "order": "DESCENDING"}]}] has all required keys and correct field definitions with order specified.

3. Final Answer:

   "indexes": [{"collectionGroup": "users", "queryScope": "COLLECTION", "fields": [{"fieldPath": "age", "order": "ASCENDING"}, {"fieldPath": "name", "order": "DESCENDING"}]}] -> Option A

4. Quick Check:

   Composite index JSON needs fields with order [OK]

Hint: Composite index JSON needs fields with order and collectionGroup [OK]

Common Mistakes:

• Omitting order in fields
• Using 'collection' instead of 'collectionGroup'
• Listing fields as simple strings without objects

3. Given this query in Firebase: db.collection('products').where('category', '==', 'books').orderBy('price', 'asc').orderBy('rating', 'desc'), what composite index is required?

medium

A. Index on fields: category (DESC), price (ASC), rating (ASC)

B. Index on fields: price (ASC), rating (DESC)

C. Index on fields: category (ASC), price (ASC), rating (DESC)

D. No composite index needed

Solution

1. Step 1: Identify query filters and orderBy fields

   The query filters on 'category' and orders by 'price' ascending and 'rating' descending.

2. Step 2: Determine composite index fields and order

   Composite index must include 'category' (filter), then 'price' (asc), then 'rating' (desc) in that order.

3. Final Answer:

   Index on fields: category (ASC), price (ASC), rating (DESC) -> Option C

4. Quick Check:

   Filter + orderBy fields = composite index fields [OK]

Hint: Include all filter and orderBy fields with correct order [OK]

Common Mistakes:

• Ignoring filter field in index
• Wrong order or direction of fields
• Assuming no index needed for multiple orderBy

4. You get an error saying a composite index is missing for this query: db.collection('orders').where('status', '==', 'shipped').orderBy('date', 'desc'). Which fix is correct?

medium

A. Create a composite index on fields: status (ASC), date (DESC)

B. Create a composite index on fields: date (DESC), status (ASC)

C. Create a single-field index on date only

D. No index needed; fix query syntax

Solution

1. Step 1: Analyze query filter and orderBy

   The query filters on 'status' and orders by 'date' descending.

2. Step 2: Determine correct composite index order

   Composite index must start with filter field 'status' (ASC by default), then 'date' (DESC) as orderBy.

3. Final Answer:

   Create a composite index on fields: status (ASC), date (DESC) -> Option A

4. Quick Check:

   Filter field first, then orderBy fields in index [OK]

Hint: Filter field first in index, then orderBy fields [OK]

Common Mistakes:

• Reversing field order in index
• Creating single-field index only
• Ignoring error and changing query syntax

5. You want to query a collection 'events' filtering by 'location' and 'type', and sorting by 'date' ascending. Which composite index definition is correct?

hard

A. Index on fields: date (ASC), location (ASC), type (ASC)

B. Index on fields: location (ASC), type (ASC), date (ASC)

C. Index on fields: location (DESC), type (DESC), date (ASC)

D. No composite index needed if only filtering

Solution

1. Step 1: Identify query filter and sort fields

   The query filters on 'location' and 'type', and sorts by 'date' ascending.

2. Step 2: Determine composite index order

   Composite index must list filter fields first in any order, then the sort field last with ascending order.

3. Step 3: Validate options

   Index on fields: location (ASC), type (ASC), date (ASC) matches filter fields first (location, type) then date ascending. Index on fields: date (ASC), location (ASC), type (ASC) starts with date, which is incorrect. Index on fields: location (DESC), type (DESC), date (ASC) uses descending for filters, which is wrong. No composite index needed if only filtering is incorrect because sorting requires composite index.

4. Final Answer:

   Index on fields: location (ASC), type (ASC), date (ASC) -> Option B

5. Quick Check:

   Filters first, then sort field in index [OK]

Hint: Filter fields first, then sort field ascending in index [OK]

Common Mistakes:

• Placing sort field before filters in index
• Using descending order for filter fields
• Assuming no index needed when sorting