Serial and identity columns in PostgreSQL - Time & Space Complexity

Time Complexity: Serial and identity columns

O(n)

Understanding Time Complexity

When using serial or identity columns in PostgreSQL, it's important to understand how the database generates unique numbers as new rows are added.

We want to see how the time to get the next number grows as more rows are inserted.

Scenario Under Consideration

Analyze the time complexity of inserting rows with a serial or identity column.

CREATE TABLE users (
  id SERIAL PRIMARY KEY,
  name TEXT
);

INSERT INTO users (name) VALUES ('Alice');
INSERT INTO users (name) VALUES ('Bob');
-- More inserts follow

This code creates a table with a serial column that auto-generates unique IDs for each new row.

Identify Repeating Operations

Each insert operation requests the next number from a sequence.

• Primary operation: Fetching the next sequence value.
• How many times: Once per inserted row.

How Execution Grows With Input

Getting the next number from a sequence is a simple, direct operation that does not depend on how many rows exist.

Input Size (n)	Approx. Operations
10	10 sequence fetches
100	100 sequence fetches
1000	1000 sequence fetches

Pattern observation: Each insert does one sequence fetch, so the work grows linearly with the number of inserts.

Final Time Complexity

Time Complexity: O(n)

This means the total time grows directly in proportion to the number of rows inserted.

Common Mistake

[X] Wrong: "Fetching the next serial number gets slower as the table grows because it has to check all existing rows."

[OK] Correct: The sequence value is stored separately and does not scan the table, so fetching the next number stays fast regardless of table size.

Interview Connect

Understanding how sequences work helps you explain database behavior clearly and shows you know how auto-generated keys perform as data grows.

Self-Check

What if we replaced the serial column with a UUID generated on insert? How would the time complexity of generating unique IDs change?