一、 實驗內容

查詢優化器是一個溝通語句SQL到具體執行邏輯的橋梁。

從query到具體執行，代碼要經過如下的過程：

query parsing：從文本query得到一棵語法樹，語法樹等上下文被綁定（保存）到執行計劃中

query optimization：從語法樹生成優化的執行計劃

query execution：按照執行計劃調用執行器執行

底層執行：執行器調用事務管理器，執行并發控制，底層數據結構簡化如project1，2

 

 

Parser是常規操作，用來生成語句AST；

Binder不重要，它只是用來讓Planner擁有AST信息和數據庫底層信息的；

Planner產生的Plan是一棵樹，每個節點是一種操作；1條SQL語句可能產生很多個Plan，但是每個Plan只處理一個Table的數據

Optimizer是Project3的主體之一，它接收plan，輸出優化后的plan。在Optimize接口中實現具體的邏輯。

Catalog圖中未提及，保存了Table和Index的信息，正是一部分元數據存儲的地方

 

背景知識：

       通常流程：Executor調用Transaction接口，執行增刪改查操作；對外暴露Next接口，，并加入標記；執行器的執行過程是迭代器模型，又稱火山模型（Volcano）或者流水線（Pipeline）模型；

實現的接口

Task #1 - Access Method Executors  實現SeqScan、Insert、Delete、IndexScan 算子。

Task #2 - Aggregation & Join Executors：實現Aggregation、NestedLoopJoin、NestedIndexJoin 三個算子。HashJoin不是必須的要求。

Task #3 - Sort + Limit Executors and Top-N Optimization：實現Sort，Limit算子，并實現TopN算子優化；

Leaderboard Task：為 Optimizer 實現新的優化規則，讓稍微復雜的樣例sql 語句執行得更快。

二、 實驗FAQ

1.迭代器模式

迭代器的優點是什么？執行過程可以不用一次性查出所有數據，節約內存。

對于查詢，一次Next得到一條數據，而且在火山模型下，可能是嵌套的節點由上到下調用Next；

而對于刪除，修改，一次調用要執行完對所有記錄的操作。

其他模式：向量化模型（Vectorization Model），不遵循一次Next產生一條數據的模式。

2.執行器關聯變量

每個executor有exec_ctx_，保存主要的上下文變量，包括事務管理器TransactionManager，目錄Catalog，鎖管理器；

executor中的table存儲的方式：Catalog目錄保存了TableInfo，TableInfo里保存了實際的Table；

一些特有的變量，如Aggregation算子用在group_by中，查詢計劃plan保存了group_bys_的查詢條件；

Schema作為輸出的變量，表示數據的每個列屬性

3. HashJoin、NestedLoopJoin

JOIN為連接操作，即兩個表的笛卡爾積，對于A JOIN B, 若A有n個滿足條件的行，B有m個，若不加任何條件限制，則查詢結果集為nxm；

NestedLoopJoin，HashJoin為數據庫內部連接方式

而內連接，左外連接，右外連接為SQL支持的功能, 通過連接方式實現這些功能

1)     我們有常用結論，以較小的表作為左表進行連接，是一個代價相對小的方式，此時該表稱為驅動表；

2)     hash join(HJ)是一種用于equi-join（而anti-join就是使用NOT IN時的join）的技術。主要將小表、大表分別hash到桶中，最后比較哈希桶中的數據得到結果；

3)     當Join個數大于1個，如A JOIN B JOIN C的時候，即為嵌套查詢；

4）大表、小表只是簡化稱呼，實際中可能操作的是臨時表，是加了過濾條件的

4.執行計劃優化

查詢優化包括：

基于規則的優化（Rule-Based-Optimization，簡稱 RBO）

基于代價的優化（Cost-Based Optimization，簡稱 CBO）

 

找到OptimizeCustom，在其中多加一條實現自己的規則即可；

auto Optimizer::OptimizeCustom(const AbstractPlanNodeRef &plan) -> AbstractPlanNodeRef {

  auto p = plan;

  //所有的優化規則

  p = OptimizeMergeProjection(p);

  p = OptimizeMergeFilterNLJ(p);

  p = OptimizeNLJAsIndexJoin(p);

  // p = OptimizeNLJAsHashJoin(p);  // Enable this rule after you have implemented hash join.

  p = OptimizeOrderByAsIndexScan(p);

  p = OptimizeSortLimitAsTopN(p);

  return p;

}

Query 1: Where's the Index?

SELECT * FROM (t1 INNER JOIN t2 ON t1.x = t2.x) INNER JOIN t3 ON t2.y = t3.y;

其中表t1有索引，我們需要利用到索引加快查詢速度，但是原有的查詢優化只能利用右表的索引；對于此，可以根據索引的位置交換JOIN的順序；

Query 2: Too Many Joins!

SELECT * FROM t4, t5, t6

WHERE (t4.x = t5.x) AND (t5.y = t6.y) AND (t4.y >= 1000000)

AND (t4.y < 1500000) AND (t6.x >= 100000) AND (t6.x < 150000);

 

 

可以看到Filter在JOIN的上方，要將其進行下推，提前進行Filter操作，避免處理過多的無用數據；具體做法是將Filter節點下移到JOIN的下方；

 

Query 3: The Mad Data Scientist

SELECT v, d1, d2 FROM (

SELECT v,

MAX(v1) AS d1, MIN(v1), MAX(v2), MIN(v2),

MAX(v1) + MIN(v1), MAX(v2) + MIN(v2),

MAX(v1) + MAX(v1) + MAX(v2) AS d2

FROM t7 LEFT JOIN (SELECT v4 FROM t8 WHERE 1 == 2) ON v < v4 GROUP BY v
)

這個查詢里有很多重復的字段，未經優化會產生很多重復計算；

要進行列裁剪；包括將重復的字段進行合并；

5.測試

project3的測試主要是手工測試，通過寫好的SQL在shell里執行，直接查看生成的數據是否正確；這里沒有必要寫成單測的形式，因為相較于前面的測試來說這個實驗的代碼確實略微簡單；

用如下命令測試：

cd build && make -j$(nproc) shell

./bin/bustub-shell

make -j$(nproc) sqllogictest

./bin/bustub-sqllogictest ../test/sql/p3.00-primer.slt --verbose

References

[1]自動測評網站 GradeScope，course entry code: PXWVR5 https://www.gradescope.com/

[2] https://15445.courses.cs.cmu.edu/fall2022 課程官網

[3] https://github.com/cmu-db/bustub Bustub Github Repo

[4] Database System Concepts 6^th version, Abraham.Silberschatz.