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?