Column-level permissions in PostgreSQL - Time & Space Complexity

Time Complexity: Column-level permissions

O(n)

Understanding Time Complexity

When checking column-level permissions in a database, we want to know how the time to verify access grows as the number of columns or users increases.

We ask: How does permission checking scale when more columns or users are involved?

Scenario Under Consideration

Analyze the time complexity of this permission check query.

-- Check if user has access to a specific column
SELECT has_column_privilege('username', 'table_name', 'column_name', 'SELECT');

-- Or check permissions for multiple columns
SELECT column_name
FROM information_schema.columns
WHERE table_name = 'table_name'
  AND has_column_privilege('username', 'table_name', column_name, 'SELECT');
    

This code checks if a user can select specific columns in a table, either one column or multiple columns.

Identify Repeating Operations

Look for repeated checks or loops.

• Primary operation: Checking permission for each column.
• How many times: Once per column when checking multiple columns.

How Execution Grows With Input

As the number of columns grows, the permission check runs once per column.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to check permissions grows linearly with the number of columns checked.

Common Mistake

[X] Wrong: "Checking permissions for multiple columns is done all at once, so time stays the same no matter how many columns there are."

[OK] Correct: Each column's permission is checked separately, so more columns mean more checks and more time.

Interview Connect

Understanding how permission checks scale helps you design efficient security in databases and shows you can think about performance in real systems.

Self-Check

"What if we cached permission results for columns? How would that change the time complexity when checking permissions repeatedly?"