Implementations of the present disclosure include providing, at each node in a set of nodes of a database system, a table partition of a plurality of table partitions, the plurality of table partitions being provided by partitioning a table using a primary key, providing, at each node in the set of nodes of the database system, a secondary index partition of a plurality of secondary index partitions, each secondary index partition including a replicate table of at least a portion of the table, the plurality of secondary index partitions being provided by partitioning the table using one or more secondary keys, and for at least one operation executed on a table partition, executing a replication protocol to replicate the at least one operation on a secondary index partition that corresponds to the table partition.