面向列的 DBMS 如何過濾多個列？

我正在學習面向列的 DBMS /“列”如何在 OLAP 情況下工作。

假設我們有一個包含 3 列的數百萬筆交易timestamp的shop日誌：product``A

SELECT DISTINCT product FROM data
WHERE timestamp BETWEEN 1600010000 AND 1602678400 
           AND shop = 'A'

這將像這樣儲存（誠然，這或多或少是一種抽象）：

timestamp [1600000000, 1600000005, 1600000005, 1600000017, 1600000018, ... ]
shop      [A, A, B, D, C, ...]
product   [X153, S76D, TYA6, LKJ6, SDH7, ...]

對於此查詢：

• 我完全明白我們如何通過時間戳實現快速查找，因為此列已排序：通過 2 次二分搜尋，我們可以找到時間戳 = 1600010000 和 1602678400的索引。通過****少於 30 次幾個字節的讀取操作，它完成了，我們有rowid_start, rowid_end（我不知道它在列的上下文中是否仍然稱為 rowid ）構成了這個時間範圍的邊界。關鍵是我們不必讀取兆字節的數據，而只需讀取幾個字節。
• 問題：那麼，柱狀過濾器如何通過shop = 'A'？我們是否必須讀取範圍中列的每個條目**來測試它是否存在？shop``rowid_start .. rowid_end``A**這可能是數百 MB 或 GB 的數據。

TL;DR：一旦我們過濾了一列，如何在不進行 FULL SCAN 的情況下進行第二列過濾？

有幾個因素可以減少對shop列進行全掃描的恐懼。

1. 每一列的值可以按相同的順序儲存：timestamp的第一個值對應shop中的第一個值，product中的第一個值；第二到第二到第二，依此類推。因此，給出時間戳範圍開始和結束的偏移量的快速查找也給出了商店中相應值的偏移量。如果商店程式碼是固定長度或可以強制為固定長度，則搜尋可以直接跳轉到商店值列表中的該偏移量。更多關於這個很快。
2. 對於面向磁碟而不是完全在記憶體中的系統，可以保存元數據以顯示哪些磁碟文件對應於每列的哪些偏移量。所以 IO 僅限於必要的文件。
3. IO 仍然是面向塊的，所有商店程式碼在磁碟上都是連續的。一次（相對較快的）順序讀取會將大量商店程式碼返回到記憶體中。
4. 這些程式碼可以連續儲存在記憶體中，這對預取和處理器記憶體非常友好。
5. 壓縮。即使商店程式碼很長或長度可變，唯一值也可能相對較少（沃爾瑪的商店少於12,000 家）。可以應用字典壓縮，它將每個長字元串映射到一個更短的固定長度整數。映射表保存一次，這些整數成為列數組中保存的值。遊程編碼可以進一步減小“商店”數組的大小，產生與文件大小、記憶體和 CPU 記憶體使用率有關的良性回饋。

您所說的 RowID 是一種有用的視覺化，但不需要物理實現。由於元組的列以相同的順序儲存，因此偏移量執行 RowID 的功能。對於多謂詞查詢，不太可能為每個謂詞建構表示偏移量的實際整數數組，併計算它們的交集。相反，每個謂詞都會產生一個點陣圖，並且這些點陣圖將被與（或）運算以產生最終的謂詞。每個位代表滿足謂詞的元組的偏移量。

最早的列儲存之一 ( C-Store ) 允許列集的冗餘儲存，每個列集都可以進行不同的排序以促進快速謂詞查找。我知道最近沒有實現此功能的系統，但這是一個有趣的想法。

按列組織的儲存引擎在實現上大不相同，因此幾乎不可能對您的問題做出一般性的回答。在一個非常基本的層面上，雖然帶有適度高級查詢優化器的 DBMS 會實現這樣的東西：

1. 每列的值儲存在一起（如您所述）。每個值都有某種指針（想想 ROWID），該指針對於該特定行的所有列都是通用的；此 ID 允許引擎將為列儲存而分解的行重新組合在一起。
2. 對每個列級謂詞的評估會生成一個與謂詞匹配的“行 ID”列表。在您的情況下，將有兩個列表，一個用於包含匹配"timestamp"值的行，另一個用於shop.
3. 來自多個謂詞的“行 ID”列表合併為一個列表。在您的情況下，這將是兩個列表的交集。
4. 選擇列表中附加列的值（product在您的範例中）使用最終的“行 ID”獲取並返回給客戶端。

要深入了解按列組織的儲存和查詢引擎的一種可能實現，您可以查看Db2 開發人員的這篇文章。

引用自：https://dba.stackexchange.com/questions/282596