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?"

Practice

1. What is the main purpose of using indexes in MySQL query optimization?

easy

A. To encrypt the data for security

B. To speed up data retrieval by reducing the search area

C. To store backup copies of data

D. To increase the size of the database

Solution

1. Step 1: Understand what indexes do

   Indexes help the database find rows faster by creating a quick lookup structure.

2. Step 2: Relate indexes to query speed

   By reducing the number of rows scanned, indexes speed up data retrieval significantly.

3. Final Answer:

   To speed up data retrieval by reducing the search area -> Option B

4. Quick Check:

   Indexes improve search speed = D [OK]

Hint: Indexes speed up searches by narrowing data to scan [OK]

Common Mistakes:

• Thinking indexes increase database size only
• Confusing indexes with backups
• Believing indexes encrypt data

2. Which of the following is the correct syntax to check the query execution plan in MySQL?

easy

A. EXPLAIN SELECT * FROM users;

B. PLAN SELECT * FROM users;

C. SHOW PLAN SELECT * FROM users;

D. DESCRIBE PLAN SELECT * FROM users;

Solution

1. Step 1: Recall the command to view query plans

   MySQL uses the EXPLAIN keyword before a SELECT query to show the execution plan.

2. Step 2: Identify the correct syntax

   Only EXPLAIN SELECT * FROM users; is valid syntax to check the plan.

3. Final Answer:

   EXPLAIN SELECT * FROM users; -> Option A

4. Quick Check:

   EXPLAIN shows query plan = C [OK]

Hint: Use EXPLAIN before SELECT to see query plan [OK]

Common Mistakes:

• Using SHOW PLAN which is invalid in MySQL
• Forgetting EXPLAIN keyword
• Confusing DESCRIBE with EXPLAIN

3. Given the table employees(id INT PRIMARY KEY, name VARCHAR(50), department_id INT) with an index on department_id, what will be the effect of this query?
SELECT * FROM employees WHERE department_id = 5;

medium

A. The query will scan the entire table without using the index

B. The query will return no rows because indexes filter data

C. The query will fail due to missing index

D. The query will use the index to quickly find rows with department_id = 5

Solution

1. Step 1: Understand index usage on department_id

   Since there is an index on department_id, MySQL can use it to locate matching rows efficiently.

2. Step 2: Analyze query behavior

   The WHERE clause filters by department_id = 5, so the index helps avoid scanning all rows.

3. Final Answer:

   The query will use the index to quickly find rows with department_id = 5 -> Option D

4. Quick Check:

   Index on filter column speeds query = B [OK]

Hint: Indexed columns in WHERE speed up searches [OK]

Common Mistakes:

• Assuming index is ignored automatically
• Thinking query fails without index
• Believing indexes filter out rows

4. You wrote this query:
SELECT * FROM orders WHERE customer_id = 10 AND status = 'shipped';
You notice it runs slowly. Which fix will most likely improve performance?

medium

A. Add ORDER BY customer_id

B. Remove the WHERE clause

C. Add an index on (customer_id, status)

D. Use SELECT COUNT(*) instead of SELECT *

Solution

1. Step 1: Identify slow query cause

   The query filters on two columns but may lack a composite index to speed filtering.

2. Step 2: Apply composite index for optimization

   Adding an index on (customer_id, status) helps MySQL quickly find matching rows using both filters.

3. Final Answer:

   Add an index on (customer_id, status) -> Option C

4. Quick Check:

   Composite index speeds multi-column filters = A [OK]

Hint: Use composite index for multiple WHERE columns [OK]

Common Mistakes:

• Removing WHERE clause loses filtering
• ORDER BY does not speed filtering
• Changing SELECT * to COUNT(*) changes result, not speed

5. You have a large table sales(date DATE, product_id INT, amount DECIMAL) without indexes. You want to find total sales for product 101 in 2023 quickly. Which optimization technique is best?

hard

A. Create an index on (product_id, date) and use a query filtering both

B. Add a full table scan hint to force scanning all rows

C. Use SELECT * without WHERE to get all data

D. Drop the table and recreate it

Solution

1. Step 1: Identify query needs

   The query filters by product_id and date range, so indexing these columns helps speed filtering.

2. Step 2: Apply composite index for efficient filtering

   Creating an index on (product_id, date) allows MySQL to quickly find relevant rows without scanning the whole table.

3. Final Answer:

   Create an index on (product_id, date) and use a query filtering both -> Option A

4. Quick Check:

   Composite index on filter columns = A [OK]

Hint: Index columns used in WHERE for faster queries [OK]

Common Mistakes:

• Forcing full table scan slows query
• Selecting all rows wastes time
• Dropping table loses data