#68 資料庫 Table Join 的運行方式 - 上集

在資料庫引擎中，table join 是一個很重要並且常見的動作．這一篇文章將討論以邏輯上來看資料庫引擎是如何進行 table join 的動作．

假設資料庫中有兩個表格，一個是學生表格，一個老師表格，這兩個表格裡都各自有一個 id 欄位用來代表學生編號與老師編號．對這兩個表格來說，這個 id 非常適合做為 primary key．學生表格裡有一個欄位是老師 id，這用來代表某學生的班導師是某位老師．這是一個一對多的關係，所以只要在學生表格上有一個老師 id 的欄位便能說明這個關係．用一個簡單的 SQL 語法可以用來表示這樣的關係

Select S.Name, R.Name
From S join R
On S.TeacherId = R.TeacherId    ( S = Student, R = Teacher)

假設你是資料庫引擎的程式設計師，需要處理以上的語法並回傳結果，你會怎麼處理呢? 所有的資料都儲存在磁碟中，但運算時你得把資料搬到記憶中才能計算，於是你可能會想到最直覺的方法就是把所有老師和學生的資料放到記憶體中，然後用兩個 for loop 將學生與老師的資料一筆一筆的比對，把比對成功的結果暫存起來，執行完畢之後就把結果回傳給使用者．這方法是假設所有的資料並沒有任何 index 建立的情況下．

以上的想法很直覺，但會面臨到幾個問題．第一個問題是有可能把學生和老師的資料全部載入到記憶體中嗎 ? 如果學生老師人數不多，這是可能的．但如果是一家龐大電子商務公司的訂單與客戶資料呢 ? 資料量一定大於記體量容量，所以把兩個表格的全部資料載入到記憶體是不可行的．因此，當你寫兩個 for loop 做資料比對時，資料必須一批一批地從硬碟載入到記憶體．如同以前的文章提過，所有資料的儲存單位是以 page 為主，所以可以一個一個 page 依序地載入到記憶體，然後對該 page 裡的資料進行比對的動作．如下圖所示:

比如老師表格 (R)  有二個 page，學生表格 (S) 有五個 page．當第一個老師 page 被載入到記憶體，接著第一個學生 page 被載入記憶體進行資料比對，然後再換第二個學生 page 被載入，一直到第五個學生 page，然後再換成第二個老師 page 被載入到記憶體，接著再依序 (反向) 將學生 page 一一載入比對資料．符合條件的資料將被放在記憶體另一個區域，如上圖的粉紅區域．整個比對完成之後，就將粉紅區域的資料回傳給使用者．如果採用這個方法，老師和學生的 page 將被載入 2+5+4 = 11 次．以速度來看，這 11 次從硬碟載入到記憶體的 page 讀取時間應該主宰了這個動作大部份的時間．

如果將以上的點子做一個小改進，也就是將其中一個表格絕大部份的內容載入到記憶體，而另一個表格一次只載入一個 page 到記憶體，如下圖所示 :

假設，老師的兩個 page 一次全被載入到記憶體，而學生表格的五個 page 將依序載入到記憶體，然後進行資料比對．這樣的 page 載入將發生 2 + 5 = 7 次．理論上應該比前一個方式來的好．這也是典型的用空間換時間的方法．

Select S.Name, R.Name
From S join R
On S.TeacherId = R.TeacherId    ( S = Student, R = Teacher)
Where S.Age = 20

上述語法是另外一種情況．如果表格資料的數量很大並且在適當的欄位上 (S.Age) 皆建立 index 的話，那麼就不用將所有的 page 都載入到記憶體中來進行資料比對．只要透過 Index tree 的尋找機制，將符合條件的資料所在的 page 載入到記憶體進行比對．所以，在 table join 時，若能適當地加上條件 (where)  並且該條件有 index，這將對 table join 的處理速度有莫大的幫助．

其實，以上所說的方法用在表格資料不大的情況下都算能應付的過去，但如果表格資料太大時，以上的方法並不具有效率，為什麼呢 ? 顯而易見，你看到了兩個 for loop 的想法是整個運算方式的主體．有這兩個  for loop 在，速度當然是快不起來．因此，下一篇資料庫的文章將介紹更快的方式．