Common rule patterns in Firebase - Time & Space Complexity

Time Complexity: Common rule patterns

O(n)

Understanding Time Complexity

When using Firebase security rules, it's important to know how the number of checks grows as your data or requests grow.

We want to understand how the time to evaluate rules changes when more data or requests are involved.

Scenario Under Consideration

Analyze the time complexity of these Firebase rules checking multiple documents.

service cloud.firestore {
  match /databases/{database}/documents {
    match /posts/{postId} {
      allow read: if request.auth != null &&
        exists(/databases/$(database)/documents/users/$(request.auth.uid)) &&
        get(/databases/$(database)/documents/posts/$(postId)).data.published == true;
    }
  }
}
    

These rules check if the user exists and if the post is published before allowing read access.

Identify Repeating Operations

Look at what happens each time a read request is made:

• Primary operation: Two document reads: one to check the user document, one to check the post document.
• How many times: Once per read request for each post.

How Execution Grows With Input

As the number of read requests grows, the number of document reads grows the same way.

Input Size (n)	Approx. Api Calls/Operations
10	20 document reads (2 per request)
100	200 document reads
1000	2000 document reads

Pattern observation: The number of operations grows directly with the number of requests.

Final Time Complexity

Time Complexity: O(n)

This means the time to check rules grows linearly with the number of read requests.

Common Mistake

[X] Wrong: "Checking multiple documents in rules happens all at once and does not add time."

[OK] Correct: Each document read in rules is a separate operation, so more checks mean more time.

Interview Connect

Understanding how rule checks scale helps you design efficient security rules that keep your app fast and safe.

Self-Check

What if we added a loop in rules to check multiple related documents? How would the time complexity change?