自己動(dòng)手寫(xiě)數(shù)據(jù)庫(kù)：解析 Select 語(yǔ)句并生成查詢樹(shù)
首先，我們需要給原來(lái)代碼打個(gè)補(bǔ)丁，在SelectScan 結(jié)構(gòu)體初始化時(shí)需要傳入 UpdateScan 接口對(duì)象，但很多時(shí)候我們需要傳入的是 Scan 對(duì)象，因此我們需要做一個(gè)轉(zhuǎn)換，也就是當(dāng)初始化 SelectScan 時(shí)，如果傳入的是 Scan 對(duì)象，那么我們就將其封裝成 UpdateScan 接口對(duì)象，因此在 query 目錄下增加一個(gè)名為 updatescan_wrapper.go 的文件，在其中輸入內(nèi)容如下：
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
}上面代碼邏輯簡(jiǎn)單，如果調(diào)用 Scan 對(duì)象接口時(shí)，他直接調(diào)用其 Scan 內(nèi)部對(duì)象的接口，如果調(diào)用到 UpdateScan 的接口，那么它什么都不做。完成上面代碼后，我們?cè)趕elect_plan.go 中進(jìn)行一些修改：
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)
}上面代碼在創(chuàng)建 SelectScan 對(duì)象時(shí)，先判斷傳進(jìn)來(lái)的對(duì)象是否能類型轉(zhuǎn)換為 UpdateScan，如果不能，那意味著s.p.Open 獲取的是 Scan 對(duì)象，因此我們使用前面的代碼封裝一下再用來(lái)創(chuàng)建 SelectScan 對(duì)象。完成這里的修改后，我們進(jìn)入正題。
前面我們?cè)趯?shí)現(xiàn) sql 解析器后，在解析完一條查詢語(yǔ)句后會(huì)創(chuàng)建一個(gè) QueryData 對(duì)象，本節(jié)我們看看如何根據(jù)這個(gè)對(duì)象構(gòu)建出合適的查詢規(guī)劃器(Plan)。我們將采取由簡(jiǎn)單到負(fù)責(zé)的原則，首先我們直接構(gòu)建 QueryData 的信息去構(gòu)建查詢規(guī)劃對(duì)象，此時(shí)我們不考慮它所構(gòu)造的查詢樹(shù)是否足夠優(yōu)化，后面我們?cè)俾倪M(jìn)構(gòu)造算法，直到算法能構(gòu)建出足夠優(yōu)化的查詢樹(shù)。
我們先看一個(gè)具體例子，假設(shè)我們現(xiàn)在有兩個(gè)表 STUDENT, EXAM，第一個(gè)表包含兩個(gè)字段分別是學(xué)生 id 和姓名：
id | name
———— | ——-
1 | Tom
2 | Jim
3 | John
第二個(gè)表包含的是學(xué)生 id,科目名稱，考試乘機(jī)：
stuid | exam|grad
———— | ——-|——-|
1 | math| A|
1 | algorithm| B
2 | writing| C |
2| physics| C|
3|chemical|B|
3|english| C|
現(xiàn)在我們使用 sql 語(yǔ)句查詢所有考試成績(jī)得過(guò) A 的學(xué)生：
select name from STUDENT, EXAM where id = student_id and grad='A'當(dāng) sql 解釋器讀取上面語(yǔ)句后，他就會(huì)創(chuàng)建一個(gè) QueryData 結(jié)構(gòu)，里面 Tables 對(duì)了就包含兩個(gè)表的名字，也就是 STUDENT, EXAM。由于這兩個(gè)表不是視圖，因此上面代碼中判斷 if viewDef != nil 不成立，于是進(jìn)入 else 部分，也就是代碼會(huì)為這兩個(gè)表創(chuàng)建對(duì)應(yīng)的 TablePlan 對(duì)象，接下來(lái)直接對(duì)這兩個(gè)表執(zhí)行 Product 操作，也就是將左邊表的一行跟右邊表的每一行合起來(lái)形成新表的一行，Product 操作在 STUDENT 和 EXAM 表后所得結(jié)果如下：
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|
…..|….|…..|…|…|
接下來(lái)代碼創(chuàng)建 ScanSelect 對(duì)象在上面的表上，接著獲取該表的每一行，然后檢測(cè)該行的 id 字段是否跟 student_id 字段一樣，如果相同，那么查看其 grad 字段，如果該字段是’A’，就將該行的 name 字段顯示出來(lái)。
下面我們看看如何使用代碼把上面描述的流程實(shí)現(xiàn)出來(lái)。首先我們先對(duì)接口進(jìn)行定義，在 Planner 目錄下的 interface.go 文件中增加如下內(nèi)容：
type QueryPlanner interface {
CreatePlan(data *query.QueryData, tx tx.Transaction) Plan
}接著在 Planner 目錄下創(chuàng)建文件 query_planner.go，同時(shí)輸入以下代碼，代碼的實(shí)現(xiàn)邏輯將接下來(lái)的文章中進(jìn)行說(shuō)明：
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,直接創(chuàng)建 QueryData 對(duì)象中的表
plans := make([]Plan, 0)
tables := data.Tables()
for _, tblname := range tables {
//獲取該表對(duì)應(yīng)視圖的 sql 代碼
viewDef := b.mdm.GetViewDef(tblname, tx)
if viewDef != nil {
//直接創(chuàng)建表對(duì)應(yīng)的視圖
parser := parser.NewSQLParser(viewDef)
viewData := parser.Query()
//遞歸的創(chuàng)建對(duì)應(yīng)表的規(guī)劃器
plans = append(plans, b.CreatePlan(viewData, tx))
} else {
plans = append(plans, NewTablePlan(tx, tblname, b.mdm))
}
}
//將所有表執(zhí)行 Product 操作，注意表的次序會(huì)對(duì)后續(xù)查詢效率有重大影響，但這里我們不考慮表的次序，只是按照
//給定表依次執(zhí)行 Product 操作，后續(xù)我們會(huì)在這里進(jìn)行優(yōu)化
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 語(yǔ)句后生成的對(duì)象，它的 Tables 數(shù)組包含了 select 語(yǔ)句要查詢的表，所以上面代碼的 CreatePlan 函數(shù)先從 QueryData 對(duì)象獲得 select 語(yǔ)句要查詢的表，然后使用遍歷這些表，使用 NewProductPlan 創(chuàng)建這些表對(duì)應(yīng)的 Product 操作，最后在 Product 的基礎(chǔ)上我們?cè)賱?chuàng)建 SelectPlan，這里我們就相當(dāng)于使用 where 語(yǔ)句中的條件，在 Product 操作基礎(chǔ)上將滿足條件的行選出來(lái)，最后再創(chuàng)建 ProjectPlan，將在選出的行基礎(chǔ)上，將需要的字段選擇出來(lái)。
下面我們測(cè)試一下上面代碼的效果，首先在 main.go 中，我們先把 student, exam 兩個(gè)表構(gòu)造出來(lái)，代碼如下：
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() //指向一個(gè)可用插槽
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() //指向一個(gè)可用插槽
ts.SetInt("stuid", 1)
ts.SetString("exam", "math")
ts.SetString("grad", "A")
ts.Insert() //指向一個(gè)可用插槽
ts.SetInt("stuid", 1)
ts.SetString("exam", "algorithm")
ts.SetString("grad", "B")
ts.Insert() //指向一個(gè)可用插槽
ts.SetInt("stuid", 2)
ts.SetString("exam", "writing")
ts.SetString("grad", "C")
ts.Insert() //指向一個(gè)可用插槽
ts.SetInt("stuid", 2)
ts.SetString("exam", "physics")
ts.SetString("grad", "C")
ts.Insert() //指向一個(gè)可用插槽
ts.SetInt("stuid", 3)
ts.SetString("exam", "chemical")
ts.SetString("grad", "B")
ts.Insert() //指向一個(gè)可用插槽
ts.SetInt("stuid", 3)
ts.SetString("exam", "english")
ts.SetString("grad", "C")
mdm.CreateTable("exam", exam_sch, tx)
return tx, mdm
}然后我們用解析器解析select查詢語(yǔ)句生成 QueryData 對(duì)象，最后使用BasicQueryPlanner創(chuàng)建好執(zhí)行樹(shù)和對(duì)應(yīng)的 Scan 接口對(duì)象，最后我們調(diào)用 Scan 對(duì)象的 Next 接口來(lái)獲取給定字段，代碼如下：
func main() {
//構(gòu)造 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"))
}
}上面代碼運(yùn)行后所得結(jié)果如下：
