爲什麼需要向量化執行引擎

前言

在一些前沿數據庫中，經常可以看到一個很火的詞彙——向量化執行引擎，比如 ClickHouse、DuckDB、Doris 等等，我對這個概念一直還停留在淺顯的理論層面，一直沒有機會深入，藉此機會，好好捋一捋這個高大尚的詞彙，什麼是向量化執行引擎。

傳統數據庫執行器

早期數據庫受限於硬件，內存和 CPU 等都十分昂貴，所以大多數數據庫執行器都採用傳統的火山模型，火山模型又稱 Volcano Model 或者 Pipeline Model，火山模型從最頂層的輸出節點開始，不斷從下層節點拉取數據，一種自頂向下的執行方式，所以也可以稱之爲拉取模型，Greenplum、PostgreSQL、MySQL 以及 Oracle 等主流數據庫均採用拉模型。最常見的拉模型是 Tuple-At-A-Time，即每次從下層拉取一個元組，這樣可以縮減內存使用量，但是這樣的話，CPU 的大部分處理時不是用來真正的處理數據，而是在遍歷查詢操作樹，CPU 有效利用率不高，同時這也會導致低指令緩存性能和頻繁跳轉。在火山模型中，一個查詢計劃會被分解爲多個代數運算符 (Operator)。每個 Operator 就是一個迭代器，都要實現一個 next() 接口，通常包括三個步驟：

  1. 調用子節點 Operator 的 next() ，獲取一個元組

  2. 對元組執行 Operator 特定的處理；

  3. 返回處理後的元組。

以 PostgreSQL 爲例：

可以看到，查詢樹每次調用 next() 接口從下層節點拉取一條元組，自頂向下嵌套調用 next() ，數據則自底向上地被拉取處理

但是爲什麼之前的數據庫設計者沒有去優化這方面呢？是他們沒想到嗎？怎麼可能？這個時候我們可能要考慮到 30 年前的硬件水平了，當時的 IO 速度是遠遠小於 CPU 的計算速度的，那麼 SQL 查詢引擎的優化則會被 IO 開銷所遮蔽（畢竟花費很多精力只帶來 1% 場景下的速度提升意義並不大）。

隨着硬件的不斷革新，硬件的能力早已不同往日，火山模型的弊端逐漸顯露。性能表現差強人意。當需要處理的數據量增大時，具有顯著的缺陷。搞懂了火山模型的缺點之後，現在來講爲什麼向量化模型能夠解決這個問題。鑑於火山模型每次處理一行一行數據，next 調用代價又比較高，那麼我們可以很自然地想到，有沒有辦法一次處理一批數據呢？這正是向量化模型的重要區別，每個 operator 仍然需要實現 next() 函數，但是每次調用 next() 函數返回的是一批元組，而不是一個元組，所以向量化模型也可稱爲批處理模型。

在提及向量化模型之前，我們還需要了解一下列存的概念，以及爲什麼向量化執行引擎必須要構架在列存儲的表上才能夠發揮出最大的優勢，列存之於向量化引擎，就好比王八看綠豆——看對眼了。列存，顧名思義，按照列進行存儲，一列數據存儲在一起

What is column storage and where are the features and scenarios? – HIGH-END  FPGA Distributor

這樣的好處不言而喻，類似的數據在進行壓縮的時候，能夠達到一個比較好的壓縮比，其次按列讀取，相對於行存將所有數據讀取上來再提取對應的屬性，可以減少 I/O 總量。另外因爲列存每列的各行數據存儲在一起，可以認爲這些數據是以數組或者向量的方式存儲的，基於這樣的特徵，當該列數據需要進行某一同樣操作 (做到取多條數據同時計算)，可以使用 SIMD 進一步提升計算效率，SIMD 的全稱是：Single Instruction Multiple Data，在一條指令中同時處理多個數據的技術叫做 SIMD。SIMD 指令在本質上非常類似一個向量處理器，可對控制器上的一組數據 (又稱 “數據向量”)  同時分別執行相同的操作從而實現空間上的並行。

如上圖所示：

經過多年的發展，支持 SIMD 的指令集有很多。各種 CPU 架構都提供各自的 SIMD 指令集，要判斷當前設備 CPU 的支持能力，在命令行通過 cat /proc/cpuinfo 在輸出中查看 flags 一項，看是否包含 avx、avx2 等。SIMD 指令需要硬件支持 MMX 系列，SSE (Streaming SIMD Extensions) 系列、AVX (Advanced Vector Extensions) 系列擴展指令集。目前大部分 CPU 都支持 AVX2，只有最新的 CPU 才支持 AVX512。

因此，向量化執行引擎就採用了這種思路，每次處理一批數據。向量化執行引擎能夠發揮效率的前提是數據是按列存儲的，基於行存模型去談向量化是不可能的。對於典型的 OLTP 點查場景，行存則更有優勢。

另外還有一種優化方式是採用 Push 模型，從最底層的節點起始，持續生成數據，並逐級將數據推送給上層節點。一般來說，每個處理節點都有兩個通道，一個入口，負責接收子節點的數據；一個出口，負責輸出給上層節點處理後的值。那麼每個處理節點（父子節點），都可以看做是一個生產者消費者模型。

對於消費者而言，有兩種方式獲取信息：

  1. 推模型 (push)：由消息中間件主動將消息推送給消費者；可以儘可能快地將消息發送給消費者，但是若消費者的處理消息的能力較弱（一條消息長時間處理），中間件會不斷地向消費者 push 消息，消費者的緩衝區可能會溢出；

  2. 拉模型 (pull)：由消費者主動向消息中間件拉取消息；會增加消息的延遲，即消息到達消費者的時間變長。

推模型比拉模型複雜，但 CPU 利用率要高於拉模型。由於子算子產生的結果會直接 Push 給父算子進行操作，Push 模型的 Context switch 相對較少，對 CPU Cache 的友好性也更強。但是使用推模型會不可避免的產生其他問題。如果使用拉模型，那麼使用一個進程就可以完成整個 SQL 的執行流程；但是換成推模型，每個節點都會自發運行往父節點推數據，那麼一個 SQL 就需要使用多個進程來完成，CPU 的利用率肯定是上去了，但是如果存在高併發場景，併發執行 SQL 量很多，那麼進程數也會暴增。

小結

  1. 火山模型，可以很容易實現輸出控制，比如 limit 返回 TopN 的時候，雖然被稱爲流水線方式，但是某些算子是會阻塞流水線的，也就是需要等到子節點完成所有數據的處理後才能繼續運轉，比如我們所熟知的 ORDER BY，子查詢等。另外火山模型處理邏輯清晰，每個 Operator 只要關心自己的處理邏輯即可，耦合性低。

  2. 向量化模型，通常用在 OLAP 數倉類系統，結合 SIMD，一次性處理一批數據，可以顯著提高查詢的執行效率。

甚好甚好，經過學習，對這些概念有了一些更加清晰的認知。

參考

PgSQL · 引擎介紹 · 向量化執行引擎簡介

PostgreSQL 技術內幕（十六）如何寫一個執行器算子？

【CMU 15-445/645 Database Systems】12 Query Processing - 01A

PgSQL 內核特性 - push-based pipeline 執行引擎

PieCloudDB 自研全新向量化執行器，帶來性能的數量級提升

向量化代碼實踐與思考：如何藉助向量化技術給代碼提速

向量化執行引擎是怎麼玩的？

SQL 優化之火山模型、向量化、編譯執行

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/GYirGddU0aeyL5E60daeog

猜你喜歡