書接上文，本篇繼續分享ClickHouse原始碼中一個重要的流，
FilterBlockInputStream的實作，重點在于分析Clickhouse是如何在執行引擎實作向量化的Filter運算子，而利用這個Filter運算子的，就可以實作where, having的資料過濾，
話不多說，準備發車~~ 本文的原始碼分析基于ClickHouse v19.16.2.2的版本，
1.Selection的實作
Selection是關系代數之中重要的一個的一個運算，通常也會用σ符合來selection的實作，
而在SQL陳述句之中，實作Selection運算的便是：where與having，而本文就要從一個簡單的SQL陳述句出發，帶領大家一同梳理Clickhouse的原始碼，來探究它是如何實作選擇運算的，
先看如下的查詢
SELECT * FROM test where a > 3 and b < 1;
這里掃描了test表，并且需要篩選出了a列大于3且b列小于1的行，老規矩，咱們先嘗試打開ClickHouse的Debug日志看一下具體的執行的pipeline，(ClickHouse 20.6之后的版本，終于支持了使用Explain陳述句來查看執行計劃，真是千呼萬喚始出來啊~~）
這里分為了4個流，而咱們需要關注的流就是Filter流，它實作了從存盤引擎的資料讀取資料，并且執行函式運算，并最終實作資料過濾的邏輯，
所以Clickhouse的運算式計算并不單單只由ExpressionBlockInputStream來完成的，而FilterBlockInputStream同樣也需要包含Expression進行運算式的向量化的計算與過濾，
吐槽時間：私以為這樣的實作并不優雅，如果在Filter上層再套一層ExpressionBlockinputStream結構上會更加清晰，不過這樣的實作可能會導致額外的性能損耗，Clickhouse為了實作查詢的高效執行可謂是『喪心病狂』, 后續分析聚合函式的實作時，我們會見到更為Dirty的代碼，
2. FilterBlockInputStream的原始碼剖析
- FilterBlockInputStream readImpl()的實作
直接上代碼看一下FilterBlockInputStream的資料讀取方法吧，這部分代碼比較多，我們拆解出來梳理
/// Determine position of filter column.
header = input->getHeader();
expression->execute(header);
filter_column = header.getPositionByName(filter_column_name);
auto & column_elem = header.safeGetByPosition(filter_column);
/// Isn't the filter already constant?
if (column_elem.column)
constant_filter_description = ConstantFilterDescription(*column_elem.column);
首先，構造FilterBlockInputStream時會首先讀取下一級流的Block Header，通過Header來分析是否有常量列滿足always true或always false的邏輯，來設定ConstantFilterDescription，比如存在全部是null列的過濾列，無論進行什么運算式計算，結果都是false，如果這樣的話，就直接放回空的block給上層流就ok了，
if (expression->checkColumnIsAlwaysFalse(filter_column_name))
return {};
// Function: checkColumnIsAlwaysFalse
for (auto & action : actions)
{
if (action.type == action.APPLY_FUNCTION && action.function_base)
{
auto name = action.function_base->getName();
if ((name == "in" || name == "globalIn")
&& action.result_name == column_name
&& action.argument_names.size() > 1)
{
set_to_check = action.argument_names[1];
}
}
}
接下來決議FilterBlockInputStream之中所有的運算式，查詢是否有in或globalin的函式呼叫，并且其第二個引數set為空，那么同樣表示運算式alwaysFalse也可以直接回傳為空的Block，
比如說有如下查詢：select * from test2 where a in (select a from test2 where a > 10)
而這個子查詢select a from test2 where a > 10回傳的是空集的話，那么就會被直接過濾了，回傳空的block，
接下來進入一個while回圈,不斷從底層的流讀取資料，并進行對應的運算式計算，這里我刪去了一些冗余的代碼:
while (1)
{
res = children.back()->read();
expression->execute(res);
size_t columns = res.columns();
ColumnPtr column = res.safeGetByPosition(filter_column).column;
這里的實作很簡單，就是不停從底層的流讀取資料Block，通過運算式計算生成filter_column列，這個列是一組bool列，標識了對應的行是否還應該存在，
舉個栗子，如果有如下查詢select * from test where a > 10 and b < 2，ClickHouse的運算式會生成如下執行流程如下(注意：ClickHouse遵從函式式編程的邏輯，任意函式呼叫都會生成新的一列)：
1. add const column : 10
2. function call : a > 10 (生成一組新生成的bool列，列名為`a > 10`)
3. remove const column : 10
4. add const column : 2
5. function call : b < 2 (生成一組新生成的bool列，列名為`b < 2`)
6. remove const column : 2
7. call function : a > 10 and b < 2 (生成一組新生成的bool列，列名為`a > 10 and b < 2`)
8. remove column : a > 10
9. remove column : b < 2
而最終新生成的這列就是我們后續需要用到過濾最終結果的filter_column列了，
接下來就進入最核心的一部分代碼了，遍歷Block之中除了const column與filter_column列的所有列，進行實際的資料過濾，IColumn介面中實作了一個介面為filter，也就是說，每一個列型別都需要實作一個過濾方法，用一組bool陣列來過濾列資料，
/** Removes elements that don't match the filter.
* Is used in WHERE and HAVING operations.
* If result_size_hint > 0, then makes advance reserve(result_size_hint) for the result column;
* if 0, then don't makes reserve(),
* otherwise (i.e. < 0), makes reserve() using size of source column.
*/
using Filter = PaddedPODArray<UInt8>;
virtual Ptr filter(const Filter & filt, ssize_t result_size_hint) const = 0;
我們直接跳到子類的實作中來看一下：
template <typename T>
ColumnPtr ColumnVector<T>::filter(const IColumn::Filter & filt, ssize_t result_size_hint) const
{
const UInt8 * filt_pos = filt.data();
const UInt8 * filt_end = filt_pos + size;
const T * data_pos = data.data();
while (filt_pos < filt_end)
{
if (*filt_pos)
res_data.push_back(*data_pos);
++filt_pos;
++data_pos;
}
return res;
}
這之中最為核心的就是這個while回圈，遍歷bool陣列，然后將合法資料塞進一個新的列之中，最終新的列替換舊的列，就完成了一列資料的過濾，之后對于剩余的列依次按照上述流程過一遍就完成了整個block的過濾，這里也可以看到，這個while回圈也是一組很簡單，沒有control flow break的一段代碼，能夠給予編譯器向量化優化的空間很大，當然，ClickHouse還提供了一個手工呼叫向量化API的過濾版本代碼：
#ifdef __SSE2__
/** A slightly more optimized version.
* Based on the assumption that often pieces of consecutive values
* completely pass or do not pass the filter.
* Therefore, we will optimistically check the parts of `SIMD_BYTES` values.
*/
static constexpr size_t SIMD_BYTES = 16;
const __m128i zero16 = _mm_setzero_si128();
const UInt8 * filt_end_sse = filt_pos + size / SIMD_BYTES * SIMD_BYTES;
while (filt_pos < filt_end_sse)
{
int mask = _mm_movemask_epi8(_mm_cmpgt_epi8(_mm_loadu_si128(reinterpret_cast<const __m128i *>(filt_pos)), zero16));
if (0 == mask)
{
/// Nothing is inserted.
}
else if (0xFFFF == mask)
{
res_data.insert(data_pos, data_pos + SIMD_BYTES);
}
else
{
for (size_t i = 0; i < SIMD_BYTES; ++i)
if (filt_pos[i])
res_data.push_back(data_pos[i]);
}
filt_pos += SIMD_BYTES;
data_pos += SIMD_BYTES;
}
#endif
熟悉向量化操作的同學應該會覺得上面的代碼很簡單，每一操作了16個bool陣列，只是筆者比較好奇的是，原則上用avx2或者是avx512應該能夠寫出一批次處理更多資料的向量化代碼，為啥沒做呢？所以可能某些支持了指令集avx2或avx512指令集上編譯的上述代碼，不打開SSE2的編譯宏定義，通過編譯器來實作自動向量化，可能執行速度會更快，
到這里，基本上完成了整個資料的過濾流程，當然，事情還沒結束，我們的filter_column列通常是不需要再保留的，所以最后ClickHouse還會通過一段代碼剔除這個列:
Block FilterBlockInputStream::removeFilterIfNeed(Block && block)
{
if (block && remove_filter)
block.erase(static_cast<size_t>(filter_column));
return std::move(block);
}
3.要點梳理
第二小節梳理完成了一整個filter資料流程的代碼梳理，這里重點梳理一下實作向量化執行的要點：
- ClickHouse的計算是純粹函式式編程式的計算，不會改變原先的列狀態，而是產生一組新的列，我們需要使用這部分新生成
bool列來進一步過濾資料， - 通過對最終統一對
bool列的處理，不僅保證了Cache的親和度，同時也保證了代碼的簡潔，給自動化向量化優化提供了盡可能多的空間，最后手工撰寫了可以用編譯宏打開的向量化代碼，進一步保證了高效的向量化實作， - 短路執行 vs 向量化執行 這部分ClickHouse的運算式過濾的執行邏輯與Doris完全不同，由于Clickhouse需要向量查詢執行，所以函式運算式無法短路執行， 比如，如果你寫
WHERE a > 1 AND b < 2，從上面的分析來看，ClickHouse都兩個運算式都會進行計算，即使是所有的列都不滿足a > 1但是b < 2也會進行計算，而當前Doris目前在存盤引擎的列存過濾的運算式沒有實作向量化過濾，而是通過短路過濾的形式，這兩種方式目前看起來并沒有絕對的優劣：顯然，短路執行 vs 向量化執行的表現，很大程度上性能的表現取決于運算式的過濾率，
4. 小結
好了，到這里也就把ClickHouse函式資料過濾的代碼梳理完了，
所以看到這里，大家相比對于ClickHouse之中如何高效的實作where, having有新的理解，
筆者是一個ClickHouse的初學者，對ClickHouse有興趣的同學，歡迎多多指教，交流，
5. 參考資料
官方檔案
ClickHouse源代碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/265096.html
標籤：其他
上一篇：理解「分布式系統」曾經發生的事情
下一篇：Redis-第十章節-鏈表