1 背景

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

本文將簡要介紹 decimal 類型的數(shù)據(jù)結構和計算, 對比 decimal 在 MySQL, ClickHouse 兩個不同類型系統(tǒng)中的實現(xiàn)差異, 描述實現(xiàn) decimal 運算的主要思路. MySQL 在結果的長度比較接近上限的情況下, 會有比較違反直覺的地方, 本文會在最后列出這些可能需要注意的問題.

2 Decimal類型的使用

decimal 的使用在多數(shù)數(shù)據(jù)庫上都差不多, 下面以 MySQL 的 decimal 為例, 介紹 decimal 的基本使用方法.

2.1 描述Decimal

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

2.2 建表時定義Decimal

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

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

2.3 寫入decimal數(shù)據(jù)

可以向其中插入合法的數(shù)據(jù), 例如

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

此時執(zhí)行 select * from t 會得到

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

注意到 123.4 變成了 123.40, 這就是精確類型的特點, d 列的每行數(shù)據(jù)都要求 scale=2, 即小數(shù)點后有兩位

當插入不滿足 precision 和 scale 定義的數(shù)據(jù)時

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)這樣的數(shù)字看起來滿足要求, 但實際上需要滿足 scale=2 的要求, 因此會變成 1234.50(precision=6, scale=2) 也不滿足要求.

2.4 取出deimcal進行計算

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

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

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

1. 加法/減法/sum：取兩邊最大的 scale
2. 乘法：兩邊的 scale 相加
3. 除法：被除數(shù)的 scale + div_precision_increment(取決于數(shù)據(jù)庫實現(xiàn))

3 Decimal類型的實現(xiàn)

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

實現(xiàn) decimal 需要思考以下問題

1. 支持多大的 precision 和 scale
2. 在哪里存儲 scale
3. 在連續(xù)乘法或除法時, scale 不斷增長, 整數(shù)部分也不斷擴大, 而存儲的 buffer 大小總是有上限的, 此時應該如何處理？
4. 除法可能產生無限小數(shù), 如何決定除法結果的 scale?
5. decimal 的表示范圍和計算性能是否有沖突, 是否可以兼顧

3.1 MySQL

先來看看 MySQL decimal 相關的數(shù)據(jù)結構

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) 的數(shù)組 buf 來存儲 decimal 的數(shù)字, 每個 decimal_digit_t 最多存儲 9 個數(shù)字, 用 intg 表示整數(shù)部分的數(shù)字個數(shù), frac 表示小數(shù)部分的數(shù)字個數(shù), sign 表示符號. 小數(shù)部分和整數(shù)部分需要分開存儲, 不能混合在一個 decimal_digit_t 中, 兩部分都向小數(shù)點對齊, 這是因為整數(shù)和小數(shù)通常需要分開計算, 所以這樣的格式可以更容易地將不同 decimal_t 小數(shù)和整數(shù)分別對齊, 便于加減法運算. len 在 MySQL 實現(xiàn)中恒為 9, 它表示存儲的上限, 而 buf 實際有效的部分, 則是由 intg 和 frac 共同決定. 例如：

// 123.45 decimal(5, 2) 整數(shù)部分為 3,  小數(shù)部分為 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, 它就表示整數(shù)部分為 123, 第二個數(shù)字為 450000000 (共 9 個數(shù)字), 由于 frac=2, 它表示小數(shù)部分為 .45

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

// decimal(81, 18) 63 個整數(shù)數(shù)字, 18 個小數(shù)數(shù)字, 用滿整個 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 個數(shù)字, 但是也有些場景無法用滿 81 個數(shù)字, 這是因為整數(shù)和小數(shù)部分是分開存儲的, 所以一個 decimal_digit_t (int32) 可能只存儲了一個有效的小數(shù)數(shù)字, 但是其余的部分沒有辦法給整數(shù)部分使用, 例如一個 decimal 整數(shù)部分有 62 個數(shù)字, 小數(shù)部分有 19 個數(shù)字(precision=81, scale=19), 那么小數(shù)部分需要使用 3 個 decimal_digit_t (int32), 整數(shù)部分還有 54 個數(shù)字的余量, 無法存下 62 個數(shù)字. 這種情況下, MySQL 會優(yōu)先滿足整數(shù)部分的需求, 自動截斷小數(shù)點后的部分, 將它變成 decimal(80, 18)

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

準備步驟

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

1. MySQL 會將數(shù)字的個數(shù) ROUND_UP 到 9 的整數(shù)倍, 這樣后面就可以按照 decimal_digit_t 為單位來進行計算
2. 此外還要針對參與運算的兩個 decimal 的具體情況, 計算結果的 precision 和 scale, 如果發(fā)現(xiàn)結果的 precision 超過了支持的上限, 那么會按照 decimal_digit_t 為單位減少小數(shù)的數(shù)字.
3. 在乘法過程中, 如果發(fā)生了 2 中的減少行為, 則需要 TRUNCATE 兩個運算數(shù), 避免中間結果超出范圍.

加法主要步驟

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

1. 將小數(shù)較多的 decimal 多出的小數(shù)數(shù)字復制到結果中
2. 將兩個 decimal 公共的部分相加
3. 將整數(shù)較多的 decimal 多出的整數(shù)數(shù)字與進位相加到結果中

代碼中使用了 stop, stop2 來標記小數(shù)點對齊后, 長度不同的數(shù)字出現(xiàn)差異的位置.

/* 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 的數(shù)字, 這是因為兩個 decimal_digit_t(int32) 相乘后得到的可能會是一個 64 bit 的數(shù)字. 在計算時一定要先把類型轉換到 dec2(int64), 再計算, 否則會得到溢出后的錯誤結果. 乘法與加法不同, 乘法不需要對齊, 例如計算 11.11 5.0, 那么只要計算 111150=55550, 再移動小數(shù)點位置就能得到正確結果 55.550

MySQL 實現(xiàn)了一個雙重循環(huán)將 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, 其基本思路和手動除法也比較類似.

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

D4: 將 guess 與除數(shù)相乘, 再從被除數(shù)中剪掉結果 然后做一些修正, 移動向下一個 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 是列存, 相同列的數(shù)據(jù)會放在一起, 因此計算時通常也將一列的數(shù)據(jù)合成 batch 一起計算.

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

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

在計算時會講 c_start 指向的數(shù)組轉換成實際的類型, 對于 decimal, ClickHouse 使用足夠大的 int 來表示, 根據(jù) 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 的方法更輕量, 但是范圍更小, 同時也帶來了一個問題是沒有小數(shù)點的位置, 在進行加減法、大小比較等需要小數(shù)點對齊的場景下, ClickHouse 會在運算實際發(fā)生的時候將 scale 以參數(shù)的形式傳入, 此時配合上面的數(shù)字就可以正確地還原出真實的 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), 那么計算時傳入的參數(shù)就是  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 的小數(shù)點位置是對齊的, 可以直接計算.

加法主要步驟

ClickHouse 實現(xiàn)加法同樣要先對齊, 對齊的方法是將 scale 較小的數(shù)字乘上一個系數(shù), 使兩邊的 scale 相等. 然后直接做加法即可. ClickHouse 在計算中也根據(jù) 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, 乘法不需要對齊, 直接按整數(shù)相乘就可以了, 比較短的 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 再直接做整數(shù)除法. 本身來講除法和乘法一樣是不需要對齊小數(shù)點的, 但是除法不一樣的地方在于可能會產生無限小數(shù), 所以一般數(shù)據(jù)庫都會給結果一個固定的小數(shù)位數(shù), ClickHouse 選擇的小數(shù)位數(shù)是和被除數(shù)一樣, 因此需要將 a 乘上 scale, 然后在除法運算的過程中, 這個 scale 被自然減去, 得到結果的小數(shù)位數(shù)就可以保持和被除數(shù)一樣.

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 的數(shù)組來表示一個大數(shù), ClickHouse 則是盡可能使用原生類型, GCC 和 Clang 都支持 int128 擴展, 這使得 ClickHouse 的這種做法可以比較方便地實現(xiàn).

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

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

4. MySQL 違反直覺的地方

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

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

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)

總結

到此這篇關于數(shù)據(jù)庫中Decimal類型使用以及實現(xiàn)方法的文章就介紹到這了,更多相關Decimal類型使用及實現(xiàn)內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論