image.png

image.png

作者：袁洋 | StoneData 技術(shù)架構(gòu)師

審核：王博

論文鏈接：columnstoresfntdbs.pdf (harvard.edu)

列存四先驅(qū)和 MIT 知名教授 Samuel Madden 于 2013 年在某期刊上寫的一篇當(dāng)時(shí)列存相關(guān)技術(shù)的綜述。文章還挺全面也很經(jīng)典，通過(guò)剖析三個(gè)經(jīng)典的現(xiàn)代列存的數(shù)據(jù)庫(kù) C-store、MonetDB、VectorWise，闡述了各項(xiàng)單獨(dú)技術(shù)的來(lái)龍去脈和相輔相成的關(guān)系。

image.png

行式存儲(chǔ) vs 列式存儲(chǔ)

在數(shù)據(jù)庫(kù)存儲(chǔ)引擎?zhèn)韧ǔＳ袃深惔鎯?chǔ)模型：

• 行式存儲(chǔ) NSM（N-ary Storage Model）

• 列式存儲(chǔ) DSM（Decomposition Storage Model）

image.png

1.1 NSM

一般是將一行數(shù)據(jù)完整的從頭到尾連續(xù)存儲(chǔ)（超長(zhǎng)的字段一般會(huì)單獨(dú)存儲(chǔ)，行內(nèi)記錄邏輯地址），連續(xù)多行構(gòu)成一個(gè)頁(yè)，頁(yè)的尾部通常會(huì)存儲(chǔ)索引來(lái)解決 record 不定長(zhǎng)時(shí)的快速查找問(wèn)題。

以行為單位存儲(chǔ)，再配合以 B+ 樹(shù)或 SS-Table 作為索引，就能快速通過(guò)主鍵找到相應(yīng)的行數(shù)據(jù)。

行式存儲(chǔ)對(duì)于 OLTP 場(chǎng)景是很自然的：大多數(shù)操作都以實(shí)體（entity）為單位，即大多為 增刪改查 一整行記錄，顯然把一行數(shù)據(jù)存在物理上相鄰的位置是個(gè)很好的選擇。

優(yōu)點(diǎn)

行存在 insert/update/delete/point lookup query (點(diǎn)查)的場(chǎng)景是占優(yōu)的：因?yàn)樯婕暗男袛?shù)據(jù)是連續(xù)存儲(chǔ)的，理論上不存在讀寫放大。

缺點(diǎn)

在讀取時(shí)，由于會(huì)讀取大量無(wú)效列數(shù)據(jù)，譬如 select name from R where age < 40，那么對(duì)于每次 age 的遍歷，除了會(huì)將無(wú)用的其他數(shù)據(jù)一起讀入，每次讀取 record，都可能會(huì)引起 cache miss。對(duì) cpu cache 非常不友好。

image.png

1.2 DSM

在存儲(chǔ)時(shí)將多行數(shù)據(jù)的相同 column 連續(xù)存儲(chǔ)在一起，相同 column 的數(shù)據(jù)組成一個(gè)一個(gè)的塊(Block)。

優(yōu)點(diǎn)

列式存儲(chǔ)非常適用于大量復(fù)雜查詢的數(shù)據(jù)分析場(chǎng)景，列式數(shù)據(jù)庫(kù)相較于傳統(tǒng)的行式數(shù)據(jù)庫(kù)具有以下優(yōu)點(diǎn)：

（1）更高的查詢效率。由于數(shù)據(jù)按列存儲(chǔ)，當(dāng)需要查詢某一列的數(shù)據(jù)時(shí)，列式數(shù)據(jù)庫(kù)只需要讀取該列的數(shù)據(jù)，而不需要讀取整行數(shù)據(jù)，因此查詢速度更快。

（2）更好的數(shù)據(jù)壓縮。由于同一列的數(shù)據(jù)類型相同，因此可以采用更加有效的數(shù)據(jù)壓縮方式，減少存儲(chǔ)空間的占用。

（3）更快的并行處理能力。列式數(shù)據(jù)庫(kù)可以同時(shí)處理多個(gè)列，因此可以更好地利用多核處理器和并行計(jì)算資源，提高數(shù)據(jù)處理效率。

缺點(diǎn)

列存在更新場(chǎng)景明顯存在缺陷：

每 insert/update/delete 一行數(shù)據(jù)，需要同時(shí)修改多個(gè)列(會(huì)去更新存在不同位置的 column)，帶來(lái) IO 放大，且為隨機(jī) IO。

image.png

1.3 PAX：一個(gè) Cache 友好高效的行列混存方案

可以看到，NSM 和 DSM 都有各自的優(yōu)劣，所以如何將它們和優(yōu)點(diǎn)結(jié)合起來(lái)，就是 PAX 考慮的問(wèn)題。

• NSM 能更快速的取出一行記錄，這是因?yàn)橐恍械臄?shù)據(jù)相鄰保存在同一頁(yè)

• DSM 能更好的利用 CPU Cache 以及使用更緊湊的壓縮

image.png

PAX 全稱是 Partition Attributes Across，它的核心思路是：嘗試將 DSM 的一些優(yōu)點(diǎn)引入 NSM，將兩者的優(yōu)點(diǎn)相結(jié)合。將一個(gè)頁(yè)劃分成多個(gè) minipage，minipage 內(nèi)按列存儲(chǔ)，而一頁(yè)中的各個(gè) minipage 能組合成完整的若干 relation。

假設(shè)有 n 個(gè) attributes，PAX 就會(huì)將 page 分成 n 個(gè) mini pages，然后將第一個(gè) attribute 的放在第一個(gè) mini page 上面，第二個(gè)放在第二個(gè) mini page，以此類推。

image.png

在每個(gè) page 的開(kāi)頭，會(huì)存放每個(gè) mini page 的 offset，mini page 對(duì)于 Fixed-length attribute 的數(shù)據(jù)，會(huì)使用 F-minipage ，而對(duì)于 variable-length attribute 的數(shù)據(jù)，則會(huì)使用 V-minipage。對(duì)于 F-minipage 來(lái)說(shuō)，最后會(huì)有一個(gè) bit vector 來(lái)存放 null value。而對(duì)于 V-minipage 來(lái)說(shuō)，最后會(huì)保存每個(gè)每個(gè) value 的在 mini page 里面的 offset。

一篇關(guān)于 PAX 的 paper 供大家進(jìn)一步學(xué)習(xí)和研究。

Paper: https://www.vldb.org/conf/2001/P169.pdf

image.png

怎么讓列式數(shù)據(jù)庫(kù)更快

僅僅將數(shù)據(jù)存儲(chǔ)在列中，并不足以讓基于列的存儲(chǔ)獲得全部性能。該論文中花了大量篇幅來(lái)分析幾個(gè)關(guān)鍵的列存數(shù)據(jù)庫(kù)加速技術(shù)， 如下圖所示

image.png

根據(jù)論文中的這些技術(shù)特性，下面我們逐步分析向量化計(jì)算，數(shù)據(jù)壓縮，延遲物化 ，連接優(yōu)化幾個(gè)部分。

image.png

向量化計(jì)算

3.1 概念

火山模型（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 在物理上的表示）。

目前主要有兩種關(guān)于向量化執(zhí)行引擎的實(shí)現(xiàn)方法：

1. 仍然使用火山模型，只不過(guò)一次返回一組列。這種模型的優(yōu)勢(shì)是仍然使用（火山模型），這個(gè)優(yōu)化器于執(zhí)行器模型已經(jīng)很成熟，剩下需要的工作量就在于如何將一次一 tuple 的處理模式，修改為一次向上返回一組列存行值（例如：100-1000 行）處理方式，難度相對(duì)較小

2. 將整個(gè)模型改造成為層次型的執(zhí)行模式，這種模式需要將優(yōu)化好的執(zhí)行計(jì)劃樹(shù)，最終轉(zhuǎn)換為編譯執(zhí)行，即，一次調(diào)用下來(lái)之后，每一層都完成后才向上返回?cái)?shù)據(jù)，這樣能夠最大程度的減少各層次節(jié)點(diǎn)間的調(diào)用次數(shù)，提高 CPU 的有效計(jì)算效率

   
   
   image.png

上圖描述的就是火山模型實(shí)現(xiàn)的行存執(zhí)行引擎與列存執(zhí)行引擎，其中左邊代表的是當(dāng)前比較流行的傳統(tǒng)行存火山模型，右邊代表的是列存實(shí)現(xiàn)的火山模型，從上圖我們可以看到火山模式是從執(zhí)行計(jì)劃樹(shù)的根節(jié)點(diǎn)開(kāi)始向葉子節(jié)點(diǎn)遞歸調(diào)用，然后有葉子節(jié)點(diǎn)，通常是各種的掃描節(jié)點(diǎn)返回一條符合過(guò)濾條件的 tuple 給上層節(jié)點(diǎn)處理，每一層節(jié)點(diǎn)在處理完該 tuple 之后繼續(xù)網(wǎng)上層節(jié)點(diǎn)傳遞記錄（Agg 節(jié)點(diǎn)不是立刻往上層節(jié)點(diǎn)返回?cái)?shù)據(jù)，它需要計(jì)算完所有的 Tuple，才能繼續(xù)往上層節(jié)點(diǎn)返回，所以這里 AGG 算子在處理好這個(gè) Tuple 之后，又會(huì)往下調(diào)用掃描算子返回下一條符合過(guò)濾條件的記錄）。這樣處理完整個(gè)表的記錄之后，AGG 算子會(huì)把數(shù)據(jù)返回到上一層節(jié)點(diǎn)繼續(xù)處理，在整個(gè)過(guò)程中需要 AGG 算子緩存中間結(jié)果。右邊列存執(zhí)行引擎，執(zhí)行邏輯基本上與左邊行存執(zhí)行引擎一致，但是每次掃描處理的是一組組以 col 組織的列數(shù)據(jù)集合，這樣我們最為直觀的觀察就是從上層節(jié)點(diǎn)向下層節(jié)點(diǎn)的調(diào)用次數(shù)少了。相應(yīng)的 CPU 的利用率得到了提高，另外數(shù)據(jù)被組織在一起?？梢岳糜布l(fā)展帶來(lái)的一些收益；如 SIMD, 循環(huán)優(yōu)化，將所有數(shù)據(jù)加載到 CPU 的緩存當(dāng)中去，提高緩存命中率，提升效率。在列存儲(chǔ)與向量化執(zhí)行引擎的雙重優(yōu)化下，查詢執(zhí)行的速度會(huì)有一個(gè)非常巨大的飛躍大約 3-5 倍。

向量化執(zhí)行流程

1. 將查詢進(jìn)度控制邏輯與數(shù)據(jù)處理邏輯分開(kāi)

2. 每個(gè)操作符的 next()方法返回 N 個(gè)圖元的矢量

3. 避免產(chǎn)生大量中間結(jié)果

論文中闡述了一種觀點(diǎn)：在面向塊和矢量化處理的視線中，通過(guò)在運(yùn)算符之間傳遞 緩存行 大小的 元組 塊，并且一次對(duì)多個(gè)值進(jìn)行操作，而不是使用傳統(tǒng)的 一次一個(gè)元組 的迭代器，列存儲(chǔ)可以實(shí)現(xiàn)大幅提高緩存利用率和 CPU 效率。

3.2 向量化執(zhí)行的優(yōu)勢(shì)

1. 降低解釋開(kāi)銷

減少了解釋的開(kāi)銷, 與 tuple-at-a-time 模型相比，查詢解釋器執(zhí)行的函數(shù)調(diào)用量減少了一個(gè)與矢量大小相等的系數(shù)。在 TPC-H Q1 的查詢中可以將性能提高兩個(gè)數(shù)量級(jí)。

2. 緩存局部性

列數(shù)據(jù)是連續(xù)的，分配的內(nèi)存塊也是連續(xù)的，所以在第一次訪問(wèn)時(shí)，大塊的內(nèi)存塊會(huì)被加載到高速緩存中。這使得后續(xù)訪問(wèn)數(shù)組中的元素變得相對(duì)較快。

3. 編譯器優(yōu)化的可能性

自動(dòng)內(nèi)存預(yù)取、觸發(fā)編譯器來(lái)生成 SIMD 指令、有效使用 CPU 緩沖機(jī)制

4. 并行內(nèi)存訪問(wèn)

并行內(nèi)存訪問(wèn)。通過(guò)無(wú)序推測(cè)生成多個(gè)并行未命中的代碼的執(zhí)行速度通常是非矢量化內(nèi)存查找的四倍

3.5 向量化執(zhí)行比傳統(tǒng)模式的優(yōu)勢(shì)

• 減少了函數(shù)調(diào)用的開(kāi)銷（調(diào)用次數(shù)減少 N 倍）

• 通過(guò)調(diào)整向量大小來(lái)提高緩存局部性能力

• 避免分支預(yù)測(cè)，提高并行內(nèi)存訪問(wèn)速度

• 編譯器有機(jī)會(huì)進(jìn)行編譯器優(yōu)化，可以利用 SIMD 指令集加速計(jì)算

• 基于塊的算法優(yōu)化

• 可以以更小的代價(jià)做 Profiling(面向性能分析開(kāi)銷)

適應(yīng)性執(zhí)行：動(dòng)態(tài)選擇最優(yōu)實(shí)現(xiàn)(多臂老虎機(jī)問(wèn)題)

image.png

數(shù)據(jù)壓縮

4.1 Compression Perspectives

同一列的數(shù)據(jù)放一起信息熵要遠(yuǎn)低于來(lái)自不同列的數(shù)據(jù)。信息熵越低，數(shù)據(jù)越高度有序。 壓縮算法在信息熵低 (即具有高數(shù)據(jù)值局部性) 的數(shù)據(jù)上表現(xiàn)更好；來(lái)自同一列的值往往比來(lái)自不同列的值有更多的值局部性。value locality 的意思就是某個(gè)數(shù)據(jù) (數(shù)據(jù)的內(nèi)容或者邏輯地址) 被訪問(wèn)地更頻繁。

通常情況下，數(shù)據(jù)庫(kù)系統(tǒng)的底線目標(biāo)是性能，即盡可能快地處理一個(gè)或多個(gè)查詢，而不是壓縮率。壓縮通過(guò)減少花在 I/O 上的時(shí)間來(lái)提高性能。

4.2 壓縮帶來(lái)的優(yōu)勢(shì)

• 按列壓縮壓縮率遠(yuǎn)高于按行壓縮，如果數(shù)據(jù)是排序的壓縮率會(huì)更高

• 數(shù)據(jù)庫(kù)系統(tǒng)的終極目標(biāo)是性能而不是壓縮率。但是數(shù)據(jù)被壓縮后能減少磁盤 IO，減少?gòu)膬?nèi)存到 CPU 帶寬的使用。從而進(jìn)一步提高了性能

• 一些壓縮算法會(huì)把數(shù)據(jù)壓縮為固定寬度（fixed-width）數(shù)組，這樣就可以進(jìn)一步利用 SIMD 來(lái)加速

• 基于頻率的分段壓縮，每一段數(shù)據(jù)有更低的信息熵

4.3 壓縮算法

4.3.1 RLE, 游程長(zhǎng)度壓縮算法

RLE, 游程長(zhǎng)度壓縮算法, 是一種無(wú)損數(shù)據(jù)壓縮的形式, 使用值、起始位置、運(yùn)行長(zhǎng)度三要素。其中同一數(shù)據(jù)值被存儲(chǔ)為單一的數(shù)據(jù)值和計(jì)數(shù)，而不是作為原始值存儲(chǔ)。如果一列的前 42 個(gè)元素含有值 M，也就說(shuō)起始位置為 1， 42 個(gè) M 的長(zhǎng)度， 那么這 42 個(gè)元素可以被替換成 (M, 1, 42) 的三要素信息。在列式存儲(chǔ)中，由于列的數(shù)據(jù)是連續(xù)的，相同值的情況很常見(jiàn)，因此會(huì)出現(xiàn)較多的 RLE encoding 機(jī)會(huì)。

image.png

4.3.2 Bit-Vector Encoding 位向量編碼算法

位向量編碼是為每一個(gè)不同的取值生成一個(gè)位向量, 根據(jù)位向量( 串)中不同的位置取值 0 或 1 來(lái)對(duì)應(yīng)并確定不同的原始值。位向量編碼算法其實(shí)就是位圖索引算法，適用于低基數(shù)的列，相對(duì)于 B 樹(shù)索引，它的 count,and,or 操作更有效，位圖索引位存放的是 0,1 的 bit，相對(duì)于 B 樹(shù)索引，占字節(jié)數(shù)特別少,不適合 update、insert、delete 頻繁的列-因?yàn)橐粋€(gè)數(shù)據(jù)的更新可能會(huì)導(dǎo)致 2 個(gè)位圖向量的更新。bitmap 的思想就是數(shù)據(jù)壓縮。用一個(gè)二進(jìn)制 bit(0 或者 1)去標(biāo)記某個(gè)元素對(duì)應(yīng)的 value， 這就是 bit + map。適用于低基數(shù)的列，相對(duì)于 B 樹(shù)索引，它對(duì) count, and, o r 操作更有效，位圖索引位存放的是 0,1 的 bit，相對(duì)于 B 樹(shù)索引，占字節(jié)數(shù)特別少。不適合 update、insert、delete 頻繁的列：因?yàn)橐粋€(gè)數(shù)據(jù)的更新可能會(huì)導(dǎo)致 2 個(gè)位圖向量的更新。 舉例如下

image.png

4.3.3 字典編碼算法

字典編碼就是生成一個(gè)“原始值替代值”的對(duì)照字典。為了起到壓縮的作用, 替代值的長(zhǎng)度小于原始值的長(zhǎng)度。存儲(chǔ)的時(shí)候, 只存儲(chǔ)替代值而不是原始值, 從而壓縮了存儲(chǔ)空間

字典編碼算法把唯一值編入字典，每一個(gè)唯一值都匹配一個(gè)序號(hào)，而序號(hào)用于索引字典，通過(guò)存儲(chǔ)序號(hào)來(lái)壓縮數(shù)據(jù)。如果數(shù)據(jù)表中存在大量的重復(fù)/頻繁值，那么使用字典編碼壓縮率高，效果非常好。

image.png

關(guān)于字典編碼的 Paper, 可以看看這個(gè)。

Paper: Dictionary Compression for a Scan-Based, Main-Memory Database System

https://publications.systems.ethz.ch/sites/default/files/publications/BernetJanickSpring2010.pdf

舉例如下:

image.png

image.png

延遲物化

5.1 什么是物化？

物化,即將常用元組或可能會(huì)用到的邏輯元組從實(shí)際物理存儲(chǔ)的狀態(tài)生成為實(shí)體化的元組, 也稱為物化, 存儲(chǔ)在內(nèi)存中，是包括一個(gè)查詢結(jié)果的數(shù)據(jù)庫(kù)對(duì)像，它是遠(yuǎn)程數(shù)據(jù)的的本地副本，是一個(gè)物理表。在隨后查詢時(shí), 直接讀取已經(jīng)物化的元組, 以提高查詢的效率。

image.png

5.2 延遲物化

而元組物化有兩種方案, 分別是提前物化: 在提交查詢之前物化元組; 延時(shí)物化: 盡量推遲物化元組的時(shí)間, 在查詢中間的某個(gè)時(shí)刻物化元組。對(duì)于列數(shù)據(jù)庫(kù)來(lái)說(shuō), 提前物化需要解壓所有已經(jīng)壓縮的數(shù)據(jù), 其時(shí)間和空間的開(kāi)銷是很大的。同時(shí), 提前物化會(huì)涉及到很多不必要的列, 有悖列數(shù)據(jù)庫(kù)按列存儲(chǔ)、按需取用的初衷。因此, 在列數(shù)據(jù)庫(kù)領(lǐng)域, 提出了延時(shí)物化的思想。

把從各個(gè)列中獲取的數(shù)據(jù)重新組裝為行的過(guò)程稱之為 tuple construction，延遲物化的目的就是盡可能推遲 tuple construction 的時(shí)機(jī)。把這個(gè)物化的時(shí)機(jī)盡量的拖延到整個(gè)查詢生命周期的后期。

延遲物化意味著在查詢執(zhí)行的前一段時(shí)間內(nèi)，查詢執(zhí)行的模型不是關(guān)系代數(shù)，而是基于 Column 的。

5.3 延遲物化的收益?

1. 減少物化的 tuple 數(shù)量

2. 降低 IO、網(wǎng)絡(luò)、計(jì)算壓力

3. 可以在列存(壓縮)數(shù)據(jù)上進(jìn)行高效計(jì)算

4. 減少內(nèi)存訪問(wèn)帶來(lái)的開(kāi)銷

5. 在掃描數(shù)據(jù)相對(duì)較少的情況下，需要 cache 的數(shù)據(jù)量更少，此時(shí)也會(huì)提高整個(gè)計(jì)算的 cache 命中率，減少 cpu 的消耗

5.4 一個(gè) 延遲物化的例子

SQL:

select name from person where id > 10 and age > 20

5.4.1 行存做法

從文件中讀出三列的所有數(shù)據(jù)，物化成行數(shù)據(jù)：一行行的 person 數(shù)據(jù)。然后應(yīng)用兩個(gè)過(guò)濾條件：id > 10 and age > 20，F(xiàn)ilter 之后從數(shù)據(jù)里面抽出 name 字段，作為最后的結(jié)果進(jìn)行 output

image.png

5.4.2 列存上，延遲物化的做法

延遲物化的做法是：

1. 直接在每一個(gè) Column 數(shù)據(jù)上分別應(yīng)用過(guò)濾條件，從而得到兩個(gè)滿足過(guò)濾條件的 bitmap

2. 然后再把兩個(gè) bitmap 做位與操作得到同時(shí)滿足兩個(gè)條件的所有的 bitmap

3. 因?yàn)樽詈笮枰氖?name 字段，因此拿著這些 position 對(duì) name 字段的數(shù)據(jù)進(jìn)行過(guò)濾就得到了最終的結(jié)果

image.png

5.4.3 普通物化和延遲物化對(duì)比

這兩者的權(quán)衡在于，雖然延遲加載能夠減少數(shù)據(jù)的加載量，但需要維護(hù)原始數(shù)據(jù)的位置 ，這樣才能找到對(duì)應(yīng)行的其他列的值。然而如果篩選條件（person.id > 10 and person.age > 20）不能大量過(guò)濾數(shù)據(jù)，延遲加載反而低效。

對(duì)于這種情況，就需要根據(jù)一些統(tǒng)計(jì)信息選擇合適的加載算法，來(lái)最大限度的提高效率。

延遲物化帶來(lái)的好處

• 關(guān)系代數(shù)里面的 selection 和 aggregation 都會(huì)產(chǎn)生一些不必要的物化操作，從一種形式的 tuple, 變成另外一種形式的 tuple。如果對(duì)物化進(jìn)行延遲的話，可以減少物化的開(kāi)銷(因?yàn)橐锘淖侄紊倭?，甚至直接不需要物化

• 如果數(shù)據(jù)是被壓縮過(guò)的，物化的過(guò)程就必須對(duì)數(shù)據(jù)進(jìn)行解壓，這會(huì)影響壓縮帶來(lái)的好處

• 列式的內(nèi)存組織形式對(duì) CPU Cache 非常友好，從而提高計(jì)算效率，相反行式的內(nèi)存組織形式因?yàn)榉潜匾牧姓加昧?Cache Line 的空間，Cache 效率低

• 塊遍歷的優(yōu)化手段對(duì) Column 類型的數(shù)據(jù)效果更好，因?yàn)閿?shù)據(jù)以 Column 形式保存在一起，數(shù)據(jù)是定長(zhǎng)的可能性更大。而如果 Row 形式保存在一起數(shù)據(jù)是定長(zhǎng)的可能性非常?。ㄒ?yàn)槟阋恍袛?shù)據(jù)里面只要有一個(gè)是非定長(zhǎng)的，比如 VARCHAR，那么整行數(shù)據(jù)都是非定長(zhǎng)的）

延遲物化的缺點(diǎn)

延遲物化且多表 Join 連接后， 許多 Join Algorithms 會(huì)對(duì)左（外）側(cè)輸入位置關(guān)系排序，右（內(nèi)）側(cè)輸出位置不會(huì)排序(準(zhǔn)確的說(shuō)至少有一側(cè)不會(huì)被排序)，因?yàn)橐赃@種無(wú)序的方式從列中提取值需要為每個(gè)位置跳轉(zhuǎn)存儲(chǔ)， 產(chǎn)生了隨機(jī)訪問(wèn)，相比順序訪問(wèn)會(huì)產(chǎn)生較大的開(kāi)銷。

對(duì)左（外）側(cè)輸入位置關(guān)系排序也有例外：對(duì)兩組輸入進(jìn)行排序或重新分區(qū)的 Join 算法，不會(huì)對(duì)左右位置列表進(jìn)行排序。但無(wú)論哪種方式，至少有一組輸出位置不會(huì)被排序。

從下圖可以看出延遲物化在列式數(shù)據(jù)庫(kù)優(yōu)化中可以帶來(lái)巨大的收益

image.png

image.png

表連接

6.1 更加有效地表連接

Hash-join

• 以 Hash-join (散列連接，典型連接算法) 為例，column store 可以讓 probe 探測(cè)表更緊湊（會(huì)產(chǎn)生更緊湊的散列表，從而在探測(cè)期間 during probing 產(chǎn)生更好的訪問(wèn)模式）

• a smaller hash table leads to less cache misses 更小的散列表導(dǎo)致了更少的緩沖區(qū)丟失

Jive-Join

Jive-Join (兩次排序) 解決 Unordered positional lookups?；舅枷胧窃谖覀兿胍崛〉奈恢昧斜碇刑砑右粋€(gè)額外的列，這是一個(gè)密集有序遞增的整數(shù)序列。

Invisible Join

在延遲物化缺點(diǎn)部分提到，Join 后，許多 Join Algorithms 會(huì)對(duì)左（外）側(cè)輸入位置關(guān)系排序，右（內(nèi)）側(cè)輸出位置不會(huì)排序，這是因?yàn)樽罅兄械奈恢猛ǔ０错樞虻?，而右列中的位置?huì)被探測(cè)以查找連接謂詞匹配項(xiàng)。因此需要添加一個(gè)排序列。

為了解決這個(gè)問(wèn)題，又提出了一個(gè)新的 Join 算法：Invisible Join 隱式連接。

更多 Join 實(shí)現(xiàn)

當(dāng)然還有 BroadcastJoin，LookupJoin，SortJoin...

6.2 Jive-Join

對(duì)于 Join 而言，運(yùn)算的核心在于兩表中 Joinkey 的匹配上。對(duì)于其他列數(shù)據(jù)匹配上了就復(fù)制，匹配不上就丟棄。結(jié)合延遲物化，匹配后再加載其他列數(shù)據(jù)，從而減小不必要的 IO。

舉個(gè)例子， 如下 SQL：

SELECT emp.age, dept.name FROM emp, dept WHERE emp.dept_id = dept.id

假設(shè)原始數(shù)據(jù)值如下：

image.png

根據(jù)上面延遲物化部分我們可以已知，數(shù)據(jù)的查詢過(guò)程中，我們先抽出 emp 表的 dept_id 和 dept 表的 id 列數(shù)據(jù)，進(jìn)行匹配；并輸出匹配結(jié)果對(duì)應(yīng)原表的位置信息。(黃色文字部分是指 position 指向的值， 在實(shí)際 Join 中不會(huì)出現(xiàn))

會(huì)得到如下的數(shù)據(jù)：

image.png

然后根據(jù)輸出的位置信息，就可以從原始數(shù)據(jù)中抽取 age、name 列的數(shù)據(jù)得到 Join 最后的結(jié)果。

由于上圖右側(cè)輸出無(wú)序，如果回表查必然造成大量隨機(jī) IO ，為了解決這個(gè)問(wèn)題，Jive Join[參考文獻(xiàn) Fast Joins Using Join Indices]采用了對(duì)其進(jìn)行排序之后再查詢，即將隨機(jī) IO 轉(zhuǎn)化為順序 IO 的方法進(jìn)行優(yōu)化。

實(shí)現(xiàn)方式為：在右側(cè)表 position 列上添加一個(gè)額外的列(一個(gè)密集遞增的整數(shù)序列)。

image.png

排序輸出：

image.png

image.png

最后，為了保持原 SQL 語(yǔ)義的一致性，我們對(duì)數(shù)據(jù)結(jié)構(gòu)再次排序，這次是按最初添加到連接輸出的列，將當(dāng)前數(shù)據(jù)結(jié)構(gòu)恢復(fù)為原始連接順序（以便與另一個(gè)表的連接輸出相匹配）：

image.png

6.3 Jive-Join 進(jìn)一步的優(yōu)化思路

• 不需要完全排序整個(gè)列數(shù)據(jù), 來(lái)減少 join 值中列輸出的隨機(jī)訪問(wèn)性能開(kāi)銷

• 存儲(chǔ)介質(zhì)被分成連續(xù)的存儲(chǔ)塊，塊內(nèi)的隨機(jī)訪問(wèn)比跨塊的隨機(jī)訪問(wèn)代價(jià)小得多

• 因此，只需要在存儲(chǔ)（或其近似值）上劃分為可以找到這些位置的塊。在每個(gè)分區(qū)內(nèi)，位置可以保持無(wú)序，因?yàn)榇鎯?chǔ)塊內(nèi)的隨機(jī)訪問(wèn)要便宜得多

• 保證塊維度的順序訪問(wèn)，塊內(nèi)的數(shù)據(jù)可以保持無(wú)序，來(lái)替代全局列按精確的位置順序訪問(wèn)。這個(gè)也就是一個(gè)新的概念: Radix Hash Join：

https://nan01ab.github.io/2019/03/Hash-Joins.html

image.png

總結(jié)

7.1 列式存儲(chǔ)優(yōu)點(diǎn)

數(shù)據(jù)壓縮，確定一列數(shù)據(jù)的規(guī)律

1. 查詢時(shí)可以時(shí)讀的數(shù)據(jù)量更少，在 IO 密集型計(jì)算中獲得更多的性能優(yōu)勢(shì)

2. 相同類型壓縮效率更高

3. 可以針對(duì)不同類型使用不同的壓縮算法。LZ4，run-length encoding，delta encoding

4. 高效的壓縮可以減少磁盤 IO 數(shù)據(jù)量，但是高效的壓縮都必須遵循某種特殊的規(guī)律，比如數(shù)據(jù)的長(zhǎng)度，類型等一致；基于列式的查詢數(shù)據(jù)庫(kù)正好遵循這一點(diǎn)；此外，某些特別的數(shù)據(jù)壓縮格式，比如 RUN-Length 編碼，甚至可以在不做解壓時(shí)便可以對(duì)數(shù)據(jù)過(guò)濾，減少無(wú)關(guān)的 IO

數(shù)據(jù)選擇優(yōu)勢(shì)大

1. 可以選擇特定的列做計(jì)算而不是讀所有列

2. 對(duì)聚合計(jì)算友好

更容易向量化

1. 向量化基于 SIMD (single instruction multiple data) 。對(duì)于現(xiàn)代多核 CPU，其都有能力用一條指令執(zhí)行多條數(shù)據(jù)

2. 向量化對(duì)數(shù)據(jù)格式有要求：要處理的數(shù)據(jù)需要是連續(xù)內(nèi)存；需要明確數(shù)據(jù)類型

3. 執(zhí)行模型要求：數(shù)據(jù)需要按批讀??；函數(shù)的調(diào)用需要明確數(shù)據(jù)類型

4. 列存數(shù)據(jù)庫(kù)本身按列存儲(chǔ)和讀取，可以保證數(shù)據(jù)按批讀取，在內(nèi)存中連續(xù)；可以根據(jù)列的類型定義數(shù)據(jù)讀寫邏輯；函數(shù)按列類型處理

更適合做延遲物化

1. 物化: 將列數(shù)據(jù)轉(zhuǎn)換為可以被計(jì)算或者輸出的行數(shù)據(jù)或者內(nèi)存數(shù)據(jù)結(jié)果的過(guò)程，物化后的數(shù)據(jù)通常可以用來(lái)做數(shù)據(jù)過(guò)濾，聚合計(jì)算，Join

2. 緩存友好；節(jié)省 CPU / 內(nèi)存帶寬；可以利用到執(zhí)行計(jì)劃和算子的優(yōu)化，例如 filter；可以直接在壓縮列做計(jì)算

7.2 寫在最后

實(shí)際上，列存數(shù)據(jù)庫(kù)不只是列式存儲(chǔ)的存儲(chǔ)格式問(wèn)題，底層存儲(chǔ)的變化往往牽一發(fā)而動(dòng)全身，如何適應(yīng)性的修改計(jì)算引擎、存儲(chǔ)引擎、存取方式等來(lái)達(dá)到更高更快的性能，并適應(yīng)不同的 workload 或者硬件發(fā)展的趨勢(shì)，都是基于列式存儲(chǔ)數(shù)據(jù)庫(kù)要關(guān)心的問(wèn)題。