SPRINTER：快速 n 元连接查询处理

复杂 OLAP 查询的方法

摘要

​ OLAP查询处理的概念现在被广泛使用被各种应用所采用。复数包含非唯一键（称为FK-FK 连接）在这些应用程序中增加。然而现有的内存 OLAP 系统往往不处理这种高效的复杂查询，因为它们会产生大量的中间结果或招致大量的探测成本。
​ 在本文中，我们提出了一种有效的查询规划方法用于复杂的 OLAP 查询。它基于成本模型生成包含 n 元连接运算符的查询计划。该计划确实不生成处理 FK-FK 连接的中间结果并显着降低探头成本。我们还提出了一个n元连接运算符的有效处理方法。我们通过集成我们的系统来实现原型系统 SPRINTER将建议的方法转化为开源的内存中 OLAP系统。通过使用 TPC-DS 基准的实验，我们已经证明，对于复杂查询，SPRINTER 的性能优于最先进的 OLAP 系统。

关键字

​ n连接运算符，查询规划，查询优化，FKFK连接，复杂OLAP查询处理，协同处理

INTRODUCTION

​ 有许多用于大规模数据分析的内存中 OLAP 查询处理系统，例如 Quick step [34]、MemSQL [11]、MonetDB [9]、Hyrise [16]、Ora cle [23] 、DB2 [6]、SQL Server [24]、SAP HANA [41]、Peloton [28]、OmniSci [33]、CoGaDB [10]、Kinetica [21] 和豹猫 [17]。 这些系统主要专注于有效处理传统的星形/雪花连接查询，这些查询包含一个主键之间的一些连接操作表和另一个表的外键 [45, 50]。 中的一个
这些系统中查询优化的目标是减少由连接引起的处理中间结果的成本查询计划中的操作 [40, 45]。 为实现目标，现有系统利用了各种技术，例如中间结果的流水线[28, 50]。

​ OLAP查询处理的概念现在正被广泛应用于各种应用中，包括图形分析[1,13]、人工智能[22][20,26]和生物信息学[20,26]。作为应用程序 如果会变得越来越复杂，这些应用程序中的查询工作负载往往会变得越来越复杂。特别是，包含一对外部操作之间的连接操作的查询的数量 唯一的)键，而不是传统的一对主键和外键在应用程序中增加。本文将这种连接操作表示为FK-FK连接。一个FK-FK连接通常会产生一个lar 由于重复的连接键值而导致的连接结果数。如果查询包含两个事实表之间的FK-FK连接操作(s)，则由于hu，高效处理查询将变得更加困难 中间结果的通用量。这种复杂的查询通常发生在具有包含多个星形或雪花模式[3]的暴风雪模式的数据库上。例如，TPC-DS 基准测试使用一个暴风雪模式，在TPC-DS基准测试中总共99个查询中的26个（即26.2%的查询）包含一个或多个FK-FK连接操作[30]。

​ 现有的OLAP系统往往不能有效地处理包含FK-FK连接操作的复杂查询。它们通常会生成一个左深的连接树，并在一个实时操作员中处理该计划 方式，哪里可以

​ 由于查询中FK-FK连接（或非键连接）操作符的下一个操作符无法处理的中间结果太大，因此会显著降级，或处理本身可能会失败 计划[47]。流水线技术通过在一组由其余关系构建的哈希表中查找探测关系的每个元组来计算连接树中的一系列多个连接运算符 [27,50]。它可能对PK-FK连接的查询有效，但对于事实表中包含FK-FK连接的复杂查询可能无效，因为存在以下两个问题：许多关键比较 以及大量的内存使用量。首先，探测关系中每个元组的连接键值需要与哈希表中的所有重复键值相匹配。可能会有很多比赛到期 对于FK-FK连接操作，这可以根据连接键值的重复程度成比例地大大降低查询性能。其次，保留一组由非专业人员构建的所有哈列表 主存中的关系需要大量内存，特别是当表数量增加时。由于上述两个问题，性能可能会显著下降，或者 当我们对包含FK-FK连接的查询使用管道技术时，处理本身可能会失败。

​ 在本文中，我们提出了一种有效的查询处理方法，用于包含FK-FK连接的复杂OLAP查询。SPRINTER背后的直觉是，一个n-ary连接操作数的查询计划 与一系列二进制连接运算符之一相比，or可以减少中间结果的数量，而且多路连接处理[44]并不总是这样，但对于处理t可以非常有效 他查询计划。多路连接处理已用于分布式查询处理[2,13,49]和图形模式查询处理[31,44]，但几乎没有在内存中的OLAP系统中使用 由于哈希连接在内存内处理环境[5,39]中通常优于排序合并连接，并且OLAP查询是不同于图形模式查询的特别查询和无环查询。我们提出了一个查询计划 可以生成包含n-ary连接运算符的查询计划，而不是只有一系列二进制连接运算符的传统计划的查询方法。

​ 一般来说，生成一个具有n-ary连接运算符(称为n-ary连接树)的查询计划是很简单的，因为查询计划的搜索空间比只考虑bina时变得更大 ry加入操作员。我们提出的查询规划方法基于成本模型 heuristic式和递归地搜索一个良好的查询计划。我们提出了所使用的成本模型和一种查询优化方法 t允许查询规划方法只有在与传统的二进制左深连接树相比有益时才生成n-ary连接树。然后，我们解释了单向连接处理方法 r是一个基于最坏情况最优连接算法的n个连接算子。我们实现了我们所有的方法成为一个开源的现代内存OLAP处理系统，OmniSci[33]，跨所有相关的层和模块，包括查询计划生成器和物理连接操作符。通过出口 在使用TPC-DS基准测试进行的化学实验中，我们已经证明了SPRINTER在处理速度和数据方面都显著优于最先进的OLAP查询处理系统 可以处理的没有内存的大小。

​ 我们的主要贡献总结如下：
• 我们提出了一种查询规划方法，可以生成复杂 OLAP 查询的 n 元连接树包含FK-FK 加入。
• 我们提出了成本模型和查询优化n路连接树的方法。
• 我们提出了一种 n 元的 n 路处理方法基于最坏情况最优的连接运算符加入算法。
• 我们在所有相关层和基于开源 OLAP 系统的基础上实施原型系统包括查询计划生成器和物理连接运算符。
• 在大量实验中，我们证明 SPRINTER 的性能明显优于最先进的基于 CPU 的协同处理 OLAP处理系统。

本文的其余部分组织如下。

在第2.2节中，我们提出了一个在SPRINTER中使用的最坏情况下的最优连接算法。在第3节中，我们将描述本文的一个激励例子。

在Secti 在4上，我们提出了n个连接树的查询规划方法。

在第5节中，我们提出了一种自动连接处理方法和优化方法，以提高查询性能。我们建议将成本为m

第6节中的odel。

第7节介绍了实验评价的结果。

最后，我们在第8节中讨论相关的工作，

并在第9节中总结本文。

PRELIMINARIES

Sorting algorithms

在本节中，我们将在表1中总结SPRINTER中现有的并行排序算法和技术。虽然本文的核心贡献是查询的优化 包含使用n-ary连接操作符的FK-FK连接，当n-ary连接操作符的输入大小非常大时，使用GPU进行排序可以进一步提高查询性能。因此，SPRINTER使用d 不同的排序算法和技术取决于要排序的表的基数，排序列的数量，和GPU内存的容量，在GPU排序。

表1中基于比较的算法意味着，它们需要在排序的关键值（如快速排序、合并排序、气泡排序）和基于非比较的算法之间进行比较 n，它们不需要这样的比较来进行排序（例如，radix排序）。对于一个给定的N个元组值的输入数组，每个元组值由k个列组成，我们知道的速度的极限 基于比较的算法为O（N.loдN），而基于非比较的算法为O（k.N）。因此，如果k很小，后者通常比前者快。

**Table 1:**在SPRINTER中使用的并行排序算法和技术。

​ 大多数GPU排序算法只能对GPU内存中的数据进行排序。然而，要排序的输入阵组可以远远大于OLAP系统中的GPU内存容量。在那个cas e，SPRINTER使用异构排序[15]，有效地利用CPU和GPU。图1显示了输入数组X的异构排序的时间轴，其中我们假设X太大，t o适合GPU内存，因此，我们需要将其分成六个子数组{X1、·、·、X6}。虽然异构排序在CPU上可以在CPU和GPU上使用不同的算法，但我们在GPU上使用radix排序 和在CPU上的合并排序，因为该组合通常显示出最好的性能。异构排序使用多个GPU流，以隐藏主存和GPU模因之间的数据拷贝成本 y尽可能通过重叠三种低级GPU操作，H2D拷贝、排序和D2H拷贝。它在wenev时立即使用CPU对主存中一些已排序的子阵列执行合并排序 他们是可用的。我们假设Xˆ是全局排序的数组，并初始化为一个空数组。图1中的红色框显示了使用CPU的即时合并排序，其中merдe({Xi，Xj})perf 将一组已排序的块{Xi，Xj}合并到Xˆ中。

​ 图1：异构排序[15]的时间轴。

2.2最坏情况下的最优连接算法

​ 在本节中，我们将描述SPRINTER用于处理n-ary连接运算符的最坏情况下的最优连接算法。最坏情况下的最优连接算法[13,44]主要是支撑的 通过避免生成中间结果，用以有效地处理图形模式查询（例如，三角形查询）。一些算法[1,31,44]需要对输入关系和存储进行预处理 ng预处理作为数据结构的结果，如B+-tree，而其他[13,47]只是使用二进制搜索排序关系并执行连接。我们使用th e后一种算法，特别是部落连接(TJ)[13]。

​ 图2说明了三角形查询Q（x、y、z）：-R（x、y）、S、（y、z）、T（x、z）的处理，其中R、S和T为边缘关系。最坏情况下的最优连接算法通常使用一个修复程序 ed对所有连接变量的全局排序。我们假设图2中的全局变量的顺序是x≺和≺z。TJ算法按(≺，y)排序，按x≺排序，按(y，z)排序，按y≺排序 z，并根据顺序x≺z排序(x，z)，进行预处理。然后，TJ首先扫描第一个连接变量x(即R和T)上的所有关系，然后作为合并连接进行，直到找到a 该变量的匹配值，例如，x=1。然后，它简单地递归地计算残余的queryQ‘(y，z)=Rx=1(y)、S(y，z)、Tx=1(z)，其中残余的关系Rx=1和Tx=1实际上是子arr 通过调整R和T的起始和端点获得R和T的方法和x=1。在递归调用期间，它将扫描下一个连接变量y上的所有关系，直到找到匹配的值y= 3.然后，它通过扫描z来递归地再次进行，最后输出（1,3,4）。

​ 当在数组或子数组中寻找一个特定的值时(例如，在S中寻找y=3)时，TJ使用二进制搜索，因此，单个搜索的成本是O(loдN)。然而，TJ的主要成本是补屑素 g输入关系的成本[13]。如果一个查询有L个连接变量，则可能的全局变量顺序的数量为L！。虽然TJ在任何变量排序下是最坏情况最优的，但这种“最坏情况”p 实际上，由于每个变量顺序的搜索成本不同，可能远非最优，因此，TJ估计每个可能订单的连接处理成本，并选择最好的订单。

​ 图2：部落连接[13]的示例。

3 动机

​ 在本节中，我们将介绍一个激励性的查询，它显示了现有的OLAP查询处理系统的缺点。该查询是TPC-DS基准数据库[30]上的一个查询，广泛用于t 测试OLAP系统[18]的查询性能。虽然该查询包含包括聚合在内的各种操作，但我们将在本节中重点关注连接操作。图3显示了的连接图 该查询包含蓝色矩形的三个事实表{SS、SR、CS}和绿色矩形的三维表{D、I、C}。为了简单起见，我们只使用关系名称的缩写 在本文中。在图中，我们描述了连接图的每条边上的连接条件。蓝线有2个FK-FK连接操作，绿线有5个PK-FK连接操作。

​ 图3：激励性查询的连接图。

​ 图4显示了由Syssem-X、OmniSci[33]和我们的SPRINTER生成的查询计划及其性能。系统-x是一份功能齐全的最先进的商业化备忘录 ry数据库系统，支持索引驱动的查询执行和查询优化技术，如开花过滤器和自适应连接。它支持许多查询处理技术，如 索引驱动的查询执行、bloom过滤器和自适应连接。在图4(a)中，它为查询计划生成一个左深连接树，并以操作员一次操作的方式执行该计划。C1、C2和C3 是相同的关系，即关系C，但在查询处理过程中作为不同的关系来处理，这在OLAP处理系统中很常见。除了系统-x之外，还有许多系统包括 DingMonetDB[9]、CoGaDB[10]、Kinetica[21]和快速步骤[34]生成与图4(a)中几乎相同的查询计划，并以一次操作符的方式执行它。

​ 图4(a)中的计划在最后一个连接之前生成22.3亿(B)中间元组作为左操作数，并以CS的1.44亿(M)元组作为右操作数。然后，它构建了散列t 能够探测144M元组，并探测2.23B中间元组。因为连接操作是FK-FK连接，并且在哈希表中有许多重复的键值，所以num 在探测连接过程中，哈希表中的关键值被访问，我们称之为探测成本，这是巨大的，特别是160.9B倍。

​ OmniSci[33]是一个开源的协同处理数据库系统，其中协同处理意味着同时利用cpu和gpu进行查询处理。在图4(b)中，它生成了一个左深jo的查询计划 如图4(a)所示，但以非阻塞和流水线的方式执行计划，它不会生成和存储供连接的中间结果。详细地说，它评估一系列所有连接操作 通过对关系SS的SR、CS、I、D、D、C1、C2、C3}顺序构建的7个散列表，依次探测连接树中的错误。在中，SS和SR之间的第一个连接 图4(b)对29M元组SR的每个SS元组进行探针，探针成本为4.1B。然后，第二个连接探测每个元组通过了针对散列的第一个连接 1.44M元组的CS表，探针成本为20.7 B. 我们可以类似地计算每个连接的探针成本，总探针成本为25.8 B.

​ 短跑器是我们提出的方法跨所有相关层和模块无缝集成到OmniSci中的原型系统。我们选择OmniSci作为SPRINTER的基础系统，因为它是o 没有最先进的开源现代数据库系统。虽然我们提出SPRINTER使用OmniSci作为基础系统，但SPRINTER原则上可以使用任何数据库系统作为基础系统。在Fi中 Gure4(c)，SPRINTER生成一个查询计划，由多个白色的二进制连接操作符和一个红色的n-ary连接运算符组成。它分别执行三个连接子树，即S1={SS、C1、D， I}、S2={SR、C2}和S3={CS、C3}，以像OmniSci这样的流水线方式，然后，以一次操作符的方式执行无连接操作符，这将在第5节中描述。当我们计算时 S1、S2、S3的探针总成本仅为758M。此外，当我们计算在三个连接子树的结果中处理n-ary连接的总成本时，它变为312M.O 总之，SPRINTER的总处理成本约为1.07B，比其他两个系统的总处理成本要小得多。

​ 图4(d)显示了上述三个系统对TPC-DSSF=100数据库的查询性能。性能结果表明，OmniSci通过消除la，提高了系统x的性能 通过管道得到Rge中间结果，SPRINTER通过将单个大连接树分割成多个较小的连接子树并执行n个连接来提高OmniSci的性能 他是连接子树的结果。我们将解释一个比第6节中的图更精确的成本模型。

4查询规划方法

​ 在本节中，我们首先将在第4.1节中介绍用于生成包含单个n-ary连接操作符的查询计划的查询规划方法。然后，我们将该方法推广到更复杂的查询中 这样它就可以生成一个在4.2节中包含多个n-ary连接的操作符。

​ 图4：针对激励性查询的查询计划。

4.1单个n个连接运算符的查询

​ 对于查询规划，我们考虑一个来自给定查询Q的连接图，它在定义4.1中定义。

定义4.1。（连接图）查询Q的连接图G=(V、E、f(v∈V)、д(e∈E)、h(e∈E))是一个无向多重图。顶点v∈V表示Q中连接的关系，边=(X，Y) ∈E是两个端表X和Y之间的连接操作，特别是X[i]和Y[j]之间的连接操作，其中i∈X和j∈Y。有三个标记功能f(v)、д(e)和h(e)。函数f(v)返回 关系v的类型，即事实或维数，函数д(e）连接操作的类型，即PK-FK或FK-FK-FK，以及函数h(e)等连接谓词e，即h(e)=(X[i]、Y[j] ).

​ 在本节中，我们考虑一个连接图G只包含通过FK-FK连接操作边缘连接的顶点子图的情况。我们将这样一个子图表示为核心子图 并在定义4.2中定义它。

​ 定义4.2。（核心子图）连接图G的核心子图，即核心=(Vc，Ec)⊆G，是其中任何两个顶点X和Ys.t的连接分量。X∈Vc和Y∈Vc通过as连接 Ex，y EC S.T。 D（e∈ex，y）=fk-fk，f(x)=f act and f(y)=f act。

​ 在图3中，一个子图{SS，SR，CS}是一个核心子图，因为所有的顶点都是事实表，一对顶点SSSSR通过FK-FK边连接，另一对顶点SRRCS也是 通过FK-FK边缘连接。子图{SS、SR、CS}是图3中连接图中通过FKFK边连接的最大子图。如果一对顶点SSSSR有两个边{e1，e2}s.t.，g(e1)= FKKFKandg(e2)=PKKFK，只有e1属于核心子图{SS，SR，CS}。

​ 在大多数情况下，系统可以基于元数据和统计数据找到一个核心子图，如引用约束、表基数和列的不同值的数量。以防一个系统 m对它们的了解有限，查找它们的技术，包括自动外键检测[12,48]，将有助于找到一个核心子图。

​ 如果一个连接图G只有一个核心子图核心，那么我们可以将G分解为核心子图核心和一组彼此在边不相交的非核心子图。在这里， 核心或非核心的任意两个子图都可以在两个子图之间有一个或多个公共顶点。图5显示了图3中连接图的一种可能的分解，其中有 一个单核子图核心={e4、e5}和三个非核子图G1={e3、e6、e7}、G2={e2}和G3={e1}。一般来说，一个连接图有很多可能的分解。我们表示se 可能的分解的t。例如，我们可以将连接图分解为单个核子图核心={e4、e5}和单个非核子图G1={e1、e2、e3、e6、e7}。然后，我们就可以使用r 将上述两种分解方法分别表示为D1={核心、G1、G2、G3}和D2={core、G1}。

​ 图5：激励性查询的分解。

<<<<<<< HEAD
算法1提供了仅包含单个核心子图的查询的基本查询规划方法。这种方法背后的直觉是使一个核心子图成为一个查询计划和mak的根节点 用非核心子图表示查询计划中的根节点的子节点。它从连接图G（行2）中找到可能的分解{Di}，从每个分解Di中生成一个查询计划Pi 3-9)，然后选择其中成本最低的最佳计划P∗（第11行）。我们将在第6节中介绍一个计划的成本模型。当从非核心子图制作连接子树Sj时 ，通常有很多可能的连接子树。然而，我们只考虑为一个非核心子图生成一个左深二进制连接子树，这可以显著减少 查询计划的搜索空间。将核心子图作为查询计划的根也是减少查询计划搜索空间的 heuristic式方法。 heuristic式方法背后的直觉是 通过在查询计划的最后一步处理事实表上的FK-FK连接，从而减少从非核心子图中的连接操作生成的中间结果量。
=======
​ 算法1提供了仅包含单个核心子图的查询的基本查询规划方法。这种方法背后的直觉是使一个核心子图成为一个查询计划和mak的根节点 用非核心子图表示查询计划中的根节点的子节点。它从连接图G（行2）中找到可能的分解{Di}，从每个分解Di中生成一个查询计划Pi 3-9)，然后选择其中成本最低的最佳计划P∗（第11行）。我们将在第6节中介绍一个计划的成本模型。当从非核心子图制作连接子树Sj时 ，通常有很多可能的连接子树。然而，我们只考虑为一个非核心子图生成一个左深二进制连接子树，这可以显著减少 查询计划的搜索空间。将核心子图作为查询计划的根也是减少查询计划搜索空间的启发式方法。启发式方法背后的直觉是 通过在查询计划的最后一步处理事实表上的FK-FK连接，从而减少从非核心子图中的连接操作生成的中间结果量。

c050ef667e21f7ae5e2e8f8620a157be214c5b23

​ 图6显示了由上述两个分解的D1={core、G1、G2、G3}和D2={core、G1}生成的两个可能的查询计划树。图6中的每个二进制连接运算符都对应于一条绿色的边 在图5中。相比之下，图6中的每个根n-连接运算符对应于图5中的一组蓝色边{e4，e5}。我们注意到，核心或非核心子图之间共享的关系出现了mu 查询计划中的重复次。例如，C在图6(a)中出现了三次，因为它在图5中的三个子图{G1、G2、G3}之间共享。当比较图6中的两个查询计划时，我们可以说 计划P1通常成本低于计划P2，因为P1再扫描一个维度表C两次，而P2再扫描两个事实SR和CS一次。

图6：针对激励性查询的查询计划。

4.2多个n个连接运算符的查询

​ 在本节中，我们将解释当一个查询中有多个核心子图时的查询规划方法。我们将核心子图的数量表示为Ncore。针对这种qu的一种朴素的查询规划方法 ery是将连接图中的一个特定的核心视为连接图中的唯一的核心，并将第4.1节中解释的方法应用于连接图。一种更好的规划方法是推广方法 将算法1递归地应用于所有非核心子图。对于广义版本，我们只需要进行修改算法1中的第6行。详细地说，我们称为算法1中第6行的以下算法2，通过考虑Gj为算法2的输入，并考虑算法2的输出P∗为Sj。在奥尔戈里斯市 m2，第1行为Gj生成一个传统的查询计划Pold（例如，左深连接树），这是由基础系统的查询规划方法(例如，SPRINTER的OmniSci)完成的。IfGj没有核心的s 然后，算法2返回常规的查询计划作为输出。如果Gj有一个或多个核心子图，则第3行将生成一个查询计划Pnew，其中有一个n-ary连接运算符作为Gj，w的根节点 hich是由算法1完成的。然后，第4行估计Pold成本和PNew成本，这将在第6节中详细解释。在比较了两种成本后，只有计划的成本较低 作为输出返回。

4.3搜索空间

​ 我们可以用我们的方法计算一个查询的可能查询计划的数量。一般来说，在连接图G中有Ncore(G)核心子图，分解的数量取决于哪个c 矿石子图被选为一个根节点。我们将将核心子图Ci作为根节点时的分解数表示为Ndcmp(Ci)。如果算法1中的第6行总是使用传统的计划 对于一个子图，每个分解将生成单个查询计划。因此，我们可以计算具有由一个朴素m生成的单个n-ary连接运算符（作为一个根节点）的可能计划的数量 如E式。1.

<<<<<<< HEAD
如果算法1中的第6行使用算法2，则每个分解都可以生成多个查询计划。对于一个特定的分解Dj(1≤j≤Ndcmp(Ci))，我们假设存在Nsubg(Dj)非核心子图。例如，在图6中，Nsubg(D1)=3和Nsubg(D2)=1。对于每个子图Gk，都存在Nrecur(Gk)查询计划。因此，我们可以计算出该基因产生的可能计划的数量 已排序方法，最多可以有Ncore(G)n-ary连接运算符，如Eq。2.
=======
Ndcmp 是以ci为子图核心时，分解数，Ncore个核心子图，

如果算法1中的第6行使用算法2，则每个分解都可以生成多个查询计划。对于一个特定的分解Dj(1≤j≤Ndcmp(Ci))，我们假设存在Nsubд(Dj)非核心子网格 hs。例如，在图6中，Nsubд(D1)=3和Nsubд(D2)=1。对于每个子图Gk，都存在Nrecur(Gk)查询计划。因此，我们可以计算出该基因产生的可能计划的数量 已排序方法，最多可以有Ncore(G)n-ary连接运算符，如Eq。2.

c050ef667e21f7ae5e2e8f8620a157be214c5b23

​ 在图6(a)中，可以生成3！=6查询计划取决于连接子树的顺序。在式式中。2，我们不考虑连接子树之间的顺序，因为总处理时间 连接子树是相同的，不管顺序如何。我们将在第5节中详细解释它。因此，我们可以在算法1中第9行连接子树。

5n-ARY JOIN处理方法

​ 在本节中，我们将介绍SPRINTER的n连接处理方法。我们将执行一种处理具有一组子连接子树的n个连接运算符的朴素方法 g请执行以下六个步骤。

• 步骤1：逐个评估{S1、·、·、Sn}。

• 步骤2：计算{S1、·、··、Sn}结果的必要统计数据。

• 步骤3：估计连接变量的每个全局顺序的成本。

• 步骤4：选择最佳的全局变量顺序。

• 步骤5：按全局顺序对{S1、·、·、Sn}的结果进行排序。

• 第6步：在n个已排序的关系上合并连接。

  对于一个n-ary连接操作符，子节点的可能顺序数变为n！在原则上。我们假设n个连接运算符的子级从左到右计算。对于n 在朴素方法中，无论处理子节点的顺序如何，处理n-ary连接运算符的所用时间都变得相同。图7(a)显示了一个用于评估三个连接子的示例时间线 根据上述六个步骤。如果n-ary连接运算子具有关系，而不是将连接子树作为其子树，例如，图6(b)中的SR2和二硫化碳，我们考虑rela t值分别为S2和S3。我们将将Si计算为Teval(Si)的经过时间，以及对其结果进行排序的经过时间表示为Tsort(Si)。我们假设Teval(Si)=Tsort(Si)(1≤i≤3) 为了简单起见，Teval(Si)<Teval(Sj)(i<j)。步骤2-4在图7(a)中的时间t1时完成，**它确定了连接列之间的一定全局应用TJ算法的顺序。**步骤5 根据全局顺序对每个结果进行排序，步骤6在时间t2时使用第2节2.2中所述的TJ算法完成。我们可以知道，在图中，总经过的时间不会改变 即使Ure7(a)，即使{S1、S2、S3}的评估顺序发生了改变，或者即使是Teval(Si)>TSort(Si)或Teval(Si)<Tsort(Si)。

​ 在朴素方法中，Teval(Si)和Tsort(Si)由于存在一种同步障碍而不能重叠

​ 图7：图6(a)中三个连接子树{S1、S2、S3}的评估时间线。

​ 时间t1，因此，即使我们利用GPU进行排序步骤，也很难大大减少总运行的时间。因此，我们使用一种改进的方法来处理一个n-ary连接算子，它由of请执行以下四个步骤。

• 步骤1：估计连接变量的每个全局顺序的成本。
• 步骤2：选择最佳的全局变量顺序。
• 步骤3：对结果进行重叠排序。
• 步骤 4: 在n个已排序的关系上合并连接。

​ 图7(b)显示了修改后的方法的时间线。在步骤1-2中，它首先确定全局变量的顺序，而不计算{S1、···、Sn}的结果的统计数据 t1)。我们将在第5.1节中详细解释如何确定SPRINTER的整体顺序。然后，在步骤3中，它重叠了使用CPU评估Si，并使用GPU(i，j)对Sj的结果进行排序。在t中 他的方法是，无论{S1、S2、S3}的处理顺序如何，图7(b)中的总经过的时间仍然没有改变，而且，无论是Teval(Si)>Tsort(Si)，还是Teval，都没有改变 (Si)<Tsort(Si)。

​ 我们可以进一步减少如图7(b)所示的总运行时间。SPRINTER可以利用流水线技术来评估每个子连接子树，因为它的基础系统，即OmniSci，是一个 基于流水线技术。由于SPRINTER可以同时使用CPU和GPU，并且同时使用流水线技术，评估Si和排序Sj的结果可以重叠w 即使我=j。图7(c)显示了同时使用CPU和GPU并启用流水线技术时的时间线。我们假设S1的中间结果的大小， S2和S3分别是在GPU中一次可以处理的数据大小的1倍、2倍和3倍。图中红色虚线表示主机（即主存）到设备（即GPU内存）的拷贝，记为H2D 复制。 对于 S2 和 S3，部分中间结果是通过流水线技术收集和块复制到 GPU 内存进行排序。

 即使我们同时使用CPU和GPU，也使用流水线技术，总运行时间不会根据子级的处理顺序而改变。我们考虑Teval(Si)+光标 t(Si)作为儿童Si的成本。图7(c)显示了评估低成本子节点优先(LCF)的策略，而图7(d)显示了评估高成本子节点优先（HCF的策略 )。我们可以看到这两种策略都同时完成了。无论Teval(Si)>Tsort(Si)还是Teval(Si)<TSort(Si)，这种趋势都保持不变。因此，我们使用任何固定的策略 y（例如HCF）用于对n连接运算子的子级排序。

5.1全球订单的确定

​ 一般来说，在合理短的时间内精确计算每个全局连接变量顺序的成本是一个非常具有挑战性的问题。现有的最坏情况最优连接算法也是我们的 e heuristic式算法实际上是为了确定了图模式查询的全局顺序[1,13,44]。本文还提出了一种 heuristic式算法来确定一个相当好的全局算法 对于OLAP查询的可变顺序快速，我们将在未来的工作中进一步改进。

​ 算法3展示了我们的 heuristic式算法。给定一个核心子图，它找到所有的连接变量，并为每个连接变量准备一个三重态w，|Ew|，Cw，其中w是一个连接变量，|Ew|，n 连接条件的对数，即具有w的关系的基数之和。例如，图8显示了TPC-DSQ17的一个核心子图，它有三个连接变量，项目、cust和票据。 对于项目，|Estem|=2，和Citem=||CS||+||SR||+||SS||。然后，该算法按(|Ew|，Cw)的降序对三联体列表进行排序。在这里，如果一个连接变量 w1 可能与另一个连接变量 w2 在 (|Ew |,Cw ) 方面联系在一起，则其中一个可以在全局变量顺序中排在另一个之前。 例如，item ≺ cust ≺ ticket 和cust ≺ item ≺ ticket 都是允许的。 直观地，算法选择具有更多连接条件和可能有更多元组作为更高优先级处理的连接变量，以减少对排序关系进行二分搜索的总量。 我们将在第 7.3 节中展示这种方法的影响。

​ 图8：TPC-DSQ17的核心子图。

5.2排序策略

​ 在本节中，我们将介绍我们为每个子节点连接子树的结果选择特定排序算法的策略。图9显示了考虑到以下三个因素的策略：avai GPU的不能力，要排序的数据的大小和排序列的数量。首先，如果GPU不可用，SPRINTER使用CPU排序，特别是一个基于非比较的算法，如果num 排序列的b只是一个，但在其他方面是基于比较的算法，如2.1节所述。其次，如果要排序的数据可以适应GPU内存，SPRINTER使用一个非比较基础 d或基于比较的GPU排序算法，具体取决于排序列的数量。第三，如果要排序的数据不能适合GPU内存，我们需要仔细选择一个排序算法 GPU排序缺乏良好实现的问题。据我们所知，GPU[7]的一个基于比较的算法的实现速度仅比CPU[37]的实现算法略快。

​ 图9：排序算法的选择策略。

​ 如果要排序的关系有多个排序列，并且大于GPU内存，典型的方法将将关系划分为子数组，使用基于比较的算法对每个子数列进行排序 m，并使用CPU合并子阵列。

​ 但是，合并已排序子数组的成本可能非常大，因为随着排序列的索引增加（例如，第 3、第 4 位），每个已排序子数组中的列值都是重复的，并且没有按照特定排序列进行排序。 排序使用GPU和使用CPU合并实际上比排序慢在很多情况下使用 CPU，因此，我们使用 CPU 排序红线框中的情况，如果基于比较的 GPU 排序算法的性能为后来改进。 如果一个关系只有一个排序列，我们只在 2.1 节中使用异构排序，因为那里是基于非比较的非常快速的实现GPU算法，合并子数组的代价不是这么大。 我们将展示每个案例的实验评估在第 7 节的图 9 中。

​ 由于SPRINTER像其他现代OLAP系统一样使用柱列布局，它为每个Si的连接列阵组和1≤i≤)维护元组ID向量(tidVic)，其中使用前者 用于排序每个Si和连接{Si}，后者用于元组重建。在单个GPU中可以一次排序的最大元组数取决于排序算法的实现 使用ithm。例如，当我们对Si具有一个4字节连接列和4字节元组ID的NVIDIAGTX1080ti的结果进行排序时，我们可以使用大约14亿和7亿元组进行排序 分别为就地和不到位的分类。

5.3合并加入排序关系

​ 对于具有连接子树的任意连接操作子{S1、···、Sn}，由于我们有n个排序结果{Sˆ1、·、·、Sˆn}，通过对每个连接子树的结果进行排序，我们可以很容易地执行合并连接 gTJ算法。图10(a)显示了图8中核心子图的三元连接运算符的合并连接示例。为了简单起见，我们将列项、cust和票单表示为i、c和 t，分别。我们假设全局顺序是≺≺。SPRINTER扫描第一个连接变量i上的{CSˆ，SRˆ，SSˆ}，并假设当前的指针是i=2（蓝色箭头）。然后，它执行一个电阻 ual查询Q‘(c、t)=CSˆi=2(c)、SRˆi=2(c、t)、SSˆi=2(c、t)递归地在第二个连接变量c上，可以找到至少一个匹配，即c=4（绿色箭头）。因此，它执行一个更窄的resi 双queryQ‘’(t)=CSˆi=2、c=4（·）、SRˆi=2、c=4(t)、SSˆi=2、c=4(t)递归。残差查询Q‘’(t)找到两个匹配的元组{（2,4,1)，(2,4,1）}。同样地，它还可以找到另外四个匹配的t 通过在CSˆ中移动绿色指针，（2,4,1）的组。这样，我们就可以处理一个具有许多FK-FK连接的核心子图，而不产生大量的中间结果。

​ 人们可以考虑另一种合并连接方法，它只通过i对CS、SR和SS进行排序，从而降低了排序成本。然而，它可能会显著增加合并连接的成本，从而降低整体成本 性能。图 10(b) 显示了这样一个示例，其中 c 列中的值未排序，我们假设 CS 和 SR 与图 10(a) 相同。 当执行残差查询 Q′(c,t) = CSˆ i=2(c), SRˆ i=2(c,t), SSˆ i=2(c,t)时，我们必须扫描残差关系 SSˆ i =2 在 c 列上按顺序进行，而不是进行二分查找。 因此，根据所有连接变量对核心子图中的所有关系进行排序很重要。

​ 图10：图8中的核心子图的合并连接示例。

​ 表2：符号汇总表。

6个关于查询优化的成本模型

​ 使用n-ary连接运算符的查询处理可能并不总是比仅使用二进制连接运算符的传统查询处理方法获得更好的性能。因此，我们使SPRINTER成为一名将军 e只有在成本模型有利时才包含n个连接算符的查询计划。给定一个查询Q，算法2考虑了原始计划Pold和新计划Pnew。因此，我们需要 建立成本模型成本(PNew)和成本(Pold)，以确定成本(PNew)<成本(Pold)。特别地，我们建立了关于基本系统的成本的成本模型(Pold) （即，OmniSci）。我们将在查询处理过程中访问的元组（或散希表中的元素）的数量作为成本的度量。表2总结了本节中使用的符号。

6.1基础系统的成本模型

​ 我们认为查询计划 Pold 由 M- 1 个二元连接运算符组成，用于 M 个关系。 每个输入关系 Ri 可能有自己的一组过滤谓词 pi，我们在将谓词应用于关系 (1 ≤ i ≤ M) 后考虑结果关系 Fi。我们考虑PK-FK连接或FK-FK连接的每个二进制连接运算符都使用主内存哈希连接算法进行计算，该算法不仅在OmniSci[33]中很常见，而且在其他内存查询中也很常见 处理系统[5,8,19,28,50]。我们假设查询处理探测最左关系的每个元组，即F1与由其余关系{Fi|2≤构建的散列表集相比 i≤M}以流水线的方式。情商。3显示了Pold的成本函数，其中构建(Fi)是构建哈希表的成本函数(Eq。4)和探测(F1)探测元组的成本函数 F1（Eq。5).

​

​ 在式式中。4、κ是一个常数值，表示在构建相应哈希表的关系Fi上的完整扫描数。我们使用κ=2，因为我们的基础系统使用了高级处理的通用技术 连接键[19]的直方图，这需要对关系进行两次完整扫描。值取决于所使用的基本系统。在式式中。5，我们认为术语Ifj|1当j>i时变成1。用于 例如，由于术语Iij=3(即|=1=1，|1探测|2的成本成为||F1||×dup2。然而，当j≤i(例如，Ii=4j=3f2)时，这个术语就会变成本身。没有基因的丢失 相反，我们可以假设F1的每个元组与F2散希表中的dup2元素进行比较，而不管散希表的类型如何（例如，开放寻址、单独的链接）。探测a 针对F2，我们可以假设总共有一个||F1||·F2元组存活下来，并对F3进行探测。也就是说，将每个||F1||·f2元组与f3散列表中的dup3元素进行了平均比较。 对F3进行探测后，共有||F1|的|·f2·F3元组存活，每个元组与F4散希表中的dup4元素进行比较。这样，我们就可以聚合e的数量 在管道中的散列表中访问的clives。5.

6.2SPRINTER的成本模型

​ 一般来说，查询计划Pnew由M个关系的n-ary和二进制连接运算符组成。我们假设Pnew中至少有一个n个连接运算符，否则不需要生成Pnew。在p 根据第4节中的查询规划方法，Pnew有一个n-ary连接运算符作为根。我们将n-ary连接算子表示为O，并假设O有连接子树作为其子树 {Si|1≤i≤n}。我们注意到，如果一个连接子树Si也有一个或多个n-ary连接运算符，那么由于第4节中的查询规划方法，它也有该运算子作为根。

​ 因此，我们可以递归地定义 Pnew 的成本函数，如Eq.6，其中cost（Si）变成了等式。 3 如果 Si 没有 n 元连接运算符并成为Eq.6 否则。

​ Eq.7表示n-ary连接处理的成本，其中包括n个连接子树结果的排序成本和使用TJ算法的连接成本。SPRINTER使用不同的排序算法 算法根据排序输入，即排序列的数量和表的大小，我们省略了这些算法的成本分析，因为它们在精简中已经众所周知了特性。

​ 如果w1≺w2≺···≺wL被确定为n个连接操作器O的全局变量顺序，Eq。8显示了合并n个排序关系{Sˆi|1≤i≤n}的TJ算法的成本。我们表示的是 与特定连接变量a(w)相关的关系数。例如，图8中的u（项目）=2、andu（票）=1。我们可以考虑在所有关系之间具有最小基数的关系 与连接变量w相关的（1)、(1）、S(u(w))，其基数表示为Nwmin。同样，我们可以考虑w具有最大基数的关系，并表示其基数 作为Nwmax。然后，单个连接变量w的TJ算法的代价变成了Eq。9，这在[44]中也进行了总结。

Eq. 9,术语(1+loд（)表示对下一个键值的二进制搜索的摊销成本。由于TJ根据全局变量的顺序连续搜索关系，因此，总数 TJ的成本变成了Eq.8.

7 实验评价

​ 在本节中，我们将给出两类实验结果。首先，我们将短跑器与现有的OLAP查询处理系统所经过的复杂OLAP查询时间i进行比较 nTPC-DS基准。其次，我们展示了SPRINTER的特点。详细地，我们通过实证验证了第5节中描述的排序算法的选择策略，该策略提出了成本模型 以及排序算法的性能。

7.1 实验设置

​ 查询和数据集：在 TPC-DS 基准测试中，共有 26 个 TPC-DS 查询至少有一个 FK-FK 连接 [30]。在这些查询中，我们发现只有 11 个查询可以在 比较所有 OLAP 系统，并且至少有一个存在解析错误的 OLAP 系统不支持剩余的查询。 因此，我们使用 11 个查询来比较系统。 我们注意到，对于没有 FK-FK 连接的查询（例如，99 - 26 = 73 个 TPC-DS 查询），SPRINTER 显示出与基本系统（例如 OmniSci）相同的性能，因为 SPRINTER 使用相同的查询计划 此类查询的基本系统。

​ 为了评估SPRINTER的特点，我们通常使用合成查询，这些查询是通过修改第3节中的激励查询而生成的，并在TPC-DS数据库上评估它们。对于数据集 ，我们使用了从SF=100 (100 GB)到SF=400 (400 GB)的TPC-DS数据库，这是以往研究中广泛使用的规模。

​ 环境：我们在一台机器上进行所有实验，配备了两台英特尔Xeonen10核cpu，512GB主存和一个11GB的NVIDIAGTX1080TiGPU。操作数 使用的名词名词系统是CentOS7.5。

系统比较：与短跑系统相比，OLAP系统分为两种类型：基于cpu的系统(如Syssem-x)和协同处理系统(如OmniSci)。所有的系统都是基于 柱状存储布局。我们注意到，每个系统都被设置为尽可能多地同时使用主存和GPU设备内存（仅用于共同处理系统）。表3总结了其中的功能 在实验中使用的系统。

表3：系统比较汇总。

​ 对于基于cpu的系统，System-Y是最先进的商业化的OLAP数据库系统之一，支持索引驱动的查询执行和查询优化技术，如bloomf 过滤器的散列连接和基于成本的查询规划器，这类似于System-X。但是，它生成了一个二进制灌木树的查询计划，这是与System-x的主要区别之一。此外，Sys tem-Y以流水线的方式处理查询计划，并支持查询执行的协变性。我们使用最新版本的系统x和系统y进行实验。

​ 我们也比较SPRINTER 与著名的矢量化引擎 Mon etDB [9] (v11.31.13) 和 Actian Vector [51] (v5.1)，其中前者使用一次操作员模型，但后者使用
用于查询评估的流水线模型。 对于协处理System-Z 是最先进的商业化系统
利用 GPU 的 OLAP 数据库系统，我们使用其最新的发布用于实验。 我们还使用两个开源协同处理系统进行评估，OmniSci [33] (v4.5.0) 和CoGaDB [10] (v0.4.2)。 我们表示 SPRINTER 的版本仅使用 CPU 作为 SPRINTER(C) 和 SPRINTER 之一使用 CPU 和 GPU 作为 SPRINTER(G)。 由于SPRINTER在一次操作符中执行 n 元连接操作符尽管它以流水线方式执行每个连接子树以这种方式，我们将其查询评估模型描述为一次操作符和流水线的组合。

7.2 性能比较

​ 图11显示了SPRINTER(C)和SPRINTER(G)与第7.1节中描述的现有OLAP系统的比较结果。在图中，操作。m。是指由于故障而导致的查询评估失败 内存。T.O.表示超时（超过1800秒）。M.E.是指由于分割故障和分配不良等主存相关错误而导致的查询评估失败。y轴是对数比例尺 e图。我们使用一个SF=100的数据集，因为一个更大的数据集会产生大量的o.o.o.m。在许多系统中。对于每个系统和每个查询，我们运行五次查询以预热系统并报告bes 未经过时间。

​ 与基于cPU的系统的比较：图11(a)显示了与基于cPU的系统的比较结果。我们首先注意到，只有SPRINTER成功地执行了所有11个查询，但其他系统f 在至少一个查询中出错。从大量的中间结果或电信号从大量的探针成本，在第3节中解释。此外，SPRINTER(C)和SPRINTER(G)均超过 错误格式比较测试的大多数查询的所有系统，这是由于它们不同的查询计划和不同的连接处理。对于所有系统组合通常执行的查询 即Q37、Q64和Q95，SPRINTER在系统中表现最好。特别是，对于Q64，SPRINTER(G)与Syssem-Y、System-X、MonetDB和Actia相比，提高了性能 n向量分别为6.6、7.4、20.1和5.1倍。

SPRINTER(C)和SPRINTER(G)之间的性能差距并不大，因为数据大小相对较小(SF=100)。我们注意到，当前的SPRINTER没有使用先进的查询优化技术 系统x和系统y使用的niques，因为它的基础系统，OmniSci，还不支持它们。因此，将优化技术应用于O上，可以进一步提高SPRINTER的性能 mniSci或SPRINTER。

​ 图11：使用TPC-DS基准查询(SF=100)的性能比较。

​ 对所有测试的查询进行比较。与基于cpu的系统相比，现有的协同处理系统在处理sam时有更多的故障，通常性能更差 e查询。这是因为协同处理系统通常不使用先进的查询优化技术，而且还不够成熟，无法利用GPU来有效地处理复杂的查询。 例如，OmniSci在图4中优于System-X，因为激励查询的关系具有高fi值（即接近1）。然而，图11中的TPC-DS查询通常fi较低 值（即，接近0），因此，配备支持索引驱动的查询执行和查询优化技术的System-X优于OmniSci。

​ OmniSci只能执行两个查询，Q37和Q97，尽管使用OmniSci作为基础系统的SPRINTER可以执行所有11个查询。OmniSci和CoGaDB首先尝试使用GPU执行给定的查询。 但是，如果尝试失败，OmniSci和CoGaDB将使用CPU和主内存执行查询。这种两步方法增加了执行查询所需的数据无法匹配时的运行时间 在GPU内存中。此外，OmniSci以流水线的方式执行查询，而CoGaDB则以任意操作员的方式执行查询。因此，CoGaDB往往由于运行运行而失败。从大的中间结果a d缺乏查询优化技术。对于OmniSci，即使在使用主内存执行查询时，如果查询变得更加复杂，它也往往会错误地估计所需的内存量， 因此，左较深的连接树变得越来越深。因此，OmniSci往往由于错误内存分配的m.E.或FK-FK连接的大量探测成本而失败。

​ 相比之下，SPRINTER虽然是基于OmniSci的，但没有失败，查询性能显着提升。 SPRINTER生成的查询计划中的左深连接子树比OmniSci的连接树小很多，同时， 几乎没有用于构建哈希表的事实表，如第 3 节所示。 OmniSci 可以充分评估这种小而简单的连接子树，而不会导致 ME 的失败此外，SPRINTER 的探测成本远小于 的 OmniSci 由于 n-ary join 处理，所以没有 T.O. 对于 Q37 和 Q97，SPRINTER(G) 与 OmniSci 相比，性能分别提高了 88.8 倍和 1.5 倍。

7.3 SPRINTER特征

​ 成本模型的验证：我们对第6节中的成本模型进行了经验验证。在算法2中，我们决定是否使用传统的左深连接树的计划（表示为左深）或更多 基于成本模型的无连接操作（表示为无连接操作）的总体计划。因此，成本模型尽可能地与实际性能相一致是非常重要的。

​ 图12：成本模型的验证。

​ 图12显示了基于成本模型的估计和在查询空间中的实际性能结果。对于查询空间，我们将图3中的激励查询的（1）修改为数字o fFK-FK连接、（2）过滤选择性(即fi)和（3）在散列表中具有相同键的元素的平均数量(即dupi)。激励查询中FK-FK连接的数量为两个 （图12(a)），通过cust列连接（连接）一个新的事实表CR与CS和C，该数字变成3（图12(b)）。我们在y轴上的选择性fi在0.0001和1.0之间变化 通过调整c的fi。我们还在x轴上改变dupi，通过不同的连接列将C替换为不同的维度表，如CD、CA、I和HD，从而改变dupi。例如，如果我们使用CD而不是C和joinCD 通过cdemo列的事实表，{dupi}大约变成6(dupi=6)。在这种情况下，我们通过调整CD的fi来改变y轴上的选择性fi。类似地，我们设置了dupi= 11使用C，dupi=19使用CA，dupi=44使用I，dupi=126使用HD。图12显示了结果，其中红色单元格表示左深平面比n型灌木丛获得更好的性能 平面图，蓝色单元格表示相反的情况。在图中，在大多数单元格的估计和实际结果方面都优于左深部计划 查询空间。我们注意到，该估计通常与实际结果一致（90%匹配）。

​ 全局变量阶 heuristic式算法的验证：我们使用三个TPC-DS查询Q17、Q25和Q29(SF=100)验证了 heuristic式算法在算法3中的有效性。在的 图13左表，Ew和Cw是算法3中使用的统计数据，Rank是按(|Ew|，Cw)对变量进行排序时的排序。所有三个qu的核心子图 经过测试的Q17、Q25和Q29由三个连接变量C、I和T组成。存在3！这三个变量的=6个顺序，图13中的右图显示了s的查询处理时间 ix对这三个查询的不同顺序。根据我们的 heuristic式算法，I≺C≺T和C≺I≺T的性能应该最好，而T≺I≺C和T≺C≺I的性能最差。此前 预测的结果与图中的实际结果一致。这意味着我们选择良好的全局变量顺序的 heuristic式算法很简单，但很有效。

​ 图13：不同全局变量顺序的结果。

​ 图14：性能分解的结果。

​ 性能细分：图14显示了使用三个TPC-DS查询Q17、Q25和Q29对SPRINTER的微观评估结果。基于三种主要技术，有五种可能的配置 提出：名词连接处理（简称，名词），在算法3中选择一个全局变量顺序。O.)并将Teval与Tsort重叠(很快，O.E.)。在图14中，没有输出选项平均值 s随机选择一个全局变量顺序，而不使用算法3。没有O.E.选项意味着评估连接子树，然后对其结果进行排序，如图7所示。在图中，第五条，即， 没有N-ary、没有V.O.和没有O.E.，显示了基础系统的性能，即OmniSci。

​ 在图中，N-ary选项提高了Q17和Q25的查询性能。第四条(即N-ary，但没有V.O和没有O.E)比第五条表现得更差的原因 e系统)是由于随机选择的全局变量顺序较差。结果表明，不仅n-ary查询处理，而且选择一个良好的全局变量顺序是重要的 f性能。在第二（即V.O，但没有O.E）和第三（即O.E，但没有V.O）条之间，第二条比第三条提高性能更显著 （即，没有输出和无输出）。结果意味着选择一个良好的全局变量顺序比与Tsort重叠Teval更重要。总的来说，只有没有O.E的N-ary和V.O选项才能超过其性能 m是所有已测试的查询的基本系统。优化选项只是进一步提高了性能。

​ 排序性能：我们通过经验验证了选择连接算法的策略。图15显示了表1中排序算法的性能评价。当对Fi中的单个列进行排序时 Gure15(a)，cpu半径比cpu合并快，gpu半径比gpu合并快，如图9所示。当对图15(b)中的多列进行排序时，gpu合并仅比mergecpu合并稍快，如5.2节所示。当对大于G的单列关系进行排序时 图15(c)中的PU内存，异构排序比cpu半径快得多。总的来说，实验结果验证了图9中的策略。

图15：排序策略的验证。

8 相关工作

​ 多路连接处理：最近，人们提出了最坏情况最优(WCO)连接算法来评估图模式查询[31,44]中发生的多路连接。它们在理论上提供了一个紧密的结构 通过执行多排序关系之间的一种集交集，以多路连接结果的坏大小进行约束。其中一些是[1,31,44]需要构建一个大规模的inde x表示加入前的全局变量顺序。它们对于在少量关系上有一些全局变量顺序的图模式查询很有用。然而，将它们应用于广告-中却具有挑战性 特殊的OLAP查询，因为每个OLAP查询在大量关系上都有许多可能的全局变量顺序。

​ [2,13,49]的一些研究讨论了分布式环境上的多路连接处理。他们的优化目标是通过重新分配多个连接关系的组合来最小化通信成本 r，而不是一次变换连接操作的一对输入关系。

​ WCO连接算法的查询计划：DunceCap[36,43]专注于为WCO连接算法生成超树查询计划。它利用了inp的最小超树宽度之间的连接 ut查询和查询结果的大小。在这里，宽度表示一个给定的查询与无环查询[32]的距离或相应的超图[38]的循环程度。具有mi的计划树 最小宽度保证了最小的最坏情况下的输出大小，因此，它的查询性能与宽度[4]成正比，这被称为agm绑定。

​ DunceCap 对于图数据集上的循环查询（例如三角形查询）很有用，因为它利用超图来捕获查询中存在的循环。 然而，它不适用于 OLAP 查询，因为它们通常是非循环的。 例如，第 3 节中的激励查询在相应的超图中没有循环，因为 C1、C2 和 C3 在超图中被视为不同的关系。 中没有循环查询TPC-DS 基准测试。

​ 对于此类非循环查询，超树宽度的概念无法提供确定最佳查询计划的洞察力。 此外，过滤谓词对大事实表可能会显着减少连接结果的大小，因此可能远离最坏情况的界限。

​ OLAP查询的协处理方法：近年来，数据库社区[14,15,17,35,42]已经积极研究了OLAP查询处理的协处理方法。它们可以按int类型进行分类 o两组：（1)加速数据库内核[15,42]和(2）端到端查询评估引擎[14,17,35]。协同处理方法的主要问题是GPU内存的限制，这可能会 由于主存和设备内存[14]之间频繁的数据传输而导致较高的I/O开销，或在运行时由于内存不足而导致故障。

9 结论

​ 本文提出了一种针对具有FK-FK连接的复杂OLAP查询的快速n-ary连接查询处理方法。它会生成一个包含n-ary连接运算符的查询计划，如果它优于 基于我们的成本模型的传统的左深二进制连接树。该计划可以通过将事实表格上的FK-FK连接放入一个n-ary连接操作符中，从而显著降低探测成本。我们也有p 提出了一种基于TJ算法和 heuristic式算法选择良好的全局变量阶的有效的n元连接处理方法。我们已经实现了原型系统短跑机t 我们提出的方法被集成到开源的内存OLAP系统OmniSci系统中，横跨所有相关的层和模块中。通过使用TPC-DS基准测试的实验，我们已经证明了 即使没有使用GPU排序，SPRINTER的性能也优于最先进的OLAP系统，尽管它的基础系统OmniSci达到了它们中第二差的性能。

ACKNOWLEDGMENTS

​ 这项研究得到了韩国政府(MSIT)资助的韩国国家研究基金会(NRF)的资助。2018R1A5A1060031)，国家特区基础科学研究项目 韩国科学基金会(NRF)由科学、信息和未来规划部资助。2017R1E1A1A01077630)，和信息通信技术规划评估研究所(IITP)gra 由韩国政府资助(MSIT)资助。2019-0-01267，基于gpu的超快多类型图形数据库引擎SW)。