Foreign key linking mental model in SQL - Time & Space Complexity

Time Complexity: Foreign key linking mental model

O(n)

Understanding Time Complexity

When we use foreign keys in databases, we link tables together. Understanding how this linking affects the time it takes to run queries helps us write better database code.

We want to know how the work grows when the tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following SQL query using a foreign key join.

SELECT orders.order_id, customers.name
FROM orders
JOIN customers ON orders.customer_id = customers.customer_id
WHERE customers.city = 'New York';
    

This query finds all orders made by customers who live in New York by linking the orders and customers tables using a foreign key.

Identify Repeating Operations

Look at what repeats as the query runs.

• Primary operation: Scanning the orders table and looking up matching customers based on the customer_id foreign key.
• How many times: For each order, the database looks up the matching customer to check the city.

How Execution Grows With Input

As the number of orders and customers grows, the work to find matching rows grows too.

Input Size (n)	Approx. Operations
10	About 10 lookups
100	About 100 lookups
1000	About 1000 lookups

Pattern observation: The work grows roughly in direct proportion to the number of orders.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows linearly with the number of orders.

Common Mistake

[X] Wrong: "Joining tables with foreign keys always makes queries slow and complex."

[OK] Correct: With proper indexes, the database can quickly find matching rows, so the query time grows in a simple, predictable way.

Interview Connect

Understanding how foreign key joins scale helps you explain how databases handle linked data efficiently, a useful skill in many real-world projects.

Self-Check

"What if we added an index on customers.city? How would the time complexity change?"