Composite primary keys in SQL - Time & Space Complexity

Time Complexity: Composite primary keys

O(log n)

Understanding Time Complexity

When using composite primary keys in a database, it's important to understand how the time to find or insert data changes as the table grows.

We want to know how the database handles searching and maintaining these keys as more rows are added.

Scenario Under Consideration

Analyze the time complexity of this table definition and a query using a composite primary key.

CREATE TABLE Orders (
  OrderID INT,
  ProductID INT,
  Quantity INT,
  PRIMARY KEY (OrderID, ProductID)
);

SELECT * FROM Orders WHERE OrderID = 101 AND ProductID = 202;
    

This code creates a table with a composite primary key made of two columns and queries a row using both keys.

Identify Repeating Operations

Look at what the database does repeatedly when searching or inserting.

• Primary operation: Searching the index built on both OrderID and ProductID.
• How many times: The database traverses the index tree nodes, which depends on the number of rows.

How Execution Grows With Input

As the number of rows grows, the database index grows too, but it stays balanced.

Input Size (n)	Approx. Operations
10	About 3-4 steps to find a row
100	About 5-6 steps
1000	About 7-8 steps

Pattern observation: The number of steps grows slowly, even if the table gets much bigger.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find or insert a row grows slowly and predictably as the table gets bigger.

Common Mistake

[X] Wrong: "Using two columns as a primary key doubles the search time compared to one column."

[OK] Correct: The database uses a balanced index tree that handles multiple columns efficiently, so search time grows with the total number of rows, not the number of key columns.

Interview Connect

Understanding how composite keys affect search time shows you know how databases keep data organized and efficient, a useful skill in many real projects.

Self-Check

What if we added a third column to the composite primary key? How would the time complexity change?

Practice

1. What is a composite primary key in a database table?

easy

A. A primary key that uses only one column to identify rows.

B. A primary key made up of two or more columns combined to uniquely identify a row.

C. A key that allows duplicate values in the table.

D. A foreign key that references multiple tables.

Solution

1. Step 1: Understand primary key basics

   A primary key uniquely identifies each row in a table.

2. Step 2: Define composite primary key

   A composite primary key uses two or more columns together to ensure uniqueness.

3. Final Answer:

   A primary key made up of two or more columns combined to uniquely identify a row. -> Option B

4. Quick Check:

   Composite primary key = multiple columns [OK]

Hint: Composite keys combine columns to ensure unique rows [OK]

Common Mistakes:

• Thinking a primary key can have duplicates
• Confusing composite key with foreign key
• Assuming composite key uses only one column

2. Which of the following is the correct syntax to define a composite primary key on columns order_id and product_id in SQL?

easy

A. PRIMARY KEY (order_id, product_id)

B. PRIMARY KEY order_id, product_id

C. PRIMARY KEY order_id & product_id

D. PRIMARY KEY (order_id + product_id)

Solution

1. Step 1: Recall SQL syntax for composite keys

   Composite keys are defined by listing columns inside parentheses separated by commas.

2. Step 2: Match correct syntax

   PRIMARY KEY (order_id, product_id) uses parentheses and comma correctly: PRIMARY KEY (order_id, product_id).

3. Final Answer:

   PRIMARY KEY (order_id, product_id) -> Option A

4. Quick Check:

   Composite key syntax uses parentheses and commas [OK]

Hint: Use parentheses and commas for composite keys [OK]

Common Mistakes:

• Omitting parentheses around columns
• Using symbols like & or + incorrectly
• Listing columns without commas

3. Given the table OrderDetails with composite primary key (order_id, product_id), what will this query return?

SELECT * FROM OrderDetails WHERE order_id = 101;

medium

A. No rows because both keys must be specified.

B. Only one row with order_id 101 and any product_id.

C. An error because product_id is missing in WHERE clause.

D. All rows where order_id is 101, regardless of product_id.

Solution

1. Step 1: Understand composite key usage in queries

   Composite keys uniquely identify rows, but queries can filter by any column(s).

2. Step 2: Analyze the query filter

   The query filters only by order_id = 101, so it returns all rows with that order_id regardless of product_id.

3. Final Answer:

   All rows where order_id is 101, regardless of product_id. -> Option D

4. Quick Check:

   Filtering by part of composite key returns matching rows [OK]

Hint: Filtering by part of composite key returns matching rows [OK]

Common Mistakes:

• Assuming missing key column causes error
• Thinking only full composite key filters work
• Expecting only one row when multiple match

4. You try to create a table with this SQL:

CREATE TABLE Enrollment (
 student_id INT,
 course_id INT,
 PRIMARY KEY student_id, course_id
);

What is the problem?

medium

A. Missing parentheses around the composite key columns.

B. student_id and course_id cannot be primary keys.

C. PRIMARY KEY must be declared after all columns.

D. Composite keys require UNIQUE keyword instead.

Solution

1. Step 1: Check syntax for composite primary key

   Composite keys require parentheses around the column list in PRIMARY KEY declaration.

2. Step 2: Identify error in given SQL

   The statement uses PRIMARY KEY student_id, course_id without parentheses, causing syntax error.

3. Final Answer:

   Missing parentheses around the composite key columns. -> Option A

4. Quick Check:

   Composite keys need parentheses [OK]

Hint: Always use parentheses for composite primary keys [OK]

Common Mistakes:

• Omitting parentheses in PRIMARY KEY clause
• Confusing primary key with unique constraint
• Placing PRIMARY KEY before column definitions

5. You have a table Attendance with columns student_id, class_date, and session. You want to ensure each student can only have one attendance record per class date and session. Which composite primary key should you define?

hard

A. (class_date, session)

B. (student_id, class_date)

C. (student_id, class_date, session)

D. (student_id, session)

Solution

1. Step 1: Understand uniqueness requirement

   Each student must have only one record per class date and session, so all three columns combined must be unique.

2. Step 2: Choose composite key covering all uniqueness factors

   Composite key must include student_id, class_date, and session to enforce this rule.

3. Final Answer:

   (student_id, class_date, session) -> Option C

4. Quick Check:

   Composite key covers all uniqueness columns [OK]

Hint: Include all columns that define uniqueness in composite key [OK]

Common Mistakes:

• Leaving out session or class_date from key
• Using only two columns when three needed
• Confusing foreign keys with primary keys