A data store may implement dynamically assign storage locations to logical partitions according to query predicate indexes. Query predicate indexes may be maintained for individual storage locations in a data store that indicate whether storage locations store data values that do not satisfy a query predicate. The query predicate indexes may be evaluated to assign the storage locations to one or multiple logical partitions. The logical partitions may then be utilized to provide access to data stored in the data store. In some embodiments, a logical partition may be a remote storage partition that identifies data in storage locations to copy to a remote data store.