干货！阿里云AnalyticDB MySQL如何打造极致RuntimeFilter能力

阿里云数据库 2023-01-16

847

1.RuntimeFilter

1.1 什么是RuntimeFilter

RuntimeFilter是通过等价关系传递动态生成的filter condition以减少参与Join计算数据量的方法，在业界有广泛应用。

图1

RuntimeFilter优化生效的流程如下：

1. 根据查询的Join Condition，生成一条动态过滤条件传递规则：决定生产者（生成过滤条件的子查询）和消费者（应用过滤条件进行过滤的子查询）。

2. 先执行生产者，用实时结果集动态构建一个RuntimeFilter Object。

3. 将这个RuntimeFilter Object传递给消费者。

4. 消费者使用RuntimeFilter Object进行过滤，从而提前减少后续参与计算的数据量。通常情况下，消费者可以利用RuntimeFilter Object在数据进行分布式shuffle之前提前过滤掉部分数据，从而减少网络传输的数据量。更极端情况下，RuntimeFilter Object还可能下推到存储端命中索引裁剪，直接减少TableScan的磁盘扫描数据量。

RuntimeFilter Object的过滤原则是属于True Negative范畴，并不保证能把所有无关数据提前过滤掉。业界常见的RuntimeFilter Object包括MinMax Filter、InSet Filter、Bloom Filter等，它们的构建成本、内存占用大小以及单次查找耗时都远小于HashBasedJoin计算使用的HashTable，这是RuntimeFilter可以在Join之前预先粗过滤的根本。

1.2 RuntimeFilter的难点

接下来本文将从创建RuntimeFilter传递规则、RuntimeFilter Object传递以及RuntimeFilter Object的生成和使用三个方面来展开介绍整个RuntimeFilter技术的难点。

▶︎ 1.2.1 如何选择RuntimeFilter Object的生产者以及对应的消费者们

RuntimeFilter是一个在执行时，由生产者产生传递给消费者消费的过滤条件。在广义定义下，每条数据链路上的计算节点，都可以作为RuntimeFilter的生产端，通过上下左右的等值条件传递到RuntimeFilter的消费端。下左图是一个全联通的Bushy Tree Inner Join Graph (Join条件都相同)，每个子查询都生产一个RuntimeFilter；下右图中，黑线表示数据流，Join的执行依赖于Probe和Build的数据流；橙线表示信息流，如5和6可以互相生成和消费RuntimeFilter。

图2

在实际的实现中，我们往往不会生成这样的全联通依赖关系，一方面这会产生循环依赖，不可能全部生效；另一方面生产和消费RuntimeFilter本身都有开销，我们应该选择其中开销更低收益更大的。这包含了以下三个方面的问题：

1.选择有价值的生产者，能快速生成有很好过滤效果的RuntimeFIlter。

2.选择最根部的消费者们，最大化这个RuntimeFilter在整个SQL执行层面的过滤效果。

3.生产者和消费者的关系不能形成循环依赖。

▶︎ 1.2.2 RuntimeFilter Object如何在分布式执行框架中传递

前面我们在介绍RuntimeFilter Object的时候，只是简单把它描述成了一个单一逻辑实体。实际情况下，由于常见的分布式MPP数据库执行引擎具备单机&多机并行能力的，上一节中我们在执行计划图里描绘的一个逻辑RuntimeFilter Object可能是由N个机器节点上的M*N个内存对象共同构成的。这使得RuntimeFilter Object在生产者和消费者之间的传播关系变得非常复杂，这种传播关系打破了SQL执行引擎原有的自底向上数据传播模式。

RuntimeFilter Service是业界最常见的RuntimeFilter Object传递实现，包括Impala、Doris等。这种实现思路是在Coordinator节点（前端节点）上起一个专门的服务，负责接收所有生产者生成的partial RuntimeFilter Object，执行RuntimeFilter Object合并，再广播发给消费者。

▶︎ 1.2.3 RuntimeFilter Object的高效生成和使用

RuntimeFilter Object的实现有多种选择，用来表示生产端的结果集，常见的几种实现以及适用场景如下表：

以上这些RuntimeFilter Object有各自倾向使用的场景，需要系统预估生产者的结果集情况来决定构建哪种类型。然而在真实的SQL运行环境中，消费者侧的数据分布情况、波动的系统负载以及机器硬件水平，都会对最优选择策略产生影响。

对于消费端来说，它一定程度上依赖生产端产生的RuntimeFilter Object，所以消费者会有等待生产者完成的逻辑，当然这不是硬性的等待逻辑，最差就是消费者放弃使用RuntimeFilter加速。这中间主要是看系统对消费者侧的等待策略，系统可以在消费者等待的时间段暂停消费者数据流上的Task下发，也可以是系统立即下发了TaskTask但是Task内部逻辑把自己阻塞住。最后从整个SQL最后的响应时间来说，消费者如何等待生产者会有很多trade off场景，消费者死等生产者并不一定是最优的选择。

2.Sideways Information Passing框架（SIP）

ADB SIP框架是一种SQL执行时的信息收集传递框架，传递的信息可以是数据特征、统计信息也可以是一个临时内存表。一个抽象的SIP框架，不需要感知它收集、传递的信息具体内容或类别，只需要具备收集发送对应的运行时信息能力，Session淘汰能力，以及最优的信息传递链路搭建能力。

2.1 SIP传递的运行时信息概念

运行时信息由类型和粒度来定义，与信息的发布订阅者无关，是对信息本身的一个描述。

类型：信息的类型，比如RowCount/Ndv/Histogram/HashSet/MagicSet等。
粒度：在分布式计算引擎中，数据通过一定的算法划分为不同的分片并行执行。在执行中，每个算子可以获取一个部分的统计信息，如果是传递给具有相同分布属性的算子，可以直接利用分片的统计信息进行一些优化；如果是传递给不同分布属性的算子，或全局的优化器、调度器等模块，就需要讲所有信息聚合在一起生成全局的信息。分片、全局描述的就是信息的粒度。

为了减少重复生产的开销，信息具备以下2个特征：

1.可被推导：基于同一个结果集的信息，支持复杂向简单推导，比如HashSet可以推导Histogram和Ndv。

2.可被复用：相同的信息可以被不同订阅者订阅，数据只产生一次，可以被消费多次。

比如下图的查询，Agg在运行中生成一个HashSet，即可以作为SIP信息传给左表进行SemiJoin减少TableScan的数据扫描量，又可以推导出Histogram并作为Radix HashJoin算法调整的输入选择Hash Builder的切片大小。

图3

这对我们的实现有三个要求，一是需要定义不同信息类型之间的推导关系，二是定义了发布订阅者的关系是一对多的关系，三是需要有一个信息生命周期的管理，所有订阅者都消费后再进行数据清理。

2.2 SIP框架的组成概念

整个框架由发布者、订阅者、管道三部分组成。信息的发布者是某个算子或者优化器，在执行中进行信息的收集并发布给管道。管道是一个中心化的模块，有一个管理器，进行发布订阅关系的管理和匹配，在接收到来自发布者的信息后，决定发给哪个或哪些消费者；管道还有一个服务模块进行信息的数据接收、处理、分发。订阅者可以是算子、优化器、调度器等，根据应用场景的由规则自定义。

图4

▶︎ 2.2.1 发布者（Publisher）

生成信息有一定的开销，我们希望利用已有算子算法的一些特征，在不打断算子流水线计算的同时，以最小的代价进行运行时信息收集。根据算子算法特征的不同，不同类型的信息生成方式各有不同。

1.所有算子可以产生Basic统计信息 - 算子作为执行流水线的组成，在根据其语义进行内存申请和计算时，可以以忽略不计的开销产生一些基础统计信息，如RowCount。

2.某些算子可以产生Derived统计信息 - 比如Hash Agg和Hash Builder Operator，计算过程中就需要生成Hash Table，我们可以直接用这个Hash Table构建出Hash Set，或推导出Histogram和Ndv。

3.可以通过插入算子产生Derived统计信息 - 然而并不是所有算子都会构建Hash Table。我们单独定义了一个InfoCollectOperator，可在不能复用已有算子收集统计信息时用来专门收集统计信息。

▶︎ 2.2.2 订阅者（Subscriber）

根据应用场景的不同，信息的订阅者可以有多种形式。目前我们的应用中包括算子、优化器、调度器。优化器的不同模块中可能有多个订阅者，分别订阅来自不同发布者的不同信息。在执行时，订阅者对发布者有一个信息流的弱依赖。订阅者在整个流水线中有一个阻塞的作用，一般情况下，订阅者会等待收到信息并决策后再继续流水线执行；但由于我们传递的信息是用来调优的，在异常情况下如果超时没有收到信息，为不影响查询整体的响应时间，需要有短路的机制取消阻塞继续执行。

▶︎ 2.2.3 管道（Channel）

管道分为两个模块。

1.管道管理器 - 负责构建逻辑桥梁和进行信息管理，在执行前决定发布订阅者的对应关系，在执行中指导收到的运行时信息该发去哪及何时清理。

2.管道服务 - 负责构建数据传输的物理桥梁，在不同节点之间进行信息的传递，由管理器决定传给哪个节点的哪个。

3.AnalyticDB RuntimeFilter实现

AnalyticDB MySQL（简称ADB）是支持高并发低延时查询的新一代云原生数据仓库，高度兼容MySQL协议以及SQL:92、SQL:99、SQL:2003标准，可以对海量数据进行即时的多维分析透视和业务探索。ADB融合了数据库、大数据技术于一体，支持高吞吐的数据实时增删改、低延时的实时分析和复杂ETL混合负载，兼容上下游生态链路工具，用于构建企业级报表系统、数据仓库和数据服务引擎。

3.1 基于全局等价关系的生产者-消费者的关系发现

在多数业界实现中，RuntimeFilter的生效范围是一个Join的sub-graph维度而不是整个query维度（如上图2中RTF5，只在Node2这个Join的sub-graph生效，即消费者只是Node5；而在全局维度看，如果Join-0和Join-2的条件相同，RTF5至少还可以被Node1消费）。这是因为传统的RuntimeFilter应用于星型模型或者雪花模型，经常在不同的维度进行Join，全局区别于子查询的更多可优化场景较少。而在实践中，存在着更多复杂查询场景，还是有很多通过全局传递可优化的场景。如TPC-DS的Q24，item表经过filter后的结果集可以通过传递用来过滤两张大表store_returns和store_sales。基于TPC-DS的99条query，我们调研了全局等价关系的应用场景：支持全局维度相比仅支持join子查询维度，仅看RuntimeFilter可生效个数来说，有23%的扩展 (620 vs 798)。

这种通过全局等价关系使RuntimeFilter有更多应用场景的思路类似于Data/Join-Induced Predicates (DIP)中的全局思想。DIP通过数据分布特征(data statistics/data layout)和Join列全局等价关系的传导，在计划阶段决定分区裁剪，来减少计算数据量。我们这里的全局等价关系不局限于通过数据分布特征决定分区裁剪，而是应用于广义的RuntimeFilter。

3.2 基于SIP框架的RuntimeFilter Object订阅发布

ADB的RuntimeFilter Object统一都是通过SIP框架来进行发布订阅的。如下图5所示，SIP框架通过信息的共享、合并、短路三种手段降低了整个RuntimeFilter Object分布式传递的开销，在高并发在线查询场景下大大降低了RuntimeFilter Object传播对QPS和RT的影响。

1.共享：SIP支持一个信息被多个订阅者共享，这个信息只需要产生一次并传递一次到coordinator节点，如果订阅者在同一个计算节点也只需要传递一次。

2.合并：多个信息如果同时产生，我们通过信息合并，在节点间传递时只发送一次网络请求，从而减少网络连接。

3.短路：当信息粒度为分片，即不需要全局信息时，我们直接在节点内部通过传递给对应订阅者短路节点间传递的网络开销。