全文将围绕以下几方面展开：
- 项目背景
- 技术方案
- 优化与诊断
- 效果及展望
01 项目背景
1. ClickHouse执行模式
ClickHouse 的执行模式相对比较简单，和Druid、ES 类似，其基本查询模式分为两个阶段：
第一阶段，Coordinator 收到查询后将请求发送给对应的 worker 节点；
第二阶段，Coordinator 收到各个 worker 节点的结果后汇聚起来处理后返回。
以下面的SQL为例：
Select name from student_distribute where id = 5
①当 Coordinator 收到请求后，由于student_distribute是一个分布式表，因此需要将SQL 改写为对local表查询，并转发请求给每一个shard的worker；
②Worker收到请求后查询本地的local表数据，返回结果给coordinator；
③Coordinator汇总每一个shard的数据并把结果返回给client。
Select name from student_local where id = 5
第二阶段执行的模式能够高效地支持很多常见场景，比如常见的针对大宽表的各类查询，但是随着业务场景的复杂化，也存在以下三点问题：
其一，第一阶段返回的数据比较多且第二阶段的计算比较复杂时，对于Coordinator的压力会比较大，容易成为query的瓶颈，且shard越多可能计算越慢，瓶颈越大。例如一些重计算的agg算子count distinct。如果我们使用hash表去重时，第二阶段需要在coordinator单机上merge各个worker的hash表，计算量很重且不能并行；又比如说group by基数比较大或者window计算。
其二，join是SQL的重要场景。由于不支持Shuffle操作，对于Join来说右表必须是全量数据。无论是普通Join还是Global Join，当Join的右表比较大时都放到内存里容易OOM，而Spill到磁盘虽然解决内存问题，可能会因为有磁盘 io和序列化计算的开销影响性能。特别是当Join为最常见的Hash Join 时，右表如果是大表构建也比较慢。虽然社区最近也做了一些右表构建的优化，通过单机按照 join key split 来达到并行构建hash table。但是额外的代价是左右表都增加了一次 split 操作。
其三，对于复杂查询（如多表 Join、嵌套多个子查询、window function等）的支持并不友好，由于不能通过shuffle来分散数据，生成的pipeline在一些case下不能充分并行，难以充分发挥集群的全部资源。
2. 其他MMP数据库
目前主流的MPP数据库基本都支持Stage执行的方式。以Presto为例，如下图所示，一个两表join的agg sql可拆分为5个 Stage。
其中 Stage3、Stage4分别对应左右表数据读取，Stage2完成两表Join和partial agg 计算，Stage1完成final agg计算，Stage0收集Stage1的数据后汇总和输出。在这个过程中，Stage 3、4、2、1可以在多个节点上并行执行，单个复杂的query被拆分成若干Stage，从而实现了Stage之间，不同worker的数据传输。
3. 业务背景和目标
随着业务复杂程度提高，业务并不希望所有的数据都通过etl 产生大宽表；复杂查询（特别是多轮分布式 Join和比较多的agg）的需求越来越强烈，而整体的数据量又在不断增长。在集群资源有限的情况下，我们希望能够充分利用机器资源，基于ClickHouse 高效地支持复杂查询。
ByteHouse是字节跳动研发同学基于开源ClickHouse 进行了深度优化和改造的版本，提供海量数据上更强的查询服务和数据写入性能，支持多种应用场景。如图所示，ByteHouse在内部多个场景如行为分析、画像分析、智能营销分析、APP 日志分析上得到充分的验证和使用，并在多个方面进行了增强，具备特有的能力。
02 技术方案
1. 设计思想
基于 ClickHouse 的复杂查询的实现采用分Stage的方式，替换目前 ClickHouse的两阶段执行方式。类似其他分布式数据库引擎（如 Presto、Impala 等），将一个复杂的Query按照数据交换情况切分成多个Stage，Stage和Stage之间通过 exchange完成数据的交换，单个Stage内不存在数据交换。Stage间的数据交换主要有以下三种形式：
①按照单（多）个 key 进行 Shuffle（shuffle）
②由1个或者多个节点汇聚到一个节点（我们称为 gather）
③同一份数据复制到多个节点（也称为 broadcast 或者说广播）
按照不同的功能切分不同的模块，设计目标如下：
①各个模块约定好接口，尽量减少彼此的依赖和耦合。一旦某个模块有变动不会影响别的模块，例如Stage生成逻辑的调整不影响调度的逻辑。
②模块采用插件的架构，允许模块根据配置灵活支持不同的策略。
2. 相关术语
- ExchangeNode 在语法树中表示数据交换的节点
- PlanSegment 单个 Stage 对应的执行的计划片段
- ExchangeManager 管理数据的 exchange，负责不同 Stage 节点之间的数据交换
- SegmentScheduler 计划片段调度器，负责下发计划片段给 worker，由 Coordinator 节点调用
- InterpreterPlanSegment 计划片段执行器，执行一个具体的计划片段
3. 执行流程
①Coordinator 接受复杂查询后，在目前 ClickHouse 语法树的基础上，根据节点类型和数据分布情况插入 Exchange 节点并生成分布式 Plan。
②Coordinator 根据 Exchange Node 类型，切分分布式 Plan 生成每个 Stage 的执行片段 PlanSegment。
③Coordinator 调用 SegmentScheduler 将各阶段的 PlanSegment 发送到 Worker 节点。
④Worker 节点接受 PlanSegment 通过 InterpreterPlanSegment 完成数据的读取和执行，通过 ExchangeManager 完成数据的交互。
⑤Coordinator 从最后一轮 Stage 对应节点的 ExchangeManager 读取数据后处理后返回给 client。
4. Plan切分
下面是一个Plan切分的例子，这是1个2表Join的查询场景，根据Exchange信息，将整个分布式 Plan切分成4个Stage。
5. 查询片段调度器（SegmentScheduler）
查询片段调度器SegmentScheduler 根据上下游依赖关系和数据分布，以及 Stage 并行度和worker 分布和状态信息，按照一定的调度策略，将 PlanSemgent 发给不同的 Worker 节点。
目前支持的2种策略是：
①依赖调度：根据 Stage 依赖关系定义拓扑结构，产生 DAG 图，根据 DAG 图调度 stage，类似于拓扑排序，等到依赖的 Stage 启动后再启动新的 Stage。例如刚才的两表 join，会先调度左右表读取 stage，再调度 join stage。
②AllAtOnce：类似于Presto的AllAtOnce策略，会先计算每一个 Stage 的相关信息，一次性调度所有的Stage。
相比而言，这两种策略是在容错、资源使用和延时上做取舍。
第一种调度策略可以实现更好的容错，由于 ClickHouse 可以有多个副本，当前一个 Stage 部分节点连接失败时可以尝试切换到副本节点，对后续依赖 stage 无感知。这里指的是读数据的 Stage，我们称为 Source Stage，非 Source Stage 因为没有数据依赖，容错能力会更强，只要保证并行度的节点数即可，甚至极端情况下可以降低 stage 并行度来支持更好的容错。缺点是调度有依赖，不能完全并行，会增加调度时长，对于一些数据量和计算量小，但是 stage 多的节点调度延时可能会占 SQL 整体时间不小的比例。我们也做了一些针对性的优化，对于无依赖关系的尽可能支持并行。
第二种调度策略通过并行可以极大降低调度延时，为防止大量网络 io 线程，我们通过异步化并且控制线程数目；这种策略的缺点是容错性没有依赖调度好，因为每一个 stage 的 worker 在调度前就已经确定，如果有一个 worker 出现连接异常则整个查询会直接失败。并且可能有一些 Stage 上游数据还没有 Ready 就被调度执行了，需要长时间等数据。例如 final agg stage，需要等 partial agg 完成后才能拿到数据。虽然我们做了一些优化，并不会长时间空跑浪费 cpu 资源，但是毕竟也消耗了一部分资源，比如创建了执行的线程。
6. 查询片段执行器（InterpreterPlanSegment）
下面介绍下计划片段是如何执行的，原本 ClickHouse的查询和节点执行主要是 SQL 形式，切分Stag后需要支持执行一个单独的PlanSemgent。因此 InterpreterPlanSegment 的主要功能就是接受一个序列化后的 PlanSemgent，能够在 Worker 节点上运行整个 PlanSemgent 的逻辑。主要的步骤为：
①根据 input 信息读取数据，如果 input 是具体的 table，则从本地读取数据；如果 input 是一个 exchange input，则从对应的 ExchangeManager 读取数据；
②执行 PlanSemgent 的逻辑；
③输出处理后的结果数据，如果是 Coordinator 节点，就将数据发给 Client；如果是非Coordinator 节点，就按照数据的exchange方式写给本实例对应的 ExchangeManager。
Interpreter部分我们尽量复用当前ClickHouse的执行逻辑，例如processor 执行方式，process list管理等等。相比于InterpreterSelect逻辑要更简单一些，可以认为1 个Stage只有1个阶段。当然我们也做了很多功能和性能的增强，例如我们支持1个 stage处理多个join等，这样可以减少stage数目和不必要的数据传输，在一张大表（通常情况下是事实表） join 多个维度表的场景有比较好的帮助。
InterpreterPlan Segment执行完会向coordinator上报对应的状态信息。执行异常的时候会将异常信息报告给查询片段调度器，取消Query其他worker的执行。
7. 数据交换（ExchangeManager）
ExchangeManager是PlanSegment数据交换的媒介，更是平衡数据上下游处理能力的重要组件。整体上采用 push 的方式，当上游数据 ready 时主动推送给下游，并支持反压。其架构如下图所示：
具体的流程如下：
①下游PlanSegment执行时，当input为exchange input时，根据一定的 token 规则 （通常由 query_id+segment_id+index_id 等组成）和数据 source 信息，向上游 ExchangeManager 注册对应的数据请求；
②上游ExchangeManager收到请求后，建立上下游数据通道，并将上游的数据推送到下游，如果通道一直建立不了会 block 上游的执行。
在这个过程中，上下游都会通过队列来优化发送和读取，当队列饱和的时候通过反压的机制控制上游的执行速度。由于采用了 push 和队列，这里我们要考虑一个特殊的场景，在某些 case 下下游的 Stage 并不需要读取全部的上游数据，一个典型的场景是 limit。例如 limit 100，下游 stage 是需要读取 100 条数据即可，而上游可能会输出更大规模的数据，因此在这种情况下，当下游 stage 读到足够的数据后，需要能主动取消上游数据的执行并清空队列。这是一个特定场景的优化，能够大大加速查询时间。
ExchangeManager 需要考虑和优化的点还有：
①细粒度的内存控制，能够按照实例、query、segment 多层次进行内存控制，避免 OOM，更长期的考虑是支持 spill 到磁盘上，降低对内存的使用。为了提升传输效率，小数据需要进行 merge，大数据要 split。同时，网络处理在某些场景要保证有序性，比如 sort 时，partial sort 和 merge sort 的网络传输必须有序，否则数据可能是有问题的。
②连接复用和网络优化，包括针对上下游在同一个节的场景下选择走内存的交换不走网络，可以减少网络的开销和减少数据序列化、反序列化的代价。另外，由于 ClickHouse 在计算方面做了非常充足的优化，有些场景下甚至内存带宽成为瓶颈，我们在ExchangeManager的一些场景上也应用zero copy等技术来减少内存的拷贝。
③异常处理和监控，相比于单机执行，分布式情况下异常情况更复杂且不好感知。通过重试能避免一些节点的暂时高负载或者异常，以及出问题时能够快速感知、排查和做针对性解决和优化。这里的工程实践更多一些。
03 优化与诊断
1. Join 多种实现
根据数据的规模和分布，我们支持了多种Join实现，目前已经支持的有：
①Shuffle Join，最通用的 Join；
②Broadcast Join，针对大表Join小表的场景，通过把右表广播到左表的所有 worker 节点来减少左表的传输；
③Colocate Join，针对左右表根据Join key保持相通分布的场景，减少左右表数据传输。
2. 网络连接优化
网络连接的优化的核心本质就是减少连接的使用。特别是数据需要Shuffle 的时候，下一轮 Stage的每一个节点需要从上一轮Stage的每一个节点拉取数据。当一个集群的节点比较多的时候，如果存在比较多的复杂 Query(Stage多，并行度（节点数）比较大)，集群的Worker节点会建立非常多的连接，如下图所示，单节点建立的连接数与集群节点数、并发stage数成正比。
字节内部的clickhouse集群规模非常大，最大的集群（单集群几千台规模）在目前 ClickHouse 的执行模式下单机最大可能会建立上几万个网络连接。因此如果支持复杂 Query 执行，由于stage变多了，需要优化网络连接，特别是支持连接复用。我们通过尽可能复用连接，在不同节点之间只会建立固定数目的连接，不同的查询会复用这些连接，不随 query 和 stage 的规模而增长。
3. 网络传输优化
在数据中心领域，远程直接内存访问（RDMA）是一种绕过远程主机操作系统内核访问其内存中数据的技术，由于不经过操作系统，不仅节省了大量CPU资源，同样也提高了系统吞吐量、降低了系统的网络通信延迟，尤其适合在大规模并行计算机集群中有广泛应用。
由于ClickHouse在计算层面做了很多优化，而网络带宽相比于内存带宽要小不少，在一些数据量传输特别大的场景，网络传输会成为一定的瓶颈。为了提升网络传输的效率和提升数据exchange的吞吐，一方面我们引入压缩来降低传输数据量，另一方面我们引入 RDMA 来减少一定的开销。经过测试，在一些数据传输量大的场景，有不小的收益。
4. Runtime Filter
Join算子通常是OLAP引擎中最耗时的算子。如果想优化 Join 算子，可以有两种思路，一方面可以提升Join算子的性能，例如更好的Hash Table实现和Hash算法，以及更好的并行。另一方面可以尽可能减少参与Join计算的数据。
Runtime Filter在一些场景，特别是事实表join维度表的星型模型场景下会有比较大的效果。因为这种情况下通常事实表的规模比较大，而大部分过滤条件都在维度表上，事实表可能要全量join维度表。Runtime Filter的作用是通过在 Join 的 probe 端（就是左表）提前过滤掉那些不会命中Join的输入数据来大幅减少 Join 中的数据传输和计算，从而减少整体的执行时间。以下图为例：
左表并没有直接过滤条件，右表带有过滤条件item.proce > 1000。当完成右表查询时，可以确定item.id 的范围和集合，根据join类型inner join和join条件sales.item_id=item.id可以推断出sales.item的范围和集合。我们可以把sales.item 的范围和集合作为一个过滤条件，在join前过滤sales的数据。
我们在复杂查询上支持了Runtime Filter，目前主要支持minmax和bloomfilter。
总体执行流程如下：
①build plan segment worker（right table）会将生成的单节点 runtime filter 发送到coordinator节点；
②coordinator 在等待各个 worker的 runtime filter 都发送完成之后进行一次merge操作，将合并好的 runtime filter 分发到各个 execute plan segment worker（left table）节点中去；
③在 runtime filter 构造期间，execute plan segment（left table） 需要等待一定的时间，在超时之前如果runtime filter已经下发，则通过 runtime filter 执行过滤。
这里需要思考一个问题，Runtime filter column 是否构建索引（主键、skip index等）和命中prewhere？如果runtime filter的列（join column）构建了索引是需要重新生成 pipeline 的。因为命中索引后，可能会减少数据的读取，pipeline并行度和对应数据的处理range都可能发生变化。如果runtime filter的列跟索引无关，可以在计划生成的时候预先带上过滤条件，只不过一开始作为占位是空的，runtime filter下发的时候把占位信息改成真正的过滤条件即可。这样即使runtime filter 下发超时了，查询片段已经开始执行了，只要查询片段没有执行完，之后的数据仍然可以进行过滤。
需要注意的是，runtime filter 是一种特殊场景下的优化，其针对的场景是右表数据量不大，且构建的 runtime filter 对左表有比较强的过滤效果。如果右表数据量比较大，构建runtime filter比较慢，或者对左表的数据过滤效果很差甚至没有，那么 runtime filter 反而会增加查询的耗时。因此，要根据数据的特征和规模来决定是否开启。
5. 诊断和分析
引入复杂查询的多Stage 执行模型后，SQL的执行模式变得复杂了。特别是当用户查询一些非常复杂的查询，几百行的sql生成的stage会非常多，把stage都看一遍并理解sql的含义要花比较长的时间。题外话：我们很早之前就完整的跑通了所有的tpcds query，这里面就有一些sql可能会产生几十个 stage。那么在这种情况下，如何定位 SQL 的瓶颈并加以优化是一个难题。
我们做了如下两点优化：
首先，最常见的做法是增加各类完善的metrics，包括整个Query的执行时间和不同Stage的执行时间、IO数据量、算子处理数据和执行情况、算子 metrics 和profile event等。
其次，我们记录了反压信息和上下游队列长度，以此来推断 stage 执行情况和瓶颈。
坦率地说，SQL 场景包括万象，很多非常复杂的场景目前还是需要对引擎比较熟悉的同学才能诊断和分析SQL才能给出优化建议。在不断积累经验的过程中，我们希望通过能够不断完善 metrics 和分析路径，不断减轻oncall的负担，并且在某些场景下可以更智能的给出优化提示，这对于使用同学来说也是有好处的。
04 效果及展望
1. 复杂查询效果
根据上面的执行模型的三个缺点，分别测试如下三个场景：
①第二阶段的计算比较复杂
②Hash Join 右表为大表
③多表 Join
以SSB 1T数据作为数据集，集群包含8个节点。
2. 第二阶段的计算比较复杂
这个case SQL 如下图所示
uniqExact是count distinct的默认算法，采用hash table进行数据去重。使用复杂查询后，query 执行时间从 8.514s=>2.198s，第二阶段 agg uniqExact 算子的合并原本由 coordinator单点合并，现在通过按照group by key shuffle 后可以由多个节点并行完成。因此通过shuffle减轻了coordinator的merge agg 压力。
3. Hash Join 右表为大表
这个 case 演示了右表是一个大表的场景，由于 ClickHouse 对多表的优化做的还不是很到位。这里采用子查询来下推过滤的条件。
在这个case中，采用复杂查询模式后，query 执行时间从17.210=>1.749s。lineorder 是一张大表，通过shuffle可以将大表数据按照join key shuffle到每个worker节点，减少了右表构建的压力。
4. 多表 Join
这个 case 是一个 5 表 join 的 case。
开启复杂查询模式后，query 执行时间从8.583s=>4.464s，所有的右表可同时开始数据读取和构建。为了和现有模式对比，针对复杂查询没有开启 runtime filter，开启 runtime filter后效果会更快。
这里还要重点说一下，今天的分享主要是从执行模式上讲解如何支持复杂查询。实际上，优化器对于复杂查询的性能提升也非常大。通过一些rbo的规则，比如常见的谓词下推、相关子查询处理等。实际上这里的优化规则非常多，可以极大的提升 SQL 的执行效率。上面的 SQL 其实原本比较简单，5 表 join 和一些维表的过滤条件，这里写成子查询是为了在 ClickHouse 现有模式下右表过滤条件更好下推。其实对于我们来说，在复杂查询的模式下，由于有优化器的存在，用户不用写的这么复杂，优化器会自动完成下推和rbo优化。
上面是一些规则的优化，实际上在复杂查询中， cbo 的优化也有很大作用。举一个例子，在 ClickHouse 中，相同的两个表，大表 join 小表的性能比小表 join 大表要好很多。前一个效果 2 中如果把表顺序调整一下会快很多；另外，选用哪一种 join 的实现对 join 性能影响比较大，如果满足 join key 分布，colcate join 比 shuffle join 来说完全减少了数据的 shuffle。多表 join 中，join 的顺序和 join 的实现方式对执行的时长影响会比 2 表 join 影响更大。借助数据的统计信息，通过一些 cbo 优化，可以得到一个比较优的执行模式。
有了优化器，业务同学可以按照业务逻辑来写任何的 SQL，引擎自动计算出相对最优的 SQL 计划并执行，加速查询的执行。
5. 展望
CLickHouse 目前的模式其实在很多单表查询的场景上表现优异。我们主要是针对复杂的查询场景做优化，主要是实现多stage的执行模式，并实现了stage之间数据传输。工程实践上来说，做了比较多的尝试和优化来提升执行和网络传输的性能，并且希望通过完善metrics和智能诊断来降低SQL分析和调优的门槛，并减少oncall 的压力。
目前的实现只是第一步，未来我们还有很多努力的方向。
首先，肯定是继续提升执行和 Exchange 的性能。这里不谈论引擎执行通用的优化，比如更好的索引或者算子的优化，主要是跟复杂查询模式有关。
其次是Metrics 和智能诊断加强，就如同刚才提到的，SQL 的灵活度太高了，对于一些复杂的查询没有 metrics 几乎难以诊断和调优，这个我们会长期持续的去做。
