Array data type in PostgreSQL - Time & Space Complexity

Time Complexity: Array data type

O(n)

Understanding Time Complexity

When working with arrays in PostgreSQL, it's important to understand how the time to process them grows as the array gets bigger.

We want to know how the number of operations changes when we access or manipulate array elements.

Scenario Under Consideration

Analyze the time complexity of the following PostgreSQL query using array functions.

SELECT unnest(numbers) AS num
FROM (VALUES (ARRAY[1,2,3,4,5])) AS t(numbers);
    

This query takes an array of numbers and expands it into individual rows, one for each element.

Identify Repeating Operations

Look for repeated actions in the query.

• Primary operation: The unnest function processes each element of the array one by one.
• How many times: It runs once for every element in the array.

How Execution Grows With Input

As the array gets bigger, the work grows in a simple way.

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

Pattern observation: The number of operations grows directly with the number of elements.

Final Time Complexity

Time Complexity: O(n)

This means the time to process the array grows in a straight line with the number of elements.

Common Mistake

[X] Wrong: "Accessing any element in a PostgreSQL array is always instant, no matter the size."

[OK] Correct: While accessing a single element by index is fast, operations like unnest or searching go through each element, so time grows with array size.

Interview Connect

Understanding how array operations scale helps you explain query performance clearly and shows you know how data size affects work done.

Self-Check

"What if we changed unnest to a function that searches for a value in the array? How would the time complexity change?"

Practice

1. What is the correct way to declare an integer array column named scores in a PostgreSQL table?

easy

A. scores integer[]

B. scores array(integer)

C. scores [integer]

D. scores int array

Solution

1. Step 1: Understand PostgreSQL array syntax

   PostgreSQL uses type[] to declare an array column, for example integer[].

2. Step 2: Match the syntax to the options

   Only scores integer[] uses the correct syntax scores integer[].

3. Final Answer:

   scores integer[] -> Option A

4. Quick Check:

   Array declaration = type[] [OK]

Hint: Use type[] to declare arrays in PostgreSQL [OK]

Common Mistakes:

• Using parentheses instead of square brackets
• Writing 'array(integer)' which is invalid syntax
• Trying to put brackets before the type

2. Which of the following is the correct syntax to insert an array of integers {10, 20, 30} into a column numbers in PostgreSQL?

easy

A. INSERT INTO table_name (numbers) VALUES ('{10,20,30}');

B. INSERT INTO table_name (numbers) VALUES (ARRAY(10, 20, 30));

C. INSERT INTO table_name (numbers) VALUES ([10, 20, 30]);

D. INSERT INTO table_name (numbers) VALUES (10, 20, 30);

Solution

1. Step 1: Know how to insert arrays in PostgreSQL

   Arrays are inserted as string literals with curly braces, like '{10,20,30}'.

2. Step 2: Check each option

   INSERT INTO table_name (numbers) VALUES ('{10,20,30}'); uses the correct string literal format. INSERT INTO table_name (numbers) VALUES ([10, 20, 30]); uses square brackets which is invalid. INSERT INTO table_name (numbers) VALUES (ARRAY(10, 20, 30)); uses wrong ARRAY syntax (should be ARRAY[10,20,30]). INSERT INTO table_name (numbers) VALUES (10, 20, 30); inserts separate values, not an array.

3. Final Answer:

   INSERT INTO table_name (numbers) VALUES ('{10,20,30}'); -> Option A

4. Quick Check:

   Array insert = string with curly braces [OK]

Hint: Insert arrays as strings with curly braces '{...}' [OK]

Common Mistakes:

• Using square brackets instead of curly braces
• Using ARRAY() with parentheses instead of ARRAY[]
• Inserting multiple values without array syntax

3. Given a table students with a column grades integer[], what will the query SELECT grades[2] FROM students WHERE id = 1; return if the row with id = 1 has grades = {85, 90, 78}?

medium

A. 85

B. NULL

C. 90

D. 78

Solution

1. Step 1: Understand PostgreSQL array indexing

   PostgreSQL arrays start at index 1, so grades[2] accesses the second element.

2. Step 2: Identify the second element in the array

   The array is {85, 90, 78}, so the second element is 90.

3. Final Answer:

   90 -> Option C

4. Quick Check:

   Array index 2 = 90 [OK]

Hint: PostgreSQL arrays start at 1, not 0 [OK]

Common Mistakes:

• Assuming array index starts at 0
• Confusing element positions
• Expecting entire array instead of single element

4. Consider the query: SELECT numbers[0] FROM data_table; where numbers is an integer array column. What is the likely result?

medium

A. Returns the first element of the array

B. Returns NULL because PostgreSQL arrays start at index 1

C. Syntax error due to invalid index

D. Returns the entire array

Solution

1. Step 1: Recall PostgreSQL array indexing rules

   PostgreSQL arrays start at index 1, so index 0 is invalid but does not cause syntax error.

2. Step 2: Understand behavior of accessing index 0

   Accessing index 0 returns NULL, not an error or the first element.

3. Final Answer:

   Returns NULL because PostgreSQL arrays start at index 1 -> Option B

4. Quick Check:

   Index 0 access = NULL [OK]

Hint: Index 0 in PostgreSQL arrays returns NULL, not error [OK]

Common Mistakes:

• Expecting index 0 to return first element
• Thinking it causes syntax error
• Assuming it returns entire array

5. You have a table orders with a column item_ids integer[]. How would you write a query to find all orders that include the item ID 42 anywhere in the array?

hard

A. SELECT * FROM orders WHERE item_ids[42] IS NOT NULL;

B. SELECT * FROM orders WHERE item_ids[1] = 42;

C. SELECT * FROM orders WHERE ARRAY[42] @> item_ids;

D. SELECT * FROM orders WHERE 42 = ANY(item_ids);

Solution

1. Step 1: Understand how to check if an array contains a value

   PostgreSQL provides the ANY() operator to check if a value exists in an array.

2. Step 2: Analyze each option

   SELECT * FROM orders WHERE 42 = ANY(item_ids); correctly uses 42 = ANY(item_ids). SELECT * FROM orders WHERE item_ids[42] IS NOT NULL; incorrectly tries to access index 42. SELECT * FROM orders WHERE ARRAY[42] @> item_ids; uses @> which checks if array contains another array, but syntax is reversed (should be item_ids @> ARRAY[42]). SELECT * FROM orders WHERE item_ids[1] = 42; only checks first element.

3. Final Answer:

   SELECT * FROM orders WHERE 42 = ANY(item_ids); -> Option D

4. Quick Check:

   Use ANY() to check value in array [OK]

Hint: Use value = ANY(array) to check membership [OK]

Common Mistakes:

• Using wrong operator like @> with reversed operands
• Checking only first element instead of whole array
• Trying to access array at index equal to value