在現代數據庫管理系統（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），這屬于并行執行中的協調開銷，而不是分區本身導致了索引查找的低效。