Query optimization techniques in MySQL - Time & Space Complexity

Time Complexity: Query optimization techniques

O(n)

Understanding Time Complexity

When we optimize queries, we want to know how the time to run them changes as data grows.

We ask: How does the work needed grow when the database gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT orders.order_id, customers.customer_name
FROM orders
JOIN customers ON orders.customer_id = customers.customer_id
WHERE orders.order_date > '2023-01-01';

This query joins two tables and filters orders after a certain date.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning rows in orders and matching with customers.
• How many times: Once for each order, then matching customer for each order.

How Execution Grows With Input

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

Input Size (n orders)	Approx. Operations
10	About 10 order checks and matches
100	About 100 order checks and matches
1000	About 1000 order checks and matches

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: "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 grows with data size, just usually slower.

Interview Connect

Understanding how query time grows helps you explain how to keep databases fast as they get bigger.

Self-Check

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