SpiceDB query planning shows why authorization cost depends on data shape

At a glance

What this is: Authzed describes an experimental SpiceDB query planner that uses relationship-shape statistics to choose cheaper authorization paths at query time.

Why it matters: IAM and IGA teams using ReBAC need to treat authorization performance as a graph-shape and policy-design problem, because query order can materially affect latency and scale.

Context

ReBAC authorization systems do not only fail on logic errors; they also slow down when the relationship graph becomes deep, wide, or uneven. In that setting, the cost of a permission check depends on how much of the graph must be traversed before the engine can prove access or deny it, which makes data shape a first-class performance variable.

Authzed’s article frames the issue around SpiceDB’s query planner, which can estimate traversal cost and reorder work at runtime. For identity teams, the governance question is whether authorization structures are being designed with enough shape awareness to keep checks predictable as relationship volume grows.

Key questions

Q: What breaks when ReBAC authorization data is highly skewed?

A: When one side of a relationship is sparse and another is extremely dense, fixed evaluation order can force the engine to explore far more of the graph than necessary. That leads to unpredictable latency, wasted datastore calls, and checks that are logically correct but operationally expensive.

Q: Why does authorization latency depend on graph shape?

A: Because the engine has to traverse relationships to prove or deny access, and the number of objects behind each edge changes how much work the check needs. Dense groups, deep nesting, and wide fan-out all increase the cost of reaching a decision, even when the policy itself is simple.

Q: How do security teams know a query planner is helping?

A: They should look for shorter checks on dense graphs, fewer unnecessary traversals, and better short-circuiting on intersections where one branch usually fails. If latency only improves on trivial requests, the planner is not addressing the part of the model that actually creates cost.

Q: Should teams redesign authorization models for performance or keep policy structure unchanged?

A: Teams should preserve the security intent of the policy, but they should not assume every graph shape is equally efficient. If a permission model creates extreme fan-out or deep joins, restructuring the data model may be necessary to keep authorization usable at scale.

Technical breakdown

Why relationship shape changes ReBAC cost

Relationship-based access control answers questions by traversing a graph of users, groups, resources, and permissions. In a simple case, a permission check can touch only a few edges; in a dense case, the engine may need to explore many possible paths before it can conclude anything. That means the same policy can have very different runtime cost depending on how many objects sit on each side of a relation, how deep nesting goes, and whether one branch is likely to fail or succeed quickly. Traditional caching and batching help, but they do not fully solve the problem when the graph itself is skewed.

Practical implication: Model ReBAC policies with graph cost in mind, not just logical correctness.

How query planning reorders arrows and intersections

The planner described in the article treats a permission check as a tree of operations that can be rearranged before execution. For an arrow, it can choose which side of the relation to inspect first when it expects one side to be smaller or cheaper. For an intersection, it can evaluate the most likely failing branch first and short-circuit the rest if that branch returns no permission. The important technical shift is that the engine is no longer following a fixed evaluation order. It is using cost estimates from relationship statistics to choose a cheaper plan at query time.

Practical implication: Verify that your authorization engine can short-circuit expensive branches instead of evaluating every path equally.

Why statistics become part of authorization architecture

The planner only works well if it has usable statistics about relationship shape. Those statistics describe how many related objects exist, how sparse or dense a branch is, and how expensive a traversal is likely to be. That is similar in spirit to database query planning, where the optimiser depends on metadata to avoid worst-case joins. In authorization, the same idea means the data model and the operational telemetry behind it become part of the access-control architecture. Without that metadata, the engine is forced into generic traversal choices that ignore whether a branch is wide, narrow, or effectively empty.

Practical implication: Keep authorization statistics accurate enough that the planner can make defensible runtime choices.

NHI Mgmt Group analysis

Query planning turns authorization performance into a data-shape governance issue: once ReBAC graphs become deep and uneven, latency is determined as much by relationship distribution as by policy logic. That changes the governance conversation from "is the permission model correct?" to "is the permission model operationally scalable under real graph shape?" Practitioners should treat graph shape as part of authorization design, not an implementation detail.

Static evaluation order is a hidden performance assumption: many authorization engines implicitly assume that any branch can be explored in roughly the same way. That assumption fails when one relation is sparse and another is dense, because the cheapest proof path is no longer obvious in advance. The result is unnecessary traversal work that would never be visible in a policy review but shows up immediately in production latency.

Cost-aware authorization is becoming a design expectation, not an optimisation bonus: once an engine can reorder arrows and intersections using statistics, policy authors and platform teams have to think about whether their data model gives the planner room to win. That means the shape of groups, resource fan-out, and nesting depth are now part of the control surface. The practical conclusion is that authorization architecture must be designed with runtime selectivity in mind.

Relationship statistics are the new supporting control plane for ReBAC: the planner depends on metadata about how authorization data is distributed, not just on the relationships themselves. That makes stale or unrepresentative statistics an operational risk because the engine can choose a plan that looks cheap on paper but is expensive in practice. Identity teams should therefore treat planner inputs as governed operational data, not as invisible implementation plumbing.

What this signals

Query planners expose a new design constraint for ReBAC programmes: if relationship distributions are highly uneven, performance tuning shifts from infrastructure-first thinking to policy-shape thinking. Teams should expect more pressure to understand which relations are dense, which are sparse, and which paths dominate real traffic.

Authorisation statistics now behave like operational identity data: if the metadata behind traversal cost is stale, the engine may make the wrong runtime choice even though the policy is unchanged. That makes planner inputs part of ongoing governance, not a one-time tuning exercise.

For practitioners

• Design for graph selectivity Review whether your ReBAC schema creates highly skewed relations, deep nesting, or large fan-out paths that make some checks much more expensive than others.
• Profile expensive authorization paths Measure which permission checks repeatedly trigger broad traversal, then identify where intersections, unions, or arrows could be restructured to shorten the common path.
• Validate planner statistics regularly Check that relationship-count metadata reflects current production distributions, especially after major onboarding waves, tenancy changes, or policy expansions.
• Separate cheap fail paths from expensive success paths Make sure the authorization model gives the engine a realistic chance to short-circuit on branches that are likely to deny access before it explores dense relations.
• Test worst-case authorization latency Load-test deep and wide graph patterns rather than only average traffic, because the planner’s value appears most clearly when traversal cost is uneven.

Key takeaways

• ReBAC authorization performance is not only a database or cache problem. The shape of the relationship graph determines how much traversal work each check must do.
• SpiceDB’s experimental planner uses relationship statistics to reorder checks and short-circuit expensive work when one branch is likely cheaper or more selective.
• Identity teams should design authorization graphs, observe hot paths, and keep traversal statistics current if they want predictable latency at scale.

Key terms

• Relationship-based access control (ReBAC): A model where access decisions are made by following relationships between subjects, resources, and groups rather than by simple role membership alone. In practice, the policy engine evaluates graph paths to determine whether a user or service should be allowed to act.
• Query planner: A query planner is the component that decides which order and direction to evaluate parts of an authorization request. In graph-based access control, it turns reachability into a cost-based routing problem, choosing paths that can reduce fan-out, short-circuit sooner, and limit unnecessary work.
• Graph selectivity: The degree to which one authorization path is narrow or broad relative to another. High selectivity means a branch is likely to eliminate many candidates quickly, which helps an engine short-circuit work and reduce traversal cost.
• Traversal cost: The amount of work needed to follow relationships and prove a permission result. In ReBAC, cost rises when the graph is deep, wide, or uneven, and it directly affects latency, datastore load, and the stability of authorization checks.

Deepen your knowledge

NHI governance, agentic AI identity, and machine identity lifecycle are core topics in our NHI Foundation Level course, the industry's only accredited NHI security programme. If you are responsible for identity security strategy or NHI governance in your organisation, it is worth exploring.