Contributors: Aneesh Raman, Subhadeep Sarkar, Matthaios Olma, Manos Athanassoulis
Indexing in data systems can be perceived as the process of adding structure to the incoming, otherwise unsorted data. If the data ingestion order matches the indexed attribute order, the index ingestion cost is entirely redundant and can be avoided altogether. In this work, we identify sortedness as a resource that can accelerate index ingestion. We propose a new sortedness-aware (SWARE) design paradigm that pays less indexing cost for near-sorted data. When applied to a classical index like the B+-tree SWARE offers a 9× speedup for write intensive workloads and a 4× benefit in mixed workloads by exploiting data sortedness.