Towards Systematic Index Dynamization

Douglas B. Rumbaugh

doi:10.14778/3681954.3681969

2024-08-30

PRE

Douglas B. Rumbaugh *

Dong Xie

DOI：10.14778/3681954.3681969

原文链接

原文求助

摘要

En 中文

在利用复杂领域特定查询分析大规模数据集方面存在显著兴趣。在许多情况下，这些查询可以通过专用索引进行加速。然而，开发实用索引较为困难，因为数据库通常需要额外功能，如更新、并发支持、崩溃恢复等。为缓解这一问题，主要有三条研究方向：（1）自动索引构建/调优，其通过核心数据结构基元构建索引以优化特定工作负载；（2）通用索引模板，其泛化常见数据结构（如B+树）以支持自定义数据类型上的自定义查询；（3）数据结构动态化框架（如Bentley-Saxe方法），其将静态数据结构转换为可更新结构，同时限制额外查询开销。前两者局限于非常具体的查询和/或数据结构，因此不适合构建通用索引动态化框架。后者在通用性方面更有前景，但在查询类型、删除支持及性能调优方面存在局限。本文讨论了经典索引动态化技术的局限性，并提出了一条通向更通用、更系统化解决方案的路径。我们通过将其实现为C++20元编程库，并对四种示例查询及其对应静态索引结构进行案例研究，展示了本框架的可行性。借助该框架，许多理论/早期阶段的索引设计可轻松扩展更新支持，并提供了查询/更新性能权衡的广泛调优空间。这使索引设计者能专注于高效数据布局和查询算法，从而显著缩小创新索引设计与部署之间的差距。