简介：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右表打算行数；而为了获得理想的过滤率，缩小误判率p，ADB PG应用了PG高版本Bloom Filter的思路，设计Bloom FIlter大小Bytes为n的2倍，即总体n:m达到1:16。在这个设计下，能够计算失去最佳的k取值为11，p(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自适应调度。

原文链接
本文为阿里云原创内容，未经容许不得转载。