StoneDB 源碼解讀系列｜查詢模塊流程及源碼介紹——StoneDB 優(yōu)化器
StoneDB 源碼解讀系列文章正式開啟，預(yù)計以周更的形式跟大家見面，請多多支持~
本篇源碼解讀內(nèi)容已進行直播分享，可在視頻號觀看直播回放，也可點擊閱讀原文跳轉(zhuǎn)至 B 站觀看回放視頻。
PPT內(nèi)容可在社區(qū)論壇中查看下載：https://forum.stonedb.io/t/topic/93
StoneDB 采用基于知識網(wǎng)格技術(shù)和列式存儲引擎。該存儲引擎為海量數(shù)據(jù)背景下 OLAP 應(yīng)用而設(shè)計，通過列式存儲數(shù)據(jù)、知識網(wǎng)格過濾、高效數(shù)據(jù)壓縮等特性，為應(yīng)用系統(tǒng)提供低成本和高性能的數(shù)據(jù)查詢支持。本文主要圍繞 StoneDB 引擎的查詢模塊，包括：查詢模塊結(jié)構(gòu)圖、查詢流程、知識網(wǎng)格等展開。
StoneDB 架構(gòu)圖
查詢模塊結(jié)構(gòu)圖
SQL模塊（Query Layer）
SQL Parser
? ? ? ?解析器的主要作用是解析SQL語句，最終生成語法樹。解析器會對SQL語句進行語法和語義分析，如果有錯誤，則返回相應(yīng)的錯誤信息。檢查通過后，解析器會查詢緩存，如果緩存中有對應(yīng)的語句和查詢結(jié)果，則直接返回結(jié)果，不進行接下來的優(yōu)化和執(zhí)行步驟。
Optimizer
? ? ? ?優(yōu)化器的主要作用是對SQL語句進行優(yōu)化，包括選擇合適的索引，數(shù)據(jù)的讀取方式，生成代價最小的執(zhí)行計劃。
Execute
? ? ? ?執(zhí)行器的主要作用是判斷操作的表是否有權(quán)限，如果有權(quán)限，會根據(jù)表的存儲引擎定義，調(diào)用接口去讀取數(shù)據(jù)，最后返回滿足條件的查詢結(jié)果。
Filter
粗糙集過濾，找到可能包含的包。
DPN evaluation
根據(jù)DPN迭代判斷包里面每條是否滿足。
decompress
分片并行解壓粗糙過濾后命中的包。
知識網(wǎng)格模塊（Knowledge Grid）
? ? ? ?知識網(wǎng)格是由數(shù)據(jù)包節(jié)點和知識節(jié)點組成的。由于數(shù)據(jù)包都是壓縮存放的，所以數(shù)據(jù)讀取解壓的代價比較高，在查詢中如何做到讀取盡量少的數(shù)據(jù)包是提升效率的關(guān)鍵。知識網(wǎng)格正是起到了這樣的一個作用，它能夠有效的過濾查詢中不符合條件的數(shù)據(jù)，以最小的代價定位以數(shù)據(jù)包為最小單位的數(shù)據(jù)。知識網(wǎng)格的數(shù)據(jù)大小只占數(shù)據(jù)總量的1%以下，通常情況下可以加載到內(nèi)存中，進一步提升查詢效率。
? ? ? ?對于大部分統(tǒng)計、聚合性查詢，StoneDB 往往只需要使用知識網(wǎng)格就能返回查詢結(jié)果，這是因為通過知識網(wǎng)格可以消除或大量減少需要解壓的數(shù)據(jù)包，降低 IO 消耗，提高查詢響應(yīng)時間和網(wǎng)絡(luò)利用率。例如：數(shù)據(jù)包節(jié)點記錄了最大值、最小值、平均值、總和、總記錄數(shù)、null 值的數(shù)量，如果想對某個列做聚合運算，那么知識網(wǎng)格就能根據(jù)這些元數(shù)據(jù)很快的得到結(jié)果，而無需再解壓訪問底層的數(shù)據(jù)包。
數(shù)據(jù)包節(jié)點（Data Pack Node）
? ? ? ?數(shù)據(jù)包節(jié)點也稱為元數(shù)據(jù)節(jié)點（Metadata Node），因為數(shù)據(jù)包節(jié)點記錄了每個數(shù)據(jù)包中列的最大值、最小值、平均值、總和、總記錄數(shù)、null 值的數(shù)量、壓縮方式、占用的字節(jié)數(shù)。每一個數(shù)據(jù)包節(jié)點對應(yīng)一個數(shù)據(jù)包。
知識節(jié)點（Knowledge Node）
? ? ? ?數(shù)據(jù)包節(jié)點的上一層是知識節(jié)點，記錄了數(shù)據(jù)包之間或者列之間關(guān)系的元數(shù)據(jù)集合，比如值數(shù)據(jù)包的最小值與最大值的范圍、列之間的關(guān)聯(lián)關(guān)系。大部分的知識節(jié)點數(shù)據(jù)是裝載數(shù)據(jù)的時候產(chǎn)生的，另外一部分是查詢的時候產(chǎn)生的。
查詢流程圖
查詢流程大致步驟如下：
Client 連接
? ? ? ?與數(shù)據(jù)庫建立連接，此過程遵循 MySQL5.6、5.7 的連接協(xié)議。
SQL Parser
? ? ? ? 對 SQL 語句進行語法和語義分析。
解析入口：
StoneDB Optimizer
? ? ? ?對 SQL 語句進行優(yōu)化，生成代價最小的執(zhí)行計劃。
優(yōu)化函數(shù)：
知識網(wǎng)格
? ? ? ?StoneDB 在執(zhí)行查詢的時候會根據(jù)知識網(wǎng)絡(luò)（Knowledge Grid）把 DP 分成三類：
相關(guān)的 DP（Relevant Packs），滿足查詢條件限制的 DP
不相關(guān)的 DP（Irrelevant Packs），不滿足查詢條件限制的 DP
可疑的 DP（Suspect Packs），DP 里面的數(shù)據(jù)部分滿足查詢條件的限制
入口函數(shù)：
獲取DN：
命中之后，解壓相關(guān)包。
主函數(shù)：
返回結(jié)果集。
主函數(shù)：
知識網(wǎng)格
?知識網(wǎng)絡(luò)總覽圖
知識網(wǎng)格由數(shù)據(jù)元信息節(jié)點 (MD) 和知識節(jié)點 (KN) 組成，?通過知識網(wǎng)格，StoneDB 引擎無需通過傳統(tǒng)數(shù)據(jù)索引、數(shù)據(jù)分區(qū)、預(yù)測、手動調(diào)優(yōu)或特定架構(gòu)等方式就能高速處理復(fù)雜的分析查詢。?
元信息節(jié)點(MD)
數(shù)據(jù)元信息節(jié)點 (MD) 與數(shù)據(jù)節(jié)點 (DN) 之間保持 1:1 關(guān)系，元信息節(jié)點中包含了其對應(yīng)數(shù)據(jù)塊中數(shù)據(jù)的相關(guān)信息：
數(shù)據(jù)聚合函數(shù)值 (MIN，MAX，SUM，AVG 等)。
記錄數(shù)量 (count)。
數(shù)據(jù)中的 null 記錄標記。
元信息節(jié)點在數(shù)據(jù)裝載的時候就會構(gòu)建，MD 為數(shù)據(jù)壓縮， 聚合函數(shù)即席查詢等技術(shù)提供了支持。
知識節(jié)點 (KN) 除了基礎(chǔ)元數(shù)據(jù)外，還包括數(shù)據(jù)特征以及更深度的數(shù)據(jù)統(tǒng)計信息。
知識網(wǎng)格存儲在內(nèi)存中，方便快速查詢。
數(shù)據(jù)結(jié)構(gòu)：
獲取DPN：
知識節(jié)點(KN)
Column Metadata 包含了該列的數(shù)據(jù)類型定義，約束條件等基礎(chǔ)信息。
主類：
FieldRange 是一個標識數(shù)據(jù)節(jié)點 (DN) 中記錄值范圍段的標識 Map。針對數(shù)值類型的記錄 (date/time， integer，decimal…)，F(xiàn)ieldRange 可以用來快速確認當前對應(yīng) DN 是否包含所需數(shù)據(jù)。FieldRange 的組成：
從 MD 中獲取數(shù)據(jù)塊的 MAX 與 MIN，并將 MAX-MIN 劃分為固定段(例如1024)。
每個段中分別使用1個 bit 標識是否有記錄存在于該范圍內(nèi)。
Char Map 是一個記錄字符是否匹配的 Map。針對字符類型的記錄(char，varchar等)，CharMap 可以快速確定當前 DP 是否包含所需數(shù)據(jù)。
統(tǒng)計當前 DN 內(nèi)，1-64 長度中 ASCII 字符是否存在的標識值。
字符檢索時，按照字符順序，依次對比字符標示值即可知道該 DN 是否包含匹配數(shù)據(jù)。
join nodes
在 Join 查詢時自動創(chuàng)建，以關(guān)系位圖的形式，存儲 Join 操作中關(guān)聯(lián) DataNode 的信息。
存儲在 Session 中，僅對當前 Client 生效。
顯著提高Join查詢性能。減少無效 DN 掃描，避免無用 IO 的產(chǎn)生。
distributions
統(tǒng)計當前 Column 中各記錄的值分布信息。
基于統(tǒng)計信息，和粗糙集 (RoughSet) 計算，提供近似查詢支持 (Approximate Query)。
以上是本文全部內(nèi)容。
