Index selection strategy in MySQL - Time & Space Complexity

Time Complexity: Index selection strategy

O(log n)

Understanding Time Complexity

When a database uses an index to find data, it can do it faster than searching every row.

We want to understand how choosing the right index affects the speed of finding data as the table grows.

Scenario Under Consideration

Analyze the time complexity of this query using an index.

SELECT * FROM employees
WHERE last_name = 'Smith';

-- Assume there is an index on last_name
    

This query looks for all employees with the last name 'Smith' using an index on the last_name column.

Identify Repeating Operations

Look at what repeats when the database searches for matching rows.

• Primary operation: Searching the index tree to find matching entries.
• How many times: The search follows a path down the index, which grows slowly as the table grows.

How Execution Grows With Input

As the table gets bigger, the index search path grows slowly, not linearly.

Input Size (n)	Approx. Operations
10	About 3 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: The number of steps grows slowly, like climbing a short ladder, even if the table grows a lot.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find data grows slowly as the table gets bigger, thanks to the index.

Common Mistake

[X] Wrong: "Using an index means the query always runs instantly no matter the table size."

[OK] Correct: Even with an index, the search takes more steps as the table grows, just much fewer than scanning all rows.

Interview Connect

Understanding how indexes speed up searches helps you explain why databases stay fast with lots of data.

Self-Check

"What if the query searched on a column without an index? How would the time complexity change?"

Practice

1. What is the main purpose of using an index in a MySQL database?

easy

A. To increase the size of the database

B. To speed up data retrieval by creating shortcuts

C. To backup the database automatically

D. To store data in a compressed format

Solution

1. Step 1: Understand what an index does

   An index creates a shortcut to quickly find data without scanning the whole table.

2. Step 2: Compare options with index purpose

   Only To speed up data retrieval by creating shortcuts describes speeding up data retrieval, which is the main use of indexes.

3. Final Answer:

   To speed up data retrieval by creating shortcuts -> Option B

4. Quick Check:

   Index = Speed up search [OK]

Hint: Indexes speed up searches by creating shortcuts [OK]

Common Mistakes:

• Thinking indexes compress data
• Confusing indexes with backups
• Believing indexes increase database size

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 email_index ON users (email);

B. CREATE INDEX ON users email_index (email);

C. CREATE INDEX users.email_index (email);

D. INDEX CREATE email_index ON users (email);

Solution

1. Step 1: Recall 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, others have wrong order or keywords.

3. Final Answer:

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

4. Quick Check:

   CREATE INDEX index_name ON table (column) [OK]

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

Common Mistakes:

• Swapping index name and table name
• Omitting ON keyword
• Wrong keyword order

3. Given a table orders with an index on customer_id, what will happen when you run this query?

SELECT * FROM orders WHERE customer_id = 123;

medium

A. The query will fail with a syntax error

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

C. The query will use the index to quickly find matching rows

D. The query will update the customer_id values

Solution

1. Step 1: Understand index usage in WHERE clause

   When a column in WHERE has an index, MySQL uses it to find rows faster.

2. Step 2: Analyze query behavior

   The query filters by customer_id, which has an index, so it uses the index to speed up search.

3. Final Answer:

   The query will use the index to quickly find matching rows -> Option C

4. Quick Check:

   Indexed column in WHERE = index used [OK]

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

Common Mistakes:

• Assuming full table scan always happens
• Confusing SELECT with UPDATE
• Expecting syntax errors in correct queries

4. You created an index on last_name but your query SELECT * FROM employees WHERE first_name = 'John'; is slow. What is the likely problem?

medium

A. The index on last_name is not used because the query filters on first_name

B. The index on last_name causes a syntax error

C. The query is missing a JOIN clause

D. The index automatically updates first_name values

Solution

1. Step 1: Identify which column is indexed

   The index is on last_name, but the query filters on first_name.

2. Step 2: Understand index usage

   Indexes only help if the filtered column is indexed; here first_name is not indexed, so index is unused.

3. Final Answer:

   The index on last_name is not used because the query filters on first_name -> Option A

4. Quick Check:

   Index column ≠ filtered column = no index use [OK]

Hint: Index helps only if filtered column matches indexed column [OK]

Common Mistakes:

• Expecting index on different column to help
• Thinking index causes syntax errors
• Confusing filtering with updating

5. You have a table products with columns category, price, and stock. You often run this query:

SELECT * FROM products WHERE category = 'Books' AND price < 20;

Which index strategy is best to speed up this query?

hard

A. Create an index only on price

B. Create separate indexes on category and stock

C. Create a composite index on (stock, price)

D. Create a composite index on (category, price)

Solution

1. Step 1: Analyze query filter columns

   The query filters on category and price together.

2. Step 2: Choose index covering both columns

   A composite index on (category, price) helps MySQL filter efficiently on both conditions.

3. Step 3: Evaluate other options

   Separate indexes or indexes on stock do not help this query's WHERE clause.

4. Final Answer:

   Create a composite index on (category, price) -> Option D

5. Quick Check:

   Composite index on filtered columns = best speed [OK]

Hint: Composite index on all filtered columns speeds queries best [OK]

Common Mistakes:

• Indexing unrelated columns
• Using separate indexes instead of composite
• Ignoring query filter columns