SIGMOD 2019 现场直击!带给你最独家的 15 篇论文全解读

1,335 阅读24分钟
SIGMOD会议位列数据库方向的三大顶级会议之首(其次是VLDB及ICDE)。2019 SIGMOD于6月30日至7月5日在荷兰阿姆斯特丹举办。

SIGMOD是数据库方向的三大顶级会议之一(另外两个是VLDB及ICDE),2019 SIGMOD于6月30日至7月5日在荷兰阿姆斯特丹举办。阿姆斯特丹是一个非常美丽的城市,以郁金香、运河、风车、梵高等闻名于世。今年的SIGMOD在欧洲举行,参加的总人数相比往年更少,欧洲本土的参会人员相比往年更多。OceanBase团队的核心成员也有幸亲临现场参加了这一数据库的盛会。

OceanBase展台前聚集了来自世界各地探讨技术的参会者

随着SIGMOD每年在世界各地的召开,我们越来越能感受到OceanBase在华人学者工程师中的知名度越来越高。很多同学已经了解到OceanBase在诸多金融机构拥有了很多落地应用的案例,甚至还有欧洲同学希望来到千里之外的中国来做OceanBase的intern。我们也愈发感受到,华人在数据库领域正在逐步形成一股不可忽视的力量。

SIGMOD分为Research Session和Industrial Session。其中,Research Session总共提交了430篇文章,录用88篇,录用比例为22%;Industrial Session提交了53篇论文,录用了16篇。整体上看,今年的SIGMOD算是一个小年,很难看到让人眼前一亮的论文。

最重磅 | 两大议题:机器学习&区块链

今年的两个Keynote分别是:Lise Getoor的“Responsible Data Science”,以及C. Mohan的“State of Public and Private Blockchains:Myths and Reality”。

这两篇论文都和传统的数据库关系不大,第一篇是机器学习相关,近年来一直都是SIGMOD的热点,第二篇是区块链,今年的SIGMOD还专门加入了一个区块链的专场。



C. Mohan认为联盟链比较有前景,不过台下有人提问反对,认为不能因为公有链比较难就回避问题,而是应该投入精力去研究。

最权威 | 最佳论文/奖项花落谁家

SIGMOD 2019的十年最佳论文(Test of Time Award)颁给了—— Privacy Integrated queries: an extensible platform for privacy-preserving data analysis 关于数据管理中的隐私性处理的文章。这也符合这两年全社会对于互联网大数据时代隐私保护的关注,Google和Facebook等互联网巨头,都在美国和欧洲受到相关监管机构的挑战。

SIGMOD还有一个奖项叫做System Awards,2015到2018年的获奖者分别是Postgres(2015),MonetDB(2016),SQLite(2017),Hive and Pig(2018),今年的获奖者是Aurora(2019)。可以看出,这些系统都具备世界范围内的影响力,我们也期待未来中国的系统能够获得该奖项。

最独家 | Anastasia荣获终身成就奖

今年的E.F. Codd Innovation Award给了Anastasia Ailamaki,这一奖项类似于数据库研究领域的终身成就奖,表彰对于数据库研究事业做出了重要贡献的人士。

Anastasia Ailamaki是EPFL的教授,在University of Wisconsin-Madison获得的PhD学位,是David DeWitt和Mark Hill两位数据库和计算机体系架构方向大牛的弟子,她提出了一个很有意思的话题——Architecture-conscious data management。



她认为除了扩展性以外,单线程的极致性能在数据库的实现中是至关重要的一点,而要做到这一点,数据库的系统架构,编码设计都需要充分考虑到计算机体系架构的特点,1998年就提出了这些方向的话题和研究,然而20年过去了,这方面的工作反而并不见提升,相关研究方向的学生越来越少,工程产品实现的性能也不尽如人意。


大家对于计算机编程的理解越来越往上而不是往下走了,很少有人能做到一个配合体系架构的更好性能的设计和实现。这其实也是我们日常工作中常常会思考到的一个问题,实事求是的说,我们今天的系统软件开发者可能在对底层体系架构的理解,反映到上层编码实现上是存在着理论知识和实践经验的缺失。

最全面 | 四大研究领域论文全解读

从大的方向来看,院校学术研究方向,以欧洲(慕尼黑工大TUM,CWI等)和亚洲院校(NUS, HKUST)为代表,主要在做一些新硬件,列存,in-memory,向量引擎编译执行方面的工作和传统的数据库优化的方向,开源社区在更加积极的拥抱SQL,传统商业数据库公司忙着进行数据库的云化,MS在本次会议上关于数据库上云一气提出了三篇相关paper,结合Oracle 19c的新功能开发点来看,都是围绕着在云上部署和自动运维,管理数据库而展开工作。整体来看也确实符合当下数据库研究的趋势以及工业界的发展现状。

然而传统关系数据库内核的突破性工作变得越来越少,很多研究工作是多个领域相结合的成果。云数据库、新型硬件,自治数据库、AI+数据库、图数据库,以及今年新增的区块链,这些都成为了SIGMOD 2019讨论的热点。接下来我们从参会关注的角度,分别列举一些会议的论文以飨读者。

研究领域一:学院派数据库

1. Cache-oblivious High-performance Similarity Join

这篇论文,如前述Anastasia所述的针对计算机体系架构进行数据库的设计这个方向,是要解决在当前内存数据库的情况下,传统的IO bound不再是瓶颈的情况下,如何使得算法能够更好的适应三级缓存,CPU寄存器以及TLB表,从而能够做到cache-oblivious的去解决similarity join的问题,比如关系数据库中会用到的band join(Oracle 12c也有实现),N-way join等。更进一步的,相比于大部分实现仅是做到cache-aware,修改算法去适配已知的cache大小去达到更好的性能,在系统硬件变化,或者有多个用户争抢不能确定可使用缓存大小的前提下,做到cache-oblivous的情况下同样能够高效的实现算法执行。

主要的贡献就是提出了采用F(ast)G(eneral)F(orm) Hilbert curve join的方法,充分的发掘SIMD、MIMD的能力,做到高效的执行。实验显示,runtime和cache miss都大幅好于现有的算法。下一步他们计划在更多的数据库算子,比如k-nearest neighbor, N way-join上采用类似的算法,从而可以高效的利用CPU缓存和寄存器,实现极致的算法性能。这篇论文其实对于工业界的数据库实现来说是一个很好的工程实践的例子,相关的算法实现有非常好的参考价值。

2. Hyperion: Building the Largest In-memory Search Tree

这是继去年SIGMOD Best Paper之后,又一篇讨论以Trie的方式来实现数据库的索引结构的论文。大家知道通常来说,最常见的数据库索引有B+ tree, hash, bitmap等,最近这些年对以Trie来实现数据库索引有不少的研究在投入,主要想要达到的目的是做到一个效率和内存使用的平衡。效率上要做到对范围查询和点查询都能够有比较好的支持。本篇论文的主要贡献在于通过减少额外开销,减少内部分片和优化内存管理的实现,达到了一个极优的点查询性能和不错的范围查询性能,同时内存使用比其他同类的实现要大大的降低。这也是索引结构实现的又一个有意义的尝试。

3. Designing Distributed Tree-based Index Structures for Fast RDMA-capable Networks

这篇论文介绍了在当今大集群,大内存的情况下,分布式场景中,如何更好的利用这一硬件特性,构建分布式索引并采用RDMA技术来进行性能加速的思想。在当前的Network Attached Memory(NAM)架构下,集群的整体内存总量是非常大的,那么在处理这样海量数据的情况下,构建的大量的索引也需要分布式的存储在多台机器的内存里,那么对索引的查询,更新等操作,在传统的操作方法下,必然会存在网络的额外开销。RDMA技术已经提出了很多年,本论文最大的贡献点就在于对于建索引这个场景,详细讨论了粗粒度,细粒度以及混合策略的三种索引内部结构设计方式,采用RDMA的方法,评估各种方式索引的性能。这是一个非常实用的方向,在我们的分布式数据库的工程产品实践中也可以借鉴。新硬件,尤其是基于高速网络实现的远程高效访问机制,是对share nothing系统架构的一个很大的红利。

4. BriskStream: Scaling Data Stream Processing on Shared-Memory Multicore Architectures

这篇论文是新加坡国立的同学对于在Scale up的系统里,如何应对多核NUMA(Non Uniform Memory Access)架构,更好的进行流计算处理做的一些工作。传统数据库领域,以Oracle为代表,是Scale up的重要实践者,而在Scale up的硬件设计中,NUMA是一个重要的设计点。Oracle对此做了很多的优化,保证OLAP查询在多个Socket上的负载均衡,保证内存的本地访问,提高系统的整体性能。在流计算领域,目前还没有太多的这方面的工作。

作者提出了一个叫做Relative-Location Aware Scheduling(RLAS)的执行优化策略,在数百核NUMA架构下能够将计算性能真正的Scale up,性能超过开源的DSPS一个数量级。从分布式数据库系统的角度来看,NUMA也会是未来的一个方向,当计算机体系架构进一步发展,单机的Scale up设计继续往前演进的时候,对于NUMA架构的引入可能会更加的普遍,到那时候,不是一定要特别高端的硬件CPU架构才会需要做NUMA aware的设计,很可能普通的PC server用的CPU也是这样的架构。如何在这样的架构下让代码表现的更好,这也是architecture aware设计的一个重要的考虑点

5. DuckDB: an Embeddable Analytical Database

这篇文章是一个Demo小短文,出自CWI的数据库实验室,想法出自SQLite这个产品形态,因为对于分析型查询的支持效率不高,他们做了一个完备的数据库系统,并没有什么特别创新的思想,就是根据已有的各方面比较成熟的理论,搭建了一个系统,有自己的parser,optimizer,query engine等等,采用向量处理引擎,做了一些工程上的优化,同时实现了Hyper的MVCC思路,提供了较好的OLTP的支持。之所以提及这篇论文,是觉得欧洲学术圈的同学们这种不是为了追求创新而创新,看到实际的问题就去搭建系统解决的做法,很是值得称道。目前DuckDB能跑所有的22个TPC-H查询,和99个TPC-DS查询中的97个,项目的同学还在持续的开发着这个系统。

研究领域二:开源数据库/大数据产品

6. Apache Hive: From MapReduce to Enterprise-grade Big Data Warehousing

Apache Hive在项目成立之初是一个面向大数据分析的系统,在这篇paper中,Hive全面转向了拥抱传统关系型数据库的思路,这充分证明了一点,技术是为商业服务的,企业客户既然是这个市场的大金主,那么一切企业客户需要解决的问题,喜欢的解决方案,才是技术方案需要去要考虑的方向。在这篇论文中,Hive表示做了如下的几点增强,以更好的适应企业数据库市场的需求,去和传统数据库厂商竞争:

1.SQL和ACID的支持,基于Hive的Metastore做了一个transaction manager,实现了read-committed级别的隔离;

2.优化器技术,没有采用自己实现的方案,集成了Calcite,对于开源生态来说,这也是一个很自然的选择,从开发周期,工作量,生态维护来看,自研对自己系统最好的优化器的投入非常大;

3.执行引擎优化,从MapReduce转换到了Tez,还加入了LLAP的支持,可以对数据做缓存的执行系统;

4.多数据源支持。看得出来Hive想要在企业市场去分一杯羹的野心,但是企业市场对开源的服务支持,企业自身技术能力的门槛是一个很重要的考量,这一块开源产品还有很长的路要走。

7. One SQL to Rule Them All-an Efficient and Syntactically Idiomatic Approach to Management of Streams and Tables

这篇论文是Apache几个顶级的开源项目,Beam/Flink/Calcite的贡献者加上美国能源部下属的橡树岭国家实验室共同做的一个项目,从标题就可以看出,主要的建议和工作就是用一套统一的SQL语言同时支持现在的point-in-time的关系查询以及流处理查询,他们建议对现有的SQL标准进行扩展。主要的想法是将现有的关系扩展,看成可以随着时间维度变化的关系,在此基础上引入事件时间处理的语义和流数据的时间维度物化控制。其实数据库领域对于流式的关系数据处理一直都有研究,如OpenCQ,CONQUER以及获得过SIGMOD十年大奖的NiagaraCQ系统,现在做流处理的社区希望能在不改变现有SQL算子的基础上,通过扩展SQL标准,能够实现大一统的处理。这应该是一个有益的尝试,如果关系数据库社区能够接纳这一意见,相信未来的关系数据库产品能够给客户带来更大的价值。


8. FoundationDB Record Layer:A Multi-Tenant Structured Datastore

FoundationDB是一个底层支持事务的分布式Key-Value存储,2015年被苹果收购,用于iCloud存储服务。收购之前,FoundationDB有一些公开的设计文档,我就是从这个系统借鉴了table group的设计。在分布式系统中,经常出现同一个事务同时操作多张表格,比如一次交易需要同时修改交易基础表和交易扩展信息表,FoundationDB会把这些表格放到一个table group里面,避免分布式事务。Table group和Google Spanner里面的entity group解决了类似的问题,但语法有些不同。这篇论文的Record Layer是一个构建在FoundationDB之上的开源库,封装数据类型、Schema、索引、多租户等功能。

研究领域三:老牌商业数据库厂商

对于传统的数据库厂商来说,这几年的关键词其实就一个——云化。在传统数据库市场格局已经基本定型的局面下,数据库云化是一个对市场进行重新洗牌,重新塑造新的市场领导者的机会。在刚刚过去的6月份,Gartner发布了题为《The Future of the DBMS Market Is Cloud》的报告,明确的断言了未来数据库市场将会是云的天下。根据Gartner的统计数据显示,数据库市场在过去的两年增长率分别是13%和18.4%(过去十年增长最快的速率),其中68%的增长来自于云数据库市场,而在剩下32%的来自于用户本地数据库服务的增长中,更多的是由于数据库价格的提升和现有系统升级而产生的开销——换句话说,本地数据库服务的新增长相比之下非常之少


在云数据库的这片战场上,我们既看到了像Microsoft SQL Server这样的传统数据库大厂,也有靠提供数据库云服务起家的市场新贵——Amazon AWS,二者在过去两年的云数据库市场表现最为抢眼,他们两家一起贡献了约75%的云数据库增长份额。相比之前,数据库的老牌霸主Oracle在转型云化的道路上走的就不那么顺利,市场份额在不断受到瓜分的同时,云服务负责人Thomas Kurian和其他几位管理骨干的出走也为整个云化蒙上了一层阴影。

这些市场上的变化在今年的SIGMOD上也能看到一些端倪。比如,微软今年一口气提交了三篇论文,都是和数据库上云的部署、运维有关;而AWS的Aurora数据库则因为“在云服务环境下重新定义了关系数据库的存储系统”而获得了2019 ACM SIGMOD System Award。相比之下,Oracle仅仅是在去年的SIGMOD上发表了一篇来自于Oracle Labs的研究论文,云数据库方面的产出并不是很多(不过据了解相关的研究和工程实现也在不停的推进中)。

9. Socrates: The New SQL Server in the Cloud

近两年来,云数据库在架构上选择单机模型+存储计算分离是一个总体的趋势,比较有代表性的有Amazon的Aurora,这篇论文介绍了SQL Server的存储计算分离的数据库服务: Socrates。Socrates是SQL Server的存储计算分离架构。相比本地存储架构,Socrates的优势在于提升了存储容量(4TB => 100TB),提高了可用性(99.99% => 99.999%),并且存储容量更加弹性。

Aurora是公有云上第一个存储计算分离的系统,论文发表在SIGMOD 2017,叫做“Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases”。Aurora提出了“the log is database”的设计理念,数据库实例往底层存储只写redo日志,将日志回放等操作下放到底层存储,从而大大降低网络开销。Socrates与Aurora在这点上原理类似,XLog Service用来存储日志,Page Server用来存储物理页面,数据库计算层往XLog Service写入redo日志,Page Server从XLog Service读取日志并回放。Socrates的特点在于把XLog Service和Page Server分得比较开,整体架构比较清晰。

值得一提的是,SQL Server之前的一个版本是基于逻辑复制单机技术库的HADR系统,很显然,作为一个逻辑复制的高可用方案,HADR并不能解决SQL Server作为一个单机云数据库在扩展性上遇到的挑战,这也是Socrates系统的设计目的。相比这个架构下的前辈——Aurora,Socrates从概念上创新的点似乎不多,但其作为Azure云数据库产品的一个重要补充是有明确的市场价值的

10. Automatically Indexing Millions of Databases in Microsoft Azure SQL Database

索引是关系数据库——尤其是OLTP场景——最重要的优化手段之一,因为谈到数据库的运维和调优,索引的创建是最重要的问题。关于索引建议的论文有非常长的研究历史,相比那些研究性论文来说,这篇论文在理论上的创新不算很多,但作为一篇工程实践的总结,还是值得一读。

作者提出了在云数据库时代自动索引创建的四大挑战:索引创建的服务的可扩展性、如何生成用于索引建议的输入(如何识别有价值的workload)、在优化器估计有误的情况下如何避免性能回退以及如何尽可能不影响系统的正常运行。在系统架构上,作者引入了control plane这个模块,用以在全局层面控制、调度、监控、管理整个索引创建的各个环节,这个设计笔者觉得还是很有必要的。随着云数据库的应用场景越来越广,用户越来越多,如何在大规模下同时管理多个数据库实例是重要的研究方向,而我们也会看到越来越多的数据库单实例的功能(例如index advisor)被抽象到整个云数据库运行环境,数据库管控平台和数据库内核的能力边界需要被重新定义。

论文同时也提到了一个重要的经验,就是对于索引自动创建这个功能来说,不影响用户正常的应用是非常重要的,只有在不“做恶”的情况下,才能使更多的用户更放心的使用“自动创建索引”的功能,才能真正将整个功能大面积的推广开来,这也是该项目得以“成功”落地的关键。

11. AI Meets AI: Leveraging Query Executions to Improve Index Recommendations

跟上面一篇论文一样,本篇文章也来自微软研究院,解决的都是SQL Server的索引推荐问题,但做法有些不同,感觉有点像“一鱼多吃”。这篇论文可以当做是上一篇论文的延伸阅读。上一篇论文提到,优化器在进行代价模型估计的时候其实会犯各种各样的错误,这也造成一个索引的创建很有可能适得其反的引入性能回退,那么有没有一种不依赖优化器的索引推荐方式呢?论文就尝试使用机器学习的方法来对“好”索引和“坏”索引进行判断,由于测试场景有限,这种依赖机器学习算法的推荐方式的通用性,我们还不太确定,但机器学习算法作为优化器的补充或是替代这个方向还是值得继续关注。

12. Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations

说过Oracle和微软,总要提一下IBM。相比较而言,IBM似乎对DB2已经不太上心了,C Mohan把主要的精力都投入了区块链的研究。不过这篇来自IBM Almaden实验室——System-R这个现代关系数据库的鼻祖产品的发源地的论文还是一篇比较纯粹的在传统数据库领域做研究的文章,研究的核心问题也是数据库用户比较关心的问题——索引的空间占用问题。建索引是传统数据库优化的重要手段。随着数据库负载复杂化,越来越多的索引被创建,系统空间的使用也越来越多,对用户来说,这是一笔不小的成本开销。针对这个问题,学术界过去提出了几种不同的优化思路,一个方向是以用户的空间或者存储预算作为约束,对保留哪些索引进行选择以及优化;另外一个思路是从数据结构上对索引进行压缩和裁剪,使单个索引的空间利用率更高。本文的作者在这里提供了一个新的思路,这个思路就是利用在数据库中经常存在的数据键的关联性(correlation)——也就是文中所称的数据间的“软依赖”——来综合多个索引的数据存储。论文的思路是通过一个叫做“TRS-TREE”的数据结构,建立相关联的数据在一定范围内的映射,从而减少了冗余数据的存储。由于数据关联性往往是近似或者模糊的,这样的索引查询数据往往带有假阳性(false positive),因此,最终结果还需要在原始表中进行再次验证才能返回给用户。数据库中的数据关联性也是一个经常被研究的特性,例如数据关联性对优化器的影响等问题,这篇论文也为数据关联性的应用提供了一个全新的思路。

研究领域四:数据库与其他技术的结合与应用

13. FITing-Tree:A Data-aware Index Structure

Learned Index是AI+System的热门方向,利用AI统计实际数据的规律来设计更加高效的索引结构。前两年Google Jeff Dean团队提出了一种Learned BTree Index,不过这个结构有一个明显的缺陷:对插入和更新不友好。FITing-Tree的思路看起来更接地气一些,它也是一个BTree结构,中间节点和传统BTree相同,但叶子节点不存储全量,只存储数据段(Segment)的范围,而如何划分数据段是通过机器学习统计的方法实现的。

14. Fast General Distributed Transactions with Opacity

这篇论文讲的是如何通过RDMA新硬件优化分布式事务,实现透明可扩展。2015年有一篇相关论文,叫做“No compromises:distributed transactions with consistency,availability,and performance”,这篇论文的工作更进一步。其中,这篇论文提到了一个使用Marzullo算法实现全局时钟同步的做法,不依赖原子钟等硬件,服务器之间的时钟误差大约在6毫秒左右,和Google Spanner系统中的TrueTime有共同之处,可以用来实现分布式系统的租约机制。

15. Towards Scaling Blockchain Systems via Sharding

区块链的一大难题在于可扩展性,无论是公有链还是联盟链,区块链的每个节点都必须存储全量数据,每个事务都要求多数节点提交。这篇文章想要解决可扩展性问题,但解决方案并不是通用的。它做了一个基本假设:区块链里面的说谎的节点不超过一定比例。接下来,就是如何把区块链sharding,使得每个shard之内说谎的节点不超过一定比例,并在这个假设的基础上优化PBFT算法。

总结

不光是传统的数据库大厂将战场选在了数据库云化,一些中小型的数据库服务商也开始在云服务市场发力,例如历史悠久的列存储数据库MonetDB,这两年就把研究重心放到了云服务版本的开发上;而一些新兴的数据库引擎,例如近几年备受关注的分析数据库厂商Snowflake,则干脆直接基于云服务的运行环境进行开发,直接跳过了on-premise的产品形态,同样得到了市场的高度认可,这些都是数据库市场正在进行重构的显著信号。

值得一提的是,尽管Gartner的报告旗帜鲜明的指出“云”是数据库市场的未来,报告中也明确的提到了一种称为“数据库斯德哥尔摩综合综合征”的现象——即建立在传统本地数据库服务架构之上的企业,虽然看到了云服务化的优势和趋势,在面临选择时仍然可能出于规避风险的考虑继续使用本地的数据库服务,整个企业面向云化转型的周期也会非常之长——他们就像是被绑架了的人质,小心翼翼的维系和传统数据库解决方案(绑架者)的“锁链”。因此,尽管云数据库市场发展迅猛,但要真正将传统企业用户争取过来,云数据库服务商们还需要做好打持久仗的准备。从这个角度来讲,大家都还有机会