Stitching Many-to-Many Relationships in Cache

A one-to-many relationship has an obvious home: the child holds the parent’s id. A many-to-many has none — put tagIds on the todo and you cannot answer “which todos have this tag” without scanning every todo; put todoIds on the tag and you cannot render a todo’s tags without scanning every tag; put both and you now store the same fact twice and get to keep them in step forever. This page covers the third option, which is to give the relationship its own place in the cache. It sits under Relationship Stitching in Cache, alongside Resolving One-to-Many Relationships in Cache, and it assumes the flattening described in Flattening Deeply Nested GraphQL Responses.

Prerequisites

• Entities already normalized into flat, id-keyed collections.
• A server that can return the relationship as edges, or a response you can derive edges from.
• Memoized selectors, since both directions are derived — see Memoizing Selectors With Reselect.

---

Step 1 — Store the Relationship as Edges

An edge is a pair plus whatever the join carries. It gets its own cache entry, keyed like any other collection.

export interface TagEdge {
  todoId: string;
  tagId: string;
  /** Join-table payload: when it was applied, and by whom. */
  addedAt: string;
  addedBy: string;
}

export const tagEdgeKeys = {
  all: ['tagEdges'] as const,
  forBoard: (boardId: string) => [...tagEdgeKeys.all, 'board', boardId] as const,
};

export const tagEdgeQueries = {
  forBoard: (boardId: string) =>
    queryOptions({
      queryKey: tagEdgeKeys.forBoard(boardId),
      queryFn: ({ signal }) => fetchTagEdges(boardId, signal),
      // Edges change more often than the entities they connect.
      staleTime: 15_000,
    }),
};

Cache Behavior Analysis: Giving edges their own query key means they have their own staleTime, their own invalidation and their own entry — so applying a tag can invalidate the edges without refetching every todo body, which is the practical payoff over embedding ids in the entities. Scoping the edge collection by board rather than fetching all edges globally keeps the entry bounded: an unscoped edge collection grows with the product of both entity counts and becomes the largest thing in the cache. The join payload lives on the edge because it belongs to neither side — addedAt is a property of the relationship, and there is nowhere else it can go without duplicating it.

---

Step 2 — Derive Both Directions

Neither entity stores the relationship, so both views are computed. One pass over the edges builds both indexes.

import { createSelector } from 'reselect';

interface StitchInput { todos: Record<string, Todo>; tags: Record<string, Tag>; edges: TagEdge[] }

export const selectIndexes = createSelector(
  [(input: StitchInput) => input.edges],
  (edges) => {
    const tagsByTodo = new Map<string, string[]>();
    const todosByTag = new Map<string, string[]>();
    for (const edge of edges) {
      (tagsByTodo.get(edge.todoId) ?? tagsByTodo.set(edge.todoId, []).get(edge.todoId)!).push(edge.tagId);
      (todosByTag.get(edge.tagId) ?? todosByTag.set(edge.tagId, []).get(edge.tagId)!).push(edge.todoId);
    }
    return { tagsByTodo, todosByTag };
  },
);

export const selectTagsForTodo = createSelector(
  [selectIndexes, (input: StitchInput) => input.tags, (_input: StitchInput, todoId: string) => todoId],
  (indexes, tags, todoId) =>
    (indexes.tagsByTodo.get(todoId) ?? [])
      .map((tagId) => tags[tagId])
      // A tag referenced by an edge but not yet fetched is skipped, not undefined.
      .filter((tag): tag is Tag => Boolean(tag)),
);

Cache Behavior Analysis: Building both indexes in one pass keyed only on edges means the expensive work runs once per edge change rather than once per direction, and structural sharing keeps edges referentially stable across refetches that return identical data, so a poll costs nothing. Filtering out missing tags is not defensive padding: edges routinely arrive before the entities they reference, and rendering undefined in a tag list is the most common symptom of a partially loaded graph. Because the indexes are Maps rather than plain objects, lookup is O(1) without the prototype hazards of using arbitrary ids as object keys.

---

Step 3 — Maintain Edges Through Mutations

Applying a tag inserts an edge; removing one deletes it. Both need an optimistic path, and both are simpler than updating two entity collections.

export function useApplyTag(boardId: string) {
  const client = useQueryClient();
  const key = tagEdgeKeys.forBoard(boardId);

  return useMutation({
    scope: { id: `tag-edges-${boardId}` },
    mutationFn: ({ todoId, tagId }: { todoId: string; tagId: string }) => applyTag(todoId, tagId),

    onMutate: async ({ todoId, tagId }) => {
      await client.cancelQueries({ queryKey: key });
      const previous = client.getQueryData<TagEdge[]>(key);

      client.setQueryData<TagEdge[]>(key, (edges = []) => {
        // Idempotent: applying a tag that is already applied is a no-op, not a duplicate.
        if (edges.some((edge) => edge.todoId === todoId && edge.tagId === tagId)) return edges;
        return [...edges, { todoId, tagId, addedAt: new Date().toISOString(), addedBy: 'me' }];
      });

      return { previous };
    },

    onError: (_error, _variables, context) => {
      if (context?.previous) client.setQueryData(key, context.previous);
    },

    // Reconcile with the server: it owns addedAt and addedBy.
    onSettled: () => client.invalidateQueries({ queryKey: key }),
  });
}

Cache Behavior Analysis: One setQueryData on the edge collection updates both derived directions simultaneously, because both selectors read the same source — the equivalent bidirectional update would need two writes plus a guarantee that neither can happen without the other. The idempotence check matters because the same tag can be applied from a todo detail view and a tag panel in quick succession, and a duplicate edge would show the tag twice. Scoping the mutation serializes edge writes for this board, so two rapid applications cannot interleave their optimistic array rebuilds — a real hazard when both read edges and write a new array.

---

Step 4 — Index the Edges When the Collection Grows

A linear scan is fine at a few hundred edges and not at fifty thousand. When it stops being fine, store the index rather than deriving it.

export interface EdgeIndex {
  edges: TagEdge[];
  tagsByTodo: Record<string, string[]>;
  todosByTag: Record<string, string[]>;
}

/** Build once at the query boundary, so components read O(1) lookups. */
export function indexEdges(edges: TagEdge[]): EdgeIndex {
  const tagsByTodo: Record<string, string[]> = {};
  const todosByTag: Record<string, string[]> = {};
  for (const edge of edges) {
    (tagsByTodo[edge.todoId] ??= []).push(edge.tagId);
    (todosByTag[edge.tagId] ??= []).push(edge.todoId);
  }
  return { edges, tagsByTodo, todosByTag };
}

export const indexedEdgeQueries = {
  forBoard: (boardId: string) =>
    queryOptions({
      queryKey: tagEdgeKeys.forBoard(boardId),
      queryFn: async ({ signal }) => indexEdges(await fetchTagEdges(boardId, signal)),
      staleTime: 15_000,
      // The index is derived, so structural sharing on it is wasted work —
      // the edges array is what needs stable identity.
      structuralSharing: (previous, next) =>
        previous && (previous as EdgeIndex).edges === (next as EdgeIndex).edges ? previous : next,
    }),
};

Cache Behavior Analysis: Building the index inside queryFn means it is computed once per fetch rather than once per selector invalidation, and it is stored in the cache alongside the edges so every consumer shares one copy. The custom structuralSharing avoids the default deep comparison walking three structures when only one of them is authoritative — comparing the edges reference is sufficient, because the two indexes are pure functions of it. The trade is that mutations must now update three fields consistently, which is why this refactor belongs at the point where the scan is genuinely measurable rather than pre-emptively.

---

Edge Cases & Gotchas

Edges arriving before entities. An edge referencing a tag not yet fetched must not render as undefined. Filter unresolved references in the selector and let the entity query fill them in — the list simply grows as data arrives.

Deleting an entity leaves orphan edges. Removing a tag must remove its edges too, or the derived index keeps a reference to something that no longer exists. Do it in the same mutation, or invalidate the edges alongside.

Apollo’s normalized cache. Apollo stores references in both directions if the server returned them, so reading works — but a mutation that adds an edge does not update the reverse direction unless a type policy says so. The usual pragmatic answer there is to refetch the affected connection.

---

Common Pitfalls & Resolutions

---

Frequently Asked Questions

Why not store tagIds on the todo and todoIds on the tag?

Because it stores one fact in two places, and two copies of a fact drift. Every mutation now has to update both sides, and it has to do so atomically — but a server response that returns only the updated todo silently leaves the tag’s list wrong, and nothing detects it until a user notices a tag panel disagreeing with a todo. It also doubles the invalidation surface: applying a tag must invalidate both entity collections rather than one edge collection. A single source with two derived views has neither problem, and the derivation is a handful of lines.

Does Apollo InMemoryCache handle this automatically?

Partly. It normalizes both entity types and stores references between them, so if the server returns a todo with its tags and a tag with its todos, reading either direction from the cache works without any code from you. What it does not do is maintain the reverse direction after a mutation: adding a tag to a todo updates the todo’s tag list, and the tag’s todo list stays as it was until something refetches it. Type policies with a merge function can close that gap, but the pragmatic answer in most codebases is to invalidate the affected connection and let the server be authoritative.

When is an edge collection overkill?

Whenever one side clearly owns the other. A todo’s checklist items, a comment’s reactions, an invoice’s line items — these are one-to-many with an unambiguous owner, and an array of ids on the owner is simpler, cheaper and has no consistency obligation because there is only one writer. The signal that you have crossed into needing edges is the second direction becoming a real query: the moment someone asks “which todos have this tag” and the answer requires scanning every todo, the relationship deserves its own home.

---

Related

• Relationship Stitching in Cache — the parent guide on reconstructing a graph from flat cached entities.
• Resolving One-to-Many Relationships in Cache — the simpler shape, where an owner holds the ids.
• Denormalizing Cache Data for Rendering — turning the stitched graph back into render-ready objects.
• Memoizing Selectors With Reselect — keeping both derived directions cheap.