Index impact on INSERT and UPDATE in SQL - Time & Space Complexity

Time Complexity: Index impact on INSERT and UPDATE

O(n x k)

Understanding Time Complexity

When we add or change data in a table with indexes, the time it takes can change.

We want to understand how indexes affect the speed of INSERT and UPDATE commands.

Scenario Under Consideration

Analyze the time complexity of the following SQL commands with indexes.

-- Insert a new row
INSERT INTO employees (id, name, department) VALUES (101, 'Alice', 'HR');

-- Update an existing row
UPDATE employees SET department = 'Finance' WHERE id = 101;
    

This code adds a new employee and then updates their department in a table that has indexes.

Identify Repeating Operations

Look at what happens repeatedly when these commands run.

• Primary operation: Updating the index entries for each affected row.
• How many times: Once per row inserted or updated, plus once per index on the table.

How Execution Grows With Input

As you add or update more rows, the work grows with the number of rows and indexes.

Input Size (n rows)	Approx. Operations
10	10 x (1 + number of indexes)
100	100 x (1 + number of indexes)
1000	1000 x (1 + number of indexes)

Pattern observation: The time grows linearly with the number of rows and the number of indexes.

Final Time Complexity

Time Complexity: O(n x k)

This means the time grows with the number of rows (n) and the number of indexes (k) that need updating.

Common Mistake

[X] Wrong: "Indexes only slow down SELECT queries, so INSERT and UPDATE speed stay the same."

[OK] Correct: Every INSERT or UPDATE must also update all indexes, so more indexes mean more work and slower writes.

Interview Connect

Understanding how indexes affect data changes helps you design databases that balance fast reads and writes.

Self-Check

What if we added a new index on the department column? How would that change the time complexity for INSERT and UPDATE?

Practice

1. What is the main impact of having many indexes on a table when performing INSERT operations?

easy

A. Inserts become slower because each index must be updated.

B. Inserts become faster because indexes help locate where to insert.

C. Inserts are unaffected by indexes.

D. Inserts cause indexes to be deleted automatically.

Solution

1. Step 1: Understand how indexes affect inserts

   When inserting a new row, the database must update all indexes related to that table to keep them accurate.

2. Step 2: Analyze the effect on performance

   Updating multiple indexes adds overhead, making inserts slower as more indexes exist.

3. Final Answer:

   Inserts become slower because each index must be updated. -> Option A

4. Quick Check:

   More indexes = slower inserts [OK]

Hint: More indexes slow inserts due to extra updates [OK]

Common Mistakes:

• Thinking indexes speed up inserts
• Believing inserts ignore indexes
• Assuming indexes get deleted on insert

2. Which of the following is the correct syntax to create an index on the email column of a table named 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 standard SQL index creation syntax

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

2. Step 2: Match the syntax to options

   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:

   CREATE INDEX ... ON table(column) [OK]

Hint: Use CREATE INDEX index_name ON table(column) [OK]

Common Mistakes:

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

3. Given a table products with a non-clustered index on category_id, what happens internally when you run this query?

UPDATE products SET price = price * 1.1 WHERE category_id = 5;

medium

A. The update ignores the index and scans the whole table.

B. The update is slower because the index on category_id must be rebuilt entirely.

C. The update fails because indexes cannot be used with UPDATE statements.

D. The update is faster because the index helps find rows quickly, but the index must be updated if category_id changes.

Solution

1. Step 1: Understand index use in WHERE clause

   The index on category_id helps quickly find rows where category_id = 5.

2. Step 2: Consider index updates during UPDATE

   Since category_id is not changed, the index entries remain valid; only the data column price is updated.

3. Final Answer:

   The update is faster because the index helps find rows quickly, but the index must be updated if category_id changes. -> Option D

4. Quick Check:

   Index speeds search; update affects data, not index keys [OK]

Hint: Indexes speed WHERE search; update index only if key changes [OK]

Common Mistakes:

• Thinking index rebuilds fully on update
• Assuming update ignores indexes
• Believing update fails with indexes

4. You have a table orders with an index on order_date. You run this query:

UPDATE orders SET order_date = '2024-01-01' WHERE order_id = 100;

But the update is very slow. What is a likely cause?

medium

A. Indexes do not affect update speed, so the cause is elsewhere.

B. The query syntax is incorrect, causing a full table scan.

C. The index on order_date must be updated because the indexed column value changed.

D. The order_id column is not indexed, causing slow search.

Solution

1. Step 1: Identify which columns are indexed and updated

   The order_date column is indexed and is being updated.

2. Step 2: Understand index maintenance on update

   Updating an indexed column requires updating the index entry, which adds overhead and slows the update.

3. Final Answer:

   The index on order_date must be updated because the indexed column value changed. -> Option C

4. Quick Check:

   Updating indexed columns slows updates due to index maintenance [OK]

Hint: Updating indexed columns slows updates due to index changes [OK]

Common Mistakes:

• Ignoring index update cost
• Blaming syntax errors without checking
• Assuming indexes don't affect update speed

5. You manage a large table employees with indexes on department_id and last_name. You notice INSERT and UPDATE operations are slow. Which strategy best balances read speed and write performance?

hard

A. Remove all indexes to speed up writes, sacrificing read speed.

B. Keep only essential indexes used frequently in queries, reducing overhead on writes.

C. Add more indexes to speed up all queries regardless of write cost.

D. Disable indexes during inserts and updates and rebuild them after every operation.

Solution

1. Step 1: Understand the trade-off between indexes and write speed

   More indexes improve read speed but slow down inserts and updates because each index must be maintained.

2. Step 2: Choose a balanced approach

   Keeping only essential indexes used often reduces write overhead while maintaining reasonable read performance.

3. Final Answer:

   Keep only essential indexes used frequently in queries, reducing overhead on writes. -> Option B

4. Quick Check:

   Balance indexes for reads and writes [OK]

Hint: Keep only needed indexes to balance reads and writes [OK]

Common Mistakes:

• Removing all indexes hurting reads
• Adding too many indexes slowing writes
• Rebuilding indexes too often causing delays