KOE: A Key Distribution-Oriented Performance Estimation Framework for Diverse Index Structures

Index structures are a fundamental component of web search and modern database systems, playing a crucial role in enabling efficient data retrieval and management. However, selecting the most appropriate index structure for specific scenarios and workloads is a highly challenging task. This is especially true for learned indexes, where the cumulative distribution characteristics of stored keys not only affects performance but also impacts the robustness of the index. In this paper, we propose a key distribution-aware framework called KOE, to estimate the performance and robustness of various index structures. The framework predicts two critical metrics-performance and memory consumption-across various data distributions and workloads, integrating both temporal and statistical characteristics through a novel learning-based approach, denoted as TStatE. Experimental results demonstrate that KOE provides accurate, data-driven performance and robustness estimation, facilitates systematic index selection and optimization, and can effectively generalize across different index types and workloads, making it a robust tool for exploring trade-offs in index deployment.