PRIMARY KEY constraint in SQL - Time & Space Complexity

Time Complexity: PRIMARY KEY constraint

O(log n)

Understanding Time Complexity

When we use a PRIMARY KEY constraint in a database table, it helps keep data unique and easy to find.

We want to understand how the time to check or find a primary key changes as the table grows.

Scenario Under Consideration

Analyze the time complexity of inserting and searching rows with a PRIMARY KEY constraint.

CREATE TABLE Employees (
  EmployeeID INT PRIMARY KEY,
  Name VARCHAR(100),
  Department VARCHAR(50)
);

INSERT INTO Employees (EmployeeID, Name, Department) VALUES (1, 'Alice', 'HR');
SELECT * FROM Employees WHERE EmployeeID = 1;
    

This code creates a table with a PRIMARY KEY on EmployeeID, inserts a row, and searches by that key.

Identify Repeating Operations

When inserting or searching, the database checks the PRIMARY KEY to keep values unique and find rows fast.

• Primary operation: Searching or checking the PRIMARY KEY index.
• How many times: Depends on the number of rows, but the index helps avoid scanning all rows.

How Execution Grows With Input

As the table grows, the database uses the PRIMARY KEY index to quickly find or check keys without looking at every row.

Input Size (n)	Approx. Operations
10	About 3-4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: The steps grow slowly even as the table gets much bigger, thanks to the index.

Final Time Complexity

Time Complexity: O(log n)

This means finding or checking a primary key takes a small number of steps that grow slowly as the table gets bigger.

Common Mistake

[X] Wrong: "Searching by PRIMARY KEY scans every row, so it takes longer as the table grows linearly."

[OK] Correct: The PRIMARY KEY uses an index (like a tree) that lets the database jump quickly to the right spot without checking every row.

Interview Connect

Understanding how PRIMARY KEY constraints speed up data access shows you know how databases keep things efficient as data grows.

Self-Check

"What if the PRIMARY KEY was not indexed? How would the time complexity for searching change?"

Practice

1. What is the main purpose of a PRIMARY KEY in a database table?

easy

A. To speed up database backups

B. To uniquely identify each row and prevent null values

C. To store large text data

D. To allow duplicate values in a column

Solution

1. Step 1: Understand the role of PRIMARY KEY

   A PRIMARY KEY uniquely identifies each row and does not allow nulls, ensuring data integrity.

2. Step 2: Compare options with PRIMARY KEY purpose

   Options A, B, and C do not describe uniqueness or null restriction, which are key features of PRIMARY KEY.

3. Final Answer:

   To uniquely identify each row and prevent null values -> Option B

4. Quick Check:

   PRIMARY KEY = unique + not null [OK]

Hint: PRIMARY KEY means unique and no nulls [OK]

Common Mistakes:

• Thinking PRIMARY KEY allows duplicates
• Confusing PRIMARY KEY with foreign key
• Assuming PRIMARY KEY stores large text

2. Which of the following is the correct syntax to define a PRIMARY KEY on the id column during table creation?

easy

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

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

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

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

Solution

1. Step 1: Review correct PRIMARY KEY syntax inline

   PRIMARY KEY is declared after the column type, like id INT PRIMARY KEY.

2. Step 2: Check each option's syntax

   CREATE TABLE users (id INT PRIMARY KEY, name VARCHAR(50)); correctly places PRIMARY KEY after id INT. Options B, C, and D have syntax errors or misplaced keywords.

3. Final Answer:

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

4. Quick Check:

   PRIMARY KEY follows column type inline [OK]

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

Common Mistakes:

• Placing PRIMARY KEY after wrong column
• Using PRIMARY KEY without parentheses for multiple columns
• Syntax errors with misplaced keywords

3. Given the table creation:

CREATE TABLE orders (
  order_id INT,
  product_id INT,
  PRIMARY KEY (order_id, product_id)
);

What will happen if you try to insert two rows with the same order_id but different product_id?

medium

A. Only the second row will be inserted

B. Only the first row will be inserted; second causes error

C. Both rows cause a syntax error

D. Both rows will be inserted successfully

Solution

1. Step 1: Understand composite PRIMARY KEY behavior

   The PRIMARY KEY is on both order_id and product_id together, so uniqueness is checked on the pair.

2. Step 2: Analyze insertion of rows with same order_id but different product_id

   Since product_id differs, the pair is unique, so both rows can be inserted without error.

3. Final Answer:

   Both rows will be inserted successfully -> Option D

4. Quick Check:

   Composite PRIMARY KEY = unique pairs [OK]

Hint: Composite key means unique pairs, not single columns [OK]

Common Mistakes:

• Assuming order_id alone must be unique
• Thinking composite key allows duplicates in all columns
• Confusing syntax error with constraint violation

4. Consider this table creation:

CREATE TABLE employees (
  emp_id INT,
  email VARCHAR(100),
  PRIMARY KEY emp_id
);

What is wrong with this statement?

medium

A. PRIMARY KEY must be declared with parentheses around column name

B. PRIMARY KEY cannot be on emp_id column

C. email column must be PRIMARY KEY instead

D. Table cannot have a PRIMARY KEY

Solution

1. Step 1: Check syntax for table-level PRIMARY KEY

   When declaring PRIMARY KEY separately, column names must be inside parentheses, like PRIMARY KEY (emp_id).

2. Step 2: Identify error in given statement

   The statement misses parentheses around emp_id, causing syntax error.

3. Final Answer:

   PRIMARY KEY must be declared with parentheses around column name -> Option A

4. Quick Check:

   Table-level PRIMARY KEY needs parentheses [OK]

Hint: Table-level PRIMARY KEY needs parentheses [OK]

Common Mistakes:

• Omitting parentheses in table-level PRIMARY KEY
• Thinking PRIMARY KEY can't be on emp_id
• Confusing column-level and table-level syntax

5. You want to create a table students where each student is uniquely identified by a combination of student_id and campus_id. Which of the following statements correctly enforces this using a PRIMARY KEY?

hard

A. CREATE TABLE students (student_id INT PRIMARY KEY, campus_id INT PRIMARY KEY);

B. CREATE TABLE students (student_id INT, campus_id INT, PRIMARY KEY student_id, campus_id);

C. CREATE TABLE students (student_id INT, campus_id INT, PRIMARY KEY (student_id, campus_id));

D. CREATE TABLE students (student_id INT, campus_id INT, UNIQUE (student_id, campus_id));

Solution

1. Step 1: Understand composite PRIMARY KEY requirement

   To uniquely identify rows by two columns, a composite PRIMARY KEY on both columns is needed.

2. Step 2: Evaluate each option's correctness

   CREATE TABLE students (student_id INT, campus_id INT, PRIMARY KEY (student_id, campus_id)); correctly defines a composite PRIMARY KEY. CREATE TABLE students (student_id INT PRIMARY KEY, campus_id INT PRIMARY KEY); tries to assign two PRIMARY KEYs, which is invalid. CREATE TABLE students (student_id INT, campus_id INT, PRIMARY KEY student_id, campus_id); has syntax errors. CREATE TABLE students (student_id INT, campus_id INT, UNIQUE (student_id, campus_id)); uses UNIQUE but not PRIMARY KEY.

3. Final Answer:

   CREATE TABLE students (student_id INT, campus_id INT, PRIMARY KEY (student_id, campus_id)); -> Option C

4. Quick Check:

   Composite PRIMARY KEY uses parentheses around columns [OK]

Hint: Use parentheses for composite PRIMARY KEY columns [OK]

Common Mistakes:

• Trying multiple PRIMARY KEYs on separate columns
• Missing parentheses in PRIMARY KEY declaration
• Using UNIQUE instead of PRIMARY KEY for uniqueness