前言

在前三天的文章中，我們介紹了執行一個 SQL 查詢的完整生命週期。今天我們將深入探討 LogicalPlan 的設計模式，理解為什麼它採用 Enum 設計，以及各個變體的具體結構。LogicalPlan 是 DataFusion 查詢優化和執行的核心抽象，認識其設計模式對於整個系統架構的理解會更有幫助。

LogicalPlan 為何設計成 Enum？

統一抽象與類型安全

LogicalPlan 採用 Rust 的 Enum 設計，這是一個非常巧妙的選擇。在關係代數中，查詢計劃本質上就是一棵樹，其中每個節點代表一個關係運算符（如投影、過濾、連接等）。Enum 設計提供了以下優勢：

1. 類型安全：Rust 的編譯器會確保我們處理所有可能的節點類型，避免遺漏任何情況。
2. 模式匹配：可以優雅地使用 match 語句處理不同的節點類型，代碼清晰且易於維護。
3. 統一接口：所有節點類型都實現相同的 trait，提供一致的 API。
4. 記憶體利用效率：Enum 只會為實際使用的變體分配記憶體，避免了虛函數表的開銷。

LogicalPlan 的樹狀結構

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Hash)]
pub enum LogicalPlan {
    /// 投影運算：SELECT 子句
    Projection(Projection),
    /// 過濾運算：WHERE 子句
    Filter(Filter),
    /// 聚合運算：GROUP BY 和聚合函數
    Aggregate(Aggregate),
    /// 連接運算：JOIN 操作
    Join(Join),
    /// 表掃描：FROM 子句
    TableScan(TableScan),
    /// 空關係：特殊情況處理
    EmptyRelation(EmptyRelation),
    // ... 更多變體
}

這種設計讓查詢計劃的樹狀結構變得直觀：每個節點包含其子節點的引用，形成一個完整的查詢樹。

主要變體 (Variants) 介紹

Scan 類：數據源操作

TableScan - 表掃描節點

pub struct TableScan {
    /// 表名引用
    pub table_name: TableReference,
    /// 數據源提供者
    pub source: Arc<dyn TableSource>,
    /// 列投影（選擇哪些列）
    pub projection: Option<Vec<usize>>,
    /// 輸出模式
    pub projected_schema: DFSchemaRef,
    /// 過濾條件（下推到數據源）
    pub filters: Vec<Expr>,
    /// 限制讀取行數
    pub fetch: Option<usize>,
}

TableScan 是查詢樹的葉子節點，負責從數據源讀取數據。它支援列投影和謂詞下推優化，可以將過濾條件直接傳遞給底層數據源，減少 I/O 開銷。

EmptyRelation - 空關係節點

pub struct EmptyRelation {
    /// 是否產生一個佔位行
    pub produce_one_row: bool,
    /// 輸出模式描述
    pub schema: DFSchemaRef,
}

EmptyRelation 用於處理特殊情況，如沒有 FROM 子句的查詢或優化過程中的空結果集。

Transform 類：數據轉換操作

Projection - 投影運算

pub struct Projection {
    /// 表達式列表（SELECT 子句的內容）
    pub expr: Vec<Expr>,
    /// 輸入邏輯計劃
    pub input: Arc<LogicalPlan>,
    /// 輸出模式
    pub schema: DFSchemaRef,
}

Projection 對應 SQL 的 SELECT 子句，負責計算表達式並選擇輸出列。它包含要計算的表達式列表和對輸入計劃的引用。

Filter - 過濾運算

pub struct Filter {
    /// 謂詞表達式（WHERE 條件）
    pub predicate: Expr,
    /// 輸入邏輯計劃
    pub input: Arc<LogicalPlan>,
}

Filter 對應 SQL 的 WHERE 子句，根據布爾表達式過濾行。注意 Filter 沒有自己的 schema 字段，因為它不改變輸出結構，只是過濾行。

Limit - 限制運算

pub struct Limit {
    /// 跳過的行數
    pub skip: Option<usize>,
    /// 獲取的行數
    pub fetch: Option<usize>,
    /// 輸入邏輯計劃
    pub input: Arc<LogicalPlan>,
}

Limit 對應 SQL 的 LIMIT 和 OFFSET 子句，用於分頁查詢。

Join 類：連接操作

Join - 連接運算

pub struct Join {
    /// 左輸入計劃
    pub left: Arc<LogicalPlan>,
    /// 右輸入計劃
    pub right: Arc<LogicalPlan>,
    /// 等值連接條件
    pub on: Vec<(Expr, Expr)>,
    /// 非等值過濾條件
    pub filter: Option<Expr>,
    /// 連接類型（Inner, Left, Right, Full）
    pub join_type: JoinType,
    /// 連接約束
    pub join_constraint: JoinConstraint,
    /// 輸出模式
    pub schema: DFSchemaRef,
    /// 空值相等性處理
    pub null_equality: NullEquality,
}

Join 節點是二元運算符，有兩個子節點。它支持多種連接類型和非等值條件，是查詢優化的重要目標。

CrossJoin - 交叉連接 (笛卡爾積)

pub struct CrossJoin {
    /// 左輸入計劃
    pub left: Arc<LogicalPlan>,
    /// 右輸入計劃
    pub right: Arc<LogicalPlan>,
    /// 輸出模式
    pub schema: DFSchemaRef,
}

Aggregate 類：聚合操作

Aggregate - 聚合運算

pub struct Aggregate {
    /// 輸入邏輯計劃
    pub input: Arc<LogicalPlan>,
    /// 分組表達式（GROUP BY 子句）
    pub group_expr: Vec<Expr>,
    /// 聚合表達式（聚合函數）
    pub aggr_expr: Vec<Expr>,
    /// 聚合輸出模式
    pub schema: DFSchemaRef,
}

Aggregate 對應 SQL 的 GROUP BY 和聚合函數，是分析查詢的核心節點

Window - 窗口函數

pub struct Window {
    /// 輸入邏輯計劃
    pub input: Arc<LogicalPlan>,
    /// 視窗表達式列表
    pub window_expr: Vec<Expr>,
    /// 輸出模式
    pub schema: DFSchemaRef,
}

Window 實現 SQL 的視窗函數，支持 OVER 子句的複雜分析功能。

TreeNode trait 和樹遍歷模式

TreeNode trait 的設計

LogicalPlan 實現了 TreeNode trait，這是一個強大的抽象，提供了統一的樹遍歷和重寫接口：

pub trait TreeNode: Sized {
    /// 深度優先遍歷樹節點
    fn visit<'n, V: TreeNodeVisitor<'n, Node = Self>>(
        &'n self,
        visitor: &mut V,
    ) -> Result<TreeNodeRecursion>;
    
    /// 重寫樹節點
    fn rewrite<F: TreeNodeRewriter<Node = Self>>(
        self,
        rewriter: &mut F,
    ) -> Result<Transformed<Self>>;
    
    /// 訪問子節點
    fn apply_children<'n, F: FnMut(&'n Self) -> Result<TreeNodeRecursion>>(
        &'n self,
        f: F,
    ) -> Result<TreeNodeRecursion>;
}

樹遍歷的實現

在 LogicalPlan 的 TreeNode 實現中，每個變體都需要定義如何訪問其子節點：

impl TreeNode for LogicalPlan {
    fn apply_children<'n, F: FnMut(&'n Self) -> Result<TreeNodeRecursion>>(
        &'n self,
        f: F,
    ) -> Result<TreeNodeRecursion> {
        match self {
            LogicalPlan::Projection(Projection { input, .. }) => {
                f(input.as_ref())
            }
            LogicalPlan::Filter(Filter { input, .. }) => {
                f(input.as_ref())
            }
            LogicalPlan::Join(Join { left, right, .. }) => {
                f(left.as_ref())?;
                f(right.as_ref())
            }
            LogicalPlan::TableScan(_) => Ok(TreeNodeRecursion::Continue),
            // ... 其他變體
        }
    }
}

這種設計讓優化器可以輕鬆地遍歷整個查詢樹，應用各種優化規則。

LogicalPlan 的不可變性設計

為什麼選擇不可變性？

DataFusion 的 LogicalPlan 設計為不可變的，這帶來以下好處：

1. 線程安全：多個線程可以安全地共享同一個計劃，無需額外的同步機制。
2. 優化器安全：優化規則可以安全地創建新的計劃，而不會影響原始計劃。
3. 快取友好：相同的子計劃可以被多個父計劃共享，節省內存。
4. 函數式風格：符合 Rust 的函數式編程理念，代碼更易於理解和測試。

Arc 的使用

LogicalPlan 使用 Arc<LogicalPlan> 來實現共享所有權：

pub struct Projection {
    pub expr: Vec<Expr>,
    pub input: Arc<LogicalPlan>,  // 共享所有權
    pub schema: DFSchemaRef,
}

這帶表多個節點可以引用同一個子計劃，而不需要複製整個計劃樹。當優化器創建新的計劃時，未修改的部分可以繼續共享。

小結

LogicalPlan 的 Enum 設計是 DataFusion 架構的核心，它通過類型安全、模式匹配和不可變性提供了強大而靈活的查詢表示能力。明天我們將繼續探討表達式系統，了解 Expr 的設計和類型推導機制，這將幫助我們更全面地理解 DataFusion 的查詢處理能力。