Functions returning SETOF in PostgreSQL - Time & Space Complexity

Time Complexity: Functions returning SETOF

O(n)

Understanding Time Complexity

When a function returns multiple rows, it processes each row one by one. We want to understand how the time it takes grows as the number of rows grows.

How does the function's work increase when it returns more rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

CREATE FUNCTION get_active_users()
RETURNS SETOF users AS $$
BEGIN
  RETURN QUERY
  SELECT * FROM users WHERE active = true;
END;
$$ LANGUAGE plpgsql;

This function returns all active users from the users table one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the users table rows that match the condition.
• How many times: Once for each active user row returned.

How Execution Grows With Input

As the number of active users grows, the function processes more rows.

Input Size (n)	Approx. Operations
10	About 10 row reads and returns
100	About 100 row reads and returns
1000	About 1000 row reads and returns

Pattern observation: The work grows roughly in direct proportion to the number of rows returned.

Final Time Complexity

Time Complexity: O(n)

This means the time grows linearly with the number of rows the function returns.

Common Mistake

[X] Wrong: "The function runs in constant time no matter how many rows it returns."

[OK] Correct: Because the function must process and return each row, the time increases as more rows are returned.

Interview Connect

Understanding how functions that return multiple rows scale helps you explain performance in real database tasks. It shows you can think about how data size affects work done.

Self-Check

"What if the function used a LIMIT clause to return only a fixed number of rows? How would the time complexity change?"