INSERT with RETURNING clause in PostgreSQL - Time & Space Complexity

Time Complexity: INSERT with RETURNING clause

O(n)

Understanding Time Complexity

When we add new rows to a database table using INSERT, it is helpful to know how the time to do this grows as we add more rows.

We want to understand how the database handles inserting data and returning results as the input size changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

INSERT INTO employees (name, department, salary)
VALUES ('Alice', 'Sales', 50000),
       ('Bob', 'HR', 45000),
       ('Carol', 'IT', 60000)
RETURNING id, name;
    

This code inserts three new employee records and returns their generated IDs and names.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting each row into the table and writing it to disk.
• How many times: Once for each row in the VALUES list (3 times here, but can be many more).

How Execution Grows With Input

As the number of rows to insert grows, the work grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 10 insert operations and 10 returned rows
100	About 100 insert operations and 100 returned rows
1000	About 1000 insert operations and 1000 returned rows

Pattern observation: The time grows linearly as you add more rows to insert and return.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert and return rows grows directly with the number of rows you add.

Common Mistake

[X] Wrong: "The RETURNING clause makes the insert take much longer regardless of how many rows are inserted."

[OK] Correct: Returning data adds some work, but it scales with the number of rows inserted, not independently. The main cost is still inserting each row.

Interview Connect

Understanding how inserting multiple rows and returning data scales helps you explain database performance clearly and confidently in real situations.

Self-Check

"What if we changed the INSERT to add rows one at a time inside a loop instead of all at once? How would the time complexity change?"