WALDEN: Workload-Aware Learned Tree Index

The rapid development of learned indexes brings a surge in the indexing performance of database management systems. It treats an index as a learned model and learns a mapping between keys and their values’ positions in the database. Existing works mainly focus on improving the regression accuracy of the model itself. However, we observe that the real-world query workload is biased and keys have different access frequencies, which indicates that keys are not equally important. Simply optimizing the regression accuracy by treating keys equivalently may not be the most effective for the workload. We propose the novel Workload-Aware Learned Tree Index (WALDEN) which sets weights to keys and arranges important keys into the shallower levels of the tree index. Specifically, an algorithm which minimizes keys’ weighted collision degree is devised to build this workload-aware tree index efficiently. Furthermore, we also design an index update mechanism to monitor and respond to any significant shift in the query workload distribution. Comprehensive evaluations are conducted on synthetic workloads on real datasets undercommon settings, which show that WALDEN outperforms the state-of-the-art learned indexes with an improvement between 9.7 and 500% in terms of the average throughput.