FOREIGN KEY constraint in SQL - Time & Space Complexity

Time Complexity: FOREIGN KEY constraint

O(log n)

Understanding Time Complexity

When we use a FOREIGN KEY constraint, the database checks that related data exists. This checking takes time.

We want to understand how this checking time grows as the data grows.

Scenario Under Consideration

Analyze the time complexity of inserting a row with a FOREIGN KEY constraint.

INSERT INTO Orders (OrderID, CustomerID, OrderDate)
VALUES (101, 5, '2024-06-01');

-- CustomerID is a FOREIGN KEY referencing Customers(CustomerID)
    

This code inserts a new order and checks if the CustomerID exists in the Customers table.

Identify Repeating Operations

When inserting, the database must check the FOREIGN KEY value exists.

• Primary operation: Searching the referenced table for the matching key.
• How many times: Once per insert, but the search depends on the size of the referenced table.

How Execution Grows With Input

The search to verify the key usually uses an index, making it fast even if the table grows.

Input Size (n)	Approx. Operations
10	About 3-4 steps to find the key
100	About 7 steps
1000	About 10 steps

Pattern observation: The number of steps grows slowly, not directly with the number of rows.

Final Time Complexity

Time Complexity: O(log n)

This means the check gets a little slower as the referenced table grows, but it stays efficient.

Common Mistake

[X] Wrong: "Checking a FOREIGN KEY is as slow as scanning the whole referenced table every time."

[OK] Correct: Databases use indexes to find keys quickly, so they don't scan the whole table.

Interview Connect

Understanding how FOREIGN KEY checks scale shows you know how databases keep data correct without slowing down too much.

Self-Check

"What if the referenced column does not have an index? How would the time complexity change?"