lide-reed edited a comment on issue #695: Optimize decimal URL: https://github.com/apache/incubator-doris/issues/695#issuecomment-471912925 # Doris DecimalV2 设计文档 ## 1 引入 DecimalV2 的背景 ### 1.1 Decimal 类型介绍 Decimal 是有固定精度和小数位数的数据类型。 Decimal 和 Numeric 是同义词，可以互换使用。 Deicimal 可以有如下表示： ``` decimal[ (p[ ,s] )] and numeric[ (p[ ,s] )] ``` 固定的精度和小数位数数字。当使用最大精度的时候，有效位从 -10^38 + 1 到 10^38 - 1. 其中： ``` p (precision) 表示将被用来存储十进制数字的总位数，包括小数点左边的整数部分和右边的小数部分。 范围从 1 到 38 （SQL Server 默认是18）. s (scale) 表示将被用来存储十进制数字的小数部分的位数。p - s 即是小数点左边整数部分的位数。 范围从 0 到 p. Scale 默认是 0，由于其范围是 0 <= s <= p， 所有最大存储字节是可变的，基于精度 precision。 ``` ### 1.2 为什么需要 Decimal 类型 由于计算机内部无法用二进制来精确的表达10进制小数，而有些场合（例如金融）需要精确的小数计算，Float 和 Double 不能满足这种精确性要求，因此需要引入 Decimal 类型。 ### 1.3 现有的 Decimal 实现的问题 现有的 Decimal 虽然理论上可以实现 38 为精度，但是实际受存储格式（12个字节）限制，实际只能表示（27, 9）精度的 Decimal。 现有的 Decimal 是通过 40 个字节的 buffer 实现的，定义如下： ``` #define DECIMAL_BUFF_LENGTH 9 class DecimalValue { ... private: int32_t _int_length : 8; int32_t _frac_length : 8; int32_t _buffer_length : 8; bool _sign; int32_t _buffer[DECIMAL_BUFF_LENGTH]; }; ``` 由于数据占用空间较大，而且计算按照十进制位操作，因此性能不好，尤其影响TPC-DS查询性能。 ## 2 DecimalV2 实现方案 ### 2.1 如何表示 通过一个 128 位整数（16个字节）表示 Decimal，其中后 32 位表示小数部分， 前面 96 位表示整数部分（包括符号），当前受存储限制，精度固定为 (27,9)。 ``` class DecimalValue { ... private: int128_t _value; }; ``` 这个设计正好对应存储的整数部分和小数部分。 ``` struct decimal12_t { static const int32_t FRAC_RATIO = 1000000000; static const int32_t MAX_INT_DIGITS_NUM = 18; static const int32_t MAX_FRAC_DIGITS_NUM = 9; int64_t integer; int32_t fraction; ... } ``` ### 2.2 加法 考虑正负数和溢出判断，分两层实现：do_add 只做两个正数的相加操作。 ``` static const uint32_t ONE_BILLION = 1000000000; static const int64_t MAX_INT_VALUE = 999999999999999999; static const int32_t MAX_FRAC_VALUE = 999999999; static const int128_t MAX_DECIMAL_VALUE = static_cast<int128_t>(MAX_INT_VALUE) * ONE_BILLION + MAX_FRAC_VALUE; // x>=0 && y>=0 static int do_add(int128_t x, int128_t y, int128_t* result) { int error = E_DEC_OK; if (DecimalV2Value::MAX_DECIMAL_VALUE - x >= y) { *result = x + y; } else { *result = DecimalV2Value::MAX_DECIMAL_VALUE; error = E_DEC_OVERFLOW; LOG(INFO) << "overflow (x=" << x << ", y=" << y << ")"; } return error; } DecimalV2Value operator+(const DecimalV2Value& v1, const DecimalV2Value& v2) { int128_t result; int128_t x = v1.value(); int128_t y = v2.value(); if (x == 0) { result = y; } else if (y == 0) { result = x; } else if (x > 0) { if (y > 0) { do_add(x, y, &result); } else { do_sub(x, -y, &result); } } else { // x < 0 if (y > 0) { do_sub(y, -x, &result); } else { do_add(-x, -y, &result); result = -result; } } return DecimalV2Value(result); } ``` ### 2.3 减法 考虑正负数和溢出判断，分两层实现：do_sub 只做两个正数的相减操作。 ``` static int do_sub(int128_t x, int128_t y, int128_t* result) { int error = E_DEC_OK; *result = x - y; return error; } DecimalV2Value operator-(const DecimalV2Value& v1, const DecimalV2Value& v2) { int128_t result; int128_t x = v1.value(); int128_t y = v2.value(); if (x == 0) { result = -y; } else if (y == 0) { result = x; } else if (x > 0) { if (y > 0) { do_sub(x, y, &result); } else { do_add(x, -y, &result); } } else { // x < 0 if (y > 0) { do_add(-x, y, &result); result = -result; } else { do_sub(-x, -y, &result); result = -result; } } return DecimalV2Value(result); } ``` ### 2.4 乘法 考虑正负数和溢出判断，分两层实现：do_mul 只做两个正数的相乘操作。 ``` // clear leading zero for __int128 static int clz128(unsigned __int128 v) { if (v == 0) return 128; unsigned __int128 shifted = v >> 64; if (shifted != 0) { return __builtin_clzll(shifted); } else { return __builtin_clzll(v) + 64; } } static int do_mul(int128_t x, int128_t y, int128_t* result) { int error = E_DEC_OK; // The bits of result as following is 120 // clz128((MAX_INT_VALUE * ONE_BILLION + MAX_FRAC_VALUE) * ONE_BILLION) = 8 // The bits range of m * n is in (m+n-1 --> m+n) int bits = 128 + 128 - clz128(x) - clz128(y); if (bits > (120 + 1)) { *result = DecimalV2Value::MAX_DECIMAL_VALUE; LOG(INFO) << "overflow (x=" << x << ", y=" << y << ")"; error = E_DEC_OVERFLOW; return error; } int128_t product = x * y; *result = product / DecimalV2Value::ONE_BILLION; // overflow if (*result > DecimalV2Value::MAX_DECIMAL_VALUE) { *result = DecimalV2Value::MAX_DECIMAL_VALUE; LOG(INFO) << "overflow (x=" << x << ", y=" << y << ")"; error = E_DEC_OVERFLOW; return error; } // truncate with round int128_t remainder = product % DecimalV2Value::ONE_BILLION; if (remainder != 0) { error = E_DEC_TRUNCATED; if (remainder >= (DecimalV2Value::ONE_BILLION >> 1)) { *result += 1; } LOG(INFO) << "truncate (x=" << x << ", y=" << y << ")" << ", result=" << *result; } return error; } DecimalV2Value operator*(const DecimalV2Value& v1, const DecimalV2Value& v2){ int128_t result; int128_t x = v1.value(); int128_t y = v2.value(); if (x == 0 || y == 0) return DecimalV2Value(0); bool is_positive = (x > 0 && y > 0) || (x < 0 && y < 0); do_mul(abs(x), abs(y), &result); if (!is_positive) result = -result; return DecimalV2Value(result); } ``` ### 2.5 除法 考虑正负数和溢出判断，分两层实现：do_div 只做两个正数的相除操作。 ``` static int do_div(int128_t x, int128_t y, int128_t* result) { int error = E_DEC_OK; int128_t dividend = x * DecimalV2Value::ONE_BILLION; *result = dividend / y; // overflow int128_t remainder = dividend % y; if (remainder != 0) { error = E_DEC_TRUNCATED; if (remainder >= (y >> 1)) { *result += 1; } LOG(INFO) << "truncate (x=" << x << ", y=" << y << ")" << ", result=" << *result; } return error; } DecimalV2Value operator/(const DecimalV2Value& v1, const DecimalV2Value& v2){ int128_t result; int128_t x = v1.value(); int128_t y = v2.value(); //todo: return 0 for divide zero if (x == 0 || y == 0) return DecimalV2Value(0); bool is_positive = (x > 0 && y > 0) || (x < 0 && y < 0); do_div(abs(x), abs(y), &result); if (!is_positive) result = -result; return DecimalV2Value(result); } ``` ### 2.6 取余 考虑正负数和溢出判断，分两层实现：do_mod 只做两个正数的取余操作。 ``` static int do_mod(int128_t x, int128_t y, int128_t* result) { int error = E_DEC_OK; *result = x % y; return error; } DecimalV2Value operator%(const DecimalV2Value& v1, const DecimalV2Value& v2){ int128_t result; int128_t x = v1.value(); int128_t y = v2.value(); //todo: return 0 for divide zero if (x == 0 || y == 0) return DecimalV2Value(0); do_mod(x, y, &result); return DecimalV2Value(result); } ``` ## 3 其它问题 ### 3.1 对齐问题 当通过 GCC 7 编译后，16 字节的数据拷贝需要对齐，如果源数据不对齐会导致 Core dump。 如果一定要对未对齐的 16 字节数据进行拷贝，就需要告诉编译器，不要用 SSE 提供的对对齐字节的操作指令，或者直接用 memcpy。 如下所示，有两种指令，通过 gdb 的 x/i $pc 指令可以查看当前指令： 指令 | 说明 ------------- | ------------- movdqa | 把2个对齐的四字节整数传送到xmm寄存器或者内存 movdqu | 把2个不对齐的四字节整数传送到xmm寄存器或者内存 ### 3.2 兼容之前的 Decimal 问题 考虑滚动升级和用户的业务兼容性，在 FE 中，将用户输入的以及从Catalog 中读取的 Decimal 转为 DecimalV2，同时对将写入 Catalog 中的 DecimalV2 转为 Decimal。
---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected] With regards, Apache Git Services --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
