卯兔科技西安网站建设,wordpress 微信 登录,做钻石资讯网站,泉州建站平台简介#xff1a;AnalyticDB for PostgreSQL(以下简称ADB PG)是一款PB级的MPP架构云原生数据仓库。本文从ADB PG架构设计的角度出发#xff0c;探讨Runtime Filter在ADB PG中的实现方案#xff0c;并介绍了基于Bloom Filter的ADB PG Dynamic Join Filter功能技术细节。 作者 …简介AnalyticDB for PostgreSQL(以下简称ADB PG)是一款PB级的MPP架构云原生数据仓库。本文从ADB PG架构设计的角度出发探讨Runtime Filter在ADB PG中的实现方案并介绍了基于Bloom Filter的ADB PG Dynamic Join Filter功能技术细节。 作者 | 宇毅 来源 | 阿里开发者公众号
前言
近年来数据库系统服务的数据量呈指数级增长同时也面临处理的业务需求愈发复杂、实时性要求越来越高等挑战。单机数据库系统已经逐渐不能满足现代的数据库服务要求因此分布式数据库/数据仓库得到了越来越广泛地运用。
在实时分析OLAP领域分布式数据仓库可以充分发挥系统的分布式特点将复杂的OLAP任务分解下发到系统中的所有节点进行计算提升分析性能分布式数据仓库也可以比较方便地对系统节点进行扩容应对用户业务数据量增加的需求。但是分布式数据仓库用户无法避免的一个问题是随着数据仓库集群规模增大扩容带来的性价比愈发降低。
造成这种现象的一个原因是表连接Join作为数据库业务中最广泛使用的算子之一在分布式计算中依赖系统节点间的数据交互当分布式集群规模增大时节点之间的数据交互代价会明显增加这种情况下非常考验分布式系统的网络处理能力并依赖用户的数据表设计和SQL编写能力以缓解数据交互压力。
针对这个问题业界不同的分布式数据库系统提出了不同的Join运行时过滤(Runtime Filter)算法。AnalyticDB for PostgreSQL(以下简称ADB PG)是一款PB级的MPP架构云原生数据仓库同样也面临着上述问题的挑战。本文从ADB PG架构设计的角度出发探讨Runtime Filter在ADB PG中的实现方案并介绍了基于Bloom Filter的ADB PG Dynamic Join Filter功能技术细节。
ADB PG架构简介
ADB PG基于开源项目Greenplum构建在单机PostgreSQL的基础上进行扩展将多个PG服务同时启动在单个或多个服务器上并组成集群以分布式的形式提供数据库服务。 ADB PG将每一个PG服务称为一个Segment并引入了Slice的概念。Slice用于解决分布式系统中的网络结构当数据库涉及到MPP多阶段计算时例如Hash Join左右表的Join Key不满足相同的Hash分布那么就需要对Join Key通过网络传输进行重分布ADB PG将网络传输的前后阶段切分为不同的Slices。以下是一个ADB PG集群示意图。 在这种架构下如何解决大规模集群下表连接Join的性能问题呢业界解决这个问题的一个方案是引入网络代理节点同一机器内的Segment将网络数据发送至本地代理节点由代理节点与其它机器上的代理节点进行网络收发工作以减少网络拥塞。该方案对ADB PG架构的挑战较大且没有从根本上减少Join的网络Shuffle开销。因此为了从Join根源上减少Join计算的数据量ADB PG设计并实现了Join Runtime Filter方案。
Runtime Filter和Bloom Filter
Runtime FIlter的目的是在Join计算前筛选掉一部分数据需要一个Filter的实现“载体”。在结合ADB PG的架构设计、存储层和网络层的特点后我们选择使用Bloom Filter作为Runtime Filter的实现形式。
Bloom Filter是一种概率数据结构通常被用于判断一个元素是否属于一个集合。Bloom Filter的优点是其空间效率非常高计算性能通常也高缺点是存在阳性误判率false positive但是不存在false negative即Bloom Filter判断一个元素是否属于集合的结果不是单纯的true or false而是possible true or false。 上图是一个标准Bloom Filter的计算思路示意图其中的0、1为Bloom Filter用于表示集合信息的bit array即每一位用一个bit存储。上方x,y,z表示向Bloom Filter中插入的三个元素分别使用3种hash算法计算hash值后在bit array中置位。而下方为判断元素w是否属于集合由于3个hash值中的某一位没有在bit array中被置位可以肯定的是w不属于集合。
Bloom Filter通常由以下几个参数描述
m --- Bloom Filter bit array的大小m bits k --- 使用的hash函数个数k p --- 误判率 n --- Bloom Filter插入的元素个数
我们省略推导过程直接将各个参数的关系给出 当Bloom Filter足够大时可以简化为 在设计Bloom Filter时n和m我们可以根据实际计算场景提前确定上述公式可以视为自变量为k应变量为p的函数p(k)此函数通常在k 0时通常不是单调的由n:m确定。因此Bloom Filter在设计时要考虑如何确定hash函数k的个数以获得最小的误判率p。根据上式可以计算得到当p为极小值时对应k的值为 Bloom Filter的参数设计
如何将Bloom Filter应用至ADB PG Join过滤优化我们首先要设计选择Bloom Filter的参数。对于Bloom Filter插入元素的个数n可以直接使用执行计划中获得的Join右表计划行数而为了获得理想的过滤率减少误判率pADB PG使用了PG高版本Bloom Filter的思路设计Bloom FIlter大小Bytes为n的2倍即总体n:m达到1:16。在这个设计下可以计算得到最佳的k取值为11p(k)函数如下图所示当k 11时可以取得最小的p 0.046% k 11意味着对于每一个元素都需要计算11个hash值以插入到Bloom Filter bit array中这对于ADB PG是无法接受的构建Bloom Filter的代价明显过大。在构建Bloom Filter时ADB PG会综合误判率、hash计算等因素考虑选择合适的k值。
在确定构建Bloom Filter的基本原则后接下来就是工程实现问题。Bloom Filter的工程实现非常简单高效通常我们可以直接使用bitset数组来建立Bloom Filter通过位操作实现Bloom Filter的插入和查找。下图为向一个Bloom Filter bitset数组中插入元素的计算示意图。 Dynamic Join Filter in ADB PG
在完成ADB PG Hash Join的Bloom Filter设计后接来下讨论如何将Bloom Filter应用至Join的Runtime Filter中。ADB PG将基于Bloom Filter的Runtime Filter命名为Dynamic Join Filter。
1 Dynamic Join Filter的实现方式
由于ADB PG优化器通常会选择将右表作为小表左表作为大表因此ADB PG将Dynamic Join Filter的设计特点为单向过滤的即仅用于右表过滤左表暂不考虑左表过滤右表的形式同时我们也可以将Dynamic Join Filter灵活应用于Hash Join左表链路不同算子的过滤中。 由于Hash Join的形式不同Dynamic Join Filter的实现形式可以总结为Local Join和MPP Join两种形式并根据Runtime Filter是否具有下推算子的能力做进一步区分。
Local Join
Local Join是指左右表的Join Key均满足相同Hash分布无需再Shuffle数据。此时Hash、Hash Join和左表Scan处于同一个Slice内部即同一个进程中我们可以直接在进程空间内将Bloom Filter传递给左表Scan算子过滤输出。 MPP Join
MPP Join是指左右表的Join Key均不满足相同Hash分布需要针对Join Key Shuffle数据。在前文介绍过ADB PG的Hash Join和Hash算子一定处于同一个Slice内部因此基于基本原则只需要考虑左表Shuffle的情况即左表在Hash Join前存在Motion的场景。 MPP Join存在的另一种情况是左表Motion下不是简单的Scan也没有关联信息将Join Key的Bloom Filter下推至Scan。那么以减少网络传输数据量为最后准则将Bloom Filter过滤放在Motion前减少Motion Sender的数据。 2 Bloom Filter网络传输
Dynamic Join Filter在各个计算节点上建立了一个Local Bloom Filter每个计算节点需要收集所有其它节点的Bloom Filter并在本地组成完整的Bloom Filter后才能开始过滤计算。我们将Bloom Filter的收发分为两种模式全量传输和位传输。在发送前我们可以判断两种模式的数据量大小并自适应选择数据量小的模式。 Bloom Filter全量传输 Bloom Filter位传输
性能测试
接下来我们对ADB PG Dynamic Join Filter的性能表现测试。测试集群为ADB PG公有云搭建的实例测试使用TPC-H 1TB测试集scale 10000测试通过开启\关闭Dynamic Join Filter功能对比执行性能。下图展示了TPC-H执行性能有差异的Query测试结果 可以看到Dynamic Join Filter在Q5、Q8、Q9和Q17上均获得了较大的性能提升其中Q17的优化性能最佳执行时间137s优化至8s。而Q10存在略微的性能回退10s回退至12s原因在于Q10的Join Key是完全匹配的Dynamic Join Filter无法做到动态提前过滤而优化器未能准确估算代价导致计划仍然使用了Dynamic Join Filter。此外Q20也因为优化器下推规则的的原因没有选择Dynamic Join Filter实际上经过分析Q20与Q17类似比较适合使用Dynamic Join Filter。为了解决这些问题ADB PG优化器相关功能仍在开发迭代中。
总结未来规划
Dynamic Join Filter根据ADB PG架构设计、存储层和网络层特点使用Bloom Filter作为Join Runtime Filter的实现形式在TPC-H测试中取得了明显的性能提升成果。未来我们将从以下几个方面做进一步的开发和优化提升客户使用体验
完善Dynamic Join Filter功能支持各种模式的Hash Join并进一步推广到Merge Sort Join、NestedLoop Join的优化中提升优化器的代价估算模型精度完善优化器下推规则Runtime Filter自适应调度。
原文链接
本文为阿里云原创内容未经允许不得转载。
