使用毫秒延遲查詢 Parquet
已發布 2022 年 12 月 26 日
作者 tustvold 和 alamb
使用毫秒延遲查詢 Parquet
注意：本文最初發布於 InfluxData 部落格。
我們認為直接查詢 Apache Parquet 檔案中的資料，可以達到與大多數專用檔案格式相似甚至更好的儲存效率和查詢效能。雖然這需要大量的工程努力，但 Parquet 開放格式和廣泛生態系統支援的優勢，使其成為廣泛資料系統的顯而易見的選擇。
在本文中，我們解釋了快速查詢 Parquet 格式儲存資料所需的幾種先進技術，這些技術已在 Apache Arrow Rust Parquet 讀取器中實作。這些技術共同使 Rust 實作成為查詢 Parquet 檔案最快（如果不是最快）的實作之一，無論是在本機磁碟還是遠端物件儲存上。它能夠在 幾毫秒內查詢 GB 級的 Parquet 資料。
我們要感謝 InfluxData 對這項工作的支持。InfluxData 對開放原始碼軟體有著深刻且持續的承諾，並且贊助了我們的大部分時間來撰寫這篇部落格文章，以及作為建構 InfluxDB IOx 儲存引擎的一部分的許多貢獻。
背景
Apache Parquet 是一種越來越流行的開放格式，用於儲存 分析型資料集，並且由於其引人注目的組合，已成為具有成本效益、與 DBMS 無關的資料儲存的事實標準
- 高壓縮率
- 適用於 S3 等商業塊儲存
- 廣泛的生態系統和工具支援
- 跨多種不同平台和工具的可移植性
- 支援 任意結構化資料
越來越多的其他系統，例如 DuckDB 和 Redshift 允許直接查詢 Parquet 中儲存的資料，但與其原生（自訂）檔案格式相比，支援通常仍然是次要考量。此類格式包括 DuckDB .duckdb 檔案格式、Apache IOT TsFile、Gorilla 格式 等。
有史以來第一次，以前僅在封閉原始碼商業實作中提供的相同複雜查詢技術，現在可以作為開放原始碼使用。所需的工程能力來自大型、運作良好的開放原始碼專案，這些專案擁有全球貢獻者社群，例如 Apache Arrow 和 Apache Impala。
Parquet 檔案格式
在深入探討有效率地從 Parquet 讀取資料的細節之前，重要的是要了解檔案佈局。檔案格式經過仔細設計，可以快速定位所需的資訊、跳過不相關的部分，並有效率地解碼剩餘的內容。
- Parquet 檔案中的資料被分成稱為
RowGroup的水平切片 - 每個
RowGroup都包含綱要中每個欄位的單個ColumnChunk
例如，下圖說明了一個 Parquet 檔案，其中包含三個欄位「A」、「B」和「C」，儲存在兩個 RowGroup 中，總共有 6 個 ColumnChunk。
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃┏━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━┓ ┃
┃┃┌ ─ ─ ─ ─ ─ ─ ┌ ─ ─ ─ ─ ─ ─ ┐┌ ─ ─ ─ ─ ─ ─ ┃ ┃
┃┃ │ │ ┃ ┃
┃┃│ │ ││ ┃ ┃
┃┃ │ │ ┃ ┃
┃┃│ │ ││ ┃ RowGroup ┃
┃┃ │ │ ┃ 1 ┃
┃┃│ │ ││ ┃ ┃
┃┃ │ │ ┃ ┃
┃┃└ ─ ─ ─ ─ ─ ─ └ ─ ─ ─ ─ ─ ─ ┘└ ─ ─ ─ ─ ─ ─ ┃ ┃
┃┃ColumnChunk 1 ColumnChunk 2 ColumnChunk 3 ┃ ┃
┃┃ (Column "A") (Column "B") (Column "C") ┃ ┃
┃┗━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━┛ ┃
┃┏━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━┓ ┃
┃┃┌ ─ ─ ─ ─ ─ ─ ┌ ─ ─ ─ ─ ─ ─ ┐┌ ─ ─ ─ ─ ─ ─ ┃ ┃
┃┃ │ │ ┃ ┃
┃┃│ │ ││ ┃ ┃
┃┃ │ │ ┃ ┃
┃┃│ │ ││ ┃ RowGroup ┃
┃┃ │ │ ┃ 2 ┃
┃┃│ │ ││ ┃ ┃
┃┃ │ │ ┃ ┃
┃┃└ ─ ─ ─ ─ ─ ─ └ ─ ─ ─ ─ ─ ─ ┘└ ─ ─ ─ ─ ─ ─ ┃ ┃
┃┃ColumnChunk 4 ColumnChunk 5 ColumnChunk 6 ┃ ┃
┃┃ (Column "A") (Column "B") (Column "C") ┃ ┃
┃┗━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━┛ ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
ColumnChunk 的邏輯值使用多種 可用編碼之一寫入到一個或多個 Data Pages 中，這些 Data Pages 在檔案中依序附加。Parquet 檔案的末尾是頁尾，其中包含重要的元資料，例如
- 檔案的綱要資訊，例如欄位名稱和類型
- 檔案中
RowGroup和ColumnChunk的位置
頁尾也可能包含其他專用資料結構
- 每個
ColumnChunk的選用統計資訊，包括最小值/最大值和 Null 計數 - 指向 OffsetIndexes 的選用指標，其中包含每個 Page 的位置
- 指向 ColumnIndex 的選用指標，其中包含每個 Page 的列計數和摘要統計資訊
- 指向 BloomFilterData 的選用指標，它可以快速檢查值是否存在於
ColumnChunk中
例如，先前圖表中的 2 個 Row Group 和 6 個 ColumnChunk 的邏輯結構可以儲存在 Parquet 檔案中，如下圖所示（未按比例）。ColumnChunk 的 Page 位於最前面，後面接著頁尾。資料、編碼方案的有效性以及 Parquet 編碼器的設定決定了每個 ColumnChunk 所需的 Page 數量和大小。在本例中，ColumnChunk 1 需要 2 個 Page，而 ColumnChunk 6 僅需要 1 個 Page。除了其他資訊外，頁尾還包含每個 Data Page 的位置和欄位的類型。
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┃
┃ Data Page for ColumnChunk 1 ("A") ◀─┃─ ─ ─│
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ┃
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┃ │
┃ Data Page for ColumnChunk 1 ("A") ┃
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ┃ │
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┃
┃ Data Page for ColumnChunk 2 ("B") ┃ │
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ┃
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┃ │
┃ Data Page for ColumnChunk 3 ("C") ┃
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ┃ │
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┃
┃ Data Page for ColumnChunk 3 ("C") ┃ │
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ┃
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┃ │
┃ Data Page for ColumnChunk 3 ("C") ┃
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ┃ │
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┃
┃ Data Page for ColumnChunk 4 ("A") ◀─┃─ ─ ─│─ ┐
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ┃
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┃ │ │
┃ Data Page for ColumnChunk 5 ("B") ┃
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ┃ │ │
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┃
┃ Data Page for ColumnChunk 5 ("B") ┃ │ │
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ┃
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┃ │ │
┃ Data Page for ColumnChunk 5 ("B") ┃
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ┃ │ │
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┃
┃ Data Page for ColumnChunk 6 ("C") ┃ │ │
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ┃
┃┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ │ │
┃┃Footer ┃ ┃
┃┃ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ ┃ │ │
┃┃ ┃File Metadata ┃ ┃ ┃
┃┃ ┃ Schema, etc ┃ ┃ ┃ │ │
┃┃ ┃ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ ┃ ┃
┃┃ ┃ ┃Row Group 1 Metadata ┃ ┃ ┃ ┃ │ │
┃┃ ┃ ┃┏━━━━━━━━━━━━━━━━━━━┓ ┃ ┃ ┃ ┃
┃┃ ┃ ┃┃Column "A" Metadata┃ Location of ┃ ┃ ┃ ┃ │ │
┃┃ ┃ ┃┗━━━━━━━━━━━━━━━━━━━┛ first Data ┣ ─ ─ ╋ ╋ ╋ ─ ─
┃┃ ┃ ┃┏━━━━━━━━━━━━━━━━━━━┓ Page, row ┃ ┃ ┃ ┃ │
┃┃ ┃ ┃┃Column "B" Metadata┃ counts, ┃ ┃ ┃ ┃
┃┃ ┃ ┃┗━━━━━━━━━━━━━━━━━━━┛ sizes, ┃ ┃ ┃ ┃ │
┃┃ ┃ ┃┏━━━━━━━━━━━━━━━━━━━┓ min/max ┃ ┃ ┃ ┃
┃┃ ┃ ┃┃Column "C" Metadata┃ values, etc ┃ ┃ ┃ ┃ │
┃┃ ┃ ┃┗━━━━━━━━━━━━━━━━━━━┛ ┃ ┃ ┃ ┃
┃┃ ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┃ ┃ ┃ │
┃┃ ┃ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ ┃ ┃
┃┃ ┃ ┃Row Group 2 Metadata ┃ ┃ ┃ ┃ │
┃┃ ┃ ┃┏━━━━━━━━━━━━━━━━━━━┓ Location of ┃ ┃ ┃ ┃
┃┃ ┃ ┃┃Column "A" Metadata┃ first Data ┃ ┃ ┃ ┃ │
┃┃ ┃ ┃┗━━━━━━━━━━━━━━━━━━━┛ Page, row ┣ ─ ─ ╋ ╋ ╋ ─ ─ ─ ─
┃┃ ┃ ┃┏━━━━━━━━━━━━━━━━━━━┓ counts, ┃ ┃ ┃ ┃
┃┃ ┃ ┃┃Column "B" Metadata┃ sizes, ┃ ┃ ┃ ┃
┃┃ ┃ ┃┗━━━━━━━━━━━━━━━━━━━┛ min/max ┃ ┃ ┃ ┃
┃┃ ┃ ┃┏━━━━━━━━━━━━━━━━━━━┓ values, etc ┃ ┃ ┃ ┃
┃┃ ┃ ┃┃Column "C" Metadata┃ ┃ ┃ ┃ ┃
┃┃ ┃ ┃┗━━━━━━━━━━━━━━━━━━━┛ ┃ ┃ ┃ ┃
┃┃ ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┃ ┃ ┃
┃┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┃ ┃
┃┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
在建立 Parquet 檔案時，有許多重要的準則需要考慮，例如如何最佳地排序/叢集資料並將其結構化為 RowGroup 和 Data Pages。此類「物理設計」考量因素很複雜，值得撰寫一系列專門的文章，但本文不加以討論。相反，我們專注於如何使用可用的結構來使查詢非常快速。
最佳化查詢
在任何查詢處理系統中，以下技術通常可以提高效能
- 減少必須從次要儲存裝置傳輸以進行處理的資料（減少 I/O）
- 減少解碼資料的計算負載（減少 CPU）
- 交錯/管線化資料的讀取和解碼（提高平行處理能力）
相同的原則適用於查詢 Parquet 檔案，如下所述
解碼最佳化
Parquet 透過使用 複雜的編碼技術（例如執行長度壓縮、字典編碼、Delta 編碼等）實現令人印象深刻的壓縮率。因此，CPU 密集型的解碼任務可能會佔據查詢延遲的主要部分。Parquet 讀取器可以使用多種技術來提高此任務的延遲和吞吐量，正如我們在 Rust 實作中所做的那樣。
向量化解碼
大多數分析系統一次解碼多個值到欄狀記憶體格式（例如 Apache Arrow），而不是逐列處理資料。這通常稱為向量化或欄狀處理，並且是有益的，因為它
- 分攤了切換要解碼的欄位類型時的分派開銷
- 透過從
ColumnChunk讀取連續值來改善快取局部性 - 通常允許在單個指令中解碼多個值。
- 透過單個大型分配避免許多小的堆積分配，從而為字串和位元組陣列等可變長度類型節省大量成本
因此，Rust Parquet 讀取器實作了專用解碼器，用於將 Parquet 直接讀取到 欄狀記憶體格式（Arrow 陣列）。
串流解碼
在跨 ColumnChunk 的 Page 中儲存哪些列之間沒有關係。例如，第 10,000 列的邏輯值可能在欄位 A 的第一個 Page 中，而在欄位 B 的第三個 Page 中。
向量化解碼最簡單的方法，也是 Parquet 解碼器最初經常實作的方法，是一次解碼整個 RowGroup（或 ColumnChunk）。
但是，鑑於 Parquet 的高壓縮率，單個 RowGroup 很可能包含數百萬列。一次解碼這麼多列並非最佳，因為它
- 需要大量的中間 RAM：針對處理最佳化的典型記憶體內格式（例如 Apache Arrow）所需的記憶體遠遠超過其 Parquet 編碼形式。
- 增加查詢延遲：後續處理步驟（例如篩選或聚合）只能在整個
RowGroup（或ColumnChunk）解碼完成後才能開始。
因此，最好的 Parquet 讀取器支援「串流」資料輸出，方法是按需產生可配置大小的列批次。批次大小必須足夠大，才能分攤解碼開銷，但又必須足夠小，才能實現有效率的記憶體使用，並允許下游處理在解碼後續批次的同時並行開始。
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┃
┃ Data Page for ColumnChunk 1 │◀┃─ ┌── ─── ─── ─── ─── ┐
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┃ │ ┏━━━━━━━┓ ┌ ─ ┐ ┌ ─ ┐ ┌ ─ ┐ │
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┃ ┃ ┃ │ │
┃ Data Page for ColumnChunk 1 │ ┃ │ ┃ ┃ ─ ▶│ │ │ │ │ │ │
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┃ ─ ─┃ ┃─ ┤ │ ─ ─ ─ ─ ─ ─ │
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┃ │ ┃ ┃ A B C │
┃ Data Page for ColumnChunk 2 │◀┃─ ┗━━━━━━━┛ │ └── ─── ─── ─── ─── ┘
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┃ │ Parquet
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┃ Decoder │ ...
┃ Data Page for ColumnChunk 3 │ ┃ │
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┃ │ ┌── ─── ─── ─── ─── ┐
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┃ │ ┌ ─ ┐ ┌ ─ ┐ ┌ ─ ┐ │
┃ Data Page for ColumnChunk 3 │◀┃─ │ │ │
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┃ ─ ▶│ │ │ │ │ │ │
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┃ │ ─ ─ ─ ─ ─ ─ │
┃ Data Page for ColumnChunk 3 │ ┃ A B C │
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┃ └── ─── ─── ─── ─── ┘
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
Parquet file Smaller in memory
batches for
processing
雖然串流並不是一個難以解釋的功能，但解碼的狀態性質，尤其是跨多個欄位和 任意巢狀資料，其中列和值之間的關係不是固定的，這需要 複雜的中間緩衝和大量的工程努力才能正確處理。
字典保留
字典編碼，也稱為 類別編碼，是一種技術，其中欄位中的每個值都不是直接儲存的，而是儲存單獨列表（稱為「字典」）中的索引。對於具有重複值（低 基數）的欄位，此技術實現了 第三正規化 的許多優點，並且對於字串欄位（例如「城市」）尤其有效。
ColumnChunk 中的第一個 Page 可以選擇性地是字典 Page，其中包含欄位類型的值列表。然後，此 ColumnChunk 中的後續 Page 可以編碼到此字典中的索引，而不是直接編碼值。
鑑於此編碼的有效性，如果 Parquet 解碼器只是將字典資料解碼為原生類型，它將重複且無效率地複製相同的值，這對於字串資料來說尤其是一場災難。為了有效率地處理字典編碼的資料，必須在解碼期間保留編碼。方便的是，許多欄狀格式（例如 Arrow DictionaryArray）都支援此類相容的編碼。
保留字典編碼在讀取到 Arrow 陣列時會大幅提高效能，在某些情況下超過 60 倍，並且使用的記憶體也顯著減少。
保留字典的主要複雜因素是字典是按 ColumnChunk 儲存的，因此字典在 RowGroup 之間會發生變化。讀取器必須自動重新計算跨多個 RowGroup 的批次的字典，同時還要針對批次大小均勻劃分到每個 RowGroup 的列數的情況進行最佳化。此外，欄位可能僅 部分字典編碼，這進一步使實作複雜化。有關此技術及其複雜性的更多資訊，請參閱關於將此技術應用於 C++ Parquet 讀取器的 部落格文章。
投影下推
最基本的 Parquet 最佳化，也是最常針對 Parquet 檔案描述的最佳化是投影下推，它可以減少 I/O 和 CPU 需求。此處的投影是指「選擇部分欄位而不是全部欄位」。鑑於 Parquet 組織資料的方式，僅讀取和解碼參考欄位所需的 ColumnChunk 非常簡單。
例如，考慮以下形式的 SQL 查詢
SELECT B from table where A > 35
此查詢僅需要欄位 A 和 B（而不是 C）的資料，並且投影可以「下推」到 Parquet 讀取器。
具體來說，使用頁尾中的資訊，Parquet 讀取器可以完全跳過提取 (I/O) 和解碼 (CPU) 儲存欄位 C 資料的 Data Pages（在我們的範例中為 ColumnChunk 3 和 ColumnChunk 6）。
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐┃
┌─────▶ Data Page for ColumnChunk 1 ("A") ┃
│ ┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘┃
│ ┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐┃
├─────▶ Data Page for ColumnChunk 1 ("A") ┃
│ ┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘┃
│ ┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐┃
├─────▶ Data Page for ColumnChunk 2 ("B") ┃
│ ┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘┃
│ ┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐┃
│ ┃ Data Page for ColumnChunk 3 ("C") ┃
│ ┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘┃
A query that │ ┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐┃
accesses only │ ┃ Data Page for ColumnChunk 3 ("C") ┃
columns A and B │ ┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘┃
can read only the │ ┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐┃
relevant pages, ─────┤ ┃ Data Page for ColumnChunk 3 ("C") ┃
skipping any Data │ ┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘┃
Page for column C │ ┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐┃
├─────▶ Data Page for ColumnChunk 4 ("A") ┃
│ ┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘┃
│ ┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐┃
├─────▶ Data Page for ColumnChunk 5 ("B") ┃
│ ┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘┃
│ ┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐┃
├─────▶ Data Page for ColumnChunk 5 ("B") ┃
│ ┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘┃
│ ┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐┃
└─────▶ Data Page for ColumnChunk 5 ("B") ┃
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘┃
┃┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐┃
┃ Data Page for ColumnChunk 6 ("C") ┃
┃└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
述詞下推
與投影下推類似，述詞下推也避免從 Parquet 檔案中提取和解碼資料，但它使用篩選運算式來實現。此技術通常需要與查詢引擎（例如 DataFusion）更緊密地整合，以確定有效的述詞並在掃描期間評估它們。不幸的是，如果沒有仔細的 API 設計，Parquet 解碼器和查詢引擎最終可能會緊密耦合，從而阻止重複使用（例如，Cloudera Parquet 述詞下推文件中有不同的 Impala 和 Spark 實作）。Rust Parquet 讀取器使用 RowSelection API 來避免這種耦合。
RowGroup 修剪
許多基於 Parquet 的查詢引擎支援的最簡單形式的述詞下推是使用儲存在頁尾中的統計資訊來跳過整個 RowGroup。我們將此操作稱為 RowGroup 修剪，它類似於許多經典資料倉儲系統中的 分區修剪。
對於上面的範例查詢，如果特定 RowGroup 中 A 的最大值小於 35，則解碼器可以跳過提取和解碼來自該整個 RowGroup 的任何 ColumnChunk。
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃Row Group 1 Metadata ┃
┃ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃
┃ ┃Column "A" Metadata Min:0 Max:15 ┃◀╋ ┐
┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┃ Using the min
┃ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ │ and max values
┃ ┃Column "B" Metadata ┃ ┃ from the
┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┃ │ metadata,
┃ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ RowGroup 1 can
┃ ┃Column "C" Metadata ┃ ┃ ├ ─ ─ be entirely
┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┃ skipped
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ │ (pruned) when
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ searching for
┃Row Group 2 Metadata ┃ │ rows with A >
┃ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ 35,
┃ ┃Column "A" Metadata Min:10 Max:50 ┃◀╋ ┘
┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┃
┃ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃
┃ ┃Column "B" Metadata ┃ ┃
┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┃
┃ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃
┃ ┃Column "C" Metadata ┃ ┃
┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
請注意，基於最小值和最大值的修剪對於許多資料佈局和欄位類型有效，但並非全部有效。具體來說，對於具有許多不同的虛擬隨機值（例如識別碼或 UUID）的欄位，它並不是那麼有效。值得慶幸的是，對於此用例，Parquet 也支援每個 ColumnChunk 的 Bloom Filters。我們正在積極努力在 Apache Rust 的實作中新增 Bloom Filter 支援。
Page 修剪
更複雜形式的述詞下推使用頁尾元資料中的選用 頁面索引 來排除整個 Data Pages。解碼器僅解碼來自其他欄位的相應列，通常會跳過整個 Page。
由於各種原因，不同 ColumnChunk 中的 Page 通常包含不同數量的列，這一事實使此最佳化變得複雜。雖然頁面索引可以識別一個欄位中需要的 Page，但從一個欄位修剪 Page 並不會立即排除其他欄位中的整個 Page。
Page 修剪按如下方式進行
- 將述詞與頁面索引結合使用，以識別要跳過的 Page
- 使用位移索引確定哪些列範圍對應於未跳過的 Page
- 計算跨未跳過 Page 的範圍的交集，並且僅解碼這些列
最後一點非常難以實作，尤其是對於巢狀列表，其中 單個列可能對應於多個值。幸運的是，Rust Parquet 讀取器在內部隱藏了這種複雜性，並且可以解碼任意 RowSelections。
例如，要掃描欄位 A 和 B，它們儲存在 5 個 Data Pages 中，如下圖所示
如果述詞是 A > 35，
- Page 1 使用頁面索引修剪（最大值為
20），留下 [200->onwards] 的 RowSelection， - Parquet 讀取器完全跳過 Page 3（因為它的最後一列索引是
99） - （僅）透過讀取 Page 2、4 和 5 來讀取相關列。
如果述詞改為 A > 35 AND B = "F"，則頁面索引甚至更有效
- 使用
A > 35，與之前一樣產生 [200->onwards] 的 RowSelection - 在剩餘的 B 的 Page 4 和 Page 5 上使用
B = "F"，產生 [100-244] 的 RowSelection - 相交兩個 RowSelection 會留下組合的 RowSelection
[200-244] - Parquet 讀取器僅解碼 Page 2 和 Page 4 中的那 50 列。
┏━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┃
┃ ┌──────────────┐ │ ┌──────────────┐ │ ┃
┃ │ │ │ │ │ │ ┃
┃ │ │ │ │ Page │ │
│ │ │ │ │ 3 │ ┃
┃ │ │ │ │ min: "A" │ │ ┃
┃ │ │ │ │ │ max: "C" │ ┃
┃ │ Page │ │ │ first_row: 0 │ │
│ │ 1 │ │ │ │ ┃
┃ │ min: 10 │ │ └──────────────┘ │ ┃
┃ │ │ max: 20 │ │ ┌──────────────┐ ┃
┃ │ first_row: 0 │ │ │ │ │
│ │ │ │ │ Page │ ┃
┃ │ │ │ │ 4 │ │ ┃
┃ │ │ │ │ │ min: "D" │ ┃
┃ │ │ │ │ max: "G" │ │
│ │ │ │ │first_row: 100│ ┃
┃ └──────────────┘ │ │ │ │ ┃
┃ │ ┌──────────────┐ │ │ │ ┃
┃ │ │ │ └──────────────┘ │
│ │ Page │ │ ┌──────────────┐ ┃
┃ │ 2 │ │ │ │ │ ┃
┃ │ │ min: 30 │ │ │ Page │ ┃
┃ │ max: 40 │ │ │ 5 │ │
│ │first_row: 200│ │ │ min: "H" │ ┃
┃ │ │ │ │ max: "Z" │ │ ┃
┃ │ │ │ │ │first_row: 250│ ┃
┃ └──────────────┘ │ │ │ │
│ │ └──────────────┘ ┃
┃ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ┃
┃ ColumnChunk ColumnChunk ┃
┃ A B
━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━━ ━━┛
從 Arrow C++ 以及擴展 pyarrow/pandas 讀取和寫入這些索引的支援在 PARQUET-1404 中追蹤。
延遲實體化
前兩種形式的述詞下推僅在 RowGroup、ColumnChunk 和 Data Pages 的元資料上運作，在解碼值之前。但是，相同的技術也擴展到一個或多個欄位的值在解碼它們之後但在解碼其他欄位之前，這通常稱為「延遲實體化」。
當以下情況時，此技術尤其有效
- 述詞非常具有選擇性，即篩選掉大量列
- 每列都很大，原因是列寬（例如 JSON blobs）或欄位很多
- 選定的資料叢集在一起
- 述詞所需的欄位解碼成本相對較低，例如 PrimitiveArray / DictionaryArray
SPARK-36527 和 Impala 中有關於此技術優勢的更多討論。
例如，給定上述述詞 A > 35 AND B = "F"，其中引擎使用頁面索引來確定只有 [100-244] 的 RowSelection 中的 50 列可能匹配，使用延遲實體化，Parquet 解碼器
- 解碼欄位 A 的 50 個值
- 在這些 50 個值上評估
A > 35 - 在本例中，只有 5 列通過，產生 RowSelection
- RowSelection[205-206]
- RowSelection[238-240]
- 僅解碼這些選定項目的欄位 B 的 5 列
Row Index
┌────────────────────┐ ┌────────────────────┐
200 │ 30 │ │ "F" │
└────────────────────┘ └────────────────────┘
... ...
┌────────────────────┐ ┌────────────────────┐
205 │ 37 │─ ─ ─ ─ ─ ─▶│ "F" │
├────────────────────┤ ├────────────────────┤
206 │ 36 │─ ─ ─ ─ ─ ─▶│ "G" │
└────────────────────┘ └────────────────────┘
... ...
┌────────────────────┐ ┌────────────────────┐
238 │ 36 │─ ─ ─ ─ ─ ─▶│ "F" │
├────────────────────┤ ├────────────────────┤
239 │ 36 │─ ─ ─ ─ ─ ─▶│ "G" │
├────────────────────┤ ├────────────────────┤
240 │ 40 │─ ─ ─ ─ ─ ─▶│ "G" │
└────────────────────┘ └────────────────────┘
... ...
┌────────────────────┐ ┌────────────────────┐
244 │ 26 │ │ "D" │
└────────────────────┘ └────────────────────┘
Column A Column B
Values Values
在某些情況下（例如我們的範例，其中 B 儲存單字元值），延遲實體化機制的成本可能超過解碼的節省。但是，當滿足上面列出的一些條件時，節省量可能相當可觀。查詢引擎必須決定要下推哪些述詞以及以何種順序應用它們才能獲得最佳結果。
雖然這超出了本文檔的範圍，但相同的技術也可以應用於多個述詞以及多個欄位上的述詞。有關更多資訊，請參閱 Parquet crate 中的 RowFilter 介面，以及 DataFusion 中的 row_filter 實作。
I/O 下推
雖然 Parquet 是為有效率地存取 HDFS 分散式檔案系統 而設計的，但它與 AWS S3 等商業塊儲存系統配合得非常好，因為它們具有非常相似的特性
- 相對緩慢的「隨機存取」讀取：每次請求讀取大型 (MB) 資料區段比發出許多請求讀取較小部分更有效率
- 檢索第一個位元組之前的顯著延遲
- 高每次請求成本：通常按每次請求收費，無論讀取的位元組數多少，這鼓勵減少請求次數，每次請求讀取較大的連續資料區段。
為了從此類系統中最佳地讀取資料，Parquet 讀取器必須
- 最大限度地減少 I/O 請求的數量，同時也應用各種下推技術，以避免提取大量未使用的資料。
- 與適當的任務排程機制整合，以交錯 I/O 和對提取的資料進行處理，以避免管線瓶頸。
由於這些是大量的工程和整合挑戰，因此許多 Parquet 讀取器仍然需要將檔案完整提取到本機儲存。
為了處理檔案而提取整個檔案並非理想選擇，原因如下
- 高延遲：解碼必須在整個檔案提取完成後才能開始（Parquet 元資料位於檔案末尾，因此解碼器必須先看到末尾，然後才能解碼其餘部分）
- 浪費工作：提取整個檔案會提取所有必要的資料，但也可能會提取大量不必要的資料，這些資料在讀取頁尾後將被跳過。這不必要地增加了成本。
- 需要昂貴的「本機連接」儲存裝置（或記憶體）：許多雲端環境不提供具有本機連接儲存裝置的運算資源，它們要么依賴昂貴的網路區塊儲存裝置（例如 AWS EBS），要么將本機儲存裝置限制為某些類型的 VM。
避免需要緩衝整個檔案需要一個複雜的 Parquet 解碼器，該解碼器與 I/O 子系統整合，可以最初提取和解碼元資料，然後針對相關資料區塊進行範圍提取，並與 Parquet 資料的解碼交錯進行。此最佳化需要仔細的工程設計，以從物件儲存中提取足夠大的資料區塊，以使每次請求的開銷不會超過減少傳輸位元組數所帶來的增益。SPARK-36529 更詳細地描述了循序處理的挑戰。
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│
│
Step 1: Fetch │
Parquet Parquet metadata
file on ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━▼━━━━━━━┓
Remote ┃ ▒▒▒▒▒▒▒▒▒▒ ▒▒▒▒▒▒▒▒▒▒ ░░░░░░░░░░ ┃
Object ┃ ▒▒▒data▒▒▒ ▒▒▒data▒▒▒ ░metadata░ ┃
Store ┃ ▒▒▒▒▒▒▒▒▒▒ ▒▒▒▒▒▒▒▒▒▒ ░░░░░░░░░░ ┃
┗━━━━━━━━━━━▲━━━━━━━━━━━━━━━━━━━━━▲━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
│ └ ─ ─ ─
│
│ Step 2: Fetch only
─ ─ ─ ─ ─ ─ ─ ─ ─ relevant data blocks
此圖表中未包含的詳細資訊包括合併請求和確保實際實作所需的最小請求大小。
Rust Parquet crate 提供了一個非同步 Parquet 讀取器，可以有效率地從任何 AsyncFileReader 讀取資料，該讀取器
- 有效率地從任何支援範圍請求的儲存媒體讀取資料
- 與 Rust 的 futures 生態系統整合，以避免封鎖執行緒等待網路 I/O 並且可以輕鬆地交錯 CPU 和網路
- 同時請求多個範圍，以允許實作合併相鄰範圍、並行提取範圍等。
- 使用先前描述的下推技術來消除盡可能提取資料的情況
- 輕鬆與 Apache Arrow object_store crate 整合，您可以在此處閱讀更多相關資訊
為了讓您了解可能實現的效果，下圖顯示了從遠端檔案提取頁尾元資料、使用該元資料確定要讀取的 Data Pages，然後同時提取資料和解碼的時間軸。為了匹配網路延遲、頻寬和可用 CPU，此過程通常必須一次針對多個檔案完成。
begin
metadata read of end read
read ─ ─ ─ ┐ data of data │
begin complete block block
read of │ │ │ │
metadata ─ ─ ─ ┐ At any time, there are
│ │ │ │ │ multiple network
│ ▼ ▼ ▼ ▼ requests outstanding to
file 1 │ ░░░░░░░░░░ ▒▒▒read▒▒▒ ▒▒▒read▒▒▒ │ hide the individual
│ ░░░read░░░ ▒▒▒data▒▒▒ ▒▒▒data▒▒▒ request latency
│ ░metadata░ ▓▓decode▓▓
│ ░░░░░░░░░░ ▓▓▓data▓▓▓
│ │
│
│ ░░░░░░░░░░ ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒read▒▒▒▒│▒▒▒▒▒▒▒▒▒▒▒▒▒▒
file 2 │ ░░░read░░░ ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒data▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
│ ░metadata░ │ ▓▓▓▓▓decode▓▓▓▓▓▓
│ ░░░░░░░░░░ ▓▓▓▓▓▓data▓▓▓▓▓▓▓
│ │
│
│ ░░│░░░░░░░ ▒▒▒read▒▒▒ ▒▒▒▒read▒▒▒▒▒
file 3 │ ░░░read░░░ ▒▒▒data▒▒▒ ▒▒▒▒data▒▒▒▒▒ ...
│ ░m│tadata░ ▓▓decode▓▓
│ ░░░░░░░░░░ ▓▓▓data▓▓▓
└───────────────────────────────────────┼──────────────────────────────▶Time
│
結論
我們希望您喜歡閱讀有關 Parquet 檔案格式以及用於快速查詢 Parquet 檔案的各種技術的文章。
我們認為，大多數 Parquet 開放原始碼實作沒有本文中描述的廣泛功能的原因是，這需要巨大的努力，而這以前只有在資金充足的商業企業中才有可能實現，這些企業將其實作保持為封閉原始碼。
但是，隨著 Apache Arrow 社群（包括 Rust 從業者和更廣泛的 Arrow 社群）的成長和品質的提高，我們協作和建構尖端開放原始碼實作的能力令人振奮且非常滿意。本部落格中描述的技術是許多工程師在公司、業餘愛好者和世界各地多個儲存庫（尤其是 Apache Arrow DataFusion、Apache Arrow 和 Apache Arrow Ballista）中貢獻的成果。
如果您有興趣加入 DataFusion 社群，請取得聯繫。