KEYS pattern matching (avoid in production) in Redis - Time & Space Complexity

Time Complexity: KEYS pattern matching (avoid in production)

O(n)

Understanding Time Complexity

When using Redis, the KEYS command helps find keys matching a pattern. But it can be slow if many keys exist.

We want to know how the time to run KEYS grows as the number of keys grows.

Scenario Under Consideration

Analyze the time complexity of the following Redis command.

KEYS user:*
    

This command finds all keys starting with "user:" by checking every key in the database.

Identify Repeating Operations

Look for repeated work inside the command.

• Primary operation: Scanning every key in the database to check if it matches the pattern.
• How many times: Once for each key stored in Redis.

How Execution Grows With Input

As the number of keys grows, the work grows too because Redis checks each key one by one.

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

Pattern observation: The time grows directly with the number of keys. Double the keys, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run KEYS grows linearly with the number of keys in the database.

Common Mistake

[X] Wrong: "KEYS is fast even with many keys because Redis is very quick."

[OK] Correct: Redis checks every key one by one, so more keys mean more work and slower response.

Interview Connect

Understanding how commands like KEYS scale helps you write better Redis queries and avoid slowdowns in real projects.

Self-Check

"What if we used SCAN instead of KEYS? How would the time complexity change?"

Practice

1. What does the Redis command KEYS * do?

easy

A. Returns all keys in the current database

B. Deletes all keys in the current database

C. Returns the number of keys in the current database

D. Sets a new key with a wildcard name

Solution

1. Step 1: Understand the KEYS command

   The KEYS command searches for keys matching a given pattern.

2. Step 2: Analyze the pattern *

   The pattern * matches all keys in the current database.

3. Final Answer:

   Returns all keys in the current database -> Option A

4. Quick Check:

   KEYS * lists all keys [OK]

Hint: Remember * matches everything in KEYS command [OK]

Common Mistakes:

• Thinking KEYS deletes keys
• Confusing KEYS with COUNT commands
• Assuming KEYS sets keys

2. Which of the following is the correct unquoted syntax to find keys starting with 'user:' using KEYS?

easy

A. KEYS user:*

B. KEYS user*

C. KEYS 'user:*'

D. KEYS 'user*'

Solution

1. Step 1: Understand pattern syntax in KEYS

   Patterns do not require quotes; wildcards like * match any characters.

2. Step 2: Match keys starting with 'user:'

   The pattern should be user:* without quotes to match keys starting with 'user:'.

3. Final Answer:

   KEYS user:* -> Option A

4. Quick Check:

   Use unquoted patterns with * wildcard [OK]

Hint: Use unquoted patterns with * for KEYS [OK]

Common Mistakes:

• Adding quotes around pattern
• Using colon without wildcard
• Using wrong wildcard placement

3. Given keys: user:1, user:2, admin:1, what is the output of KEYS user:*?

medium

A. ["admin:1"]

B. ["user:1", "user:2", "admin:1"]

C. ["user:1", "user:2"]

D. []

Solution

1. Step 1: Identify keys matching pattern user:*

   Keys starting with 'user:' are user:1 and user:2.

2. Step 2: Exclude keys not matching pattern

   admin:1 does not start with 'user:', so it is excluded.

3. Final Answer:

   ["user:1", "user:2"] -> Option C

4. Quick Check:

   Pattern matches keys starting with 'user:' [OK]

Hint: Match only keys starting with pattern prefix [OK]

Common Mistakes:

• Including keys with different prefixes
• Returning empty list incorrectly
• Confusing pattern syntax

4. What is wrong with this command: KEYS user?*?

medium

A. The question mark is not a valid wildcard in KEYS

B. The pattern should be quoted

C. The command will delete keys instead of listing

D. The pattern matches only keys with exactly one character after 'user' followed by any characters

Solution

1. Step 1: Understand the question mark wildcard in KEYS

   The question mark ? matches exactly one character in Redis patterns.

2. Step 2: Analyze the pattern user?*

   This pattern matches keys starting with 'user', followed by exactly one character, then any characters.

3. Final Answer:

   The pattern matches only keys with exactly one character after 'user' -> Option D

4. Quick Check:

   ? matches exactly one character [OK]

Hint: Remember ? matches exactly one character in KEYS [OK]

Common Mistakes:

• Thinking ? is invalid wildcard
• Assuming pattern deletes keys
• Forgetting ? matches exactly one character

5. You want to find all keys containing the word 'session' anywhere in their name without blocking Redis in production. Which approach is best?

hard

A. Use KEYS *session* command directly

B. Use SCAN 0 MATCH *session* iteratively

C. Use GET *session* command

D. Use DEL *session* to remove keys first

Solution

1. Step 1: Understand why KEYS is discouraged in production

   KEYS blocks Redis and can cause performance issues on large datasets.

2. Step 2: Use SCAN with MATCH for safe iteration

   SCAN iterates keys incrementally without blocking, using MATCH *session* to filter keys containing 'session'.

3. Final Answer:

   Use SCAN 0 MATCH *session* iteratively -> Option B

4. Quick Check:

   SCAN is safe for production key matching [OK]

Hint: Use SCAN with MATCH to avoid blocking Redis [OK]

Common Mistakes:

• Using KEYS in production causing blocking
• Using GET with wildcards (invalid)
• Deleting keys without checking