Primary keys and uniqueness in SQL - Time & Space Complexity

Time Complexity: Primary keys and uniqueness

O(log n)

Understanding Time Complexity

When we use primary keys and uniqueness constraints in a database, the system must check if new data breaks these rules.

We want to know how the time to check these rules grows as the data grows.

Scenario Under Consideration

Analyze the time complexity of inserting a new row with a primary key constraint.

INSERT INTO users (user_id, name) VALUES (123, 'Alice');
-- user_id is the primary key
    

This code adds a new user, ensuring the user_id is unique as required by the primary key.

Identify Repeating Operations

What does the database do to keep the primary key unique?

• Primary operation: Searching the index for the user_id to check uniqueness.
• How many times: Once per insert, but the search depends on the number of rows.

How Execution Grows With Input

As the table grows, the time to check if the user_id exists changes.

Input Size (n)	Approx. Operations
10	About 4-5 steps to find or confirm uniqueness
100	About 7 steps
1000	About 10 steps

Pattern observation: The number of steps grows slowly, not directly with n, but with how deep the index tree is.

Final Time Complexity

Time Complexity: O(log n)

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

Common Mistake

[X] Wrong: "Checking uniqueness takes the same time no matter how big the table is."

[OK] Correct: The database uses an index, which grows in a balanced way, so checking takes more steps as data grows, but not one step per row.

Interview Connect

Understanding how primary keys affect performance shows you know how databases keep data safe and fast, a key skill for real projects.

Self-Check

"What if the primary key was not indexed? How would the time complexity change?"

Practice

1. Which of the following is TRUE about a PRIMARY KEY in a SQL table?

easy

A. It allows duplicate values but no NULLs.

B. It uniquely identifies each row and cannot contain NULL values.

C. It can contain multiple NULL values.

D. It is used only for indexing and does not enforce uniqueness.

Solution

1. Step 1: Understand the role of PRIMARY KEY

   A PRIMARY KEY uniquely identifies each row in a table and does not allow NULL values to ensure every row is distinct.

2. Step 2: Compare options with PRIMARY KEY properties

   It uniquely identifies each row and cannot contain NULL values. correctly states uniqueness and no NULLs. Other options contradict these rules.

3. Final Answer:

   It uniquely identifies each row and cannot contain NULL values. -> Option B

4. Quick Check:

   PRIMARY KEY = unique + no NULL [OK]

Hint: Primary key = unique + no NULL values [OK]

Common Mistakes:

• Thinking primary keys allow NULLs
• Confusing primary key with unique constraint
• Assuming primary key allows duplicates

2. Which SQL statement correctly defines a column id as a primary key in a table?

easy

A. CREATE TABLE users (id INT, name VARCHAR(50) PRIMARY KEY);

B. CREATE TABLE users (id INT UNIQUE, name VARCHAR(50));

C. CREATE TABLE users (id INT PRIMARY KEY, name VARCHAR(50));

D. CREATE TABLE users (id INT NOT NULL, name VARCHAR(50));

Solution

1. Step 1: Identify correct PRIMARY KEY syntax

   The correct syntax to define a primary key inline is column_name data_type PRIMARY KEY.

2. Step 2: Check each option

   CREATE TABLE users (id INT PRIMARY KEY, name VARCHAR(50)); uses correct syntax. CREATE TABLE users (id INT UNIQUE, name VARCHAR(50)); uses UNIQUE, not PRIMARY KEY. CREATE TABLE users (id INT NOT NULL, name VARCHAR(50)); only uses NOT NULL. CREATE TABLE users (id INT, name VARCHAR(50) PRIMARY KEY); incorrectly assigns PRIMARY KEY to the wrong column.

3. Final Answer:

   CREATE TABLE users (id INT PRIMARY KEY, name VARCHAR(50)); -> Option C

4. Quick Check:

   PRIMARY KEY syntax = column_name data_type PRIMARY KEY [OK]

Hint: PRIMARY KEY goes right after column type [OK]

Common Mistakes:

• Using UNIQUE instead of PRIMARY KEY
• Placing PRIMARY KEY on wrong column
• Omitting PRIMARY KEY keyword

3. Given the table employees with id as PRIMARY KEY, what happens if you run this SQL?

INSERT INTO employees (id, name) VALUES (1, 'Alice');
INSERT INTO employees (id, name) VALUES (1, 'Bob');

medium

A. The second insert fails due to duplicate primary key.

B. Both rows are inserted successfully.

C. The second insert overwrites the first row.

D. Both inserts fail because primary keys cannot be integers.

Solution

1. Step 1: Understand PRIMARY KEY uniqueness constraint

   PRIMARY KEY enforces unique values. The first insert adds id=1 successfully.

2. Step 2: Analyze second insert with duplicate id

   The second insert tries to add id=1 again, violating uniqueness, causing an error.

3. Final Answer:

   The second insert fails due to duplicate primary key. -> Option A

4. Quick Check:

   Duplicate PRIMARY KEY value causes insert failure [OK]

Hint: Duplicate primary keys cause insert errors [OK]

Common Mistakes:

• Assuming duplicates are allowed in primary key
• Thinking second insert overwrites first
• Believing primary keys cannot be integers

4. You have this table definition:

CREATE TABLE products (
  product_id INT UNIQUE,
  name VARCHAR(100)
);

Which problem will occur if you try to insert two rows with product_id as NULL?

medium

A. Both rows insert successfully because UNIQUE allows multiple NULLs.

B. The second insert fails because UNIQUE does not allow duplicate NULLs.

C. Syntax error because NULL is not allowed in UNIQUE columns.

D. Both inserts fail because product_id is not a PRIMARY KEY.

Solution

1. Step 1: Understand UNIQUE constraint with NULLs

   UNIQUE allows only one NULL in some databases, but standard SQL allows multiple NULLs because NULL means unknown.

2. Step 2: Apply to given inserts

   In most SQL systems, inserting multiple rows with NULL in a UNIQUE column succeeds because NULLs are not considered equal.

3. Final Answer:

   Both rows insert successfully because UNIQUE allows multiple NULLs. -> Option A

4. Quick Check:

   UNIQUE allows multiple NULLs in most SQL [OK]

Hint: UNIQUE allows multiple NULLs, PRIMARY KEY does not [OK]

Common Mistakes:

• Assuming UNIQUE disallows multiple NULLs
• Confusing UNIQUE with PRIMARY KEY NULL rules
• Expecting syntax error on NULL in UNIQUE

5. You want to create a table orders where each order has a unique order_id and a unique tracking_number that can be NULL. Which SQL definition is correct?

hard

A. CREATE TABLE orders (order_id INT UNIQUE, tracking_number VARCHAR(20) PRIMARY KEY);

B. CREATE TABLE orders (order_id INT, tracking_number VARCHAR(20) UNIQUE PRIMARY KEY);

C. CREATE TABLE orders (order_id INT PRIMARY KEY UNIQUE, tracking_number VARCHAR(20) NOT NULL UNIQUE);

D. CREATE TABLE orders (order_id INT PRIMARY KEY, tracking_number VARCHAR(20) UNIQUE);

Solution

1. Step 1: Define order_id as PRIMARY KEY

   order_id must be unique and not NULL, so PRIMARY KEY is appropriate.

2. Step 2: Define tracking_number as UNIQUE and nullable

   tracking_number should be unique but can be NULL, so UNIQUE constraint without NOT NULL is correct.

3. Step 3: Evaluate options

   CREATE TABLE orders (order_id INT PRIMARY KEY, tracking_number VARCHAR(20) UNIQUE); matches requirements. CREATE TABLE orders (order_id INT UNIQUE, tracking_number VARCHAR(20) PRIMARY KEY); wrongly assigns PRIMARY KEY to tracking_number. CREATE TABLE orders (order_id INT PRIMARY KEY UNIQUE, tracking_number VARCHAR(20) NOT NULL UNIQUE); makes tracking_number NOT NULL, disallowing NULLs. CREATE TABLE orders (order_id INT, tracking_number VARCHAR(20) UNIQUE PRIMARY KEY); has invalid syntax combining UNIQUE and PRIMARY KEY on tracking_number.

4. Final Answer:

   CREATE TABLE orders (order_id INT PRIMARY KEY, tracking_number VARCHAR(20) UNIQUE); -> Option D

5. Quick Check:

   PRIMARY KEY unique + NOT NULL, UNIQUE allows NULL [OK]

Hint: PRIMARY KEY = unique+not null; UNIQUE allows NULL [OK]

Common Mistakes:

• Making UNIQUE column NOT NULL when NULLs allowed
• Assigning PRIMARY KEY to wrong column
• Combining UNIQUE and PRIMARY KEY on same column incorrectly