Named windows with WINDOW clause in PostgreSQL - Time & Space Complexity

Time Complexity: Named windows with WINDOW clause

O(n log n)

Understanding Time Complexity

We want to understand how the time to run a query changes when using named windows with the WINDOW clause in PostgreSQL.

Specifically, how does naming windows affect the work the database does as data grows?

Scenario Under Consideration

Analyze the time complexity of the following query using named windows.

SELECT employee_id, department_id, salary,
       AVG(salary) OVER dept_win AS avg_dept_salary,
       RANK() OVER dept_win AS rank_in_dept
FROM employees
WINDOW dept_win AS (PARTITION BY department_id ORDER BY salary DESC);
    

This query calculates the average salary and rank of employees within each department using a named window called dept_win.

Identify Repeating Operations

Look for repeated work inside the query.

• Primary operation: The database processes each department's employees separately (partition) and orders them by salary.
• How many times: Once per department, for all employees in that department.

How Execution Grows With Input

The work depends on how many employees there are and how they are grouped by department.

Input Size (n)	Approx. Operations
10 employees	About 10 operations, grouped by departments
100 employees	About 100 operations, grouped by departments
1000 employees	About 1000 operations, grouped by departments

Pattern observation: The total work grows roughly in direct proportion to the number of employees.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of employees because sorting is needed within each department.

Common Mistake

[X] Wrong: "Using a named window makes the query run faster because it avoids repeated work."

[OK] Correct: Naming a window just helps write the query cleaner; the database still does the sorting and partitioning once per window, so the main work stays the same.

Interview Connect

Understanding how window functions work with partitions and ordering helps you explain query performance clearly and shows you know how databases handle grouped calculations efficiently.

Self-Check

"What if we removed the ORDER BY clause inside the WINDOW definition? How would the time complexity change?"