Time Complexity: JSONB containment (@>) operator
O(n * m)
0
0
JSONB containment (@>) operator in PostgreSQL - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time it takes to check if one JSONB value contains another grows as the data size increases.
Specifically, how does the JSONB containment operator (@>) behave when the JSON data gets bigger?
Scenario Under Consideration
Analyze the time complexity of the following PostgreSQL query using the JSONB containment operator.
SELECT *
FROM products
WHERE attributes @> '{"color": "red"}';
This query finds all products whose JSONB column attributes contains the key-value pair color: red.
Identify Repeating Operations
Look for repeated work inside the query execution.
- Primary operation: For each row, the database checks if the JSONB data contains the given JSON structure.
- How many times: This check happens once per row scanned in the table.
How Execution Grows With Input
As the number of rows grows, the database must do more containment checks.
| Input Size (n rows) | Approx. Operations |
|---|---|
| 10 | 10 containment checks |
| 100 | 100 containment checks |
| 1000 | 1000 containment checks |
Pattern observation: The number of containment checks grows directly with the number of rows scanned.
Final Time Complexity
Time Complexity: O(n * m)
This means the time to run the query grows linearly with the number of rows checked and the size of the JSONB data per row.
Common Mistake
[X] Wrong: "The JSONB containment operator runs in constant time no matter how big the data is."
[OK] Correct: The operator must look inside each JSONB value, so the time depends on how many rows and the size of JSON data it checks.
Interview Connect
Understanding how JSONB containment scales helps you write efficient queries and explain performance in real projects.
Self-Check
What if we add a GIN index on the JSONB column? How would the time complexity change?