Subscription filtering in GraphQL - Time & Space Complexity

Time Complexity: Subscription filtering

O(n)

Understanding Time Complexity

When using subscription filtering in GraphQL, we want to know how the work grows as more data or filters are involved.

We ask: How does filtering affect the time it takes to send updates?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

subscription onNewMessage($channelId: ID!) {
  messageAdded(channelId: $channelId) {
    id
    content
    author
  }
}
    

This subscription listens for new messages but only sends updates for a specific channel using a filter.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each new message against the filter condition (channelId match).
• How many times: Once per new message event received by the server.

How Execution Grows With Input

As more messages arrive, the server checks each one to see if it matches the filter before sending updates.

Input Size (n)	Approx. Operations
10	10 filter checks
100	100 filter checks
1000	1000 filter checks

Pattern observation: The number of checks grows directly with the number of new messages.

Final Time Complexity

Time Complexity: O(n)

This means the time to filter messages grows linearly with the number of new messages received.

Common Mistake

[X] Wrong: "Filtering subscriptions happens instantly regardless of message volume."

[OK] Correct: Each new message must be checked against the filter, so more messages mean more work.

Interview Connect

Understanding how filtering affects subscription performance shows you can think about real-time data efficiently.

Self-Check

"What if we added multiple filters instead of one? How would the time complexity change?"