Array aggregation with ARRAY_AGG in PostgreSQL - Time & Space Complexity

Time Complexity: Array aggregation with ARRAY_AGG

O(n)

Understanding Time Complexity

When using ARRAY_AGG in PostgreSQL, we want to understand how the time to build the array grows as the number of rows increases.

We ask: How does the work change when we aggregate more rows into an array?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT department_id, ARRAY_AGG(employee_name) AS employees
FROM employees
GROUP BY department_id;
    

This query groups employees by their department and collects all employee names into an array for each department.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each employee row once to add their name to the array.
• How many times: Once per employee row, so the number of times equals the total number of employees.

How Execution Grows With Input

As the number of employees grows, the work to add each name to the array grows linearly.

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

Pattern observation: The work grows directly with the number of rows aggregated.

Final Time Complexity

Time Complexity: O(n)

This means the time to build the array grows in a straight line as more rows are added.

Common Mistake

[X] Wrong: "ARRAY_AGG runs in constant time no matter how many rows there are."

[OK] Correct: Each row must be processed and added to the array, so more rows mean more work.

Interview Connect

Understanding how aggregation functions scale helps you explain query performance clearly and shows you know how databases handle data growth.

Self-Check

"What if we used ARRAY_AGG with a WHERE clause filtering half the rows? How would the time complexity change?"

Practice

1. What does the PostgreSQL function ARRAY_AGG do?

easy

A. It counts the number of rows in a table.

B. It collects multiple row values into a single array.

C. It sorts rows in ascending order.

D. It deletes duplicate rows from a table.

Solution

1. Step 1: Understand the purpose of ARRAY_AGG

   ARRAY_AGG is used to gather multiple values from rows into one array value.

2. Step 2: Compare with other options

   Counting rows uses COUNT(), deleting duplicates or sorting rows uses other clauses like DISTINCT or ORDER BY, not ARRAY_AGG.

3. Final Answer:

   It collects multiple row values into a single array. -> Option B

4. Quick Check:

   ARRAY_AGG = collects rows into array [OK]

Hint: ARRAY_AGG groups rows into one array [OK]

Common Mistakes:

• Confusing ARRAY_AGG with COUNT or ORDER BY
• Thinking ARRAY_AGG sorts data by default
• Assuming ARRAY_AGG removes duplicates automatically

2. Which of the following is the correct syntax to aggregate values into an array using ARRAY_AGG in PostgreSQL?

easy

A. SELECT ARRAY_AGG(column_name) FROM table_name;

B. SELECT ARRAY_AGG column_name FROM table_name;

C. SELECT ARRAY_AGG(column_name) table_name;

D. SELECT ARRAY_AGG(column_name) FROM table_name WHERE;

Solution

1. Step 1: Recall correct function call syntax

   ARRAY_AGG requires parentheses around the column name and a FROM clause.

2. Step 2: Check each option

   SELECT ARRAY_AGG(column_name) FROM table_name; uses correct syntax with parentheses and FROM clause; others miss parentheses or have syntax errors.

3. Final Answer:

   SELECT ARRAY_AGG(column_name) FROM table_name; -> Option A

4. Quick Check:

   Correct ARRAY_AGG syntax uses parentheses and FROM [OK]

Hint: Always use parentheses with ARRAY_AGG(column) [OK]

Common Mistakes:

• Omitting parentheses around column_name
• Leaving incomplete WHERE clause
• Missing FROM keyword

3. Given the table students with columns class and name, what is the output of this query?

SELECT class, ARRAY_AGG(name ORDER BY name) FROM students GROUP BY class ORDER BY class;

medium

A. [{class: '1A', array_agg: ['Alice']}, {class: '2B', array_agg: ['Charlie', 'David', 'Bob']}]

B. [{class: '1A', array_agg: ['Bob', 'Alice']}, {class: '2B', array_agg: ['David', 'Charlie']}]

C. [{class: '1A', array_agg: ['Alice', 'Charlie']}, {class: '2B', array_agg: ['Bob', 'David']}]

D. [{class: '1A', array_agg: ['Alice', 'Bob']}, {class: '2B', array_agg: ['Charlie', 'David']}]

Solution

1. Step 1: Understand GROUP BY and ARRAY_AGG with ORDER BY

   The query groups rows by class and collects names into arrays sorted alphabetically.

2. Step 2: Analyze the ordering inside ARRAY_AGG

   Names inside each class array are sorted ascending, so 'Alice' comes before 'Bob' in '1A', and 'Charlie' before 'David' in '2B'.

3. Final Answer:

   [{class: '1A', array_agg: ['Alice', 'Bob']}, {class: '2B', array_agg: ['Charlie', 'David']}] -> Option D

4. Quick Check:

   ARRAY_AGG with ORDER BY sorts array elements [OK]

Hint: ARRAY_AGG(... ORDER BY ...) sorts array elements [OK]

Common Mistakes:

• Ignoring ORDER BY inside ARRAY_AGG
• Mixing names between groups
• Assuming ARRAY_AGG sorts groups, not elements

4. Identify the error in this query:

SELECT class, ARRAY_AGG(name ORDER BY) FROM students GROUP BY class;

medium

A. Missing column name after ORDER BY inside ARRAY_AGG.

B. GROUP BY clause is not allowed with ARRAY_AGG.

C. ARRAY_AGG cannot be used with ORDER BY.

D. Missing FROM keyword before table name.

Solution

1. Step 1: Check syntax of ORDER BY inside ARRAY_AGG

   ORDER BY inside ARRAY_AGG requires a column name to specify sorting order.

2. Step 2: Validate other parts of the query

   GROUP BY is valid with ARRAY_AGG; FROM clause is present; ORDER BY without column is invalid.

3. Final Answer:

   Missing column name after ORDER BY inside ARRAY_AGG. -> Option A

4. Quick Check:

   ORDER BY needs a column name inside ARRAY_AGG [OK]

Hint: ORDER BY inside ARRAY_AGG needs a column name [OK]

Common Mistakes:

• Leaving ORDER BY empty inside ARRAY_AGG
• Thinking GROUP BY disallows ARRAY_AGG
• Forgetting to specify sorting column

5. You have a table orders with columns customer_id and product. You want to create a query that returns each customer_id with an array of unique products they ordered, sorted alphabetically. Which query achieves this?

hard

A. SELECT customer_id, ARRAY_AGG(product ORDER BY product) FROM orders GROUP BY customer_id;

B. SELECT customer_id, ARRAY_AGG(DISTINCT product) FROM orders GROUP BY customer_id ORDER BY product;

C. SELECT customer_id, ARRAY_AGG(DISTINCT product ORDER BY product) FROM orders GROUP BY customer_id;

D. SELECT customer_id, ARRAY_AGG(product) FROM orders ORDER BY customer_id;

Solution

1. Step 1: Use ARRAY_AGG with DISTINCT and ORDER BY

   To get unique products sorted, use ARRAY_AGG(DISTINCT product ORDER BY product).

2. Step 2: Group by customer_id to aggregate per customer

   GROUP BY customer_id ensures aggregation per customer; ORDER BY inside ARRAY_AGG sorts products alphabetically.

3. Final Answer:

   SELECT customer_id, ARRAY_AGG(DISTINCT product ORDER BY product) FROM orders GROUP BY customer_id; -> Option C

4. Quick Check:

   Use DISTINCT inside ARRAY_AGG with ORDER BY for unique sorted arrays [OK]

Hint: Use DISTINCT inside ARRAY_AGG with ORDER BY for unique sorted arrays [OK]

Common Mistakes:

• Omitting DISTINCT causes duplicates in array
• Placing ORDER BY outside ARRAY_AGG affects rows, not array elements
• Not grouping by customer_id