前言

上一篇的文章中我們大致瞭解了 DataFusion 專案結構，接下來就要開始就要和大家一起閱讀 DataFusion 的原始碼，深入瞭解查詢引擎內部的邏輯!

舉例來說，當我們呼叫 ctx.sql() 執行以下 SQL 查詢時:

let df = ctx.sql("SELECT id, name FROM users WHERE age > 18").await?;

這行程式碼其實觸發了一連串的轉換過程，而昨天介紹的 datafusion-sql crate 就是負責這個階段的核心模組。今天我們先介紹幾個基礎概念，讓我們繼續看下去吧~

什麼是抽象語法樹 (AST)?

在開始解析流程之前，我們先來看看抽象語法樹(Abstract Syntax Tree, AST) 是甚麼酷東西。 舉凡像是程式語碼或 SQL 語法等語言都是以人類的看得懂的語意設計的，對電腦而言只是一份有各種縮排或括號的文字檔而已，需要將這些文字轉換成電腦可以辨識的資料結構才能進行後續的應用，而 AST 便是其中一種這樣的資料結構。

如同其名，AST 是一個由節點（Node）和邊（Edge）組成的樹。每個節點代表程式碼中的一個語法結構或操作（ex. 一個變數、一個運算符或一個條件判斷）。以一個簡單的 SQL 查詢為例:

SELECT name FROM users WHERE age > 18;

這個查詢的 AST 結構大致如下:

從這樣的結構可以發現原本語句中的空白、分號或是註解縮排等都被忽略了，但原本的語意還是可以透過節點間的關係得知，因此就有利於電腦遍歷這些節點進行語法檢查、編譯成機器碼執行或是轉譯成另一種程式語言等應用。

什麼是邏輯計畫 (LogicalPlan)?

對於一個資料庫系統或查詢引擎而言，將 SQL 轉換成 AST 後的應用會是甚麼呢? 當然就是基於這些 AST 的節點關係規劃一個 “該如何取得或處理這些資料的” 的行動計劃囉! 以上述的查詢為例，我們可以大致產生一個 LogicalPlan:

Projection: users.name [型別: String]
  Filter: users.age > 18 [型別: Int32 > Int32 ✓]
    TableScan: users [來源: /data/users.csv]

從上面的計畫可以理解成以下步驟:

1. 從 /data/users.csv 讀取資料
2. 保留那些 age > 18 的列
3. 從上一步的資料，只取出 name 這一欄

而這樣的 LogicalPlan 就可以繼續往下轉換成 physical plan 實際被電腦執行囉! 至於physical plan是甚麼就留待下回揭曉啦!

今天我們先介紹了 AST 和 LogicalPlan, 明天就來一起閱讀原始碼，看看 DataFusion 是從解析 SQL 到產生 LogicalPlan 的過程。

參考資料

• Apache DataFusion SIGMOD 2024 Paper
• Crafting Interpreters - Representing Code
• How Query Engines Work