引言
近日，在国际数据库领域顶级会议ACM SIGMOD 2023上，阿里云数据库与浙江大学合作的一篇论文《Detecting Logic Bugs of Join Optimizations in DBMS》获得最佳论文。
SIGMOD数据管理国际会议（Special Interest Group on Management Of Data.）是由美国计算机协会（ACM）数据管理专业委员会（SIGMOD）发起、在数据库领域具有最高学术地位的国际性学术会议，所收录的论文代表了行业内的最高水平。会议的目的是在全球范围内为数据库领域的研究者、开发者以及用户提供一个探索最新学术思想和研究方法、交流开发技巧、工具以及经验的平台，引导和促进数据库学科的发展。
每年，该会议都会对在数据管理领域做出的贡献颁发多个奖项，其中的“最佳论文奖”，用于表彰每次会议上质量最高的论文，这是中国大陆研究团队自SIGMOD自1975年开始以来49年的历史中，第一次获得该会议的最佳论文奖！
阿里云数据库研究的崛起
数据库是理论研究和工程实践结合非常强的计算机学科，因此除了相关高校外，国内数据库厂商在数据库研究方面也投入巨大，国产数据库及相关技术在国际上的地位逐年攀升。以阿里云PolarDB为代表的中国新一代数据库在国产化替代中的大规模应用及云化部署数据库方面的技术创新，在数据库行业中备受关注。
除了依靠自身的研发力量去开展前沿技术研究，阿里云数据库团队与国内各大高校和研究机构都有深入的合作研究，特别是与以杭州为主场的浙江大学，更是合作共建了下一代数据库实验室。每年PolarDB数据库研发团队会根据业务研发过程中的技术挑战，提炼出需要联合攻关研究的问题并“张榜”出来，而浙江大学的师生则根据其擅长的研究领域，对感兴趣的研究问题提出初步的解决思路并“揭榜”，双方针对目标问题进行多次讨论确定大致技术路线之后，浙江大学会派遣博士/硕士实习生进入PolarDB研发团队实习以深入挖掘问题背景并在实际业务中对解决方案进行验证。对于那些值得深入研究的问题，联合实验室会多年延续同一个课题进行研究。该次获奖的浙大团队即与PolarDB数据库团队有着多年合作历史。合作团队基于该Best Paper技术开发的数据库逻辑测试工具，落地于PolarDB内核测试系统，该工具累积检测出50余项数据库逻辑错误，最终代码漏洞均在上线前被修复。在此之前，双方合作的另一项研究方向，数据库查询表示学习项目也落地于PolarDB数据库的外围服务系统，通过自动化慢查询检测与慢查询分类，及时预警慢查询并推荐合理的优化方法。该研究的结果论文也发表在SIGMOD 2022上。
2023年截至目前，阿里云数据库团队共有23篇论文被SIGMOD、VLDB、ICDE、OSDI、ASPLOS等国际顶会收录，其中就包括了这篇最佳论文。研究范围覆盖云原生、智能化、HTAP、安全可信等数据库前沿研究方向。也代表中国在数据库国际性学术会议中已占据非常重要的席位。
而针对本次PolarDB 查询优化器当中的漏洞探测这一传统经典问题，阿里云与浙大的研究团队创新使用Learning-Base的方法来指导在给定shcehma集合之上搜寻有效的Join Query组合，最终取得了突破性成果，这充分展现了计算机系统多领域交叉技术研究的效力。下文概述本篇论文要解决的核心问题及技术思路。
最佳论文的研究背景及动机
阿里云PolarDB是国内领先的云原生数据库系统，其自2017年发布以来，迅速被云上企业广泛采用。随着PolarDB数据库的客户数越来越多，在其上运行的应用复杂程度的增加，用户对于更强大、更安全的数据库的需求也越来越迫切。因此，如何检查数据库漏洞和错误，成为保障数据库安全、提升数据库稳定性的关键之一。
在数据库查询执行期间，主要有两类错误（bug）：一种常见的错误是数据库突然崩溃停止，这种错误对于开发人员来说相对容易检测，因为数据库连接会突然中断。然而，还存在一类隐藏的错误，即逻辑漏洞。在这种情况下，数据库正常运行并返回结果，但实际上并非正确的结果。
以上图中的两个逻辑漏洞为例，
- 图a展现了MySQL的一个哈希连接错误，这种错误发生在错误地将零和负零视为不同值的情况下，导致最终返回一组空集合；
- 图b涉及数据类型转换和数据精度损失导致的错误半连接：在MySQL中，当比较两个值是否相等时，数据类型转换和精度损失可能导致意外的结果，从而影响查询结果集的构建。
逻辑漏洞很难检测，但其导致的后果确很严重，因此也被视为“无声的漏洞”，而本次Best Paper的便主要聚焦于此问题。
针对逻辑漏洞，领域内已经有一些检测方法，例如部分查询语义（PQS），但这些方法通常只支持针对单表选择查询的检测，在涉及多表查询以及不同的连接算法和连接结构的情况下，仍存在大量的研究空白。而最常用的差分测试，通过在不同数据库中执行相同操作，以验证其一致性，这种测试仍存在问题：假如两个数据库返回相同的结果，也有可能是基于同样错误的逻辑生成了一样的结果，也即如何验证查询结果正确性的关键问题。同时，测试数据库现在面临的搜索空间是非常庞大的，如何引导测试以尽可能消耗最小的资源穷尽全部测试，也是一个需要解决的问题。
核心技术思路
围绕这两个关键问题，阿里云与浙大联合团队引入了一个名为TQS（转换查询合成）的全新解决方案，以解决MySQL数据库中可能出现的逻辑错误。
TQS包括DSG和KQE两部分，分别为数据驱动的模式和查询生成，与知识引导的查询空间探索。
测试数据生成
为解决测试数据的真值生成问题，阿里云与浙大的联合团队采用了以下方法：
1、首先，根据给定的宽表，使用函数依赖（FD）将该表拆分为多个表。
2、在测数据集中插入一些噪声数据作为边缘情况的样本（图中彩色数据），并基于数据库的模式图模型，随机游走生成一系列查询。这样是为了覆盖边缘测试场景。
3、构建RowID映射表，用于记录在表拆分过程中，宽表中的行和拆分后表的行的对应关系。根据表连接是表拆分的逆向过程的直觉，构建基于构建RowID映射的Bitmap索引，以便从宽表中检索到连接查询的理论真值。这些真值生成后，便是检测潜在逻辑错误的参照样本。
查询模式生成
在解决了数据生成及其有效性问题之后，接下来需要解决查询SQL的自动化生成问题， 在既定数据集合上可生成的连接查询的数量会随着表格和列的数量呈指数级增长，这显然无法使用枚举法一一验证。为了：更高效地探索查询未知空间呢， 联合研究团队提出了TQS的第二部分设计——KQE。
KQE首先将模式图进一步拓展为一个规划迭代图，来表示整个查询生成空间。同时，在大量的历史查询图中，KQE构建了一个基于嵌入的图索引，以确保新生成的查询图尽可能地远离其在历史查询中的近邻，探索更多的未知空间。
总体来看，KQE可基于结构相似性为生成的查询图评分，同时也通过自适应随机游走多样化查询生成，从而极大降低了对于重复查询的概率，节省了计算资源开支。
实验效果分析
为了验证TQS方法的通用性，除了PolarDB之外, 研究团队也在MySQL、MariaDB、TiDB另外三款流程的DBMS上进行了实验。
运行了 24 小时后，TQS 成功找到了 115 个漏洞：MySQL 中 31 个、MariaDB 中 30 个、TiDB 中 31 个、PolarDB 中 23 个。通过最小化测试样例，我们进一步将它们分为20种类型。
实验检出的漏洞分类详表
目前所有这些被检测到的漏洞都提交给了相应数据库社区，并得到了他们积极的反馈。这些漏洞的危机程度被数据库社区判定为首要危急或严重级别，一些漏洞已经修复在了其数据库最新版本中。
具体来说，MySQL 8.0.28的错误主要集中在Semi-join和Sub-query的执行过程中，其中，几个错误被评定为首要危急，即最紧急的错误，这些错误已经在MySQL 8.0.30版本中得到修复，并提供了相应的修复说明。另外，针对PolarDB，我们则直接提交错误报告，相关错误已经被修复。
总的来说，相比于其它方法，TQS在多项指标上取得了更优的效果，较原有方法实现高达100倍的性能提升，各组件的有效性也通过控制变量实验得到了检验。
后记
依托于阿里巴巴-浙江大学前沿技术联合研究中心这一研究载体，阿里云瑶池数据库团队与浙江大学师生，完成了从实践中提出问题、由校企联合攻关、成果落地产业界的科研新探索。论文一作、浙江大学博士唐秀正是在阿里云PolarDB进行研究型实习期间，与联合团队一起完成的课题攻坚。而这篇Best Paper只是一个起点，阿里云瑶池数据库团队将继续与各大高校合作探索数据库技术的边界，为客户提供安全，稳定，高性能，低成本的数据库服务。
