定义
Thomas H. Cormen 《算法导论》一书中对分而治之有详细且专业的定义：将原问题分解为几个规模较小的但类似于原问题的小问题，递归的求解子问题，然后再合并这些子问题的解来建立原问题的解。人们将这类算法称为：Divide and Conquer Algorithm，分治法。
Divide: the problem into a number of subproblems that are smaller instances of the same problem.
Conquer: the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
Combine: the solutions to the subproblems into the solution for the original problem.
分解（Divide）：将原问题分割为若干相同的较小的子问题。解决（Conquer）：通过递归方式求解子问题；若子问题规模足够小，则直接求解。合并（Combine）：将子问题的解整合为原问题的解。
Join
两表 join 是关系型数据库常见和重要的操作，nested loop join（NLJ）是所有 join 算法中最基本的一种，大多数关系型数据库都支持。虽然它的执行效率并不高，但是其多表连接思想是最朴实的。
假设有两张表R和S，NLJ 会通过两次循环的方法扫描每个(r, s)对，如果行r 和行s 满足join的条件，就输出之。显然，其时间复杂度为O(R * S)。
来自：Join Processing in Relational Databases
基于NLJ 而来的 Block Nested-Loop Join（BNLJ）算法，通过分块处理机制显著优化 NLJ 算法的性能瓶颈。其设计核心体现了分治法（Divide and Conquer）的“分解、求解、合并”思想。
BNLJ 的思路不再是逐行处理，而是将表 R 和表S 划分为若干个数据块 (block)，并将这些块数据放在内存中进行连接、判断操作，从而实现一次读取一块的数据，不再是一行一行判断，从而显著提供查询速度。这样就可以将时间复杂度从O(R * S)降低到O(R/m * S/n)，其中m、n 分别代表R和S 快数量。
来自：《Eficient Join Algorithms For Large Database Tables in a Multi-GPU Environment》
BNLJ分治思想如下：
分解：将表数据划分为适合join 内存大小的数据块。例如一个100万行的表，如果一个块能容纳1000行，就会被分成1000个块，执行次数减少1000倍。
解决：对每个数据块，执行两表的扫描和匹配操作。这里每个子问题的处理方式与原问题一致（都是join操作），但规模更小。
合并：各个数据块与连接操作的完成，会产生多个子结果集，将这些子结果集进行汇总，最终得到两个表连接的完整结果集。
这个过程就如同把各个工作小组完成的子任务成果进行整合，形成最终完整的项目成果 。
除了NLJ 连接算法，数据库三大连接中算法中 Hash Join、Sort Merg Join的优化算法也体现了分而治之的思想，具体可以参考 跟着论文学习数据库5：Join
SIMD
SIMD(Single Instruction Multiple Data)，即单指令流多数据流，一种充分利用现代CPU多核、多线程能力的新数据处理方式。传统关系型数据库（Oracle、MySQL、Postgres）处理数据模型被称为火山模型或者迭代模型。
数据库执行 SQL 时生成一棵查询树，在查询树的每个节点被抽象成一个操作符（Operator）迭代器，操作符通过 open() 、next()、close() 三个接口进行控制和数据管理，从而形成控制流从上往下，数据向下向上。
火山模型流程图
火山模型好处是处理逻辑清晰，操作符的模块化、松耦合也能实现良好的扩展性。但它的缺点也比较明显，迭代器中的next() 接口函数每次只处理一个元组（tuple），并不能充分利用现代 CPU 的超标量流水线的乱序执行、大缓存、SIMD 等特性。更多关于查询执行模式的信息可以参考 跟着论文学习数据库8：查询执行模型
单指令单数据和单指令多数据示意图
为了解决火山模式的问题，数据库工程师们提出了向量模型（Vectorized Model）。与火山模型不同的是，向量模型中迭代器 next() 函数由每次迭代处理一个元组（tuple）变成以数组（又称向量）的形式处理一批元组，从而提高数据库数据处理能力。如上图所示。
发表于2002年的《Implementing Database Operations Using SIMD Instructions》论文中，最先提出将SIMD应用于数据库的操作符，包括filter（过滤）、projection（投影）、aggregation（聚合）等数据库算子提升数据库性能。
SIMD的分治思想：
分解：将数据集由逐条处理分割为符合SIMD寄存器大小的数组的形式处理，比如将1kb数据，按数组形式分割，实现数据的批处理。
解决：对每个数组应用相同的向量化指令进行并行计算，这里每个数组的处理方式与原数据处理一致，但每个数组相比整个数据集规模更小。
合并：将每个迭代器中的向量计算结果记录，并在最后一次向量计算中完成结果合并。
对于OLAP和计算密集型程序来说，经常需要对大量不同数据进行同样的运算，更适合通过列式存储，而列式存储的一大特点就是局部性、顺序存储、同类数据。Clickhouse 数据库的成功告诉大家，使用SIMD计算进行数据库引擎的向量化执行，可以做到数据级别的并行计算，实现数据量级的性能提升。
Parallel
数据库的 parallel 并行计算是指通过利用多个服务器、多个处理器、处理器中的多核以及多指令集等技术，实现数据库任务的并行化处理，从而加快任务处理的速度。但要注意的是，并行计算的有并没有提高单位资源的使用效率，而是通过提高单位时间使用更多的的资源，实现性能的提升。
它基本的思路是计算下推，将尽可能多的计算分发到多个 worker 上并行完成，由单一服务串行执行变为并行多个worker 同时执行。对于 shared nothing 和shared disk 两种不同架构的，下推的方式有所不同。对于SD架构，对于数据的分片是逻辑而非物理的，每个worker 都可以看到全量的表数据；而对于SN架构，每个 worker 只能看到自己分片的数据，一般会采用简单的 scatter-gather 执行模式，通常只有一个 plan slice，由多个 worker 完成相同功能并将结果返回汇总层。
Parallel的分治思想：
分解：将一个大任务有一个work 执行分割为多个worker 同时进行。
解决：对每个worker 用相同的逻辑进行计算，
合并：将子任务每个worker结果整合为最终结果集。
PostgreSQL 从 9.6 开始支持并行顺序扫描、聚合，在11 版本后支持了更多的并行算子：并行哈希连接、Append、创建索引等，相关参数有：max_parallel_workers、max_parallel_workers_per_gather、parallel_tuple_cost 、parallel_setup_cost 等
MySQL 直到在 8.0.14 版本才中第一次引入了并行查询特性，相关参数有innodb_parallel_read_threads、parallel_query_threads、slave_parallel_workers、innodb_ddl_threads 等。这两个开源数据库中的翘楚，也都应用了 SMP 线程级并行处理技术提升数据库的单节点处理性能，但 PG 相对来说比 MySQL 走的更快。
总结
可以说，分而治之思想计算机领域中处理复杂问题的重要设计理念。通过将复杂计算任务或大规模数据集进行合理拆分，转化为多个可独立处理的子问题，再由不同计算单元对这些子问题并行求解，最终将各子结果整合为完整输出的高效处理模式，形成 "分解、解决、合并" 的逻辑。本文简单介绍了表Join、SIMD、Parallel 等场景下的分治思想。
作者介绍
司马辽太杰，10余年数据库架构和运维管理经验，擅长常见关系型、NoSQL、MPP 等类型数据库。业余热爱历史、足球，读点闲书。欢迎关注个人公众号“程序猿读历史”。有需要联系的可以从公众号上扫码加我好友，感谢。
