Practical window function patterns in PostgreSQL - Time & Space Complexity

Time Complexity: Practical window function patterns

O(n log n)

Understanding Time Complexity

When using window functions in PostgreSQL, it's important to understand how the time to run your query changes as your data grows.

We want to know how the query's work increases when the number of rows gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following window function query.

SELECT employee_id, department_id, salary,
       RANK() OVER (PARTITION BY department_id ORDER BY salary DESC) AS salary_rank
FROM employees;
    

This query ranks employees by salary within each department.

Identify Repeating Operations

Look for repeated work inside the query.

• Primary operation: Sorting rows within each department to assign ranks.
• How many times: Once per department, sorting all employees in that department.

How Execution Grows With Input

As the number of employees grows, the sorting work grows too.

Input Size (n)	Approx. Operations
10	About 10 log 10 (sorting 10 rows)
100	About 100 log 100 (sorting 100 rows)
1000	About 1000 log 1000 (sorting 1000 rows)

Pattern observation: The work grows a bit faster than the number of rows because sorting takes more effort as data grows.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to run the query grows a little faster than the number of rows because sorting is involved.

Common Mistake

[X] Wrong: "Window functions always run in linear time because they just add a column."

[OK] Correct: Window functions often require sorting or partitioning, which can take more time than just scanning rows.

Interview Connect

Understanding how window functions scale helps you write efficient queries and explain your reasoning clearly in real-world situations.

Self-Check

"What if we removed the PARTITION BY clause? How would the time complexity change?"