Commit history as a query problem

Git’s version control duties include more than just coordinating collaborative edits to a shared repository. It is also the tool developers use to investigate the repository’s past. Viewed through a database lens, these history investigations form a distinct class of queries, and the shape of commit data has a direct influence on how Git answers them.

Several common history queries rely purely on commit structure; file-level history is left for a separate discussion.

Recent history and reachability

The most frequent interaction with history is git log, which displays recent commits on the current branch. Internally, this triggers a walk that starts from known commits (such as branch tips) and follows parent pointers until all relevant commits have been emitted. The command can be adapted to compare histories across branches or to render a graphical view of the graph.

Reachability questions also show up in containment queries. git tag --contains lists tags that can reach a given commit, while git branch --contains does the same for branches. These are practically useful—for instance, when you need to know which product versions include a particular bugfix.

Finding a merge base

Merges use a three-way merge algorithm, which requires a third commit: the merge base. A merge base is any commit reachable from both sides of the merge, though the algorithm performs better when the base is as close as possible to both tips. Git therefore tries to choose a single merge base that is not reachable from any other candidate base. In some histories this “best” base is not unique, and Git will report all such bases.

The git merge-base command emits the object ID of the chosen merge base for two given commits. Related to this is the concept of a boundary commit when examining the range B..A: a commit is on the boundary if it is reachable from both A and B, and at least one of its children is reachable from A but not from B. Boundary commits help visualize where two histories diverge and can reveal the unique best merge base.

The structure of commit data

A commit stores a snapshot of the repository along with several pieces of metadata:

  • The tree object ID representing the root of the worktree at that point in time.
  • Parent commit object IDs, which determine the commit type:
    • Zero parents: a root commit.
    • One parent: a typical commit, often called a patch.
    • Two parents: a merge.
    • Three or more parents: an octopus merge.
  • Author and committer name/email, which can differ.
  • Author and committer timestamps.
  • A commit message with optional metadata trailers, such as Co-authored-by:.

Treating commits as vertices in a directed graph—where each commit has edges to its parents—makes it possible to model history as dots and arrows.

Why general graph databases don’t fit

General-purpose graph databases are designed for queries that stay shallow: walk a few relationships from a node before stopping. Social networks are the canonical example, where nearly every node is within a short distance of any other. Those relationships are usually unordered and highly variable in count.

Git inverts that pattern. Commands rarely target a commit by its object ID; instead they start from a small set of references and may need to walk thousands of parent edges. Parent order also matters—especially the first parent, which by convention tracks the previous state of the branch before a merge. Checking out a pull request merge history with git log --first-parent depends on this ordering. This query profile requires specialized storage rather than a generic graph engine.

The commit-graph file as an index

Without help, walking history forces Git to load and parse each commit’s full plain-text content from the object store just to discover its parents. That is acceptable for small repos, but as history grows, the overhead of object lookup and header parsing dominates. Git solves this with the commit-graph file, which you can generate with git commit-graph write --reachable. Most users get it automatically through git gc --auto or background maintenance.

The file acts as a query index over the most expensive parts of history traversal. It stores parent relationships, commit dates, and root tree information in a compact, structured form, avoiding repeated decompression and parsing of commit objects unless a commit must be displayed.

Conceptually, the commit-graph resembles two database tables. The primary table has one row per commit with columns for object ID, root tree, date, and the first two parents. A -1 value marks the absence of a parent, which covers root commits and ordinary patches. Since most commits have at most two parents, that is enough. If a commit does have three or more, its second-parent column holds a special bit flag that points into a second table of overflow edges. That table stores the extra parents as a list, with the last entry carrying a flag to signal the end.

The file is closed under reachability: any commit stored in it also has its parents stored in it. That invariant lets the file reference parents by row number rather than by full object ID. This constant-time parent lookup is both fast and compact—each parent costs just four bytes.

Speeding up the walk loop

Without the commit-graph file, visiting a commit follows a costly loop:

  1. Start with an object ID.
  2. Locate that object in the object store.
  3. Load and decompress the object from disk.
  4. Parse the content to extract parent object IDs.

With a commit-graph present, Git intercepts this flow with an extra step before each generic object lookup: a binary search for the object ID in the commit-graph. That search is logarithmic in the number of commits—not in the total object count. If the commit isn’t found there, Git falls back to the original path. Once a commit’s position is known, its parent rows can be fetched immediately by position with no further binary searches.

The impact shows up in commands like git rev-list, which prints only object IDs and thus isolates the cost of walking edges from the cost of formatting output. core.commitGraph toggles the use of the file. The Linux kernel repository, with more than a million commits, is a practical test case: avoiding the expensive per-commit parsing yields on the order of a 6x speedup in these examples.

That is a solid constant-factor gain, but further improvements require algorithmic changes beyond skipping the parsing overhead.

Making reachability queries faster with generation numbers

Two of Git's most common questions about commits are “can commit A reach commit B?” and its inverse. Commands such as git tag --contains and git branch --contains rely on fast answers to those queries. While proving that a path does exist from one commit to another is expensive — it requires walking the whole path — proving the opposite is much cheaper when there is extra data available.

The commit-graph file exists specifically to store data that is not part of the normal commit object format. One such piece of data is a generation number. The key property any generation number must satisfy is simple: if commit A has a smaller generation number than commit B, then A cannot reach B. This gives Git a negative reachability index — it can rule out entire portions of the graph without walking them.

The topological level

The most basic generation number is the topological level, defined recursively:

  1. A commit with no parents has topological level 1.
  2. Any other commit has a topological level one greater than the maximum topological level of its parents.

Because every commit has a strictly larger topological level than its parents, any commit reachable from a given commit always has a smaller topological level. That satisfies the generation number property.

Note that equal generation numbers intentionally say nothing. Commits that exist in the repository but are not yet in the commit-graph file have no precomputed generation number. Git treats these as having generation number infinity, which is larger than any stored value. Equality is left as an unknown state rather than special-casing these commits.

Cutting walks short

Reachability queries like git tag --contains <b> or git merge-base --is-ancestor <b> <a> walk backward from a starting point looking for a target. Without generation numbers, a walker that cannot find the target will end up traversing the entire history. The old heuristic was a breadth-first search ordered by commit date — that helps when the target exists, but does nothing when it does not.

Generation numbers enable two improvements to this walk:

  • A hard cutoff: when a commit's generation number is below that of the target, it cannot possibly lead to the target, so exploring it is pointless. This is especially effective when the target is recent, eliminating large swaths of old history immediately.
  • Depth-first search on the first parent: in typical repositories the first parent of a merge represents the previous branch tip, while later parents introduce relatively small topic branches. Tracing the first-parent chain drops the walk quickly toward the generation-number cutoff where the target is likely to sit, often finding the relevant merge far sooner than a breadth-first scan would.

Depth-first search without the generation-number cutoff would actually be a regression — it would spend most of its time diving into very old commits. Combined, the two techniques produce substantial speedups for reachability checks. Notably, git tag --contains must consider every tag, including ones too old to reach the target; the cutoff prevents those walks from starting at all. For code-level details, the general-purpose can_all_reach_from_with_flags() method shows how the presence of generation numbers selects different algorithms.

Incremental topological sorting

Generational data also accelerates git log --graph, which needs a special ordering to render its visualization. Topological sorting has a hard requirement — every commit must appear before its parents — and a soft one: when a merge appears, the commits it introduced (those reachable from its second parent but not from its first) should be shown first. The classic approach, Kahn's algorithm, first walks the entire reachable set to compute in-degrees (how many times each commit appears as a parent) and then walks again, only emitting commits whose in-degree has dropped to zero.

That was impractical for interactive use: on a large history like the Linux kernel, showing the first 100 results via git log --graph -n 100 took over seven seconds because the in-degree pass had to touch every reachable commit before a single line could be printed.

The fix is to interleave both Kahn passes using generation numbers. Git maintains the states of two simultaneous walks. The in-degree walk uses a priority queue ordered by generation number and computes just enough in-degrees that the output walk can safely emit commits. Before adding a commit to its output stack, the output walk checks that the in-degree walk's maximum remaining generation is below that commit's generation — guaranteeing no unseen commit could still be its parent. This alternation means Git outputs the first page of results after exploring only recent commits, not the entire history.

The performance difference is most dramatic on unbounded ranges, where the old algorithm's initial walk covered everything. When a commit range like v5.18..v5.19 is used, a third preliminary walk filters to the range itself, helping the old code too — but the in-degree pass still sweeps that full range, while the interleaved version stays ahead as long as the range is substantial.

Corrected commit dates

Topological level is the smallest integer that can serve as a generation number, which makes it simple but not always optimal. Consider a merge that brings in a fix based on a very old commit — common when a developer wants an early fix on maintenance branches. The innocent-looking merge gives that ancient commit a small topological level relative to its contemporaries, steering generation-number-guided walks toward the wrong parts of the graph.

Commit date is a better heuristic for limiting walks, but it cannot be trusted as a strict generation number — clock skew can make a child appear older than its parent. A Google Summer of Code project in 2020 resolved this with the corrected commit date:

  • A root commit's corrected commit date is its own date.
  • Otherwise, take the maximum corrected commit date of the parents; if that exceeds the commit's own date, use that maximum plus one, otherwise use the commit's own date.

This uses the commit date whenever it is safely usable, and only adjusts upward to maintain the generation-number invariant. Corrected commit dates both fix the pathological slowdowns from old-based fixes and typically give slight improvements over topological level. Recent Git versions default to corrected commit dates; users can revert to the older behavior via the commitGraph.generationVersion config option.

Indexing the filesystem

The commit-graph file is a query index tailored to Git’s reachability and commit-ordering questions. Every git log --graph, branch merge-base check, or fetch negotiation walks that structure instead of parsing raw commit objects. The format trades a little extra disk space for a large reduction in object parsing, which is exactly the same trade an application database makes when it maintains a specialized index for a hot query pattern.

The same principle applies one level up. Git’s file-history queries (git log -- path) are expensive because they combine tree-diffing with commit-graph traversal. In a repository with millions of commits, walking every commit that touches anywhere in the tree is wasteful when only a handful of paths are of interest. Git needs a mechanism to prune commits that could not have modified a given path, without first parsing each commit’s tree.

That mechanism exists, and it lives inside the commit-graph file itself as a second index. It records, for each commit, the sets of files and directories that the commit changed relative to its parents. A file-history query can then consult this index and skip whole regions of the commit graph that contain no relevant entries. The index is not a full-text search over history; it is a Bloom-filter-like structure that answers “did this commit touch that path?” with a small false-positive rate and no false negatives at the cost of position-dependent path hashing.

Because the index is stored inside the commit-graph, it is written and refreshed alongside the core commit-ordering data and remains available to any reader that loads the graph. This makes large-repository file history queries dramatically faster, at the price of additional computation during commit-graph writes.

Before that index exists, Git falls back to the slower method: it walks the commit graph and parses each commit’s tree to compute a diff, only to discard most results. The optimized path is an option, not a default. You can enable it explicitly, typically in one of three ways:

  1. Run git commit-graph write --reachable manually.
  2. Set fetch.writeCommitGraph to true so writes happen during fetches.
  3. Run git maintenance start to have Git schedule background maintenance that writes and maintains the graph.

If you work with large Git repositories and haven’t already, make sure at least one of those is in effect. The background maintenance route is the most hands-off and keeps incremental updates flowing without shelling out to a separate maintenance script.

The next step is to look at exactly how file-history queries use the tree-object structure together with the commit graph — and the file-history index stored inside it — to limit object parsing in large repositories.