Range queries for scoring in Redis - Time & Space Complexity

Time Complexity: Range queries for scoring

O(log n + m)

Understanding Time Complexity

When we ask Redis to find items within a score range, we want to know how the time it takes grows as more items are stored.

We are trying to see how the cost changes when the number of scored items increases.

Scenario Under Consideration

Analyze the time complexity of the following Redis commands.

ZADD leaderboard 100 user1
ZADD leaderboard 200 user2
ZADD leaderboard 300 user3

ZRANGEBYSCORE leaderboard 150 350
    

This code adds users with scores to a sorted set and then queries users with scores between 150 and 350.

Identify Repeating Operations

Look for repeated work inside the query.

• Primary operation: Redis scans the sorted set to find members with scores in the given range.
• How many times: It depends on how many items fall inside the score range.

How Execution Grows With Input

As the total number of items grows, the time to find items in a score range grows mostly with how many items match the range.

Input Size (n)	Approx. Operations
10	About number of items in range (e.g., 3)
100	About number of items in range (e.g., 20)
1000	About number of items in range (e.g., 150)

Pattern observation: The work grows with how many items are returned, not the total stored.

Final Time Complexity

Time Complexity: O(log n + m)

This means Redis quickly finds the start point with a small cost, then spends time proportional to how many items match the score range.

Common Mistake

[X] Wrong: "The query time grows only with the total number of items stored."

[OK] Correct: Redis uses a fast search to jump to the start of the range, so the main cost depends on how many items are in the range, not all items.

Interview Connect

Understanding how range queries scale helps you explain how databases handle large data efficiently, a useful skill in many real-world projects.

Self-Check

"What if we asked for a range that includes almost all items? How would the time complexity change?"

Practice

1. What does the Redis command ZRANGEBYSCORE do?

easy

A. It returns members in a sorted set within a specified score range.

B. It deletes members from a sorted set based on score.

C. It adds new members to a sorted set with scores.

D. It returns the total number of members in a sorted set.

Solution

1. Step 1: Understand the command purpose

   ZRANGEBYSCORE is used to get members from a sorted set filtered by score range.

2. Step 2: Compare options with command behavior

   Only "It returns members in a sorted set within a specified score range." correctly describes returning members within a score range.

3. Final Answer:

   It returns members in a sorted set within a specified score range. -> Option A

4. Quick Check:

   ZRANGEBYSCORE = returns members by score range [OK]

Hint: ZRANGEBYSCORE fetches members filtered by score range [OK]

Common Mistakes:

• Confusing ZRANGEBYSCORE with commands that add or delete members
• Thinking it returns count instead of members
• Assuming it sorts members by name instead of score

2. Which of the following is the correct syntax to get members with scores between 10 and 20 from a sorted set named myzset?

easy

A. ZRANGEBYSCORE myzset [10 [20

B. ZRANGEBYSCORE myzset (10 (20

C. ZRANGEBYSCORE myzset 10 20

D. ZRANGEBYSCORE myzset "10" "20"

Solution

1. Step 1: Recall basic syntax of ZRANGEBYSCORE

   The command format is ZRANGEBYSCORE key min max where min and max are numbers or special strings.

2. Step 2: Analyze options for correct syntax

   ZRANGEBYSCORE myzset 10 20 uses plain numbers 10 and 20 correctly. Options A and B use parentheses or brackets which mean exclusive or inclusive but are not needed here. ZRANGEBYSCORE myzset "10" "20" uses quotes which are unnecessary.

3. Final Answer:

   ZRANGEBYSCORE myzset 10 20 -> Option C

4. Quick Check:

   Syntax = ZRANGEBYSCORE key min max [OK]

Hint: Use plain numbers for inclusive score range in ZRANGEBYSCORE [OK]

Common Mistakes:

• Using parentheses or brackets incorrectly for inclusive ranges
• Adding quotes around numeric scores
• Mixing up min and max order

3. Given the sorted set myzset with members and scores: {"a":5, "b":10, "c":15, "d":20}, what is the result of ZRANGEBYSCORE myzset 10 20 WITHSCORES?

medium

A. ["b", "10", "c", "15", "d", "20"]

B. ["a", "5", "b", "10", "c", "15"]

C. ["c", "15", "d", "20"]

D. ["a", "5", "d", "20"]

Solution

1. Step 1: Identify members with scores between 10 and 20 inclusive

   Members with scores 10, 15, and 20 are "b", "c", and "d" respectively.

2. Step 2: Understand WITHSCORES option output

   WITHSCORES returns members and their scores as alternating elements in the list.

3. Final Answer:

   ["b", "10", "c", "15", "d", "20"] -> Option A

4. Quick Check:

   Members with scores 10-20 + WITHSCORES = ["b", "10", "c", "15", "d", "20"] [OK]

Hint: WITHSCORES returns member-score pairs in order [OK]

Common Mistakes:

• Including members outside the score range
• Returning only members without scores
• Mixing order of members and scores

4. What is wrong with this command to get members with scores between 5 and 15 from myzset?

ZRANGEBYSCORE myzset 5 15 WITHSCORE

medium

A. The score range should be reversed as 15 5.

B. The option should be WITHSCORES, not WITHSCORE.

C. The command needs a LIMIT clause to work.

D. The key name must be quoted.

Solution

1. Step 1: Check the option spelling

   The correct option to include scores is WITHSCORES (plural), not WITHSCORE.

2. Step 2: Verify other parts of the command

   The score range 5 to 15 is correct, LIMIT is optional, and key names do not require quotes.

3. Final Answer:

   The option should be WITHSCORES, not WITHSCORE. -> Option B

4. Quick Check:

   Correct option spelling = WITHSCORES [OK]

Hint: Use WITHSCORES (plural) to get scores with members [OK]

Common Mistakes:

• Misspelling WITHSCORES option
• Reversing min and max scores
• Adding unnecessary quotes around key

5. You have a sorted set players with player names and their scores. You want to find all players with scores greater than 50 but less than or equal to 100, including their scores. Which command correctly achieves this?

hard

A. ZRANGEBYSCORE players [50 100 WITHSCORES

B. ZRANGEBYSCORE players 50 100 WITHSCORES

C. ZRANGEBYSCORE players (50 (100 WITHSCORES

D. ZRANGEBYSCORE players (50 100 WITHSCORES

Solution

1. Step 1: Understand score range requirements

   Scores must be greater than 50 (exclusive) and less than or equal to 100 (inclusive).

2. Step 2: Use parentheses for exclusive and plain number for inclusive

   In Redis, (50 means greater than 50 (exclusive), and 100 means less than or equal to 100 (inclusive).

3. Step 3: Check command syntax

   ZRANGEBYSCORE players (50 100 WITHSCORES correctly uses (50 and 100 with WITHSCORES option.

4. Final Answer:

   ZRANGEBYSCORE players (50 100 WITHSCORES -> Option D

5. Quick Check:

   Exclusive lower bound uses (number) syntax [OK]

Hint: Use (number for exclusive, number for inclusive in range [OK]

Common Mistakes:

• Using brackets [] which Redis does not support for range
• Not using parentheses for exclusive bounds
• Confusing inclusive and exclusive range syntax