Precomputed Graph Traversal in a Reactive Document Database

Why This Solves the N+1 Problem for Real-Time Apps

The traditional N+1 query problem: you load a list of N items, then for each item you run a query to load related data. N+1 total queries. In a request-response system, you solve this with eager loading or batching.

In a reactive system, the N+1 problem is worse. Every standing query that traverses a relationship is continuously re-evaluated. Without precomputed indexes, a formula like bubble my_groups = iterate _users where account == @who traverse in_group would require:

1. Find the user (table scan or index lookup -- O(1) with index)
2. For that user, scan every group's member table to find matches
3. Return matching groups

Step 2 is O(groups * avg_members_per_group). With 200 groups averaging 50 members each, that is 10,000 comparisons per viewer per state change. With 1,000 viewers, that is 10 million comparisons per mutation. And mutations happen constantly in a real-time application.

With graph indexing, step 2 becomes a hash map lookup. The RxAssocGraph maps user IDs to sets of group IDs. Finding my groups is O(my_group_count), not O(total_groups * total_members). The graph updates incrementally: when a member is added to a group, only that single edge is processed. No full recomputation.

Nested Table Joins: The Killer Feature

The most powerful application of graph indexing is crossing into nested tables. Adama allows tables inside records -- a record in _groups can contain a table<Member> _members. This is natural for document store modeling but creates a query nightmare: finding which groups contain a specific user requires scanning every group and every nested members table.

Graph indexing solves this by joining through nested tables:

record User {
  public int id;
  public string name;
  public principal account;
}
table<User> _users;

record Member { int user_id; }

assoc<User, Group> _users_to_groups;

record Group {
  public int id;
  public string name;
  table<Member> _members;

  // Join through the NESTED table
  join _users_to_groups via _members[x] from x.user_id to id;
}
table<Group> _groups;

bubble my_groups = iterate _users where account == @who
                   traverse _users_to_groups;

Each Group record's join statement connects its nested _members table to the global association. The DifferentialEdgeTracker monitors every group's members table simultaneously. When you add a member to any group, only that edge is processed and added to the graph. The my_groups bubble resolves in constant time per result group.

Dynamic Edges and Conditional Relationships

Edges are reactive. Add an edge record and the graph updates. Remove one and it updates again. No manual cache invalidation:

channel add_edge(AddEdge msg) {
  _edges <- {person_id: msg.person, tag_id: msg.tag};
  // all_tags formula automatically reflects the new edge
}

channel remove_edge(RemoveEdge msg) {
  (iterate _edges where id == msg.edge_id).delete();
  // all_tags formula automatically drops the removed edge
}

For conditional edges -- soft deletes, feature flags, approval workflows -- the @maybe expression makes from/to values optional:

join link via edges[x]
  from (x.enabled ? @maybe(x.from) : @maybe<int>)
  to (x.enabled ? @maybe(x.to) : @maybe<int>);

When enabled is false, the edge is excluded from the graph. Toggle enabled to true and the edge appears. This lets you model approval workflows where relationships exist but are not yet active, without creating or destroying edge records.

Multiple Joins Per Association

An association can have multiple join statements from different source tables. The runtime uses reference counting internally, so if the same from-to pair comes from two different sources, the edge exists as long as at least one source contributes it:

join access via _direct[d] from d.user_id to d.resource_id;
join access via _group[g] from g.user_id to g.resource_id;

This naturally models "direct access OR group-based access" without union queries.

For bidirectional relationships (like "friends"), you declare two associations -- one for each direction -- and join both from the same edge table:

assoc<User, User> friends_of;
assoc<User, User> friends_with;

join friends_of via _friendships[f] from f.user_a to f.user_b;
join friends_with via _friendships[f] from f.user_b to f.user_a;

Associations also support a third type parameter for documenting the edge record type: assoc<User, Group, Membership> member_of;. This does not change behavior but makes the relationship's semantics explicit in the declaration.

Performance Characteristics and Tradeoffs

Here are the actual costs:

• Edge insertion/deletion: O(1) per edge (hash map operations)
• Traversal: O(source records + result records) -- proportional to input/output, not total edges
• Memory: O(total edges) for the graph index
• Updates: Differential -- only changed edge records are reprocessed each commit cycle

Graph recomputation happens during the document's commit cycle via __computeGraphs(), after all mutations in the transaction have been applied. This means you can add 50 edges in one message and the graph processes them all in one batch.

The memory cost is the main tradeoff. If you have a million edges, that is real memory (roughly 16-24 bytes per edge for the hash map entries plus reference counts). For most applications this is negligible -- a million edges in 24MB is nothing on a server with 8GB+ RAM. But if you are modeling a social graph with billions of edges per document, this is not the right tool.

The other tradeoff is that graph indexing is an upfront investment. You pay on every write to keep the index current, even if no one is reading. For tables with frequent writes and rare reads, a plain iterate ... where ... with a field index might be cheaper. The break-even point: if you have more than a few connected viewers and the relationship involves more than ~100 edge records, graph indexing wins.

I am prouder of this feature than almost anything else in the language, because it solves a problem that is genuinely painful without it. The N+1 query problem in a reactive system is not a performance annoyance -- it is a scaling wall. Graph indexing turns it into a data structure problem with known, bounded costs.