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