Foreign key ON UPDATE behavior in SQL - Time & Space Complexity

Time Complexity: Foreign key ON UPDATE behavior

O(n)

Understanding Time Complexity

When a foreign key has an ON UPDATE rule, the database may need to update related rows automatically.

We want to understand how the time to update grows as the number of related rows increases.

Scenario Under Consideration

Analyze the time complexity of this foreign key update behavior.

ALTER TABLE Orders
  ADD CONSTRAINT fk_customer
  FOREIGN KEY (customer_id)
  REFERENCES Customers(id)
  ON UPDATE CASCADE;

UPDATE Customers
  SET id = id + 100
  WHERE id = 5;
    

This code sets a foreign key with ON UPDATE CASCADE, then updates a customer ID, causing related Orders rows to update.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Updating all rows in the child table (Orders) that reference the updated parent row.
• How many times: Once for each related row in Orders with the matching customer_id.

How Execution Grows With Input

As the number of related Orders rows grows, the database must update more rows.

Input Size (n)	Approx. Operations
10	10 updates to Orders rows
100	100 updates to Orders rows
1000	1000 updates to Orders rows

Pattern observation: The work grows directly with the number of related rows to update.

Final Time Complexity

Time Complexity: O(n)

This means the update time grows linearly with the number of related rows that need updating.

Common Mistake

[X] Wrong: "Updating the parent row is always a quick single operation regardless of child rows."

[OK] Correct: Because ON UPDATE CASCADE forces updates on all related child rows, the time depends on how many child rows exist.

Interview Connect

Understanding how foreign key updates scale helps you reason about database performance and data integrity in real projects.

Self-Check

"What if the ON UPDATE rule was SET NULL instead of CASCADE? How would the time complexity change?"