>

Base Layer EP 06: Ari Shamash on Your Agent Shouldn't Have Your Password

[Listen now]

Building a Query Planner: Testing Strategy to Validate Correctness in SpiceDB

How we validate the correctness of the experimental SpiceDB Query Planner by layering consistency tests, property-based tests, and end-to-end steelthread tests on top of unit tests.

Joey Schorr
November 19, 2026·8 min read

This post is part 3 of our series on the SpiceDB Query Planner. Read part 1 and part 2.

In our previous blog post about Query Planner, we laid out a vision for how a modern query planner could improve the performance of a relationship-based access control database like SpiceDB. Query planners are traditionally found in relational databases like Postgres, where they improve the performance of queries such as SELECT by splitting execution into two stages (planning and execution) rather than executing everything in a single step.

This post continues our series on developing the experimental Query Planner in SpiceDB, providing a deep dive into its design and implementation. Today, we cover recent developments in the first phase of work: correctness.

For a permissions database, correctness is the top priority. If SpiceDB returns the wrong answer to a Check request, it doesn't matter how fast it responded; any incorrect answer is, at minimum, a security vulnerability. This sets SpiceDB apart from traditional databases. If Postgres returns an incomplete set of rows for a query, it is certainly a bug, but whether it becomes a security issue depends on the context of the application rather than being an inherent breach.

One of our primary goals in developing the Query Planner has been identifying and resolving correctness issues early, before the experimental planner ever touches a production environment. To achieve this, we rely on four testing strategies in SpiceDB: unit tests, consistency tests, property-based tests, and steelthread tests. Since unit tests are standard, we'll first start by looking at SpiceDB's consistency test suite.

Consistency Tests

In SpiceDB, a "consistency test" verifies that for a specific schema and set of pre-defined relationships, all API responses remain consistent with one another. For instance, if a CheckPermission request returns PERMISSIONSHIP_HAS_PERMISSION, the resource-and-subject pair must also appear in the output of LookupResources and LookupSubjects (and vice versa). If they differ, the API implementations are out of sync, signaling a bug in one or more endpoints.

Consistency tests: a fixed schema and set of relationships are run through CheckPermission, LookupResources, LookupSubjects, and ExpandPermissionTree, and the results are cross-checked against an accessibility set for agreement across APIs.

Consistency tests are implemented in consistency_test.go, which loads configurations from the testconfigs directory. Each YAML file in that directory represents a single consistency test, specifying the schema, relationships, and expected assertions. Notably, this uses the exact format used by the SpiceDB Playground, making test cases fully interchangeable between the two.

Consistency tests execute in a number of steps:

First, the test runner constructs a SpiceDB datastore (using an in-memory store by default, though a subset runs against production datastore backends). It writes the schema with full validation, applies each relationship via the WriteRelationships API, and reads them back. This verifies that schema writes and relationship updates work as expected across all input scenarios.

Second, the predefined assertions are executed as CheckPermission calls to validate the baseline state intended by the test author.

Third, the test constructs an "accessibility set," representing every accessible subject across all resource and permission combinations. For example, in a schema with a view permission on a document, the accessibility set collects every user who has access to each document by running CheckPermission across every subject and resource pair.

Finally, the runner calls LookupResources, LookupSubjects, ExpandPermissionTree, and several other APIs against every combination of resource, permission, and subject, cross-checking the results across APIs to ensure full consistency.

To support the Query Planner, we integrated it as another consumer of the consistency test suite in query_plan_consistency_test.go. This ensures that the Query Planner's output matches the legacy implementation across all existing APIs.

Consistency tests quickly proved their worth by uncovering numerous bugs during early Query Planner development. However, they have a fundamental blind spot: they only test known schema structures and relationships. If an edge case isn't covered by a predefined scenario, the bug will remain hidden until encountered in production.

To proactively catch these unknown edge cases, we introduced property-based testing.

Property-Based Tests

Property-based testing takes a proactive approach to validation. Instead of testing static scenarios, a property-based test defines a set of properties, such as the valid structural shapes (definitions and permissions operations) allowed within a schema. The testing framework continuously generates randomized test cases based on these rules, starting from a random seed. This allows us to explore a vastly larger state space without manually authoring every permutation.

When a property-based test discovers a failure, the framework automatically shrinks the failing input down to a minimal reproducible test case, which can then be saved as a standard test for regression tracking and TDD fix development.

Property-based tests: a random seed generates test cases with varied schema shapes (union, intersection, exclusion) and matching relationships, which are checked against the Query Planner. Passing cases continue with more cases; failing cases are shrunk to a minimal case and saved as a reproducible regression test.

In SpiceDB, property-based testing began with the v2 schema package, which was designed from the ground up to compose modular schema components. Built on top of this, the testing package leverages rapid, a Go property-based testing framework, to generate randomized schemas and corresponding relationship tuples.

For example, inside mustGenerateOperation, the generator randomly selects permission constructs like unions, intersections, exclusions, and arrows using rapid:

go
choice := rapid.IntRange(0, 3).Draw(t, path+"::permissionTypeChoice")
switch choice {
case 0:
    // Direct relation.
    relationName := rapid.SampledFrom(relationNames).Draw(t, path+"::directRelationName")
    return schema.NewRelationRef(relationName)

case 1:
    // Union
    numChildren := rapid.IntRange(1, 3).Draw(t, path+"::unionNumChildren")
    unionBuilder := schema.NewUnion()

Another section generates relationships based on the structure of the generated schema:

go
// Select a random subject type from the allowed types.
allowedSubjectType := rapid.SampledFrom(allowedSubjectTypes).Draw(t, resourceTypeName+"#"+relationName+"-"+"subjectTypeName")

// Generate a random subject ID.
subjectID := rapidObjectString.Draw(t, "subjectID")

relationship := tuple.Relationship{
    RelationshipReference: tuple.RelationshipReference{
        Resource: tuple.ObjectAndRelation{
            ObjectType: resourceTypeName,
            ObjectID:   resourceID,
            Relation:   relationName,
        },
        Subject: tuple.ObjectAndRelation{
            ObjectType: allowedSubjectType.Type(),
            ObjectID:   subjectID,
            Relation:   allowedSubjectType.Subrelation(),
        },
    },
}

Together, these two generator subsystems produce schema and relationships:

zed
schema: |+
  definition s_b0 {}

  definition s_hz {
        relation r_ob030z4x6k: s_hz
  }

  definition d_n0 {
        relation r_1ccxk: s_b0
        relation r_3o: s_b0
        relation r_ab7yk3hut2f5f021: s_hz#r_ob030z4x6k | s_hz
        permission p_a0706vd241x = ((r_1ccxk - r_3o))
        permission p_68f1 = r_3o + r_3o
  }

  definition d_6_02r {
        relation r__3s031072h: s_b0
        relation r_dgnjcz: s_hz#r_ob030z4x6k | s_hz
        relation r_1vfz: s_b0

        permission p_3m6j5 = r__3s031072h - ((r_dgnjcz->r_ob030z4x6k & r__3s031072h) - r_dgnjcz->r_ob030z4x6k + r_dgnjcz->r_ob030z4x6k)
  }

relationships: |-
  d_n0:o_15b4eb2#r_1ccxk@s_b0:o_zeq032pfm11snk2#...
  d_n0:o_g1frw#r_1ccxk@s_b0:o_o6#...
  d_n0:o_184bh56e#r_3o@s_b0:o_118y7o15gtm5s258m#...
  d_6_02r:o_02ushz#r_1vfz@s_b0:o_dlzxo3k0h1#...
  d_6_02r:o_61088_511128czh840adw14t420#r_dgnjcz@s_hz:o_0ghjx6n402#r_ob030z4x6k
  d_n0:o_540zb56f0j02m#r_1ccxk@s_b0:o_24b#...
  d_n0:o_n1qfam#r_ab7yk3hut2f5f021@s_hz:o_0_j#r_ob030z4x6k
  d_n0:o_4y001#r_ab7yk3hut2f5f021@s_hz:o_cif8034321#r_ob030z4x6k
  d_6_02r:o_11#r_1vfz@s_b0:o_r7x#...
  d_n0:o_7gu9d4o92u4c#r_ab7yk3hut2f5f021@s_hz:o_ztd0q0x15u11p4ae7#...
assertions:
  assertTrue: []
  assertFalse: []

While generated schemas are dense and synthetically named, these scenarios are automatically fed into both the Query Planner integration tests and the consistency testing suite for exhaustive verification.

Property-based testing has already uncovered subtle logical edge cases. When a bug is found, we often simplify the generated case and add it to our permanent consistency test suite for explicit coverage. Combined with unit and consistency tests, property-based testing has significantly raised our confidence in correctness.

Unit, consistency, and property-based tests still share one common limitation: they evaluate component logic in isolation rather than testing complete API calls end-to-end.

Steelthread Tests

To bridge this gap, SpiceDB relies on "steelthread tests."

Named after the software architecture concept, itself originally based on a bridge building technique (yes, really!), steelthread tests execute end-to-end requests with predefined inputs and outputs through every layer of the SpiceDB stack.

In SpiceDB, steelthread operations execute complete API requests through request validation, caching, concurrency controls, core permission logic, and datastore backends. This lets us validate proof-of-concept changes in the Query Planner, ensure full stack compatibility, and verify that complex or unusual queries behave consistently and performantly across both legacy and new execution paths.

Steelthread tests: a predefined API request, such as a CheckPermission call, runs end-to-end through the SpiceDB stack (validation, caching, concurrency, Query Planner, and datastore) and is compared against the expected output.

Summing Everything Up

Correctness is paramount for a permissions database like SpiceDB, and ensuring that Query Planner produces the right results is a critical first step toward making it production-ready. By combining consistency tests, property-based tests, and steelthread tests, alongside our existing unit tests, we've built a layered approach to identifying correctness issues early and across a wide variety of scenarios.

The big picture: consistency tests, property-based tests, and steelthread tests, built on a foundation of unit tests, work together to ensure the correctness and security of the SpiceDB Query Planner.

Consistency tests ensure that Query Planner agrees with the existing SpiceDB implementations, property-based tests help uncover edge cases that we might never have thought to test manually, and steelthread tests verify that everything continues to work correctly through the entire SpiceDB stack. Together, these approaches have already helped us identify and resolve numerous issues, giving us significantly greater confidence in the correctness of Query Planner as we continue its development. While there's still more work ahead, this testing foundation puts us in a much stronger position to move forward with the next phases of the project.

Related

See AuthZed in action

Build delightful, secure application experiences with AuthZed.