SQL Server Column Store Indeses. 1

1. 概述... 1

2. 索引存儲... 2

2.1 列式索引存儲... 2

2.2 數據編碼和壓縮... 3

2.2.1 編碼... 3

2.2.2 優化行順序... 4

2.2.3 壓縮... 4

2.3 I/O和Cache. 4

3 查詢處理和優化... 4

3.1 查詢處理加強... 4

3.2 查詢優化

SQL Server 11增加了新特性列存儲索引和相關的查詢操作符。批量行處理來提高數據倉庫的查詢性能。

傳統的數據庫系統使用行存儲的，heap，btree都是。這種數據組織方式對于，只處理到一部分數據的事務處理表現很好，但是并不適應數據倉庫的，數據倉庫通常是對掃描很多記錄，但是只涉及到某一些行。這個時候列方式組織就能執行的很好。因為可以讀取需要的列，并且列存儲的數據可以得到很好的壓縮。

SQL Server列存儲索引是純粹的列存儲，不是混合的。不同的列被存放在不同的page下。

使用1TB測試數據庫(TPC-DS),catalog_sales包含1.44billion條數據，使用星型結構來測試列存儲索引的性能提升，只對事實表做列存儲索引，其他表都是行存儲。在40核啟用了超線程，256GB內存，磁盤性能在10GB/sec設備上測試。

SELECT w_city ,w_state ,d_year ,SUM(cs_sales_PRice) AS cs_sales_price

FROM Warehouse ,catalog_sales ,date_dim

WHERE w_warehouse_sk = cs_warehouse_skAND cs_sold_date_sk = d_date_skAND w_state = 'SD'AND d_year = 2002

GROUP BY w_city , w_state ,d_year

ORDER BY d_year , w_state , w_city;

比較容易看出性能，在improvement行中可以看出，CPU花費少了13倍，在cold情況下執行時間少了25倍。

在SQL Server 11之前所有的索引都是以行存儲的。不管是btree還是heap。

列存儲，以新的索引類型引入到SQL Server列存儲索引。設計的目的是為了加快列的掃描。

列存儲保存方式如下：

　　1. 把行轉化為column segment，先把行分為一個個的row groups，每個groups由1million數據。每個row group獨立的進行編碼和壓縮。生產一個壓縮的column segment，里面只包含一個列。

如圖表分為3個row group，獨立的進行編碼和壓縮，生成9個壓縮的column segments。

　　2. 然后使用現有的blob存儲機制來保存這些壓縮的column segments。Segment目錄用來跟蹤每個segment的位置，這樣每個segment可以很容易的被定位。這個segment目錄被保存在系統表可以使用sys.column_store_segments來查看，視圖里面也保存了一些元數據。

數據存儲是使用壓縮的方式來減少存儲空間和I/O消耗。可以選擇允許column segment直接使用不需要解壓縮。壓縮步驟如下：

1.對所有的column的值進行編碼。

2.優化行的順序。

3.對每個行進行壓縮。

編碼就是把列值轉化為唯一的類型：32bit或者64bit。支持2個類型的encode：基于字典的編碼和基于值的編碼。

基于字典的編碼把不同的值轉為連續的int值的集合。存入數據目錄，本質上是存入以dataids為索引的一個數組中。每個數據字典保存在獨立的blob中，可以使用sys.column_store_dictionaries查看。

基于值的編碼應用在int或者decimal數據類型上。把某個范圍的值弄小。基于值的編碼由2部分組成：基值和指數。

一旦指數被選中，column segment上的值就會被調整。

重要的性能提升主要是來自于壓縮，數據使用RLE壓縮(run-length encoding)。RLE在許多一樣的數據在一起的時候壓縮表現會很好。因為在row groups中順序是不重要的，所以可以隨意的重新組織順序來提高壓縮效率。

我們使用vertipaq算法來重新重新組織row group中的順序，提高RLE的壓縮性能。

一旦row group中的行被重新排序，就可以使用RLE來壓縮。

Blob存儲的column segment或者字典可能跨多個page，當我們讀入內存的時候column segment和字典被保存在新的cache中用來保存大對象，而不是基于page 的buffer pool中。而且每個對象都是連續的，沒有空隙。

為了提高I/O性能，預讀可以被應用在segment內和多個segment上。對于磁盤存儲，可以使用額外的壓縮，是否使用額外的壓縮，需要在I/O和cpu之間平衡。

標準的查詢處理是基于行的，一次處理一行，為了減少cpu，使用了新的處理方式，以批處理的方式一次性處理一批行。批處理方式適用于OLAP但是不會取代行處理在OLTP中的地位。

SQL Server沒有去創建一個新的引擎，而是在原來的引擎上面做擴展。有以下好處：

1.用戶不需要花時間在新的引擎上，和不需要再2個引擎上做轉化。

2.極大的減少了實現引擎的花費

3.查詢計劃可以混合兩個操作。

4.查詢可以自動的在batch和row操作間轉化。

5.所有的特性相容。

新的batch有獨立的訪問方法有不同的數據源支持，列存儲索引的訪問方法支持謂詞和bitmap過濾。Batch模式一般適用于數據密集的計算，計算復制的過濾條件，select列表，join和聚合。

新的訪問方法有新的優化，如：延遲字符串實例化和透明使用新的迭代器。雖然批處理方式可以減少cpu處理時間，但是達不到目標。

有一些額外的優化方式：

1.新的迭代器針對最新的cpu進行優化，增加內存的吞吐量。

2.bitmap過濾的實現。

3.runtime資源管理被提升，可以讓操作以更靈活的方式共享。

和其他索引不同，列存儲索引不能很好的支持point query和range scan，因為列存儲索引沒有順序，沒有統計信息。列存儲索引值提供高壓縮的數據來減少cpu和io，對于scan可以從列存儲索引上提升性能。

是否使用batch處理方式由查詢分析器決定，也可以混合row和batch處理，但是2者之間的轉化是有花費的，因此mssql會限制轉化次數。

為了在生成的圖形計劃中區分batch和row，加入了一個新的屬性，用這個屬性來區分是batch還是row。，也可以決定是否有必要做轉化。所有的batch操作要求輸入都是batch，row操作輸入都是row。

除了batch處理方法，也引入的新的方法來控制多個join。Sql server優化器視圖把inner join轉化為一個多維join操作。好處是可以一次性處理整個join graph。

1.我們先通過join的表達式和謂詞來識別那個join key 是唯一的。使用識別的唯一信息來判斷哪些是事實表，哪些是維度表，事實表不會有唯一信息。

2.然后從最小的事實表開始展開join graph，盡量多的覆蓋維度表，在事實表周圍形成一個雪花型。然后處理另外一個試試表。

3.之后，我們會有多個雪花型join，然后從最大的事實表開始，遞歸的把周圍的雪花以維度表方式加入，開始形成最終的執行計劃。首先，識別哪些join值得創建bitmap過濾，一旦識別就創建一個right deep join樹，把維度表放在左邊，事實表放在右邊。每個維度表可能都是一個雪花型，然后以遞歸的方式分解每一個雪花。在每個join上，確定條件，檢查是否可以使用batch，如果不行則用row模式。若到達了，所有吧可以batch的放在下面，其他的放在上面。

參考：

SQL Server Column Store Indexes