How Graph Stores Index the Graph

Wikidata's public query service holds more than 16 billion triples and grows by roughly a billion a year. In May 2025 its operators stopped trying to scale one instance and split the graph in two, serving scholarly articles from a separate endpoint, on the stated grounds that the Blazegraph backend was nearing its capacity at Wikidata's size (Wikidata, WDQS graph split). A poster the following August put the two halves at about 8.7 billion and 8.4 billion triples. Graph storage is not a solved problem, and the reasons are visible in the index design.

One table, six orderings

An RDF store has a single logical table of three columns and no useful column statistics, which inverts the usual relational situation. The standard response is to index every permutation of the three positions: SPO, SOP, PSO, POS, OSP, OPS. Any triple pattern, whatever combination of positions is bound, then becomes a prefix scan over one of the six.

Hexastore made the argument explicitly, indexing RDF in all six orderings and reporting speedups of up to five orders of magnitude against the vertical-partitioning designs of the time, at the price of a worst-case fivefold increase in index space (Weiss, Karras & Bernstein, 2008, Hexastore: Sextuple Indexing for Semantic Web Data Management, PVLDB 1(1)). RDF-3X, from the same year, added aggregated indexes on partial keys (SP, PS, SO, OS, PO, OP) so that counting and projection queries never touch the full triple.

Underneath both sits dictionary encoding: every IRI and literal is mapped to a fixed-width integer id once, so the indexes store compact tuples of integers and string comparison happens only at the dictionary boundary. The dictionary is usually the first thing to become a bottleneck on load, not the indexes.

Why joins decide the query plan

A SPARQL basic graph pattern is a multiway self-join over that one table. Evaluate it as a sequence of binary joins, as a classical optimiser would, and you can materialise intermediate results far larger than the final answer, which is the standard pathology on cyclic patterns such as triangles.

The theory that fixed this starts with the AGM bound of Atserias, Grohe and Marx, a tight bound on the maximum output size of a full conjunctive query given the sizes of its input relations. If a bound on output size exists, an algorithm can aim to run in time proportional to it, which Ngo, Porat, Ré and Rudra showed is achievable. Veldhuizen's leapfrog triejoin made the result practical: it is worst-case optimal in the same sense, it runs on ordinary sorted B-tree structures with nothing more exotic than sorted intersection, and it stays optimal on finer-grained instance classes, running in \(O(n \log n)\) on one class where the earlier algorithm is \(\Theta(n^{1.375})\) (Veldhuizen, 2014, Leapfrog Triejoin: A Simple, Worst-Case Optimal Join Algorithm, ICDT).

The practical consequence is that a modern graph engine's join operator intersects sorted id lists across all patterns simultaneously, variable by variable, rather than joining two patterns at a time. The six-permutation index is exactly what makes those intersections cheap, which is why the index design and the join algorithm are one decision rather than two.

Property graphs store adjacency instead

A native property-graph engine stores a node record that points at its first relationship, and relationship records that form doubly linked lists threaded through both endpoints. Traversing from a node to its neighbours is pointer chasing with no index lookup, so the cost of one hop depends on that node's degree and not at all on the size of the graph. An RDF store pays a B-tree descent per hop, which is logarithmic rather than constant but over a far larger structure.

What property graphs give up is the ability to say anything about a statement. An edge can carry properties, but there is no edge-of-an-edge, so provenance about a relationship has to be modelled as a node, at which point the model has reinvented reification. They also had no standard query language until GQL, published as ISO/IEC 39075 in April 2024 and, by the standards body's own framing, the first new database query language ISO had published since SQL in 1987.

When it breaks

Six permutations cost roughly fivefold space. On a billion-triple graph the limiting resource becomes load time and memory for the indexes, not query latency. This is the first thing to give when a graph grows, and it is why ingest rate and query rate have to be capacity-planned separately.

Skewed predicates defeat the prefix scan. rdf:type may appear on every subject in the graph. A POS lookup bound only on that predicate is a scan of the whole store wearing an index's clothes, and the planner's estimate for it will be badly wrong.

Cardinality estimation on self-joins is unreliable. One table, no per-column histograms worth the name, and every join is a self-join, so estimates compound in the worst way. Engines compensate with characteristic sets, sampling or adaptive execution, and all three fail on the same queries: long chains over high-degree hubs.

There is a real scale ceiling. The Wikidata operators' decision to split the graph rather than scale the backend is the clearest public evidence that single-instance triple stores top out well below what people assume, and that a split is a breaking change for every query written against the old endpoint.

Materialised entailment collides with index maintenance. Each derived triple has to be inserted into all six permutations, so a materialising store pays the fivefold write amplification on inferences as well as assertions.

Dictionary churn is permanent. Ids are assigned once and never reclaimed in most designs, so a pipeline that mints fresh IRIs per load grows the dictionary without bound even if the triple count is flat.