Composite types in PostgreSQL - Time & Space Complexity

Time Complexity: Composite types

O(n)

Understanding Time Complexity

When working with composite types in PostgreSQL, it's important to understand how the time to process data grows as the amount of data increases.

We want to know how the execution time changes when we access or manipulate composite type data.

Scenario Under Consideration

Analyze the time complexity of the following PostgreSQL query using composite types.

CREATE TYPE address AS (
  street TEXT,
  city TEXT,
  zip_code TEXT
);

SELECT (a).city
FROM (SELECT ROW('123 Main St', 'Springfield', '12345')::address AS a) sub;
    

This code defines a composite type and selects a field from a composite value.

Identify Repeating Operations

Look for repeated actions that affect performance.

• Primary operation: Accessing a field from a composite type value.
• How many times: Once per row returned by the query.

How Execution Grows With Input

As the number of rows increases, the database must access the composite field for each row.

Input Size (n)	Approx. Operations
10	10 field accesses
100	100 field accesses
1000	1000 field accesses

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

Final Time Complexity

Time Complexity: O(n)

This means the time to access composite fields grows linearly with the number of rows processed.

Common Mistake

[X] Wrong: "Accessing a field inside a composite type is a constant time operation regardless of the number of rows."

[OK] Correct: While accessing one field is quick, doing it for many rows means the total time grows with the number of rows.

Interview Connect

Understanding how composite types affect query time helps you explain data access costs clearly and shows you can reason about database performance.

Self-Check

"What if we nested composite types inside each other? How would that affect the time complexity when accessing a deeply nested field?"