自己動手寫數據庫：解析 Select 語句并生成查詢樹
首先，我們需要給原來代碼打個補丁，在SelectScan 結構體初始化時需要傳入 UpdateScan 接口對象，但很多時候我們需要傳入的是 Scan 對象，因此我們需要做一個轉換，也就是當初始化 SelectScan 時，如果傳入的是 Scan 對象，那么我們就將其封裝成 UpdateScan 接口對象，因此在 query 目錄下增加一個名為 updatescan_wrapper.go 的文件，在其中輸入內容如下：
package query
import (
"record_manager"
)
type UpdateScanWrapper struct {
scan Scan
}
func NewUpdateScanWrapper(s Scan) *UpdateScanWrapper {
return &UpdateScanWrapper{
scan: s,
}
}
func (u *UpdateScanWrapper) GetScan() Scan {
return u.scan
}
func (u *UpdateScanWrapper) SetInt(fldName string, val int) {
//DO NOTHING
}
func (u *UpdateScanWrapper) SetString(fldName string, val string) {
//DO NOTHING
}
func (u *UpdateScanWrapper) SetVal(fldName string, val *Constant) {
//DO NOTHING
}
func (u *UpdateScanWrapper) Insert() {
//DO NOTHING
}
func (u *UpdateScanWrapper) Delete() {
//DO NOTHING
}
func (u *UpdateScanWrapper) GetRid() *record_manager.RID {
return nil
}
func (u *UpdateScanWrapper) MoveToRid(rid *record_manager.RID) {
// DO NOTHING
}上面代碼邏輯簡單，如果調用 Scan 對象接口時，他直接調用其 Scan 內部對象的接口，如果調用到 UpdateScan 的接口，那么它什么都不做。完成上面代碼后，我們在select_plan.go 中進行一些修改：
func (s *SelectPlan) Open() interface{} {
scan := s.p.Open()
updateScan, ok := scan.(query.UpdateScan)
if !ok {
updateScanWrapper := query.NewUpdateScanWrapper(scan.(query.Scan))
return query.NewSelectionScan(updateScanWrapper, s.pred)
}
return query.NewSelectionScan(updateScan, s.pred)
}上面代碼在創建 SelectScan 對象時，先判斷傳進來的對象是否能類型轉換為 UpdateScan，如果不能，那意味著s.p.Open 獲取的是 Scan 對象，因此我們使用前面的代碼封裝一下再用來創建 SelectScan 對象。完成這里的修改后，我們進入正題。
前面我們在實現 sql 解析器后，在解析完一條查詢語句后會創建一個 QueryData 對象，本節我們看看如何根據這個對象構建出合適的查詢規劃器(Plan)。我們將采取由簡單到負責的原則，首先我們直接構建 QueryData 的信息去構建查詢規劃對象，此時我們不考慮它所構造的查詢樹是否足夠優化，后面我們再慢慢改進構造算法，直到算法能構建出足夠優化的查詢樹。
我們先看一個具體例子，假設我們現在有兩個表 STUDENT, EXAM，第一個表包含兩個字段分別是學生 id 和姓名：
id | name
———— | ——-
1 | Tom
2 | Jim
3 | John
第二個表包含的是學生 id,科目名稱，考試乘機：
stuid | exam|grad
———— | ——-|——-|
1 | math| A|
1 | algorithm| B
2 | writing| C |
2| physics| C|
3|chemical|B|
3|english| C|
現在我們使用 sql 語句查詢所有考試成績得過 A 的學生：
select name from STUDENT, EXAM where id = student_id and grad='A'當 sql 解釋器讀取上面語句后，他就會創建一個 QueryData 結構，里面 Tables 對了就包含兩個表的名字，也就是 STUDENT, EXAM。由于這兩個表不是視圖，因此上面代碼中判斷 if viewDef != nil 不成立，于是進入 else 部分，也就是代碼會為這兩個表創建對應的 TablePlan 對象，接下來直接對這兩個表執行 Product 操作，也就是將左邊表的一行跟右邊表的每一行合起來形成新表的一行，Product 操作在 STUDENT 和 EXAM 表后所得結果如下：
id|name|student_id | exam|grad
————|——-|———— | ——-|——-|
1|Tom|1|math|A|
1|Tom|1|algorithm|B|
1|Tom|2|writing|A|
1|Tom|2|physics|C|
1|Tom|3|chemical|B|
1|Tom|3|english|A|
…..|….|…..|…|…|
接下來代碼創建 ScanSelect 對象在上面的表上，接著獲取該表的每一行，然后檢測該行的 id 字段是否跟 student_id 字段一樣，如果相同，那么查看其 grad 字段，如果該字段是’A’，就將該行的 name 字段顯示出來。
下面我們看看如何使用代碼把上面描述的流程實現出來。首先我們先對接口進行定義，在 Planner 目錄下的 interface.go 文件中增加如下內容：
type QueryPlanner interface {
CreatePlan(data *query.QueryData, tx tx.Transaction) Plan
}接著在 Planner 目錄下創建文件 query_planner.go，同時輸入以下代碼，代碼的實現邏輯將接下來的文章中進行說明：
package planner
import (
"metadata_management"
"parser"
"tx"
)
type BasicQueryPlanner struct {
mdm *metadata_management.MetaDataManager
}
func CreateBasicQueryPlanner(mdm *metadata_management.MetaDataManager) QueryPlanner {
return &BasicQueryPlanner{
mdm: mdm,
}
}
func (b *BasicQueryPlanner) CreatePlan(data *parser.QueryData, tx *tx.Transaction) Plan {
//1,直接創建 QueryData 對象中的表
plans := make([]Plan, 0)
tables := data.Tables()
for _, tblname := range tables {
//獲取該表對應視圖的 sql 代碼
viewDef := b.mdm.GetViewDef(tblname, tx)
if viewDef != nil {
//直接創建表對應的視圖
parser := parser.NewSQLParser(viewDef)
viewData := parser.Query()
//遞歸的創建對應表的規劃器
plans = append(plans, b.CreatePlan(viewData, tx))
} else {
plans = append(plans, NewTablePlan(tx, tblname, b.mdm))
}
}
//將所有表執行 Product 操作，注意表的次序會對后續查詢效率有重大影響，但這里我們不考慮表的次序，只是按照
//給定表依次執行 Product 操作，后續我們會在這里進行優化
p := plans[0]
plans = plans[1:]
for _, nextPlan := range plans {
p = NewProductPlan(p, nextPlan)
}
p = NewSelectPlan(p, data.Pred())
return NewProjectPlan(p, data.Fields())
}上面代碼中 QueryData就是解析器在解析 select 語句后生成的對象，它的 Tables 數組包含了 select 語句要查詢的表，所以上面代碼的 CreatePlan 函數先從 QueryData 對象獲得 select 語句要查詢的表，然后使用遍歷這些表，使用 NewProductPlan 創建這些表對應的 Product 操作，最后在 Product 的基礎上我們再創建 SelectPlan，這里我們就相當于使用 where 語句中的條件，在 Product 操作基礎上將滿足條件的行選出來，最后再創建 ProjectPlan，將在選出的行基礎上，將需要的字段選擇出來。
下面我們測試一下上面代碼的效果，首先在 main.go 中，我們先把 student, exam 兩個表構造出來，代碼如下：
func createStudentTable() (*tx.Transation, *metadata_manager.MetaDataManager) {
file_manager, _ := fm.NewFileManager("student", 2048)
log_manager, _ := lm.NewLogManager(file_manager, "logfile.log")
buffer_manager := bmg.NewBufferManager(file_manager, log_manager, 3)
tx := tx.NewTransation(file_manager, log_manager, buffer_manager)
sch := record_manager.NewSchema()
mdm := metadata_manager.NewMetaDataManager(false, tx)
sch.AddStringField("name", 16)
sch.AddIntField("id")
layout := record_manager.NewLayoutWithSchema(sch)
ts := query.NewTableScan(tx, "student", layout)
ts.BeforeFirst()
for i := 1; i <= 3; i++ {
ts.Insert() //指向一個可用插槽
ts.SetInt("id", i)
if i == 1 {
ts.SetString("name", "Tom")
}
if i == 2 {
ts.SetString("name", "Jim")
}
if i == 3 {
ts.SetString("name", "John")
}
}
mdm.CreateTable("student", sch, tx)
exam_sch := record_manager.NewSchema()
exam_sch.AddIntField("stuid")
exam_sch.AddStringField("exam", 16)
exam_sch.AddStringField("grad", 16)
exam_layout := record_manager.NewLayoutWithSchema(exam_sch)
ts = query.NewTableScan(tx, "exam", exam_layout)
ts.BeforeFirst()
ts.Insert() //指向一個可用插槽
ts.SetInt("stuid", 1)
ts.SetString("exam", "math")
ts.SetString("grad", "A")
ts.Insert() //指向一個可用插槽
ts.SetInt("stuid", 1)
ts.SetString("exam", "algorithm")
ts.SetString("grad", "B")
ts.Insert() //指向一個可用插槽
ts.SetInt("stuid", 2)
ts.SetString("exam", "writing")
ts.SetString("grad", "C")
ts.Insert() //指向一個可用插槽
ts.SetInt("stuid", 2)
ts.SetString("exam", "physics")
ts.SetString("grad", "C")
ts.Insert() //指向一個可用插槽
ts.SetInt("stuid", 3)
ts.SetString("exam", "chemical")
ts.SetString("grad", "B")
ts.Insert() //指向一個可用插槽
ts.SetInt("stuid", 3)
ts.SetString("exam", "english")
ts.SetString("grad", "C")
mdm.CreateTable("exam", exam_sch, tx)
return tx, mdm
}然后我們用解析器解析select查詢語句生成 QueryData 對象，最后使用BasicQueryPlanner創建好執行樹和對應的 Scan 接口對象，最后我們調用 Scan 對象的 Next 接口來獲取給定字段，代碼如下：
func main() {
//構造 student 表
tx, mdm := createStudentTable()
queryStr := "select name from student, exam where id = stuid and grad=\"A\""
p := parser.NewSQLParser(queryStr)
queryData := p.Query()
test_planner := planner.CreateBasicQueryPlanner(mdm)
test_plan := test_planner.CreatePlan(queryData, tx)
test_interface := (test_plan.Open())
test_scan, _ := test_interface.(query.Scan)
for test_scan.Next() {
fmt.Printf("name: %s\n", test_scan.GetString("name"))
}
}上面代碼運行后所得結果如下：
