数据库内核月报

数据库内核月报 － 2021 / 03

MySQL · 源码阅读 · Decimal 的实现方法

Author: 臻成

背景

数字运算在数据库中是很常见的需求, 例如计算数量、重量、价格等, 为了满足各种需求, 数据库系统通常支持精准的数字类型和近似的数字类型. 精准的数字类型包含 int, decimal 等, 这些类型在计算过程中小数点位置是固定的, 其结果和行为比较可预测. 当涉及钱时, 这个问题尤其重要, 因此部分数据库实现了专门的 money 类型. 近似的数字类型包含 float, double 等, 这些数字的精度是浮动的.

本文将简要介绍 decimal 类型的数据结构和计算, 对比 decimal 在 MySQL, ClickHouse 两个不同类型系统中的实现差异, 描述实现 decimal 运算的主要思路. MySQL 在结果的长度比较接近上限的情况下, 会有比较违反直觉的地方, 本文会在最后列出这些可能需要注意的问题.

创建和使用 decimal

decimal 的使用在多数数据库上都差不多, 下面以 MySQL 的 decimal 为例, 介绍 decimal 的基本使用方法.

描述 decimal

与 float 和 double 不同, decimal 在创建时需要指定两个描述精度的数字, 分别是 precision 和 scale, precision 指整个 decimal 包括整数和小数部分一共有多少个数字, scale 指 decimal 的小数部分包含多少个数字, 例如：123.45 就是一个 precision=5, scale=2 的 decimal. 我们可以在建表时按照这种方式定义我们想要的 decimal.

在建表时定义 decimal

可以在建表时这样定义一个 decimal:

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

写入 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) 也不满足要求.

取出 decimal 进行计算

计算的结果不受定义的限制, 而是受到内部实现格式的影响, 对于 MySQL 结果最大可以到 precision=81, scale=30, 但是由于 MySQL decimal 的内存格式和计算函数实现问题, 这个大小不是在所有情况都能达到, 将在后文中详细介绍. 继续上面的例子中：

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

结果突破了 precision=5, scale=2 的限制, 这里涉及运算时 scale 的变化, 基本规则是：

  1. 加法/减法/sum：取两边最大的 scale
  2. 乘法：两边的 scale 相加
  3. 除法：被除数的 scale + div_precision_increment(取决于数据库实现)

decimal 实现

在这一部分中, 我们主要介绍 MySQL 的 decimal 实现, 此外也会对比 ClickHouse, 看看 decimal 在不同系统中的设计与实现差异.

实现 decimal 需要思考以下问题

  1. 支持多大的 precision 和 scale
  2. 在哪里存储 scale
  3. 在连续乘法或除法时, scale 不断增长, 整数部分也不断扩大, 而存储的 buffer 大小总是又上限的, 此时应该如何处理？
  4. 除法可能产生无限小数, 如何决定除法结果的 scale?
  5. decimal 的表示范围和计算性能是否有冲突, 是否可以兼顾

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 等代码.

pic

ClickHouse

ClickHouse 是列存, 相同列的数据会放在一起, 因此计算时通常也将一列的数据合成 batch 一起计算.

pic

一列的 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 的小数点位置是对齐的, 可以直接计算.

总结

MySQL 通过一个 int32 的数组来表示一个大数, ClickHouse 则是尽可能使用原生类型, GCC 和 Clang 都支持 int128 扩展, 这使得 ClickHouse 的这种做法可以比较方便地实现. MySQL 与 ClickHouse 的实现差别还是比较大的, 针对我们开始提到的问题, 分别来看看他们的解答.

  1. precision 和 scale 范围, MySQL 最高可定义 precision=65, scale=30, 中间结果最多包含 81 个数字, ClickHouse 最高可定义 precision=38, scale=37, 中间结果最大为 int128 的最大值 -2^127 ~ 2^127-1.
  2. 在哪里存储 scale, MySQL 是行式存储, 使用火山模型逐行迭代, 计算也是按行进行, 每个 decimal 都有自己的 scale；ClickHouse 是列式存储, 计算按列批量进行, 每行按照相同的 scale 处理能提升性能, 因此 scale 来自表达式解析过程中推导出来类型中.
  3. scale 增长, scale 增长超过极限时, MySQL 会通过动态挤占小数空间, truncate 运算数, 尽可能保证计算完成, ClickHouse 会直接报溢出错.
  4. 除法 scale, MySQL 通过 div_prec_increment 来控制除法结果的 scale, ClickHouse 固定使用被除数的 scale.
  5. 性能, MySQL 使用了更宽的 decimal 表示, 同时要进行 ROUND_UP, 小数挤占, TRUNCATE 等动作, 性能较差, ClickHouse 使用原生的数据类型和计算最大限度地提升了性能.

MySQL decimal

在这一部分中, 我们将讲述一些 MySQL 实现造成的违反直觉的地方. 这些行为通常发生在运算结果接近 81 digit 时, 因此如果可以保证运算结果的范围较小也可以忽略这些问题.

  1. 乘法的 scale 会截断到 31, 且该截断是通过截断运算数字的方式来实现的, 例如: select 10000000000000000000000000000000.100000000 * 10000000000000000000000000000000 = 10000000000000000000000000000000.100000000000000000000000000000 * 10000000000000000000000000000000.555555555555555555555555555555 返回 1, 第二个运算数中的 .555555555555555555555555555555 全部被截断
  2. MySQL 使用的 buffer 包含了 81 个 digit 的容量, 但是由于小数部分必须和整数部分分开, 因此很多时候无法用满 81 个 digit, 例如: select 99999999999999999999999999999999999999999999999999999999999999999999999999.999999 = 99999999999999999999999999999999999999999999999999999999999999999999999999.9 返回 1
  3. 计算过程中如果发现整数部分太大会动态地挤占小数部分, 例如: select 999999999999999999999999999999999999999999999999999999999999999999999999.999999999 + 999999999999999999999999999999999999999999999999999999999999999999999999.999999999 = 999999999999999999999999999999999999999999999999999999999999999999999999 + 999999999999999999999999999999999999999999999999999999999999999999999999 返回 1
  4. 除法计算中间结果不受 scale = 31 的限制, 除法中间结果的 scale 一定是 9 的整数倍, 不能按照最终结果来推测除法作为中间结果的精度, 例如 select 2.0000 / 3 * 3 返回 2.00000000, 而 select 2.00000 / 3 * 3 返回 1.999999998, 可见前者除法的中间结果其实保留了更多的精度.
  5. 除法, avg 计算最终结果的小数部分如果正好是 9 的倍数, 则不会四舍五入, 例如: select 2.00000 / 3 返回 0.666666666, select 2.0000 / 3 返回 0.66666667