程序员 php shell 编程 linux Firefox centos java wordpress nginx 开源 apache 微软 Ubuntu mysql Android Windows google Python 云计算

原廠解讀:達夢數據庫列存儲技術原理與實現

本次分享內容由三個部分組成:

列存儲數據組織實現

智能索引的實現

自適應壓縮算法

目前數據庫主流數據組織技術分為數據按行存儲和數據按列存儲,達夢數據庫表數據的存儲方式同時支持行存儲和列存儲。行存儲是以記錄為單位進行存儲的,數據頁面中存儲的是完整的若幹條記錄;列存儲是以列為單位進行存儲的,每一個列的所有行數據都存儲在一起,一個段只存儲一個列的數據,而且一個指定的頁面中存儲的都是某一個列的連續數據。

列存表的存儲方式有以下幾個優點:

同一個列的數據都是連續存儲的,可以加快某一個列的數據查詢速度(相對行存減小不必要IO);

  1.  

    20160617105403839.jpg 

     

  2. 連續存儲的列數據,具有更大的壓縮單元和數據相似性,可以獲得遠優於行存儲的壓縮效率;

    條件掃描借助數據區的統計信息進行精確過濾,可以進一步減少IO,提高掃描效率(智能索引)。

    下面我們主要介紹達夢數據庫的列存儲的技術特點及具體實現,並詳細介紹列存儲的數據組織方式、智能索引的實現、自適應壓縮算法設計。

      1 列存儲數據組織實現

    達夢的列存儲表又叫HUGE表,是建立在HTS表空間上的(全稱HUGE TABLESPACE)。這個表空間與普通的表空間不同。普通的表空間,數據是通過段、簇、頁來管理的,並且以固定大小(4K、8K、16K、32K)的頁面為管理單位;而HTS相當於一個簡單的文件系統,創建一個HTS,其實就是創建一個空的目錄。在創建一個HFS表之後,數據庫會在指定的HTS表空間目錄下創建一系列的目錄及文件,文件系統結構如下圖所示:

 

20160617105351658.jpg

從上圖可以看出,在HTS目錄下成功創建HFS表,系統內部需要經過以下步驟: 首先,在HTS目錄下創建這個表對應的模式目錄。目錄名為“SCH+長度為9的ID號”組成的字符串。

其次,在模式目錄下創建對應的表目錄。表目錄也是同樣的道理,表目錄名為“TAB+長度為4的ID號”組成的字符串。表目錄中存放的是這個表中所有的文件。

再次,在新創建表時,每一個列對應的一個以dta為後綴的文件,文件大小可以在建表時指定,默認為64M,文件名為“col+長度為4的列號+_+長度為10的文件號”。例如,在上圖中,0000表示第1列,0001表示第2列……;0000000000表示第1個文件,0000000001表示第2個文件……最初一個列只有一個文件即可,當隨著數據量不斷增長,一個文件已放不下之後,系統會自動創建新的文件來存儲不斷增長的數據。

對於一個文件,其內部存儲是按照區來管理的,區是文件內部數據管理的最小單位,也是唯一的單位(類似於行存的頁)。一個區中,可以存儲單列數據的行數是通過創建表時指定的,一經指定,在這個表的生命過程就不能再修改。

一個區內,存儲的僅僅是數據而已,對於NULLABLE屬性的列,存儲的還有相應的NULL標誌。每一個區的開始位置及長度在文件內都是4K對齊的。對於一個HFS表,相應的還配備一個輔助表來管理其數據。

因為在上面介紹的文件中只存儲了數據,輔助表用來管理以及輔助系統用戶操作這些數據,該輔助表是在創建HFS表時系統自動創建的。輔助表中每一條記錄對應文件中的一個數據區,輔助表包括下面15列:

COLID:表示當前這條記錄對應的區所在的列的列ID號;

SEC_ID:表示當前這個記錄對應的區的區ID號,每一個區都有一個ID號,並且唯一;

FILE_ID:表示這個區的數據所在的文件號;

OFFSET:表示這個區的數據在文件中的偏移位置,4K對齊;

COUNT:表示這個區中存儲的數據總數(有可能包括被刪除的數據);

ACOUNT:表示這個區中存儲的實際數據行數;

N_LEN:表示這個區中存儲的數據在文件中的長度,4K對齊的;

N_NULL:表示這個區中的數據中包括的NULL值的行數;

N_DIST:表示這個區中所有數據互不相同的行數;

MAX_VAL:表示這個區中的最大值,精確值;

MIN_VAL:表示這個區中的最小值,精確值;

SUM_VAL:表示這個區中所有值的和,精確值;

CPR_FLAG:表示這個區是否壓縮;

ENC_FLAG:表示這個區是否加密;

CHKSUM:用來較驗的,該功能暫未啟用。

 

 

前面7列是用来控制数据存取的,根据这些信息就可以知道这个区的具体存储位置、长度及基本信息。后面8列都是用来对这个区进行

統計分析的。其中,COLID和SEC_ID的組合鍵為輔助表的聚簇關鍵字。

實際上數據庫對列存數據的查找過程就是通過對輔助表信息的檢索,利用輔助信息操縱HTS目錄下文件的過程。

  2 智能索引的實現

列存表做條件掃描可以借助數據區的統計信息進行精確過濾,可以進一步減少IO,提高掃描效率。數據區的統計信息是數據庫系統自動維護的,在一定程度上可以替代BTree索引,所以被一些廠商稱為“智能索引”。

下圖為區最大值、最小值信息起到過濾作用的示意圖:

 

20160617105334617.png

 

除了最大值、最小值起到跳區掃描減少IO的作用,區和值、區內有效行數等其它信息在一些統計分析場景甚至可以完全避免數據區的掃描。如MAX(),COUNT(),AVG()等一些函數可以直接通過查詢輔助表獲得。

  3 自適應壓縮算法

連續存儲的列數據,具有更大的壓縮單元和數據相似性,可以獲得遠優於行存儲的壓縮效率。根據列存儲的特性,達夢提供一套自適應的壓縮算法,可以根據數據特性以區為單位自動選擇相應的算法最大化壓縮率和性能。

下面詳細介紹4種編碼策略:

(1) 字典編碼

利用數據類型的一致性,將相同的值提取出來生成符號表,每個列值則直接存儲該值映射成的符號表值id即可。

字典編碼的示例如下:

 

20160617105324185.jpg

 

(2) 常量編碼

當區內的數據大部分的數據相同,只有少數不同時,可以采用常量編碼。該編碼將區內數據出現最多的一個值作為常量值,其他值作為異常值。異常值使用<行號+值>的方式存儲。

20160617105314622.jpg

 

(3) RLE编码

 

当区内的数据存在大量的相同值,每个不同值的个数比较均匀,且连续出现时,可以使用RLE编码。

 

20160617105303190.jpg

 

(4) 序列编码

 

当区内的数据差值成等差数列,或者存在一定的代数关系,则可以使用序列编码。

 

20160617105252600.jpg

 

(5) 四種編碼使用策略

字典編碼、常量編碼和RLE編碼都是基於重復值較多的情況下使用的,如果不同值中,某個值出現多次,其他的值都只出現一次,則可以使用常量編碼;如果這些不同值都連續出現多次,且出現的次數相當,則使用RLE編碼;如果這些不同值出現的次數相當,但都不連續,則使用字典編碼。從上可知,這三種編碼方式都是基於不同值的分布特征來確定使用哪種編碼,也就是說,只會使用三種中的一種編碼方式,不會嵌套使用。

序列編碼基於前後兩個數據的差值大部分都相同的一種編碼方式,當差值計算出來之後,可以再分析其數據特征確定再使用前面三種編碼方式。

綜上所述,這四種編碼策略如下:

如果該列為自增列或序列,則直接使用序列編碼;

獲得區數據統計信息:不同值個數n_dist、每個不同值個數、不同值數據指針、每個值連續出現的次數、整型數的最大值;

根據獲得的區統計信息,確定使用常量編碼、RLE編碼還是字典編碼;這三種編碼的使用順序為:優先使用常量編碼,其次使用RLE編碼,最後才使用字典編碼。

如果編碼後的總長度超過了原始長度,則不編碼,直接返回;

除了采用編碼進行壓縮外還可以對區采用QUICKLZ或1-9級LZ算法進一步壓縮,兩者可以同時存在,也就是對編碼後的存儲結構進一步二進制壓縮。

通過以上壓縮算法,通常可以將數據壓縮幾倍,如果運氣好(數據有序、重復值很多等)壓縮率可達數百倍。目前CPU性能發展很快,而存儲性能提升有限,特別是大數據處理領域不大可能大規模使用SSD。解壓引起的性能損失遠遠小於磁盤IO等待的開銷。

Q&A

Q1:智能索引針對的數據類型和長度有限制嗎?

A1:“智能索引”不能用於大字段類型如BLOB,CLOB,其它達夢支持的基本數據類型都可以利用“智能索引”。

Q2:字典壓縮算法的字典有大小限制嗎?會根據列中數據量變化嗎?字典建立在列上還是區上呢?

A2:區是列的子集,如果數據庫采用字典編碼去壓縮一個區,則這個區維護一個字典,字典會根據數據量變化。比如這個區有1000個不同值,則字典就有1000個值。有1萬個不同值,則字典就有1萬個值。字典編碼有大小限制,如果系統判斷采用字典壓縮算法後,壓縮率達不到閥值會放棄采用該編碼壓縮。

Q3:首先,在HTS目錄下創建這個表對應的模式目錄。目錄名為“SCH+長度為9的ID號”組成的字符串。9位的ID號,是指表的tabid麽 ?

A3:SCH+9位ID,那個ID是模式的編碼號。

Q4:如果字段值為20000000000000000xxxxxxxx,這種數據類型,智能索引是否還會生效?

A4:會生效,只有數據很亂的時候才不生效。比如所有的區最大值最小值都很相近,比如都是1到10000000000,則無法利用智能索引。

Q5:數據字段中若有大量的空值,請問這種壓縮策略能不能有很好的壓縮率?如何實現?

A5:NULL在達夢數據庫裏也是一個特殊字符,在列存裏同其它數據處理。也是根據數據的實際情況選擇編碼方式壓縮。一般大量同一個字符,壓縮率一般都很好。

Q6:請問下收費規則如何?支持數據倉庫嗎?對經典的多對多關系怎麽拆分?

A6:數據庫的收費規則得咨詢銷售,不過肯定比Oracle便宜。數據倉庫可以基於我們構建,你說的多對多關系拆分可以線下討論。

Q7:和Oracle兼容性如何?

A7:達夢在DML類語句上,100%兼容Oracle語法。PL/SQL大部分都兼容。如果DML語句發現有不兼容的地方告訴我們,我們立馬改了。PL/SQL不兼容的看情況,對於常用的語法和Oracle是兼容的,很冷門的包如果沒有項目推動,一般不會主動去兼容。

Q8:達夢是基於開源數據庫改的麽?

A8:完全自主開發、自主原創,源代碼都是我們自己寫的。

延伸阅读

评论