Time Complexity: RETURNING clause mental model
O(n)
0
0
RETURNING clause mental model in PostgreSQL - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time needed to run a query with a RETURNING clause changes as the data grows.
Specifically, how does adding RETURNING affect the work the database does?
Scenario Under Consideration
Analyze the time complexity of this PostgreSQL query using RETURNING.
INSERT INTO employees (name, department)
VALUES ('Alice', 'Sales'), ('Bob', 'HR'), ('Carol', 'IT')
RETURNING id, name;
This query inserts multiple rows and returns the new ids and names of those rows.
Identify Repeating Operations
Look for repeated work inside the query.
- Primary operation: Inserting each row one by one.
- How many times: Once per row inserted.
- Additional operation: Returning the requested columns for each inserted row.
- How many times: Also once per inserted row.
How Execution Grows With Input
As the number of rows inserted grows, the work grows too.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 inserts + 10 returns |
| 100 | About 100 inserts + 100 returns |
| 1000 | About 1000 inserts + 1000 returns |
Pattern observation: The total work grows roughly in direct proportion to the number of rows.
Final Time Complexity
Time Complexity: O(n)
This means the time to run the query grows linearly with the number of rows inserted and returned.
Common Mistake
[X] Wrong: "RETURNING just adds a tiny fixed cost, so it doesn't grow with more rows."
[OK] Correct: The database must return data for each row inserted, so the work grows with the number of rows, not fixed.
Interview Connect
Understanding how RETURNING affects query time helps you explain performance clearly and shows you know how databases handle data flow.
Self-Check
"What if we used RETURNING * to return all columns instead of just a few? How would the time complexity change?"