对数据系统、数据结构和算法的设计进行了调查。随着数据的长，硬件不断变化，新的应用越来越频繁。一据密集型应用程序希望平衡和控制云上的内存需求、读取成本、写入成本和货币成本。为了满足当前场景的确切需要，需要定制数据系统、存储和计算解决方案。为了跟上应用程序和工作负荷的快速发展，这些系统应该快速、几乎自动地合成，尽可能地从循环中删除人类系统设计师和管理员。此外，该系统应学习过去和当前的系统性能和工作负载模式，以不断调整其设计。 我们调查了1)自主设计和2)学习数据系统的新趋势，以及这些技术如何应用于关系NoSQL大数据系统和广泛的数据科学应用。我们关注该技术的最新研究进展和实际应用，以及其整合带来的许多开放研究机会。我们特别强调如何促进数据结构、算法和查询优化，以及机器学习的设计和解决方案可能设计空间的详细映射，以创建定制系统。我们还定位并联系了过去在自动调整、模块化/可扩展和自适应数据系统方面的开创性系统设计和研究，以突出新的挑战过去和新技术的机会。

Offline Indexing 离线索引是自调优数据库系统的最早方法。目前，所有主要数据库产品都为自动数据库物理设计提供了自动调优工具。自动调优工具主要依靠假设分析和与优化器的密切交互来决定哪些索引对给定的工作负荷可能更有用。离线索引需要数据库管理员（DBA）大量参与。具体来说，DBA调用工具并提供其输入，即代表性工作负载。对给定的工作量进行分析，并建议进行适当的物理设计。

Online Indexing 系统继续通过在线索引监控工作量，并定期重新评估物理设计。System COLT是最早的在线索引方法之一。COLT对工作负荷进行持续监控，并在特定时期定期进行，即每N次查询，重新考虑物理设计。物理设计可能需要创建新索引或删除旧索引。COLT为了获得成本估计，需要多次调用优化器。后来提出了一种更轻的方法，即需要更少的优化器调用。通过动态构建完整的索引，同时查询相同的数据，共享扫描算子，软索引扩展了以前的在线方法。 在线索引的主要限制是，物理设计的重组可能是一项昂贵的行动，a）完成需要很多时间，b）需要大量的资源。这意味着在线索引主要适用于查询模式变化不太频繁的中等动态工作负荷。否则，当我们完成物理设计时，工作负荷可能会再次改变，导致性能不佳。

Adaptive Indexing and Layouts 自适应索引是自调数据库中的一种轻量级方法。自适应索引解决了动态工作负载离线和在线索引的局限性；作为查询处理的一部分，它通过构建或优化部分和增量索引来响应工作负载的变化。也就是说，不需要DBA或离线处理。自适应索引通过使用轻量级操作对每个查询做出反应，可以立即适应不断变化的工作负荷。随着查询数量的增加，索引的细化程度越高，性能也越好。最近，随着对关系系统的大量研究，NoSQL基本存储在系统、更新、并发和时间序列数据管理中的适应性引起了广泛关注。通常，在这些工作中，布局会适应介绍的要求。类似地，通过实验、学习进行调优，通过机器学习进行调优可以使用测试反馈来调整设计的部分。 虽然自动调谐和自适应提供了为一系统实现许多不同性能特性的能力，但它们不会从根本上改变系统的特性，因为系统仍然在严格由其原始设计定义的狭窄设计空间内移动。

Modular/Extensible Systems and System Synthesizers         模块化系统是一种在计算机科学的许多领域都已探索过的想法：尤其是在数据库系统中，人们研究了这样一个概念，即以最小的实现工作量轻松添加数据类型，或以干净的接口添加即插即用功能和整个系统组件。模块化是系统构建特别是数据密集型系统的一个非常有前途的方向（因为没有单一的完美存储设计）。然而，在实践中，到目前为止，我们只看到具有“大型”组件的系统，这些组件实际上不允许系统彻底改变其行为，而是支持或不支持特定功能。

Generalized Tree Indexes         扩展性的一个很好的例子是关于广义搜索树索引（GiST）的工作。GiST旨在使用于索引的数据结构易于扩展，并以最小的工作量针对特定问题和数据进行裁剪。它是一个模板，一个抽象的索引定义，允许设计人员和开发人员实现一大类索引。最初的提议只关注记录检索，但后来的工作增加了对并发的支持，一个更通用的API，改进的性能，对生成的索引的选择性估计，甚至还有帮助调试的可视化工具。

Self-designed Systems         自行设计的系统依赖于映射系统中关键设计决策的可能空间的概念。例如，数据计算器引入了键值存储的设计空间。设计空间由所有设计定义，这些设计可以描述为“设计第一原则”的组合和调整。第一个原则是一个基本的设计概念，不能分解为其他概念，例如，对于数据结构设计：围栏指针、链接、时间分区等。直觉是，在过去几十年中，研究人员发明了许多基本设计概念，因此可以从这些概念中合成大量具有有趣特性的新有效设计。[31]中的设计空间涵盖了最先进的设计，但也揭示了可以衍生出大量额外的存储设计。作为类比，考虑化学中的元素周期表；它对现有元素进行了分类，但也预测了未知元素及其属性。同样，我们可以创建数据结构周期表，该周期表描述了比天空中的恒星更多的键值存储设计。类似的工作为数据库服务器的缓存一致性协议和并行算法的设计创造了设计空间。         自行设计的系统使用设计空间自动生成最适合目标工作负载和硬件的设计。要做到这一点，我们需要知道空间中的各个点在它们为生成的系统提供的性能属性方面是如何不同的。例如，学习成本模型是一种能够学习基本访问模式（随机访问、扫描、排序搜索）成本的方法，从中我们可以为给定的数据结构规范合成复杂算法的成本。反过来，这些成本可以被机器学习算法使用，机器学习算法迭代生成的数据结构规范来标记设计，并计算奖励，决定下一步尝试哪个规范。例如，使用遗传算法和动态规划的早期结果表明，此类方法具有自动发现接近最优存储设计的强大潜力。此外，设计连续体是另一个允许准确快速搜索最佳设计的方向。设计连续体是一个性能超平面，连接所有可能设计集中的特定设计子集。设计连续体实际上是设计空间的投影，是设计的“口袋”，我们可以在其中识别其成员之间的统一属性。早期结果表明，存在一个涵盖B树、LSM树和日志+索引键值存储的设计连续体。

Learned Systems         在学习系统中，传统的核心数据系统组件被模型取代。例如，学习的索引用模型替换数据结构的索引部分。模型可以是任何东西，从简单的线性模型、模型的层次结构到任意复杂的神经网络。反过来，数据结构可以是用于基本存储、二次索引或系统中所需的任何其他数据结构的结构。模型捕获数据属性，在许多情况下，使用通用的一刀切的数据结构设计很难捕获这些数据属性，该设计具有预定义的工作负载，并且支持良好。此外，在大多数情况下，模型将需要更少的数据来表示数据结构中所需的索引信息，从而导致设计的内存占用比标准设计少得多。这一点非常重要，尤其是在内存量是一个重要成本因素的云环境中。此外，用模型替换索引中基于键的元数据，有效地将遍历索引的成本从内存限制转移到CPU限制，这有利于现代硬件。学习索引的早期结果表明，在内存占用小得多的情况下，可以匹配甚至优于传统索引。         用模型替换传统系统组件的原则可以应用于数据系统设计的许多领域。例如，最近关于学习基数估计的工作表明，在解决数据库优化中最古老的问题之一方面取得了有希望的结果，该问题通常会由于陈旧的统计数据而导致糟糕的查询计划。此外，最近对学习优化器的研究表明，在优化具有多个连接的复杂查询计划方面有着很好的结果。SageDB是一个最新的数据系统整体设计系统提案，其中学习的组件在其设计中是一级公民。模型可以在更多领域提供帮助，例如，它们甚至可以用作存储旧数据或执行近似处理的数据表示方法。

Research Opportunities         与过去仅依赖自动调谐和自适应的设计相比，自行设计和学习系统的新机会是能够设计能够提供更广泛性能行为的数据系统。例如，自行设计的系统可以假设任何行为，只要它是其设计空间的一部分，而学习系统可以假设模型可以支持的任何行为。在这两种情况下，我们可以假设比固定的先验设计更多的行为。在两个方向上都有许多开放的研究问题，例如，对于自行设计的系统：有效搜索最优设计，快速高效地生成目标设计的代码，易于扩展支持的设计空间，对于学习系统：有效存储模型，用现代硬件高效执行复杂模型，性能结果的鲁棒性和可解释性。         此外，学习和自行设计的系统以及工作负载触发的自适应性的融合带来了令人振奋的研究和实践机会，现代技术采用了机器学习的自动调整。长期议程是建立具有模型和设计空间的系统，作为一等公民，同时能够适应查询工作负载以及自动调整任何暴露的旋钮。实际上，所有系统迟早都会暴露旋钮，例如，为了适应系统投入生产后出现的特殊性能或功能需求。

Applications: Relational, Big Data, Data Science         在本教程的最后一部分中，我们将讨论所描述的新方向如何应用于关系系统以外的众多数据密集型领域。我们讨论了NoSQL系统（如LSM树、B树和日志+索引系统），以及广泛的数据科学应用，如统计密集处理和机器学习系统。实际上，所有这些领域都需要处理不断增长的数据。支持的数据存储和精确处理算法需要根据高级算法/工作负载和硬件所需的精确访问模式而有所不同。随着数据的增长，即使是这些决策中最轻微的次优也可能需要花费数小时到数天的处理时间。本教程中提出的新想法展示了开放式研究问题，旨在为此类数据密集型应用程序生成接近最优的存储系统。

Audience         本教程的目标受众是具有数据结构、算法和数据系统设计基础知识的学生、学者、研究人员和软件工程师。我们假设基本了解基本数据结构，如B树、LSM树和哈希表。此外，我们假设对数据库系统架构、其组件以及它们如何广泛交互具有基本知识，例如，对基于成本的优化器、执行引擎、存储引擎、行存储和列存储有较高的理解。本教程自成一体，提供了所有必要的背景知识，不需要关于自动调整、自适应系统/索引、自行设计和学习系统的先验知识。

Output         目标学习输出如下：

1. 了解构建与应用需求相匹配的新定制系统的需要
2. 了解最先进的基于旋钮的系统的长期技术局限性
3. 通过自行设计和学习的系统面临新的研究挑战
4. 在不同的数据密集型环境中面临新的机遇：关系、NoSQL和数据科学

        Stratos Idreos是哈佛大学计算机科学副教授，他在哈佛大学领导数据系统实验室。他的研究重点是使设计工作量和硬件意识的数据结构和数据系统变得简单甚至自动化，并将其应用于关系、NoSQL和广泛的数据科学和数据探索问题。Stratos因其关于自适应索引的论文获得ACM SIGMOD Jim Gray博士论文奖。他获得了2011年ERCIM Cor Baayen奖 来自欧洲信息学和数学研究理事会的“计算机科学和应用数学领域最有前途的欧洲年轻研究员”。他在超大数据库会议上获得了2011年挑战与愿景最佳论文奖以及“最佳会议奖”2012年VLDB和2017年SIGMOD上的选择。2015年，他因在自适应数据系统方面的工作获得了IEEE数据工程技术委员会颁发的IEEE TCDE新星奖。Stratos还获得了IBM zEnterpise System Recognition Award、Facebook Faculty Award、NetApp Faculty Award和NSF Career Award。         蒂姆·克拉斯卡是麻省理工学院计算机科学和人工智能实验室的电气工程和计算机科学副教授。他的研究重点是构建机器学习系统，以及将机器学习用于系统，其广泛目标是用高效简洁的模型取代传统的庞大系统组件。此外，Tim还致力于通过交互式和可视化数据探索工具实现数据科学的民主化。在加入麻省理工学院之前，他是布朗大学的助理教授，曾在谷歌研究院工作，并在苏黎世理工学院获得博士学位后，成为加州大学伯克利分校AMPLab的博士后。Tim是2017年Alfred P.Sloan计算机科学研究员，获得了2017年VMware Systems Research Award、NSF CAREER Award、Air Force Young Investigator Award、两个超大数据库（VLDB）会议最佳演示奖和IEEE国际数据工程会议（ICDE）的最佳论文奖。Tim也是2018年VLDB早期职业奖的获得者，他推动了交互式数据分析的系统研究。

        这项工作部分由美国国家科学基金项目IIS-1452595资助。