本次分享内容由三個部分組成：
列存儲資料組織實作
智能索引的實作
自适應壓縮算法
目前資料庫主流資料組織技術分為資料按行存儲和資料按列存儲，達夢資料庫表資料的存儲方式同時支援行存儲和列存儲。行存儲是以記錄為機關進行存儲的，資料頁面中存儲的是完整的若幹條記錄；列存儲是以列為機關進行存儲的，每一個列的所有行資料都存儲在一起，一個段隻存儲一個列的資料，而且一個指定的頁面中存儲的都是某一個列的連續資料。
列存表的存儲方式有以下幾個優點：
同一個列的資料都是連續存儲的，可以加快某一個列的資料查詢速度（相對行存減小不必要io）；
連續存儲的列資料，具有更大的壓縮單元和資料相似性，可以獲得遠優于行存儲的壓縮效率；
條件掃描借助資料區的統計資訊進行精确過濾，可以進一步減少io，提高掃描效率（智能索引）。
下面我們主要介紹達夢資料庫的列存儲的技術特點及具體實作，并詳細介紹列存儲的資料組織方式、智能索引的實作、自适應壓縮算法設計。
1 列存儲資料組織實作
達夢的列存儲表又叫huge表，是建立在hts表空間上的（全稱huge tablespace）。這個表空間與普通的表空間不同。普通的表空間，資料是通過段、簇、頁來管理的，并且以固定大小（4k、8k、16k、32k）的頁面為管理機關；而hts相當于一個簡單的檔案系統，建立一個hts，其實就是建立一個空的目錄。在建立一個hfs表之後，資料庫會在指定的hts表空間目錄下建立一系列的目錄及檔案，檔案系統結構如下圖所示：
從上圖可以看出，在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索引，是以被一些廠商稱為“智能索引”。
下圖為區最大值、最小值資訊起到過濾作用的示意圖：
除了最大值、最小值起到跳區掃描減少io的作用，區和值、區内有效行數等其它資訊在一些統計分析場景甚至可以完全避免資料區的掃描。如max()，count()，avg()等一些函數可以直接通過查詢輔助表獲得。
3 自适應壓縮算法
連續存儲的列資料，具有更大的壓縮單元和資料相似性，可以獲得遠優于行存儲的壓縮效率。根據列存儲的特性，達夢提供一套自适應的壓縮算法，可以根據資料特性以區為機關自動選擇相應的算法最大化壓縮率和性能。
下面詳細介紹4種編碼政策：
(1) 字典編碼
利用資料類型的一緻性，将相同的值提取出來生成符号表，每個列值則直接存儲該值映射成的符号表值id即可。
字典編碼的示例如下：
(2) 常量編碼
當區内的資料大部分的資料相同，隻有少數不同時，可以采用常量編碼。該編碼将區内資料出現最多的一個值作為常量值，其他值作為異常值。異常值使用<行号+值>的方式存儲。
(3) rle編碼
當區内的資料存在大量的相同值，每個不同值的個數比較均勻，且連續出現時，可以使用rle編碼。
(4) 序列編碼
當區内的資料內插補點成等差數列，或者存在一定的代數關系，則可以使用序列編碼。
(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：完全自主開發、自主原創，源代碼都是我們自己寫的。
作者介紹 李鵬
現任職于達夢資料庫，從事資料庫測試和技術職稱工作；
擅長資料庫性能瓶頸分析定位及調優，主要負責資料庫産品性能測試及重點項目競争性測試；
曾參與國電電網、南方電網、國家工商總局等項目的poc測試，積累了豐富的資料庫測試經驗。
<b></b>
<b>本文來自雲栖社群合作夥伴"dbaplus"，原文釋出時間：2016-06-17</b>