OLAP數(shù)倉(cāng)入門(mén)：進(jìn)階篇

未看過(guò)前一篇文章的讀者，歡迎做進(jìn)一步了解：

OLAP數(shù)倉(cāng)入門(mén)：基礎(chǔ)篇

01

有哪些類(lèi)型的OLAP數(shù)倉(cāng)？

1. 按數(shù)據(jù)量劃分

對(duì)一件事物或一個(gè)東西基于不同角度，可以進(jìn)行多種分類(lèi)方式。對(duì)數(shù)倉(cāng)產(chǎn)品也一樣。比如我們可以基于數(shù)據(jù)量來(lái)選擇不同類(lèi)型的數(shù)量，如下圖所示：

本系列文章主要關(guān)注的是數(shù)據(jù)量處于百萬(wàn)到百億級(jí)別的偏實(shí)時(shí)的分析型數(shù)倉(cāng)，Cloudera的Impala、Facebook的Presto和Pivotal的GreenPlum均屬于這類(lèi)系統(tǒng)；如果超過(guò)百億級(jí)別數(shù)據(jù)量，那么一般選擇離線數(shù)倉(cāng)，如使用Hive或Spark等（SparkSQL3.0看起來(lái)性能提升很明顯）；對(duì)于數(shù)據(jù)量很小的情況，雖然是分析類(lèi)應(yīng)用，也可以直接選擇普通的關(guān)系型數(shù)據(jù)庫(kù)，比如MySQL等，“殺雞焉用牛刀”。

這些系統(tǒng)均屬于網(wǎng)易杭研大數(shù)據(jù)和數(shù)據(jù)庫(kù)團(tuán)隊(duì)的研究范疇，對(duì)各系統(tǒng)均有深入研究和優(yōu)化，對(duì)外提供網(wǎng)易猛犸、網(wǎng)易有數(shù)和網(wǎng)易云RDS等服務(wù)。

2. 按建模類(lèi)型劃分

下面我們主要關(guān)注數(shù)據(jù)量中等的分析型數(shù)倉(cāng)，聚焦OLAP系統(tǒng)。根據(jù)維基百科對(duì)OLAP的介紹，一般來(lái)說(shuō)OLAP根據(jù)建模方式可分為MOLAP、ROLAP和HOLAP 3種類(lèi)型，下面分別進(jìn)行介紹并分析優(yōu)缺點(diǎn)。

MOLAP：

這應(yīng)該算是最傳統(tǒng)的數(shù)倉(cāng)了，1993年Edgar F. Codd提出OLAP概念時(shí)，指的就是MOLAP數(shù)倉(cāng)，M即表示多維（Multidimensional）。大多數(shù)MOLAP產(chǎn)品均對(duì)原始數(shù)據(jù)進(jìn)行預(yù)計(jì)算得到用戶可能需要的所有結(jié)果，將其存儲(chǔ)到優(yōu)化過(guò)的多維數(shù)組存儲(chǔ)中，可以認(rèn)為這就是上一篇所提到的“數(shù)據(jù)立方體”。

由于所有可能結(jié)果均已計(jì)算出來(lái)并持久化存儲(chǔ)，查詢時(shí)無(wú)需進(jìn)行復(fù)雜計(jì)算，且以數(shù)組形式可以進(jìn)行高效的免索引數(shù)據(jù)訪問(wèn)，因此用戶發(fā)起的查詢均能夠穩(wěn)定地快速響應(yīng)。這些結(jié)果集是高度結(jié)構(gòu)化的，可以進(jìn)行壓縮/編碼來(lái)減少存儲(chǔ)占用空間。

但高性能并不是沒(méi)有代價(jià)的。首先，MOLAP需要進(jìn)行預(yù)計(jì)算，這會(huì)花去很多時(shí)間。如果每次寫(xiě)入增量數(shù)據(jù)后均要進(jìn)行全量預(yù)計(jì)算，顯然是低效率的，因此支持僅對(duì)增量數(shù)據(jù)進(jìn)行迭代計(jì)算非常重要。其次，如果業(yè)務(wù)發(fā)生需求變更，需要進(jìn)行預(yù)定模型之外新的查詢操作，現(xiàn)有的MOLAP實(shí)例就無(wú)能為力了，只能重新進(jìn)行建模和預(yù)計(jì)算。

因此，MOLAP適合業(yè)務(wù)需求比較固定，數(shù)據(jù)量較大的場(chǎng)景。在開(kāi)源軟件中，由eBay開(kāi)發(fā)并貢獻(xiàn)給Apache基金會(huì)的Kylin即屬于這類(lèi)OLAP引擎，支持在百億規(guī)模的數(shù)據(jù)集上進(jìn)行亞秒級(jí)查詢。

其架構(gòu)圖較直觀得反映了基于cube的預(yù)計(jì)算模型（build），如下所示：

ROLAP：

與MOLAP相反，ROLAP無(wú)需預(yù)計(jì)算，直接在構(gòu)成多維數(shù)據(jù)模型的事實(shí)表和維度表上進(jìn)行計(jì)算。R即表示關(guān)系型（Relational）。顯然，這種方式相比MOLAP更具可擴(kuò)展性，增量數(shù)據(jù)導(dǎo)入后，無(wú)需進(jìn)行重新計(jì)算，用戶有新的查詢需求時(shí)只需寫(xiě)好正確的SQL語(yǔ)句既能完成獲取所需的結(jié)果。

但ROLAP的不足也很明顯，尤其是在數(shù)據(jù)體量巨大的場(chǎng)景下，用戶提交SQL后，獲取查詢結(jié)果所需的時(shí)間無(wú)法準(zhǔn)確預(yù)知，可能秒回，也可能需要花費(fèi)數(shù)十分鐘甚至數(shù)小時(shí)。本質(zhì)上，ROLAP是把MOLAP預(yù)計(jì)算所需的時(shí)間分?jǐn)偟搅擞脩舻拿看尾樵兩?，肯定?huì)影響用戶的查詢體驗(yàn)。

當(dāng)然ROLAP的性能是否能夠接受，取決于用戶查詢的SQL類(lèi)型，數(shù)據(jù)規(guī)模以及用戶對(duì)性能的預(yù)期。對(duì)于相對(duì)簡(jiǎn)單的SQL，比如TPCH中的Query響應(yīng)時(shí)間較快。但如果是復(fù)雜SQL，比如TPC-DS中的數(shù)據(jù)分析和挖掘類(lèi)的Query，可能需要數(shù)分鐘。

相比MOLAP，ROLAP的使用門(mén)檻更低，在完成星型或雪花型模型的構(gòu)建，創(chuàng)建對(duì)應(yīng)schema的事實(shí)表和維度表并導(dǎo)入數(shù)據(jù)后，用戶只需會(huì)寫(xiě)出符合需求的SQL，就可以得到想要的結(jié)果。相比創(chuàng)建“數(shù)據(jù)立方體”，顯然更加方便。

有分析表明，雖然ROLAP的性能比如MOLAP，但由于其靈活性、擴(kuò)展性，ROLAP的使用者是MOLAP的數(shù)倍。

The survey shows that ROLAP tools have 7 times more users than MOLAP tools within each company

HOLAP：

MOLAP和ROLAP各有優(yōu)缺點(diǎn)，而且是互斥的。如果能夠?qū)烧叩膬?yōu)點(diǎn)進(jìn)行互補(bǔ)，那么是個(gè)更好的選擇。而HOLAP的出現(xiàn)就是這個(gè)目的，H表示混合型（Hybrid），這個(gè)想法很樸素直接。對(duì)于查詢頻繁而穩(wěn)定但又耗時(shí)的那些SQL，通過(guò)預(yù)計(jì)算來(lái)提速；對(duì)于較快的查詢、發(fā)生次數(shù)較少或新的查詢需求，像ROLAP一樣直接通過(guò)SQL操作事實(shí)表和維度表。

目前似乎沒(méi)有開(kāi)源的OLAP系統(tǒng)屬于這個(gè)類(lèi)型，一些大數(shù)據(jù)服務(wù)公司或互聯(lián)網(wǎng)廠商，比如HULU有類(lèi)似的產(chǎn)品。相信未來(lái)HOLAP可能會(huì)得到進(jìn)一步發(fā)展，并獲得更大規(guī)模的使用。

HTAP：

從另一個(gè)維度看，HTAP也算是一種OLAP類(lèi)型的系統(tǒng)，是ROLAP的一個(gè)擴(kuò)展，具備了OLAP的能力。最新發(fā)展顯示，有云廠商在HTAP的基礎(chǔ)上做了某種妥協(xié)，將T（transaction）弱化為S（Serving），朝HSAP方向演進(jìn)。關(guān)于HTAP/HSAP，本文不做進(jìn)一步展開(kāi)，可自主查詢其他資料。

主流的OLAP數(shù)倉(cāng)系統(tǒng)很多，包含上面所述的各種類(lèi)型，下圖是Gartner 2019 年發(fā)布的數(shù)據(jù)分析市場(chǎng)排名（數(shù)據(jù)來(lái)源）

可以發(fā)現(xiàn)，傳統(tǒng)的商業(yè)廠商和閉源的云服務(wù)廠商占據(jù)了絕大部分市場(chǎng)。大部分系統(tǒng)筆者只聽(tīng)過(guò)而沒(méi)有研究過(guò)。作為屁股在互聯(lián)網(wǎng)公司的數(shù)據(jù)庫(kù)/數(shù)據(jù)倉(cāng)庫(kù)開(kāi)發(fā)者，本文后續(xù)主要聚焦在基于Hadoop生態(tài)發(fā)展的開(kāi)源OLAP系統(tǒng)（SQL on Hadoop）。

02

有哪些常用的開(kāi)源ROLAP產(chǎn)品？

目前生產(chǎn)環(huán)境使用較多的開(kāi)源ROLAP主要可以分為2大類(lèi)，一個(gè)是寬表模型，另一個(gè)是多表組合模型（就是前述的星型或雪花型）。

1. 寬表模型

寬表模型能夠提供比多表組合模型更好的查詢性能，不足的是支持的SQL操作類(lèi)型比較有限，比如對(duì)Join等復(fù)雜操作支持較弱或不支持。

目前該類(lèi)OLAP系統(tǒng)包括Druid和ClickHouse等，兩者各有優(yōu)勢(shì)，Druid支持更大的數(shù)據(jù)規(guī)模，具備一定的預(yù)聚合能力，通過(guò)倒排索引和位圖索引進(jìn)一步優(yōu)化查詢性能，在廣告分析場(chǎng)景、監(jiān)控報(bào)警等時(shí)序類(lèi)應(yīng)用均有廣泛使用；ClickHouse部署架構(gòu)簡(jiǎn)單，易用，保存明細(xì)數(shù)據(jù)，依托其向量化查詢、減枝等優(yōu)化能力，具備強(qiáng)勁的查詢性能。兩者均具備較高的數(shù)據(jù)實(shí)時(shí)性，在互聯(lián)網(wǎng)企業(yè)均有廣泛使用。

除了上面介紹的Druid和ClickHouse外，ElasticSearch和Solar也可以歸為寬表模型。但其系統(tǒng)設(shè)計(jì)架構(gòu)有較大不同，這兩個(gè)一般稱(chēng)為搜索引擎，通過(guò)倒排索引，應(yīng)用Scatter-Gather計(jì)算模型提高查詢性能。對(duì)于搜索類(lèi)的查詢效果較好，但當(dāng)數(shù)據(jù)量較大或進(jìn)行掃描聚合類(lèi)查詢時(shí)，查詢性能會(huì)有較大影響。

2. 多表組合模型

采用星型或雪花型建模是最通用的一種ROLAP系統(tǒng)，常見(jiàn)的包括GreenPlum、Presto和Impala等，他們均基于MPP架構(gòu)，采用該模型和架構(gòu)的系統(tǒng)具有支持的數(shù)據(jù)量大、擴(kuò)展性較好、靈活易用和支持的SQL類(lèi)型多樣等優(yōu)點(diǎn)。

相比其他類(lèi)型ROLAP和MOLAP，該類(lèi)系統(tǒng)性能不具有優(yōu)勢(shì)，實(shí)時(shí)性較一般。通用系統(tǒng)往往比專(zhuān)用系統(tǒng)更難實(shí)現(xiàn)和進(jìn)行優(yōu)化，這是因?yàn)橥ㄓ孟到y(tǒng)需要考慮的場(chǎng)景更多，支持的查詢類(lèi)型更豐富。而專(zhuān)用系統(tǒng)只需要針對(duì)所服務(wù)的某個(gè)特定場(chǎng)景進(jìn)行優(yōu)化即可，相對(duì)復(fù)雜度會(huì)有所降低。

對(duì)于ROLAP系統(tǒng)，尤其是星型或雪花型的系統(tǒng)，如果能夠盡可能得縮短響應(yīng)時(shí)間非常重要，這將是該系統(tǒng)的核心競(jìng)爭(zhēng)力。這塊內(nèi)容，我們放在下一節(jié)著重進(jìn)行介紹。

03

有哪些黑科技用于優(yōu)化ROLAP系統(tǒng)性能？

目前生產(chǎn)環(huán)境使用的ROLAP系統(tǒng)，均實(shí)現(xiàn)了大部分的該領(lǐng)域性能優(yōu)化技術(shù)，包括采用MPP架構(gòu)、支持基于代價(jià)的查詢優(yōu)化（CBO）、向量化執(zhí)行引擎、動(dòng)態(tài)代碼生成機(jī)制、存儲(chǔ)空間和訪問(wèn)效率優(yōu)化、其他cpu和內(nèi)存相關(guān)的計(jì)算層優(yōu)化等。下面逐一進(jìn)行介紹。

1. 什么是MPP架構(gòu)？

首先來(lái)聊聊系統(tǒng)架構(gòu)，這是設(shè)計(jì)OLAP系統(tǒng)的第一次分野，目前生產(chǎn)環(huán)境中系統(tǒng)采用的架構(gòu)包括基于傳統(tǒng)的MapReduce架構(gòu)加上SQL層組裝的系統(tǒng)；主流的基于MPP的系統(tǒng)；其他非MPP系統(tǒng)等。

MR架構(gòu)及其局限：

在Hadoop生態(tài)下，最早在Hive上提供了基于MapReduce框架的SQL查詢服務(wù)。

但基于MR框架局限性明顯，比如：

• 每個(gè)MapReduce 操作都是相互獨(dú)立的，Hadoop不知道接下來(lái)會(huì)有哪些MapReduce。

• 每一步的輸出結(jié)果，都會(huì)持久化到硬盤(pán)或者HDFS 上。

第一個(gè)問(wèn)題導(dǎo)致無(wú)法進(jìn)行跨MR操作間的優(yōu)化，第二個(gè)問(wèn)題導(dǎo)致MR間數(shù)據(jù)交互需要大量的IO操作。兩個(gè)問(wèn)題均對(duì)執(zhí)行效率產(chǎn)生很大影響，性能較差。

MPP優(yōu)缺點(diǎn)分析：

MPP是massively parallel processing的簡(jiǎn)稱(chēng)，即大規(guī)模并行計(jì)算框架。相比MR等架構(gòu)，MPP查詢速度快，通常在秒計(jì)甚至毫秒級(jí)以內(nèi)就可以返回查詢結(jié)果，這也是為何很多強(qiáng)調(diào)低延遲的系統(tǒng)，比如OLAP系統(tǒng)大多采用MPP架構(gòu)的原因。

下面以Impala為例，簡(jiǎn)單介紹下MPP系統(tǒng)架構(gòu)。

上圖即為Impala架構(gòu)圖，展示了Impala各個(gè)組件及一個(gè)查詢的執(zhí)行流程。

• 用戶通過(guò)Impala提供的impala-shell或beeline等客戶端/UI工具向Impala節(jié)點(diǎn)下發(fā)查詢SQL；接收該SQL的Impala節(jié)點(diǎn)即為Coordinator節(jié)點(diǎn)，該節(jié)點(diǎn)負(fù)責(zé)進(jìn)行SQL解析；

• 首先產(chǎn)生基于單節(jié)點(diǎn)的執(zhí)行計(jì)劃；再對(duì)執(zhí)行計(jì)劃進(jìn)行分布式處理，比如將Join、聚合（aggregation）等并行化到各Impala Executor節(jié)點(diǎn)上。執(zhí)行計(jì)劃被切分為多個(gè)Plan Fragment（PF），每個(gè)PF又由一到多個(gè)Operator組成；

• 接著，下發(fā)經(jīng)過(guò)優(yōu)化后的執(zhí)行計(jì)劃的PF到對(duì)應(yīng)的Executor節(jié)點(diǎn)，多個(gè)執(zhí)行節(jié)點(diǎn)并行處理任務(wù)，縮短整個(gè)任務(wù)所需時(shí)間；

• 執(zhí)行節(jié)點(diǎn)掃描HDFS/Hbase等存儲(chǔ)上的數(shù)據(jù)，并逐層進(jìn)行處理，比如進(jìn)行跨節(jié)點(diǎn)的數(shù)據(jù)shuffe，Join等操作；

• 執(zhí)行節(jié)點(diǎn)完成任務(wù)并將輸出結(jié)果統(tǒng)一發(fā)送到Coordinator節(jié)點(diǎn)；

• Coordinator節(jié)點(diǎn)匯總各個(gè)執(zhí)行節(jié)點(diǎn)數(shù)據(jù)，做最后處理，最終返回給用戶想要的結(jié)果集。

MPP架構(gòu)之所以性能比MR好，原因包括：

• PF之間的數(shù)據(jù)交互（即中間處理結(jié)果）駐留在內(nèi)存Buffer中不落盤(pán)（假設(shè)內(nèi)存夠大）；

• Operator和PF間基于流水線處理，不需要等上一個(gè)Operator/PF都完成后才進(jìn)行下一個(gè)處理。上下游之間的關(guān)系和數(shù)據(jù)交互式預(yù)先明確的。

這樣可以充分利用CPU資源，減少I(mǎi)O資源消耗。但事情往往是兩面的，MPP并不完美，主要問(wèn)題包括：

• 中間結(jié)果不落盤(pán)，在正常情況下是利好，但在異常情況下就是利空，這意味著出現(xiàn)節(jié)點(diǎn)宕機(jī)等場(chǎng)景下，需要重新計(jì)算產(chǎn)生中間結(jié)果，拖慢任務(wù)完成時(shí)間；

• 擴(kuò)展性沒(méi)有MR等架構(gòu)好，或者說(shuō)隨著MPP系統(tǒng)節(jié)點(diǎn)增多到一定規(guī)模，性能無(wú)法線性提升。有個(gè)原因是“木桶效應(yīng)”，系統(tǒng)性能瓶頸取決于性能最差的那個(gè)節(jié)點(diǎn)。另一個(gè)原因是規(guī)模越大，出現(xiàn)節(jié)點(diǎn)宕機(jī)、壞盤(pán)等異常情況就會(huì)越頻繁，故障率提高會(huì)導(dǎo)致SQL重試概率提升。

基于上述分析，MPP比較適合執(zhí)行時(shí)間不會(huì)太久的業(yè)務(wù)場(chǎng)景，比如數(shù)小時(shí)。因?yàn)闀r(shí)間越久，故障概率越大。

其他非MPP架構(gòu)：

基于MR系統(tǒng)局限性考慮，除了采用MPP架構(gòu)外，Hive和Spark均使用不同方式進(jìn)行了優(yōu)化，包括Hive的Tez，SparkSQL基于DAG（Directed Acyclic Graph）等。

不同架構(gòu)有不同優(yōu)缺點(diǎn)，重要的是找到其適用的場(chǎng)景，并進(jìn)行靠譜地優(yōu)化，充分發(fā)揮其優(yōu)勢(shì)。

2. 什么是基于代價(jià)的查詢優(yōu)化？

有了適合的系統(tǒng)架構(gòu)并不一定能夠帶來(lái)正向收益，“好馬配好鞍”，執(zhí)行計(jì)劃的好壞對(duì)最終系統(tǒng)的性能也有著決定性作用。執(zhí)行計(jì)劃及其優(yōu)化，就筆者的理解來(lái)說(shuō)，其來(lái)源于關(guān)系型數(shù)據(jù)庫(kù)領(lǐng)域。這又是一門(mén)大學(xué)問(wèn)，這里僅簡(jiǎn)單介紹。

分布式架構(gòu)使得執(zhí)行計(jì)劃能夠進(jìn)行跨節(jié)點(diǎn)的并行優(yōu)化，通過(guò)任務(wù)粒度拆分、串行變并行等方式大大縮短執(zhí)行時(shí)間。除此之外，還有2個(gè)更重要的優(yōu)化方式，就是傳統(tǒng)的基于規(guī)則優(yōu)化以及更高級(jí)的基于代價(jià)優(yōu)化。

基于規(guī)則優(yōu)化：

通俗來(lái)說(shuō)，基于規(guī)則的優(yōu)化（rule based optimization，RBO）指的是不需要額外的信息，通過(guò)用戶下發(fā)的SQL語(yǔ)句進(jìn)行的優(yōu)化，主要通過(guò)改下SQL，比如SQL子句的前后執(zhí)行順序等。比較常見(jiàn)的優(yōu)化包括謂語(yǔ)下推、字段過(guò)濾下推、常量折疊、索引選擇、Join優(yōu)化等等。

謂語(yǔ)下推，即PredicatePushDown，最常見(jiàn)的就是where條件等，舉MySQL為例，MySQL Server層在獲取InnoDB表數(shù)據(jù)時(shí)，將Where條件下推到InnoDB存儲(chǔ)引擎，InnoDB過(guò)濾where條件，僅返回符合條件的數(shù)據(jù)。在有數(shù)據(jù)分區(qū)場(chǎng)景下，謂語(yǔ)下推更有效；

字段過(guò)濾下推，即ProjectionPushDown，比如某個(gè)SQL僅需返回表記錄中某個(gè)列的值，那么在列存模式下，只需讀取對(duì)應(yīng)列的數(shù)據(jù)，在行存模式下，可以選擇某個(gè)索引進(jìn)行索引覆蓋查詢，這也是索引選擇優(yōu)化的一種場(chǎng)景；

常量或函數(shù)折疊也是一種常見(jiàn)的優(yōu)化方式，將SQL語(yǔ)句中的某些常量計(jì)算（加減乘除、取整等）在執(zhí)行計(jì)劃優(yōu)化階段就做掉；

Join優(yōu)化有很多方法，這里說(shuō)的基于規(guī)則優(yōu)化，主要指的是Join的實(shí)現(xiàn)方式，比如最傻瓜式的Join實(shí)現(xiàn)就是老老實(shí)實(shí)得讀取參與Join的2張表的每條記錄進(jìn)行Join條件比對(duì)。而最普遍的優(yōu)化方式就是Hash Join，顯然效率很高。不要認(rèn)為這是想當(dāng)然應(yīng)該有的功能，其實(shí)MySQL直到8.0版本才具備。另外Join的順序及合并，有部分也可以直接通過(guò)SQL來(lái)進(jìn)行判斷和選擇。

基于代價(jià)優(yōu)化：

基于規(guī)則的優(yōu)化器簡(jiǎn)單，易于實(shí)現(xiàn)，通過(guò)內(nèi)置的一組規(guī)則來(lái)決定如何執(zhí)行查詢計(jì)劃。與之相對(duì)的是基于代價(jià)優(yōu)化（cost based optimization，CBO）。

CBO的實(shí)現(xiàn)依賴(lài)于詳細(xì)可靠的統(tǒng)計(jì)信息，比如每個(gè)列的最大值、最小值、平均值、區(qū)分度、記錄數(shù)、列總和，表大小分區(qū)信息，以及列的直方圖等元數(shù)據(jù)信息。

CBO的一大用途是在Join場(chǎng)景，決定Join的執(zhí)行方式和Join的順序。這里所說(shuō)的Join我們主要是討論Hash Join。

Join執(zhí)行方式：

根據(jù)參與Join的驅(qū)動(dòng)表（Build Table）和被驅(qū)動(dòng)表（Probe Table）的大小，Hash Join一般可以分為broadcast和partition兩種。

廣播方式適用于大表與小表進(jìn)行Join，在并行Join時(shí)，將小表廣播到大表分區(qū)數(shù)據(jù)所在的各個(gè)執(zhí)行節(jié)點(diǎn)，分別與大表分區(qū)數(shù)據(jù)進(jìn)行Join，最后返回Join結(jié)果并匯總。

而分區(qū)方式是最為一般的模式，適用于大表間Join或表大小未知場(chǎng)景。分別將兩表進(jìn)行分區(qū)，每個(gè)分區(qū)分別進(jìn)行Join。

顯然，判斷大小表的關(guān)鍵就看是否能夠通過(guò)某種方式獲取表的記錄數(shù)，如果存儲(chǔ)層保存了記錄數(shù)，那么可從元數(shù)據(jù)中直接獲取。

如果Join的兩表都是大表，但至少有個(gè)表是帶Where過(guò)濾條件的，那么在決定走分區(qū)方式前還可進(jìn)一步看滿足條件的記錄數(shù)，這時(shí)候，物理上進(jìn)行分區(qū)的表存儲(chǔ)方式可發(fā)揮作用，可以看每個(gè)分區(qū)的最大值和最小值及其記錄數(shù)來(lái)估算過(guò)濾后的總記錄數(shù)。當(dāng)然，還有種更精確的方式是列直方圖，能夠直接而直觀得獲取總記錄數(shù)。

如果上述的統(tǒng)計(jì)信息都沒(méi)有，要使用CBO還有另一種方式就是進(jìn)行記錄的動(dòng)態(tài)采樣來(lái)決定走那種Join方式。

Join順序：

如果一個(gè)查詢的SQL中存在多層Join操作，如何決定Join的順序?qū)π阅苡泻艽笥绊憽＿@塊也已是被數(shù)據(jù)庫(kù)大佬們充分研究過(guò)的技術(shù)。

一個(gè)好的CBO應(yīng)該能夠根據(jù)SQL 語(yǔ)句的特點(diǎn)，來(lái)自動(dòng)選擇使用Left-deep tree（LDT，左圖）還是 bushy tree（BYT，右圖）執(zhí)行join。

兩種Join順序沒(méi)有好壞之分，關(guān)鍵看進(jìn)行Join的表數(shù)據(jù)即Join的字段特點(diǎn)。

對(duì)于LDT，如果每次Join均能夠過(guò)濾掉大量數(shù)據(jù)，那么從資源消耗來(lái)看，顯然是更優(yōu)的。對(duì)于給每個(gè)列都構(gòu)建了索引的某些系統(tǒng)，使用LDT相比BYT更好。

一般來(lái)說(shuō)，選擇BYT是效率更高的模式，通過(guò)串行多層Join改為并行的更少層次Join，可以發(fā)揮MPP架構(gòu)的優(yōu)勢(shì)，盡快得到結(jié)果，在多表模式ROLAP場(chǎng)景常采用。

3. 為什么需要向量化執(zhí)行引擎？其與動(dòng)態(tài)代碼生成有何關(guān)系？

查詢執(zhí)行引擎 (query execution engine) 是數(shù)據(jù)庫(kù)中的一個(gè)核心組件，用于將查詢計(jì)劃轉(zhuǎn)換為物理計(jì)劃，并對(duì)其求值返回結(jié)果。查詢執(zhí)行引擎對(duì)系統(tǒng)性能影響很大，在一項(xiàng)針對(duì)Impala和Hive的對(duì)比時(shí)發(fā)現(xiàn)，Hive在某些簡(jiǎn)單查詢上（TPC-H Query 1）也比Impala慢主要是因?yàn)镠ive運(yùn)行時(shí)完全處于CPU bound的狀態(tài)中，磁盤(pán)IO只有20%，而Impala的IO至少在85%。

什么原因?qū)е逻@么大的差別呢？首先得簡(jiǎn)單說(shuō)下火山模型的執(zhí)行引擎。

火山模型及其缺點(diǎn)：

火山模型（Volcano-style execution）是最早的查詢執(zhí)行引擎，也叫做迭代模型 (iterator model)，或 one-tuple-at-a-time。在這種模型中，查詢計(jì)劃是一個(gè)由operator組成的DAG，其中每一個(gè)operator 包含三個(gè)函數(shù)：open，next，close。Open 用于申請(qǐng)資源，比如分配內(nèi)存，打開(kāi)文件，close 用于釋放資源，next方法遞歸的調(diào)用子operator的 next方法生成一個(gè)元組（tuple，即行row在物理上的表示）。

下圖描述了“select sum(C1) from T1 where C2 > 15”的查詢計(jì)劃，該查詢計(jì)劃包含Project，HashAgg，Scan等operator，每個(gè) operator的next方法遞歸調(diào)用子節(jié)點(diǎn)的 next，一直遞歸調(diào)用到葉子節(jié)點(diǎn)Scan operator，Scan operator的next 從文件中返回一個(gè)元組。

其缺點(diǎn)主要在于：

• 大量虛函數(shù)調(diào)用：火山模型的next方法通常實(shí)現(xiàn)為一個(gè)虛函數(shù)，在編譯器中，虛函數(shù)調(diào)用需要查找虛函數(shù)表, 并且虛函數(shù)調(diào)用是一個(gè)非直接跳轉(zhuǎn) (indirect jump), 會(huì)導(dǎo)致一次錯(cuò)誤的CPU分支預(yù)測(cè) (brance misprediction), 一次錯(cuò)誤的分支預(yù)測(cè)需要十幾個(gè)周期的開(kāi)銷(xiāo)?；鹕侥Ｐ蜑榱朔祷匾粋€(gè)元組，需要調(diào)用多次next 方法，導(dǎo)致昂貴的函數(shù)調(diào)用開(kāi)銷(xiāo)

• 類(lèi)型裝箱：對(duì)于a + 2 * b之類(lèi)表達(dá)式，由于需要對(duì)不同數(shù)據(jù)類(lèi)型的變量做解釋?zhuān)栽贘ava中需要把這些本來(lái)是primitive（如int等類(lèi)型）的變量包裝成Object，但執(zhí)行時(shí)又需要調(diào)用具體類(lèi)型的實(shí)現(xiàn)函數(shù)，這本質(zhì)上也是虛函數(shù)調(diào)用的效率問(wèn)題；

• CPU Cache利用效率低：next方法一次只返回一個(gè)元組，元組通常采用行存儲(chǔ)，如果僅需訪問(wèn)第一列而每次均將一整行填入CPU Cache，將導(dǎo)致Cache Miss；

• 條件分支預(yù)測(cè)失?。含F(xiàn)在的CPU都是有并行流水線的，但是如果出現(xiàn)條件判斷會(huì)導(dǎo)致無(wú)法并行。比如判斷數(shù)據(jù)的類(lèi)型（是string還是int），或判斷某一列是否因?yàn)槠渌侄蔚倪^(guò)濾條件導(dǎo)致本行不需要被讀取等場(chǎng)景；

• CPU與IO性能不匹配：每次從磁盤(pán)讀取一個(gè)行數(shù)據(jù)，經(jīng)過(guò)多次調(diào)用交給CPU進(jìn)行處理，顯然，大部分時(shí)間都是CPU等待數(shù)據(jù)就緒，導(dǎo)致CPU空轉(zhuǎn)。

通過(guò)上述描述，可以得出解決問(wèn)題的基本方法?？梢詫?wèn)題分為2大類(lèi)，分別用下述的向量化引擎和動(dòng)態(tài)代碼生成技術(shù)來(lái)解決。

向量化執(zhí)行引擎：

向量化執(zhí)行以列存為前提，主要思想是每次從磁盤(pán)上讀取一批列，這些列以數(shù)組形式組織。每次next都通過(guò)for循環(huán)處理列數(shù)組。這么做可以大幅減少next的調(diào)用次數(shù)。相應(yīng)的CPU的利用率得到了提高，另外數(shù)據(jù)被組織在一起?？梢赃M(jìn)一步利用CPU硬件的特性，如SIMD，將所有數(shù)據(jù)加載到CPU的緩存當(dāng)中去，提高緩存命中率，提升效率。在列存儲(chǔ)與向量化執(zhí)行引擎的雙重優(yōu)化下，查詢執(zhí)行的速度會(huì)有一個(gè)非常巨大的飛躍。

動(dòng)態(tài)代碼生成：

向量化執(zhí)行減少CPU等待時(shí)間，提高CPU Cache命中率，通過(guò)減少next調(diào)用次數(shù)來(lái)緩解虛函數(shù)調(diào)用效率問(wèn)題。而動(dòng)態(tài)代碼生成，則是進(jìn)一步解決了虛函數(shù)調(diào)用問(wèn)題。

動(dòng)態(tài)代碼生成技術(shù)不使用解釋性的統(tǒng)一代碼，而是直接生成對(duì)應(yīng)的執(zhí)行語(yǔ)言的代碼并直接用primitive type。對(duì)于判斷數(shù)據(jù)類(lèi)型造成的分支判斷，動(dòng)態(tài)代碼的效果可以消除這些類(lèi)型判斷，使用硬件指令來(lái)進(jìn)一步提高循環(huán)處理效率。

具體實(shí)現(xiàn)來(lái)說(shuō)，JVM系如Spark SQL，Presto可以用反射，C++系的Impala則使用了llvm生成中間碼。相對(duì)來(lái)說(shuō)，C++的效率更高。

向量化和動(dòng)態(tài)代碼生成技術(shù)往往是一起工作達(dá)到更好的效果。

4. 都有哪些存儲(chǔ)空間和訪問(wèn)效率優(yōu)化方法？

存儲(chǔ)和IO模塊的優(yōu)化方法很多，這里我們還是在Hadoop生態(tài)下來(lái)考慮，當(dāng)然，很多優(yōu)化方法不是Hadoop特有的，而是通用的。OLAP場(chǎng)景下，數(shù)據(jù)存儲(chǔ)最基礎(chǔ)而有效的優(yōu)化是該行存儲(chǔ)為列存儲(chǔ)，下面討論的優(yōu)化措施均基于列存。

數(shù)據(jù)壓縮和編碼：

數(shù)據(jù)壓縮是存儲(chǔ)領(lǐng)域常用的優(yōu)化手段，以可控的CPU開(kāi)銷(xiāo)來(lái)大幅縮小數(shù)據(jù)在磁盤(pán)上的存儲(chǔ)空間，一來(lái)可以節(jié)省成本，二來(lái)可以減小IO和數(shù)據(jù)在內(nèi)存中跨線程和跨節(jié)點(diǎn)網(wǎng)絡(luò)傳輸?shù)拈_(kāi)銷(xiāo)。目前在用的主流壓縮算法包括zlib、snappy和lz4等。壓縮算法并不是壓縮比越高越好，壓縮率越高的算法壓縮和解壓縮速度往往就越慢，需要根據(jù)硬件配置和使用場(chǎng)景在cpu 和io之間進(jìn)行權(quán)衡。

數(shù)據(jù)編碼可以理解為輕量級(jí)壓縮，包括RLE和數(shù)據(jù)字典編碼等。

上圖截至Presto論文，展示了RLE編碼和數(shù)據(jù)字典編碼的使用方式。RLE用在各列都是重復(fù)字符的情況，比如page0中6行記錄的returnflag都是"F"。數(shù)據(jù)字典可高效使用在區(qū)分度較低的列上，比如列中只有幾種字符串的場(chǎng)景。考慮到同個(gè)表的列的值相關(guān)性，數(shù)據(jù)字典可以跨page使用。

與數(shù)據(jù)壓縮相比，數(shù)據(jù)編碼方式在某些聚合類(lèi)查詢場(chǎng)景下，無(wú)需對(duì)數(shù)據(jù)進(jìn)行解碼，直接返回所需結(jié)果。比如假設(shè)T1表的C1列為某個(gè)字符，RLE算法將16個(gè)C1列的值“aaaaaabbccccaaaa”編碼為6a2b4c4a，其中6a表示有連續(xù)6個(gè)字符a。當(dāng)執(zhí)行 select count(*) from T1 where C1=’a’時(shí)，不需要解壓6a2b4c4a，就能夠知道這16行記錄對(duì)應(yīng)列值為a有10行。

在列存模式下，數(shù)據(jù)壓縮和編碼的效率均遠(yuǎn)高于行存。

數(shù)據(jù)精細(xì)化存儲(chǔ)：

所謂數(shù)據(jù)精細(xì)化存儲(chǔ)，是通過(guò)盡可能多得提供元數(shù)據(jù)信息來(lái)減少不必要的數(shù)據(jù)掃描和計(jì)算，常用的方法包括但不限于如下幾種：

• 數(shù)據(jù)分區(qū)：數(shù)據(jù)分區(qū)可用于將表中數(shù)據(jù)基于hash或range打散到多個(gè)存儲(chǔ)節(jié)點(diǎn)上，配合多副本存儲(chǔ)?？梢蕴岣邤?shù)據(jù)容災(zāi)和遷移效率。除此之外，在查詢時(shí)可以快速過(guò)濾掉不符合where條件要求的數(shù)據(jù)分區(qū)，無(wú)需逐列讀取數(shù)據(jù)進(jìn)行判斷。

• 行組：與數(shù)據(jù)分區(qū)類(lèi)似，Hadoop中常用的parquet和orcfile還將表數(shù)據(jù)分為多個(gè)行組（row group），每個(gè)行組內(nèi)的記錄按列存儲(chǔ)。這樣即達(dá)到列存提高OLAP查詢效率，同時(shí)能夠兼顧查詢多行的需求；

• 局部索引：在數(shù)據(jù)分區(qū)或行組上創(chuàng)建索引，可以提高查詢效率。如下圖所示，orcfile在每個(gè)行組的頭部維護(hù)了Index Data來(lái)，保存最大值和最小值等元數(shù)據(jù)，基于這些信息可以快速?zèng)Q定是否需掃描該行組。某些OLAP系統(tǒng)進(jìn)一步豐富了元數(shù)據(jù)信息，比如建立該行組記錄的倒排索引或B+樹(shù)索引，進(jìn)一步提高掃描和查詢效率。

• 富元數(shù)據(jù)：除了提供最大值和最小值信息外，還可進(jìn)一步提供平均值、區(qū)分度、記錄數(shù)、列總和，表大小分區(qū)信息，以及列的直方圖等元數(shù)據(jù)信息。

數(shù)據(jù)本地化訪問(wèn)：

數(shù)據(jù)本地化讀寫(xiě)是常見(jiàn)的優(yōu)化方法，在Hadoop下也提供了相應(yīng)的方式。

一般來(lái)說(shuō)，讀HDFS上的數(shù)據(jù)首先需要經(jīng)過(guò)NameNode獲取數(shù)據(jù)存放的DataNode信息，在去DataNode節(jié)點(diǎn)讀取所需數(shù)據(jù)。

對(duì)于Impala等OLAP系統(tǒng)，可以通過(guò)HDFS本地訪問(wèn)模式進(jìn)行優(yōu)化，直接讀取磁盤(pán)上的HDFS文件數(shù)據(jù)。HDFS這個(gè)特性稱(chēng)為"Short Circuit Local Reads"，其相關(guān)的配置項(xiàng)（在hdfs-site.xml中）如下：

<property>    <name>dfs.client.read.shortcircuit</name>    <value>true</value>  </property>  <property>    <name>dfs.domain.socket.path</name>    <value>/var/lib/hadoop-hdfs/dn_socket</value>  </property>

其中：dfs.client.read.shortcircuit是打開(kāi)這個(gè)功能的開(kāi)關(guān)，dfs.domain.socket.path是Datanode和DFSClient之間溝通的Socket的本地路徑。

運(yùn)行時(shí)數(shù)據(jù)過(guò)濾：

這是少部分OLAP系統(tǒng)才具有的高級(jí)功能，比如Impala的RunTime Filter（RF）運(yùn)行時(shí)過(guò)濾，和SparkSQL 3.0的 Dynamic Partition Pruning動(dòng)態(tài)分區(qū)裁剪，可以將驅(qū)動(dòng)表的bloomfilter（BF）或過(guò)濾條件作用在被驅(qū)動(dòng)表的數(shù)據(jù)掃描階段，從而極大減少需掃描/返回的數(shù)據(jù)量。下面分別用一個(gè)圖進(jìn)行簡(jiǎn)述，在后續(xù)分析具體OLAP系統(tǒng)時(shí)再詳述。

上圖直觀得展示了Impala runtime filter的實(shí)現(xiàn)。流程如下：

1. 同時(shí)下發(fā)兩個(gè)表的SCAN操作。左邊是大表，右邊是小表（相對(duì)而言，也有可能是同等級(jí)別的），但是左表會(huì)等待一段時(shí)間（默認(rèn)是1s），因此右表的SCAN會(huì)先執(zhí)行；

2. 右表的掃描的結(jié)果根據(jù)join鍵哈希傳遞掃不同的Join節(jié)點(diǎn)，由Join節(jié)點(diǎn)執(zhí)行哈希表的構(gòu)建和RF的構(gòu)建；

3. Join節(jié)點(diǎn)讀取完全部的右表輸入之后也完成了RF的構(gòu)建，它會(huì)將RF交給Coordinator節(jié)點(diǎn)（如果是Broadcast Join則會(huì)直接交給左表的Scan節(jié)點(diǎn)）；

4. Coordinator節(jié)點(diǎn)將不同的RF進(jìn)行merge，也就是把Bloom Filter進(jìn)行merge，merge之后的Bloom Filter就是一個(gè)GLOBAL RF，它將這個(gè)RF分發(fā)給每一個(gè)左表Scan；

5. 左表會(huì)等待一段時(shí)間（默認(rèn)1s）再開(kāi)啟數(shù)據(jù)掃描，為了是盡可能的等待RF的到達(dá)，但是無(wú)論RF什么時(shí)候到達(dá)，RF都會(huì)在到達(dá)那一刻之后被應(yīng)用；

6. 左表使用RF完成掃描之后同樣以Hash方式交給Join節(jié)點(diǎn)，由Join節(jié)點(diǎn)進(jìn)行apply操作，以完成整個(gè)Join過(guò)程。

sparksql圖2

上面2幅圖是SparkSQL 3.0的動(dòng)態(tài)分區(qū)裁剪示意圖。將右表的掃描結(jié)果（hashtable of table Date after filter）廣播給左表的Join節(jié)點(diǎn)，在進(jìn)行左表掃描時(shí)即使用右表的hashtable進(jìn)行條件數(shù)據(jù)過(guò)濾。

5. 除了上面這些，還有其他優(yōu)化方法嗎？

還有個(gè)極為重要的技術(shù)是集群資源管理和調(diào)度。Hadoop使用YARN進(jìn)行資源調(diào)度，雖然帶來(lái)了很大遍歷，但對(duì)性能要求較高的OLAP系統(tǒng)卻有些不適合。

如啟動(dòng)AppMaster和申請(qǐng)container會(huì)占用不少時(shí)間，尤其是前者，而且container的供應(yīng)如果時(shí)斷時(shí)續(xù)，會(huì)極大的影響時(shí)效性。

目前的優(yōu)化方法主要包括讓AppMaster啟動(dòng)后長(zhǎng)期駐守，container復(fù)用等方式。讓資源在需要用時(shí)已經(jīng)就位，查詢無(wú)需等待即可馬上開(kāi)始。

04

做個(gè)總結(jié)

本系列通過(guò)2篇文章，總結(jié)了下筆者最近看的一些OLAP相關(guān)文獻(xiàn)材料。筆者通過(guò)這兩篇文章主要是想說(shuō)下自己對(duì)數(shù)倉(cāng)和OLAP系統(tǒng)的理解，之所以采用問(wèn)答形式，是因?yàn)楣P者就是帶著這些問(wèn)題去google網(wǎng)上或公司內(nèi)部的資料，或者直接請(qǐng)教在這個(gè)領(lǐng)域的大佬。

原文鏈接：

https://zhuanlan.zhihu.com/p/147344996

由于水平有限，難免有所錯(cuò)誤，非常歡迎大家看后能夠指出，讓筆者有進(jìn)步的機(jī)會(huì)。這兩篇文章可以理解為是對(duì)他人文章的一次匯總加工。部分內(nèi)容直接參考了其他文章，這也是在筆者先前其他文章中極少出現(xiàn)的情況，這些內(nèi)容均在文末“引用”小結(jié)列出。

推薦閱讀：

OLAP數(shù)倉(cāng)入門(mén)：基礎(chǔ)篇

詳解hive的join優(yōu)化

Presto在滴滴的探索與實(shí)踐