Why filtering is essential in SQL - Performance Analysis

Time Complexity: Why filtering is essential

O(n)

Understanding Time Complexity

When we run database queries, filtering helps us get only the data we need.

We want to know how filtering affects the time it takes to get results.

Scenario Under Consideration

Analyze the time complexity of the following SQL query with filtering.

SELECT *
FROM employees
WHERE department = 'Sales';

This query selects all employees who work in the Sales department.

Identify Repeating Operations

Look at what repeats when the database runs this query.

• Primary operation: Checking each employee's department value.
• How many times: Once for every employee in the table.

How Execution Grows With Input

As the number of employees grows, the database checks more rows.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "Filtering makes the query run instantly no matter the size."

[OK] Correct: The database still checks each row to see if it matches the filter, so bigger tables take more time.

Interview Connect

Understanding how filtering affects query time shows you know how databases handle data efficiently.

Self-Check

"What if we add an index on the department column? How would the time complexity change?"