Why indexes speed up queries in MySQL - Performance Analysis

Time Complexity: Why indexes speed up queries

O(n) without index, O(log n) with index

Understanding Time Complexity

When we use indexes in databases, queries can find data faster. We want to understand how using an index changes the work the database does as the data grows.

How does the time to find data change when we have an index versus when we don't?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT * FROM employees WHERE employee_id = 12345;

-- Assume employee_id is indexed in the second case
    

This query looks for one employee by their ID. We compare how it runs with and without an index on employee_id.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning rows to find the matching employee_id.
• How many times: Without an index, it checks each row one by one. With an index, it uses a tree search to jump directly to the right row.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations Without Index	Approx. Operations With Index
10	10 checks	About 4 steps
100	100 checks	About 7 steps
1000	1000 checks	About 10 steps

Pattern observation: Without an index, the work grows directly with the number of rows. With an index, the work grows slowly, adding just a few steps even as data grows a lot.

Final Time Complexity

Time Complexity: O(n) without index, O(log n) with index

This means without an index, the database checks every row, but with an index, it quickly narrows down to the right row using fewer steps.

Common Mistake

[X] Wrong: "Adding an index makes the query instantly fast no matter what."

[OK] Correct: Indexes help a lot, but the speed still depends on data size and query type. Some queries don't benefit from indexes.

Interview Connect

Understanding how indexes change query speed shows you know how databases handle data efficiently. This skill helps you write faster queries and explain your choices clearly.

Self-Check

"What if the query searched for a range of employee IDs instead of one? How would the time complexity change with and without an index?"

Practice

1. Why do indexes speed up queries in MySQL?

easy

A. They store all data in memory for faster access.

B. They create shortcuts to quickly find data without scanning the whole table.

C. They compress the data to reduce size.

D. They automatically backup the database.

Solution

1. Step 1: Understand what an index does

   An index works like a shortcut or a map to find data quickly instead of checking every row.

2. Step 2: Compare with full table scan

   Without an index, MySQL must look at every row, which is slow for big tables.

3. Final Answer:

   They create shortcuts to quickly find data without scanning the whole table. -> Option B

4. Quick Check:

   Indexes = shortcuts to data [OK]

Hint: Think of index as a book's index for fast lookup [OK]

Common Mistakes:

• Confusing indexes with data compression
• Thinking indexes store all data in memory
• Believing indexes backup data automatically

2. Which of the following is the correct syntax to create an index on the column email in a table users?

easy

A. CREATE INDEX ON users email_index(email);

B. INDEX CREATE email_index ON users(email);

C. CREATE users INDEX email_index(email);

D. CREATE INDEX email_index ON users(email);

Solution

1. Step 1: Recall the correct CREATE INDEX syntax

   The correct syntax is: CREATE INDEX index_name ON table_name(column_name);

2. Step 2: Match syntax with options

   CREATE INDEX email_index ON users(email); matches the correct syntax exactly.

3. Final Answer:

   CREATE INDEX email_index ON users(email); -> Option D

4. Quick Check:

   CREATE INDEX index_name ON table(column) [OK]

Hint: Remember: CREATE INDEX name ON table(column) [OK]

Common Mistakes:

• Swapping keywords order
• Missing ON keyword
• Placing index name after table name incorrectly

3. Given the table products(id INT, name VARCHAR(50), price DECIMAL) with an index on price, what will be the effect of this query?
EXPLAIN SELECT * FROM products WHERE price = 100;

medium

A. The query will use the index on price to find matching rows quickly.

B. The query will scan the entire table ignoring the index.

C. The query will cause a syntax error due to missing index hint.

D. The query will lock the entire table during execution.

Solution

1. Step 1: Understand EXPLAIN output with index

   When a column has an index and the query filters on that column, MySQL uses the index to speed up search.

2. Step 2: Analyze query behavior

   The query filters by price = 100, so the index on price helps find rows without scanning all.

3. Final Answer:

   The query will use the index on price to find matching rows quickly. -> Option A

4. Quick Check:

   Index on filtered column = faster search [OK]

Hint: Filter on indexed column uses index automatically [OK]

Common Mistakes:

• Assuming index is ignored without hints
• Thinking syntax error occurs without hints
• Believing table locks always happen on SELECT

4. You created an index on column username but your query SELECT * FROM users WHERE username = 'alice'; is still slow. What could be the problem?

medium

A. The column username is not used in the WHERE clause.

B. The query syntax is incorrect and causes slow execution.

C. The index was not created properly or is corrupted.

D. Indexes slow down all queries by default.

Solution

1. Step 1: Check if index exists and is valid

   If the index was not created correctly or got corrupted, MySQL won't use it, causing slow queries.

2. Step 2: Verify query and column usage

   The query syntax is correct and uses the indexed column, so syntax or column usage is not the issue.

3. Final Answer:

   The index was not created properly or is corrupted. -> Option C

4. Quick Check:

   Index missing or broken = slow query [OK]

Hint: Check index existence if query is slow on indexed column [OK]

Common Mistakes:

• Blaming query syntax when it's correct
• Thinking indexes always slow queries
• Ignoring that column is used in WHERE clause

5. You have a large table orders with columns order_id, customer_id, and order_date. You often run this query:
SELECT * FROM orders WHERE customer_id = 123 AND order_date > '2023-01-01';
Which indexing strategy will speed up this query best?

hard

A. Create a composite index on (customer_id, order_date).

B. Create separate indexes on customer_id and order_date.

C. Create an index only on order_date.

D. No index is needed; full table scan is faster.

Solution

1. Step 1: Understand composite index benefits

   A composite index on (customer_id, order_date) helps MySQL filter rows by both columns efficiently in one index.

2. Step 2: Compare with separate indexes

   Separate indexes may be used but are less efficient than a composite index for combined conditions.

3. Final Answer:

   Create a composite index on (customer_id, order_date). -> Option A

4. Quick Check:

   Composite index matches multi-column WHERE best [OK]

Hint: Use composite index for multi-column WHERE filters [OK]

Common Mistakes:

• Creating only single-column indexes for multi-column queries
• Assuming full table scan is faster on large tables
• Ignoring order of columns in composite index