When a search query is received, a plurality of partition indexes are searched using the set of search terms in the search query. Each partition index corresponds to a partition of a document index. The search of each respective partition index identifies a subset of a plurality of document index sub-partitions corresponding to the respective partition index. Next, the search query is executed by only those document index sub-partitions identified by the subsets, thereby identifying documents that satisfy the search query. By using the partition index to reduce the number of document index sub-partitions searched while executing a search query, the execution of the search query is made more efficient.