C++ SQL解析器到表

Question

我正在用C++編寫一個非常簡單的數據庫以及一個SQL解析器。我做了一切。所以如果我有這樣的SQL輸入：

SELECT * FROM table WHERE `First Name`="John" AND `Last Name`="Doe" 

解析器解析這個。現在的問題是用這些信息做一些事情。我需要看看我的表格，並且實際上找到所有名字爲John和Last name是Doe的記錄。

我在想我可以實現一棵樹，它將以AND作爲主節點，==作爲它的子節點。左邊的孩子是第一個名字，右邊的孩子是姓氏。只要是真的，將該記錄推入矢量中，然後在最後打印出矢量。

這一切聽起來都很理論，但我不知道如何實際執行此操作。如果我有一個if語句像

if(record.firstname == "John") 

如何動態地改變0​​，也許它可能是!=。

Answer 1

你需要的是將SQL翻譯成可以直接執行的語言。技術術語是「查詢計劃」。查詢計劃是數據庫引擎將執行的低級操作（例如索引搜索，連接，排序）以及操作如何組合在一起。

任何體面的數據庫引擎都會爲您提供查看查詢計劃的方法。在SQL系統的情況下，通常稱爲EXPLAIN。我建議讓你最喜歡的數據庫管理系統（如果你沒有最喜歡的，所有體面的開源數據庫管理系統都會這樣做，包括MySQL和PostgreSQL），並查看各種查詢的計劃，以查看「真實「系統實施。

我也推薦關注關係代數。如果您可以訪問庫存充足的圖書館，任何正規的數據庫教科書都會有一個章節或章節，但要求Google返回不少好的參考資料。關係代數的優點是它在理論上都很好，並且有一個「明顯」的方式來使用低級別的數據庫操作來實現它。您最終可能會將其修改爲無法識別，但這應該會給您一個良好的開始。

讓我們來看一個基本的概述。先閱讀有關關係代數的內容，然後繼續閱讀。

您需要實現的主要數據結構是元組流。流中的每個元組都是不同的，但它們都具有相同的形狀：元組的每個字段都有一個名稱和一個類型。查詢操作採用一個或多個元組流（順便提一下，表可以看作是元組流）並返回單個元組流。

考慮形式的基本的SQL語句SELECT：

SELECT fields 
FROM table1,table2 
WHERE select_conditions, join_conditions 

這裏，select_conditions是任何條件如gender='F'或age > 18，其中一個字段針對恆定比較。 join_conditions是匹配一個表中的字段與另一個表中的字段的任何條件。 （我們暫時忽略比較同一個表中兩個字段的情況。）

然後一個簡單的查詢計劃可能是：

s1 := Select(table1, select_conditions_1) 
s2 := Select(table2, select_conditions_2) 
j := Join(join_conditions, s1, s2) 
res := Project(fields, j) 

的Select操作需要一個元組的數據流，並返回相同的形狀元組流，與不符合條件的元組除去。 Project操作獲取元組流並返回不同類型的元組流;它所做的只是刪除，重新排列或重複字段。最後，Join操作將兩個元組流連接在一起，連接任何兩個匹配連接條件的元組。 （如果你不知道數據庫連接操作是什麼，你真的需要知道這一點，詢問谷歌，並查找Unix「加入」命令）。

因此，在這種情況下，s1是一個表示表1中元組的匹配適用於表1的選擇條件的元組。這與s2類似。流j是根據連接條件加入的流s1和s2。最後，您只顯示查詢中提到的字段。

將SQL轉換爲關係代數中間形式其實很簡單。但是，簡單的翻譯往往效率極低。在這裏，我們通過檢查表中的每條記錄並僅返回匹配的記錄來實現選擇操作。因此，查詢需要根據查詢的結構和表中可用的信息進行優化。

例如，假設table1有場age和gender，我們有選擇的條件age > 18和gender = 'F'。進一步假設table1在age字段上有一個索引（稱爲table1_age_idx），但在gender字段上沒有索引。顯然我們應該使用索引。我們可以通過拆分操作做到這一點到兩個基本操作：

s1a := IndexSelect(table1_age_idx, age > 18) 
s2b := FilterSelect(s1a, gender = 'F') 

在這裏，我們分離了選擇操作兩成。第一個選擇是使用索引查詢實現的（請注意，select現在位於索引上，而不是表！），第二個可以通過過濾流實現，刪除gender不是'F'的任何元組。

實現連接可以通過很多方式完成（排序合併連接和散列連接都很流行）。哪一個最好再次取決於查詢和數據庫。某些索引（例如B樹和朋友）會返回按鍵排序的記錄，因此如果您已經在隨後加入的字段上完成了IndexSelect，則排序合併連接可能會更好，因爲排序是不必要的。如果連接字段上有ORDER BY子句，則同樣適用。

正如你所看到的，這是真正聰明的東西發生的地方。真正的查詢優化器使用有關表的大小以及中間元組流的可能大小的統計信息作爲其計算的一部分。在這裏知道一些關於編譯器的東西是值得的。