比SQL還好用,又一門國產資料庫語言誕生了

語言: CN / TW / HK

theme: juejin highlight: a11y-dark


資料庫語言的目標

要說清這個目標,先要理解資料庫是做什麼的。

資料庫這個軟體,名字中有個“庫”字,會讓人覺得它主要是為了儲存的。其實不然,資料庫實現的重要功能有兩條:計算事務!也就是我們常說的OLAP和OLTP,資料庫的儲存都是為這兩件事服務的,單純的儲存並不是資料庫的目標。

我們知道,SQL是目前資料庫的主流語言。那麼,用SQL做這兩件事是不是很方便呢?

image.png

事務類功能主要解決資料在寫入和讀出時要保持的一致性,實現這件事的難度並不小,但對於應用程式的介面卻非常簡單,用於操縱資料庫讀寫的程式碼也很簡單。如果假定目前關係資料庫的邏輯儲存模式是合理的(也就是用資料表和記錄來儲存資料,其合理性與否是另一個複雜問題,不在這裡展開了),那麼SQL在描述事務類功能時沒什麼大問題,因為並不需要描述多複雜的動作,複雜性都在資料庫內部解決了。

但計算類功能卻不一樣了。

這裡說的計算是個更廣泛的概念,並不只是簡單的加加減減,查詢、關聯都可以看成是某種計算。

什麼樣的計算體系才算好呢?

還是兩條:寫著簡單跑得快

image.png

寫著簡單,很好理解,就是讓程式設計師很快能寫出來程式碼來,這樣單位時間內可以完成更多的工作;跑得快就更容易理解,我們當然希望更短時間內獲得計算結果。

其實SQL中的Q就是查詢的意思,發明它的初衷主要是為了做查詢(也就是計算),這才是SQL的主要目標。然而,SQL在描述計算任務時,卻很難說是很勝任的。

SQL為什麼不行

先看寫著簡單的問題。

SQL寫出來很象英語,有些查詢可以當英語來讀和寫(網上多得很,就不舉例了),這應當算是滿足寫著簡單這一條了吧。

且慢!我們在教科書上看到的SQL經常只有兩三行,這些SQL確實算是寫著簡單的,但如果我們嘗試一些稍複雜化的問題呢?

這是一個其實還不算很複雜的例子:計算一支股票最長連續上漲了多少天?用SQL寫出來是這樣的: 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, case when closing_price>lag(closing_price) over(order by trade_date) then 0 else 1 END rise_mark from stock_price ) ) group by days_no_gain) 這個語句的工作原理就不解釋了,反正有點繞,同學們可以自己嘗試一下。

這是潤乾公司的招聘考題,通過率不足20%;因為太難,後來被改成另一種方式:把SQL語句寫出來讓應聘者解釋它在算什麼,通過率依然不高。

這說明什麼?說明情況稍有複雜,SQL就變得即難懂又難寫!

再看跑得快的問題,還是一個經常拿出來的簡單例子:1億條資料中取前10名。這個任務用SQL寫出來並不複雜: sql SELECT TOP 10 x FROM T ORDER BY x DESC 但是,這個語句對應的執行邏輯是先對所有資料進行大排序,然後再取出前10個,後面的不要了。大家知道,排序是一個很慢的動作,會多次遍歷資料,如果資料量大到記憶體裝不下,那還需要外存做快取,效能還會進一步急劇下降。如果嚴格按這句SQL體現的邏輯去執行,這個運算無論如何是跑不快的。然而,很多程式設計師都知道這個運算並不需要大排序,也用不著外存快取,一次遍歷用一點點記憶體就可以完成,也就是存在更高效能的演算法。可惜的是,用SQL卻寫不出這樣的演算法,只能寄希望於資料庫的優化器足夠聰明,能把這句SQL轉換成高效能演算法執行,但情況複雜時資料庫的優化器也未必靠譜。

看樣子,SQL在這兩方面做得都不夠好。這兩個並不複雜的問題都是這樣,現實中數千行的SQL程式碼中,這種難寫且跑不快的情況比比皆是。

為什麼SQL不行呢?

要回答這個問題,我們要分析一下用程式程式碼實現計算到底是在幹什麼。

本質上講,編寫程式的過程,就是把解決問題的思路翻譯成計算機可執行的精確化形式語言的過程。舉例來說,就象小學生解應用題,分析問題想出解法之後,還要列出四則運算表示式。用程式計算也是一樣,不僅要想出解決問題的方法,還要把解法翻譯成計算機能理解執行的動作才算完成。

用於描述計算方法的形式語言,其核心在於所採用的代數體系。所謂代數體系,簡單說就是一些資料型別和其上的運算規則,比如小學學到的算術,就是整數和加減乘除運算。有了這套東西,我們就能把想做的運算用這個代數體系約定的符號寫出來,也就是程式碼,然後計算機就可以執行了。

如果這個代數體系設計時考慮不周到,提供的資料型別和運算不方便,那就會導致描述演算法非常困難。這時候會發生一個怪現象:翻譯解法到程式碼的難度遠遠超過解決問題本身

舉個例子,我們從小學習用阿拉伯數字做日常計算,做加減乘除都很方便,所有人都天經地義認為數值運算就該是這樣的。其實未必!估計很多人都知道還有一種叫做羅馬數字的東西,你知道用羅馬數字該怎麼做加減乘除嗎?古羅馬人又是如何上街買菜的?

程式碼難寫很大程度是代數的問題

再看跑不快的原因。

軟體沒辦法改變硬體的效能,CPU和硬碟該多快就是多快。不過,我們可以設計出低複雜度的演算法,也就是計算量更小的演算法,這樣計算機執行的動作變少,自然也就會快了。但是,光想出演算法還不夠,還要把這個演算法用某種形式語言寫得出來才行,否則計算機不會執行。而且,寫起來還要比較簡單,都要寫很長很麻煩,也沒有人會去用。所以呢,對於程式來講,跑得快和寫著簡單其實是同一個問題,背後還是這個形式語言採用的代數的問題。如果這個代數不好,就會導致高效能演算法很難實現甚至實現不了,也就沒辦法跑得快了。就象上面說的,用SQL寫不出我們期望的小記憶體單次遍歷演算法,能不能跑得快就只能寄希望於優化器。

我們再做個類比:

上過小學的同學大概都知道高斯計算1+2+3+...+100的小故事。普通人就是一步步地硬加100次,高斯小朋友很聰明,發現1+100=101、2+99=101、...、50+51=101,結果是50乘101,很快算完回家午飯了。

聽過這個故事,我們都會感慨高斯很聰明,能想到這麼巧妙的辦法,即簡單又迅速。這沒有錯,但是,大家容易忽略一點:在高斯的時代,人類的算術體系(也是一個代數)中已經有了乘法!象前面所說,我們從小學習四則運算,會覺得乘法是理所當然的,然而並不是!乘法是後於加法被髮明出來的。如果高斯的年代還沒有乘法,即使有聰明的高斯,也沒辦法快速解決這個問題。

目前主流資料庫是關係資料庫,之所以這麼叫,是因為它的數學基礎被稱為關係代數,SQL也就是關係代數理論上發展出來的形式語言。

現在我們能回答,為什麼SQL在期望的兩個方面做得不夠好?問題出在關係代數上,關係代數就像一個只有加法還沒發明乘法的算術體系,很多事做不好是必然的。

關係代數已經發明五十年了,五十年前的應用需求以及硬體環境,和今天比的差異是很巨大了,繼續延用五十年前的理論來解決今天的問題,聽著就感覺太陳舊了?然而現實就是這樣,由於存量使用者太多,而且也還沒有成熟的新技術出現,基於關係代數的SQL,今天仍然是最重要的資料庫語言。雖然這幾十年來也有一些改進完善,但根子並沒有變,面對當代的複雜需求和硬體環境,SQL不勝任也是情理之中的事。

而且,不幸的是,這個問題是理論上的,在工程上無論如何優化也無濟於事,只能有限改善,不能根除。不過,絕大部分的資料庫開發者並不會想到這一層,或者說為了照顧存量使用者的相容性,也沒打算想到這一層。於是,主流資料庫界一直在這個圈圈裡打轉轉。

SPL為什麼能行

那麼該怎樣讓計算寫著更簡單、跑得更快呢?

發明新的代數!有“乘法”的代數。在其基礎上再設計新的語言。

這就是SPL的由來。它的理論基礎不再是關係代數,稱為離散資料集。基於這個新代數設計的形式語言,起名為SPL(Structured Process Language)。

SPL針對SQL的不足(更確切地說法是,離散資料集針對關係代數的各種缺陷)進行了革新。SPL重新定義了並擴充套件許多結構化資料中的運算,增加了離散性、強化了有序計算、實現了徹底的集合化、支援物件引用、提倡分步運算。

把前面的問題用SPL重寫一遍有個直接感受。

一支股票最長連續上漲多少天:

image.png sql stock_price.sort(trade_date).group@i(closing_price<closing_price[-1]).max(~.len()) 計算思路和前面的SQL相同,但因為引入了有序性後,表達起來容易多了,不再繞了。

1億條資料中取前10名: sql T.groups(;top(-10,x)) SPL有更豐富的集合資料型別,容易描述單次遍歷上實施簡單聚合的高效演算法,不涉及大排序動作。

限於篇幅,這裡不能介紹SPL(離散資料集)的全貌。我們在這裡列舉SPL(離散資料集)針對SQL(關係代數)的部分差異化改進:

遊離記錄

離散資料集中的記錄是一種基本資料型別,它可以不依賴於資料表而獨立存在。資料表是記錄構成的集合,而構成某個資料表的記錄還可以用於構成其它資料表。比如過濾運算就是用原資料表中滿足條件的記錄構成新資料表,這樣,無論空間佔用還是運算效能都更有優勢。

關係代數沒有可運算的資料型別來表示記錄,單記錄實際上是隻有一行的資料表,不同資料表中的記錄也不能共享。比如,過濾運算時會複製出新記錄來構成新資料表,空間和時間成本都變大。

特別地,因為有遊離記錄,離散資料集允許記錄的欄位取值是某個記錄,這樣可以更方便地實現外來鍵連線。

有序性

關係代數是基於無序集合設計的,集合成員沒有序號的概念,也沒有提供定位計算以及相鄰引用的機制。SQL實踐時在工程上做了一些區域性完善,使得現代SQL能方便地進行一部分有序運算。

離散資料集中的集合是有序的,集合成員都有序號的概念,可以用序號訪問成員,並定義了定位運算以返回成員在集合中的序號。離散資料集提供了符號以在集合運算中實現相鄰引用,並支援針對集合中某個序號位置進行計算。

有序運算很常見,卻一直是SQL的困難問題,即使在有了視窗函式後仍然很繁瑣。SPL則大大改善了這個局面,前面那個股票上漲的例子就能說明問題。

離散性與集合化

關係代數中定義了豐富的集合運算,即能將集合作為整體參加運算,比如聚合、分組等。這是SQL比Java等高階語言更為方便的地方。

但關係代數的離散性非常差,沒有遊離記錄。而Java等高階語言在這方面則沒有問題。

離散資料集則相當於將離散性和集合化結合起來了,既有集合資料型別及相關的運算,也有集合成員遊離在集合之外單獨運算或再組成其它集合。可以說SPL集中了SQL和Java兩者的優勢。

有序運算是典型的離散性與集合化的結合場景。次序的概念只有在集合中才有意義,單個成員無所謂次序,這裡體現了集合化;而有序計算又需要針對某個成員及其相鄰成員進行計算,需要離散性。

在離散性的支援下才能獲得更徹底的集合化,才能解決諸如有序計算型別的問題。

離散資料集是即有離散性又有集合化的代數體系,關係代數只有集合化。

分組理解

分組運算的本意是將一個大集合按某種規則拆成若干個子集合,關係代數中沒有資料型別能夠表示集合的集合,於是強迫在分組後做聚合運算。

離散資料集中允許集合的集合,可以表示合理的分組運算結果,分組和分組後的聚合被拆分成相互獨立的兩步運算,這樣可以針對分組子集再進行更復雜的運算。

關係代數中只有一種等值分組,即按分組鍵值劃分集合,等值分組是個完全劃分。

離散資料集認為任何拆分大集合的方法都是分組運算,除了常規的等值分組外,還提供了與有序性結合的有序分組,以及可能得到不完全劃分結果的對位分組。

聚合理解

關係代數中沒有顯式的集合資料型別,聚合計算的結果都是單值,分組後的聚合運算也是這樣,只有SUM、COUNT、MAX、MIN等幾種。特別地,關係代數無法把TOPN運算看成是聚合,針對全集的TOPN只能在輸出結果集時排序後取前N條,而針對分組子集則很難做到TOPN,需要轉變思路拼出序號才能完成。

離散資料集提倡普遍集合,聚合運算的結果不一定是單值,仍然可能是個集合。在離散資料集中,TOPN運算和SUM、COUNT這些是地位等同的,即可以針對全集也可以針對分組子集。

SPL把TOPN理解成聚合運算後,在工程實現時還可以避免全量資料的排序,從而獲得高效能。而SQL的TOPN總是伴隨ORDER BY動作,理論上需要大排序才能實現,需要寄希望於資料庫在工程實現時做優化。

有序支援的高效能

離散資料集特別強調有序集合,利用有序的特徵可以實施很多高效能演算法。這是基於無序集合的關係代數無能為力的,只能寄希望於工程上的優化。

下面是部分利用有序特徵後可以實施的低複雜度運算:

1)資料表對主鍵有序,相當於天然有一個索引。對鍵欄位的過濾經常可以快速定位,以減少外存遍歷量。隨機按鍵值取數時也可以用二分法定位,在同時針對多個鍵值取數時還能重複利用索引資訊。

2)通常的分組運算是用HASH演算法實現的,如果我們確定地知道資料對分組鍵值有序,則可以只做相鄰對比,避免計算HASH值,也不會有HASH衝突的問題,而且非常容易並行。

3)資料表對鍵有序,兩個大表之間對位連線可以執行更高效能的歸併演算法,只要對資料遍歷一次,不必快取,對記憶體佔用很小;而傳統的HASH值分堆方法不僅比較複雜度高,需要較大記憶體並做外部快取,還可能因HASH函式不當而造成二次HASH再快取。

4)大表作為外來鍵表的連線。事實表小時,可以利用外來鍵表有序,快速從中取出關聯鍵值對應的資料實現連線,不需要做HASH分堆動作。事實表也很大時,可以將外來鍵表用分位點分成多個邏輯段,再將事實表按邏輯段進行分堆,這樣只需要對一個表做分堆,而且分堆過程中不會出現HASH分堆時的可能出現的二次分堆,計算複雜度能大幅下降。

其中3和4利用了離散資料集對連線運算的改造,如果仍然延用關係代數的定義(可能產生多對多),則很難實現這種低複雜的演算法。

除了理論上的差異, SPL還有許多工程層面的優勢,比如更易於編寫並行程式碼、大記憶體預關聯提高外來鍵連線效能等、特有的列存機制以支援隨意分段並行等。

這裡還有更多SPL程式碼以體現其思路及大資料演算法: - 效能優化技巧:遍歷複用提速多次分組 - 效能優化技巧:TopN - 效能優化技巧:預關聯 - 效能優化技巧:部分預關聯 - 效能優化技巧:外來鍵序號化 - 效能優化技巧:維表過濾或計算時的關聯 - 效能優化技巧:有序歸併 - 效能優化技巧:有序定位關聯提速主子關聯後的過濾 - 效能優化技巧:附表 - 效能優化技巧:小事實表與大維表關聯 - 效能優化技巧:大事實表與大維表關聯 - 效能優化技巧:有序分組 - 效能優化技巧:後半有序分組 - 效能優化技巧:前半有序時的排序

SPL交流群

「其他文章」