Role hierarchy in Snowflake - Time & Space Complexity

Time Complexity: Role hierarchy in Snowflake

O(n)

Understanding Time Complexity

We want to understand how the time to check permissions grows when roles are arranged in a hierarchy in Snowflake.

Specifically, how does the number of roles affect the time to find all permissions for a user?

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

-- Create roles
CREATE ROLE role1;
CREATE ROLE role2;
GRANT ROLE role1 TO ROLE role2;
GRANT ROLE role2 TO USER some_user;

-- Check all roles granted to a user
SHOW GRANTS TO USER some_user;

This sequence creates roles and grants one role to another, forming a hierarchy. Then it checks all roles granted to a user, including inherited roles.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Checking role grants recursively to find all inherited roles.
• How many times: Once per role in the hierarchy during permission resolution.

How Execution Grows With Input

As the number of roles in the hierarchy grows, the system checks each linked role to gather permissions.

Input Size (n)	Approx. API Calls/Operations
10	About 10 role checks
100	About 100 role checks
1000	About 1000 role checks

Pattern observation: The number of checks grows roughly in direct proportion to the number of roles linked in the hierarchy.

Final Time Complexity

Time Complexity: O(n)

This means the time to find all permissions grows linearly with the number of roles in the hierarchy.

Common Mistake

[X] Wrong: "Checking permissions is instant no matter how many roles exist."

[OK] Correct: Each role linked in the hierarchy must be checked, so more roles mean more work.

Interview Connect

Understanding how role hierarchies affect permission checks shows you can reason about system behavior as it scales, a key skill in cloud infrastructure.

Self-Check

"What if roles could have multiple parent roles instead of just one? How would the time complexity change?"