Traversing a Living Graph: Sparse Kernels and Native Paths

HydraDB's traversal engine has to solve two problems at once. It must move through a large, sparse graph without repeatedly doing expensive work, and it must return the relationships and properties that make a path meaningful to an application. This chapter focuses on that boundary: what compact topology and GraphBLAS accelerate, what they deliberately leave to canonical records, and how HydraDB keeps path enumeration, relationship identity, and result size within explicit limits.

The distinction matters because a graph can have two valid descriptions of the same connection. For reachability, it may be enough to know that vertex 1 can reach vertex 2 through a relationship of a particular type. For an application, it may matter which relationship carried that connection, what its identifier is, and which weight or cost it has. HydraDB uses the first description to make traversal efficient, then returns to the second to make the answer faithful.

This work takes place inside the pinned read boundary already established for HydraDB. A compiled structure, a WAL overlay, a selector index, and relationship metadata are useful only insofar as they describe the same read view. The sparse kernel is therefore an accelerator inside the graph’s authority model, not a replacement for it.

The shortcut is the topology, not the meaning

Suppose a query asks for bounded paths from a source to a target. A general-purpose row engine could repeatedly fetch neighbor records, test whether a vertex has already been visited, and build the next frontier. That route is flexible, but it can spend substantial effort on repeated map lookups and object-store-backed reads. HydraDB can instead represent adjacency as a sparse matrix: rows or columns identify vertices, and stored entries identify connections. The matrix contains the shape of the graph, not every semantic detail attached to its relationships.

A sparse representation is useful because most real graphs are not fully connected. The engine records the nonempty connections and uses a frontier of reached vertices to expand one hop at a time. A bounded traversal can then count edge visits, retain a seen set, and stop at the requested hop limit. Those operations are especially natural for a compressed sparse column, or CSC, representation: a flat set of vertex identifiers, pointers delimiting each source's neighbor range, and indexes into the vertex dictionary.

The structural view intentionally collapses some information. If two RELATES relationships connect the same source and destination, adjacency needs to know that the pair is reachable; it does not need to duplicate the neighbor merely because two relationship records exist. Returning a path is different. The application may need both relationship identifiers, their properties, or their distinct weights. HydraDB postpones that expansion until after structural paths have been found.

This is the first important boundary: structural adjacency answers “which vertices can follow this topology?” Canonical relationship records answer “which concrete relationship and metadata realize this step?” Confusing the two either wastes the sparse representation by putting every property into it or loses application meaning by returning only endpoints.

Three rungs, three costs

HydraDB implements a ladder of sparse traversal kernels rather than treating GraphBLAS as an all-or-nothing feature.

The first rung is adjacency breadth-first search over ordinary Rust maps and sets. It needs no compiled matrix and can operate on adjacency that has already been hydrated. Its advantage is low setup cost and broad availability. Its limitation is that it does not provide the compiled path's additional capabilities, such as certain count or result-window pushdowns and direct edge-containment operations.