數(shù)據(jù)庫語言的目標(biāo)

數(shù)據(jù)庫語言的目標(biāo)

要說清這個(gè)目標(biāo)，先要理解數(shù)據(jù)庫是做什么的。數(shù)據(jù)庫這個(gè)軟件，名字中有個(gè)“庫”字，會(huì)讓人覺得它主要是為了存儲(chǔ)的。

其實(shí)不然，數(shù)據(jù)庫實(shí)現(xiàn)的重要功能有兩條：計(jì)算、事務(wù)！

也就是我們常說的 OLAP 和 OLTP，數(shù)據(jù)庫的存儲(chǔ)都是為這兩件事服務(wù)的，單純的存儲(chǔ)并不是數(shù)據(jù)庫的目標(biāo)。我們知道，SQL 是目前數(shù)據(jù)庫的主流語言。那么，用 SQL 做這兩件事是不是很方便呢？事務(wù)類功能主要解決數(shù)據(jù)在寫入和讀出時(shí)要保持的一致性，實(shí)現(xiàn)這件事的難度并不小，但對(duì)于應(yīng)用程序的接口卻非常簡單，用于操縱數(shù)據(jù)庫讀寫的代碼也很簡單。

如果假定目前關(guān)系數(shù)據(jù)庫的邏輯存儲(chǔ)模式是合理的（也就是用數(shù)據(jù)表和記錄來存儲(chǔ)數(shù)據(jù)，其合理性與否是另一個(gè)復(fù)雜問題，不在這里展開了），那么 SQL 在描述事務(wù)類功能時(shí)沒什么大問題，因?yàn)椴⒉恍枰枋龆鄰?fù)雜的動(dòng)作，復(fù)雜性都在數(shù)據(jù)庫內(nèi)部解決了。但計(jì)算類功能卻不一樣了。這里說的計(jì)算是個(gè)更廣泛的概念，并不只是簡單的加加減減，查找、關(guān)聯(lián)都可以看成是某種計(jì)算。

什么樣的計(jì)算體系才算好呢？

還是兩條：寫著簡單、跑得快。

寫著簡單，很好理解，就是讓程序員很快能寫出來代碼來，這樣單位時(shí)間內(nèi)可以完成更多的工作；跑得快就更容易理解，我們當(dāng)然希望更短時(shí)間內(nèi)獲得計(jì)算結(jié)果。其實(shí) SQL 中的 Q 就是查詢的意思，發(fā)明它的初衷主要是為了做查詢（也就是計(jì)算），這才是 SQL 的主要目標(biāo)。然而，SQL 在描述計(jì)算任務(wù)時(shí)，卻很難說是很勝任的。

SQL為什么不行

select max (consecutive_day)from (select count(*) (consecutive_day  from (select sum(rise_mark) over(order by trade_date) days_no_gain    

from (select trade_date,        

casewhenclosing_price>lag(closing_price)over(orderbytrade_date).
           
then0else1ENDrise_mark 
     
fromstock_price)) 

 groupbydays_no_gain)

這個(gè)語句的工作原理就不解釋了，反正有點(diǎn)繞，同學(xué)們可以自己嘗試一下。

SELECT TOP 10 x FROM T ORDER BY x DESC

但是，這個(gè)語句對(duì)應(yīng)的執(zhí)行邏輯是先對(duì)所有數(shù)據(jù)進(jìn)行大排序，然后再取出前 10 個(gè)，后面的不要了。大家知道，排序是一個(gè)很慢的動(dòng)作，會(huì)多次遍歷數(shù)據(jù)，如果數(shù)據(jù)量大到內(nèi)存裝不下，那還需要外存做緩存，性能還會(huì)進(jìn)一步急劇下降。如果嚴(yán)格按這句 SQL 體現(xiàn)的邏輯去執(zhí)行，這個(gè)運(yùn)算無論如何是跑不快的。

然而，很多程序員都知道這個(gè)運(yùn)算并不需要大排序，也用不著外存緩存，一次遍歷用一點(diǎn)點(diǎn)內(nèi)存就可以完成，也就是存在更高性能的算法。

可惜的是，用 SQL 卻寫不出這樣的算法，只能寄希望于數(shù)據(jù)庫的優(yōu)化器足夠聰明，能把這句 SQL 轉(zhuǎn)換成高性能算法執(zhí)行，但情況復(fù)雜時(shí)數(shù)據(jù)庫的優(yōu)化器也未必靠譜。

看樣子，SQL 在這兩方面做得都不夠好。這兩個(gè)并不復(fù)雜的問題都是這樣，現(xiàn)實(shí)中數(shù)千行的 SQL 代碼中，這種難寫且跑不快的情況比比皆是。為什么 SQL 不行呢？要回答這個(gè)問題，我們要分析一下用程序代碼實(shí)現(xiàn)計(jì)算到底是在干什么。

本質(zhì)上講，編寫程序的過程，就是把解決問題的思路翻譯成計(jì)算機(jī)可執(zhí)行的精確化形式語言的過程。

舉例來說，就象小學(xué)生解應(yīng)用題，分析問題想出解法之后，還要列出四則運(yùn)算表達(dá)式。用程序計(jì)算也是一樣，不僅要想出解決問題的方法，還要把解法翻譯成計(jì)算機(jī)能理解執(zhí)行的動(dòng)作才算完成。用于描述計(jì)算方法的形式語言，其核心在于所采用的代數(shù)體系。所謂代數(shù)體系，簡單說就是一些數(shù)據(jù)類型和其上的運(yùn)算規(guī)則，比如小學(xué)學(xué)到的算術(shù)，就是整數(shù)和加減乘除運(yùn)算。

有了這套東西，我們就能把想做的運(yùn)算用這個(gè)代數(shù)體系約定的符號(hào)寫出來，也就是代碼，然后計(jì)算機(jī)就可以執(zhí)行了。如果這個(gè)代數(shù)體系設(shè)計(jì)時(shí)考慮不周到，提供的數(shù)據(jù)類型和運(yùn)算不方便，那就會(huì)導(dǎo)致描述算法非常困難。

這時(shí)候會(huì)發(fā)生一個(gè)怪現(xiàn)象：翻譯解法到代碼的難度遠(yuǎn)遠(yuǎn)超過解決問題本身。

舉個(gè)例子，我們從小學(xué)習(xí)用阿拉伯?dāng)?shù)字做日常計(jì)算，做加減乘除都很方便，所有人都天經(jīng)地義認(rèn)為數(shù)值運(yùn)算就該是這樣的。其實(shí)未必！估計(jì)很多人都知道還有一種叫做羅馬數(shù)字的東西，你知道用羅馬數(shù)字該怎么做加減乘除嗎？古羅馬人又是如何上街買菜的？代碼難寫很大程度是代數(shù)的問題。再看跑不快的原因。

軟件沒辦法改變硬件的性能，CPU 和硬盤該多快就是多快。不過，我們可以設(shè)計(jì)出低復(fù)雜度的算法，也就是計(jì)算量更小的算法，這樣計(jì)算機(jī)執(zhí)行的動(dòng)作變少，自然也就會(huì)快了。但是，光想出算法還不夠，還要把這個(gè)算法用某種形式語言寫得出來才行，否則計(jì)算機(jī)不會(huì)執(zhí)行。而且，寫起來還要比較簡單，都要寫很長很麻煩，也沒有人會(huì)去用。

所以呢，對(duì)于程序來講，跑得快和寫著簡單其實(shí)是同一個(gè)問題，背后還是這個(gè)形式語言采用的代數(shù)的問題。如果這個(gè)代數(shù)不好，就會(huì)導(dǎo)致高性能算法很難實(shí)現(xiàn)甚至實(shí)現(xiàn)不了，也就沒辦法跑得快了。

就象上面說的，用 SQL 寫不出我們期望的小內(nèi)存單次遍歷算法，能不能跑得快就只能寄希望于優(yōu)化器。我們再做個(gè)類比：上過小學(xué)的同學(xué)大概都知道高斯計(jì)算 1+2+3+…+100 的小故事。

普通人就是一步步地硬加 100 次，高斯小朋友很聰明，發(fā)現(xiàn) 1+100=101、2+99=101、…、50+51=101，結(jié)果是 50 乘 101，很快算完回家午飯了。

聽過這個(gè)故事，我們都會(huì)感慨高斯很聰明，能想到這么巧妙的辦法，即簡單又迅速。這沒有錯(cuò)，但是，大家容易忽略一點(diǎn)：在高斯的時(shí)代，人類的算術(shù)體系（也是一個(gè)代數(shù)）中已經(jīng)有了乘法！象前面所說，我們從小學(xué)習(xí)四則運(yùn)算，會(huì)覺得乘法是理所當(dāng)然的，然而并不是！乘法是后于加法被發(fā)明出來的。

如果高斯的年代還沒有乘法，即使有聰明的高斯，也沒辦法快速解決這個(gè)問題。目前主流數(shù)據(jù)庫是關(guān)系數(shù)據(jù)庫，之所以這么叫，是因?yàn)樗臄?shù)學(xué)基礎(chǔ)被稱為關(guān)系代數(shù)，SQL 也就是關(guān)系代數(shù)理論上發(fā)展出來的形式語言?，F(xiàn)在我們能回答，為什么 SQL 在期望的兩個(gè)方面做得不夠好？

問題出在關(guān)系代數(shù)上，關(guān)系代數(shù)就像一個(gè)只有加法還沒發(fā)明乘法的算術(shù)體系，很多事做不好是必然的。關(guān)系代數(shù)已經(jīng)發(fā)明五十年了，五十年前的應(yīng)用需求以及硬件環(huán)境，和今天比的差異是很巨大了，繼續(xù)延用五十年前的理論來解決今天的問題，聽著就感覺太陳舊了？

然而現(xiàn)實(shí)就是這樣，由于存量用戶太多，而且也還沒有成熟的新技術(shù)出現(xiàn)，基于關(guān)系代數(shù)的 SQL，今天仍然是最重要的數(shù)據(jù)庫語言。

雖然這幾十年來也有一些改進(jìn)完善，但根子并沒有變，面對(duì)當(dāng)代的復(fù)雜需求和硬件環(huán)境，SQL 不勝任也是情理之中的事。而且，不幸的是，這個(gè)問題是理論上的，在工程上無論如何優(yōu)化也無濟(jì)于事，只能有限改善，不能根除。

不過，絕大部分的數(shù)據(jù)庫開發(fā)者并不會(huì)想到這一層，或者說為了照顧存量用戶的兼容性，也沒打算想到這一層。于是，主流數(shù)據(jù)庫界一直在這個(gè)圈圈里打轉(zhuǎn)轉(zhuǎn)。

SPL為什么能行

那么該怎樣讓計(jì)算寫著更簡單、跑得更快呢？

發(fā)明新的代數(shù)！

有“乘法”的代數(shù)。在其基礎(chǔ)上再設(shè)計(jì)新的語言。這就是 SPL 的由來。它的理論基礎(chǔ)不再是關(guān)系代數(shù)，稱為離散數(shù)據(jù)集。

基于這個(gè)新代數(shù)設(shè)計(jì)的形式語言，起名為SPL（Structured Process Language）。

SPL 針對(duì) SQL 的不足（更確切地說法是，離散數(shù)據(jù)集針對(duì)關(guān)系代數(shù)的各種缺陷）進(jìn)行了革新。

SPL 重新定義了并擴(kuò)展許多結(jié)構(gòu)化數(shù)據(jù)中的運(yùn)算，增加了離散性、強(qiáng)化了有序計(jì)算、實(shí)現(xiàn)了徹底的集合化、支持對(duì)象引用、提倡分步運(yùn)算。限于篇幅，這里不能介紹 SPL（離散數(shù)據(jù)集）的全貌。

我們在這里列舉 SPL（離散數(shù)據(jù)集）針對(duì) SQL（關(guān)系代數(shù)）的部分差異化改進(jìn)：游離記錄

離散數(shù)據(jù)集中的記錄是一種基本數(shù)據(jù)類型，它可以不依賴于數(shù)據(jù)表而獨(dú)立存在。

數(shù)據(jù)表是記錄構(gòu)成的集合，而構(gòu)成某個(gè)數(shù)據(jù)表的記錄還可以用于構(gòu)成其它數(shù)據(jù)表。比如過濾運(yùn)算就是用原數(shù)據(jù)表中滿足條件的記錄構(gòu)成新數(shù)據(jù)表，這樣，無論空間占用還是運(yùn)算性能都更有優(yōu)勢。

關(guān)系代數(shù)沒有可運(yùn)算的數(shù)據(jù)類型來表示記錄，單記錄實(shí)際上是只有一行的數(shù)據(jù)表，不同數(shù)據(jù)表中的記錄也不能共享。比如，過濾運(yùn)算時(shí)會(huì)復(fù)制出新記錄來構(gòu)成新數(shù)據(jù)表，空間和時(shí)間成本都變大。特別地，因?yàn)橛杏坞x記錄，離散數(shù)據(jù)集允許記錄的字段取值是某個(gè)記錄，這樣可以更方便地實(shí)現(xiàn)外鍵連接。

有序性

關(guān)系代數(shù)是基于無序集合設(shè)計(jì)的，集合成員沒有序號(hào)的概念，也沒有提供定位計(jì)算以及相鄰引用的機(jī)制。SQL 實(shí)踐時(shí)在工程上做了一些局部完善，使得現(xiàn)代 SQL 能方便地進(jìn)行一部分有序運(yùn)算。

離散數(shù)據(jù)集中的集合是有序的，集合成員都有序號(hào)的概念，可以用序號(hào)訪問成員，并定義了定位運(yùn)算以返回成員在集合中的序號(hào)。

離散數(shù)據(jù)集提供了符號(hào)以在集合運(yùn)算中實(shí)現(xiàn)相鄰引用，并支持針對(duì)集合中某個(gè)序號(hào)位置進(jìn)行計(jì)算。有序運(yùn)算很常見，卻一直是 SQL 的困難問題，即使在有了窗口函數(shù)后仍然很繁瑣。

SPL 則大大改善了這個(gè)局面，前面那個(gè)股票上漲的例子就能說明問題。

離散性與集合化

關(guān)系代數(shù)中定義了豐富的集合運(yùn)算，即能將集合作為整體參加運(yùn)算，比如聚合、分組等。

這是 SQL 比 Java 等高級(jí)語言更為方便的地方。但關(guān)系代數(shù)的離散性非常差，沒有游離記錄。而 Java 等高級(jí)語言在這方面則沒有問題。離散數(shù)據(jù)集則相當(dāng)于將離散性和集合化結(jié)合起來了，既有集合數(shù)據(jù)類型及相關(guān)的運(yùn)算，也有集合成員游離在集合之外單獨(dú)運(yùn)算或再組成其它集合。

可以說 SPL 集中了 SQL 和 Java 兩者的優(yōu)勢。有序運(yùn)算是典型的離散性與集合化的結(jié)合場景。次序的概念只有在集合中才有意義，單個(gè)成員無所謂次序，這里體現(xiàn)了集合化；而有序計(jì)算又需要針對(duì)某個(gè)成員及其相鄰成員進(jìn)行計(jì)算，需要離散性。

在離散性的支持下才能獲得更徹底的集合化，才能解決諸如有序計(jì)算類型的問題。離散數(shù)據(jù)集是即有離散性又有集合化的代數(shù)體系，關(guān)系代數(shù)只有集合化。

分組理解

分組運(yùn)算的本意是將一個(gè)大集合按某種規(guī)則拆成若干個(gè)子集合，關(guān)系代數(shù)中沒有數(shù)據(jù)類型能夠表示集合的集合，于是強(qiáng)迫在分組后做聚合運(yùn)算。離散數(shù)據(jù)集中允許集合的集合，可以表示合理的分組運(yùn)算結(jié)果，分組和分組后的聚合被拆分成相互獨(dú)立的兩步運(yùn)算，這樣可以針對(duì)分組子集再進(jìn)行更復(fù)雜的運(yùn)算。

關(guān)系代數(shù)中只有一種等值分組，即按分組鍵值劃分集合，等值分組是個(gè)完全劃分。離散數(shù)據(jù)集認(rèn)為任何拆分大集合的方法都是分組運(yùn)算，除了常規(guī)的等值分組外，還提供了與有序性結(jié)合的有序分組，以及可能得到不完全劃分結(jié)果的對(duì)位分組。

聚合理解

關(guān)系代數(shù)中沒有顯式的集合數(shù)據(jù)類型，聚合計(jì)算的結(jié)果都是單值，分組后的聚合運(yùn)算也是這樣，只有 SUM、COUNT、MAX、MIN 等幾種。

特別地，關(guān)系代數(shù)無法把 TOPN 運(yùn)算看成是聚合，針對(duì)全集的 TOPN 只能在輸出結(jié)果集時(shí)排序后取前 N 條，而針對(duì)分組子集則很難做到 TOPN，需要轉(zhuǎn)變思路拼出序號(hào)才能完成。

離散數(shù)據(jù)集提倡普遍集合，聚合運(yùn)算的結(jié)果不一定是單值，仍然可能是個(gè)集合。在離散數(shù)據(jù)集中，TOPN 運(yùn)算和 SUM、COUNT 這些是地位等同的，即可以針對(duì)全集也可以針對(duì)分組子集。

SPL 把 TOPN 理解成聚合運(yùn)算后，在工程實(shí)現(xiàn)時(shí)還可以避免全量數(shù)據(jù)的排序，從而獲得高性能。而 SQL 的 TOPN 總是伴隨 ORDER BY 動(dòng)作，理論上需要大排序才能實(shí)現(xiàn)，需要寄希望于數(shù)據(jù)庫在工程實(shí)現(xiàn)時(shí)做優(yōu)化。

有序支持的高性能

離散數(shù)據(jù)集特別強(qiáng)調(diào)有序集合，利用有序的特征可以實(shí)施很多高性能算法。這是基于無序集合的關(guān)系代數(shù)無能為力的，只能寄希望于工程上的優(yōu)化。

下面是部分利用有序特征后可以實(shí)施的低復(fù)雜度運(yùn)算：

1） 數(shù)據(jù)表對(duì)主鍵有序，相當(dāng)于天然有一個(gè)索引。對(duì)鍵字段的過濾經(jīng)?？梢钥焖俣ㄎ唬詼p少外存遍歷量。隨機(jī)按鍵值取數(shù)時(shí)也可以用二分法定位，在同時(shí)針對(duì)多個(gè)鍵值取數(shù)時(shí)還能重復(fù)利用索引信息。

2） 通常的分組運(yùn)算是用 HASH 算法實(shí)現(xiàn)的，如果我們確定地知道數(shù)據(jù)對(duì)分組鍵值有序，則可以只做相鄰對(duì)比，避免計(jì)算 HASH 值，也不會(huì)有 HASH 沖突的問題，而且非常容易并行。

3） 數(shù)據(jù)表對(duì)鍵有序，兩個(gè)大表之間對(duì)位連接可以執(zhí)行更高性能的歸并算法，只要對(duì)數(shù)據(jù)遍歷一次，不必緩存，對(duì)內(nèi)存占用很??；而傳統(tǒng)的 HASH 值分堆方法不僅比較復(fù)雜度高，需要較大內(nèi)存并做外部緩存，還可能因 HASH 函數(shù)不當(dāng)而造成二次 HASH 再緩存。

4） 大表作為外鍵表的連接。事實(shí)表小時(shí)，可以利用外鍵表有序，快速從中取出關(guān)聯(lián)鍵值對(duì)應(yīng)的數(shù)據(jù)實(shí)現(xiàn)連接，不需要做 HASH 分堆動(dòng)作。事實(shí)表也很大時(shí)，可以將外鍵表用分位點(diǎn)分成多個(gè)邏輯段，再將事實(shí)表按邏輯段進(jìn)行分堆，這樣只需要對(duì)一個(gè)表做分堆，而且分堆過程中不會(huì)出現(xiàn) HASH 分堆時(shí)的可能出現(xiàn)的二次分堆，計(jì)算復(fù)雜度能大幅下降。

其中 3 和 4 利用了離散數(shù)據(jù)集對(duì)連接運(yùn)算的改造，如果仍然延用關(guān)系代數(shù)的定義（可能產(chǎn)生多對(duì)多），則很難實(shí)現(xiàn)這種低復(fù)雜的算法。除了理論上的差異， SPL 還有許多工程層面的優(yōu)勢，比如更易于編寫并行代碼、大內(nèi)存預(yù)關(guān)聯(lián)提高外鍵連接性能等、特有的列存機(jī)制以支持隨意分段并行等。

再把前面的問題用 SPL 重寫一遍有個(gè)直接感受。一支股票最長連續(xù)上漲多少天：

stock_price.sort(trade_date).group@i(closing_price<closing_price[-1]).max(~.len())

計(jì)算思路和前面的 SQL 相同，但因?yàn)橐肓擞行蛐院?，表達(dá)起來容易多了，不再繞了。

T.groups(;top(-10,x))

SPL 有更豐富的集合數(shù)據(jù)類型，容易描述單次遍歷上實(shí)施簡單聚合的高效算法，不涉及大排序動(dòng)作。