Ordering results in Firebase - Time & Space Complexity

Time Complexity: Ordering results

O(log n)

Understanding Time Complexity

When we ask Firebase to sort data, it needs to look through the items to arrange them.

We want to know how the time it takes changes as we have more data to sort.

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

const query = firestore.collection('products')
  .orderBy('price')
  .limit(20);

const snapshot = await query.get();

snapshot.forEach(doc => {
  console.log(doc.data());
});
    

This code asks Firebase to get the first 20 products sorted by price.

Identify Repeating Operations

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

• Primary operation: The query to fetch and order documents by the 'price' field.
• How many times: One query call, but internally Firebase scans the relevant index or data to sort.

How Execution Grows With Input

As the number of products grows, Firebase uses an index to quickly find and order items.

Input Size (n)	Approx. Api Calls/Operations
10	1 query using index, fast retrieval
100	1 query using index, still fast
1000	1 query using index, efficient retrieval

Pattern observation: The query time grows slowly because Firebase uses indexes to avoid scanning all data.

Final Time Complexity

Time Complexity: O(log n)

This means as data grows, the time to order results grows slowly, thanks to indexes.

Common Mistake

[X] Wrong: "Ordering results always takes time proportional to the total number of documents."

[OK] Correct: Firebase uses indexes that let it find and order data quickly without scanning everything.

Interview Connect

Understanding how ordering works and how indexes help is a useful skill for working with databases and cloud services.

Self-Check

"What if we remove the index on the 'price' field? How would the time complexity change?"

Practice

1. What does the orderBy method do in Firebase Firestore queries?

easy

A. It deletes documents from the collection.

B. It filters documents based on a condition.

C. It sorts the query results by a specified field.

D. It adds new documents to the collection.

Solution

1. Step 1: Understand the purpose of orderBy

   The orderBy method is used to sort documents in a query result by a specific field.

2. Step 2: Differentiate from other query methods

   Filtering uses where, deleting uses delete, and adding uses add. These are different from sorting.

3. Final Answer:

   It sorts the query results by a specified field. -> Option C

4. Quick Check:

   Ordering = Sorting [OK]

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

Common Mistakes:

• Confusing orderBy with filtering
• Thinking orderBy adds or deletes data
• Assuming orderBy changes data, not just order

2. Which of the following is the correct syntax to order Firestore documents by the field age in descending order?

easy

A. db.collection('users').orderBy('age', 'desc')

B. db.collection('users').orderBy('age', descending)

C. db.collection('users').orderBy('age', 'descending')

D. db.collection('users').orderBy('age', -1)

Solution

1. Step 1: Recall Firestore orderBy syntax

   The correct syntax uses the string 'desc' for descending order, not 'descending' or other variants.

2. Step 2: Check each option

   db.collection('users').orderBy('age', 'desc') uses 'desc' correctly. Options A and B use invalid strings. db.collection('users').orderBy('age', -1) uses a number which is not valid in Firestore.

3. Final Answer:

   db.collection('users').orderBy('age', 'desc') -> Option A

4. Quick Check:

   Descending order = 'desc' string [OK]

Hint: Use 'asc' or 'desc' strings exactly in orderBy [OK]

Common Mistakes:

• Using 'descending' instead of 'desc'
• Using boolean or numbers instead of strings
• Omitting quotes around 'desc'

3. Given this Firestore query:

db.collection('products').orderBy('price', 'asc').limit(3).get()

Which products will be returned?

medium

A. The 3 products with the lowest price.

B. The 3 products with the highest price.

C. All products sorted by price ascending.

D. 3 random products from the collection.

Solution

1. Step 1: Analyze the query order and limit

   The query orders products by price ascending (lowest to highest) and limits results to 3 documents.

2. Step 2: Understand the effect of limit

   Limit(3) returns only the first 3 documents after sorting, so the 3 cheapest products.

3. Final Answer:

   The 3 products with the lowest price. -> Option A

4. Quick Check:

   orderBy ascending + limit 3 = lowest 3 [OK]

Hint: orderBy asc + limit = smallest values first [OK]

Common Mistakes:

• Confusing ascending with descending
• Ignoring the limit clause
• Assuming random order without sorting

4. You wrote this Firestore query:

db.collection('orders').orderBy('date').orderBy('total', 'desc').get()

But it throws an error about missing indexes. What should you do?

medium

A. Use where() instead of orderBy().

B. Create a composite index on 'date' ascending and 'total' descending.

C. Change 'desc' to 'descending' in orderBy.

D. Remove one orderBy to avoid multiple ordering.

Solution

1. Step 1: Understand Firestore composite index requirement

   Ordering by multiple fields requires a composite index matching the order and directions.

2. Step 2: Identify correct index to create

   You must create a composite index on 'date' ascending and 'total' descending to support this query.

3. Final Answer:

   Create a composite index on 'date' ascending and 'total' descending. -> Option B

4. Quick Check:

   Multiple orderBy needs composite index [OK]

Hint: Multiple orderBy? Create matching composite index [OK]

Common Mistakes:

• Ignoring index creation errors
• Using wrong direction strings
• Trying to avoid multiple orderBy instead of indexing

5. You want to get all users ordered by their score descending, but only those who have score greater than 50. Which query is correct?

hard

A. db.collection('users').orderBy('score', 'asc').where('score', '>', 50).get()

B. db.collection('users').orderBy('score').where('score', '>', 50).get()

C. db.collection('users').where('score', '>', 50).orderBy('score').get()

D. db.collection('users').where('score', '>', 50).orderBy('score', 'desc').get()

Solution

1. Step 1: Understand Firestore query rules for inequality filters

   Range filters like '>' require orderBy on the same field as the first ordering field. Use 'desc' for descending order.

2. Step 2: Check each option

   A uses orderBy('score', 'asc'): ascending, not descending.
   B: where('score', '>', 50).orderBy('score', 'desc'): correct for filtered descending order.
   C: orderBy('score') defaults to 'asc'.
   D: orderBy('score') defaults to 'asc'.

3. Final Answer:

   db.collection('users').where('score', '>', 50).orderBy('score', 'desc').get() -> Option D

4. Quick Check:

   Range filter + first orderBy on field + 'desc' [OK]

Hint: Range filters require orderBy on same field and direction [OK]

Common Mistakes:

• Mismatching orderBy direction with where filter
• Omitting orderBy when using range filters
• Using orderBy without specifying direction