文章出處

解剖SQLSERVER 第十四篇 Vardecimals 存儲格式揭秘（譯）

http://improve.dk/how-are-vardecimals-stored/

在這篇文章，我將深入研究vardecimals 是怎麼存儲在磁盤上的。

作為一般的介紹vardecimals 是怎樣的，什么時候應該使用，怎樣使用，參考這篇文章

vardecimal 存儲格式啟用了嗎?

首先，我們需要看一下vardecimals 是否已經開啟了，因為他會完全改變decimals 的存儲方式。Vardecimal 不是獨立的一種數據類型，所有使用decimals 的列都會使用vardecimals方式來存儲并使用相同的system type（106）。注意在SQLSERVER里面，numeric 跟decimal是完全一樣的。無論我在哪里我提到decimal, 你都可以使用numeric來替代并且會得到相同的結果

你可以執行下面語句來查看給定的表的vardecimal 是否開啟

SELECT OBJECTPROPERTY(OBJECT_ID('MyTable'), 'TableHasVarDecimalStorageFormat')

如果你沒有權限運行上面語句，或者不想使用OBJECTPROPERTY函數，你可以查詢sys.system_internals_partition_columns DMV 獲取同樣的信息。

USE test
GO

SELECT
    COUNT(*)
FROM
    sys.system_internals_partition_columns PC
INNER JOIN
    sys.partitions P ON P.partition_id = pc.partition_id
INNER JOIN
    sys.tables T ON T.object_id = P.object_id
WHERE
    T.name = 'test_vardecimal' AND
    P.index_id <= 1 AND
    PC.system_type_id = 106 AND
    PC.leaf_offset < 0

固定長度變為可變長度
正常的decimal列在記錄里面使用固定長度來存儲。這意味著存儲的是真正的數據。他不需要保存存儲的字節數的長度信息這個長度信息用來計算并存儲在元數據里。

一旦你打開vardecimals, 所有的decimals 不再使用固定長度來存儲，進而用可變長度代替。

將decimal 作為可變長度字段來存儲有一些特別含義
1、我們再也不能使用靜態的方法來計算一個給定的值的所需字節數
2、會有兩個字節的開銷用來存儲偏移值在可變長度偏移數組里
3、如果先前行記錄沒有可變長度列，那么開銷實際上是4個字節因為我們也需要存儲可變長度列的列數量
4、decimal 的實際值變成了可變數量的字節這需要我們去解讀

vardecimal 值由哪些部分組成
一旦我們開始解析行記錄然后在可變長度部分檢索vardecimal 的值，我們需要解析里面的數據。

正常的decimals 基本能存儲一個巨大無比的整數（范圍是根據元數據定義的decimal的位置）
vardecimals 的存儲使用科學計數法。使用科學計數法，我們需要存儲三個不同的值
1、符號（正數/負數）
2、指數
3、（對數的) 尾數

使用這三個組成部分，我們可以使用下面的公式計算出實際值

(sign) * mantissa * 10<sup>exponent</sup>

例子

假設我們有一個vardecimal(5,2)列，我們存儲的值是123.45。在科學記數法里，將表示為1.2345 * 10²。
在這種情況下我們有正數符號（1），一個尾數1.2345和一個指數2。SQL Server知道尾數總是有一個固定小數點在第一個數字后面，正因為如此，這會簡單的存儲整數值12345作為尾數，

當指數是2，SQLSERVER知道我們的范圍由指數2來定義，數值向右移動指數的長度，存儲0作為實際的指數

一旦我們讀取這個數，我使用下面的公式計算尾數（注意我們在這里不關心如果尾數是正的還是負的--我們會稍后將他保存到account里）

mantissa / 10<sup>floor(log10(mantissa))</sup>

將我們的值帶入進去，我們得到

12345 / 10<sup>floor(log10(12345))</sup>

通過簡化我們得到

12345 / 10<sup>4</sup>

使用科學計數法得到最終的尾數

1.2345

到目前為止一切順利，我們現在得到尾數的值。在這里我們需要做兩件事
1、加上符號位
2、根據指數值將decimal的小數點移動到右邊正確的位置。當SQLSERVER知道范圍是2，他將2替代4，并減去指數指定的范圍--允許我們忽略范圍并且只需要直接計算數字

因此我們獲得了我們最終需要計算的最后數字

(sign) * mantissa * 10<sup>exponent</sup> => (1) * 1.2345 * 10<sup>2</sup> => 1.2345 * 10<sup>2</sup> = 123.45

讀取符號位和指數
第一個字節包含符號和指數。在先前的例子里面，這些值占用4個字節（包含額外的2個字節的偏移數組）

0xC21EDC20

如果我們觀察第一個字節，并且將他轉換為binary，我們獲得下面信息

最重要的那個位是最左邊的那個位，或者從右開始數第7位（位置編號從0開始）那個位是符號位。如果設置為1表示正數，如果為0表示負數，我們看到是1表示正數

位0 - 6是一個7位的包含指數的值。一個常規的無符號7位值可以包含的范圍是0~127。當decimal 數據類型需要表示一個范圍 –1038+1到 1038-1，我們就需要存儲負數。

我們可以使用7位的其中一位作為符號位，在其余的6位里存儲值，允許的范圍是–64 到 63。然而SQLSERVER會用盡7位去存儲本身的數值，

不過存儲的是一個偏移值64。因此，指數0會被存儲為64 （64-64=0）。指數-1 會存儲63 （63-64=-1），指數1會存儲65 （65-64=1）如此類推。

在我們的例子里，讀取位0-6 將會得到下面的值

66減去64這個偏移值就得出指數2
66-64=2（指數）

尾數的chunk存儲
余下的字節包含尾數值。我們把他轉換為二進制

Hex: 1E       DC       20

Bin: 00011110 11011100 00100000

尾數存儲在10位的chunks里，每一個chunk顯式尾數的3個數字（記住，尾數是一個很大的整數，直到后來我們開始把他作為一個十進制的指針數值 10的n次冪）

把這些字節切割放進去chunks里面會得到如下的組別

在這種情況下,一個字節8位 SQLSERVER在這里會浪費4位使用這種chunk大小的話。問題來了，為什么要選擇一個chunk大小為10位？那10位需要顯示所有可能的三位整數（0-999）。

如果我們使用一個chunk的大小來表示一個數字會怎樣？

在這種情況下,一個字節8位 SQLSERVER在這里會浪費4位使用這種chunk大小的話。問題來了，為什么要選擇一個chunk大小為10位？那10位需要顯示所有可能的三位整數（0-999）。如果我們使用一個chunk的大小來表示一個數字會怎樣？

剛才那樣的情況，我們需要展示數值0-9.那總共需要4個位(0b1001 = 9)。然而，使用4個位的時候我們實際可以展示的最大范圍是0-15(0b1111 = 15) --意味著我們浪費了6個值的空間（15-9=6）這些值永遠不需要的。從百分比來講，我們浪費了6/16=37.5%

讓我們試著畫出不同的chunk大小對應浪費的百分比的圖：

我們看到chunk大小選擇4和選擇7 相比起選擇chunk大小為10 有較大的浪費。
在chunk大小為20時，對于0浪費相當接近，但是他還是有2倍浪費率相比起10來說

現在，浪費不是最重要的。對于壓縮來說，最理想的情況是對于絕對必要的數字我們不想使用多余的數字。在chunk大小為10的情況下，可以顯示3個數字，我們浪費了2個數字空間范圍是0-9。

然而，我們只關注范圍100-999。如果我們的chunk大小選擇20個位，每個chunk顯示6個數字，我們浪費了了一些字節值從0-99999，當我們只關注值1000000-999999。

基本上，這是一個折衷方案，浪費就越少而且也越好。我們繼續看圖表，粒度越來越少。很明顯選擇10個位作為chunk的大小是最好的選擇 --這個選擇的浪費是最小的并且有合適的粒度大小 3個數字

在我們繼續之前還有一些細節。想象一下我們需要存儲的尾數值為4.12，有效的整數值是412

Dec: 412
Bin: 01100111 00
Hex: 67       0

在這種情況下,我們會浪費8位在第二個字節,因為我們只需要一個塊,但我們需要兩個字節來表示這10位。在這種情況下,鑒于過去兩位不設置,SQL Server會截斷最后一個字節。因此,如果你正在讀一塊,你的磁盤上,你可以假設其余部分不設置。

在這種情況下,我在第二個字節浪費8個位，因為我們只需要一個chunk，不過我們需要兩個字節來顯示這個位。在這種情況下，多余的兩個位不會進行設置，SQLSERVER會簡單的截斷最后一個字節。因此，如果你讀取一個chunk并且位數已經超出了磁盤的范圍，你可以假設剩余的位并沒有設置

解析一個vardecimal值
最后，我們準備去解析一個vardecimal 值（使用C#實現）！我們將使用先前的例子，存儲123.45值使用decimal(5,2)列。在磁盤上，我們讀取下面的字節數組根據調用的順序

Hex: C2       1E       DC       20
Bin: 11000010 00011110 11011100 00100000

讀取符號位
讀取符號位相對來說比較簡單。我們將只需要在第一個字節上讀取：

通過位運算符我們將右移7位，剩下的位是最重要的位。這意味著我們將得到值1 表示正數的符號位，如果是0表示負數

decimal sign = (value[0] >> 7) == 1 ? 1 : -1;

讀取指數
下面（技術上來講這7個位是緊跟著符號位的）的7位包含了指數值

將十六進制值0b1000010 轉換為進制值得到的結果是66.我們知道指數總是有偏移值64，我們需要將存儲的值減去64從而得到實際值：

Exponent = 0b1000010 – 0n64 <=> Exponent = 66 – 64 = 2

讀取尾數
接下來就是尾數值。前面提到，我們需要讀取一個10個位的chunk，并且需要注意那些被截斷的部分

首先，我們需要知道有多少有用的位。這樣做很簡單,我們只需簡單的將尾數的字節數（除了第一個字節之外的所有字節）乘以8

int totalBits = (value.Length - 1) * 8;

一旦我們知道有多少位是可用的（在這個例子里 2個chunk 24位=3個字節* 8位），我們可以計算chunks的數目

int mantissaChunks = (int)Math.Ceiling(totalBits / 10d);

因為每個塊占用10位,我們只需要的比特總數除以10。如果有填充最后,匹配一個字節邊界,它將是0的,不會改變最終的結果。因此為2字節尾數我們將有8位備用,將非標準都是0。

對于一個3字節尾數我們將有4位,再次添加0尾數總額。

因為每個chunk占用10個位，我們只需要除以將位的總數除以10。如果在結尾有占位，為了匹配位的邊界，SQLSERVER會填充0但是這個不會影響上面公式得出的結果。

因此，對于一個2個字節的尾數我們會有8bit（這里作者是不是錯了？應該是6bit吧）是剩余的，這些剩余位都會被無意義的0填充。對于一個3字節的尾數我們會有4bit 剩余，

再一次在總的尾數值上填充0

這里我們準備讀取chunk的值。在讀取之前，我們需要分配兩個變量

decimal mantissa = 0;
int bitPointer = 8;

可變長的尾數值是由尾數值進行累加的，每次我們讀取一個新10-bit chunk值就累加一次。bitPointer 是一個指針指向當前讀取到的位。
我們不準備讀取第一個字節，我們會從第8位開始讀取（從0開始數，因此第8位 =第二個字節的第一位）

看一下這些位他們可以簡單的看成是一條long stream --我們只需要從左到右進行讀取，對吧？不完全是，你可否記得，最右邊的位是最重要的，
因此最右邊的位應該是我們最先要讀取的。然而，我們需要一次讀取一個字節。同樣，整體的方向是按chunk為單位的話是從左到右讀取。

一旦我們達到chunk的位置，我們每次就需要一個字節一個字節地讀取。bits1-8 在第一個字節里讀取，bits9-10 在第二個字節里讀取，

下面圖片中橙色的箭頭（最大的那個箭頭指示字節讀取順序（chunkwise）從左向右，而每個獨立的字節內部的讀取順序是小箭頭那個從右向左）

為了方便訪問所有的bits，和避免做太多的人工的位移操作，我實例化一個BitArray 類，這個類包含了所有的數據位：

var mantissaBits = new BitArray(value);

使用這個類，你必須知道bit 數組如何跟字節進行映射。形象的描述，他會像下面那樣，mantissaBits 數組指針在圖片的上面：

我知道這看起來很復雜，不過所有這些復雜的事情只不過是需要知道指針的指向。我們的代碼里面是字節數組。
我們訪問每一個獨立的bits的方式是通過mantissaBits 數組，這個數組只是一個很大的指向獨立的bits的數組指針。

看一下第一個8 bits，manitssaBits 數組按照我們的讀取方向很好地排列。第一個條目（mantissaBits[0]）指向
第一個字節的最右一位。第二個條目指向第二個字節，以此類推。因此，第一個8 bits是直接讀取的。然而，后面的兩個，在manitssaBits 數組里面他們需要
我們跳過6個條目以至于我們讀取條目14和15，他們指向下一個字節的最后兩個bits（因為是從右向左讀取的）。

讀取第二個chunk，我們必須回去讀取bit 條目8-13 然后跳到條目20-23，忽略條目16-19 因為他們只是不相關的占位padding。
這是相當棘手的。幸運的是我們可以自由選擇從重要的位到不重要的位進行讀取，或者相反

讓我們看一下代碼實現

for (int chunk = mantissaChunks; chunk > 0; chunk--)
{
    // The cumulative value for this 10-bit chunk
    decimal chunkValue = 0;

    // For each bit in the chunk, shift it into position, provided it's set
    for (int chunkBit = 9; chunkBit >= 0; chunkBit--)
    {
        // Since we're looping bytes left-to-right, but read bits right-to-left, we need
        // to transform the bit pointer into a relative index within the current byte.
        int byteAwareBitPointer = bitPointer + 7 - bitPointer % 8 - (7 - (7 - bitPointer % 8));

        // If the bit is set and it's available (SQL Server will truncate 0's), shift it into position
        if (mantissaBits.Length > bitPointer && mantissaBits[byteAwareBitPointer])
            chunkValue += (1 << chunkBit);

        bitPointer++;
    }

    // Once all bits are in position, we need to raise the significance according to the chunk
    // position. First chunk is most significant, last is the least significant. Each chunk
    // defining three digits.
    mantissa += chunkValue * (decimal)Math.Pow(10, (chunk - 1) * 3);
}

外層循環遍歷chunks，從最重要的到不重要的chunk。這里我們先遍歷chunk2再遍歷 chunk1

chunkValue 這個變量保存我們當前正在讀取的chunk的所有值。我們會進行移位操作把位的值賦值給chunkValue （chunkValue += (1 << chunkBit);）
直到已經解析完所有的10個bits

內層循環從最重要的bit到不重要的bit（就是說，在chunkbit里從條目9到條目0）。最右邊的位開始倒序讀取，我們避免跳過內部的單個字節。
我們在mantissaBits數組中總是從右到左讀取bits，下面頂層的箭頭就像這樣：

雖然我們倒序讀取每個字節里面的bit，其他的東西都是以自然方式讀取，這讓解析更加容易

byteAwareBitPointer 變量在我們的 mantissaBits數組里面是一個指針指示我們當前讀取到的值。

這種計算確保我們讀取每一個字節的時候都是從mantissaBits數組里最高位讀取到最低位。下面是讀取到的第一個chunk里面按mantissaBit 指針順序的條目值

7, 6, 5, 4, 3, 2, 1, 0, 15, 14

和第二個被讀取到的chunk 按mantissaBit 指針順序的條目值

13, 12, 11, 10, 9, 8, 23, 22, 21, 20

一旦我們讀取到特定的bit，我們進行移位把值保存到chunkValue 變量里--但只有這個位是可用的才會保存到chunkValue 變量（也就是說0不會保存并被截斷）

一旦所有的bits都已經進行了移位，我們把chunk的值賦值給mantissa 。在我們的例子里，存儲的值是12345，我們實際上
存儲的值是123450（因為每一個chunk存儲三個數字，這總是3的倍數）。第一個讀取到的chunk（chunk2）包含值123 對應值是123000。
第二個讀取到的chunk（chunk1）包含的值是450。乘以10^{(chunk–1)<3}

確保我們獲取到正確的數量級（1000 for chunk 2 and x1 for chunk 1*）。對于每次的chunk循環，我們會添加最后的chunk值到尾數（mantissa ）里最后進行相加

mantissa = mantissa / 10<sup>floor(log10(mantissa))</sup>

實現代碼如下：

mantissa = mantissa / (decimal)Math.Pow(10, Math.Floor(Math.Log10((double)mantissa)));

尾數的結果值是1.2345

尾數的解析性能
這個實現的性能談不上快，在你打擊我之前有些說話我需要說。首先，我們可以容易地將整組bits一次性進行移位而不是每次移位。
確保每個chunk不需要兩次或以上的移位操作，在這個實現里面使用了10次移位操作（因為每個chunk是10個bits）。
然而，我的目的是這個代碼實現是為了代碼的清晰和可讀性。我的目的不是為了對OrcaMDF進行速度的優化

將這些東西全部結合起來
一旦我們有了符號位，指數，尾數，我們可以簡單的計算最后的值就像這樣：

return sign * mantissa * (decimal)Math.Pow(10, exponent);

在我們的例子里，結果將是這樣：

1 * 1.2345 * 10<sup>2</sup> = 1.2345 * 100 = 123.45

結論

Vardecimal 是SQL2005 SP2唯一的壓縮功能。到了SQL2008我們才有行壓縮和頁壓縮功能（這兩個特性是vardecimal存儲格式的超集）。
從那時起，隨著行壓縮和頁壓縮的發布，微軟已經把vardecimal 作為廢棄功能，并且在將來的版本會刪除這個功能。
因為Vardecimal 需要企業版才能使用，而行壓縮和頁壓縮也是需要企業版，我們沒有理由去使用Vardecimal 功能，除非你使用的是SQL2005
或者除非你有一個非常特別的數據集除了使用decimals壓縮功能沒有其他的功能能帶來性能提升。

知道vardecimal 的存儲格式是如何工作的對于研究壓縮的內部是有好處的--壓縮內部我將會寫一篇文章并且我將會在2012年春季的SQL Server Connections里進行演示

同時你可以github上在簽出我的SqlDecimal.cs 實現。或者你可以看一下OrcaMDF 代碼里的完整實現

using System;
using System.Collections;
namespace OrcaMDF.Core.Engine.SqlTypes
{
public class SqlDecimal : ISqlType
{
private readonly byte precision;
private readonly byte scale;
private readonly bool isVariableLength;
public SqlDecimal(byte precision, byte scale)
: this(precision, scale, false)
{ }
public SqlDecimal(byte precision, byte scale, bool isVariableLength)
{
this.precision = precision;
this.scale = scale;
this.isVariableLength = isVariableLength;
}
public bool IsVariableLength
{
get { return isVariableLength; }
}
public short? FixedLength
{
get { return Convert.ToInt16(1 + getNumberOfRequiredStorageInts() * 4); }
}
private byte getNumberOfRequiredStorageInts()
{
if (precision <= 9)
return 1;
if (precision <= 19)
return 2;
if (precision <= 28)
return 3;
return 4;
}
public object GetValue(byte[] value)
{
if(!isVariableLength)
{
if (value.Length != FixedLength.Value)
throw new ArgumentException("Invalid value length: " + value.Length);
int[] ints = new int[4];
for (int i = 0; i < getNumberOfRequiredStorageInts(); i++)
ints[i] = BitConverter.ToInt32(value, 1 + i * 4);
var sqlDecimal = new System.Data.SqlTypes.SqlDecimal(precision, scale, Convert.ToBoolean(value[0]), ints);
// This will fail for any SQL Server decimal values exceeding the max value of a C# decimal.
// Might want to return raw bytes at some point, though it's ugly.
return sqlDecimal.Value;
}
else
{
// Zero values are simply stored as a 0-length variable length field
if (value.Length == 0)
return 0m;
// Sign is stored in the first bit of the first byte
decimal sign = (value[0] >> 7) == 1 ? 1 : -1;
// Exponent is stored in the remaining 7 bytes of the first byte. As it's biased by 64 (ensuring we won't
// have to deal with negative numbers) we need to subtract the bias to get the real exponent value.
byte exponent = (byte)((value[0] & 127) - 64);
// Mantissa is stored in the remaining bytes, in chunks of 10 bits
int totalBits = (value.Length - 1) * 8;
int mantissaChunks = Math.Max(totalBits / 10, 1);
var mantissaBits = new BitArray(value);
// Loop each chunk, adding the value to the total mantissa value
decimal mantissa = 0;
int bitPointer = 8;
for (int chunk = mantissaChunks; chunk > 0; chunk--)
{
// The cumulative value for this 10-bit chunk
decimal chunkValue = 0;
// For each bit in the chunk, shift it into position, provided it's set
for (int chunkBit = 9; chunkBit >= 0; chunkBit--)
{
// Since we're looping bytes left-to-right, but read bits right-to-left, we need
// to transform the bit pointer into a relative index within the current byte.
int byteAwareBitPointer = bitPointer + 7 - bitPointer % 8 - (7 - (7 - bitPointer % 8));
// If the bit is set and it's available (SQL Server will truncate 0's), shift it into position
if (mantissaBits.Length > bitPointer && mantissaBits[byteAwareBitPointer])
chunkValue += (1 << chunkBit);
bitPointer++;
}
// Once all bits are in position, we need to raise the significance according to the chunk
// position. First chunk is most significant, last is the least significant. Each chunk
// defining three digits.
mantissa += chunkValue * (decimal)Math.Pow(10, (chunk - 1) * 3);
}
// Mantissa has hardcoded decimal place after first digit
mantissa = mantissa / (decimal)Math.Pow(10, Math.Floor(Math.Log10((double)mantissa)));
// Apply sign and multiply by the exponent
return sign * mantissa * (decimal)Math.Pow(10, exponent);
}
}
}
}