Optimizing Graph Workloads: From Algorithm Choice to Memory Layout

Graphs are everywhere in backend systems: social connections, road networks, package dependencies, permission hierarchies, and transaction networks for fraud detection. They also cause performance cliffs. A query that runs in 5ms on test data takes 40 seconds in production because one "celebrity" node has two million edges.

Optimizing graph workloads happens at three levels: choosing the algorithm, representing the data, and constraining the search.

Level 1: pick the algorithm that fits the question

Many slow graph features use a general-purpose algorithm where a cheaper, specialized one would do.

A few observations that come up often:

• Don't run Dijkstra on an unweighted graph. Plain BFS gives the same answer without the heap overhead.
• Search from both ends. Bidirectional BFS or Dijkstra expands from the source and the target at the same time and stops when the frontiers meet. Because the frontier grows exponentially with depth, two searches of depth d/2 are much cheaper than one of depth d.
• Use A* when geometry is available. In road or grid routing, straight-line distance is an admissible heuristic that steers the search toward the goal and skips most of the graph.

A* in a nutshell

import heapq

def a_star(graph, start, goal, h):
    open_heap = [(h(start), 0, start)]
    best = {start: 0}
    parent = {}
    while open_heap:
        _, g, node = heapq.heappop(open_heap)
        if node == goal:
            return reconstruct(parent, goal)
        if g > best.get(node, float("inf")):
            continue  # stale heap entry
        for nxt, w in graph[node]:
            ng = g + w
            if ng < best.get(nxt, float("inf")):
                best[nxt] = ng
                parent[nxt] = node
                heapq.heappush(open_heap, (ng + h(nxt), ng, nxt))
    return None

The if g > best[...] check matters. Instead of implementing decrease-key, you push duplicate entries and skip the stale ones when they're popped. This is simpler and usually faster than a heap that supports updates.

Level 2: represent the graph for the workload

Adjacency matrix vs. adjacency list

• An adjacency matrix uses O(V²) memory. It suits only small, dense graphs, where constant-time edge lookups are worth the space.
• An adjacency list uses O(V + E). It's the default for real-world graphs, which are almost always sparse.

Compressed Sparse Row (CSR)

A list of lists ([][]int in Go, a list of lists in Python) scatters edges across the heap, so traversal constantly misses the CPU cache. CSR packs every edge into two flat arrays:

offsets: [0, 2, 5, 6, 8]        # node i's edges live in edges[offsets[i]:offsets[i+1]]
edges:   [1, 2, 0, 2, 3, 3, 0, 1]
weights: [4, 1, 4, 2, 5, 1, 3, 2]

Advantages:

• Contiguous memory, so traversal streams through the cache.
• Much smaller than pointer-based structures.
• Easy to memory-map from disk and share between processes.

The trade-off is that CSR is expensive to modify. A common pattern is to rebuild CSR snapshots periodically, and keep recent changes in a small side structure that queries check as well.

Renumber the nodes

If node IDs are UUIDs or strings, map them to dense integers 0..V-1 at load time. Integer IDs make array indexing possible (instead of hash lookups) and shrink every edge. Ordering nodes so that neighbors get nearby IDs, for example BFS order or community-based ordering, improves cache locality further.

Level 3: constrain the search space

The fastest traversal is the one that visits fewer nodes.

• Limit depth. "Friends of friends" means depth 2. Enforce that bound in the query instead of filtering results afterward.
• Filter early. Apply edge and node predicates (edge type, time window, active status) during traversal, not after.
• Handle supernodes. Nodes with huge degree, like a popular account or a default category, blow up traversal cost. Cap how many neighbors you expand, sample them, or treat these nodes as special cases.
• Precompute what's stable. Road networks use contraction hierarchies, which add shortcut edges ahead of time and make continent-scale routes answerable in milliseconds. Recommendation systems precompute candidate sets offline and rank them online.
• Cache hot subgraphs. If 80% of queries touch the same neighborhoods, keep those in memory close to the application.

Graph databases: query tuning

Native graph databases store adjacency directly, so following an edge costs a pointer hop rather than a join. They still need tuning.

Anchor the traversal with an index

A query should start from a small, indexed set of nodes:

// Slow: scans every Person node looking for a match
MATCH (p:Person)-[:FOLLOWS]->(f)
WHERE p.email = '[email protected]'
RETURN f

// Fix: create an index so the start node is found directly
CREATE INDEX person_email FOR (p:Person) ON (p.email);

Bound variable-length paths

// Dangerous: unbounded, can explore the whole graph
MATCH path = (a:Account)-[:TRANSFER*]->(b:Account)

// Safe: explicit bounds plus early filtering
MATCH path = (a:Account {id: $id})-[t:TRANSFER*1..4]->(b:Account)
WHERE all(x IN t WHERE x.amount > 1000 AND x.at > $since)
RETURN path LIMIT 50

Read the plan

Use the database's EXPLAIN or PROFILE output and look for:

• Full label scans where you expected an index seek.
• Cartesian products caused by disconnected patterns in one MATCH.
• Very high "db hits" on an expand step, which usually means a supernode or a missing filter.

Keep relationship types specific

[:RELATED_TO {kind: 'purchase'}] makes the engine load every relationship and then check a property. [:PURCHASED] lets it skip unrelated edges completely. Specific relationship types act like a free index.

Relational databases can do graph work too

For moderate graph sizes, a recursive CTE in PostgreSQL is often enough:

WITH RECURSIVE reports AS (
    SELECT id, manager_id, 1 AS depth
    FROM employees WHERE id = $1
  UNION ALL
    SELECT e.id, e.manager_id, r.depth + 1
    FROM employees e
    JOIN reports r ON e.manager_id = r.id
    WHERE r.depth < 6
)
SELECT * FROM reports;

Index the join column (manager_id), always add a depth limit, and guard against cycles if the data can contain them.

Summary

1. Match the algorithm to the question: BFS for hops, Dijkstra or A* for weights, bidirectional search when both ends are known.
2. Store graphs compactly: dense integer IDs and CSR for read-heavy workloads.
3. Shrink the search: bound depth, filter during traversal, and handle supernodes deliberately.
4. In graph databases, anchor on indexes, bound path lengths, and read the plan.

Most graph performance problems come from exploring far more of the graph than the question requires, so these steps focus on limiting that.