第17期:SQL的困難源于關系代數
在結構化數據處理領域,SQL無疑是應用最廣泛的工作語言,不僅被所有關系數據庫采用,許多新進的大數據平臺也將實現SQL作為目標。但現實是,面對當前紛雜的計算查詢需求,SQL在很多方面并不夠好用。我們在前面說過SQL的過程性問題,這其實并不是最關鍵的問題,SQL的更大困難來源于其理論基礎,即關系代數。
一
關系代數是一種代數體系。我們無法在本文的篇幅中嚴格定義代數體系這個概念,只能通俗地解釋。人們為解決某種運算問題,定義了一些數據對象及針對這些數據對象的一套運算規則,確保這些運算的封閉性和自洽性,就可以稱為一種代數體系了。比如說我們熟悉的有理數及其上的四則運算就是一種用于解決日常生活中數值計算需求的代數體系。封閉性是指計算結果必須仍然是定義過的數據對象,比如有理數的四則運算結果仍然是有理數。而自洽性指這些運算不能出現矛盾的結果,比如我們要約定不能除以0,否則把某個數除以0規定成任何數都會推出邏輯矛盾來。
這里說的數據對象,和程序設計面向對象理論中數據對象不太一樣。前者主要強調數據上的運算,而后者更多強調對象的封裝性、繼承性和重載能力。前者是為了更好的描述和實施數據運算,后者則主要是為了代碼復用。
二
代數體系設計得好與不好,嚴重影響我們實施計算的方便度和效率!
舉兩個例子:
1. 我們從小學過的算術體系都采用阿拉伯數字,用來表示數值和做四則運算都很方便,但試想如果換成羅馬數字會是個什么感覺?
2. 所有整數乘法都可以用加法表示,但如果我們在算術體系中引入了乘法來表示若干個相同數相加這種運算,就可以發明九九表來做而不必硬加,效率可顯著提高。
要讓計算機實施計算,還需要一套基于代數體系的形式化語言,用戶把計算目標按約定的語法符號寫成代碼,就可以由計算機執行了。而用計算機解決問題的過程,也可以理解為把題目解法翻譯成某種形式化語言的過程。如果代數體系及其形式化語言設計得不好,就可能發生翻譯問題解法的難度大于解決問題本身的現象!用羅馬數字來實施四則運算就是這個結果。
三
關系代數就是用來實現批量結構化數據計算的代數體系,其形式化語言就是SQL。講述關系代數和SQL原理的資料很多,這里就不再贅述了。
那么用SQL解決結構化數據運算的效果如何呢?
人們通常關心兩個效率問題。一是運算的描述效率,二是運算的執行效率。這兩個效率很容易理解,如果描述效率太低,就意味著開發成本太高,很難寫出程序進行計算;而如果執行效率低,則需要運行很久才能得到結果,那實用價值也就大打折扣了。實際上,執行高效在本質上也是個描述問題,在軟件層面不可能提高硬件性能,但可能設計出更高效的算法,那么這個語言不能限制我們寫出高效算法。
四
面對較復雜的大數據運算,SQL在這兩方面表現都很差,我們分別舉兩個并不復雜的例子說明:
1. 找出一支股票最長連續上漲了多少天
這個問題對于Java或C++程序員來講非常簡單:做個初值為0的計數器,把數據按日期排序后遍歷,發現上漲就將計數器加1,下跌則清0,***看這個計數器出現過的***值,這是個很自然的思路。但是用SQL實現就太困難了。關系代數延用了數學上的無序集合概念,數據排序只在輸出時有效,無法規定數據的遍歷次序,也就無法實施上述的自然思路。需要人為地制造出日期的序號后,再產生一個分組標志,把上漲的日期和前一天分成一組,下跌的日期分到另一組,然后計算***的分組COUNT()值,實現思路很難理解。這就發生前面所說的翻譯問題解法的難度大于解決問題本身的現象了。
2. 從10億條數據中找出***的前10名
我們知道,這樣的問題是不需要把10億行數據全部排序的。先產生一個有10個成員的空集合,然后遍歷數據,過程中始終保持這個小集合是當前已遍歷過數據中***的10個,這樣整個10億行數據只要遍歷一次,內存占用很小,運算性能很好。但關系代數中沒有顯式的集合數據類型,無法描述這個算法,只能把10億行數據大排序再取出前10后,剩下的已排序的數據沒有用了。10億行大排序的成本很高,如果內存裝不下則還會設計多次外存數據倒換的問題,性能會嚴重下降。這就會發生我們明知有好的算法卻無計可施的尷尬局面。這種情況常常就只能寄希望于數據庫在工程上的優化,但情況復雜的SQL會超出數據庫的優化能力(比如在分組中取每組的前10名)。
SQL中類似的問題還很多,遠遠不像傳說中的那么強悍。限于篇幅我們不能在本文中一一羅列,以后會逐步撰文深入剖析。
五
在運算簡單的情況,并且性能要求不高時,用SQL還是比較方便的,畢竟掌握者眾多,相關軟件也很豐富。但現代應用中的數據需求越來越復雜,數據量也越來越大,繼續采用SQL就會嚴重影響工作效率了。而且,SQL的不適應并非實現層面的問題,而是其基礎理論的問題,這不是在工程上進行優化就能解決的。面臨當前的數據運算需求,關系代數顯得過于簡單了,需要從數學上進行徹底的革新。