Why understanding relationships matters in SQL - Performance Analysis

Time Complexity: Why understanding relationships matters

O(n)

Understanding Time Complexity

When working with databases, knowing how tables relate helps us understand how queries run.

We want to see how the time to get results changes as data grows.

Scenario Under Consideration

Analyze the time complexity of the following SQL join query.

SELECT orders.order_id, customers.customer_name
FROM orders
JOIN customers ON orders.customer_id = customers.customer_id
WHERE customers.country = 'USA';
    

This query finds all orders made by customers from the USA by joining two tables on a shared key.

Identify Repeating Operations

Look for repeated steps that take time as data grows.

• Primary operation: Matching each order to a customer by comparing keys.
• How many times: For every order, the database looks up the matching customer.

How Execution Grows With Input

As the number of orders and customers grows, the work to join them grows too.

Input Size (n)	Approx. Operations
10 orders, 5 customers	About 10 lookups
100 orders, 50 customers	About 100 lookups
1000 orders, 500 customers	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 roughly in step with the number of orders.

Common Mistake

[X] Wrong: "Joining tables always means the time grows much faster, like squared."

[OK] Correct: When keys are indexed, the database can quickly find matches, so time grows linearly, not squared.

Interview Connect

Understanding how joins scale helps you explain query performance clearly and shows you know how databases handle relationships efficiently.

Self-Check

"What if the customers table had no index on customer_id? How would the time complexity change?"

Practice

1. Why is it important to understand relationships between tables in a database?

easy

A. Because relationships prevent any data from being deleted.

B. Because relationships make the database run faster automatically.

C. Because relationships allow us to connect and combine data from different tables.

D. Because relationships store data in a single table only.

Solution

1. Step 1: Understand the role of relationships

   Relationships link tables so data can be combined meaningfully.

2. Step 2: Recognize the benefit of linking data

   Linking data helps answer questions that need info from multiple tables.

3. Final Answer:

   Because relationships allow us to connect and combine data from different tables. -> Option C

4. Quick Check:

   Relationships connect tables = C [OK]

Hint: Relationships connect tables to combine data easily [OK]

Common Mistakes:

• Thinking relationships speed up database automatically
• Believing relationships prevent data deletion
• Assuming all data is stored in one table

2. Which SQL keyword is used to combine rows from two tables based on a related column?

easy

A. JOIN

B. SELECT

C. WHERE

D. GROUP BY

Solution

1. Step 1: Identify the keyword for combining tables

   JOIN is used to link rows from two tables using a common column.

2. Step 2: Differentiate from other keywords

   SELECT retrieves data, WHERE filters rows, GROUP BY groups rows; only JOIN combines tables.

3. Final Answer:

   JOIN -> Option A

4. Quick Check:

   JOIN combines tables = B [OK]

Hint: JOIN links tables on common columns [OK]

Common Mistakes:

• Using SELECT to combine tables
• Confusing WHERE with JOIN
• Thinking GROUP BY combines tables

3. Given two tables:
Employees(emp_id, name, dept_id)
Departments(dept_id, dept_name)
What will this query return?

SELECT name, dept_name FROM Employees JOIN Departments ON Employees.dept_id = Departments.dept_id;

medium

A. A list of department names only.

B. A list of employee names with their department names.

C. A list of employee names only.

D. An error because JOIN syntax is wrong.

Solution

1. Step 1: Understand the JOIN condition

   The query joins Employees and Departments where dept_id matches.

2. Step 2: Identify selected columns

   It selects employee names and their matching department names.

3. Final Answer:

   A list of employee names with their department names. -> Option B

4. Quick Check:

   JOIN on dept_id returns employee and department names = A [OK]

Hint: JOIN returns combined rows matching keys [OK]

Common Mistakes:

• Expecting only one table's columns
• Thinking JOIN causes syntax error
• Ignoring the ON condition

4. What is wrong with this SQL query?

SELECT name, dept_name FROM Employees JOIN Departments WHERE Employees.dept_id = Departments.dept_id;

medium

A. WHERE cannot be used with JOIN.

B. SELECT cannot have multiple columns.

C. Table names are incorrect.

D. Missing ON keyword for JOIN condition.

Solution

1. Step 1: Check JOIN syntax

   JOIN requires ON keyword to specify join condition, not WHERE.

2. Step 2: Understand WHERE usage

   WHERE filters rows after join; join condition must be in ON clause.

3. Final Answer:

   Missing ON keyword for JOIN condition. -> Option D

4. Quick Check:

   JOIN needs ON for condition = D [OK]

Hint: JOIN condition must use ON, not WHERE [OK]

Common Mistakes:

• Using WHERE instead of ON for join condition
• Thinking SELECT can't have multiple columns
• Assuming table names are wrong

5. You have three tables:
Orders(order_id, customer_id, product_id)
Customers(customer_id, customer_name)
Products(product_id, product_name)
How would you write a query to list each order with the customer name and product name?

hard

A. SELECT order_id, customer_name, product_name FROM Orders JOIN Customers ON Orders.customer_id = Customers.customer_id JOIN Products ON Orders.product_id = Products.product_id;

B. SELECT order_id, customer_name, product_name FROM Orders, Customers, Products WHERE Orders.customer_id = Customers.customer_id;

C. SELECT order_id, customer_name, product_name FROM Orders LEFT JOIN Customers ON Orders.customer_id = Customers.customer_id;

D. SELECT order_id, customer_name, product_name FROM Customers JOIN Products ON Customers.customer_id = Products.product_id;

Solution

1. Step 1: Identify needed joins

   Orders must join Customers on customer_id and Products on product_id to get names.

2. Step 2: Write correct JOIN syntax

   Use JOIN with ON for both tables to link properly.

3. Step 3: Check other options

   B misses the product_id join condition; C misses Products join; D joins unrelated keys.

4. Final Answer:

   SELECT order_id, customer_name, product_name FROM Orders JOIN Customers ON Orders.customer_id = Customers.customer_id JOIN Products ON Orders.product_id = Products.product_id; -> Option A

5. Quick Check:

   Correct JOINs on keys = A [OK]

Hint: Join all related tables on keys using ON [OK]

Common Mistakes:

• Missing one join to include all data
• Joining on wrong columns
• Using WHERE instead of ON for joins