Time Complexity: UNIQUE constraint
O(log n)
0
0
UNIQUE constraint in SQL - Time & Space Complexity
Understanding Time Complexity
When we add a UNIQUE constraint to a database column, the system automatically creates a unique index (typically a B-tree) to enforce uniqueness efficiently.
We want to understand how the time to check uniqueness grows as the table gets bigger.
Scenario Under Consideration
Analyze the time complexity of enforcing a UNIQUE constraint during data insertion.
INSERT INTO users (email) VALUES ('newuser@example.com');
-- The database checks the unique index on 'email' for duplicates
-- If not found, it inserts the new row into both table and index
This code inserts a new email; the database uses the index to ensure uniqueness efficiently.
Identify Repeating Operations
The database traverses the unique index (B-tree) to check for existing values.
- Primary operation: Tree traversal/comparisons in the B-tree index.
- How many times: Proportional to the height of the tree, logarithmic in the number of rows.
How Execution Grows With Input
As the table grows, the index height increases logarithmically, keeping checks efficient.
| Input Size (n) | Approx. Operations (log n) |
|---|---|
| 10 | ~3-4 comparisons |
| 100 | ~6-7 comparisons |
| 1000 | ~9-10 comparisons |
Pattern observation: The number of operations grows logarithmically with the number of rows.
Final Time Complexity
Time Complexity: O(log n)
This means the time to check and enforce uniqueness grows logarithmically as the table gets bigger, thanks to the index.
Common Mistake
[X] Wrong: "The UNIQUE check scans all rows linearly, so O(n)."
[OK] Correct: UNIQUE constraints automatically use an index (e.g., B-tree), enabling O(log n) lookups and inserts.
Interview Connect
Understanding how constraints and indexes affect performance helps you design scalable databases and optimize queries.
Self-Check
"What if there was no index on the column? How would the time complexity change?"