今天会介绍一篇比较不错的针对数据库查询优化的一个方向的论文。
论文地址：HorseIR：融合数组编程和数据库查询处理
每个人都有不同的品味，我也不例外。
我个人虽然也读很多论文-但大多数都是功利性的，也就是这些论文的内容具有以下普遍特质：
- 着眼未来，但作用于当下-也就是不是太实验性质，无法落地。当然我也不排斥理论计算机论文文章-大部分没有可落地性质的验证，更多的是数学公式和形式化证明（我也写了很久LISP方面的东西-大多数都是Haskell,scheme等，也不怕看这些理论公式推导）。但每个人倾向性不同，我首先是工程师而不是计算机科学家。如果用电视剧“生活大爆炸”中的角色来代表喜好的话。我个人更喜欢霍华德和莱纳德多于谢尔顿。因为前者创造出很多有意思的东西而不是所有东西都停留在理论研究阶段（其中还有很大的不可证伪性）。
- 优秀的延续性：一阶段做了什么（给予读者可验证的部分实验原型），二阶段可能要做什么（带来灵感）
- 最好有大的公司参与做一定的产品化的验证
针对数据的查询优化是一个永恒的话题. 无论在DAL层面优化还是所谓的CACHE-DB架构，DDD设计模式（DO,PO,聚合根）都想达到一个目的：随着业务变得复杂和数据的爆炸增长不会带来数据访问速率的降低。今天这篇论文不但带来一个很好的思路而且有具体的实验性验证：HorsePower
项目架构图
传统的关系数据库管理系统（RDBMS）似乎是数据科学领域数据存储和分析的自然选择，但现有的系统在两个方面还存在不足。首先，随着主存越来越便宜，许多工作负载现在可以装入主存，而RDBMS已经针对I/O进行了优化；其次，当前的系统支持除了通过用proce-dural语言编写的用户定义函数（UDF）进行SQL查询之外，高级分析与SQL引擎的集成大多遵循黑盒方法，限制了整体优化的机会。在本文中，我们提出了一种基于Array的中间表示，允许统一表示使用传统RDBMS优化技术优化的udf和SQL执行计划。HorseIR具有高层次的设计，支持丰富的类型和数据结构，包括齐次向量和异构列表。我们确定了从HorseIR生成有效代码的适当优化，同时考虑了内存和CPU方面。通过测试标准SQL查询和udf查询，我们将HorseIR与MonetDB RDBMS进行了比较，并展示了我们的整体方法
编译器优化有利于复杂查询的运行时。
几十年来，关系数据库管理系统（RDBMS）一直是组织首选的主要数据管理软件，SQL是事实上的标准查询语言[27]。作为一种基于关系代数的声明语言[17]，SQL给出了RDBMS
实现者优化查询执行计划的机会[13]。然而，这些优化工作的主要目标是减少磁盘访问，因为I/O在大部分RDBMS历史中一直是主要的资源瓶颈[28]。研究表明主内存大小的增加导致许多RDBMS工作负载随着磁盘块被缓存在内存中而变得计算和内存受限[7，11]，因此需要更复杂的优化策略。
此外，随着数据科学和机器学习等领域的日益普及，采用统计和学习算法的高级分析应用也随之增多。
SQL的结构限制使得它很难支持这些应用程序所需的许多复杂的线性代数和过程逻辑。因此，RDBMS供应商正转向更传统的过程语言，通过提供一种用户定义函数（UDF），可以用传统的过程语言编写，并作为常规SQL查询的一部分调用[33]。然而，在大多数情况下，这种集成遵循黑盒方法，SQL优化器无法洞察UDF的逻辑，反之亦然，
因此丧失了进行整体优化的任何机会。只有最近的努力[19，18]试图解决这个性能问题，例如让UDF分析器收集统计信息在编译的udf中。
从编程语言（PL）的角度来看，许多重要的数据分析和机器学习算法目前都是用基于数组的编程语言实现的，例如
如Python（NumPy）[8]、R[40]和MATLAB[2]。历史上，许多数据分析方法，包括许多财务计算，都是用APL完成的。
我们的方法，也是本文的主要目的，是通过提供一个通用的、基于阵列的中介表示（IR），即我们称之为HorseIR的两个主要功能，将现代数据库技术和基于阵列的PLs的优势结合起来。
- （i） 通过翻译SQL执行计划到HorseIR，许多标准的编译器优化和并行化可以应用到HorseIR，从而提高了CPU限制和内存密集型数据库查询的性能。
- （ii）通用的基于数组的IR有助于在基于PL和SQL的边界上进行优化，当RDBMS和PL作为单独的实体开发时，实现性能改进是不可能的。我们的总体方法如图1所示，图1展示了UDF和SQL查询都被转换为HorseIR，然后一起优化，以提供高效的目标代码。
研究表明，为大规模数据处理而优化的RDBMS实现往往受益于列存储体系结构，这种结构是每一列单独连续存储的方法[4，5]。这里是列的逻辑数据结构类似于编程语言数组的逻辑数据结构。因此，选择基于阵列的红外是非常重要的。列存储的工作数据集1非常适合应用数组程序优化，因为列本质上包含同构数据，这些数据很好地映射到基于数组/基于向量的基元。然而，尽管数据库（DB）表中的每一列都包含同构数据，但不同的列可能包含不同的基类型。因此，我们使用了一些来自数组语言（如ELI[14]、Q[1]和Q’Nial[29]）的见解，包括字典和表的一些特定高级类型，这些类型提供了表示DB表的清晰机制，同时仍然可以进行优化。
由于HorseIR的核心数据结构是vector（对应于DB表中的列），我们为HorseIR提供了一组丰富的定义良好的内置函数。它们具有明确定义的语义，易于优化，并且在元素级内置函数的情况下，易于并行化。我们还仔细考虑了HorseIR的类型系统，允许声明具有显式类型以及提供通配符类型和类型推断规则的变量。
为了证明我们方法的可行性，我们将流行的开源列存储RDBMS的标准版本MonetDB[25]与标准TPC-H SQL基准集[45]中10个查询的优化HorseIR代码进行了比较。做这个比较的一个重要见解 在执行HorseIR的生成和优化之前，利用SQL优化是很重要的。因此，我们根据MonetDB计算的优化执行计划生成HorseIR。这些执行计划由SQL查询生成，并基于查询中的运算符，以及输入数据集的大小和结构。这种方法允许我们受益于所有特定于数据库的优化，以及基于编译器的优化，因此，可以利用多年来在数据库和编译器社区中进行的优化开发。事实上，我们的性能结果表明，HorseIR方法的性能比标准MonetDB方法高出101%。
我们还演示了通过使用Black Scholes benchmark[9]作为UDF并查看调用UDF的SQL查询的10种变体来优化UDF/SQL的好处。由于HorseIR优化器可以优化过程间，因此可以使用SQL查询的上下文来执行优化，如果对UDF和SQL查询进行了优化，则无法分别独立的执行优化。
本文的主要贡献在于：
•确定SQL查询和UDF需要通用的IR；
•设计并实现了一个基于数组的IR，称为HorseIR，用于表示SQL查询和udf；
•演示了如何利用数据库社区开发的许多优化，根据数据集为声明性查询生成高效的执行树；
•确定了从SQL查询计划生成高效HorseIR代码的重要编译器优化；
•确定了SQL查询和UDF之间的重要跨边界优化；以及
•与基于popularcolumn store的RDBMS MonetDB相比，展示了该方法的性能优势。
论文的其余部分安排如下。我们首先在Sec中提供了RDBMS和数组编程的相关背景知识。2。然后，我们将详细介绍HorseIR的设计和实现。3、 从SQL和源语言到HorseIR的转换。四；
以及一组编译器优化。最后，在第六章中给出了我们的实验评价，在第二章中做了相关的工作。第7节和结论。
2背景
2.1传统数据库优化
SQL的理论基础是基于关系代数的。RDBMS通常将SQL查询解析为关系代数表示[12]，因为后者更易于优化[43]。关系代数运算符是一元或二元的，因为它们接受一个或 两个表2作为输入。它们的输出总是一个表。因此，很容易将这些运算符链接到运算符树中，其中一个关系运算符的输出用作另一个运算符的输入，以解决复杂的SQL查询。每个运算符都可以实现以各种方式。哪个效率最高取决于树中的位置和输入数据。因此，现代RDBMS优化器有一个查询重写子系统，该子系统生成语义等价的关系代数运算符树[26，28]。然后为每个其中，它们为树中的单个运算符选择的实现不同。然后选择总体上最便宜的执行，因此成本模型传统上关注I/O成本，因为执行被假定为I/O绑定[28]。
一个关键的优化策略是尽量减少作为查询执行计划的一部分从一个操作符“流”到另一个操作符的记录数，因为这意味着整体I/O减少。
因此，可能首先执行高选择性的运算符，即输出的记录数与接收的输入记录数相比较少的运算符。
然而，随着主存变得越来越便宜，RDBMS现在经常有这么多的主存可用，以至于查询的工作数据集可以完全装入主存。
这样一来，RDBMS工作负载就开始变得受计算限制，常常不能有效地利用底层处理器/内存体系结构[7，11]。这导致了对“块优化”技术的探索[38，47]以利用CPU性能，[10]通过计算CPU缓存利用率在其方法上更加复杂。
2.2 RDBMS中的UDF和嵌入式解释器
UDF的概念最早是在[33]中提出的。其基本思想是为用户提供一种利用传统过程语言编写无法通过SQL表达的计算代码片段的方法。新一代口译语言的日益流行Python和R[20]，特别是在数据科学家3中，鼓励RDBMS供应商将它们嵌入RDBMS软件中[41、36、44、24、35]。但是，udf只能处理已经在主存中的数据，这与SQL查询的执行不同，SQL查询可以从磁盘检索数据 如果它不在主内存中。因此，RDBMS引擎在对数据调用udf之前执行磁盘到主存的数据传输。虽然很方便，但在许多方面，将过程语言集成到RDBMS引擎中的效果并不是最佳的。RDBMS查询引擎只关心根据支持SQL查询的需要优化数据管理操作。它对自定义项的内部工作内部函数。UDF中的任何优化都留给语言解释器处理。尽管数据结构的逻辑方面是相同的，但两个系统之间通常需要物理数据格式转换。因此，这两个系统在
同一个组件和同一个请求的执行部分，将彼此视为黑匣子，从整体上消除优化请求的可能性。
在改善这一差距方面已经做了一些工作，特别是在专栏店。通过选择与解释器的物理结构相匹配的最小预处理，[41,36]试图减少MonetDB中物理数据转换的需要。[24]在SAP HANA[22]上应用了类似的方法，SAP HANA是一种商业RDBMS。
2.3阵列编程概述
数组编程受多种编程语言的支持，如APL、MATLAB和FORTRAN 90。数组编程的主要特点如下。1） 数组对象是主要的数据结构。数组对象能够表示任意维数组。因此，使用数组进行编程时会附带简洁而富有表现力的代码；2）数组编程语言作为内置函数提供丰富的运算符系列。数组编程的有趣的基本思想是对数组的所有项应用一个操作，而无需显式循环。如果一个操作是可映射的，那么代码可以在数组的每个项上并行执行。例如，MATLAB的元素级函数针对隐式数据并行性进行了很好的调整。数组编程的一个特例是矢量化。它可以在低级硬件或高级编程语言中进行。现代硬件在其芯片设计中正积极采用矢量化的概念。例如，“英特尔高级矢量扩展”（Intel Advanced Vector Extensions，AVX）4是为高效矢量运算而设计的指令集。一条指令同时对多个数据项执行一次操作。另一种矢量化是从标量形式到矢量形式的源级转换，以减少显式循环迭代的开销[34，15]。
HorseIR受ELI、Q和APL的影响。它设计有一套特殊的内置功能。除了一般的数组对象外，它还引入了齐次向量作为基本类型。此外，它还提供了一组基于列表的类型（包括表类型），用于处理异构数据。相比在传统的数组编程中，我们的设计简化了语言语义的复杂性，同时保持了处理复杂数据结构的灵活性。
3horse IR的设计与实现
HorseIR的设计动机是需要捕获一个非常干净的基于数组的IR，具有清晰的语义，从而实现优化和自动并行。IR还需要在统一的方式。在这一节中，我们通过给出关键的程序结构、类型、形状和实现细节来简要介绍HorseIR。
在其核心，HorseIR是一个类型化的、3地址的、基于SSA的中间表示，具有：简单的模块系统；静态作用域；按值调用语义；包含通配符类型的丰富基类型集；包含数组、列表、字典、表和键控表的关键复合类型；以及丰富的
一组定义良好的基元数组操作。
3.1程序结构
模块
有效的HorseIR程序由一组模块组成，每个模块定义零个或多个静态字段和零个或多个静态方法。例如，清单1显示了一个示例模块，BigDiscount和两个方法实现。如果模块包含一个名为main的方法，则可以将其用作程序的入口点。在BigDiscount模块中有一个main方法，它从数据库表行项目中读取，加载列l discount，然后调用方法compute discount。 除了程序员定义的模块外，还有一个预定义的默认模块，它收集在模块外部定义的任何字段或方法。此外，模块可以使用import语句从另一个模块导入一个或多个方法。导入的方法可以是使用方法名（不带模块名）调用，除非导入的方法与当前模块之间存在冲突，在这种情况下，必须显式使用模块名调用方法。通过这种简单的模块设计，HorseIR提供了一种模块化复杂软件的机制，并提供了一种灵活的方式来指定可重用的库。
方法
一个方法有零个或多个参数和0个或1个返回值。参数是按值传递的，这简化了程序分析，但也意味着副本消除是一个重要的优化，就像高效执行MATLAB[23]一样。前面有@的方法调用表示用户定义的或库方法调用，而没有@的方法调用是系统调用，如check cast。方法可以重载，但重载方法的类型签名不能允许任何不明确的调用。
静态字段和局部变量
静态字段具有其定义模块的作用域，局部变量具有其封闭方法的作用域。每个静态字段和局部变量都必须具有声明的类型，尽管该类型可能是通配符类型。
3.2IR类型
**在HorseIR的设计中，选型是一个非常重要的决策。第一个关键的决定是HorseIR应该是静态类型的，但是有一个特殊的通配符类型，允许在无法确定静态类型的情况下使用，从而指示必须在哪里进行动态类型检查。静态类型和动态类型之间的这种紧张关系部分是由于许多常见的数组语言都是动态类型的，因此通常不可能从这些语言生成静态类型的HorseIR。另一方面，数据库表已经声明了类型，因此可以从查询中生成静态类型的HorseIR，并且是首选。最后，静态类型和形状可以产生更高效的基于数组的代码，这一点已经得到了充分的证实，因此我们应该尽可能多地使用静态类型[32]。
基类型和同构数组
**第二个关键的决定是支持相当丰富的基类型集，其中包括：（1）您希望在基于数组的语言中找到的所有基类型（boolean、char、short、int、long、float、double和complex）；（2）您希望从SQL数据库中找到的其他基类型（string、month、date、time、datetime、minute和second）；以及（3）一种特殊的类型symbol，它提供了不可变字符串的有效表示，这对于有效的内存中数据库表示非常重要。内置操作已定义
在均匀阵列上。由于每个同构数组都可以存储在一个连续的内存区域中，因此它是一个缓存友好的设计，并且易于为并行性进行分区。因此，我们的声明实际上表示数组，每个数组都有一个显式的基类型和一个隐式的
范围（维度数）和形状（所有维度的大小）。只声明基类型，但有时可以推断范围和/或形状。例如，清单1中的参数declaration discount:f64声明discount是一个具有基的同构数组f64类型。在这种情况下，形状推断将能够根据内置方法列值的输出形状确定它实际上是一个向量。
高级异构数据结构
尽管同构数组在核心科学计算方面非常优秀，但是存储在SQL数据库中的数据不是同构的，而是具有具有不同数据类型的列。因此，HorseIR被定义为关键的异构数据类型，以便以一种 与基于数组的基元交互良好。
列表类型是基本类型，它提供用于保存不同类型的单元格，并且可以嵌套列表。其他高级类型派生自此嵌套列表类型。字典是键和值对的列表；表是字典的特例，它要求每个值都具有相同的值
长度；键控表用作两个普通表的粘合剂；枚举保留一对键和值，其中的值替换为其在键中出现位置的索引。
HorseIR支持许多重要的内置函数来处理这些数据结构，其中四个函数被广泛地应用于Sec描述的代码生成策略中。
函数列表接受任意数量的参数，并返回一个列表，其中每个参数保存在单个单元格中。返回列表的长度是参数的数目。函数raze分解一个输入列表（包括嵌套列表），创建一个包含列表所有叶元素的向量。注意，raze希望所有叶元素都是同一类型的，因为向量是同构的数据结构。此外，HorseIR支持用于从键控表或字典中获取键和值的内置函数keys和values。
对于数组的Elementwise操作与许多基于数组的语言一样，HorseIR支持大量的Elementwise操作
它接受一个（一元）或两个（二进制）参数。elementwise一元操作接受一个参数，并将其操作映射到参数的每个项上。因此，输出的形状与输入的形状相同。elementwise二进制操作有两个参数。如果两个参数的长度都不是一个，它们必须在长度上一致，表示为N。因此，有三种可能：1到N、N到1和N到N。结果总是长度为N，二进制运算以成对方式应用于每个元素（如果一个参数是标量，它实际上是通过复制到长度为N的向量来扩展的。
列表的每个操作
由于HorseIR还包括基于列表的数据结构，因此它提供了各种类似于映射的操作。HorseIR支持一元操作，每个项（f，x）对列表x的所有元素应用一个函数f，以及三个二进制操作，每个操作（f，x，y），每个左操作（f，x，y）和每个右操作（f，x，y）。对于二进制运算，输出的第i个元素分别计算为f（x（i），y（i）），f（x（i），y）和f（x，y（i））。
其他功能
HorseIR还支持助手函数和系统函数。例如，函数len返回一个标量，该标量指示其输入参数的长度，函数load table用于加载将数据库表转换为HorseIR表。
3.3 HorseIR实施
我们为HorseIR实现了三个核心组件：（1）一个HorseIR前端，它解析、执行语义检查并生成AST；（2）一个高效的并行实现库，用于HorseIR丰富的内置组件集，以及一个HorseIR的解释器。
HorseIR前端
HorseIR前端是用ANTLR4[39]构建的，ANTLR4[39]是一个流行的解析器生成器。该工具支持字符串中的Unicode编码，这很有用，因为Unicode编码广泛存在于数据库中。我们为HorseIR定义了一个干净的语法，并开发和实现了一个从ANTLR交付的CST到适合优化和解释的AST的转换。前端还执行类型检查和语义分析，尽可能使用推断类型替换通配符类型。
内置函数库
HorseIR采用一种单功能多实现策略来接受来自数据库系统的各种数据。一个内置函数可能有一个或多个实现
专门化为正确的基类型，或输入数据的大小或形状。
由于elementwise操作没有数据依赖关系，HorseIR库为所有这些操作提供了一个并行版本。此外，HorseIR还支持其他常用操作的并行代码。例如，操作和是通过部分和的聚合来实现的从每个平行线。目前，我们使用OpenMP来实现库中的并行代码，这也方便了从这些定义良好的高级内置函数生成高效的并行代码。HorseIR的设计实现了简单的并行化，并向随后的优化是因为我们支持向量/数组和列表的简单而清晰的组合。
然而，单函数并行化是不够的，因为为每个操作引入的循环屏障是昂贵的。因此，使用循环融合合并两个或多个函数通常是有益的。HorseIR使用一个名为fuse op的函数来公开这种融合，该函数将一个列表作为参数
原始函数和参数列表。此指令对应于后端的专用熔断代码。
HorseIR翻译
HorseIR解释器使用标准的解释器设计，它直接解释输入的HorseIR，调用内置库。在这个上下文中解释（而不是编译）是非常有效的，因为为查询生成的代码非常小，并且代码很好地利用了
高效的内置库功能。将来，我们可能会在解释器中添加一些JIT功能，以便从专门的代码中进一步获益。
4编译成HorseIR
RDBMS优化器能够生成非常高效的执行计划，其中考虑了查询中运算符的类型及其选择性，以及底层表的大小和结构。为了让我们的HorseIR方法利用这些优化，这样的执行
Trees必须被转化为HorseIR。在这一节中，我们首先描述了如何用HorseIR来表示各个关系代数运算符，然后讨论了完整查询执行计划的转换以及它们与过程代码的关系，最后讨论了可能的限制。
4.1关系代数到HorseIR的映射
在本节中，我们将讨论如何将最基本的关系运算符转换为Hor seIR。投影∏a1，…，an（R）以表R的记录为输入，返回相同的记录，但只返回R的列名为a1，…，an的列。在HorseIR中，函数列值加载
给定表名的列。列名形成字符串或符号向量。然后，将返回一个新表和函数表，该函数表同时接受列名和值。设colk=@列值（T，ak），其中k∈[1，n]。因此，我们可以在HorseIR进行如下项目运作。
选择表示为σP（R），其中P是选择谓词的集合，R是表。选择返回属性值满足条件P的R的记录。。。
JOIN
join操作将两个表作为输入，并将满足特定条件的两个表中的记录连接起来。让R1是一个有列的表（cola1，…，colan），R2是另一个有列的表（colb1，…，colbm）。然后，join操作返回一个新表：R1./COND R2，其中（COND☆（cola1=colb1）∧…）。新表包含表R1和R2中的列。如果r1和r2满足条件，则r1中的记录r1和r2中的记录r2将在新表中生成一条记录。在HorseIR中，我们提供了一个原始数据类型枚举，以保持联接后两个表之间的关系。枚举有两个参数K和V。K和V的类型和形状必须相同。然后，枚举记录以K表示的V值第一次出现的索引。另一方面，目标变量存储K，而源变量V可以忽略，因为所有信息都保存在枚举中。内置函数枚举构造枚举。第2节讨论了连接中的优化机会。
Aggregation
聚合函数将值列表作为输入，并返回单个值作为输出，例如sum（值的总和）和count（值的数目）。聚合的形式定义是（G1，G2，…，Gn）AGGR F1（a1），F2（a2），…，Fm（an）（R），其中（i）G1，G2，…，Gn是要分组的列的列表（在表R中）；（ii）a1，a2，…，an是R中列的名称；和（iii）F1，F2，…，Fm是聚合函数。在HorseIR中，函数组聚合可以是向量或列表的值，并返回一个字典，其中键是组中第一个值和一个值的索引由组中相同值的索引组成。（即dict
4.2 SQL执行计划
其思想是采用RDBMS生成的优化执行计划（在我们的例子中是MonetDB）并将其转换为HorseIR。执行计划具有明确定义的运算符顺序。如前一节所示，每个操作符都可以映射到一行或多行HorseIR代码中。我们的代码生成在概念上类似于具有代码模式的编译器后端。因此，将执行计划转换为基本的HorseIR程序相当简单。
然而，仍然有很多机会来优化这一基本方案，因为没有一个“一刀切”的战略。例如，在运行时使用枚举进行联接的计算非常昂贵，特别是当两个表具有相对较大的行数时。在第5节中，我们将确定并探索进一步优化生成的HorseIR代码的机会。
4.3高级别udf到HorseIR的翻译
由于HorseIR是一个高级的IR，所以用作udf源语言的语言也应该是相对高级的，并且支持数组编程，比如MATLAB和Python。在从MATLAB到HorseIR的转换中，如果输入类型信息未知，则可以将其设置为通配符类型，并在随后的类型检查中指定其实际类型。当HorseIR开始 通过嵌入式查询，它能够从数据库系统中收集列的类型信息。通过了解类型信息，HorseIR可以通过在类型推断之后移除类型保护来发出有效的代码。
将MATLAB代码转换为HorseIR的一种可能方法是使用McSAF。McSAF是Sable实验室为MATLAB开发的静态分析框架[21]。在今后的工作中，我们将利用现有的基础设施，把标准的MATLAB程序转换成HorseIR程序
使这个过程自动化。
4.4限制
**编译到HorseIR的好处可能仅限于高级基于数组的语言。即使在支持显式循环的基于数组的语言中（例如，对于MATLAB中的循环），也需要向量化技术来检测可能的源到源转换[15]。这样的自动矢量化
技术通常效率低下，并且受编程风格的影响很大。HorseIR支持使其能够处理循环的分支。但是，它可能成为性能瓶颈。为了获得最佳性能，应该以数组形式编写udf。
5优化Horse-IR
在这一节中，我们将介绍HorseIR程序的优化策略。
5.1程序内优化
**我们首先研究方法中的优化机会。经典的编译器技术，如类型和形状分析以及数据依赖性分析，对于理解程序的行为是必要的。数据库系统的研究人员也意识到了这些技术的重要性 并将其中一些集成到他们的数据库系统中，例如MonetDB中的MAL optimizer这是我们在构建自己的优化器时需要吸取的宝贵经验。我们发现可以在优化HorseIR的上下文中使用以下优化，特别是从SQL查询生成的HorseIR:Constant propagation and folding（CPF）。这是传播和预计算常量值的标准技术，特别是在HorseIR中的日期和时间。公共子表达式消除（CSE）。多余的公共子表达式与公共变量一起重新放置，公共变量仅在任何公共子表达式之前计算一次。 强度降低（SR）。操作被重写为更有效的操作。因为在这种情况下，当一个布尔向量与一个实向量相乘时，作为条件表达式，昂贵的相乘运算可以替换为便宜的三元运算。
环路融合（LF）
由于每个基于数组的内置函数都是单独并行的，所以每个函数都有一个同步屏障来收集所有派生线程的结果。可以融合相邻函数调用，减少同步屏障的数量。我们发现这种环路融合
对于在布尔向量上执行的相邻逻辑操作特别有用。这种模式在从SQL的WHERE子句生成的HorseIR代码中很常见。窥视孔优化（PH）。窥视孔是一种代码模式，编译器可以在代码片段中识别它，然后将其重写为更有效的代码。我们报告几个窥视孔如下：
•Groupby和orderby。groupby是一种聚合操作。它的输入可以采用向量或列表，因为它可以对多个列进行操作。它的实现首先对输入进行排序，然后从邻居处查找相同的项。如果groupby和orderby都在同一列上操作，则应删除orderby中的附加排序。
•内部自连接。当仅聚合操作发生在内部自联接之后时join可以替换为比join便宜的groupby。
连接转换（JT）。此技术旨在减少重建新的连接后过滤器的开销。在RDBMS中，可以使用键和外键预先计算连接。
连接的结果存储在枚举ev中，其中有一对
一。当使用过滤器选择一个键时，其外键在被压缩之前通过索引存储在枚举ev中的索引来获取布尔掩码；
2。使用筛选器选择外键时，其键保持不变。我们只需要更新ev到ev0，在其fkey部分使用较少的项。
三。当一个键及其外键都被选中时，可以通过以下步骤更新关系：（i）将fkey更新为fkey0
在场景2中；（ii）在场景1中将key to key0和fkey0更新为fkey00；并且（iii）返回一个新的枚举，其中包含
5.2程序间优化
由于RDBMS优化器和UDF解释器将彼此视为黑匣子，因此优化两者之间的交互常常成为程序员的责任，而且常常是不可行的。我们采用过程间优化的概念来优化HorseIR程序.整体而言。当来自不同语言系统的两个程序（如SQL和NumPy）被翻译成一个HorseIR程序时，我们可以对组合的IR表示进行过程间优化。
UDF矢量化（UV）。从查询调用UDF类似于从循环调用函数。先前在MATLAB中的工作表明，对带函数的循环进行矢量化有望提高整体性能[15]。
程序间程序切片（IPS）。过程间程序切片能够跟踪变量x，以收集可能影响两点之间x值的所有语句。例如，
一个查询可以将许多输入列传递给一个UDF，其中一些可能不被使用。IPS可以消除在这种非跟踪语句中不必要的计算。
Sec中的UDF基准。6.3旨在演示上述优化对UDF查询的影响。随着我们进一步探索和了解有关udf查询的更多信息，过程间优化的列表应该会不断增加。
6评估
在本节中，我们将给出测试评估的结果，比较HorseIR和MonetDB TPC-H SQL基准和Black Scholes UDF基准进行测试。TPC-H[45]是一个广泛使用的标准基准套件，用于测试用于大规模数据处理的RDBMS实现的性能能力。在过去，这个套件也被用于对MonetDB上的实现进行基准测试[10]。TPC-H模拟企业 消费者（B2C）数据库应用程序10，有8个表。它还包含一组SQL查询，从简单到复杂，涵盖了广泛的SQL结构。作为一个SQL基准标记，这些查询不使用任何UDF。该套件还包含一个数据生成器，可以创建各种大小的合成数据集，称为数据库的比例因子（SF）。 比例因子1对应于数据库大小约为1gb，较高的比例因子按比例增加数据库的大小。
为了测试UDF性能优化，我们选择从PARSEC基准套件V3.0（9）中实现黑斯科尔斯算法。Black-Scholes在金融学中使用偏微分方程（PDE）来计算欧式期权随时间的价格变化。这个算法是完全矢量化的，可以用数组编程有效地编写。由于最初的实现11是在C中实现的，我们使用NumPy UDFs实现了一个Python模块，以便与MonetDB集成。我们使用来自PARSEC包的随机数据生成器生成一百万条记录。为了使用MonetDB udf，这些记录都存储在一个
数据库表blackScholesData由9列组成。
TPC-H SQL基准测试
在本节中，我们将展示基准测试的22个SQL查询（1、3、4、6、14、16、17、18、19和22）中的10个查询的结果。选择这些查询是为了涵盖各种性能影响连接数、条件谓词、表大小、返回的列数和记录数等维度。对于每个查询，我们采用MonetDB的优化器生成的执行计划，并在转换之后手动转换它优化技术详见第4节和第5节。此外，我们通过在不同比例因子SF 1、2、4、8和16的数据库上进行测试来验证实现的可伸缩性。
图2示出了MonetDB的执行时间与HorseIR的执行时间的比率。对于大多数查询，HorseIR优于MonetDB。从所有查询的几何平均值可以看出，MonetDB在所有数据库中的执行时间大约是HorseIR的两倍尺寸测试。HorseIR的改进范围从SF 1的124%到SF 16的79%。表1总结了用于每个查询的编译器优化，以及导致这些改进的原因。我们可以看到对于不同的查询，不同的优化提供了好处，对于某些查询，这些优化提供了非常显著的性能改进。这就强调了需要有一个多样化的技术库，作为优化的机会，它们的潜在影响可以根据每个查询的特征而有很大的不同。例如，我们观察到q17从窥视孔优化中受益匪浅，SF 16的改善率高达361%，而q19则显示出改善最多804%来自回路融合优化。尽管程度不同，但q3和q4的收益
通过分析HorseIR优化技术在测试的查询中的优势，我们发现循环融合（loop fusion）是最常用的优化，它有助于包含过滤条件的查询。恒定传播和折叠、强度降低和公共子表达式考虑到查询的性质，排除的机会是适度的。虽然四个查询受益于窥视孔优化，但这仍然是我们正在探索的一个类别，并希望在未来进一步扩展。为了更好地理解数据库大小的影响，表2显示了当我们从一个比例因子更改为下一个更高比例因子时，每个查询的应时间增量。当HorseIR和MonetDB的所有查询的成本随着数据库大小的增加而增加时，我们可以很明显，对于大多数查询，MonetDB的响应时间比HorseIR的响应时间增加了很多，随着数据集的扩展，突出了HorseIR优化技术的成本效益。
另一个观察结果是，与大尺度因子相比，在低尺度因子下，MonetDB相对于HorseIR的性能稍差。
为了研究这个问题，我们通过将线程数减少到20来运行这个实验。图3显示了与所有查询中的40个线程相比，使用20个线程执行。我们可以看到MonetDB和HorseIR在SF 1上都有20个线程，但是随着数据库大小的增加，在SF 16上，对于这两个系统，拥有40个线程更快。这并不意外，因为对于较小的数据集，并行性带来的开销可能会超过它的好处。然而，有趣的是，对于较小的数据集，HorseIR与拥有额外线程相比，似乎显示出更少的开销
到MonetDB。另一方面，当SF 16的线程数从20个增加到40个时，HorseIR的加速比MonetDB快。因此，我们可以得出结论，HorseIR可以在不同的线程数和数据集大小下进行优雅的缩放。
通过对TPC-H基准测试结果的分析，我们的结论是HorseIR的统一方法是非常有前途的。因为它使用与MonetDB相同的优化执行树作为基础，所以它能够在操作序列和数据流方面利用相同的数据库优化。
除此之外，它还利用了额外的编译器优化，这些优化是根据HorseIR的基于数组的方法定制的，从而提供了总体更快的执行速度。
然而，与MonetDB相比，HorseIR在某些操作中存在一些性能差距。例如，我们对q16的分析表明，HorseIR的性能比MonetDB差，这是由于当前HorseIR与PCRE[3]模式的集成性能较低.我们用来计算谓词的匹配库，这些谓词需要在文本数据中搜索模式。我们正在通过探索即时（JIT）编译技术来改进这种集成。
7相关工作
近年来，利用编译器优化技术提高数据库查询处理性能的重要性得到了重视[30]。一种流行的方法是使用查询编译器将SQL编译成低级编程语言，作为卸载与本机解释器相比，高效编译语言的计算密集型代码部分可以提高性能。
[42]中介绍了在Scala中构造查询编译器的一种形式化方法。在使用IRs将SQL代码转换为C代码的工作中。通过使用基于单个阵列的IR，HorseIR能够以比多IR设计更少的开销处理SQL语义。
Hyper展示了一种更实用的方法，通过将SQL编译到LLVM以利用LLVM的编译器优化基础结构来提高查询性能[37]。TUPLEWARE[19，18]专注于优化以UDF为中心的工作流。他们将UDF编译成LLVM，并使用跨集群的分布式编程来提高性能。DbtoStter通过编译SQL到C++代码（6, 31），以数据流中的高性能增量处理为目标。
上面的三个系统依赖于编译器来优化生成的代码LLVM或C++。擅长优化过程代码的编译器，但对查询的高级功能知之甚少。HorseIR能够用一个相对高级的视图来优化查询。使用
UDF不再是一个黑匣子，因为HorseIR可以通过适当的静态分析看到UDF的功能。
Zhang等人。在SQL中引入了基于数组的扩展，使得数据库系统能够支持复杂的应用程序，比如Conway的Game of Life应用程序[46]。清达[16]实现了循环融合的思想，从APL的基于数组的基元中生成高效的并行代码。HorseIR能够以数组形式表示SQL查询，同时采用数组编程中的优化技术。
在金融领域采用的KDB++/Q[1]融合了SQL和编程语言，提供了一种值得注意的方法。数据库系统KDB+采用通用数组编程语言Q实现，该语言是一种基于解释器的语言。此外，它还支持SQL接口，它是语言Q之上的一种包装器
维护数据库系统，同时无缝支持数组编程语言。然而，它基于解释器的设计在很大程度上依赖于手工优化而不是系统编译器优化。
若有收获，就点个赞吧
0 人点赞
