通过多模型数据库系统中的索引选择方法优化存储策略：一项调查

《Data & Knowledge Engineering》：Refining storage strategy through index selection methods in multi-model database systems: A survey

本文系统分析多模型数据库系统中的索引选择问题，对比关系型、文档型、图数据库等主流系统的存储策略与索引机制，评估现有单模型数据库索引算法在多模型环境下的适用性，揭示算法在数据异构性、查询模式多样性及计算复杂度方面的局限性，并提出未来研究方向。

　　

Filip Mihá?|Jáchym Bártík|Pavel Koupil

查尔斯大学软件工程系，捷克共和国布拉格Malostranské náměstí 25号

摘要

多模型数据库系统结合了传统数据库系统和NoSQL数据库系统的优势。然而，这些系统的管理具有挑战性，因为用户必须为数据设计合适的存储策略。存储策略中最具影响力的因素之一是索引的选择。索引可以显著提高查询性能，但它们需要额外的存储空间和维护开销。在单模型数据库管理系统（DBMS）的背景下，索引选择问题已经得到了充分研究，但在多模型数据库系统的背景下，相关研究仍然不足。

我们通过调查当前最先进的索引选择算法，并评估它们在其他DBMS中的适用性来解决这一问题。研究结果揭示了现有算法的优点和缺点，并强调了为多模型数据库系统开发专用算法的必要性。此外，我们还提出了开放性问题，并指出了该领域未来的研究方向。我们的研究为多模型DBMS的高效索引选择算法的开发奠定了基础。

引言

在过去几十年中，我们存储和访问数据的方式发生了快速变化。最初，数据存储在传统的单节点关系型数据库中，这些数据库旨在处理规范化和结构化的数据。开发人员必须提前定义数据的模式，并以结构化的方式存储数据。然而，随着数据量的增加，关系型数据库在扩展性方面变得过于缓慢且成本高昂。此外，由于需要存储非规范化和非结构化的数据（如日志和多媒体内容），NoSQL数据库应运而生，这些数据库旨在处理非结构化数据并在分布式系统中水平扩展。同时，新的数据模型及其相应的DBMS也出现了，每种模型都针对特定的数据类型和用例进行了优化。

近年来，各种应用程序和设备生成的数据呈指数级增长，这推动了对更先进和复杂的数据库系统的需求。开发人员越来越多地需要处理多模型数据，即在单个系统中结合不同的数据模型。这导致了多模型DBMS的出现，它们将多种数据模型集成到一个统一的后端中，使用户能够在同一平台上管理和查询关系型、文档型、图型和键值型数据。虽然这些数据库能够实现高效的跨模型操作和数据整合，但在存储策略和性能优化方面带来了新的挑战，因此人们进行了大量的研究以找到针对给定多模型数据的最佳存储策略[1]、[2]、[3]、[4]。

除了多模型数据，现代应用程序还经常处理多模态数据，即来自不同模态（如文本、图像、视频和地理空间信息）的数据需要一起存储和查询。多模态数据库需要专门的索引技术，包括用于文本的倒排索引、用于空间数据的R树以及用于高维数据（如图像）的多索引哈希。在单个系统中处理如此多样化的数据类型引入了复杂性，传统的索引选择方法（针对单模型或结构化数据设计）无法直接解决这些问题[5]。因此，需要新的研究来适应和扩展这些索引选择算法，以应对多模态和多模型数据库带来的挑战。

尽管选择正确的数据模型组合对数据库性能至关重要，但这并不是唯一因素。例如，有效的索引选择和物化视图对于优化性能也是必不可少的[6]。此外，在多模态系统中，索引类型必须针对每种数据模态进行定制，自动化索引选择算法必须能够处理多种数据类型的多样化查询模式。

本文重点关注多模型和多模态DBMS中的索引选择问题。这个问题在单模型数据库领域已经得到了充分研究[7]、[8]、[9]、[10]、[11]、[12]，其对查询性能的影响已经得到很好的理解，并且一直在改进[7]。然而，随着数据模型复杂性的增加，特别是在多模型和多模态数据的情况下，对索引管理进行更高层次抽象的需求变得明显。我们认为，必须开发新的算法来自动化和优化这些复杂环境中的索引选择，以确保现代DBMS能够高效扩展并满足现实世界应用不断变化的需求。

本文的主要目标可以总结如下：

• •
  各种DBMS中的索引分析 首先，我们分析了最流行的DBMS，描述了它们的用例，并比较了它们的典型工作负载。接下来，我们全面分析了这些DBMS使用的索引策略。我们主要关注它们支持的索引类型以及实现这些索引使用的数据结构。
• •
  现有方法的分析 由于索引选择在关系型数据库的背景下已经是一个被充分研究的问题[7]，我们首先分析了当前最先进的算法，并挑选出可能适用于多模型数据的算法。我们研究的算法在方法、实现和复杂性方面各不相同。我们还考虑了基于机器学习的算法，尽管这些算法目前不如其他算法先进，但它们对未来索引选择算法的发展具有极大的潜力[6]。
• •
  它们的更广泛适用性验证 我们考虑了所选算法在其他DBMS中的适用性，并比较了每种数据库系统最适合的算法。如果算法不适用，我们会分析原因并提出改进的想法。
• •
  开放性问题的提出 最后，我们提出了多模型和多模态DBMS中索引选择研究的开放性问题。

第1节提供了流行数据模型及其相应DBMS的概述，并根据实际应用、典型查询、优势和劣势对这些模型进行了比较。第2节介绍了本文中使用的定义和符号。第3节回顾了最先进的索引选择算法，并按方法（例如机器学习、整数线性规划、贪心算法）对它们进行了分类。第4节根据不同数据模型的适用性、支持的索引类型范围和计算复杂性比较了选定的方法，并评估了它们对多模型和多模态数据的适用性。第5节提出了多模型DBMS和索引选择未来工作的挑战和开放性问题，最后是结论。

章节片段

流行数据库系统的回顾

有数百种DBMS，其中超过50%被认为是多模型系统[13]。每种系统都有不同的用途，适用于不同的数据类型。如果我们要将索引选择算法应用于多模型DBMS，就需要了解数据库系统、支持的数据模型、它们的特点以及索引如何用于优化查询性能。

本章介绍了多模型和NoSQL数据库系统中使用最流行的数据模型。

定义与符号

在本节中，我们提供了本文中使用的基本定义和符号。文献中使用了多种不同的符号，因此我们使用了我们在参考文章中最常见的符号。

索引选择算法

正确的数据库索引选择（称为索引选择问题ISP）可以对数据库系统的性能产生显著影响。当索引选择得当并得到正确使用时，可以加快查询执行速度[7]。然而，选择正确的索引需要仔细考虑数据模型、查询模式和应用工作负载。如果添加过多的索引，写入性能可能会下降，存储需求也会增加；而索引数量不足则可能导致

算法比较

第3节讨论的算法最初是在关系模型上开发和评估的。在本节中，我们比较了与多模型数据库相关的关键特性，并验证了哪些算法适用于非关系型数据。

表10展示了多模型DBMS重要的算法及其特性。如前所述，大多数被研究的算法属于贪心算法家族（因为索引选择问题是NP完全问题

开放性问题与挑战

基于我们对最先进索引选择算法及其在不同数据模型中适用性的分析，发现了一些开放性问题。在本节中，我们讨论了这些问题和挑战，并提出了未来研究的可能方向。我们将这些问题和挑战分为五个类别：通用、负载分布、候选项选择、查询成本和候选项枚举。最后四个类别基于

结论

在本文中，我们朝着开发高效且可能自主的多模型DBMS迈出了下一步。我们通过分析关系型DBMS中当前使用的最先进索引选择算法来实现这一目标。然后，我们验证了这些算法在其他数据库系统（特别是图型、键值型、文档型和列式DBMS）中的适用性。通过我们的分析，我们提出了开放性问题、挑战和想法，这些可以帮助未来的索引开发

CRediT作者贡献声明

Filip Mihá?：调查、撰写——初稿、形式分析、方法论。Jáchym Bártík：验证、资金获取、撰写——审阅与编辑。Pavel Koupil：形式分析、方法论、监督、可视化、撰写——审阅与编辑、调查、项目管理、验证、撰写——初稿。

利益冲突声明

作者声明他们没有已知的可能会影响本文所报告工作的竞争性财务利益或个人关系。

致谢

本文基于Filip Mihá?的论文[46]。这项工作得到了GA?R项目编号23-07781S和GAUK项目编号292323的支持。

Filip Mihá?于2023年在捷克布拉格的查尔斯大学获得了计算机科学学士学位，专攻人工智能。他目前正在同一领域攻读硕士学位。他的研究兴趣包括人工智能、NoSQL数据库和软件工程。