深入講解資料庫中Decimal型別的使用以及實現方法

2022-02-15 13:02:54

1 背景

數位運算在資料庫中是很常見的需求, 例如計算數量、重量、價格等, 為了滿足各種需求, 資料庫系統通常支援精準的數位型別和近似的數位型別. 精準的數位型別包含 int, decimal 等, 這些型別在計算過程中小數點位置是固定的, 其結果和行為比較可預測. 當涉及錢時, 這個問題尤其重要, 因此部分資料庫實現了專門的 money 型別. 近似的數位型別包含 float, double 等, 這些數位的精度是浮動的.

本文將簡要介紹 decimal 型別的資料結構和計算, 對比 decimal 在 MySQL, ClickHouse 兩個不同型別系統中的實現差異, 描述實現 decimal 運算的主要思路. MySQL 在結果的長度比較接近上限的情況下, 會有比較違反直覺的地方, 本文會在最後列出這些可能需要注意的問題.

2 Decimal型別的使用

decimal 的使用在多數資料庫上都差不多, 下面以 MySQL 的 decimal 為例, 介紹 decimal 的基本使用方法.

2.1 描述Decimal

與 float 和 double 不同, decimal 在建立時需要指定兩個描述精度的數位, 分別是 precision 和 scale, precision 指整個 decimal 包括整數和小數部分一共有多少個數位, scale 指 decimal 的小數部分包含多少個數位, 例如：123.45 就是一個 precision=5, scale=2 的 decimal. 我們可以在建表時按照這種方式定義我們想要的 decimal.

2.2 建表時定義Decimal

可以在建表時這樣定義一個 decimal:

create table t(d decimal(5, 2));

2.3 寫入decimal資料

可以向其中插入合法的資料, 例如

insert into t values(123.45);
insert into t values(123.4);

此時執行 select * from t 會得到

+--------+
| d      |
+--------+
| 123.45 |
| 123.40 |
+--------+

注意到 123.4 變成了 123.40, 這就是精確型別的特點, d 列的每行資料都要求 scale=2, 即小數點後有兩位

當插入不滿足 precision 和 scale 定義的資料時

insert into t values(1123.45);
ERROR 1264 (22003): Out of range value for column 'd' at row 1
insert into t values(123.456);
Query OK, 1 row affected, 1 warning
show warnings;
+-------+------+----------------------------------------+
| Level | Code | Message                                |
+-------+------+----------------------------------------+
| Note  | 1265 | Data truncated for column 'd' at row 1 |
+-------+------+----------------------------------------+
select * from t;
+--------+
| d      |
+--------+
| 123.46 |
+--------+

類似 1234.5 (precision=5, scale=1)這樣的數位看起來滿足要求, 但實際上需要滿足 scale=2 的要求, 因此會變成 1234.50(precision=6, scale=2) 也不滿足要求.

2.4 取出deimcal進行計算

計算的結果不受定義的限制, 而是受到內部實現格式的影響, 對於 MySQL 結果最大可以到 precision=81, scale=30, 但是由於 MySQL decimal 的記憶體格式和計算函數實現問題, 這個大小不是在所有情況都能達到, 將在後文中詳細介紹. 繼續上面的例子中：

select d + 9999.999 from t;
+--------------+
| d + 9999.999 |
+--------------+
|    10123.459 |
+--------------+

結果突破了 precision=5, scale=2 的限制, 這裡涉及運算時 scale 的變化, 基本規則是：

加法/減法/sum：取兩邊最大的 scale
乘法：兩邊的 scale 相加
除法：被除數的 scale + div_precision_increment(取決於資料庫實現)

3 Decimal型別的實現

在這一部分中, 我們主要介紹 MySQL 的 decimal 實現, 此外也會對比 ClickHouse, 看看 decimal 在不同系統中的設計與實現差異.

實現 decimal 需要思考以下問題

支援多大的 precision 和 scale
在哪裡儲存 scale
在連續乘法或除法時, scale 不斷增長, 整數部分也不斷擴大, 而儲存的 buffer 大小總是有上限的, 此時應該如何處理？
除法可能產生無限小數, 如何決定除法結果的 scale?
decimal 的表示範圍和計算效能是否有衝突, 是否可以兼顧

3.1 MySQL

先來看看 MySQL decimal 相關的資料結構

typedef int32 decimal_digit_t;

struct decimal_t {
  int intg, frac, len;
  bool sign;
  decimal_digit_t *buf;
};

MySQL 的 decimal 使用一個長度為 len 的 decimal_digit_t (int32) 的陣列 buf 來儲存 decimal 的數位, 每個 decimal_digit_t 最多儲存 9 個數位, 用 intg 表示整數部分的數位個數, frac 表示小數部分的數位個數, sign 表示符號. 小數部分和整數部分需要分開儲存, 不能混合在一個 decimal_digit_t 中, 兩部分都向小數點對齊, 這是因為整數和小數通常需要分開計算, 所以這樣的格式可以更容易地將不同 decimal_t 小數和整數分別對齊, 便於加減法運算. len 在 MySQL 實現中恆為 9, 它表示儲存的上限, 而 buf 實際有效的部分, 則是由 intg 和 frac 共同決定. 例如：

// 123.45 decimal(5, 2) 整數部分為 3,  小數部分為 2
decimal_t dec_123_45 = {
  int intg = 3;
  int frac = 2;
  int len = 9;
  bool sign = false;
  decimal_digit_t *buf = {123, 450000000, ...};
};

MySQL 需要使用兩個 decimal_digit_t (int32) 來儲存 123.45, 其中第一個為 123, 結合 intg=3, 它就表示整數部分為 123, 第二個數位為 450000000 (共 9 個數位), 由於 frac=2, 它表示小數部分為 .45

再來看一個大一點的例子：

// decimal(81, 18) 63 個整數數位, 18 個小數數位, 用滿整個 buffer
// 123456789012345678901234567890123456789012345678901234567890123.012345678901234567
decimal_t dec_81_digit = {
  int intg = 63;
  int frac = 18;
  int len = 9;
  bool sign = false;
  buf = {123456789, 12345678, 901234567, 890123456, 789012345, 678901234, 567890123, 12345678, 901234567}
};

這個例子用滿了 81 個數位, 但是也有些場景無法用滿 81 個數位, 這是因為整數和小數部分是分開儲存的, 所以一個 decimal_digit_t (int32) 可能只儲存了一個有效的小數數位, 但是其餘的部分沒有辦法給整數部分使用, 例如一個 decimal 整數部分有 62 個數位, 小數部分有 19 個數位(precision=81, scale=19), 那麼小數部分需要使用 3 個 decimal_digit_t (int32), 整數部分還有 54 個數位的餘量, 無法存下 62 個數位. 這種情況下, MySQL 會優先滿足整數部分的需求, 自動截斷小數點後的部分, 將它變成 decimal(80, 18)

接下來看看 MySQL 如何在這個資料結構上進行運算. MySQL 通過一系列 decimal_digit_t(int32) 來表示一個較大的 decimal, 其計算也是對這個陣列中的各個 decimal_digit_t 分別進行, 如同我們在小學數學計算時是一個數位一個數位地計算, MySQL 會把每個 decimal_digit_t 當作一個數位來進行計算、進位. 由於程式碼較長, 這裡不再對具體的程式碼進行完整的分析, 僅對程式碼中核心部分進行分析, 如果感興趣, 可以直接參考 MySQL 原始碼 strings/decimal.h 和 strings/decimal.cc 中的 decimal_add, decimal_mul, decimal_div 等程式碼.

準備步驟

在真正計算前, 還需要做一些準備工作：

MySQL 會將數位的個數 ROUND_UP 到 9 的整數倍, 這樣後面就可以按照 decimal_digit_t 為單位來進行計算
此外還要針對參與運算的兩個 decimal 的具體情況, 計算結果的 precision 和 scale, 如果發現結果的 precision 超過了支援的上限, 那麼會按照 decimal_digit_t 為單位減少小數的數位.
在乘法過程中, 如果發生了 2 中的減少行為, 則需要 TRUNCATE 兩個運算數, 避免中間結果超出範圍.

加法主要步驟

首先, 因為兩個數位的 precision 和 scale 可能不相同, 需要做一些準備工作, 將小數點對齊, 然後開始計算, 從最末尾小數開始向高位加, 分為三個步驟：

將小數較多的 decimal 多出的小數數位複製到結果中
將兩個 decimal 公共的部分相加
將整數較多的 decimal 多出的整數數位與進位相加到結果中

程式碼中使用了 stop, stop2 來標記小數點對齊後, 長度不同的數位出現差異的位置.

/* part 1 - max(frac) ... min (frac) */
while (buf1 > stop) *--buf0 = *--buf1;

/* part 2 - min(frac) ... min(intg) */
carry = 0;
while (buf1 > stop2) {
  ADD(*--buf0, *--buf1, *--buf2, carry);
}

/* part 3 - min(intg) ... max(intg) */
buf1 = intg1 > intg2 ? ((stop3 = from1->buf) + intg1 - intg2)
                     : ((stop3 = from2->buf) + intg2 - intg1);
while (buf1 > stop3) {
  ADD(*--buf0, *--buf1, 0, carry);
}

乘法主要步驟

乘法引入了一個新的 dec2, 表示一個 64 bit 的數位, 這是因為兩個 decimal_digit_t(int32) 相乘後得到的可能會是一個 64 bit 的數位. 在計算時一定要先把型別轉換到 dec2(int64), 再計算, 否則會得到溢位後的錯誤結果. 乘法與加法不同, 乘法不需要對齊, 例如計算 11.11 5.0, 那麼只要計算 111150=55550, 再移動小數點位置就能得到正確結果 55.550

MySQL 實現了一個雙重回圈將 decimal1 的每一個 decimal_digit_t 與 decimal2 的每一個 decimal_digit_t 相乘, 得到一個 64 位的 dec2, 其低 32 位是當前的結果, 其高 32 位是進位.

typedef decimal_digit_t dec1;
typedef longlong dec2;

for (buf1 += frac1 - 1; buf1 >= stop1; buf1--, start0--) {
  carry = 0;
  for (buf0 = start0, buf2 = start2; buf2 >= stop2; buf2--, buf0--) {
    dec1 hi, lo;
    dec2 p = ((dec2)*buf1) * ((dec2)*buf2);
    hi = (dec1)(p / DIG_BASE);
    lo = (dec1)(p - ((dec2)hi) * DIG_BASE);
    ADD2(*buf0, *buf0, lo, carry);
    carry += hi;
  }
  if (carry) {
    if (buf0 < to->buf) return E_DEC_OVERFLOW;
    ADD2(*buf0, *buf0, 0, carry);
  }
  for (buf0--; carry; buf0--) {
    if (buf0 < to->buf) return E_DEC_OVERFLOW;
    ADD(*buf0, *buf0, 0, carry);
  }
}

除法主要步驟

除法使用的是 Knuth's Algorithm D, 其基本思路和手動除法也比較類似.

首先使用除數的前兩個 decimal_digit_t 組成一個試商因數, 這裡使用了一個 norm_factor 來保證數位在不溢位的情況下儘可能擴大, 這是因為 decimal 為了保證精度必須使用整形來進行計算, 數位越大, 得到的結果就越準確. D3: 猜商, 就是用被除數的前兩個 decimal_digit_t 除以試商因數這裡如果不乘 norm_factor, 則 start1[1] 和 start2[1] 都不會體現在結果之中.

D4: 將 guess 與除數相乘, 再從被除數中剪掉結果然後做一些修正, 移動向下一個 decimal_digit_t, 重複這個過程.

想更詳細地瞭解這個演演算法可以參考 https://skanthak.homepage.t-online.de/division.html

norm2 = (dec1)(norm_factor * start2[0]);
if (likely(len2 > 0)) norm2 += (dec1)(norm_factor * start2[1] / DIG_BASE)；

x = start1[0] + ((dec2)dcarry) * DIG_BASE;
y = start1[1];
guess = (norm_factor * x + norm_factor * y / DIG_BASE) / norm2;

for (carry = 0; buf2 > start2; buf1--) {
  dec1 hi, lo;
  x = guess * (*--buf2);
  hi = (dec1)(x / DIG_BASE);
  lo = (dec1)(x - ((dec2)hi) * DIG_BASE);
  SUB2(*buf1, *buf1, lo, carry);
  carry += hi;
}
carry = dcarry < carry;

3.2 ClickHouse

ClickHouse 是列存, 相同列的資料會放在一起, 因此計算時通常也將一列的資料合成 batch 一起計算.

一列的 batch 在 ClickHouse 中使用 PODArray, 例如上圖中的 c1 在計算時就會有一個 PODArray, 進行簡化後大致可以表示如下:

class PODArray {
    char * c_start          = null;
    char * c_end            = null;
    char * c_end_of_storage = null;
}

在計算時會講 c_start 指向的陣列轉換成實際的型別, 對於 decimal, ClickHouse 使用足夠大的 int 來表示, 根據 decimal 的 precision 選擇 int32, int64 或者 int128. 例如一個 decimal(10, 2), 123.45, 使用這樣方式可以表示為一個 int32_t, 其內容為 12345, decimal(10, 3) 的 123.450 表示為 123450. ClickHouse 用來表示每個 decimal 的結構如下, 實際上就是足夠大的 int：

template <typename T>
struct Decimal
{
    using NativeType = T;
    // ...
    T value;
};
using Int32 = int32_t;
using Int64 = int64_t;
using Int128 = __int128;
using Decimal32 = Decimal<Int32>;
using Decimal64 = Decimal<Int64>;
using Decimal128 = Decimal<Int128>;

顯而易見, 這樣的表示方法相較於 MySQL 的方法更輕量, 但是範圍更小, 同時也帶來了一個問題是沒有小數點的位置, 在進行加減法、大小比較等需要小數點對齊的場景下, ClickHouse 會在運算實際發生的時候將 scale 以引數的形式傳入, 此時配合上面的數位就可以正確地還原出真實的 decimal 值了.

ResultDataType type = decimalResultType(left, right, is_multiply, is_division);

int scale_a = type.scaleFactorFor(left, is_multiply);
int scale_b = type.scaleFactorFor(right, is_multiply || is_division);
OpImpl::vector_vector(col_left->getData(), col_right->getData(), vec_res,
                      scale_a, scale_b, check_decimal_overflow);

例如兩個 decimal: a = 123.45000(p=8, s=5), b = 123.4(p=4, s=1), 那麼計算時傳入的引數就是 col_left->getData() = 123.45000 10 ^ 5 = 12345000, scale_a = 1, col_right->getData() = 123.4 10 ^ 1 = 1234, scale_b = 10000, 12345000 1 和 1234 10000 的小數點位置是對齊的, 可以直接計算.

加法主要步驟

ClickHouse 實現加法同樣要先對齊, 對齊的方法是將 scale 較小的數位乘上一個係數, 使兩邊的 scale 相等. 然後直接做加法即可. ClickHouse 在計算中也根據 decimal 的 precision 進行了細分, 對於長度沒那麼長的 decimal, 直接用 int32, int64 等原生型別計算就可以了, 這樣大大提升了速度.

bool overflow = false;
if constexpr (scale_left)
    overflow |= common::mulOverflow(a, scale, a);
else
    overflow |= common::mulOverflow(b, scale, b);

overflow |= Op::template apply<NativeResultType>(a, b, res);

template <typename T>
inline bool addOverflow(T x, T y, T & res)
{
    return __builtin_add_overflow(x, y, &res);
}

template <>
inline bool addOverflow(__int128 x, __int128 y, __int128 & res)
{
    static constexpr __int128 min_int128 = __int128(0x8000000000000000ll) << 64;
    static constexpr __int128 max_int128 = (__int128(0x7fffffffffffffffll) << 64) + 0xffffffffffffffffll;
    res = x + y;
    return (y > 0 && x > max_int128 - y) || (y < 0 && x < min_int128 - y);
}

乘法主要步驟

同 MySQL, 乘法不需要對齊, 直接按整數相乘就可以了, 比較短的 decimal 同樣可以使用 int32, int64 原生型別. int128 在溢位檢測時被轉換成 unsigned int128 避免溢位時的未定義行為.

template <typename T>
inline bool mulOverflow(T x, T y, T & res)
{
    return __builtin_mul_overflow(x, y, &res);
}

template <>
inline bool mulOverflow(__int128 x, __int128 y, __int128 & res)
{
    res = static_cast<unsigned __int128>(x) * static_cast<unsigned __int128>(y);    /// Avoid signed integer overflow.
    if (!x || !y)
        return false;

    unsigned __int128 a = (x > 0) ? x : -x;
    unsigned __int128 b = (y > 0) ? y : -y;
    return (a * b) / b != a;
}

除法主要步驟

先轉換 scale 再直接做整數除法. 本身來講除法和乘法一樣是不需要對齊小數點的, 但是除法不一樣的地方在於可能會產生無限小數, 所以一般資料庫都會給結果一個固定的小數位數, ClickHouse 選擇的小數位數是和被除數一樣, 因此需要將 a 乘上 scale, 然後在除法運算的過程中, 這個 scale 被自然減去, 得到結果的小數位數就可以保持和被除數一樣.

bool overflow = false;
if constexpr (!IsDecimalNumber<A>)
    overflow |= common::mulOverflow(scale, scale, scale);
overflow |= common::mulOverflow(a, scale, a);
if (overflow)
    throw Exception("Decimal math overflow", ErrorCodes::DECIMAL_OVERFLOW);

return Op::template apply<NativeResultType>(a, b);

3.3 總結

MySQL 通過一個 int32 的陣列來表示一個大數, ClickHouse 則是儘可能使用原生型別, GCC 和 Clang 都支援 int128 擴充套件, 這使得 ClickHouse 的這種做法可以比較方便地實現.

MySQL 與 ClickHouse 的實現差別還是比較大的, 針對我們開始提到的問題, 分別來看看他們的解答.

precision 和 scale 範圍, MySQL 最高可定義 precision=65, scale=30, 中間結果最多包含 81 個數位, ClickHouse 最高可定義 precision=38, scale=37, 中間結果最大為 int128 的最大值 -2^127 ~ 2^127-1.
在哪裡儲存 scale, MySQL 是行式儲存, 使用火山模型逐行迭代, 計算也是按行進行, 每個 decimal 都有自己的 scale；ClickHouse 是列式儲存, 計算按列批次進行, 每行按照相同的 scale 處理能提升效能, 因此 scale 來自表示式解析過程中推匯出來的型別.
scale 增長, scale 增長超過極限時, MySQL 會通過動態擠佔小數空間, truncate 運算數, 儘可能保證計算完成, ClickHouse 會直接報溢位錯.
除法 scale, MySQL 通過 div_prec_increment 來控制除法結果的 scale, ClickHouse 固定使用被除數的 scale.
效能, MySQL 使用了更寬的 decimal 表示, 同時要進行 ROUND_UP, 小數擠佔, TRUNCATE 等動作, 效能較差, ClickHouse 使用原生的資料型別和計算最大限度地提升了效能.

4. MySQL 違反直覺的地方

在這一部分中, 我們將講述一些 MySQL 實現造成的違反直覺的地方. 這些行為通常發生在運算結果接近 81 digit 時, 因此如果可以保證運算結果的範圍較小也可以忽略這些問題.

乘法的 scale 會截斷到 31, 且該截斷是通過截斷運算數位的方式來實現的, 例如: select 10000000000000000000000000000000.100000000 10000000000000000000000000000000 = 10000000000000000000000000000000.100000000000000000000000000000 10000000000000000000000000000000.555555555555555555555555555555 返回 1, 第二個運算數中的 .555555555555555555555555555555 全部被截斷
MySQL 使用的 buffer 包含了 81 個 digit 的容量, 但是由於小數部分必須和整數部分分開, 因此很多時候無法用滿 81 個 digit, 例如: select 99999999999999999999999999999999999999999999999999999999999999999999999999.999999 = 99999999999999999999999999999999999999999999999999999999999999999999999999.9 返回 1
計算過程中如果發現整數部分太大會動態地擠佔小數部分, 例如: select 999999999999999999999999999999999999999999999999999999999999999999999999.999999999 + 999999999999999999999999999999999999999999999999999999999999999999999999.999999999 = 999999999999999999999999999999999999999999999999999999999999999999999999 + 999999999999999999999999999999999999999999999999999999999999999999999999 返回 1
除法計算中間結果不受 scale = 31 的限制, 除法中間結果的 scale 一定是 9 的整數倍, 不能按照最終結果來推測除法作為中間結果的精度, 例如 select 2.0000 / 3 3 返回 2.00000000, 而 select 2.00000 / 3 3 返回 1.999999998, 可見前者除法的中間結果其實保留了更多的精度.
除法, avg 計算最終結果的小數部分如果正好是 9 的倍數, 則不會四捨五入, 例如: select 2.00000 / 3 返回 0.666666666, select 2.0000 / 3 返回 0.66666667
除法, avg 計算時, 運算數位的小數部分如果不是 9 的倍數, 那麼會實際上儲存 9 的倍數個小數數位, 因此會出現以下差異：

create table t1 (a decimal(20, 2), b decimal(20, 2), c integer);

insert into t1 values (100000.20, 1000000.10,   5);
insert into t1 values (200000.20, 2000000.10,   2);
insert into t1 values (300000.20, 3000000.10,   4);
insert into t1 values (400000.20, 4000000.10,   6);
insert into t1 values (500000.20, 5000000.10,   8);
insert into t1 values (600000.20, 6000000.10,   9);
insert into t1 values (700000.20, 7000000.10,   8);
insert into t1 values (800000.20, 8000000.10,   7);
insert into t1 values (900000.20, 9000000.10,   7);
insert into t1 values (1000000.20, 10000000.10, 2);
insert into t1 values (2000000.20, 20000000.10, 5);
insert into t1 values (3000000.20, 30000000.10, 2);

select sum(a+b), avg(c), sum(a+b) / avg(c) from t1;
+--------------+--------+-------------------+
| sum(a+b)     | avg(c) | sum(a+b) / avg(c) |
+--------------+--------+-------------------+
| 115500003.60 | 5.4167 |   21323077.590317 |
+--------------+--------+-------------------+
1 row in set (0.01 sec)

select 115500003.60 / 5.4167;
+-----------------------+
| 115500003.60 / 5.4167 |
+-----------------------+
|       21322946.369561 |
+-----------------------+
1 row in set (0.00 sec)