2019/01/22 by Darshana Balakrishnan, Balakrishnan, Darshana, Lukasz Ziarek +3 · 1 voice
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.1901.07627
openalex publication_date 2019/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Creating or modifying a primary index is a time-consuming process, as the index typically needs to be rebuilt from scratch. In this paper, we explore a more graceful "just-in-time" approach to index reorganization, where small changes are dynamically applied in the background. To enable this type of reorganization, we formalize a composable organizational grammar, expressive enough to capture instances of not only existing index structures, but arbitrary hybrids as well. We introduce an algebra of rewrite rules for such structures, and a framework for defining and optimizing policies for just-in-time rewriting. Our experimental analysis shows that the resulting index structure is flexible enough to adapt to a variety of performance goals, while also remaining competitive with existing structures like the C++ standard template library map.