String aggregation with STRING_AGG in PostgreSQL - Time & Space Complexity

Time Complexity: String aggregation with STRING_AGG

O(n log n)

Understanding Time Complexity

When we combine many text values into one string using STRING_AGG, it takes some time to do this work.

We want to understand how the time needed grows as we add more text values.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT department_id, STRING_AGG(employee_name, ', ' ORDER BY employee_name) AS employees
FROM employees
GROUP BY department_id;
    

This query groups employees by their department and joins their names into one string per department.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each employee record and concatenating their names per group.
• How many times: Once for each employee in the table, grouped by department.

How Execution Grows With Input

As the number of employees grows, the work to combine their names grows roughly in proportion.

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

Pattern observation: The time grows roughly in a straight line as more names are combined.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to combine strings grows proportionally to n log n due to the ORDER BY sorting inside STRING_AGG.

Common Mistake

[X] Wrong: "STRING_AGG runs instantly no matter how many rows there are."

[OK] Correct: Each name must be read and added to the result, so more rows mean more work and more time.

Interview Connect

Understanding how aggregation functions like STRING_AGG scale helps you explain query performance clearly and confidently.

Self-Check

"What if we added an ORDER BY inside STRING_AGG? How would that affect the time complexity?"

Practice

1. What does the STRING_AGG function do in PostgreSQL?

easy

A. It combines multiple text values into one string with a separator.

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

C. It sorts rows based on a column.

D. It deletes duplicate rows from a table.

Solution

1. Step 1: Understand STRING_AGG purpose

   STRING_AGG is used to join multiple text values into a single string with a separator.

2. Step 2: Compare with other options

   Counting rows, sorting, or deleting duplicates are different functions, not STRING_AGG.

3. Final Answer:

   It combines multiple text values into one string with a separator. -> Option A

4. Quick Check:

   STRING_AGG joins text values = It combines multiple text values into one string with a separator. [OK]

Hint: Remember: STRING_AGG joins strings with a separator [OK]

Common Mistakes:

• Confusing STRING_AGG with COUNT or ORDER BY
• Thinking STRING_AGG sorts rows
• Assuming STRING_AGG removes duplicates

2. Which of the following is the correct syntax to aggregate names separated by commas using STRING_AGG in PostgreSQL?

easy

A. SELECT STRING_AGG(name, ',') FROM users ORDER BY name;

B. SELECT STRING_AGG(name) FROM users;

C. SELECT STRING_AGG(name, ',') ORDER BY name FROM users;

D. SELECT STRING_AGG(name, ',') FROM users;

Solution

1. Step 1: Check basic STRING_AGG syntax

   STRING_AGG requires two arguments: the column and the separator, e.g., STRING_AGG(name, ',').

2. Step 2: Validate query structure

   ORDER BY inside STRING_AGG needs to be inside parentheses, not outside. SELECT STRING_AGG(name, ',') FROM users; is correct syntax without ordering.

3. Final Answer:

   SELECT STRING_AGG(name, ',') FROM users; -> Option D

4. Quick Check:

   Correct STRING_AGG syntax = SELECT STRING_AGG(name, ',') FROM users; [OK]

Hint: STRING_AGG needs column and separator inside parentheses [OK]

Common Mistakes:

• Omitting separator argument
• Placing ORDER BY outside STRING_AGG
• Using STRING_AGG without parentheses

3. Given the table fruits with rows: ('apple'), ('banana'), ('cherry'), what is the result of this query?

SELECT STRING_AGG(name, '; ' ORDER BY name) FROM fruits;

medium

A. 'apple; banana; cherry'

B. 'banana; apple; cherry'

C. 'cherry; banana; apple'

D. 'apple, banana, cherry'

Solution

1. Step 1: Understand ORDER BY inside STRING_AGG

   The query orders names alphabetically: apple, banana, cherry.

2. Step 2: Check separator and output

   Separator is '; ', so the result joins names with '; ' in order.

3. Final Answer:

   'apple; banana; cherry' -> Option A

4. Quick Check:

   Ordered join with '; ' separator = 'apple; banana; cherry' [OK]

Hint: ORDER BY inside STRING_AGG sorts before joining [OK]

Common Mistakes:

• Ignoring ORDER BY inside STRING_AGG
• Using wrong separator
• Assuming default comma separator

4. Identify the error in this query:

SELECT STRING_AGG(name, ', ' ORDER BY name) FROM users ORDER BY name;

medium

A. ORDER BY cannot be used inside STRING_AGG.

B. The query is correct and will run without errors.

C. ORDER BY must be inside STRING_AGG parentheses, not outside.

D. ORDER BY inside STRING_AGG must come after separator argument.

Solution

1. Step 1: Check ORDER BY usage inside STRING_AGG

   ORDER BY inside STRING_AGG after the separator is valid syntax.

2. Step 2: Check outer ORDER BY

   Without GROUP BY, the outer ORDER BY name causes an error because 'name' must appear in GROUP BY or be used in an aggregate function.

3. Final Answer:

   ORDER BY must be inside STRING_AGG parentheses, not outside. -> Option C

4. Quick Check:

   Outer ORDER BY invalid without GROUP BY = ORDER BY must be inside STRING_AGG parentheses, not outside. [OK]

Hint: ORDER BY inside STRING_AGG works; outside requires GROUP BY in aggregate queries [OK]

Common Mistakes:

• Thinking ORDER BY inside STRING_AGG is invalid
• Confusing outer ORDER BY with inner
• Misplacing ORDER BY arguments

5. You have a table orders with columns customer_id and product. How do you write a query to list each customer with a semicolon-separated list of their products sorted alphabetically?

hard

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

B. SELECT customer_id, STRING_AGG(product, '; ' ORDER BY product) FROM orders GROUP BY customer_id;

C. SELECT customer_id, STRING_AGG(product ORDER BY product, '; ') FROM orders GROUP BY customer_id;

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

Solution

1. Step 1: Group by customer_id

   We need to group rows by customer_id to aggregate products per customer.

2. Step 2: Use STRING_AGG with ORDER BY inside

   STRING_AGG(product, '; ' ORDER BY product) joins products with '; ' separator sorted alphabetically.

3. Step 3: Validate options

   SELECT customer_id, STRING_AGG(product, '; ' ORDER BY product) FROM orders GROUP BY customer_id; correctly uses GROUP BY and STRING_AGG with ORDER BY inside parentheses.

4. Final Answer:

   SELECT customer_id, STRING_AGG(product, '; ' ORDER BY product) FROM orders GROUP BY customer_id; -> Option B

5. Quick Check:

   Group by customer and ordered STRING_AGG = SELECT customer_id, STRING_AGG(product, '; ' ORDER BY product) FROM orders GROUP BY customer_id; [OK]

Hint: Put ORDER BY inside STRING_AGG parentheses for sorting [OK]

Common Mistakes:

• Placing ORDER BY outside STRING_AGG
• Omitting GROUP BY when aggregating
• Swapping arguments inside STRING_AGG