XRANGE and XREVRANGE in Redis - Time & Space Complexity

Time Complexity: XRANGE and XREVRANGE

O(n)

Understanding Time Complexity

When working with Redis streams, it's important to know how the time to get data grows as the stream gets bigger.

We want to understand how fast XRANGE and XREVRANGE commands run when we ask for entries.

Scenario Under Consideration

Analyze the time complexity of the following Redis commands.

# Get entries from a stream in forward order
XRANGE mystream - + COUNT 100

# Get entries from a stream in reverse order
XREVRANGE mystream + - COUNT 100
    

These commands fetch up to 100 entries from the stream named 'mystream', either from oldest to newest or newest to oldest.

Identify Repeating Operations

Look at what repeats when these commands run.

• Primary operation: Scanning entries in the stream to find requested range.
• How many times: Up to the number of entries requested (COUNT), or until the range ends.

How Execution Grows With Input

As you ask for more entries, the work grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 10 steps to get entries
100	About 100 steps
1000	About 1000 steps

Pattern observation: The time grows linearly with the number of entries requested.

Final Time Complexity

Time Complexity: O(n)

This means the time to get entries grows directly with how many entries you ask for.

Common Mistake

[X] Wrong: "XRANGE and XREVRANGE always take the same time no matter how many entries are requested."

[OK] Correct: The commands scan through entries to return results, so asking for more entries takes more time.

Interview Connect

Understanding how XRANGE and XREVRANGE scale helps you explain how to efficiently read data from streams in real projects.

Self-Check

"What if we remove the COUNT option and request the entire stream? How would the time complexity change?"

Practice

1. What does the Redis command XRANGE do when used on a stream?

easy

A. Adds new entries to the stream.

B. Reads stream entries from newest to oldest within a specified range.

C. Deletes entries from the stream within a specified range.

D. Reads stream entries from oldest to newest within a specified range.

Solution

1. Step 1: Understand XRANGE purpose

   XRANGE is used to read entries from a Redis stream in order from the oldest to the newest.

2. Step 2: Compare with other commands

   XREVRANGE reads in reverse order, and other commands like XADD add entries, so XRANGE is for reading oldest to newest.

3. Final Answer:

   Reads stream entries from oldest to newest within a specified range. -> Option D

4. Quick Check:

   XRANGE = oldest to newest read [OK]

Hint: XRANGE always reads forward (oldest to newest) [OK]

Common Mistakes:

• Confusing XRANGE with XREVRANGE order
• Thinking XRANGE adds or deletes entries
• Assuming XRANGE reads newest first

2. Which of the following is the correct syntax to read the last 5 entries from a Redis stream using XREVRANGE?

easy

A. XRANGE mystream + - COUNT 5

B. XREVRANGE mystream + - COUNT 5

C. XREVRANGE mystream - + COUNT 5

D. XREVRANGE mystream 0 - COUNT 5

Solution

1. Step 1: Understand XREVRANGE syntax

   XREVRANGE reads from the newest entry (+) to the oldest (-). To get last 5 entries, use range '+' to '-' with COUNT 5.

2. Step 2: Check options

   XREVRANGE mystream + - COUNT 5 uses correct order '+' to '-' and COUNT 5. XREVRANGE mystream - + COUNT 5 reverses range, XRANGE mystream + - COUNT 5 uses XRANGE, and XREVRANGE mystream 0 - COUNT 5 uses invalid start ID.

3. Final Answer:

   XREVRANGE mystream + - COUNT 5 -> Option B

4. Quick Check:

   XREVRANGE newest to oldest with COUNT [OK]

Hint: XREVRANGE uses '+' then '-' for newest to oldest [OK]

Common Mistakes:

• Swapping '+' and '-' in range
• Using XRANGE instead of XREVRANGE
• Incorrect start or end IDs

3. Given a Redis stream mystream with entries:
1609459200000-0: {"name":"Alice"}
1609459260000-0: {"name":"Bob"}
1609459320000-0: {"name":"Carol"}
What will be the result of XRANGE mystream 1609459200000-0 1609459260000-0?

medium

A. [["1609459320000-0", {"name":"Carol"}]]

B. [["1609459260000-0", {"name":"Bob"}], ["1609459200000-0", {"name":"Alice"}]]

C. [["1609459200000-0", {"name":"Alice"}], ["1609459260000-0", {"name":"Bob"}]]

D. Empty list

Solution

1. Step 1: Understand XRANGE with ID range

   XRANGE returns entries from start ID to end ID in order from oldest to newest.

2. Step 2: Identify matching entries

   Entries with IDs 1609459200000-0 and 1609459260000-0 fall within the range, so both are returned in order.

3. Final Answer:

   [["1609459200000-0", {"name":"Alice"}], ["1609459260000-0", {"name":"Bob"}]] -> Option C

4. Quick Check:

   XRANGE returns oldest to newest in range [OK]

Hint: XRANGE returns entries in ascending ID order [OK]

Common Mistakes:

• Expecting reverse order output
• Including entries outside the range
• Confusing XRANGE with XREVRANGE

4. You run the command XREVRANGE mystream - + COUNT 3 on a stream with more than 3 entries but get an empty list. What is the likely cause?

medium

A. The range start and end IDs are reversed; XREVRANGE expects '+' then '-'.

B. COUNT cannot be used with XREVRANGE.

C. The stream key 'mystream' does not exist.

D. XREVRANGE requires numeric IDs only.

Solution

1. Step 1: Check XREVRANGE range order

   XREVRANGE reads from newest to oldest, so the start ID must be '+' and end ID '-'. Using '-' then '+' reverses the order and results in an empty list.

2. Step 2: Verify other options

   COUNT is valid with XREVRANGE, a missing key returns empty list (but stream exists with >3 entries), and special IDs like -/+ are valid.

3. Final Answer:

   The range start and end IDs are reversed; XREVRANGE expects '+' then '-'. -> Option A

4. Quick Check:

   XREVRANGE range must be '+' to '-' [OK]

Hint: XREVRANGE range must start with '+' and end with '-' [OK]

Common Mistakes:

• Swapping start and end IDs in XREVRANGE
• Assuming COUNT is invalid
• Confusing the empty result with missing key

5. You want to retrieve the 3 newest entries from a stream mystream but only those with IDs greater than 1609459200000-0. Which command achieves this correctly?

hard

A. XREVRANGE mystream + 1609459200000-0 COUNT 3

B. XRANGE mystream 1609459200000-0 + COUNT 3

C. XREVRANGE mystream 1609459200000-0 + COUNT 3

D. XRANGE mystream + 1609459200000-0 COUNT 3

Solution

1. Step 1: Understand the requirement

   We want the 3 newest entries with IDs greater than 1609459200000-0, so we read backwards from newest (+) down to that ID.

2. Step 2: Choose correct command and range

   XREVRANGE reads newest to oldest, so range '+' to '1609459200000-0' with COUNT 3 gets newest entries above that ID.

3. Step 3: Eliminate wrong options

   XRANGE reads oldest to newest, so XRANGE mystream 1609459200000-0 + COUNT 3 and D read forward. XREVRANGE mystream 1609459200000-0 + COUNT 3 reverses range order for XREVRANGE, causing error.

4. Final Answer:

   XREVRANGE mystream + 1609459200000-0 COUNT 3 -> Option A

5. Quick Check:

   Newest entries above ID = XREVRANGE + to ID [OK]

Hint: Use XREVRANGE + to ID for newest entries above ID [OK]

Common Mistakes:

• Using XRANGE instead of XREVRANGE for newest entries
• Reversing range IDs in XREVRANGE
• Omitting COUNT to limit results