When indexes help and when they hurt in SQL - Time & Space Complexity

Time Complexity: When indexes help and when they hurt

O(log n)

Understanding Time Complexity

Indexes can speed up database searches but sometimes slow down other operations.

We want to understand when using an index helps and when it might hurt performance.

Scenario Under Consideration

Analyze the time complexity of this query using an index.

-- Assume an index exists on column 'name'
SELECT * FROM employees WHERE name = 'Alice';

-- Insert operation
INSERT INTO employees (id, name, department) VALUES (101, 'Bob', 'Sales');
    

The first query searches for a specific name using an index. The second inserts a new row, which may update the index.

Identify Repeating Operations

Look at what repeats during these operations.

• Primary operation for SELECT: Searching the index tree to find matching rows.
• How many times: Depends on the height of the index tree, usually much less than scanning all rows.
• Primary operation for INSERT: Adding a new entry to the index structure.
• How many times: Once per insert, but involves updating the index which can be costly.

How Execution Grows With Input

As the table grows, the index search stays efficient, but inserts get a bit slower.

Input Size (n)	Approx. Operations for SELECT	Approx. Operations for INSERT
10	About 3 steps (small tree height)	Simple insert + index update
100	About 4 steps	Insert + more index updates
1000	About 5 steps	Insert + even more index updates

Pattern observation: SELECT grows slowly with input size, INSERT grows a bit faster due to index maintenance.

Final Time Complexity

Time Complexity: O(log n)

This means searching with an index grows slowly as data grows, but insertions cost more because the index must be updated.

Common Mistake

[X] Wrong: "Adding an index always makes everything faster."

[OK] Correct: Indexes speed up searches but slow down inserts, updates, and deletes because the index must be maintained.

Interview Connect

Understanding when indexes help or hurt shows you know how databases balance speed and cost, a key skill for real projects.

Self-Check

"What if we added multiple indexes on different columns? How would that affect insert and search time complexity?"

Practice

1. Which of the following best describes when an index helps in a database?

easy

A. When you want to reduce the size of the database file.

B. When you want to speed up inserting new rows.

C. When you want to quickly find rows based on column values.

D. When you want to delete all rows faster.

Solution

1. Step 1: Understand what indexes do

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

2. Step 2: Identify when this is useful

   Searching rows by column values is faster with indexes, but inserts or deletes can slow down.

3. Final Answer:

   When you want to quickly find rows based on column values. -> Option C

4. Quick Check:

   Indexes speed up searching [OK]

Hint: Indexes speed up searches, not inserts or deletes [OK]

Common Mistakes:

• Thinking indexes speed up inserts
• Confusing index purpose with storage size
• Assuming indexes help deletes

2. Which SQL statement correctly creates an index on the column email in the table users?

easy

A. CREATE INDEX idx_email ON users(email);

B. CREATE users INDEX ON email;

C. INDEX CREATE ON users(email);

D. CREATE INDEX users_email 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 the options to syntax

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

3. Final Answer:

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

4. Quick Check:

   Correct CREATE INDEX syntax = CREATE INDEX idx_email ON users(email); [OK]

Hint: CREATE INDEX index_name ON table(column) is correct syntax [OK]

Common Mistakes:

• Swapping table and column names
• Omitting ON keyword
• Wrong order of keywords

3. Given a table orders with 1 million rows and an index on customer_id, what is the expected effect of running SELECT * FROM orders WHERE customer_id = 123;?

medium

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

B. The query will scan all rows, ignoring the index.

C. The query will be slower because indexes slow down SELECT queries.

D. The query will fail because indexes cannot be used in WHERE clauses.

Solution

1. Step 1: Understand index usage in WHERE clause

   Indexes help the database quickly locate rows matching the WHERE condition on indexed columns.

2. Step 2: Apply to the query

   Since customer_id is indexed, the query uses the index to find rows without scanning all 1 million rows.

3. Final Answer:

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

4. Quick Check:

   Indexed WHERE columns speed up SELECT [OK]

Hint: WHERE on indexed columns uses index for fast lookup [OK]

Common Mistakes:

• Thinking indexes slow down SELECT
• Believing indexes are ignored in WHERE
• Assuming query fails with indexes

4. You notice that inserting rows into a table is very slow after adding several indexes. What is the most likely cause?

medium

A. Indexes cause syntax errors during inserts.

B. Indexes speed up inserts, so the problem is elsewhere.

C. The table is too small for indexes to matter.

D. Indexes slow down inserts because each insert updates all indexes.

Solution

1. Step 1: Understand index impact on inserts

   Each insert must update all indexes to keep them current, which adds overhead and slows inserts.

2. Step 2: Identify cause of slow inserts

   Adding many indexes increases this overhead, causing slower insert performance.

3. Final Answer:

   Indexes slow down inserts because each insert updates all indexes. -> Option D

4. Quick Check:

   More indexes = slower inserts [OK]

Hint: More indexes mean slower inserts due to update overhead [OK]

Common Mistakes:

• Thinking indexes speed up inserts
• Blaming syntax errors for slow inserts
• Ignoring index update cost

5. A table products has indexes on category_id and price. You run a query filtering on category_id and sorting by price. How can indexes help, and what might hurt performance?

hard

A. Indexes do not help filtering or sorting; they only help joins.

B. Index on category_id helps filtering; index on price helps sorting; but too many indexes slow inserts.

C. Indexes speed up inserts but slow down filtering and sorting.

D. Indexes on both columns cause syntax errors in queries.

Solution

1. Step 1: Analyze filtering and sorting with indexes

   The index on category_id speeds up filtering rows matching that category. The index on price can speed up sorting if used properly.

2. Step 2: Consider performance trade-offs

   Having multiple indexes helps reads but slows down inserts and updates because all indexes must be maintained.

3. Final Answer:

   Index on category_id helps filtering; index on price helps sorting; but too many indexes slow inserts. -> Option B

4. Quick Check:

   Indexes help filtering and sorting but slow inserts [OK]

Hint: Indexes help reads but slow writes when many exist [OK]

Common Mistakes:

• Believing indexes only help joins
• Thinking indexes speed up inserts
• Assuming indexes cause syntax errors