800
數據蔣堂 | JOIN運算剖析
JOIN是SQL中用於多表關聯的運算，無論從程序員編寫還是數據庫實現角度來看，JOIN都是SQL中最難的運算。
其實，SQL對JOIN的定義非常簡單，就是對兩個集合（表）做笛卡爾積後再按某種條件過濾，寫出來的語法也就是A JOIN B ON ...的形式。原則上，笛卡爾積後的結果集應當是以兩集合成員構成的二元組為成員，不過由於SQL中的集合成員總是有字段的記錄，而且也不支持泛型數據類型來描述成員為記錄的二元組，所以就簡單地把結果集處理成由兩表記錄的字段合並後構成的新記錄集合。這也是JOIN一詞在英語中的願意，並沒有乘法（笛卡爾積）的意思。把結果集理解成二元組還是字段合並的記錄，都不會影響本文的討論。
JOIN定義中並沒有規定過濾條件的形式。理論上，隻要目標結果集是兩源集笛卡爾積的子集，都可以理解為JOIN運算。比如，我們可以計算 A JOIN B ON A<B，如果集合A={1,2,3},B={2,3,4}，則這個JOIN結果就是{(1,2),(1,3),{1,4),(2,3),{2,4),(3,4)}。
不過，有經驗的程序員都知道，現實中絕大多數JOIN都是等值JOIN，即過濾條件是一個或多個相等關係（多個之間是AND關係），語法形如A JOIN B ON A.ai=B.bi AND ...，其中ai和bi分別是A和B的字段。而前述例子中ON A<B這類稱為非等值JOIN，相對少見得多，而且許多情況下非等值JOIN可以轉換成等值JOIN來處理，所以我們這裏重點討論等值JOIN。
根據對空值的處理規則，等值JOIN還可以衍生出LEFT JOIN和FULL JOIN，而且一般會被分成一對一、一對多、多對多等幾種情況。這些常規術語在所有的SQL教科書都有，這裏就不再贅述了。
我們來考察下麵三種等值JOIN：
外鍵表
表A的某些字段與表B的主鍵關聯（所謂關聯，是指JOIN的過濾條件即由這些對應字段相等構成）。A表稱為事實表，B表稱為維表。A表中與B表主鍵關聯的字段稱為A指向B的外鍵，B也稱為A的外鍵表。外鍵表是多對一的關係，且隻有JOIN和LEFT JOIN，一般不會用到FULL JOIN。
典型例子：帳戶交易記錄和帳戶基本信息。
同維表
表A的主鍵與表B的主鍵關聯，A和B互稱為同維表。同維表是一對一的關係，JOIN、LEFT JOIN和FULL JOIN的情況都會有。
典型例子：員工表和銷售員表。
主子表
表A的主鍵與表B的部分主鍵關聯，A稱為主表，B稱為子表。主子表是一對多的關係，隻有JOIN和LEFT JOIN，不會有FULL JOIN。
典型例子：訂單和訂單明細。
這裏說的主鍵是指邏輯上的主鍵，也就是在表中取值唯一的字段（組），一個表上可能有多個字段（組）都取值唯一（並不常見），可以認為都是主鍵。不是一定是在物理表上建立的那個主鍵。
在SQL的概念體係中並不區分外鍵表和主子表，多對一和一對多從SQL的觀點看來隻是關聯方向不同，本質上是一回事。確實，訂單也可以理解成訂單明細的外鍵表。但是，我們在這裏要把它們區分開，將來在簡化語法和性能優化時將使用不同的手段。
我們說，這三種JOIN已經涵蓋了絕大多數等值JOIN的情況，甚至可以說幾乎全部有業務意義的等值JOIN都屬於這三類，把等值JOIN限定在這三種情況之中，幾乎不會減少其適應範圍。
仔細考察這三種JOIN，我們發現所有關聯都涉及主鍵，沒有多對多的情況，可以不考慮這種情況嗎？
是的！多對多的等值JOIN幾乎沒有業務意義。
如果JOIN兩個表時的關聯字段沒有涉及到任何主鍵，那就會發生多對多的情況，而這種情況幾乎一定還會有一個規模更大的表把這兩個表作為維表關聯起來。比如學生表和科目表在JOIN時，會有個成績表以學生表和科目表作為維表，單純隻有學生表和科目表的JOIN沒有業務意義了。
當寫SQL時發現多對多的情況，那大概率是這個語句寫錯了！或者數據有問題！這條法則用於排除JOIN錯誤很有效。
不過，我們一直在說“幾乎”，並沒有用完全肯定的說法，也就是說，多對多在非常罕見的情況下也有業務意義。可舉一例，用SQL實現矩陣乘法時會發生多對多的等值JOIN，具體寫法讀者可以自行補充。
笛卡爾積再過濾這種JOIN定義，確實非常簡單，而且簡單的內涵將得到更大的外延，可以把多對多等值JOIN甚至非等值JOIN等都包括進來。但是，過於簡單的內涵無法充分體現出最常見等值JOIN的運算特征。這會導致編寫代碼和實現運算時就不能利用這些特征，在運算較為複雜時（涉及關聯表較多以及有嵌套的情況），無論是書寫還是優化都非常困難。而充分利用這些特征後，我們就能創造更簡單的書寫形式並獲得更高效率的運算性能，我們將在以後的文章中逐步說明。
與其為了把罕見情況也包括進來而把運算定義為更通用的形式，還不如把這些情況定義成另一種運算更為合理。
清華大學計算機碩士，著有《非線性報表模型原理》等，1989年，中國首個國際奧林匹克數學競賽團體冠軍成員，個人金牌；2000年，創立潤乾公司；2004年，首次在潤乾報表中提出非線性報表模型，完美解決了中國式複雜報表製表難題，目前該模型已經成為報表行業的標準；2014年，經過7年開發，潤乾軟件發布不依賴關係代數模型的計算引擎——集算器，有效地提高了複雜結構化大數據計算的開發和運算效率；2015年，潤乾軟件被福布斯中文網站評為“2015福布斯中國非上市潛力企業100強”；2016年，榮獲中國電子信息產業發展研究院評選的“2016年中國軟件和信息服務業十大領軍人物”；2017年, 自主創新研發新一代的數據倉庫、雲數據庫等產品即將麵世。
數據蔣堂
《數據蔣堂》的作者蔣步星，從事信息係統建設和數據處理長達20多年的時間。他豐富的工程經驗與深厚的理論功底相互融合、創新思想與傳統觀念的相互碰撞，虛擬與現實的相互交織，產生出了一篇篇的瀝血之作。此連載的內容涉及從數據呈現、采集到加工計算再到存儲以及挖掘等各個方麵。大可觀數據世界之遠景、小可看技術疑難之細節。針對數據領域一些技術難點，站在研發人員的角度從淺入深，進行全方位、360度無死角深度剖析；對於一些業內觀點，站在技術人員角度闡述自己的思考和理解。蔣步星還會對大數據的發展，站在業內專家角度給予預測和推斷。靜下心來認真研讀你會發現，《數據蔣堂》的文章，有的會讓用戶避免重複前人走過的彎路，有的會讓攻城獅麵對紮心的難題茅塞頓開，有的會為初入行業的讀者提供一把開啟數據世界的鑰匙，有的甚至會讓業內專家大跌眼鏡，產生思想交鋒。
原文發布時間為：2017-11-8
本文作者：蔣步星
本文來自雲棲社區合作夥伴“數據派THU”，了解相關信息可以關注“數據派THU”微信公眾號
最後更新：2017-11-09 11:34:44