PSUBSCRIBE for pattern matching in Redis - Time & Space Complexity

Time Complexity: PSUBSCRIBE for pattern matching

O(p)

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?

Practice

1. What does the Redis command PSUBSCRIBE do?

easy

A. It subscribes to channels matching a pattern with wildcards.

B. It unsubscribes from all channels.

C. It publishes messages to a channel.

D. It deletes keys matching a pattern.

Solution

1. Step 1: Understand the purpose of PSUBSCRIBE

   PSUBSCRIBE listens to messages from channels that match a given pattern, using wildcards like '*'.

2. Step 2: Compare with other commands

   Unlike PUBLISH or UNSUBSCRIBE, PSUBSCRIBE focuses on pattern-based subscription.

3. Final Answer:

   It subscribes to channels matching a pattern with wildcards. -> Option A

4. Quick Check:

   PSUBSCRIBE = pattern subscription [OK]

Hint: PSUBSCRIBE listens to patterns, not single channels [OK]

Common Mistakes:

• Confusing PSUBSCRIBE with PUBLISH
• Thinking PSUBSCRIBE deletes keys
• Mixing PSUBSCRIBE with UNSUBSCRIBE

2. Which of the following is the correct syntax to subscribe to all channels starting with 'news.' using PSUBSCRIBE?

easy

A. PSUBSCRIBE news?

B. PSUBSCRIBE news.*

C. PSUBSCRIBE news#

D. PSUBSCRIBE news+

Solution

1. Step 1: Identify the wildcard for pattern matching

   In Redis PSUBSCRIBE, '*' matches any sequence of characters.

2. Step 2: Match the pattern for channels starting with 'news.'

   The pattern 'news.*' matches all channels beginning with 'news.' followed by anything.

3. Final Answer:

   PSUBSCRIBE news.* -> Option B

4. Quick Check:

   '*' wildcard = correct syntax [OK]

Hint: Use '*' to match any characters in PSUBSCRIBE patterns [OK]

Common Mistakes:

• Using '?' which matches exactly one character
• Using '#' or '+' which are not Redis wildcards
• Missing the dot after 'news'

3. Given the following Redis commands executed in order:

PSUBSCRIBE sports.*
PUBLISH sports.football "Goal!"
PUBLISH sports.basketball "Score!"
PUBLISH news.weather "Rain"

Which messages will the subscriber receive?

medium

A. "Goal!" and "Score!"

B. "Goal!" only

C. "Rain" only

D. All three messages

Solution

1. Step 1: Understand the subscription pattern

   The subscriber listens to channels matching 'sports.*', meaning any channel starting with 'sports.'.

2. Step 2: Check published messages against the pattern

   Messages on 'sports.football' and 'sports.basketball' match the pattern; 'news.weather' does not.

3. Final Answer:

   "Goal!" and "Score!" -> Option A

4. Quick Check:

   Pattern matches sports.* channels only [OK]

Hint: Only messages on matching channels are received [OK]

Common Mistakes:

• Assuming all published messages are received
• Confusing exact channel with pattern
• Ignoring the pattern prefix

4. You run the command PSUBSCRIBE sports.* but receive no messages when publishing to sports.football. What is the most likely mistake?

medium

A. You published messages before subscribing.

B. You used SUBSCRIBE instead of PSUBSCRIBE.

C. You subscribed to sports.* but published to sportsfootball without a dot.

D. You used the wrong Redis server version.

Solution

1. Step 1: Check the channel names for exact pattern match

   The pattern 'sports.*' matches channels starting with 'sports.' including the dot.

2. Step 2: Identify mismatch in published channel

   Publishing to 'sportsfootball' (no dot) does not match 'sports.*' pattern.

3. Final Answer:

   You subscribed to sports.* but published to sportsfootball without a dot. -> Option C

4. Quick Check:

   Pattern requires exact prefix including dot [OK]

Hint: Check exact channel names match pattern including dots [OK]

Common Mistakes:

• Confusing SUBSCRIBE with PSUBSCRIBE
• Ignoring dot in channel names
• Assuming order of commands affects delivery

5. You want to listen to all channels that contain the word 'chat' anywhere in their name using PSUBSCRIBE. Which pattern should you use?

hard

A. chat

B. chat*

C. *chat

D. *chat*

Solution

1. Step 1: Understand the wildcard '*' usage

   '*' matches any sequence of characters, including none.

2. Step 2: Create pattern to match 'chat' anywhere

   Using '*chat*' matches any channel with 'chat' anywhere in its name.

3. Final Answer:

   *chat* -> Option D

4. Quick Check:

   Use '*' before and after 'chat' to match anywhere [OK]

Hint: Use '*' before and after word to match anywhere [OK]

Common Mistakes:

• Using 'chat' alone matches exact channel only
• Using 'chat*' matches only channels starting with 'chat'
• Using '*chat' matches only channels ending with 'chat'