Row-level security policies in PostgreSQL - Time & Space Complexity

Time Complexity: Row-level security policies

O(n)

Understanding Time Complexity

When using row-level security policies, the database checks each row to decide if it should be visible or not.

We want to understand how the time to run a query changes as the number of rows grows.

Scenario Under Consideration

Analyze the time complexity of the following policy and query.

CREATE POLICY user_policy ON orders
  FOR SELECT
  USING (user_id = current_user);

SELECT * FROM orders;
    

This policy filters rows so each user sees only their own orders when running the SELECT query.

Identify Repeating Operations

Look at what repeats as the query runs.

• Primary operation: Checking the policy condition on each row.
• How many times: Once for every row in the orders table.

How Execution Grows With Input

As the number of rows increases, the database must check more rows against the policy.

Input Size (n)	Approx. Operations
10	10 policy checks
100	100 policy checks
1000	1000 policy checks

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

Final Time Complexity

Time Complexity: O(n)

This means the time to apply the policy grows in a straight line as the number of rows grows.

Common Mistake

[X] Wrong: "The policy is applied once, so it doesn't matter how many rows there are."

[OK] Correct: The policy condition is checked for each row to decide if it should be included, so more rows mean more checks.

Interview Connect

Understanding how row-level security affects query time helps you explain how databases keep data safe without slowing down too much.

Self-Check

"What if the policy condition used a complex subquery instead of a simple user ID check? How would the time complexity change?"