前言

昨天我們聊了 LogicalPlan 的設計模式和表達式系統，今天我們要深入 DataFusion 的優化器框架。雖然第10天我們已經簡單介紹過優化規則，但今天我們要挖得更深一些，看看 OptimizerRule 這個 trait 背後的設計哲學，以及優化器是如何協調這些規則的。

為什麼要深入了解優化器框架？因為它決定了你的查詢能跑多快。一個設計良好的優化器框架，能讓新的優化規則輕鬆集成，讓規則之間協調工作，最終讓 SQL 查詢顯著提升效能。

OptimizerRule Trait 的設計哲學

為什麼要設計成 Trait？

從 DataFusion 的原始碼可以發現所有的優化規則都實現了同一個 OptimizerRule trait。

pub trait OptimizerRule: Debug {
    fn name(&self) -> &str;
    fn apply_order(&self) -> Option<ApplyOrder> { None }
    fn rewrite(&self, plan: LogicalPlan, config: &dyn OptimizerConfig) -> Result<Transformed<LogicalPlan>>;
}

這樣的的設計有以下優點：

1. 統一性 - 所有規則都遵循相同的接口，優化器不需要知道具體是哪些規則，只要知道它們都遵循這個契約就行。這讓添加新規則變得超級簡單。

2. 可測試性 - 每個規則都可以獨立測試，不需要依賴整個優化器。你可以寫個簡單的測試，給規則一個 LogicalPlan，看看它會不會正確地優化。

3. 可組合性 - 規則可以任意組合，你可以只啟用某些規則，或者調整規則的順序，這在調優時非常有用。

ApplyOrder 的智慧

ApplyOrder 這個枚舉看起來很簡單，但其實蘊含著深刻的優化策略：

pub enum ApplyOrder {
    TopDown,    // 自頂向下
    BottomUp,   // 自底向上
}

TopDown 策略就像是「先下手為強」。比如謂詞下推規則，它需要盡快把過濾條件推到數據源，減少需要處理的數據量。所以它選擇 TopDown，在處理子節點之前就先把過濾條件推下去。

BottomUp 策略則是「先了解情況再行動」。比如常數折疊規則，它需要先知道子表達式的值，才能決定如何簡化。所以它選擇 BottomUp，等子節點都處理完了，再進行常數折疊。

這種設計讓每個規則都能選擇最適合自己的執行策略，而不是被強制使用同一種方式。

優化器執行引擎的內部機制

Fixed-Point Iteration 的巧妙之處

優化器使用固定點迭代（Fixed-Point Iteration）來確保所有可能的優化都被應用。聽起來很高大上，其實就是「一直重複，直到沒法再優化為止」。

let mut i = 0;
while i < options.optimizer.max_passes {
    for rule in &self.rules {
        // 應用規則...
    }
    i += 1;
}

為什麼需要這樣做？因為規則之間可能會相互影響。比如：

1. 規則A把一個複雜表達式簡化了
2. 規則B發現簡化後的表達式可以進一步下推
3. 規則C發現下推後又有新的優化機會

如果只跑一遍，就會錯過這些連鎖優化效果。

規則調度的藝術

優化器不是簡單地按順序執行規則，而是根據每個規則的 apply_order 來決定如何調度：

match rule.apply_order() {
    Some(apply_order) => new_plan.rewrite_with_subqueries(
        &mut Rewriter::new(apply_order, rule.as_ref(), config),
    ),
    None => rule.rewrite(new_plan, config),
}

這裡有個有趣的設計：如果規則指定了 apply_order，優化器會幫它處理遞歸；如果沒有指定，規則就得自己處理遞歸。這給了規則實現者更多的靈活性。

規則間的依賴關係和執行順序

為什麼順序很重要？

DataFusion 的預設規則順序不是隨便排的，而是經過精心設計的：

let rules = vec![
    Arc::new(EliminateNestedUnion::new()),           // 1. 先清理結構
    Arc::new(SimplifyExpressions::new()),            // 2. 簡化表達式
    Arc::new(ReplaceDistinctWithAggregate::new()),   // 3. 重寫操作
    Arc::new(EliminateJoin::new()),                  // 4. 消除不必要的 Join
    // ... 更多規則
    Arc::new(OptimizeProjections::new()),            // 最後：優化投影
];

為什麼要這樣排？

1. 先簡化，後優化 - SimplifyExpressions 在早期執行，把複雜表達式簡化，為後續規則創造更好的條件。

2. 先消除，後下推 - EliminateFilter 在 PushDownFilter 之前執行，先把明顯沒用的過濾器去掉，再考慮下推。

3. 先下推限制，後下推過濾 - PushDownLimit 在 PushDownFilter 之前執行，因為限制條件通常比過濾條件更「急迫」。

4. 最後優化投影 - OptimizeProjections 在最後執行，清理所有不必要的列。

規則間的隱式依賴

有些規則之間有隱式的依賴關係，雖然沒有明確聲明，但順序錯了就會出問題：

• EliminateFilter 依賴 SimplifyExpressions - 需要先簡化表達式，才能識別出 WHERE TRUE 或 WHERE FALSE 這樣的特殊情況
• PushDownFilter 依賴 EliminateFilter - 需要先去掉沒用的過濾器，再考慮下推
• OptimizeProjections 依賴所有其他規則 - 需要等所有優化都做完，再清理不必要的列

自定義優化規則的開發

寫一個簡單的優化規則

假設我們想寫一個規則，把 SELECT * 替換成具體的列名。這在實際應用中很有用，因為 SELECT * 會讀取所有列，包括不需要的。

#[derive(Default, Debug)]
pub struct ExpandStarRule;

impl OptimizerRule for ExpandStarRule {
    fn name(&self) -> &str {
        "expand_star"
    }

    fn apply_order(&self) -> Option<ApplyOrder> {
        Some(ApplyOrder::TopDown)  // 自頂向下，盡早處理
    }

    fn rewrite(
        &self,
        plan: LogicalPlan,
        _config: &dyn OptimizerConfig,
    ) -> Result<Transformed<LogicalPlan>> {
        match plan {
            LogicalPlan::Projection(proj) => {
                // 檢查是否有 SELECT * 的情況
                if self.has_star_projection(&proj.expr) {
                    // 展開為具體的列
                    let expanded_exprs = self.expand_star(&proj.expr, proj.input.schema())?;
                    let new_proj = Projection::try_new(expanded_exprs, proj.input)?;
                    Ok(Transformed::yes(LogicalPlan::Projection(new_proj)))
                } else {
                    Ok(Transformed::no(plan))
                }
            }
            _ => Ok(Transformed::no(plan)),
        }
    }
}

集成到優化器中

寫好規則後，需要把它加到優化器中：

let mut rules = Optimizer::new().rules;
rules.insert(0, Arc::new(ExpandStarRule::new()));  // 插入到開頭
let custom_optimizer = Optimizer::with_rules(rules);

測試你的規則

測試優化規則其實很簡單：

#[test]
fn test_expand_star() {
    let table_scan = test_table_scan().unwrap();
    let plan = LogicalPlanBuilder::from(table_scan)
        .project(vec![col("*")])?  // SELECT *
        .build()?;

    let optimizer = Optimizer::with_rules(vec![Arc::new(ExpandStarRule::new())]);
    let optimized = optimizer.optimize(plan, &OptimizerContext::new(), |_, _| {})?;

    // 檢查是否正確展開為具體的列
    assert!(matches!(optimized, LogicalPlan::Projection(_)));
}

優化器的配置和調優

調整最大迭代次數

有時候查詢很複雜，需要更多輪優化：

let config = OptimizerContext::new()
    .with_max_passes(32);  // 預設是 16

跳過失敗的規則

在開發階段，你可能不想因為一個規則出錯就讓整個優化失敗：

let options = ConfigOptions::new()
    .with_optimizer_skip_failed_rules(true);

自定義規則集合

根據不同的使用場景，你可能需要不同的規則集合：

// 只保留基本的優化規則，適合簡單查詢
let basic_rules = vec![
    Arc::new(SimplifyExpressions::new()),
    Arc::new(PushDownFilter::new()),
    Arc::new(OptimizeProjections::new()),
];

// 完整的規則集合，適合複雜查詢
let full_rules = Optimizer::new().rules;

進階技巧與最佳實務

規則的效能考量

寫優化規則時，要注意效能：

1. 避免不必要的克隆 - 如果計劃沒有改變，直接返回 Transformed::no(plan)
2. 早期退出 - 如果規則不適用，盡快返回
3. 避免深度遞歸 - 對於很深的計劃樹，考慮使用迭代而不是遞歸

調試優化規則

使用 EXPLAIN 來觀察規則的效果：

EXPLAIN (VERBOSE, FORMAT TEXT) 
SELECT * FROM table1 WHERE column1 > 100;

這會顯示優化前後的計劃，你可以看到你的規則是否正確工作。

監控優化器效能

在生產環境中，你可能想監控優化器的效能：

let start = Instant::now();
let optimized_plan = optimizer.optimize(plan, &config, |plan, rule| {
    println!("Applied rule: {} in {:?}", rule.name(), start.elapsed());
})?;

小結

今天我們深入探討了 DataFusion 的優化器框架，從 OptimizerRule trait 的設計哲學，到 Fixed-Point Iteration 的巧妙機制，再到規則間的依賴關係和自定義規則的開發。

優化器框架是 DataFusion 的核心組件之一，它通過統一的 trait 接口、靈活的執行策略和精心設計的規則順序，實現了高效且可擴展的查詢優化。理解這個框架，不僅能幫助你更好地使用 DataFusion，還能讓你在需要時開發自己的優化規則。

明天我們將探討物理計劃生成過程，看看優化後的邏輯計劃是如何轉換為可執行的物理計劃的。這將是從邏輯優化到實際執行的關鍵一步。

參考資料

• DataFusion Optimizer Source Code
• Writing Custom Optimizer Rules
• OptimizerRule Trait Documentation
• Query Optimization in Database Systems