The disclosure generally describes computer-implemented methods, software, and systems, including a method for storing information. In a database including plural records having time-related characteristics, a time-related partition is identified for relocating records in the partition to secondary storage. For each pair in one or more pairs of different time-related characteristic values of the records in the partition, a time-related distance is determined between the different time-related characteristic values. The time-related distances are aggregated for the partition. Information is stored in an index in primary storage that identifies the aggregated time-related distances for the partition.