A search index for searching a graph-based data store can include triple entries, each triple entry having a posting list value, at least one intersection identifier associated with the posting list value, and at least one result identifier associated with the intersection identifier. The index may also include search entries having a posting list value that corresponds to a text search aid. The search index may also include pre-computed path entries, such as chain path entries and converge path entries. The index may also include bucket posting lists representing ranges of object values for a particular predicate and proximity posting lists that include one or more entities and the areas of a location hierarchy with locations within the proximity of the entity. Queries for the data graph may have at least two stages, each stage being associated with a posting list from a graph index.