代码编织梦想


摘要

  尽管SQL在简单的分析查询中无处不在,但它很少用于更复杂的计算,如机器学习、线性代数和其他计算密集型算法。这些算法通常以过程方式编程,看起来与声明性SQL查询非常不同。然而,SQL实际上提供了执行各种计算的构造。在本文中,我们展示了如何将过程结构转换为SQL-启用复杂的SQL-only算法。在算法中使用SQL可以使计算更接近数据,只需要最小的用户权限,并增加软件的可移植性。生成的SQL算法的性能在很大程度上取决于底层DBMS和SQL代码。令人惊讶的是,我们发现像HyPer这样的查询引擎可以实现非常高的性能——在某些情况下甚至胜过像NumPy这样的最先进的线性代数包。

一、介绍

  理论上,任意计算都可以用SQL来表示。然而,这通常被认为是一种理论观察,而不是一种实际方法。在SQL中直接表示复杂算法的一个障碍是,算法通常是用过程语言表示的。SQL的声明性使得编写统计学习或优化算法的查询变得非常重要。

  目前,复杂的算法是在数据库系统之外实现的,使用用户定义函数(udf),或者依赖于系统特定的dbms内操作符。直接在SQL中表达算法有四个主要好处:

  • 近数据计算
      使用SQL算法,使得数据保留在数据库中,SQL查询引擎可以立即开始计算。并且只显示计算结果,而不显示底层数据,则可以确保更高的数据隐私。
  • 灵活性
      使用SQL可以自由定制修改,且只需要最小的用户权限就可以执行各种计算。
  • 高度抽象
      SQL算法的向量化、并行甚至分布式执行由底层DBMS自动完成
  • 可移植性
      如果SQL算法使用由多个DBMS供应商支持的通用SQL子集,那么该算法无需修改即可在其他DBMS上运行。

二、SQL算法原语

  在本节中,我们将过程语言的算法原语映射到SQL的声明性语法。为了演示这种转换,我们将展示Python和PostgreSQL的SQL方言中的代码片段。

2.1、Variables

  在SQL中,Variables可以表示为关系或关系中的值。这里的关系指的是一些数据结构,如标量、向量、矩阵、张量、集合、哈希表,甚至树和图。在SQL计算期间,可以使用WITH子句创建新变量。WITH子句允许命名子查询。然后可以在主查询中的几个位置引用这些命名的子查询。然而,与过程语言中的变量不同,SQL中使用with子句创建的变量是不可变的。要更新SQL变量,必须创建一个新变量。对于这类原语的python与SQL转换的例子如下:

在这里插入图片描述

2.2、Functions

  函数在大多数编程语言中都是必不可少的。SQL标准允许创建SQL函数,但并不是所有系统都支持。所以有一种替代方法是用WITH构造,从而允许将本地函数嵌入到SQL查询中。
在这里插入图片描述

2.3、Conditions

  标准SQL不提供分支结构,例如if-else来控制程序流。在SQL中,最接近if-else语句的结构是CASE语句。但是,CASE语句决定表达式的结果,因此类似于三元操作符而不是控制结构
  要在SQL中模拟条件控制流,UNION ALL构造是合适的。UNION ALL构造将两个或多个SELECT语句的结果组合在一起。通过只组合那些满足SELECT语句WHERE子句条件的结果,就可以模拟条件控制流(见清单3)。UNION ALL的唯一限制是各个SELECT语句中列的数量和列的数据类型必须匹配。
在这里插入图片描述

2.4、Loops

  在SQL中,循环有两种变体,它们是通过递归查询实现的,符合SQL标准[11]。大多数dbms都支持第一种变体,它是一个简单的循环,在子查询中没有递归引用(参见清单4),如下
在这里插入图片描述
  第二种变体包含子查询中的递归引用,据我们所知,它只在PostgreSQL、DuckDB和HyPer中得到完全支持,如下
在这里插入图片描述
  第二个循环变体允许在FROM子句的子查询中使用清单5中的递归工作表x。这些子查询也可以是递归的。如果对工作表的递归引用在FROM子句中出现超过一次,PostgreSQL将产生一个错误。可以通过在FROM子句中创建一个新变量并在以后的计算中引用它来避免这个错误(参见清单5中针对PostgreSQL的变通方法)我们大量利用子查询中的递归引用在SQL中实现各种算法。通过在子查询中支持递归引用,DBMS供应商可以在其产品中启用仅sql算法。

  递归查询的限制因素是缺乏拥有多个工作表的可能性。在递归中只允许有一个工作表。如果算法需要在每次迭代中更新多个变量,则必须立即将它们全部打包到工作表中。在迭代期间,这些变量必须从工作表中解包,然后再为下一次迭代重新打包。

2.5、Errors

  具有实用价值的SQL程序应该对错误的输入数据提供反馈。为了在SQL中实现输入验证,我们使用UNION ALL构造。在清单6中,计算了三种状态下概率分布的熵。概率的一个性质是它们大于等于零并且它们对所有状态的和是1。在创建错误关系时,在WHERE子句中检查这些前提条件。如果检测到错误输入,则Errors应该包含相应的错误消息。

在这里插入图片描述


三、案例研究

  这里使用基于梯度下降的逻辑回归作为案例研究,以证明以数据库友好风格编写的SQL算法是实用的。逻辑回归是一种流行的二元分类机器学习方法,它会导致以下凸优化问题:
在这里插入图片描述
  下面是一个用python写的基于梯度下降的逻辑回归
在这里插入图片描述

3.1、对数据库友好的SQL映射

  计算梯度是算法中最耗时的操作。如果性能很重要,那么用于计算梯度的SQL代码必须是数据库友好的。在这里,梯度计算主要由线性代数运算组成。SQL中的线性代数计算通常映射为一种格式,该格式显式存储向量或矩阵的每个值的索引。向量和矩阵的这种表示类似于用于稀疏线性代数的坐标格式(COO)。下面显示了如何在SQL中使用COO样式计算清单7中的梯度。
在这里插入图片描述
  在SQL中使用COO风格进行线性代数的一个优点是它的通用性,也就是说,SQL代码不依赖于矩阵中的列数。在使用COO风格时,默认情况下也支持稀疏线性代数。此外,正在进行积极的研究,以开发查询引擎,以减少类coo线性代数查询的执行时间[16]。然而,coo风格的SQL代码的性能可能不足,因为显式索引、糟糕的局部性和将数据转换为正确格式的昂贵转换会增加内存消耗。此外,SQL中co风格的线性代数严重依赖于连接。在清单8中,连接在WHERE子句中指定。

  SQL中coo风格线性代数的另一种方法是将关系本身视为向量或矩阵。关系的行和列对应于线性代数的行和列向量。向量和矩阵的这种表示类似于它们在密集线性代数中的表示。清单9显示了清单7中使用SQL中的密集线性代数样式的梯度计算。
在这里插入图片描述
  这里的梯度计算避免了连接,并且不需要为向量和矩阵提供显式索引。因此,我们称这种计算是数据库友好的。特性f1、f2和标签y存储在单个关系x中。在梯度计算过程中,特征和标签被传播以避免不必要的连接。例如,请查看在创建关系cse和v时如何选择特征f1和f2。例如在创建关系u时,当再次需要f1和f2时,这些“不必要的”选择避免了连接。

3.2、性能结果

  我们比较了NumPy、HyPer和PostgreSQL之间基于梯度下降的逻辑回归的性能。

  • NumPy是一个用于高性能科学计算的Python包。我们将NumPy链接到数学内核库(MKL)版本2020.0.2。英特尔的MKL库广泛使用矢量指令和多核处理。
  • HyPer是一个面向列的内存DBMS,在OLTP和OLAP工作负载下都能实现高性能[17]。我们使用Tableau公开的Hyper API版本0.0.13287。
  • PostgreSQL是一个广泛使用的、开源的、面向rowwororiented的DBMS。我们使用PostgreSQL 12.8版本。

  在我们的测量中,我们使用一台带有Intel i910980XE 18核处理器(36个超线程)的机器,运行Ubuntu 20.04.1 LTS,内存为128 GB。每个内核的基频为3.0 GHz,最大turbo频率为4.6 GHz,支持AVX-512矢量指令集。对于HyPer和PostgreSQL,我们测量了两种不同逻辑回归实现的性能。一种是基于coo风格的线性代数,另一种是数据库友好型的,使用无连接的密集风格进行线性代数(详细信息请参阅前一小节)。对于数据库测量,我们使用临时表。我们不使用数据库索引。在运行逻辑回归求解器时,我们以每秒迭代次数来报告性能。一次迭代计算梯度并更新前一次迭代的权重。我们验证所有实现计算相同的权重,从而获得相同的模型精度。

  下图显示了具有32个特征和100万个样本的数据集的基于梯度下降的逻辑回归的性能。虽然HyPer上的数据库友好实现实现了每秒100多次迭代,但PostgreSQL上的性能与它的COO实现没有什么不同。与HyPer相比,PostgreSQL的性能非常低,因为HyPer是一个使用查询编译的高效并行DBMS。因此,我们在进一步的测量中忽略了PostgreSQL。然而,令人惊讶的是,HyPer的速度几乎是NumPy的三倍。下面的测量探讨了HyPer优于NumPy的条件

在这里插入图片描述
  图2显示了性能取决于用于计算的线程数。当使用两个线程时,HyPer和NumPy的执行情况大致相同。当使用两个以上的线程时,HyPer上的数据库友好实现比NumPy快。随着可用内核数量的增加(线程数≤18),HyPer的性能会稳步提高。通过超线程的额外并行化,HyPer获得了更高的性能。与HyPer相比,NumPy中梯度计算的并行化很差。尽管MKL在并行化线性代数操作方面通常非常有效,但对于图2中包含32个特征的示例来说,它就失败了。

在这里插入图片描述
  在图3中,我们将特征的数量在4到128之间变化。我们把它留给实现来决定使用多少线程。NumPy利用数据集中所有18个核心和4个特征,但如图3所示,这种情况的效率相当低。图3显示,当数据集中少于128个特征时,HyPer是最快的替代方案。然而,HyPer和NumPy之间的性能差距随着数据集中特征数量的增加而缩小。在128个功能下,NumPy甚至比HyPer还要快一点
在这里插入图片描述

  图4显示了性能作为数据集中示例数量的函数。测量结果以对数标度表示。对于数据集中少于或等于105个示例,NumPy是最快的选择。NumPy将矩阵和向量连续地存储在内存中,因此当数据集适合缓存时,它将受益于良好的局部性。此外,由于权重更新依赖于先前计算的权重,因此对于小数据集,有效的并行化无法发挥作用。同样,为了进行基准测试,我们重复运行算法100次迭代。在HyPer中,这些时间包括缓存SQL查询的运行时。对于较小的数据量,查询的设置成本不会摊销。因此,对于小问题,NumPy要快得多。在HyPer中,测量中存在不规则性。对于数据集中的106个示例,HyPer每秒执行的迭代次数多于105个示例。这种不规律的原因是HyPer只通过一个线程执行少于或等于105个示例的所有查询。

在这里插入图片描述


四、结论以及未来工作

  纯sql算法不是一个理论噱头,但可以具有很高的实用价值。它们提供了诸如近数据计算、代码更改的灵活性、对底层DBMS体系结构的高度抽象以及可移植性等优点。我们展示了如何用SQL表示算法原语。通过使用这些原语,可以在SQL中实现计算密集型算法。在案例研究中,我们提供了数据库友好的SQL代码,它避免了线性代数操作的连接。事实证明在HyPer上的数据库友好型SQL实现甚至可以在更大的数据集上优于NumPy。

  算法中的循环通常包含对先前迭代数据的复杂计算。我们演示了如何在SQL中通过在WITH recursive的FROM子句中使用对工作表的递归引用来实现这种循环。像PostgreSQL、DuckDB或HyPer这样支持递归引用的dbms,已经可以使用SQL进行各种计算。扩展DBMS以支持子查询中的递归引用将是很简单的,我们希望本文能够促使DBMS开发人员实现这一特性。

  在未来的工作中,我们计划使用编译将命令式结构自动转换为SQL。编译器方法也可以将线性代数操作转换为SQL。为了使线性代数操作的转换尽可能高效,需要进一步探索SQL中无连接线性代数的局限性。深度学习似乎也是我们计划探索的一个有趣的用例。通过使用外部工具(如我们的矩阵演算[13-15])计算导数并将其转换为SQL,剩下要做的唯一事情就是在SQL中实现优化算法,这是可能的,正如我们在案例研究中所展示的那样。因此,我们相信SQL机器学习和其他形式的SQL计算密集分析非常有前途。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lrzHHl/article/details/138626914

机器学习实用指南_机器学习方法:实用指南-爱代码爱编程

机器学习实用指南 by Karlijn Willems 通过Karlijn Willems 机器学习方法:实用指南 (How Machines Learn: A Practical Guide) You may have heard about machine learning from interesting application