Functions returning TABLE in PostgreSQL - Time & Space Complexity

Time Complexity: Functions returning TABLE

O(n)

Understanding Time Complexity

When using functions that return tables in PostgreSQL, it's important to understand how the time to get results grows as the data grows.

We want to know how the function's execution time changes when the input or data size increases.

Scenario Under Consideration

Analyze the time complexity of the following PostgreSQL function that returns a table.

CREATE FUNCTION get_active_users(min_age INT)
RETURNS TABLE(user_id INT, user_name TEXT) AS $$
BEGIN
  RETURN QUERY
  SELECT id, name FROM users WHERE age >= min_age AND active = TRUE;
END;
$$ LANGUAGE plpgsql;

This function returns all active users who are at least a certain age.

Identify Repeating Operations

Look for repeated actions inside the function.

• Primary operation: Scanning the users table to find matching rows.
• How many times: Once per function call, but the scan checks each row in the users table.

How Execution Grows With Input

The function checks each user to see if they meet the age and active conditions.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The number of checks grows roughly in direct proportion to the number of users.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the function grows linearly with the number of users in the table.

Common Mistake

[X] Wrong: "The function runs instantly no matter how many users there are because it's just a function."

[OK] Correct: The function still has to look at each user to check conditions, so more users mean more work and more time.

Interview Connect

Understanding how functions that return tables scale helps you explain performance in real projects and shows you can think about data size effects clearly.

Self-Check

"What if the function used an index on the age column? How would the time complexity change?"