Login vs group roles in PostgreSQL - Performance Comparison

Time Complexity: Login vs group roles

O(n)

Understanding Time Complexity

When checking user permissions in PostgreSQL, we often look at logins and group roles.

We want to understand how the time to verify permissions grows as the number of roles or groups increases.

Scenario Under Consideration

Analyze the time complexity of checking if a user belongs to a specific group role.

-- Check if user has the target_role directly
SELECT 1
FROM pg_auth_members m
JOIN pg_roles r ON m.roleid = r.oid
WHERE m.member = (SELECT oid FROM pg_roles WHERE rolname = 'username')
  AND r.rolname = 'target_role';
    

This query checks if 'username' is a direct member of 'target_role'.

Identify Repeating Operations

Look for repeated checks or loops in the query.

• Primary operation: Scanning membership links between users and roles.
• How many times: Once per membership record related to the user.

How Execution Grows With Input

As the number of group roles a user belongs to grows, the checks increase.

Input Size (number of roles/groups)	Approx. Operations
10	10 membership checks
100	100 membership checks
1000	1000 membership checks

Pattern observation: The number of checks grows linearly with the number of roles/groups.

Final Time Complexity

Time Complexity: O(n)

This means the time to check permissions grows in direct proportion to the number of roles or groups the user belongs to.

Common Mistake

[X] Wrong: "Checking group roles is instant and does not depend on how many groups a user has."

[OK] Correct: Each group membership must be checked, so more groups mean more work.

Interview Connect

Understanding how permission checks scale helps you design efficient access control in real systems.

Self-Check

"What if we cached group memberships for users? How would that change the time complexity?"