Time Complexity: PSUBSCRIBE for pattern matching
O(p)
0
0
PSUBSCRIBE for pattern matching in Redis - Time & Space Complexity
Understanding Time Complexity
When using PSUBSCRIBE in Redis, we want to understand how the time to process messages changes as more patterns or messages are involved.
We ask: How does Redis handle matching messages to patterns as the workload grows?
Scenario Under Consideration
Analyze the time complexity of this Redis PSUBSCRIBE usage.
# Subscribe to channels matching patterns
PSUBSCRIBE news.* sports.* weather.*
# When a message is published to a channel
PUBLISH news.local "Breaking news!"
PUBLISH sports.football "Goal scored!"
This code subscribes to multiple channel patterns and receives messages published to matching channels.
Identify Repeating Operations
Look at what repeats when messages arrive.
- Primary operation: Matching each published message's channel name against all subscribed patterns.
- How many times: For each message, Redis checks all patterns to find matches.
How Execution Grows With Input
As the number of patterns grows, Redis must check more patterns for each message.
| Input Size (number of patterns) | Approx. Operations per message |
|---|---|
| 10 | 10 pattern checks |
| 100 | 100 pattern checks |
| 1000 | 1000 pattern checks |
Pattern observation: The work grows directly with the number of patterns; doubling patterns doubles checks.
Final Time Complexity
Time Complexity: O(p)
This means the time to process each message grows linearly with the number of subscribed patterns.
Common Mistake
[X] Wrong: "Matching a message to patterns is instant no matter how many patterns there are."
[OK] Correct: Redis must check each pattern to see if it matches, so more patterns mean more work and longer processing time.
Interview Connect
Understanding how pattern matching scales helps you explain performance trade-offs in real systems using Redis Pub/Sub.
Self-Check
What if Redis used a more advanced data structure to index patterns? How might that change the time complexity?