Query optimization strategies in DBMS Theory - Time & Space Complexity

Time Complexity: Query optimization strategies

O(n)

Understanding Time Complexity

When running database queries, the time it takes can change a lot depending on how the query is written and how the database handles it.

We want to understand how the work done grows as the data size grows and how optimization helps.

Scenario Under Consideration

Analyze the time complexity of the following SQL query with and without optimization.

SELECT employee.name, department.name
FROM employee
JOIN department ON employee.dept_id = department.id
WHERE employee.salary > 50000;
    

This query joins two tables and filters employees with salary over 50000.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Scanning rows in employee and department tables.
• How many times: Each row in employee is checked, and for each matching employee, the department is looked up.

How Execution Grows With Input

As the number of employees and departments grows, the work grows too.

Input Size (n employees)	Approx. Operations
10	About 10 employee checks + department lookups
100	About 100 employee checks + department lookups
1000	About 1000 employee checks + department lookups

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows roughly in a straight line as the number of employees increases.

Common Mistake

[X] Wrong: "Adding indexes always makes queries run instantly regardless of data size."

[OK] Correct: Indexes help, but the query still needs to check matching rows, so time still grows with data size, just more slowly.

Interview Connect

Understanding how query time grows helps you write better queries and explain your thinking clearly in interviews.

Self-Check

"What if we add an index on employee.salary? How would the time complexity change?"