欢迎关注大数据技术架构与案例微信公众号:过往记忆大数据
过往记忆博客公众号iteblog_hadoop
欢迎关注微信公众号:
过往记忆大数据

Presto 基于历史的查询优化器

摘要

现代查询优化器的一个重要特性是能够生成一个对底层数据集最优的查询计划。这需要估计中间查询计划节点的基数和计算成本,这高度依赖于查询的写法和底层数据分布。传统方法包括在基础表上收集统计数据并在优化器内部实现基数和计算成本的推导,这对于复杂查询容易出错。本文介绍了 Presto 的新颖基于历史的优化框架(HBO),它收集执行历史记录并使用它们来优化未来的类似查询。该框架以轻量级、自动化的方式为复杂查询提供准确的估计,并自动适应底层数据分布的变化。我们介绍了HBO框架的设计和实现,并提供了其在各种优化场景中使用的详细信息优化规则,以及关于在Redis键值存储之上实现统计存储的详细信息。我们还展示了在两个大型数据基础设施组织(Meta和Uber)中运行HBO在生产环境中的结果。

1 引言

每个查询引擎的一个重要组成部分是其查询优化器。这是系统负责将输入的查询树(通常是由解析器/分析器生成的抽象查询树)转换为高效执行计划的部分。随着查询复杂性的增长,可能的计划也随之增加,因此拥有一个良好的查询优化器对于寻找合适的搜索空间并生成高效的执行计划至关重要。如今,大多数企业级查询优化器都是基于成本的[7,11,15,26,28,30,31,37],意味着它们使用成本函数来预测查询计划的计算开销,并选择估计执行成本最低的计划。成本计算模块通常利用数据统计和计算成本知识来比较不同的查询计划,并指导优化器选择最佳的查询计划。该模块经常严重依赖于估计的数据分布和基数。

select * from
     (select * from R
     where type='X' and date='...') R
join
     (select * from S
     where status='Y' and date='...') S
on (R.id=S.id) 

为了说明上述内容,请考虑上面的查询语句,该语句在应用一些筛选条件后 JOIN 了两张表。

在分布式查询引擎中可能有多个替代的查询计划评估上述查询,其中一些比其他计划更加耗费计算资源。根据两边的基数不同,不同的连接顺序可能会效果更好。此外,由于数据是分布式的,优化器还负责选择一个分布策略,该策略将要连接的数据放置在相同的节点上。图2展示了上面查询的两个替代计划。如果一方较小,查询优化器可能会选择将这张表的数据广播到所有工作节点,并保留大连接方不变(见图2b),而在其他情况下,更好的查询计划将在相应的连接字段上对双方进行 shuffle 操作(见图2a)。

FlameGraph
如果想及时了解Spark、Hadoop或者HBase相关的文章,欢迎关注微信公众号:过往记忆大数据

图2:示例1中SQL查询的备选方案

在计算查询计划成本时最重要的组件是基数估计:研究发现基数估计器的质量与查询性能之间存在强烈的相关性[22]。传统的基于成本的优化器通常依赖于离线过程来收集输入数据的统计数据,如行数、要收集的统计信息等。关于输入数据的统计信息,如行数、不同值的数量以及总结数据分布的直方图。然后将其与查询计划中中间节点的基数编译时估计相结合,后者会考虑过滤器和连接谓词的选择性以及数量等因素。然而,这种方法存在几个限制和缺点。首先,它需要在查询之前对数据进行预处理。此外,基数估计器会做出一些简化假设,如数据的均匀性、过滤器和列的独立性等。它们通常无法估计复杂表达式的选择性,例如条件表达式、函数调用和多键聚合。人们尝试存储更复杂的统计数据,如多列和连接直方图,但这些需要额外的计算时间和空间,并且通常难以处理。因此,即便是行业普遍采用的基数估计器,在估计中也常常产生较大误差[22]。除了传统的成本估算方法外,过去几年中基于学习的方法在基数和成本估算方面出现了爆炸性增长(参见第7节以获得综述)。虽然这些方法前景光明,克服了许多传统方法中的简化假设,但它们在训练和完善模型方面需要更大的前期投入。基于学习的方法也给运营带来了挑战,因为在需要可预测性能的情况下,它们可能提供的鲁棒性较差。当出现问题时,它们也很难调试:学习模型的可解释性和来源仍然是一个活跃的研究领域。

为了克服上述挑战,本文介绍了Presto的基于历史的查询优化器(HBO),该优化器已在多个大型数据基础设施集团(包括Meta和Uber)的生产环境中使用多年。简而言之,HBO在 operator 节点跟踪查询执行统计数据,并使用这些数据来预测类似查询的未来性能。之所以可能,是因为观察到虽然查询复杂,但本质上却是重复的:它们通常由模板生成,并遵循相同的结构。对于许多大规模离线流程(如每日或每小时的数据提取、转换和加载以及数据分析作业),以及在更交互式的用例(如仪表板)中也是如此,查询通常由模板生成,并遵循相同的结构。

HBO解决了以往方法未能解决的许多问题,具体包括:

准确性:统计数据在实际执行过程中记录,并在 operator 级别跟踪,从而消除了仅使用基本表统计数据推导复杂表达式基数引入的大幅度估计误差。自动化:每次运行查询时都会通过一个轻量级进程跟踪历史记录,从而避免了采样开销或对统计估计器进行模型训练的需求。适应性:底层数据分布的变化会自动反映在跟踪的历史记录中,并用于未来的优化。可解释性:用户和数据库管理员可以查看估计数据的来源以及其与实际值的差距。

本文的其余部分组织如下。第2节介绍了Presto的背景信息——其底层开源数据库及其现有的查询优化器。第3节描述了HBO的架构,包括统计信息的跟踪方式及时间,以及在不同优化中的使用。第4节我们描述了与统计存储通信的API,并提供了在Redis开源键值存储中实现统计存储的详细信息。第5节描述了我们构建的工具,以使HBO易于操作。第6节展示了在两个大型数据基础设施组织(即Meta和Uber)的生产环境中使用HBO的广泛实验评估。最后,第7节我们回顾了相关工作,并在第8节总结。

2 背景

下面我们介绍Presto及其现有查询优化框架的背景信息。

2.1 Presto查询引擎

Presto[29,33]是用于Meta低延迟交互式用例以及长时间运行的ETL作业的一种分布式查询引擎。它最初于2013年在Meta(当时称为Facebook)推出,并于2019年捐赠给Linux基金会。Presto支持ANSI-SQL,并具有一个可扩展的插件框架,允许从Hive、Iceberg等各种来源读取数据。Presto被设计为一个共享一切的系统:所有查询在集群中共享资源,没有硬隔离。它以延迟优先于可伸缩性,因此查询优化器有助于支持这一目标。

由于本文的重点是Presto查询优化器,下面我们将重点关注这个组件,可以查看 [29, 33] 以获取有关Presto整体架构以及查询优化器之外的其他组件(如调度器和协调器)的更多细节。

2.2 Presto的查询优化器

从历史上看,Presto的查询优化器被设计为一个基于规则的引擎,它实现了多种标准的优化技术,如连接重排序、投影和过滤下推等,最近还针对半结构化数据(以映射和数组的形式出现)的操作进行了机器学习工作负载特定的优化。Presto的优化引擎以顺序方式执行规则,如图3所示。它从解析器/分析器组件生成的输入AST开始,并输出最终的执行计划,该计划传递给调度器和执行组件。如图所示,每个优化规则都接收输入计划并将其转换为新的计划。一些优化规则针对查询树中的特定模式被调用(并应用更多局部化转换)而其他实现则通过访问者API来遍历并转换计划树。Presto还支持一个 connector 优化框架[1],该框架允许不同的 connector 实施诸如存储层的选择下推等优化措施。最初,所有优化规则都是启发式的,意味着它们在缺乏对底层数据分布或计算成本完全了解的情况下执行转换。因此,许多查询优化规则都带有一个配置参数,使用户可以根据需要启用或禁用优化。截至撰写本文时,Presto实现了近150条优化规则,其中约三分之一可以通过配置参数启用或禁用[3]。

FlameGraph
如果想及时了解Spark、Hadoop或者HBase相关的文章,欢迎关注微信公众号:过往记忆大数据

图3:Presto基于规则的查询优化器

2.3 Presto中的统计和成本估算

大约在2016年,Presto的优化器增加了基本成本计算功能,以辅助一些主要的优化措施,如连接重排序和选择连接分配。成本计算的主要组件是基数估计器,它依赖于基础表统计数据来推导中间计划节点的基数估计。Presto在分区级别存储统计数据,包括以下内容:

分区的整体基数列统计数据,包括平均大小不同值的数量(Number of distinct values)空值的数量(Number of null values)值的区间(最小值/最大值)

目前,Presto不支持额外成熟的数据分布草图,如直方图[20]。我们正在努力从开源合作伙伴那里增加对这些特性的支持,但在撰写本文时,这些特性尚未成为Presto主要发行版的一部分。

根据上述基本表统计信息,Presto实现了一个统计计算器,用于计算查询中间节点的基数估计。该统计计算器作为计划树顶部的访问者实现,并通过一些简化假设(如列值的均匀分布以及列之间的独立性)在树中传播基本表统计信息。例如,为了估计范围谓词x BETWEEN(m, n)的基数,统计计算器将谓词定义的范围与基本列统计中定义的范围[M,N]相交,得出估计值为n-m/(N-M),并且多键分组的基数估计为每个列不同值的乘积。

3 架构

Presto基于成本的优化器能够为简单查询产生有用的估计,但随着查询和底层表达式变得更加复杂,误差范围呈指数级增长。例如,基于成本的框架能够很好地估计具有单列约束的表达式的统计数据——但即使我们为其添加一个连接条件,它也会感到困惑。在这种情况下,如果不找到表达式中使用的不同列之间的相关性,就不可能获得准确的统计数据。在我们的数据仓库中,查询通常具有复杂的表达式和业务逻辑的用户定义函数。在这些情况下,传统的基于成本的估算技术被证明是无效的。

Presto的历史优化器(HBO)利用了一个事实,即大多数数据仓库查询都是通过程序生成的——通常来自数据管道和用户仪表板。这些查询通常具有共同的结构,仅在使用的符号和常量上有所不同。这些符号通常代表不同的日期范围谓词,以选择新到达的数据,或在仪表板中选择不同的参数值。HBO利用过去执行的类似查询的精确运行时统计数据来预测未来执行的统计数据。由此产生的统计数据比CBO更准确,也更详尽。在本节中,我们将深入了解HBO的架构,并讨论HBO如何跟踪类似查询并预测统计数据。然后,在第3.7节中,我们将详细介绍HBO框架计算的统计数据如何在查询优化过程中用于估算查询计划的计算成本,并做出其他与性能相关的决策。

FlameGraph
如果想及时了解Spark、Hadoop或者HBase相关的文章,欢迎关注微信公众号:过往记忆大数据

图4:HBO的架构

3.1 需求

在设计基于历史的优化框架时,我们考虑了多个要求:

估算需要准确:如上所述,传统的基数估算框架无法为复杂查询形状产生准确的估算。适应数据和查询的变化:在我们的用例中,数据或查询都不是静态的。然而,变化通常不是剧烈的:在短时间内数据分布很少会发生显著变化(但在较长时间内可能会)。同样,在某个给定流程中的查询或仪表板通常由代码生成,并遵循类似的模板。查询处理的开销最小:传统的和新颖的基于学习的方法都依赖于使用采样和学习方法预计算基础表或中间统计数据,并在数据和查询发生变化时继续这样做。我们希望有一种轻量级机制,不需要大量的前期计算。易用性和易操作性:我们希望设计一种“免提”解决方案,它不需要用户输入就能工作。同时,该解决方案需要提供高度清晰和可调试性,以便能够回答诸如为何选择了某个特定的查询计划之类的问题。与经典方法的无缝集成:我们希望支持一种机制,在历史事件尚未可用时回退到经典成本估算。此外,应该容易在单个查询中混合搭配两者,以适应历史事件对查询的一部分可用但对完整查询不可用的情况。

在以下部分中,我们将描述我们的方法,该方法实现了上述所有要求。

3.2 概述

如图3所示,Presto的查询优化器应用一系列规则来计算最优执行计划。在此过程中,输入的计划树经历了一系列等价的变换。其中一些变换(也称为基于成本/CBO规则)在生成结果计划时会考虑成本估算。HBO背后的主要思想是在查询执行期间收集查询计划中每个节点的运行时统计数据,然后在查询优化期间搜索统计存储库以查找先前执行的类似查询计划。

def fetchStats(PlanNode) -> Optional[Stats]

# Stats seen by optimizer rules
class Stats:
     source: Enum["HBO", "CBO"]
     cardinality: int
     size : int
     ...

上面代码片段展示了优化器规则可用的API来获取统计数据。该API接受一个计划节点并返回相应的统计数据(如果可用)。统计数据可以从HBO或传统的CBO框架中得出。优化器规则不关心统计数据的来源。Presto优化器选择更可能准确的统计数据——通常更倾向于HBO统计数据。在案例历史仅出现在查询的一部分时,CBO可能会基于HBO统计数据构建下游计划节点的情况并不罕见。HBO和CBO统计数据的混合在很大程度上提高了统计数据的覆盖范围和准确性。HBO统计数据比CBO统计数据更为冗长。HBO可以存储除了经典的基数和数据大小统计之外的运行时信息,比如 shuffle 大小、task 并行度等。接下来,我们将探究从历史记录中找到相似计划节点的秘诀。

找到相似计划节点是HBO的核心,而做到这一点有几个主要的挑战:

查询变化:虽然查询通常遵循相同的模板,但参数值可能在不同运行中发生变化查询计划变化:同一个查询模板可能根据触发的优化规则的不同(但等效的)执行不同的查询计划搜索相似查询计划的开销很高:每天可能有数百万条查询被执行,对之前运行的详尽搜索资源消耗过大。

上述挑战的解决方案可以概括为:计算规范计划和哈希计划节点(computing canonical plans and hashing plan nodes)。下面,我们分别对这些方面进行详细说明。

FlameGraph
如果想及时了解Spark、Hadoop或者HBase相关的文章,欢迎关注微信公众号:过往记忆大数据

图6:HBO中的计划哈希

3.3 计算规范计划

在一个大型仓库中,搜索所有之前执行的查询计划有一个不可接受的开销。HBO采用一种不同的策略,在将计划节点写入统计存储之前将其转换为规范形式。所有相似的计划节点将共享相同的规范形式,该规范形式可作为读写统计数据的键。我们使用不同的策略创建几种规范形式,并按其置信度顺序使用它们。

计算查询的规范表示有两个主要部分:(1)通过忽略用作参数值的常量来近似生成该查询的模板,(2)将等效的计划映射到相同的规范查询计划。

规范化表扫描:在我们的数据仓库中,表通常按时间列进行分区,新数据会定期(例如每天或每小时)落入新的分区。由于我们的许多管道操作在最近降落的数据上运行,因此查询树中的表扫描节点通常附加有分区过滤器。例如,在类似“SELECT * FROM customers WHERE date='2024-01-01'”的查询中,表扫描计划节点将选择“2024年1月1日”的数据。很可能,这个查询来自一个模板谓词“WHERE date=date”,并且该查询的后续运行将为日期谓词使用不同的参数值。为了计算这个节点的规范表示,我们用“date IN('X','X')”替换原始谓词,将字面值映射到符号X。在此过程中,我们做了一个简化的假设,即各分区大小相似,从而将所有分区视为等同。我们稍后将描述如何放宽这一假设。

剪除常量:计划树中的节点可能包含不同的常量,从而导致从同一模板产生不同的查询。理想情况下,我们会擦除其中的大部分,并用“X”替换它们,就像对表扫描分区所做的那样。我们根据在移除这些常量时想要保留多少保守性,采用了几种策略。我们存储所有此类策略产生的规范形式,并在获取统计数据期间从可用的最安全的规范形式中读取。让我们来看看不同的策略:

从分区键上的等值谓词中剪除常量:如上所述,仅从表扫描分区中剪除常量。从投影中剪除常量:从表扫描分区和投影表达式中剪除所有常量。例如,SELECT *,'2024-01-01' AS date 规范为 SELECT *,'X' AS date。移除这样的常量通常不会导致统计信息的变化。从等值谓词中剪除常量:从表扫描分区、选择表达式和过滤器的特定常量中剪除常量。在这里,我们剪除等值谓词中的常量,例如 WHERE id = 128 规范为 WHERE id = 'X'。这个策略比上述策略更为激进,因为它假设所有id值的分布是均匀的,如果实际情况并非如此,并且历史统计数据是针对与当前分布不同的值记录的,那么可能会产生错误的统计数据。从范围谓词中剪除常量:在这个策略中,我们还剪除范围谓词过滤器中使用的常量。请注意,这可能会导致显著的估算错误,例如 WHERE count >= 1 和 WHERE count >= 1000 的谓词可能导致截然不同的统计数据。同样,在用户定义函数的参数中剪除常量也是危险的。截至目前,我们尚未采用这种规范化策略,但我们相信它可以与经典的基数估计结合使用,在这种情况下,直方图的使用可以告诉我们两个谓词的相对分布是否相同,并且仅在那种情况下才使用历史统计数据。这是未来工作的主题。

规范化计划节点:在这里,我们尝试计算其他方面等效的查询计划的规范表示。然后我们继续使用下面的伪代码将规范计划节点序列化为字符串。本质上,计划节点的表示包括它的所有后代节点以及节点本身:

def str(planNode):
    return str(planNode.information) + [str(c) for c in
        planNode.children]

各个规范化步骤如下:

将所有内连接节点合并为一个。其定义为:

 str(A join B join C) = str(join, [str(A),
    str(B), str(C)])

当序列化子计划节点的顺序不重要时(如联合和内连接的情况),对它们进行排序——与上述合并相结合,这解耦了计划节点表示与用户给出的连接顺序以及优化器做出的连接决策。更正式地说:

str(A join B join C) = str(join,
    sorted([str(A), str(B), str(C)]))

在规范化时,所有的内连接会被重写为左连接。对投影和过滤表达式进行规范化处理,使得像a>b和b<a这样的表达式最终相同。由于表达式也具有树状结构,这个过程可以递归进行。当查询变得复杂时,Presto优化器可能会引入临时变量。我们会内联这些变量的值,因为它们是从列、常量或其他临时变量中获取的。这会消除表示中的变量名。限制表达式可能导致查询提前终止,从而在上游计划节点中产生不完整的统计数据。对于这种情况,会在此类计划节点附加一个下游限制节点的表示。这意味着,仅当存在类似的下游限制节点时,才会使用此类计划节点的统计数据。Presto有多个执行提前终止的操作符,并且对所有此类情况都启用此功能。

哈希:一个计划节点可能有数百个子节点——其字符串表示可能相当大。然而,我们不关心这个表示的内容。我们可以简单地使用像SHA256这样的哈希算法来对序列化的计划节点进行哈希处理。统计存储将是一个键值存储,键是计划节点的哈希值,值是统计数据。这可以节省大量的存储和网络开销。我们将在第4节详细探讨统计存储的细节。

3.4 不断变化的查询计划

Presto优化器通过应用一系列规则不断地转换计划。不断变化的计划节点使得从过去搜索相似的计划节点变得更加困难——即使规范化的哈希值也可能随着规则的执行而不断变化。此外,我们只能了解被执行的最终计划节点的统计数据——中间计划节点在规划过程中会丢失。这使得在统计存储中搜索计划节点变得非常棘手。

HBO通过在优化器中引入一条中间规则来克服这个问题。该规则(图4中的“历史获取”)在优化器的后期运行,就在需要基于成本的估算之前。它会遍历当前计划树,并从统计存储中为所有节点找到相关的计划节点历史。我们保留当前版本的计划节点副本,并将它们一起存储。我们将这些节点称为“统计等效”计划节点。当查询完成时,运行时统计数据与统计等效版本的计划节点进行映射,并写入统计存储中。

优化器规则对计划进行的转换可以改变计划节点,但保持相同的统计等效计划节点。这种映射由HBO框架内部维护,规则无需显式处理。每当计划的一部分被修改时,其最顶层的修改节点和所有未修改的节点都将保持统计等效映射。自然地,规则是保持正确性的——因此它们会保留它们修改的顶层节点的输出。这使得计划哈希对于优化器所做的小规模计划修改具有鲁棒性。例如,在图6的统计等效计划中不存在物理洗牌节点。

如果需要,我们可以在优化器中多次应用“历史获取”规则。这也会为新创建的计划节点获取统计数据。在Presto中,我们在150多条优化规则中仅使用此规则的2个实例。该规则还充当一个检查点,用于批处理所有对统计存储器的调用,从而节省任何串行网络调用的开销。

3.5 存储和获取统计数据

我们已经定义了程序,用于为计划中的所有计划节点创建规范表示。在历史数据获取阶段,我们从统计存储器中获取这些节点的映射统计数据。随着查询的运行,Presto工作进程会定期向Presto协调器发送聚合的操作符(计划节点的运行时版本)统计数据。Presto协调器持续聚合统计数据,直到查询完成,并能够在最后将其写入统计存储器。以计划节点粒度存储统计数据允许我们跨不同查询共享它们。具有公共子查询的查询可以从中受益,并共享一些共同的统计数据。

3.6 适应数据变化

在上述部分,我们通过将所有分区视为相同来规范化表扫描计划节点。例如,从表中选取任意两个分区将得到相同的规范形式。然而,拥有不同大小的分区并不罕见。假设,用户选择按国家列对表格进行分区。由于全球不同地区的人口分布不同,分区大小将会有显著差异。

FlameGraph
如果想及时了解Spark、Hadoop或者HBase相关的文章,欢迎关注微信公众号:过往记忆大数据

图7:存储不同数据的统计数据

为了考虑这一点,我们存储了映射到计划节点的多个统计数据。对于每个统计数据的版本,我们关联它读取的分区的总大小。如果计划节点(包括其子节点)最终从多个表中读取数据,我们会为所有这些表存储此信息。图7展示了一个简化案例,我们为同一个计划节点存储了两个版本的统计数据。这些对应于两次先前的执行,第一次输入表包含100万行,另一次包含200万行。在查找计划节点的统计数据时,我们会找到与查询试图读取的当前分区大小最接近的条目。在示例中,对于100万输入行的统计数据,最接近有120万行的查询。也可以使用线性回归等统计模型来预测新分区大小的统计数据——不过到目前为止,我们还没有发现这种需求。

在实践中,我们存储分区的行数和字节大小。我们在第4.1节中描述了所存储内容的完整表示。如果可用的统计数据中的分区大小与我们查询中的分区大小相差太远,我们就不会使用HBO统计数据。对于每个计划节点,我们会存储多次运行的统计数据,这些运行具有不同的输入统计数据。当新的运行出现时,我们会使旧运行失效,并尝试只存储具有不同输入统计数据的运行。我们对可以存储的不同统计数据的数量设限。这个限制需要足够大以捕捉不同的输入模式。在我们的部署中使用了一个宽限50,同时仍然保持对存储开销的合理限制。大多数计划节点最终存储的统计数据要少得多。

3.7 在查询优化规则中使用HBO

几个Presto优化使用HBO作为成本估算框架。HBO 比 CBO 更强大,因为它还可以存储与调度相关的各种运行时统计数据。让我们来看看一些利用 HBO 来制定更好查询计划的优化方法。

连接重排序:Presto 实现了一种动态编程算法来探索可能的连接树空间,并使用成本估算框架选择最优的连接树。

HBO 可以准确预测过去运行的连接顺序的统计数据。对于其他连接顺序,我们使用 CBO 来预测它们的统计数据。这会导致更准确的成本估算。然而,由于 CBO 统计数据的方差较大,混合使用 HBO 和 CBO 的统计数据并不总是能得到最佳结果。例如,HBO 可能为理想的连接顺序提供正确的统计数据,但 CBO 可能不准确地偏好其他连接顺序。HBO 将无法尝试所有连接顺序以从中学习,但可以学习其他查询中运行的连接顺序。请注意,由于我们将计划统计数据存储在每个节点(而不是仅存储完整查询),因此包含经常一起连接的表的查询将能够从先前由其他查询计算出的表格准确的统计数据中受益。因此,HBO能够更好地预测连接顺序,相较于仅使用CBO。

连接分布类型:HBO也用于决定如何执行分布式连接。Presto优化器获取连接输入的大小,并使用成本模型来决定是执行广播连接还是重新分区连接,如图2所示。部分聚合 当聚合是可组合的时候,Presto可以将一个聚合拆分为部分和最终阶段,以便在数据通过网络分发之前,在计算节点上对数据进行本地预聚合,见图8。当部分聚合能够减少输出大小的时候,它是有帮助的。然而,如果部分聚合没有减少中间结果的大小,它只会在处理过程中增加开销。它还可能会因为为每个组存储额外的预聚合值而增加要分发的中间数据的大小。因此,这个优化规则是基于成本的,仅当部分聚合通过超过预定比率(通常为0.5)降低基数时触发。还要注意,虽然聚合结果的最终大小可能会显著减小,但对于部分聚合阶段可能并非如此。使用HBO,我们可以跟踪部分聚合的输出和输入大小,并存储更准确的数据来指导优化器在未来选择聚合策略。

FlameGraph
如果想及时了解Spark、Hadoop或者HBase相关的文章,欢迎关注微信公众号:过往记忆大数据

图8:部分聚合优化

偏斜缓解 外连接可能导致外侧列出现许多空值,当其中一列用作连接键时,这可能导致处理过程中的偏斜。Presto 有一个优化规则,通过合并空值为更均匀分布在各个工作节点上的非空值来缓解这种偏斜。其原理是通过重写连接键(如图 9 所示),使得空值被转换为永远不会匹配的非空值。由于这是一个基于成本的决策,取决于输出中空值的比例,我们采用 HBO 框架来跟踪空连接键的数量,并在空值比例超过阈值时启用此优化。此优化可以推广到处理除空值偏斜之外的其他偏斜场景。

-- Original query:
SELECT * FROM t1 LEFT JOIN t2 ON t1.key = t2.key

-- Rewritten query:
SELECT * FROM t1 LEFT JOIN t2
    ON COALESCE(
         CAST(t1.key AS VARCHAR),
         'l' || CAST(random(hash_partition_count) AS
             VARCHAR)
    ) = COALESCE(
         CAST(t2.key AS VARCHAR),
         'r' || CAST(random(hash_partition_count) AS
            VARCHAR)
    )

图9:在NULL偏斜优化器中重写查询,以减轻外连接中的偏斜

扩展写入器 对于INSERT查询来说,一个关键问题是正确估计写入器任务的数量:任务太多可能导致大量小文件,而太少则可能在要写入的数据量较大时造成瓶颈。Presto使用写入器扩展来减少INSERT操作期间的小文件数量。通过扩展写入器优化,Presto首先从一个单一的写入器任务开始,随着输出数据量的增加,写入器任务的数量也会增加。然而,这种方法的一个缺点是它依赖于历史查询中记录的任务数量,并从历史记录的一半原始任务数开始,而不是从一开始。

4 统计存储和连接器框架

本节提供了HBO统计存储结构和方法的详细概述。

4.1 HBO统计结构

统计存储本质上是一个键值存储,如图10所示,包含(键,值)对。每个计划节点都与一个唯一键和相应的统计值相关联。有关键和值的更多细节在下面提供。

键:由计划生成的哈希 我们讨论了计划规范化的过程,以及每个计划节点是如何首先被转换成规范形式的。然后将这个规范计划序列化成字符串,接着应用SHA256哈希算法生成一个哈希键。

值:来自之前运行的执行统计数据列表

在第3.1节中,我们调查了执行指标如何与查询执行后的计划节点相关联。我们将所有统计数据构造成一个thrift对象,这允许未来的模式变更,并通过压缩节省存储和网络开销。这成为我们在统计存储中的值。

FlameGraph
如果想及时了解Spark、Hadoop或者HBase相关的文章,欢迎关注微信公众号:过往记忆大数据

图10:HBO统计结构

图11:计划节点类型特定统计

映射值包含来自多次运行的执行统计数据(见图10)。执行统计数据包括行数、输出字节大小等详细信息,以及针对特定计划节点和优化的可选附加信息。此外,与需要计算昂贵统计数据(如NDVs)的成本基础优化(CBO)相比,混合优化(HBO)仅存储简单的统计数据,这些数据可以在运行时轻松计算,且无需任何额外成本。这些详细信息显示在图11中。例如,我们在连接计划节点的两侧存储空键的数量,以检测空值偏斜。部分聚合的输出和输入大小也被存储起来。表写入任务将其并行性作为一个有用的统计数据进行存储。此外,我们还维护一个输入统计列表,其中包含当前计划树内每个计划节点的表扫描输入统计。输入统计数据代表扫描的输入分区的大小。如果存在多个表,我们将它们的统计数据以列表形式展示。这些数据可以来源于文件系统元数据存储,在我们的案例中是Hive元数据存储。[34]

生存时间:我们为统计存储中的每个条目分配一个TTL(生存时间)。每次更新条目时,TTL都会刷新。这样,旧条目会被垃圾回收,减少我们的存储开销并移除再也不会使用的条目。

4.2 HBO统计连接器

统计连接器的主要功能是存储和检索我们的元数据存储中存储的HBO统计数据。

HBO统计连接器在Presto中实现为一个简单的模块化接口,利用Presto的插件框架以实现灵活性。Presto插件框架允许通过插件在运行时加载用户定义的、可配置的实现。

正如第3.1节所述,历史获取规则负责生成所有相关的规范计划节点。这些规则对我们连接器的API进行内部调用,以从统计存储库检索HBO统计数据。此外,如图4所示,协调器利用内存缓存按查询保存这些结果。这种方法减少了所需的网络调用次数,并确保优化器在后续规划阶段能够访问这些历史统计数据。

连接器API:连接器API如下界面所示

# Fetch stats from stats store
def get_stats(planHashes: List[String]) ->
    Dict[String, Stats]

# Store stats in stats store
def put_stats(statistics: Dict[Hash, Stats])

图12:连接器API Redis连接器实现:我们已经开源了一个利用Redis[4]作为后端的统计连接器。作为一种内存数据库,Redis提供了异常快速的读写操作,使其在缓存场景中非常有效。在我们的生产环境中,我们使用Redis的集群配置。该连接器与一个有状态的Lettuce Redis客户端集成,旨在与Redis集群保持持久连接。此外,我们还利用了Lettuce Redis客户端的异步API,默认情况下该API使用Redis的流水线功能,并通过启用多个命令的批处理来提升性能。在我们的生产环境中,我们观察到延迟在几十毫秒的范围内。

5 运营经验

在启动HBO项目时,我们的目标之一是创建一个既强大又易于用户和数据库管理员操作的框架。在本节中,我们描述了与HBO交互的用户体验以及我们构建的各种工具以实现这一目标。

启用HBO。用户可以通过设置以下配置参数来启用HBO:track_history_based_plan_statistics 和 use_history_based_plan_statistics。在我们的集群中,这两个参数都被设置为true。虽然我们不期望最终用户需要修改这些参数值,但它们是调试HBO问题、性能测试的强大工具,并且如果出现问题可以禁用该功能以减轻问题。

解释计划。Presto像大多数其他数据库引擎一样,提供了一种通过EXPLAIN命令检查查询优化器输出的方法。在基于成本的优化器中,解释计划通常包含每个计划节点的统计估计。我们扩展了EXPLAIN的输出,还显示了统计估计的来源(基于成本或基于历史)。

FlameGraph
如果想及时了解Spark、Hadoop或者HBase相关的文章,欢迎关注微信公众号:过往记忆大数据

图13:详细统计信息的解释计划

例如,请参见图13中的解释计划。它是UNION ALL查询计划的一部分。对于UNION的第一个分支(图13中的第5-6行)优化器使用了来自之前运行的基于历史的统计数据,通过相应计划节点上的来源标签“基于历史”可以看出,而对于第二个分支(第8-9行)和最终输出(第3-4行),优化器则使用经典的成本推导来估算输出的规模。还要注意,优化器能够无缝地结合以不同方式得出的统计数据,因此最终输出的估算(75K行)是两种类型统计估算的总和(由CBO生成的15K行和从HBO提取的60K行)。

可观测性。为了跟踪HBO的整体健康状况,并提供有关其大规模运营的洞察,我们在代码的各个地方插入了自动跟踪HBO运行时方面的功能,包括记录或使用的HBO的计划节点(按查询ID和计划节点ID索引)、计时器以跟踪HBO的延迟等。这使我们能够构建各种展示HBO运营属性的仪表板,包括:覆盖率、整体准确性和HBO的延迟。我们在下一部分的实验中使用了部分工具,但它们也是我们仓库日常运营的一部分。

6 实验

在本节中,我们评估了两种生产工作负载下的HBO,以回答以下问题:

有多少百分比的查询可以从历史统计数据中受益?(第6.2节)历史估算的准确性如何?(第6.2节)运行HBO的开销有多大?(第6.4节)我们从HBO中获得多少改进?(第6.3节)

6.1 设置

为了回答上述问题,我们以以下方式进行了模拟实验。我们使用真实的生产查询衍生出几个工作负载,并进行最小程度的更改:重写查询以避免影响任何生产表——而是将数据写入临时表。除此之外,查询与原始查询相同。为了运行工作负载,我们使用了与生产集群配置相同的测试集群。由于我们只有一个测试集群,而生产集群有多个——我们每隔几天对不同集群的流量进行模拟,以在测试期间捕获几乎所有的生产工作负载。

我们在测试集群中启用了HBO,并模拟了多天的生产工作负载,这些工作负载之前未启用HBO。我们首先给HBO一些时间来开始跟踪工作负载并存储统计数据。然后我们继续测量了几个指标,并将它们与生产环境的指标进行了对比。

FlameGraph
如果想及时了解Spark、Hadoop或者HBase相关的文章,欢迎关注微信公众号:过往记忆大数据

表1:来自Meta和Uber的不同HBO指标

查询形状:我们的仓库工作负载包括不同用例,如仪表板、A/B测试、ETL、机器学习、图处理等[33]。我们详细了解查询形状,以便更好地理解工作负载。

图15显示了所有查询计划中这些顶级计划节点的相对分布。40%的节点对应于常见的过滤/投影操作,而20%对应于表扫描。上述优化针对聚合、连接和表写入器计划节点。让我们来看看我们的工作负载中有多少个这样的节点。

聚合占计划节点的30%,在50%的查询中存在。连接占计划节点的6%,但通常出现在总查询的25%。90%的查询使用<=5次连接,99%使用<=10次连接。表写入器节点占计划节点的5%,但在40%的查询中存在。

关于查询中计划节点数量的更多细节在第6.2节给出。

6.2 HBO覆盖范围和统计数据的准确性

表1显示了在Meta和Uber工作负载中部署HBO后观察到的不同指标。

我们发现HBO统计数据达到了92.8%的P90准确率,这意味着对于90%的查询,HBO统计数据与实际基数相差不超过7.2%。当应用HBO时,它会生成高度准确的统计数据。这意味着随着越来越多的查询及其计划节点从HBO获取统计数据,它们自然会得到改善。让我们接下来讨论这一点。

我们的分析显示查询覆盖率为95%,意味着95%的查询从历史运行中获取统计数据。由于我们以计划节点的粒度存储统计数据,这些查询中的统计数据是混合了混合优化(HBO)和成本基础优化(CBO)的统计数据。我们测量了来自 HBO 和 CBO 统计信息,80%的计划节点统计估算来自HBO,其余20%来自CBO。

FlameGraph
如果想及时了解Spark、Hadoop或者HBase相关的文章,欢迎关注微信公众号:过往记忆大数据

图14:按计划规模划分的HBO受影响查询

图15:顶部计划节点分布

在我们的仓库中,HBO导致30-50%的查询发生计划变更。我们进行了一些回测,以检查有多少查询之前有次优计划。回测包括基于运行时统计数据的简单启发式方法,以检测不良计划。我们发现,使用HBO后,74-80%的这些次优查询计划得到优化,成为最优计划。在下一节中,我们将详细讨论这些改进。

图14 研究了HBO对不同计划大小查询的影响。该图表将查询分为10个均匀的桶,按查询计划的大小(计划树中的节点数)排序,并绘制每个桶中受HBO影响的查询百分比。我们看到,较大查询计划的查询比小型查询更需要HBO。较大的查询更复杂,消耗的资源也更多。随着计划大小的增加,CBO启发式方法的效果下降,而HBO能够介入并改进查询计划。超过50%的计划节点数超过34个的查询通过HBO得到改进。另一方面,计划节点数少于15个的查询中,没有需要HBO的。CBO能够自行优化这些小型查询。

6.3 HBO带来的改进

本节展示了HBO优化对性能和资源利用率的改进。我们还展示了第3.7节中描述的优化的结果。总体而言,P50 CPU和延迟均得到提升,参见图17。纵轴是我们工作负载在HBO优化前后CPU成本的比例,延迟也同样如此。较大的数值意味着更多的改进。

FlameGraph
如果想及时了解Spark、Hadoop或者HBase相关的文章,欢迎关注微信公众号:过往记忆大数据

图16:使用HBO的规则使P50性能得到提升

图17:来自HBO的整体P50 CPU和延迟改进

图18:HBO优化的CPU提升百分位数

我们发现,在 Meta 和 Uber 中,所有受 HBO 影响的查询的 CPU 性能平均提升了约 1.1 倍,延迟提升了 1.2 倍。这些数字适用于涉及多个 EB 级数据源的多种工作负载[33]。这对于我们的大型数据仓库来说,是一次巨大的效率提升。

FlameGraph
如果想及时了解Spark、Hadoop或者HBase相关的文章,欢迎关注微信公众号:过往记忆大数据

图19:洗牌大小改进

图20:内存利用改进

性能分析:图18显示了我们工作负载上CPU改进的直方图。我们看到,10%的查询速度提升了2.5倍以上,而中间四分位数区域的提升稳定在1到1.2倍之间。对于后端的10%查询,我们看到了大约8%的性能退化。

我们进一步分析了出现CPU时间退化的案例。其中一些查询本身并没有出现退化,因为其他指标如延迟和内存使用得到了改善。然而,我们确实看到了一些情况,即在应用了HBO之后,查询计划变得次优。在这些情况下,CBO过去预测错误的统计数据,但幸运的是查询计划最终结果良好。当应用HBO时,这些统计数据中的一些变得准确,但查询中剩余的未应用HBO的统计数据导致查询计划次优。由于CBO统计数据的变异性较高,混合使用HBO和CBO统计数据并不总是产生好的结果。然而,我们发现它在大多数情况下(P90)是有帮助的,因此我们保持在生产中对所有查询启用它。随着时间的推移,随着HBO能够覆盖更多的统计数据,次优情况变得不那么频繁。例如,在重新运行一个退化的查询时,HBO能够为查询提供所有统计数据,并且查询计划再次变得良好。

查询优化:在图16中,我们展示了在第3.7节讨论的五种优化的CPU和延迟改进情况。这些具体数字来自Meta工作负载,然而Uber工作负载也经历了类似的改进。所有优化在延迟和CPU方面都表现出改善,除了偏斜优化在CPU上略有退步。这是预期之中的,因为我们为了减轻偏斜以提高延迟而支付了小额的计算成本,这使延迟改善了5.9倍。请注意,在这种情况下我们压缩了纵轴以便于视觉清晰。所有其他优化的性能提升了1.1到1.4倍。

连接分布优化在这里显示出最多的改进(1.4倍),因为它防止了大表的额外洗牌,而且在许多情况下连接是查询执行的瓶颈。另一方面,聚合通常很快,所以部分聚合的改进较小(1.1倍),但这些改进涵盖了更广泛的查询集。直观上,我们可能期望连接排序的改进也会很高——但我们发现许多客户在实现SQL查询期间找到了这些改进。一个连接顺序不佳的SQL查询很容易因内存不足错误而失败。我们观察到连接排序带来的改进接近1.1倍。扩展写入器不会带来任何CPU节省,因为它只是改变了写入器的数量,但通过10%降低了延迟。

图 19、20 显示了在推出 HBO 后,Meta 和 Uber 工作负载中系统相关的内存指标均有所改善。Meta 工作负载的总内存使用量减少了 5%,Uber 工作负载的总内存使用量减少了 17%。我们还看到,在我们的工作负载中,worker 内的 shuffle 大小减少了 17-40%。

FlameGraph
如果想及时了解Spark、Hadoop或者HBase相关的文章,欢迎关注微信公众号:过往记忆大数据

图21:HBO优化器的延迟分解

表2:TPCH查询的统计大小

6.4 HBO的开销

HBO的计算开销分为两个方面,HBO带来的额外延迟以及存储历史统计数据的成本。

结果显示,HBO的额外延迟可以达到整体查询执行时间的0.5%。这一结论适用于短时间运行的查询(以秒计)。较长时间运行的查询的开销可以忽略不计。我们进一步分解了来自HBO优化器的延迟,如图21所示。最大的开销来自读取历史数据(40.1%)以及从元数据存储读取输入表分区的大小(38.1%),其次是哈希查询计划(18.1%)和规范查询计划(3.4%)。大多数额外延迟主要由网络调用引起,导致毫秒级的开销。

HBO的存储开销与查询计划节点的数量成正比,每个节点消耗184字节来存储相应的历史数据。表2显示了TPCH查询的计划大小及相应的HBO统计数据大小(针对1次运行)。我们看到平均每个查询有13个计划节点,平均每个查询2.3kB。

7 相关工作

传统的基于成本的优化。基于成本的优化一直是数据库研究和商业系统的核心[6, 15, 22,30,31,37]。关于系统的开创性论文

自1970年代以来,R[10]引入了以CPU指令和磁盘页访问来定义成本,大多数商业和开源数据库系统也跟随这一趋势,实现了基于成本的优化器,包括SQL Server、Teradata、Oracle、PostgreSQL等。其中一些还提供了指定查询提示[2, 5]的能力,以指导优化器选择最优计划,从而避免成本估算中的误算。传统的基于成本的优化器通常依赖直方图来近似数值列的数据分布[20]。直方图通常将值的范围划分为一系列区间,并存储落入每个区间的值的数量。大多数系统支持单列直方图,有些还支持多列直方图,以便更好地管理跨列的相关性[12, 16, 27]。直方图的另一种替代方法是抽样:对数据的一个样本运行查询,以近似整个结果的基数[17, 23]。我们在本文中提出的框架HBO是基于成本优化的思想的体现,我们用基于历史查询运行的更准确的基数估计器替换了基数估计器。

关于统计数据的看法。也许与HBO最接近的想法是之前关于创建统计视图的工作[14]。在这项工作中,DBMS提供了一个“创建统计数据”命令,允许用户预先计算给定子查询的统计数据。在查询优化过程中,引擎使用与视图匹配相同的理念来查找是否有针对该查询的统计视图,并使用提取的统计数据来估计成本。我们的方法与这项工作的几个主要区别在于:[14] 要求用户和数据库管理员主动创建统计视图,然后才能使用它们,可能需要借助自动统计视图顾问的帮助[13],而我们的方法是在每次运行查询时自动收集统计数据。统计视图也不支持随机查询表达式,因为它们依赖于视图匹配来确定匹配项。最后但同样重要的是,视图匹配的可扩展性不如我们的计划节点哈希方法,这意味着在需要超过数百个独特查询模板的情况下可能不适用(大型数据基础设施组织如Meta和Uber的情况很容易出现这种情况)。

学习优化器。近年来,关于学习查询优化的研究呈爆炸式增长。这些研究的一个重要方面涵盖了学习基数估计[18, 21, 32, 35, 36]。学习基数估计技术分为两大类:(1)将基数估计视为密度估计问题的学习数据模型,并学习每个数据点的联合数据分布;(2)学习查询模型,它学习SQL查询与其在数据库上的基数之间的映射函数。

学习优化的第三个分支关注于学习引擎提供的用于指导优化器的最佳外部旋钮值[9, 24, 25]。虽然这些方法已经显示出早期的有希望的结果,但它们还需要一个初始步骤来学习参数值。此外,它们受限于引擎作为查询提示所暴露的内容以及可以应用的范围:大多数引擎只为整个查询提供全局的旋钮(而不是针对单个操作符)。对于可以在单个操作符级别指定提示的引擎,由于查询树中每个节点的参数值组合呈指数级增长,学习步骤的开销大得令人望而却步。

查询模板提取与计划哈希。最后,计划哈希和查询模板提取的概念已被用于其他领域,如自动化工作负载分析[8, 19]。

8 结论与未来工作

在本文中,我们描述了Presto中的基于历史的查询优化框架,以及在两个大型数据基础设施组织中将其投入生产运行的初步发现。我们的结果显示,大量查询受益于历史统计数据。由于历史统计数据的准确性高于传统的基数估计,查询优化器能够做出更好的优化决策,并且我们展示了这有助于提升查询性能的各个方面,包括CPU、延迟和内存利用率。

将来我们计划以多种方式扩展HBO,包括使更多优化措施具有成本意识,并使框架更加健壮。此外,我们正在寻求改进HBO的以下几个方面:

从失败中学习:目前,HBO 仅在查询成功完成后跟踪统计数据。许多失败的查询是由于错误的连接决策/偏斜导致的高内存使用。HBO 可以在此大幅改善用户体验——使失败的查询在重试后神奇地工作。根据我们与用户的经验,一个失败的查询通常会在考虑手动优化之前被重试。失败的查询往往统计信息不完整,使其更难从中学习。HBO 可以从失败的执行中学习到一些线索——比如哪个连接边的数据更大、偏斜程度如何——并在下次运行时修复这些问题。

跟踪预测失误:由于 HBO 从统计存储中存储和读取统计数据,它还可以跟踪每个计划哈希的预测准确性。如果我们的哈希策略导致具有高方差的统计数据,我们可以将相关估计标记为“低置信度”。这也提供了一种随时间监控框架准确性的方法。

在底层数据变化时做出更好的预测:目前,HBO 仅在我们过去找到一个处理大致相同数量数据的类似运行时才返回估计值。虽然保留许多此类运行可以提高覆盖率,但我们可以使用线性回归等统计模型进一步处理输入数据差异过大的情况。例如,当底层数据翻倍时,假设 Scan+Filter 操作符的输出也会翻倍是合理的。

全局成本计算:虽然目前 Presto 的许多基于成本的决策是局部的,但我们还在研究一般性的优化查询优化框架,以保持类似级联(Cascades)的更大可能查询计划空间,并对查询计划进行全局成本计算。本文中提出的HBO理念也适用于此。

致谢

我们要感谢Meta和Uber团队中的Sreeni Viswanadha、Biswapesh Chattopad-hyay、Sara Narayan、Kaushik Ravichandran、Rohit Jain、Rongrong Zhong、Masha Basmanova、Pedro Pedreira、Zhongting Hu、Hitarth Trivedi以及许多其他成员,感谢他们就HBO的设计与实施进行了无数次的讨论、代码审查以及反馈,同时也感谢他们对本出版物的早期草稿提供的意见。

参考

[1] 2019. Improving the Presto planner for better push down and data federation. https://prestodb.io/blog/2019/12/23/improve-presto-planner/

[2] 2024. Oracle query hints. https://docs.oracle.com/en/database/oracle/oracle-database/21/sqlrf/Comments.html#GUID-D316D545-89E2-4D54-977F-FC97815CD62E__BABEAFGF

[3] 2024. Presto: Distributed SQL query engine for big data. https://github.com/prestodb

[4] 2024. Redis in-memory key-value store. httsp://www.redis.io

[5] 2024. SQL server query hints. https://learn.microsoft.com/en-us/sql/t-sql/queries/hints-transact-sql-query?view=sql-server-ver16

[6] 2024. Teradata query optimizers. https://docs.teradata.com/r/Enterprise_IntelliFlex_VMware/SQL-Request-and-Transaction-Processing/Query-Rewrite-Statistics-and-Optimization/Query-Optimizers

[7] Rafi Ahmed, Allison Lee, Andrew Witkowski, Dinesh Das, Hong Su, Mohamed Zait, and Thierry Cruanes. 2006. Cost-based query transformation in Oracle. In VLDB, Vol. 6. 1026–1036.

[8] Amirhossein Aleyasen, Mark Morcos, Lyublena Antova, Marc Sugiyama, Dmitri Korablev, Jozsef Patvarczki, Rima Mutreja, Michael Duller, Florian M. Waas, and Marianne Winslett. 2022. Intelligent Automated Workload Analysis for Database Replatforming. In Proceedings of the 2022 International Conference on Management of Data (Philadelphia, PA, USA) (SIGMOD ’22). Association for Computing Machinery, New York, NY, USA, 2273–2285. https://doi.org/10.1145/3514221.3526050

[9] Christoph Anneser, Nesime Tatbul, David Cohen, Zhenggang Xu, Prithviraj Pandian, Nikolay Laptev, and Ryan Marcus. 2023. AutoSteer: Learned Query Optimization for Any SQL Database. Proc. VLDB Endow. 16, 12 (aug 2023), 3515–3527. https://doi.org/10.14778/3611540.3611544

[10] M. M. Astrahan, M. W. Blasgen, D. D. Chamberlin, K. P. Eswaran, J. N. Gray, P. P. Griffiths, W. F. King, R. A. Lorie, P. R. McJones, J. W. Mehl, G. R. Putzolu, I. L. Traiger, B. W. Wade, and V. Watson. 1976. System R: relational approach to database management. ACM Trans. Database Syst. 1, 2 (jun 1976), 97–137. https://doi.org/10.1145/320455.320457

[11] Kassem Awada, Mohamed Y Eltabakh, Conrad Tang, Mohammed Al-Kateb, San-jay Nair, and Grace Au. 2020. Cost Estimation Across Heterogeneous SQL-Based Big Data Infrastructures in Teradata IntelliSphere.. In EDBT. 534–545.

[12] Nicolas Bruno, Surajit Chaudhuri, and Luis Gravano. 2001. STHoles: a multidi-mensional workload-aware histogram. In Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data (Santa Barbara, California, USA) (SIGMOD ’01). Association for Computing Machinery, New York, NY, USA, 211–222. https://doi.org/10.1145/375663.375686

[13] Amr El-Helw, Ihab F. Ilyas, and Calisto Zuzarte. 2009. StatAdvisor: Recom-mending Statistical Views. Proc. VLDB Endow. 2, 2 (aug 2009), 1306–1317. https://doi.org/10.14778/1687553.1687556

[14] César A Galindo-Legaria, Milind M Joshi, Florian Waas, and Ming-Chuan Wu. 2003. Statistics on views. In Proceedings 2003 VLDB Conference. Elsevier, 952–962.

[15] Goetz Graefe. 1995. The Cascades Framework for Query Optimization. IEEE Data(base) Engineering Bulletin 18 (1995), 19–29. https://api.semanticscholar.org/CorpusID:260706023

[16] Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, et al . 2021. Cardinality estimation in DBMS: A comprehensive benchmark evaluation. arXiv preprint arXiv:2109.05877 (2021).

[17] Max Heimel, Martin Kiefer, and Volker Markl. 2015. Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015, Timos K. Sellis, Susan B. Davidson, and Zachary G. Ives (Eds.). ACM, 1477–1492. https://doi.org/10.1145/2723372.2749438

[18] Benjamin Hilprecht and Carsten Binnig. 2022. Zero-Shot Cost Models for out-of-the-Box Learned Cost Prediction. Proc. VLDB Endow. 15, 11 (jul 2022), 2361–2374. https://doi.org/10.14778/3551793.3551799

[19] Hanxian Huang, Tarique Siddiqui, Rana Alotaibi, Carlo Curino, Jyoti Leeka, Alekh Jindal, Jishen Zhao, Jesus Camacho-Rodriguez, and Yuanyuan Tian. 2024. Sibyl: Forecasting Time-Evolving Query Workloads. arXiv preprint arXiv:2401.03723 (2024).

[20] Yannis Ioannidis. 2003. The history of histograms (abridged). In Proceedings 2003 VLDB Conference. Elsevier, 19–30.

[21] Kyoungmin Kim, Jisung Jung, In Seo, Wook-Shin Han, Kangwoo Choi, and Jaehyok Chong. 2022. Learned Cardinality Estimation: An In-Depth Study. In Proceedings of the 2022 International Conference on Management of Data (Philadelphia, PA, USA) (SIGMOD ’22). Association for Computing Machinery, New York, NY, USA, 1214–1227. https://doi.org/10.1145/3514221.3526154

[22] Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2015. How Good Are Query Optimizers, Really? Proc. VLDB Endow. 9, 3 (nov 2015), 204–215. https://doi.org/10.14778/2850583.2850594

[23] Viktor Leis, Bernhard Radke, Andrey Gubichev, Alfons Kemper, and Thomas Neumann. 2017. Cardinality Estimation Done Right: Index-Based Join Sampling. In Conference on Innovative Data Systems Research. https://api.semanticscholar.org/CorpusID:8154743

[24] Ryan Marcus, Parimarjan Negi, Hongzi Mao, Nesime Tatbul, Mohammad Alizadeh, and Tim Kraska. 2022. Bao: Making Learned Query Optimization Practical. SIGMOD Rec. 51, 1 (jun 2022), 6–13. https://doi.org/10.1145/3542700.3542703

[25] Ryan Marcus, Parimarjan Negi, Hongzi Mao, Chi Zhang, Mohammad Alizadeh, Tim Kraska, Olga Papaemmanouil, and Nesime Tatbul. 2019. Neo: A learned query optimizer. arXiv preprint arXiv:1904.03711 (2019).

[26] V. Markl, G. M. Lohman, and V. Raman. 2003. LEO: An autonomic query optimizer for DB2. IBM Systems Journal 42, 1 (2003), 98–106. https://doi.org/10.1147/sj. 421.0098

[27] M. Muralikrishna and David J. DeWitt. 1988. Equi-depth multidimensional histograms. In Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data (Chicago, Illinois, USA) (SIGMOD ’88). Association for Computing Machinery, New York, NY, USA, 28–36. https://doi.org/10.1145/50202.50205

[28] Mary Tork Roth, Laura M Haas, and Fatma Ozcan. 1999. Cost models do matter: Providing cost information for diverse data sources in a federated system. IBM Thomas J. Watson Research Division.

[29] Raghav Sethi, Martin Traverso, Dain Sundstrom, David Phillips, Wenlei Xie, Yutian Sun, Nezih Yegitbasi, Haozhun Jin, Eric Hwang, Nileema Shingte, and Christopher Berner. 2019. Presto: SQL on Everything. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). 1802–1813. https://doi.org/10.1109/ICDE.2019.00196

[30] Srinath Shankar, Rimma Nehme, Josep Aguilar-Saborit, Andrew Chung, Mostafa Elhemali, Alan Halverson, Eric Robinson, Mahadevan Sankara Subramanian, David DeWitt, and César Galindo-Legaria. 2012. Query Optimization in Microsoft SQL Server PDW. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (Scottsdale, Arizona, USA) (SIGMOD’12). Association for Computing Machinery, New York, NY, USA, 767–776. https://doi.org/10.1145/2213836.2213953

[31] Mohamed A Soliman, Lyublena Antova, Venkatesh Raghavan, Amr El-Helw, Zhongxian Gu, Entong Shen, George C Caragea, Carlos Garcia-Alvarado, Foyzur Rahman, Michalis Petropoulos, et al . 2014. Orca: a modular query optimizer architecture for big data. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data. 337–348.

[32] Ji Sun, Jintao Zhang, Zhaoyan Sun, Guoliang Li, and Nan Tang. 2021. Learned Cardinality Estimation: A Design Space Exploration and a Comparative Evaluation. Proc. VLDB Endow. 15, 1 (sep 2021), 85–97. https://doi.org/10.14778/3485450.3485459

[33] Yutian Sun, Tim Meehan, Rebecca Schlussel, Wenlei Xie, Masha Basmanova, Orri Erling, Andrii Rosa, Shixuan Fan, Rongrong Zhong, Arun Thirupathi, Nikhil Collooru, Ke Wang, Sameer Agarwal, Arjun Gupta, Dionysios Logothetis, Kostas Xirogiannopoulos, Amit Dutta, Varun Gajjala, Rohit Jain, Ajay Palakuzhy, Prithvi Pandian, Sergey Pershin, Abhisek Saikia, Pranjal Shankhdhar, Neerad Somanchi, Swapnil Tailor, Jialiang Tan, Sreeni Viswanadha, Zac Wen, Biswapesh Chattopad- hyay, Bin Fan, Deepak Majeti, and Aditi Pandit. 2023. Presto: A Decade of SQL Analytics at Meta. Proc. ACM Manag. Data 1, 2, Article 189 (jun 2023), 25 pages. https://doi.org/10.1145/3589769

[34] Ashish Thusoo, Joydeep Sen Sarma, Namit Jain, Zheng Shao, Prasad Chakka, Suresh Anthony, Hao Liu, Pete Wyckoff, and Raghotham Murthy. 2009. Hive: a warehousing solution over a map-reduce framework. Proc. VLDB Endow. 2, 2 (aug 2009), 1626–1629. https://doi.org/10.14778/1687553.1687609

[35] Xiaoying Wang, Changbo Qu, Weiyuan Wu, Jiannan Wang, and Qingqing Zhou. 2021. Are We Ready for Learned Cardinality Estimation? Proc. VLDB Endow. 14,9 (may 2021), 1640–1654. https://doi.org/10.14778/3461535.3461552

[36] Ziniu Wu, Parimarjan Negi, Mohammad Alizadeh, Tim Kraska, and Samuel Madden. 2023. FactorJoin: A New Cardinality Estimation Framework for Join Queries. Proc. ACM Manag. Data 1, 1, Article 41 (may 2023), 27 pages. https://doi.org/10.1145/3588721

[37] Mohamed Ziauddin, Dinesh Das, Hong Su, Yali Zhu, and Khaled Yagoub. 2008. Optimizer Plan Change Management: Improved Stability and Performance in Oracle 11g. Proc. VLDB Endow. 1, 2 (aug 2008), 1346–1355. https://doi.org/10.14778/1454159.1454175

本文翻译自:Presto’s History-based Query Optimizer https://www.vldb.org/pvldb/vol17/p4077-shankhdhar.pdf

本博客文章除特别声明,全部都是原创!
原创文章版权归过往记忆大数据(过往记忆)所有,未经许可不得转载。
本文链接: 【Presto 基于历史的查询优化器】(https://www.iteblog.com/archives/10231.html)
喜欢 (0)
分享 (0)
发表我的评论
取消评论

表情
本博客评论系统带有自动识别垃圾评论功能,请写一些有意义的评论,谢谢!