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?"