SpiceDB query planning shows why authorization cost depends on data shape

At a glance

What this is: This is Authzed’s explanation of a new query planner for SpiceDB that uses graph shape statistics to choose lower-cost authorization paths.

Why it matters: It matters because teams running ReBAC, service-account-heavy systems, or agent-adjacent authorization can no longer treat permission latency as a purely infrastructure issue.

👉 Read Authzed's explanation of SpiceDB query planning for ReBAC performance

Context

ReBAC authorization gets slower when the system has to traverse large, uneven relationship graphs to answer a permission check. The primary problem here is not authorization logic itself, but the cost of exploring the wrong part of the graph first, which becomes more visible as relationship depth and fan-out grow.

For IAM practitioners, this is relevant wherever non-human identities, services, and delegated access create large authorization graphs. The article frames query planning as a way to use relationship statistics to reduce unnecessary work, which makes data shape part of the governance conversation rather than a backend tuning detail.

Key questions

Q: How should teams reduce latency in large ReBAC authorization graphs?

A: Teams should reduce latency by identifying the highest-cost relationship paths, then simplifying schemas, reordering evaluation, or using planners that choose the cheaper traversal first. The goal is to reduce graph work before adding infrastructure. For mature programmes, graph shape should be treated as a performance control, not only a modelling choice.

Q: Why do some permission checks get much slower as relationship depth grows?

A: Permission checks slow down when the engine must explore many possible paths through a deep or wide relationship graph before it can prove access or denial. Each additional layer expands the search space. In practice, the slowest checks are usually the ones where schema design creates large fan-out or expensive intersections.

Q: How do organizations know if authorization planning is actually working?

A: Organizations should look for lower traversal work, fewer expensive subgraph explorations, and reduced tail latency on permission checks that previously hit wide or deeply nested relationships. If the planner is effective, the system should spend less time evaluating paths that do not contribute to the final decision.

Q: When should teams simplify ReBAC policies instead of tuning infrastructure?

A: Teams should simplify policies when a small set of relationship patterns consistently drives the majority of authorization cost. If the problem is structural, more caching or database capacity will only mask it. Simplification is the better path when the schema itself creates repeated expensive traversals.

Technical breakdown

How ReBAC permission checks become graph traversals

SpiceDB evaluates permission checks by traversing relationships as a directed graph. A request such as resource, permission, subject can expand into arrows, intersections, and unions across relations, which means the engine may need to explore many possible paths before it can prove access or denial. The performance problem is not simply query volume. It is the shape of the graph, including how many related objects exist and how expensive each subgraph is to explore. When the graph is sparse, traversal can stop early. When it is wide or deeply nested, the engine may do a large amount of work before reaching a conclusion.

Practical implication: treat relationship fan-out and nesting depth as first-class performance inputs in authorization design.

Why query planners use statistics to reorder checks

The planner estimates traversal cost from data statistics and then reorders evaluation to minimise work. In an arrow operation, it can choose the smaller side of the relationship first, then reduce the search space for the rest of the check. In an intersection, it can evaluate the path most likely to fail first, because one definite no short-circuits the rest. This is closer to database planning than to static policy evaluation. The key distinction is that the engine is making runtime decisions based on expected cost, not following one fixed evaluation order for every request.

Practical implication: keep relationship statistics accurate enough that runtime ordering decisions reflect real tenant data.

Query plan trees and authorization optimisation

The article describes a query plan tree as the abstract structure the planner manipulates before execution. Each node represents a relation, arrow, union, or intersection, and the tree can be reordered or rebalanced to change the work profile of a permission check. This matters because the same authorization question can have multiple valid evaluation paths, but not all paths are equally expensive. By turning the policy into a plan tree, the engine can apply heuristics at runtime without changing the underlying authorization model. That separation of policy from execution strategy is what makes the optimisation possible.

Practical implication: expect policy expressiveness to remain intact while execution strategy becomes increasingly data-aware.

Breaches seen in the wild

• Schneider Electric credentials breach — exposed credentials gave attackers access to Schneider Electric Jira, exfiltrating 40GB.
• LiteLLM PyPI package breach — LiteLLM PyPI supply chain attack, credentials stolen from users.

Read our 52 NHI Breaches Analysis report for a comprehensive view of breaches impacting Non-Human Identities including AI Agents.

NHI Mgmt Group analysis

Authorization latency is becoming a graph-shape governance problem, not just a database problem. Authzed’s planner shows that the same ReBAC policy can behave very differently depending on how relationships are distributed across the system. That means performance is no longer separable from identity structure, especially where service accounts, applications, and delegated relationships create dense permission graphs. Practitioners should treat graph shape as part of authorization governance, not only as an engineering concern.

Cost-based evaluation is the right abstraction for large authorization graphs. Fixed-order traversal assumes every path has similar cost, which stops holding once schemas include deep nesting, wide fan-out, or highly asymmetric relations. The planner’s approach mirrors mature database design: use statistics, estimate traversal cost, and choose the cheaper evaluation path first. That is a cleaner mental model for ReBAC at scale, and it should influence how teams think about policy design, data distribution, and latency budgets.

ReBAC performance tuning now depends on knowing where the expensive paths actually are. The article’s central point is that a policy engine cannot optimise what it does not measure. Shape-aware planning works only when the system can estimate the likely cost of subgraph exploration, which means relationship metadata becomes operationally relevant. The practical conclusion is that teams need visibility into relationship density and traversal hotspots before authorization latency becomes user-visible.

Named concept: authorization graph cost modelling. This article sharpens the idea that access checks should be planned against estimated graph cost, not just executed against static policy logic. That concept matters because it turns authorization performance into a measurable property of the identity graph itself. For practitioners, the implication is that ReBAC scaling depends on modelling relationship cost as carefully as entitlement scope.

This kind of planning will become more relevant as non-human identity graphs expand. Service accounts, API-driven workflows, and delegated machine access tend to create broad, uneven relationship structures that are harder to traverse efficiently. The lesson is not that ReBAC is failing, but that its runtime must become more adaptive as identity populations and relationship density increase. Teams should expect authorization engines to depend more heavily on live graph statistics over time.

From our research:

• 97% of NHIs carry excessive privileges, increasing unauthorised access and broadening the attack surface, according to Ultimate Guide to NHIs.
• Only 5.7% of organisations have full visibility into their service accounts, which means many identity teams are still operating without a reliable view of machine access.
• For a broader baseline, Ultimate Guide to NHIs , Why NHI Security Matters Now explains why machine identity growth keeps raising the governance bar.

What this signals

Authorization engines will need better identity graph telemetry as ReBAC adoption grows. The practical issue is not whether planners exist, but whether the relationship data they depend on stays accurate enough to support runtime decisions. In NHI-heavy environments, that pressure rises quickly because service and workload identities multiply the number of relationships the engine must understand.

As teams add more delegated and machine-driven access, they should expect performance tuning to become a governance topic. The systems that will hold up are the ones that can see which relation patterns are expensive, which checks are repeatedly pathologically slow, and where policy design is creating avoidable traversal work.

For practitioners

• Profile authorization hot paths Measure which permission checks consume the most traversal work, then map those paths back to relationship fan-out and nesting depth. Focus on the queries that combine wide membership sets, deep recursion, or asymmetric intersections because those are the places where query planning will matter most.
• Review schema shapes before tuning infrastructure Look at whether slow checks are caused by poor graph shape rather than raw datastore performance. If a small number of relations create most of the traversal cost, restructure the policy model or relationship layout before adding more cache or database capacity.
• Validate statistics against real tenant data Make sure any cost estimates used for evaluation ordering reflect the current distribution of relationships, not just synthetic benchmarks. Stale statistics can lead the planner to choose the wrong path, which turns optimisation into extra work instead of less work.
• Set explicit latency budgets for complex checks Define service-level targets for authorization checks that traverse deep or wide graphs, then test whether planner changes meet those budgets under production-like data. Use those results to decide where policy simplification is more effective than further optimisation.

Key takeaways

• SpiceDB’s planner turns authorization latency into a data-shape problem by choosing cheaper graph traversals at runtime.
• Large, uneven relationship graphs create expensive permission checks, especially when intersections or arrows force broad traversal.
• Teams should measure graph shape, validate statistics, and simplify policy structure before relying on infrastructure tuning alone.

Key terms

• Relationship-based access control: A permission model that grants access by evaluating relationships between subjects, resources, and intermediate objects. In practice, it turns authorization into graph traversal, which makes data shape, nesting depth, and relationship fan-out major factors in both correctness and performance.
• Query planner: A runtime component that chooses the most efficient way to evaluate an authorization request. Instead of following one fixed path, it uses cost estimates and statistics to reorder checks, reduce unnecessary traversal, and shorten the work required to reach an access decision.
• Authorization graph cost: The expected amount of work required to answer a permission check across a relationship graph. It depends on how many nodes and paths must be explored, how deep the graph is, and whether the engine can short-circuit before evaluating every branch.
• Traversal hotspot: A part of the authorization graph that consistently requires disproportionate evaluation effort. These hotspots often appear where large groups, deep recursion, or asymmetric intersections make the engine inspect many paths before it can return a decision.

Deepen your knowledge

ReBAC performance planning and authorization graph analysis are core topics in our NHI Foundation Level course, the industry's only accredited NHI security programme. If you are building identity controls for large machine and service account populations, it is worth exploring.

This post draws on content published by Authzed: SpiceDB query planning for ReBAC performance. Read the original.