Performance Issues with TiDB Decimal Calculations

Note:
This topic has been translated from a Chinese forum by GPT and might contain errors.

Original topic: tidb decimal 计算性能问题

| username: TiDBer_IcYbdUP9

Currently, the project uses TiDB’s decimal to replace shopspring/decimal. It was found that the Mul function provided in the utility functions is marked as naive vertical multiplication, and it is recommended to implement faster multiplication in scenarios with more digits. Is there any related explanation about the design principle of this multiplication?
https://github.com/pingcap/tidb/blob/master/types/mydecimal.go
And is there any consideration to use the Karatsuba algorithm for multiplication?
Thanks~

| username: Billmay表妹 | Original post link

The Decimal type in TiDB is implemented based on MySQL’s Decimal type, and its multiplication operation is realized using the naive long multiplication method. The principle of this multiplication algorithm is relatively simple: it follows the long multiplication method, multiplying digit by digit, and then summing the results to get the final outcome. The advantage of this algorithm is that it is easy to implement and understand, but its drawback is low efficiency, especially when calculating Decimal values with a large number of digits, where performance can be quite poor.

In TiDB’s code, for Decimal values with a large number of digits, a faster multiplication algorithm, the Karatsuba algorithm, is implemented. The principle of this algorithm is to split two large numbers into two smaller numbers, then recursively calculate the products of these smaller numbers, and finally combine these products to get the final result. The advantage of this algorithm is high efficiency, particularly when calculating Decimal values with a large number of digits, where its performance is much better than the naive long multiplication method.

However, in TiDB’s code, the Karatsuba algorithm is not used to calculate Decimal multiplication; instead, the naive long multiplication method is used. This is because, in actual tests, the performance of the naive long multiplication method is already good enough, and its implementation is relatively simple, without introducing additional complexity. If you need to calculate Decimal values with a large number of digits, you might consider implementing the Karatsuba algorithm yourself and replacing the multiplication implementation in TiDB.

| username: TiDBer_IcYbdUP9 | Original post link

Hello~
In the second paragraph, you mentioned “In the TiDB code, a faster multiplication algorithm has been implemented for larger Decimal values.” Could you provide the specific code file?
And is there an explanation for the current implementation of the naive long multiplication?
Thanks.