EVAL command for Lua execution in Redis - Time & Space Complexity

Time Complexity: EVAL command for Lua execution

O(n)

Understanding Time Complexity

When running Lua scripts with Redis's EVAL command, it's important to know how the time to run the script changes as the script or data grows.

We want to understand how the execution time scales when the script processes more keys or data.

Scenario Under Consideration

Analyze the time complexity of this Redis Lua script run with EVAL.

EVAL "
  local sum = 0
  for i, key in ipairs(KEYS) do
    local val = redis.call('GET', key)
    if val then
      sum = sum + tonumber(val)
    end
  end
  return sum
" 3 key1 key2 key3
    

This script sums the numeric values of the given keys by fetching each key's value one by one.

Identify Repeating Operations

Look for repeated actions inside the script.

• Primary operation: Looping over each key in the KEYS list.
• How many times: Once for each key provided to the script.

How Execution Grows With Input

The script does one GET call per key, so the work grows as the number of keys grows.

Input Size (n)	Approx. Operations
10	10 GET calls + 10 additions
100	100 GET calls + 100 additions
1000	1000 GET calls + 1000 additions

Pattern observation: The number of operations grows directly with the number of keys.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the script grows linearly with the number of keys it processes.

Common Mistake

[X] Wrong: "The script runs in constant time no matter how many keys it processes."

[OK] Correct: Each key requires a separate GET call, so more keys mean more work and longer execution time.

Interview Connect

Understanding how Lua scripts run inside Redis helps you write efficient scripts and explain their performance clearly in real-world situations.

Self-Check

"What if the script used redis.call('MGET', unpack(KEYS)) instead of looping over keys? How would the time complexity change?"

Practice

1. What is the main purpose of the EVAL command in Redis?

easy

A. To run Lua scripts inside Redis for atomic operations

B. To execute SQL queries on Redis data

C. To backup Redis data to a file

D. To create new Redis databases

Solution

1. Step 1: Understand Redis scripting

   Redis uses Lua scripts to perform complex or multiple operations atomically.

2. Step 2: Identify EVAL command role

   The EVAL command runs Lua scripts inside Redis, ensuring atomicity and reducing network calls.

3. Final Answer:

   To run Lua scripts inside Redis for atomic operations -> Option A

4. Quick Check:

   EVAL runs Lua scripts = D [OK]

Hint: EVAL runs Lua scripts atomically inside Redis [OK]

Common Mistakes:

• Confusing EVAL with SQL execution
• Thinking EVAL backs up data
• Assuming EVAL creates databases

2. Which of the following is the correct syntax to run a Lua script with EVAL in Redis?

easy

A. EVAL script numkeys key [key ...] arg [arg ...]

B. EVAL numkeys script key [key ...] arg [arg ...]

C. EVAL script key numkeys arg [arg ...]

D. EVAL script arg numkeys key [key ...]

Solution

1. Step 1: Recall EVAL syntax

   The correct syntax is EVAL script numkeys key [key ...] arg [arg ...], where numkeys tells how many keys follow.

2. Step 2: Match options

   Only EVAL script numkeys key [key ...] arg [arg ...] matches this exact order and structure.

3. Final Answer:

   EVAL script numkeys key [key ...] arg [arg ...] -> Option A

4. Quick Check:

   Script, numkeys, keys, args order = A [OK]

Hint: Remember: script, numkeys, keys, then args in EVAL [OK]

Common Mistakes:

• Placing numkeys after keys or args
• Mixing order of keys and args
• Omitting numkeys parameter

3. Given the Lua script return redis.call('GET', KEYS[1]) and the command EVAL script 1 mykey, what will Redis return if mykey holds the value 'hello'?

medium

A. An error because arguments are missing

B. nil

C. 'hello'

D. The string 'mykey'

Solution

1. Step 1: Understand the Lua script

   The script calls redis.call('GET', KEYS[1]), which fetches the value of the first key passed.

2. Step 2: Analyze the command

   The command passes 1 key: mykey. If mykey holds 'hello', the script returns 'hello'.

3. Final Answer:

   'hello' -> Option C

4. Quick Check:

   GET mykey = 'hello' [OK]

Hint: Lua script returns value of first key passed [OK]

Common Mistakes:

• Confusing keys and args
• Expecting key name instead of value
• Assuming nil if key exists

4. What is wrong with this Redis command? EVAL 'return redis.call('GET', KEYS[1])' 1 mykey

medium

A. Missing number of keys argument

B. The Lua script string uses conflicting single quotes causing syntax error

C. Keys and args are swapped

D. The command is correct and will run successfully

Solution

1. Step 1: Inspect Lua script quoting

   The Lua script is enclosed in single quotes, but inside it also uses single quotes for 'GET', causing quote conflict.

2. Step 2: Identify syntax error

   This causes a syntax error because the shell or Redis cannot parse the string properly.

3. Final Answer:

   The Lua script string uses conflicting single quotes causing syntax error -> Option B

4. Quick Check:

   Quote conflict in script string = A [OK]

Hint: Use different quotes or escape inner quotes in Lua script [OK]

Common Mistakes:

• Ignoring quote conflicts
• Forgetting to escape inner quotes
• Miscounting number of keys

5. You want to atomically increment a Redis key counter by a value passed as an argument using EVAL. Which Lua script and command correctly achieve this?

hard

A. Script: return redis.call('INCRBY', ARGV[1], KEYS[1])Command: EVAL script 1 counter 5

B. Script: return redis.call('INCRBY', KEYS[1], ARGV[1])Command: EVAL script 2 counter 5

C. Script: return redis.call('INCRBY', KEYS[1], ARGV[1])Command: EVAL script 0 counter 5

D. Script: return redis.call('INCRBY', KEYS[1], ARGV[1])Command: EVAL script 1 counter 5

Solution

1. Step 1: Understand INCRBY usage in Lua script

   The command redis.call('INCRBY', KEYS[1], ARGV[1]) increments the key by the argument value.

2. Step 2: Check command arguments

   Passing 1 as number of keys, then counter as key, and 5 as argument matches the script.

3. Final Answer:

   Script: return redis.call('INCRBY', KEYS[1], ARGV[1]) and Command: EVAL script 1 counter 5 -> Option D

4. Quick Check:

   INCRBY key arg with correct keys count = B [OK]

Hint: Keys count must match keys passed; args follow keys [OK]

Common Mistakes:

• Swapping keys and args order
• Incorrect number of keys argument
• Using zero keys when keys are needed