Unique indexes in MySQL - Time & Space Complexity

Time Complexity: Unique indexes

O(log n)

Understanding Time Complexity

When we use unique indexes in a database, it helps keep data clean by preventing duplicates.

We want to understand how the time to check uniqueness grows as the data grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

CREATE TABLE users (
  id INT PRIMARY KEY,
  email VARCHAR(255),
  UNIQUE INDEX unique_email (email)
);

INSERT INTO users (id, email) VALUES (1, '[e-mail]');
INSERT INTO users (id, email) VALUES (2, '[e-mail]');
-- Attempt to insert duplicate email
INSERT INTO users (id, email) VALUES (3, '[e-mail]');
    

This code creates a table with a unique index on the email column and tries to insert rows, including a duplicate email.

Identify Repeating Operations

• Primary operation: Checking if the email already exists in the unique index.
• How many times: Once per insert operation, the database searches the index to find duplicates.

How Execution Grows With Input

As more rows are added, the database must search a larger index to check uniqueness.

Input Size (n)	Approx. Operations
10	About 4 steps to find or reject duplicate
100	About 7 steps
1000	About 10 steps

Pattern observation: The number of steps grows slowly as data grows, not one-by-one.

Final Time Complexity

Time Complexity: O(log n)

This means checking for duplicates takes a little more time as data grows, but it grows slowly and efficiently.

Common Mistake

[X] Wrong: "Checking for duplicates takes the same time no matter how many rows there are."

[OK] Correct: The database uses a special structure that lets it find duplicates faster than checking every row one by one.

Interview Connect

Understanding how unique indexes work and their time cost shows you know how databases keep data clean efficiently.

Self-Check

"What if the unique index was on multiple columns instead of one? How would the time complexity change?"

Practice

1. What is the main purpose of a UNIQUE index in MySQL?

easy

A. To prevent duplicate values in one or more columns

B. To speed up data insertion

C. To allow duplicate values in a column

D. To delete duplicate rows automatically

Solution

1. Step 1: Understand the role of UNIQUE index

   A UNIQUE index ensures that no two rows have the same value in the indexed column(s).

2. Step 2: Compare options with this definition

   Only To prevent duplicate values in one or more columns correctly states that UNIQUE prevents duplicates. Others are incorrect or unrelated.

3. Final Answer:

   To prevent duplicate values in one or more columns -> Option A

4. Quick Check:

   UNIQUE index = prevent duplicates [OK]

Hint: UNIQUE means no duplicates allowed in indexed columns [OK]

Common Mistakes:

• Thinking UNIQUE speeds up inserts
• Believing UNIQUE allows duplicates
• Confusing UNIQUE with automatic deletion

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

easy

A. CREATE UNIQUE KEY idx_email FROM users(email);

B. CREATE INDEX UNIQUE idx_email ON users(email);

C. CREATE UNIQUE INDEX idx_email ON users(email);

D. CREATE UNIQUE ON users INDEX idx_email(email);

Solution

1. Step 1: Recall correct syntax for UNIQUE index creation

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

2. Step 2: Match options with correct syntax

   CREATE UNIQUE INDEX idx_email ON users(email); matches exactly. Others have wrong keyword order or syntax errors.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Swapping UNIQUE and INDEX keywords
• Using FROM instead of ON
• Incorrect keyword order

3. Given the table employees with a UNIQUE index on employee_id, what happens if you run this query?

INSERT INTO employees (employee_id, name) VALUES (101, 'Alice');
INSERT INTO employees (employee_id, name) VALUES (101, 'Bob');

medium

A. The second insert fails with a duplicate key error

B. Both rows are inserted successfully

C. The second insert overwrites the first row

D. The second insert is ignored silently

Solution

1. Step 1: Understand UNIQUE index effect on inserts

   A UNIQUE index on employee_id prevents duplicate values in that column.

2. Step 2: Analyze the inserts

   The first insert adds employee_id 101. The second insert tries to add the same employee_id 101, violating the UNIQUE constraint, causing an error.

3. Final Answer:

   The second insert fails with a duplicate key error -> Option A

4. Quick Check:

   UNIQUE index blocks duplicate inserts [OK]

Hint: Duplicate insert on UNIQUE column causes error [OK]

Common Mistakes:

• Assuming duplicates are allowed
• Thinking second insert overwrites first
• Believing second insert is ignored silently

4. You tried to create a UNIQUE index on the column username but got an error. Which of these is the most likely cause?

medium

A. The table does not exist

B. The username column contains duplicate values

C. You forgot to specify the index name

D. UNIQUE indexes are not supported on text columns

Solution

1. Step 1: Understand UNIQUE index creation requirements

   Creating a UNIQUE index requires all existing values in the column to be unique.

2. Step 2: Identify common error causes

   If duplicates exist, MySQL throws an error when creating the UNIQUE index.

3. Final Answer:

   The username column contains duplicate values -> Option B

4. Quick Check:

   Duplicates block UNIQUE index creation [OK]

Hint: Check for duplicates before creating UNIQUE index [OK]

Common Mistakes:

• Assuming index name is mandatory
• Believing UNIQUE not allowed on text columns
• Ignoring existing duplicates

5. You want to ensure that the combination of first_name and last_name in the contacts table is unique, but duplicates are still appearing. Which is the best way to fix this?

hard

A. Use a CHECK constraint to prevent duplicates

B. Create separate UNIQUE indexes on first_name and last_name individually

C. Add a PRIMARY KEY on first_name

D. Create a UNIQUE index on both first_name and last_name columns together

Solution

1. Step 1: Understand uniqueness on multiple columns

   To ensure uniqueness on a combination, a composite UNIQUE index on both columns is needed.

2. Step 2: Analyze other options

   Separate UNIQUE indexes allow duplicates across combinations. PRIMARY KEY on one column doesn't cover both. CHECK constraints can't enforce uniqueness.

3. Final Answer:

   Create a UNIQUE index on both first_name and last_name columns together -> Option D

4. Quick Check:

   Composite UNIQUE index = unique pairs [OK]

Hint: Use composite UNIQUE index for multi-column uniqueness [OK]

Common Mistakes:

• Creating separate UNIQUE indexes instead of composite
• Using PRIMARY KEY on one column only
• Relying on CHECK constraints for uniqueness