在现代数据库管理系统（DBMS）中，并行执行是实现高性能和高可用性的核心策略之一。它允许数据库系统利用多核CPU和多个存储设备，同时处理多个任务或单个复杂任务的多个部分，从而显著提升数据处理能力。

并行执行的好处

并行执行为数据库系统带来了多方面的显著优势。

性能提升

• 吞吐量（Throughput） ：系统在单位时间内可以处理更多查询和数据，即每秒运行的查询数量更多。
• 延迟（Latency） ：单个查询的执行时间可以大幅缩短，因为任务可以同时进行。这对于需要快速响应的应用程序尤为重要。
• 响应性与可用性提升 ：并行执行使得系统即使在某个线程因等待磁盘I/O而阻塞时，其他线程也能继续运行，处理内存中的数据，从而保持系统的活跃和响应速度。
• 潜在的总拥有成本（TCO）降低 ：通过更有效地利用硬件资源，系统可以在更少的硬件上完成更多工作，减少硬件采购、软件许可、部署劳动力和能源消耗等总成本。这意味着购买拥有更多核心的新机器时，数据库系统可以充分利用其优势。

并行数据库与分布式数据库的区别

虽然并行数据库和分布式数据库都旨在通过跨多个资源分布数据库来提高性能，但它们之间存在关键的区别，本课程主要关注并行数据库。

并行数据库（Parallel DBMS）

• 资源物理位置 ：资源（如CPU、磁盘）彼此物理距离非常近。例如，同一机架单元内的机器，或具有多个CPU插槽的服务器。
• 通信方式 ：资源之间通过高速、高带宽的内部互连（如CPU插槽之间的互连）进行通信。
• 通信假设 ：通信被认为是快速、廉价且可靠的，消息不会丢失或乱序。

分布式数据库（Distributed DBMS）

• 资源物理位置 ：资源可以彼此相距很远。例如，在同一数据中心的不同机器，或位于全球不同地区的服务器。
• 通信方式 ：资源之间通过较慢且不可靠的通信通道（如公共广域网）进行通信。
• 通信假设 ：通信成本和潜在问题（如消息丢失、延迟）必须被考虑和处理。

对于应用程序而言 ：无论是并行数据库还是分布式数据库，都应向应用程序呈现为单个逻辑数据库实例。这意味着SQL查询在任何一种系统上都应该产生相同的结果，并且无需重写应用程序或SQL语句。

数据库进程模型

DBMS的进程模型定义了系统如何组织其内部结构，以支持来自多用户应用程序的并发请求。一个“工作者（worker）”是DBMS中负责执行任务并返回结果的组件，它可以是进程或线程。

历史上和当前存在三种主要的进程模型。

方法一：每个工作者一个进程（Process per DBMS Worker）

这是最基本的方法，每个工作者都是一个独立的操作系统（OS）进程。

优点 ：如果某个工作者进程崩溃，通常不会导致整个系统崩溃，提高了系统的弹性。在早期（1970-1990年代），由于缺乏标准的线程API，这种方法在不同操作系统上的可移植性更好，因为fork和join是通用的OS原语。

缺点/挑战

• 进程开销大 ：OS进程的创建和上下文切换开销（context switch overhead）比线程高得多。
• 共享数据复杂 ：每个进程通常有独立的内存地址空间，若要共享全局数据结构（如缓冲池），需要操作系统提供的共享内存机制（shared memory）来协调，这增加了复杂性。

示例：IBM DB2、Postgres（早期版本）、Oracle等老旧系统。

方法二：进程池（Process Pool）

这是“每个工作者一个进程”方法的延伸。系统维护一个预先创建好的工作者进程池，当有新的连接或请求到来时，调度器（dispatcher）从池中分配一个空闲进程来处理。

优点 ：避免了为每个新连接即时fork进程的开销。池中的进程可以更好地协同工作，实现一定程度的查询并行性。

缺点 ：仍然依赖OS调度器和共享内存机制。可能对CPU缓存局部性（cache locality）不利，因为一个连接的后续请求可能由不同的进程处理。

示例 ：IBM DB2、Postgres（2015年切换到此模型）。

方法三：每个工作者一个线程（Thread per DBMS Worker）

这是现代DBMS最常见的做法，整个数据库系统运行在一个单独的OS进程中，而工作者由进程内部的多个线程表示。

优点

• 开销小 ：线程的创建和上下文切换开销远低于进程。
• 共享数据简便 ：所有线程共享同一地址空间，简化了全局数据结构（如缓冲池）的访问和管理，无需复杂的共享内存机制。
• DBMS更精细的调度控制 ：DBMS可以自己管理线程调度，对任务的执行有更细粒度的控制，因为它可以全局了解所有任务和可用资源。

缺点 ：一个线程的崩溃可能导致整个DBMS进程的崩溃，因此要求代码质量极高。

示例 ：IBM DB2、Microsoft SQL Server、MySQL、Oracle（2014年）。

重要提示 ： 采用多线程架构并不意味着DBMS自动支持查询内并行（intra-query parallelism） 。例如，MySQL 5.7是一个多线程DBMS，但其本身不能将单个查询分解为多个线程并行执行（此功能可能在8.0版本中得到改进）。

查询内并行（Intra-Query Parallelism）

查询内并行旨在通过并行执行单个查询的操作来提高其性能，这对于长时间运行的分析型查询（OLAP）特别有用。

查询计划中的操作符可以被视为生产者/消费者模型：一个操作符（生产者）生成数据，并将其传递给其上方的操作符（消费者）。并行化算法适用于所有关系型操作符。

有三种主要的查询内并行方法。

方法一：算子内并行 / 水平并行（Intra-Operator / Horizontal Parallelism）

概念 ：将单个操作符分解成多个独立的执行片段（fragments），每个片段在不同的线程上并行地处理输入数据的不同子集。例如，对于一个扫描操作符，可以有多个扫描实例在不同线程上并行扫描表的不同部分。

核心机制：Exchange Operator

• DBMS会在查询计划中人工插入一种特殊的“交换操作符（Exchange Operator）”来协调和合并子操作符的结果。
• 发明者 ：由发明 Volcano 迭代器模型和 B+ 树书籍的 Goetz Graefe 提出。
• 类型 ：

Gather（汇聚） ：将来自多个工作者的结果合并成一个单一的输出流。这是最常见的类型，因为查询的最终结果通常需要汇聚成一个单一的输出返回给应用程序。

Repartition（重新分区） ：根据数据的值重新组织多个输入流，并将它们分发到多个输出流。这允许DBMS在数据已经按某种方式分区后，根据需要重新分区数据。

Distribute（分发） ：将单个输入流拆分成多个输出流，通常用于将数据分发给多个工作者进行并行处理。例如，在 Grace Hash Join 的构建阶段，可以将单个输入流分发到不同的哈希桶。

方法二：算子间并行 / 垂直并行 / 流水线并行（Inter-Operator / Vertical / Pipelined Parallelism）

概念 ：不同的操作符在独立的线程中同时运行，通过“流水线”的方式将数据从一个阶段直接传递到下一个阶段，而无需中间结果的物化（materialization）。

工作原理 ：下游操作符（消费者）在收到上游操作符（生产者）发出的元组后立即开始处理，形成一个数据流动的管道。例如，一个 Join 操作符的输出可以立即作为 Projection 操作符的输入。

应用场景 ：这种方法在流处理系统（如Spark Streaming、Apache Flink）中广泛使用，也适用于数据库系统。

方法三：Bushy 并行（Bushy Parallelism）

概念 ：可以视为算子间并行的一种扩展。它允许工作者同时执行查询计划中不同分支（或“灌木状”结构）的多个操作符。

特点 ：通常在查询计划包含多个独立的Join操作时体现，每个 Join 可以由不同的工作者并行执行，然后通过 Exchange 操作符汇聚结果。

以上三种并行方法并非互斥， DBMS 可以根据查询、硬件和数据特点，组合使用这些技术以达到最佳性能。

I/O 并行：解决磁盘瓶颈

如果磁盘 I/O 成为主要瓶颈，那么仅仅增加 CPU 核心和线程并不能提升性能，甚至可能因为多个工作者同时争抢磁盘资源而使情况恶化。因此，为了充分利用并行计算能力，需要实现 I/O 并行。

I/O 并行化的基本思想是将数据库系统的数据和文件分散存储在多个存储设备上。

多磁盘并行（Multi-Disk Parallelism）

概念 ：通过操作系统或硬件配置，将DBMS的文件存储在多个物理存储设备上。

实现方式 ：可以通过存储设备（Storage Appliances）或 RAID（Redundant Array of Independent Disks，独立磁盘冗余阵列） 配置来实现。

RAID

• RAID 0 (Stripping - 条带化) ：数据被分成块，并以轮询（round-robin）方式写入不同的磁盘。这提高了I/O吞吐量，但没有冗余。
• RAID 1 (Mirroring - 镜像) ：每个数据块都在至少两个磁盘上保存完整的副本，提供数据冗余。读取性能可以并行化，但写入成本较高。

透明性 ：对DBMS是透明的。DBMS感知不到底层是多个磁盘，因此它无法基于底层磁盘布局来优化查询计划。

数据库分区（Database Partitioning）

概念 ：DBMS主动将数据分解成不相交的子集，并将其分配给不同的磁盘位置。与RAID不同， DBMS知道数据的分区方式和物理位置 。

优点 ：缓冲池管理器（Buffer Pool Manager）知道页的磁盘位置，因此可以智能地进行I/O调度。

理想状态 ：分区对于应用程序应该是透明的。应用程序访问逻辑表，无需关心数据具体存储在哪里。

两种主要分区方法

• 垂直分区（Vertical Partitioning）

概念 ：将表的属性（列）存储在不同的物理位置（如不同的文件或磁盘卷）。类似于列式存储，但可能不具备列式存储的所有优化（如压缩、列式查询执行）。

实现 ：需要存储元组ID信息，以便在查询时将不同列的数据重新组合成完整的记录。

适用场景 ：当查询通常只访问表的少数几列时，可以减少I/O量。

• 水平分区（Horizontal Partitioning）

概念 ：将表的元组（行）根据某个分区键（partitioning key）分成不相交的段，并存储在不同的分区中 。这通常被称为 分片（sharding） ，尽管在并行数据库中更多是指单机内的数据分布。

实现方式 ：可以通过哈希分区（Hash Partitioning）、范围分区（Range Partitioning）或谓词分区（Predicate Partitioning）等方式实现。

优势 ：当查询只需要访问特定元组时，可以直接定位到包含该元组的分区进行I/O操作。多个工作者可以同时并行地操作不同的分区，从而提高I/O效率。

关于索引（B+树）的影响 ：在水平分区下， DBMS知道每个元组属于哪个分区 。因此，当进行索引查找（如B+树）时，系统可以根据查询条件中的分区键，直接确定目标元组可能存在的分区，然后只在该分区（对应的磁盘）上进行查找。这意味着 不需要进行“系统内查找所有分区”的操作 ，而是可以精准定位。B+树等索引在并行环境中面临的挑战更多是并发控制方面（如闩锁抢占和耦合 latch crabbing/coupling），这属于并行执行中的协调开销，而不是分区本身导致了索引查找的低效。