WALK: A Workload-Aware Learned Kd-Tree
摘要
The efficient extraction of large-scale data is crucial in the era of big data. To swiftly and effectively retrieve required data from vast datasets while avoiding scanning irrelevant data, it is essential to perform effective scanning and filtering operations on multidimensional data tables. Databases typically create clustered indexes on one-dimensional or multidimensional data, such as B-tree and R-tree, or employ advanced dimensionality reduction techniques like space-filling curves (e.g., Hilbert curves) to reduce multidimensional data to one dimension. However, these index structures are constructed based solely on the data itself, disregarding the impact of workload distribution characteristics on the index structure. Consequently, they cannot directly optimize an important metric: the amount of accessed query data which significantly influences query performance. We propose a novel index structure called WALK along with a greedy construction method to address this issue. WALK is a multidimensional learned index structure optimized for in-memory operations that can automatically adjust its structure according to different datasets and workloads. Experimental results demonstrate that WALK’s range query performance is 2 \(\times \) faster than Kd-tree, 6 \(\times \) faster than Qd-tree, and 1.5 \(\times \) faster than LK, while consuming less memory and supporting updates. By considering both data and query factors during index construction, WALK significantly enhances query efficiency and resource utilization, providing a robust solution for managing and querying large-scale multidimensional data in the era of big data.