天天看點

資料蔣堂 | SQL的困難源于關系代數

資料蔣堂 | SQL的困難源于關系代數

在結構化資料處理領域,SQL無疑是應用最廣泛的工作語言,不僅被所有關系資料庫采用,許多新進的大資料平台也将實作SQL作為目标。但現實是,面對目前紛雜的計算查詢需求,SQL在很多方面并不夠好用。我們在前面說過SQL的過程性問題,這其實并不是最關鍵的問題,SQL的更大困難來源于其理論基礎,即關系代數。

資料蔣堂 | SQL的困難源于關系代數

關系代數是一種代數體系。我們無法在本文的篇幅中嚴格定義代數體系這個概念,隻能通俗地解釋。人們為解決某種運算問題,定義了一些資料對象及針對這些資料對象的一套運算規則,確定這些運算的封閉性和自洽性,就可以稱為一種代數體系了。比如說我們熟悉的有理數及其上的四則運算就是一種用于解決日常生活中數值計算需求的代數體系。封閉性是指計算結果必須仍然是定義過的資料對象,比如有理數的四則運算結果仍然是有理數。而自洽性指這些運算不能出現沖突的結果,比如我們要約定不能除以0,否則把某個數除以0規定成任何數都會推出邏輯沖突來。

這裡說的資料對象,和程式設計面向對象理論中資料對象不太一樣。前者主要強調資料上的運算,而後者更多強調對象的封裝性、繼承性和重載能力。前者是為了更好的描述和實施資料運算,後者則主要是為了代碼複用。

資料蔣堂 | SQL的困難源于關系代數

代數體系設計得好與不好,嚴重影響我們實施計算的友善度和效率!

舉兩個例子:

1. 我們從國小過的算術體系都采用阿拉伯數字,用來表示數值和做四則運算都很友善,但試想如果換成羅馬數字會是個什麼感覺?

2. 所有整數乘法都可以用加法表示,但如果我們在算術體系中引入了乘法來表示若幹個相同數相加這種運算,就可以發明九九表來做而不必硬加,效率可顯著提高。

要讓計算機實施計算,還需要一套基于代數體系的形式化語言,使用者把計算目标按約定的文法符号寫成代碼,就可以由計算機執行了。而用計算機解決問題的過程,也可以了解為把題目解法翻譯成某種形式化語言的過程。如果代數體系及其形式化語言設計得不好,就可能發生翻譯問題解法的難度大于解決問題本身的現象!用羅馬數字來實施四則運算就是這個結果。

資料蔣堂 | SQL的困難源于關系代數

關系代數就是用來實作批量結構化資料計算的代數體系,其形式化語言就是SQL。講述關系代數和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就會嚴重影響工作效率了。而且,SQL的不适應并非實作層面的問題,而是其基礎理論的問題,這不是在工程上進行優化就能解決的。面臨目前的資料運算需求,關系代數顯得過于簡單了,需要從數學上進行徹底的革新。

專欄作者簡介

資料蔣堂 | SQL的困難源于關系代數

潤乾軟體創始人、首席科學家

清華大學計算機碩士,著有《非線性報表模型原理》等,1989年,中國首個國際奧林匹克數學競賽團體冠軍成員,個人金牌;2000年,創立潤乾公司;2004年,首次在潤乾報表中提出非線性報表模型,完美解決了中國式複雜報表制表難題,目前該模型已經成為報表行業的标準;2014年,經過7年開發,潤乾軟體釋出不依賴關系代數模型的計算引擎——集算器,有效地提高了複雜結構化大資料計算的開發和運算效率;2015年,潤乾軟體被福布斯中文網站評為“2015福布斯中國非上市潛力企業100強”;2016年,榮獲中國電子資訊産業發展研究院評選的“2016年中國軟體和資訊服務業十大領軍人物”;2017年, 自主創新研發新一代的資料倉庫、雲資料庫等産品即将面世。

資料蔣堂

《資料蔣堂》的作者蔣步星,從事資訊系統建設和資料處理長達20多年的時間。他豐富的工程經驗與深厚的理論功底互相融合、創新思想與傳統觀念的互相碰撞,虛拟與現實的互相交織,産生出了一篇篇的瀝血之作。此連載的内容涉及從資料呈現、采集到加工計算再到存儲以及挖掘等各個方面。大可觀資料世界之遠景、小可看技術疑難之細節。針對資料領域一些技術難點,站在研發人員的角度從淺入深,進行全方位、360度無死角深度剖析;對于一些業内觀點,站在技術人員角度闡述自己的思考和了解。蔣步星還會對大資料的發展,站在業内專家角度給予預測和推斷。靜下心來認真研讀你會發現,《資料蔣堂》的文章,有的會讓使用者避免重複前人走過的彎路,有的會讓攻城獅面對紮心的難題茅塞頓開,有的會為初入行業的讀者提供一把開啟資料世界的鑰匙,有的甚至會讓業内專家大跌眼鏡,産生思想交鋒。

原文釋出時間為:2017-08-04

本文作者:蔣步星

本文來自雲栖社群合作夥伴“資料派THU”,了解相關資訊可以關注“資料派THU”微信公衆号