之前做了一次，被骂的狗血淋头，没想到谢老师的要求这么高，也没想到科软的hxd们这么卷。。。都准备的这么好

pre要求

全英文讲诉，不能粘贴论文的文章，之前已经被骂过一次。

要求理解论文的主要思想，不要怀疑老师不懂，老师都是有研究过这些论文的。

ppt的讲诉，不能太长，要突出重点，

讲诉的时候，要随时应对老师的提问，提问包含概念的理解，重要公式要求出现中ppt中。

论文选题

相比研究之前的skyline，我更希望看点对我有用的东西，

所以我准备选取数据库方向的文章。

SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries. Yoon-Min Nam, Donghyoung Han, Min-Soo Kim. SIGMOD 2020

离谱，wps新版的划词翻译的地方还不好找，

如果不登陆的话，功能都是灰色的，微信扫描之后功能就亮了。

短跑器：一种针对复杂OLAP查询的快速n元连接查询处理方法
复杂OLAP查询的快速n元连接查询处理方法

<<<<<<< HEAD

超键(super key):在关系中能唯一标识元组的属性集称为关系模式的超键

候选键(candidate key):不含有多余属性的超键称为候选键

主键(primary key):用户选作元组标识的一个候选键程序主键

外键 (FK) 是用于建立和加强两个表数据之间的链接的一列或多列

通过将保存表中主键值的一列或多列添加到另一个表中，可创建两个表之间的链接。这个列就成为第二个表的外键。

一张表外键的值一般来说是另一张表主键的值。因此，外键的存在使得表与表之间可以联系起来

FOREIGN KEY 约束防止这种情况的发生。如果主键表中数据的更改使之与外键表中数据的链接失效，则这种更改是不能实现的，从而确保了引用完整性。如果试图删除主键表中的行或更改主键值，而该主键值与另一个表的 FOREIGN KEY 约束值相关，则该操作不可实现。若要成功更改或删除FOREIGN KEY 约束的行，可以先在外键表中删除外键数据或更改外键数据，然后将外键链接到不同的主键数据上去。

OLAP联机分析处理是一种软件技术，它使分析人员能够迅速、一致、交互地从各个方面观察信息，以达到深入理解数据的目的。

随着市场竞争的日趋激烈，企业更加强调决策的及时性和准确性，这使得以支持决策管理分析为主要目的的应用迅速崛起，这类应用被称为联机分析处理，它所存储的数据被称为信息数据。

数据仓库：数据仓库系统的主要应用主要是OLAP（On-Line Analytical Processing），支持复杂的分析操作，侧重决策支持，并且提供直观易懂的查询结果。

基本每家电商公司都会经历，从只需要业务数据库到要数据仓库的阶段。

• 电商早期启动非常容易，入行门槛低。找个外包团队，做了一个可以下单的网页前端 + 几台服务器 + 一个MySQL，就能开门迎客了。这好比手工作坊时期。
• 第二阶段，流量来了，客户和订单都多起来了，普通查询已经有压力了，这个时候就需要升级架构变成多台服务器和多个业务数据库（量大+分库分表），这个阶段的业务数字和指标还可以勉强从业务数据库里查询。初步进入工业化。
• 第三个阶段，一般需要 3-5 年左右的时间，随着业务指数级的增长，数据量的会陡增，公司角色也开始多了起来，开始有了 CEO、CMO、CIO，大家需要面临的问题越来越复杂，越来越深入。高管们关心的问题，从最初非常粗放的：“昨天的收入是多少”、“上个月的 PV、UV 是多少”，逐渐演化到非常精细化和具体的用户的集群分析，特定用户在某种使用场景中，例如“20~30岁女性用户在过去五年的第一季度化妆品类商品的购买行为与公司进行的促销活动方案之间的关系”。

这类非常具体，且能够对公司决策起到关键性作用的问题，基本很难从业务数据库从调取出来。原因在于：

1. 业务数据库中的数据结构是为了完成交易而设计的，不是为了而查询和分析的便利设计的。
2. 业务数据库大多是读写优化的，即又要读（查看商品信息），也要写（产生订单，完成支付）。因此对于大量数据的读（查询指标，一般是复杂的只读类型查询）是支持不足的。

而怎么解决这个问题，此时我们就需要建立一个数据仓库了，公司也算开始进入信息化阶段了。数据仓库的作用在于：

1. 数据结构为了分析和查询的便利；
2. 只读优化的数据库，即不需要它写入速度多么快，只要做大量数据的复杂查询的速度足够快就行了。

数据库 比较流行的有：MySQL, Oracle, SqlServer等

数据仓库 比较流行的有：AWS Redshift, Greenplum, Hive等

本OLAP查询，基于成本模型 生成包含 n 元连接运算符的 查询计划。

+：a+b所以‘+’就是二元运算符。
++：a++所以++就是一元运算符。

n元就是n个元素，n个表做连接运算

本文结论：SPRINTER 的性能优于最先进的 OLAP 系统。

keywords: n元连接运算符，查询规划，查询优化，FK-FK连接，复杂OLAP查询处理，协同处理

现有系统利用了各种技术，例如中间结果的流水线

OLAP查询处理的概念现在正被广泛应用于各种应用中，包括图形分析[1,13]、人工智能[22][20,26]和生物信息学

In particular, the number of queries which

contain join operations between a pair of foreign (or non

unique) keys rather than a conventional pair of primary and

foreign keys increases in the applications.

!尤其是，查询的数量包括了外键之间的连接操作，而不是增加在应用程序的传统主键和外键

本文将这种连接操作表示为FK-FK连接，一个FK-FK连接通常会产生一个lar 由于重复的连接键值而导致的连接结果数。

流水线技术通过在一组由其余关系构建的哈希表中查找探测关系的每个元组来计算连接树中的一系列多个连接运算符 [27,50]。

!它可能对PK-FK连接的查询有效，但对于事实表中包含FK-FK连接的复杂查询可能无效

内连接实际上就是利用 where 子句对两张(多表)表形成的笛卡尔积进行筛选,我们前面学习的查询都是内连接,也是在开发过程中用的最多的连接查询。

外连接，如果是全外连接，左*右含有的行

数据库视图：

视图是一种虚拟的表（逻辑表），具有和物理表相同的功能。
可以对视图进行增，改，查，操作，
试图通常是有一个表或者多个表的行或列的子集。
对视图的修改不影响基本表。
它使得我们获取数据更容易，相比多表查询

视图是一个虚拟表，其查询的数据来自于视图定义时的 as select xx 查询语句。视图的列来自于一个表或多个表，所以视图不可以和表名重名。
数据多用作查询，一般不会通过视图去修改数据。

!因为存在以下两个问题：许多key比较 以及大量的内存使用量。

首先，探测关系中每个元组的连接键值需要与哈希表中的所有重复键值相匹配。可能会有很多比赛到期 对于FK-FK连接操作，这可以根据连接键值的重复程度成比例地大大降低查询性能。

n元连接操作和二元连接操作相比，可以减少中间结果数量，大多数情况下更有效，

多路连接处理(归并？）已用于分布式查询处理[2,13,49]和图形模式查询处理[31,44]，但几乎没有在内存中的OLAP系统中使用 ，因为在内存内的处理环境中，哈希连接通常优于归并排序连接，并且不同于OLAY图形模式查询，OLAY查询是ad-hoc(点对点)和acyclic(无环)；

!我们提出了一种方法，可以生成n元连接的查询，而不是传统的二元操作，

生成一个具有n-ary连接运算符(称为n-ary连接树)的查询计划是很简单的，相比较二元 搜索空间变得更大，

我们提出了所使用的成本模型和一种查询优化方法 t允许查询规划方法

!实际应用环境很少 出现简单的二元连接,而更多的是复杂的多元连接(multi-mays join)

n 元连接可以以多种方式分解成 n−1 个二 元连接，每二元连接又可以采用多种算法,因此存在大量执行计划。

!算法代价以 I/O 为主,CPU 因等待 I/O 而空闲,因此,优化连接 性能最有效的方法是减少 I/O 操作

等值连接与自然连接是应用最广泛的连接操作,自然连接与等值连接无本质区别,可以通过修改属性名把 等值连接操作转化为自然连接操作,所以研究自然连接具有普遍意义.本节以自然连接(ڇ(为例,设 R 和 S 是两个 数据集,attr(⋅)表示数据集的属性集

与等值连接的区别

\1. 等值连接中不要求属性值完全相同，而自然连接要求两个关系中进行比较的必须是相同的属性组（属性名可以不同），即要求必须有相同的值域。

\2. 等值连接不将重复属性去掉，而自然连接去掉重复属性，也可以说，自然连接是去掉重复列的等值连接（如图所示）

!由于连接运算结果是确定的,因此无论采用何种顺序执行多元连接,结果集大小是一致的.因此,我们需找 到这些执行计划中 I/O 代价最小的作为最优执行计划.

较直接的算法为逐一计算每个执行计划的 I/O 代价,搜索 I/O 代价最小的执行计划

首先,对于任意一个执行计划,需要逐一计算 SiڇSj 的结果集大小Φij 和 6 种算法的 I/O代价,选取 I/O 代价最小的算法作为 SiڇSj 的执行算法.那么对于一个 n 元连接的执行计划选择,至少要计算

次连接代价。并在这么多代价里面搜索最小代价。

只有在与传统的二进制左深连接树相比有益时才生成n-ary连接树

保证 多作业的并行性同时会降低每个作业的并行性,多作业并行并没有带来额外的性能提升

若 I/O 密集型和 CPU 密集型作业并行执行,则有助于提高资源利用率,提高性能

若多个 I/O 密集型作业并行执行,每个作业需要 的资源不能互补,而且会争抢 I/O 资源

FK总是和PK相连接
当两个表中间有了PK-FK连接，那么这两个表就有了关系

单向连接啥基于最坏情况最优连接算法， the worst case optimal join algorithm，

we have demonstrated that SPRINTER significantly outperforms the state-of-the-art OLAP query processing systems in terms of both processing speed and data size that can be processed without our of memory.

我们已经证明了SPRINTER在处理速度和数据方面都显著优于最先进的OLAP查询处理系统 可以在内存不溢出的情况下处理

本文贡献如下：

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

2.2 sprinter 中使用最坏情况下最优连接算法

当n-ary连接操作符的输入大小非常大时，使用GPU进行排序可以进一步提高查询性能。因此，SPRINTER使用不同的排序算法和技术取决于要排序的表的基数，排序列的数量，和GPU内存的容量，在GPU排序。

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

在那个case，SPRINTER使用异构排序[15]，有效地利用CPU和GPU。

we assume that X is too large to fit in GPU memory, and so, we need to split it into six subar rays {X1, · · · ,X6}.

虽然异构排序在CPU上可以在CPU和GPU上使用不同的算法，但我们在GPU上使用radix排序 和在CPU上的合并排序，因为该组合通常显示出最好的性能。

异构排序使用多个GPU流，以隐藏主存和GPU模因之间的数据拷贝成本。 y尽可能通过重叠三种低级GPU操作，H2D拷贝、radix排序和D2H拷贝。

两两合并成一个新的这下一个x2 在x1排序的时候对x2进行排序

最坏情况最优连接算法

通过避免生成中间结果，用以有效地处理图形模式查询（例如，三角形查询），一些算法[1,31,44]需要对输入关系和存储进行预处理，预处理作为数据结构的结果，如B+-tree，


当在数组或子数组中寻找一个特定的值时(例如，在S中寻找y=3)时，TJ使用二分查找，因此，单个搜索的成本是O(logN),如果一个查询有L个连接变量，则可能的全局变量顺序的数量为L！，排列组合。 虽然TJ在任何变量排序下是最坏情况最优的，但这种“最坏情况”p 实际上，由于每个变量顺序的搜索成本不同IO成本，可能远非最优。因此，TJ估计每个可能顺序的连接处理成本（这就是TJ），并选择最好的顺序。

3 一个激励例子

在本节中，我们将介绍一个激励性的查询，它显示了现有的OLAP查询处理系统的缺点。该查询是TPC-DS(?)基准数据库[30]上的一个查询，广泛用于t 测试OLAP系统[18]的查询性能。虽然该查询包含包括聚合在内的各种操作，但我们将在本节中重点关注连接操作。图3显示了的连接图 该查询包含蓝色矩形的三个事实表{SS、SR、CS} （事实表，记录具体事件，如用户交易流水表）和绿色矩形的三维表{D、I、C}。（每个维度可能包含多个属性 比如时间维度看有插入时间 更新时间）为了简单起见，我们只使用关系名称的缩写 在本文中。在图中，我们描述了连接图的每条边上的连接条件。蓝线有2个FK-FK连接操作，绿线有5个PK-FK连接操作。 外键连接越少越好？

图4显示了由Syssem-X、OmniSci[33]和我们的SPRINTER生成的查询计划及其性能。

系统-x是一个功能齐全的最先进的商业化的内存数据库系统,支持索引驱动的查询执行和查询优化技术，如bloom过滤器和自适应连接。

在图4(a)中，它为查询计划生成一个左深连接树相当于从左到右顺序结合，并以操作员一次操作的方式执行该计划。

C1、C2和C3 是相同的关系，即关系C，但在查询处理过程中作为不同的关系来处理，这在OLAP处理系统中很常见。除了系统-x之外，还有许多系统包括 DingMonetDB[9]、CoGaDB[10]、Kinetica[21]和快速步骤[34]生成与图4(a)中几乎相同的查询计划，并以一次操作符的方式执行它。【？】

2.23B就是22.3亿

图4(a)中的计划在最后一个连接之前生成22.3亿(B)中间元组作为左操作数，并以CS的1.44亿(M)元组作为右操作数

因为连接操作是FK-FK连接，并且在哈希表中有许多重复的键值，所以num 在探测连接过程中，哈希表中的key值被访问，我们称之为探测成本，这是探测成本，特别是160.9B倍。

OmniSci[33]是一个开源的协同处理数据库系统，其中协同处理意味着同时利用cpu和gpu进行查询处理。

如图b,它生成了一个左深连接的查询计划和a一样。

但是是以非阻塞和流水线的方式执行计划，它不会生成和存储要连接的中间结果。

详细地说，它评估一系列所有连接操作 通过对关系SS的SR、CS、I、D、D、C1、C2、C3}顺序构建的7个散列表，依次探测连接树中的错误。

图b中SS和SR的第一个连接 ，对SS的每一个元祖依次探测SR的29M元祖，即暴力遍历、，哪个探测成本变成了4.1亿美元。

然后，第二个连接探测每个元组通过了针对散列的第一个连接 1.44M元组的CS表，探针成本为20.7 B.

我们可以类似地计算每个连接的探针成本，总探针成本为25.8 B.

SPRINTER是系统原型，即我们提出的一种集成了跨所有相关层和模块无缝集成到OmniSci中的方法。

我们选择OmniSci作为SPRINTER的基础系统，因为它是最先进的开源现代数据库系统

虽然我们提出SPRINTER使用OmniSci作为基础系统，但SPRINTER原则上可以使用任何数据库系统作为基础系统。

如图c，SPRINTER生成一个查询计划，由多个白色的二进制连接操作符和一个红色的n-ary连接运算符组成。

它分别执行三个连接子树，

• S1={SS、C1、D， I}
• S2={SR、C2}
• S3={CS、C3}

像OmniSci这样的流水线方式，然后，以一次操作符的方式执行无连接操作符，这将在第5节中描述。

当我们计算时 S1、S2、S3的探针总成本仅为758M

此外，当我们计算在三个连接子树的结果中处理n-ary连接的总成本时，它变为312M.

总之，SPRINTER的总处理成本约为1.07B，比其他两个系统的总处理成本要小得多。

图4(d)显示了上述三个系统对TPC-DSSF=100数据库的查询性能。

性能结果表明，OmniSci通过流水线方式消除了单个大块的连接，

SPRINTER通过将单个大连接树分割成多个较小的连接子树并执行n个连接来提高OmniSci的性能 通过将单个大的连接树分割成多个较小的连接子树，并对连接子树的结果执行n个连接。

4 n个连接树的查询规划方法

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

我们考虑一个来自给定查询Q的连接图

查询Q的连接图G=(V、E、f(v∈V)、g(e∈E)、h(e∈E))是一个无向多重图。

顶点v∈V表示Q中连接的关系，

边=(X，Y) ∈E是两个端表X和Y之间的连接操作，特别是X[i]和Y[j]之间的连接操作，其中i∈X和j∈Y。

有三个标记功能f(v)、g(e)和h(e)。

函数f(v)返回 关系v的类型，即事实或维数，

函数g(e）连接操作的类型，即PK-FK或FK-FK，

以及函数h(e)等连接谓词e，即h(e)=(X[i]、Y[j] ).

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

连接图G的核心子图，即核心=(Vc，Ec)⊆G，s.t.是subject to 的缩写，表示约束条件。在。。。的情况下。

其中任何两个顶点X和Y在X∈Vc和Y∈Vc的情况下，通过as连接 E**X,Y ⊆ EcE**c s.t. g(e ∈ E**X,Y )

= FK-FK, f (X) = f act and f (Y) = f act.

在图3中，一个子图{SS，SR，CS}是一个核心子图，因为所有的顶点都是事实表，

事实数据表是包含描述业务内特定事件的数据。是发生在现实世界中的操作型事件所产生的可度量数据，通常包含大量的行。日常查询请求的主要目标就是基于事实表展开计算和聚合操作。
从最低粒度级别来看，事实表行对应一个度量事件，也可以说，一个度量事件必然对应一个最低粒度的事实行为。

我们认为的一行数据是什么样的，粒度。

事实数据表不应该包含描述性的信息，也不应该包含除数字度量字段及使事实与维度表中对应项的相关索引字段除外的任何数据。

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

如果一个连接图G只有一个核心子图核心，那么我们可以将G分解为核心子图核心和一组彼此在边不相交的非核心子图。

我们就可以使用r 将上述两种分解方法分别表示为D1={core、G1、G2、G3}和D2={core、G1}。

算法1提供了仅包含单个核心子图的查询的基本查询规划方法。

<<<<<<< HEAD
这种方法背后的直觉是使一个核心子图成为一个查询计划和mak的根节点 用非核心子图表示查询计划中的根节点的子节点。我们将将核心子图Ci作为根节点时的分解数表示为Ndcmp(Ci)。

4.3 搜索空间

分解的数量取决于选择哪个核心子图作为根节点，我们可以用我们的方法计算一个查询的可能查询计划的数量。一般来说，在连接图G中有Ncore(G)核心子图。

计算具有由一个朴素m生成的单个n-ary连接运算符（作为一个根节点）的可能计划的数量

如果算法1中的第6行使用算法2，则每个分解都可以生成多个查询计划

对于一个特定的分解Dj(1≤j≤Ndcmp(Ci))，我们假设存在Nsubg(Dj)非核心子图 hs

对于每个子图Gk，都存在Nrecur(Gk)查询计划。因此，我们可以计算出该基因产生的可能计划的数量 已排序方法，最多可以有Ncore(G)n-ary连接运算符，

在图6(a)中，可以生成3！=6查询计划取决于连接子树的顺序。在式式中。2，我们不考虑连接子树之间的顺序，因为总处理时间 连接子树是相同的

=======
这种方法背后的直觉是使一个核心子图成为一个查询计划和mak的root根节点 用非核心子图表示查询计划中的根节点的子节点。用非核心子图表示查询计划中的根节点的子节点。

**从每个分解Di中生成一个查询计划Pi 3-9)**从每个分解Di中生成一个查询计划Pi 3-9)从每个分解Di中生成一个查询计划Pi 3-9)

当从非核心子图制作连接子树Sj时 ，通常有很多可能的连接子树。

！！我们只考虑为一个非核心子图生成一个左深二进制连接子树，这可以显著减少 查询计划的搜索空间。前面有证明，至于为什么 需要搞一搞

图b为左深二元连接树

将核心子图作为查询计划的根也是减少查询计划搜索空间的启发式方法。

背后的直觉是 通过在查询计划的最后一步处理事实表上的FK-FK连接，从而减少从非核心子图中的连接操作生成的中间结果量。

代码5-7对于每一个分解方法Di计算代价，第九行做排序

第11行选择最好的方案，

背后的直觉是 通过在查询计划的最后一步处理事实表上的FK-FK连接，从而减少从非核心子图中的连接操作生成的中间结果量。

图6显示了由上述两个分解的D1={core、G1、G2、G3}和D2={core、G1}生成的两个可能的查询计划树。

图6中的每个二进制连接运算符都对应于一条绿色的边

相比之下，图6中的每个根n-连接运算符对应于图5中的一组蓝色边{e4，e5}。

For example, C appears three times in Figure 6(a) since it is shared among three subgraphs {G1,G2,G3}三种颜色 in Figure 5.

When comparing two query plans in Figure 6, we can say the plan P1 就是D1 usually has a lower cost than the plan P2 since P1 scans a dimension table C two more times, whereas P2 scans two fact tables SR and CS one more time.

4.2 针对激励性查询的查询计划

我们将解释当一个查询中有多个核心子图时的查询规划方法。我们将核心子图的数量表示为Ncore。这种查询的一种朴素的查询规划方法是将连接图中的特定的核心视为连接图中的唯一的核心，并将第4.1节中解释的方法应用于连接图。

一种更好的规划方法是推广方法 将算法1递归地应用于所有非核心子图。

我们只需要进行修改算法1中的第6行。

Ndcmp 是以ci为子图核心时，分解数，Ncore个核心子图，

如果算法1中的第6行使用算法2，则每个分解都可以生成多个查询计划。

对于一个特定的分解Dj(1≤j≤Ndcmp(Ci))，Nsubg(Dj)非核心子图，

in Figure 6,

*Nsubg(D1) = 3, and *Nsubg(D2) = 1.

对于每个子图Gk，都存在Nrecur(Gk)查询计划。

因此，我们可以计算出该基因产生的可能计划的数量 已排序方法，最多可以有Ncore(G)n-ary连接运算符，如Eq.2

在图6(a)中，可以生成3！=6查询计划取决于连接子树的顺序。

我们不考虑连接子树之间的顺序，因为总处理时间 连接子树是相同的，不管顺序如何。

5 n-ARY JOIN处理方法

在本节中，我们将介绍SPRINTER的n连接处理方法。

我们将执行一种处理具有一组子连接子树的n个连接运算符的朴素方法

请执行以下六个步骤。

• 步骤1：逐个评估{S1、·、·、Sn}。Si为连接子树
• 步骤2：计算{S1、·、··、Sn}结果的必要统计数据。
• 步骤3：估计连接变量的每个全局顺序的成本。
• 步骤4：选择最佳的全局变量顺序。
• 步骤5：按全局顺序对{S1、·、·、Sn}的结果进行排序。
• 第6步：在n个已排序的关系上合并连接。

对于一个n-ary连接操作符，子节点的可能顺序数变为n！

在原则上。我们假设n个连接运算符的子级从左到右计算。

对于朴素方法，无论处理子节点的顺序如何，处理n-ary连接运算符的时间都变得相同

图7(a)显示了一个用于评估三个连接子树的示例时间线.

我们将将Si计算为Teval(Si)的经过时间，以及对其结果进行排序的经过时间表示为Tsort(Si)。

图7(a)显示了一个用于评估三个连接子的示例时间线

我们将将Si计算为Teval(Si)的经过时间，以及对其结果进行排序的经过时间表示为Tsort(Si)。

我们假设Teval(Si)=Tsort(Si)(1≤i≤3) 为了简单起见，Teval(Si)<Teval(Sj)(i<j)。经过时间按ij递增

步骤2-4在图7(a)中的时间t1时完成，它确定了连接列之间的一定全局应用TJ算法的顺序。

步骤5根据全局顺序对每个结果进行排序，

步骤6在时间t2时使用第2节2.2中所述的TJ(Tributary Join)算法完成。

我们可以知道，在图中，总经过的时间不会改变 即使Ure7(a)，即使{S1、S2、S3}的评估顺序发生了改变，或者即使是Teval(Si)>TSort(Si)或Teval(Si)<Tsort(Si)。

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

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

  c050ef667e21f7ae5e2e8f8620a157be214c5b23

5 自动连接处理方法和优化方法，提供查询性能

在本节中，我们将介绍SPRINTER的n连接处理方法。

我们将执行一种处理具有一组子连接子树的n个连接运算符的朴素方法 g请执行以下六个步骤。

• 步骤1：逐个评估{S1、·、·、Sn}。 Si为连接子树
• 步骤2：计算{S1、·、··、Sn}结果的必要统计数据。
• 步骤3：估计连接变量的每个全局顺序的成本。
• 步骤4：选择最佳的全局变量顺序。
• 步骤5：按全局顺序对{S1、·、·、Sn}的结果进行排序。
• 第6步：在n个已排序的关系上合并连接。

对于一个n-ary连接操作符，子节点的可能顺序数变为n！

对于n 在朴素方法中，无论处理子节点的顺序如何，处理n-ary连接运算符的所用时间都变得相同。

步骤6在时间t2时使用第2节2.2中所述的TJ算法完成。

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

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

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

图7(b)显示了修改后的方法的时间线。

步骤1-2中，它首先确定全局变量的顺序，而不计算{S1、···、Sn}的结果的统计数据 t1)。因为先计算 ，就达不到评估和排序的重叠效果

在步骤3中，它重叠了使用CPU评估Si，并使用GPU(i，j)对Sj的结果进行排序。

在t中 他的方法是，无论{S1、S2、S3}的处理顺序如何，图7(b)中的总经过的时间仍然没有改变（箭头的总长度没有改变）

我们可以进一步减少如图7(b)所示的总运行时间。SPRINTER可以利用流水线技术来评估每个子连接子树，因为它的基础系统，即OmniSci，是一个 基于流水线技术。

由于SPRINTER可以同时使用CPU和GPU，并且同时使用流水线技术，在评估si的时候，排序sj，我们假设s1,s2,s3分别为gpu一次可处理数据大小的1倍，2倍，3倍。

图中红色虚线表示主机（即主存）到设备（即GPU内存）的拷贝，记为H2D 复制。

确定全局顺序

一般来说，在合理短的时间内精确计算每个全局连接变量顺序的成本是一个非常具有挑战性的问题。

本文还提出了一种启发式算法来确定一个相当好的全局算法 对于OLAP查询的可变顺序快速，我们将在未来的工作中进一步改进。

给定一个核心子图，它找到所有的连接变量，并为每个连接变量准备三个变量的组合<w,|Ew|,Cw>

w是一个连接变量，Ew是w的连接条件数，Cw是w连接的约束的数量，Cw是关系中有w的数量，

图8显示了TPC-DSQ17的一个核心子图，它有三个连接变量，项目、cust和票据。

对于项目，|Estem|=2，和Citem=||CS||+||SR||+||SS||。

然后，该算法按(|Ew|，Cw)的降序对三联体列表进行排序。

则其中一个可以在全局变量顺序中排在另一个之前。 例如，item ≺ cust ≺ ticket 和cust ≺ item ≺ ticket 都是允许的。

则其中一个可以在全局变量顺序中排在另一个之前。 例如，item ≺ cust ≺ ticket 和cust ≺ item ≺ ticket 都是允许的。

直观地，算法选择具有更多连接条件和可能有更多元组作为更高优先级处理的连接变量，以减少对排序关系进行二分搜索的总量。

5.2 排序策略

三个因素：GPU的可用性，待排序的数据量的大小，数据字段的量，

如果GPU不可用，则sprinter使用cpu非比较排序number of sorting columns is only one，

其次，如果要排序的数据可以适应GPU内存，SPRINTER使用一个非比较或基于比较的GPU排序算法，具体取决于排序列的数量。

第三，如果要排序的数据不能适合GPU内存，我们需要仔细选择

一个排序算法 GPU排序缺乏良好实现的问题

GPU[7]的一个基于比较的算法的实现速度仅比CPU[37]的实现算法略快。

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

用GPU排序，再用cpu合并比很多情况下都要慢。因此我们直接用cpu比较排序。

If a relation has only a single sorting column,we just use heterogeneous sorting in Section 2.1 since there is a very fast implementation of a non-comparison based algorithm for GPU, and the cost of merging subarrays is not so large.

合并加入排序 排序啥？

item、cust和ticket表示为i、c和 t

如果4放在最后面，是不是代价就会少很多？

进行查询优化的成本模型

我们认为查询计划 P old 由 M-1 个二元连接运算符组成

使用n-ary连接运算符的查询处理可能并不总是比仅使用二进制连接运算符的传统查询处理方法获得更好的性能。因此，我们使SPRINTER成为一名将军 e只有在成本模型有利时才包含n个连接算符的查询计划。

因此，我们建立了成本模型成本(PNew)和成本(P old)，以确定成本(Pnew)<成本(Pold)。

我们将在查询处理过程中访问的元组（或散希表中的元素）的数量作为成本的度量。

Cost model of the base system

We consider that a query plan P**old consists of M M 1 binary join operators for M relations.

我们考虑PK-FK连接或FK-FK连接的每个二进制连接运算符都使用主内存哈希连接算法进行计算，该算法不仅在OmniSci[33]（GPU）排序中很常见，而且在其他内存查询中也很常见 处理系统

我们假设查询处理探测最左关系的每个元组，

EQ3显示了Pold的成本函数，其中构建(Fi)是构建哈希表的成本函数，EQ4

探测(F1)探测元组的成本函数 F1 EQ5

我们可以假设F1的每个元组都与F2的哈希表中的dup2元素进行比较，而不管哈希表的类型如何（例如，开放寻址、单独的链接）。

谓词：属于函数的一种，但其返回值是真值(true/false/unknown)

SPRINTER的成本模型

一般来说，查询计划Pnew由M个关系的n-ary和二进制连接运算符组成。

我们假设Pnew中至少有一个n个连接运算符，否则不需要生成Pnew。

Eq.7表示n-ary连接处理的成本，其中包括n个连接子树结果的排序成本和使用TJ算法的连接成本。

如果w1≺w2≺···≺wL被确定为n个连接操作器O的全局变量顺序，Eq。8显示了合并n个排序关系{Sˆi|1≤i≤n}的TJ算法的成本。

7 介绍了实验评价的结果

SPRINTER与现有的OLAP查询处理系统所经过的复杂OLAP查询时间i进行比较,in the TPC-DS benchmark

。详细地，我们通过实证验证了选择第5节中描述的排序算法的策略，

在第6节中提出的成本模型，以及排序算法的性能。

实验设置

查询和数据集：在 TPC-DS 基准测试中，共有 26 个 TPC-DS 查询至少有一个 FK-FK 连接 [30]

环境：我们在一台机器上进行所有实验，配备了两台英特尔Xeonen10核cpu，

512GB主存和一个11GB的NVIDIAGTX1080TiGPU。 操作系统OS7.5

系统比较：与sprinter系统相比，OLAP系统分为两种类型：基于cpu的系统(如Syssem-x)和协同处理系统(如OmniSci)。每个系统都被设置为尽可能多地同时使用主存和GPU设备内存（仅用于共同处理系统）

对于基于cpu的系统，System-Y是最先进的商业化的OLAP数据库系统之一，支持索引驱动的查询执行和查询优化技术，如bloomf 过滤器的散列连接和基于成本的查询规划器，

这类似于System-X。但是，它生成了一个二进制（更加平衡的树，区别于作深树）的查询计划，这是与System-x的主要区别之一。

此外，Sys tem-Y以流水线的方式处理查询计划，并支持查询执行的协变性。我们使用最新版本的系统x和系统y进行实验。

using only CPU as SPRINTER(C) and the one of SPRINTER

using both CPU and GPU as SPRINTER(G).

我们表示 SPRINTER 的版本仅使用 CPU 作为 SPRINTER(C) 和 SPRINTER 之一使用 CPU 和 GPU 作为 SPRINTER(G)。

此外，sprinter(C)和sprinter(G)的大多数查询的性能都优于所有系统，这是由于它们不同的查询计划和不同的连接处理

对于Q64，SPRINTER(G)与Syssem-Y、System-X、MonetDB和Actia相比，提高了性能 n向量分别为6.6、7.4、20.1和5.1倍

SPRINTER(C)和SPRINTER(G)之间的性能差距并不大，因为数据大小相对较小(SF=100)。

We note that the current SPRINTER does not use advanced query optimization techniques that System-X and System-Y use, since its base system, OmniSci, does not support them yet. Thus, the performance of SPRINTER can be further improved by applying the optimization techniques to OmniSci or SPRINTER.

对所有测试的查询进行比较。与基于cpu的系统相比，现有的协同处理系统在处理时有更多的故障，通常性能更差。

这是因为协同处理系统通常不使用先进的查询优化技术，而且还不够成熟，无法利用GPU来有效地处理复杂的查询。

然而，图11中的TPC-DS查询通常具有较低的fi值（即，接近于0），因此，Sissem-X配备了支持索引驱动的查询执行和查询优化技术 执行OmniSci。 fi是什么

对于OmniSci，即使在使用主内存执行查询时，如果查询变得更加复杂，它也往往会错误地估计所需的内存量， 因此，左较深的连接树变得越来越深。因此，OmniSci往往由于错误内存分配的m.E.或FK-FK连接的大量探测成本而失败。

相比之下，SPRINTER虽然是基于OmniSci的，但没有失败，查询性能显着提升。 SPRINTER生成的查询计划中的左深连接子树比OmniSci的连接树小很多，同时， 几乎没有用于构建哈希表的事实表
EXPERIMENTAL EVALUATION

相关工作

总结全文

<<<<<<< HEAD
本文提出了一种针对具有FK-FK连接的复杂OLAP查询的快速n-ary连接查询处理方法。

它会生成一个包含n-ary连接运算符的查询计划，如果它优于 基于我们的成本模型的传统的左深二进制连接树

该计划可以通过将事实表格上的FK-FK连接放入一个n-ary连接操作符中，从而显著降低探测成本。

We also have proposed an efficient n-ary join processing method which is based on the TJ algorithm and heuristic algorithm selecting a good global variable order.

我们提出的sprinter已经可以集成到开源的内存OLAP系统，OmniSci，跨所有相关的层和模块。

通过使用TPC-DS基准测试的实验，我们已经证明了 即使没有使用GPU排序，SPRINTER的性能也优于最先进的OLAP系统，尽管它的基础系统OmniSci达到了它们中第二差的性能。

算法执行过程：

算法1，确定了一个核心子图，然后对它的非核心子图一般是维表进行遍历，最后计算事实表的计算，尽量减少中间连接操作形成的结果量

算法2就是算法1的推广，有多个核心子图，对它进行遍历

=======

659ab8ab41e0f048755673e552dec5884206a142
c050ef667e21f7ae5e2e8f8620a157be214c5b23