自己動(dòng)手寫數(shù)據(jù)庫：解析 Select 語句并生成查詢樹

作者：陳屹 2023-12-15 10:14:42

前面我們在實(shí)現(xiàn) sql 解析器后，在解析完一條查詢語句后會(huì)創(chuàng)建一個(gè) QueryData 對象，本節(jié)我們看看如何根據(jù)這個(gè)對象構(gòu)建出合適的查詢規(guī)劃器(Plan)。我們將采取由簡單到負(fù)責(zé)的原則，首先我們直接構(gòu)建 QueryData 的信息去構(gòu)建查詢規(guī)劃對象，此時(shí)我們不考慮它所構(gòu)造的查詢樹是否足夠優(yōu)化，后面我們再慢慢改進(jìn)構(gòu)造算法，直到算法能構(gòu)建出足夠優(yōu)化的查詢樹。

首先，我們需要給原來代碼打個(gè)補(bǔ)丁，在SelectScan 結(jié)構(gòu)體初始化時(shí)需要傳入 UpdateScan 接口對象，但很多時(shí)候我們需要傳入的是 Scan 對象，因此我們需要做一個(gè)轉(zhuǎn)換，也就是當(dāng)初始化 SelectScan 時(shí)，如果傳入的是 Scan 對象，那么我們就將其封裝成 UpdateScan 接口對象，因此在 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
}

上面代碼邏輯簡單，如果調(diào)用 Scan 對象接口時(shí)，他直接調(diào)用其 Scan 內(nèi)部對象的接口，如果調(diào)用到 UpdateScan 的接口，那么它什么都不做。完成上面代碼后，我們在select_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 對象時(shí)，先判斷傳進(jìn)來的對象是否能類型轉(zhuǎn)換為 UpdateScan，如果不能，那意味著s.p.Open 獲取的是 Scan 對象，因此我們使用前面的代碼封裝一下再用來創(chuàng)建 SelectScan 對象。完成這里的修改后，我們進(jìn)入正題。

我們先看一個(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 語句查詢所有考試成績得過 A 的學(xué)生：

select name from STUDENT, EXAM where id = student_id and grad='A'

當(dāng) sql 解釋器讀取上面語句后，他就會(huì)創(chuàng)建一個(gè) QueryData 結(jié)構(gòu)，里面 Tables 對了就包含兩個(gè)表的名字，也就是 STUDENT, EXAM。由于這兩個(gè)表不是視圖，因此上面代碼中判斷 if viewDef != nil 不成立，于是進(jìn)入 else 部分，也就是代碼會(huì)為這兩個(gè)表創(chuàng)建對應(yīng)的 TablePlan 對象，接下來直接對這兩個(gè)表執(zhí)行 Product 操作，也就是將左邊表的一行跟右邊表的每一行合起來形成新表的一行，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|
…..|….|…..|…|…|

接下來代碼創(chuàng)建 ScanSelect 對象在上面的表上，接著獲取該表的每一行，然后檢測該行的 id 字段是否跟 student_id 字段一樣，如果相同，那么查看其 grad 字段，如果該字段是’A’，就將該行的 name 字段顯示出來。

下面我們看看如何使用代碼把上面描述的流程實(shí)現(xiàn)出來。首先我們先對接口進(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)邏輯將接下來的文章中進(jìn)行說明：

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 對象中的表
    plans := make([]Plan, 0)
    tables := data.Tables()
    for _, tblname := range tables {
        //獲取該表對應(yīng)視圖的 sql 代碼
        viewDef := b.mdm.GetViewDef(tblname, tx)
        if viewDef != nil {
            //直接創(chuàng)建表對應(yīng)的視圖
            parser := parser.NewSQLParser(viewDef)
            viewData := parser.Query()
            //遞歸的創(chuàng)建對應(yīng)表的規(guī)劃器
            plans = append(plans, b.CreatePlan(viewData, tx))
        } else {
            plans = append(plans, NewTablePlan(tx, tblname, b.mdm))
        }
    }

    //將所有表執(zhí)行 Product 操作，注意表的次序會(huì)對后續(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 語句后生成的對象，它的 Tables 數(shù)組包含了 select 語句要查詢的表，所以上面代碼的 CreatePlan 函數(shù)先從 QueryData 對象獲得 select 語句要查詢的表，然后使用遍歷這些表，使用 NewProductPlan 創(chuàng)建這些表對應(yīng)的 Product 操作，最后在 Product 的基礎(chǔ)上我們再創(chuàng)建 SelectPlan，這里我們就相當(dāng)于使用 where 語句中的條件，在 Product 操作基礎(chǔ)上將滿足條件的行選出來，最后再創(chuàng)建 ProjectPlan，將在選出的行基礎(chǔ)上，將需要的字段選擇出來。

下面我們測試一下上面代碼的效果，首先在 main.go 中，我們先把 student, exam 兩個(gè)表構(gòu)造出來，代碼如下：

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查詢語句生成 QueryData 對象，最后使用BasicQueryPlanner創(chuàng)建好執(zhí)行樹和對應(yīng)的 Scan 接口對象，最后我們調(diào)用 Scan 對象的 Next 接口來獲取給定字段，代碼如下：

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é)果如下：