alitrack

duckdb-luajit:DuckDB 大数相乘,精度悄悄没了

全文所有数字均为本机实测(Mac Studio M3 Ultra)。测试版本:DuckDB v1.5.5(稳定版)、v2.0.0-alpha49003(官方最新 alpha)、2.1 线 main 构建(alpha49002,自编译)。复现 SQL 附文末。
● ● ●

一、先说坑:你的 bignum 乘法,可能一直是 double

一句话结论:2.1.0 之前所有公开版本的 DuckDB 里,两个 BIGNUM 相乘静默返回 DOUBLE,不报错、不告警,精度直接丢。 DuckDB 从 1.4 起提供了 BIGNUM 类型,看起来大数运算齐活了:
SELECT '123456789012345678901234567890'::bignum * '987654321098765432109876543210'::bignum;
但在 v2.1.0 之前的所有公开版本里——包括你 curl install.duckdb.org | DUCKDB_VERSION=alpha bash 拿到的最新 alpha——这句 SQL 实际发生的是:
SELECT typeof('1'::bignum * '1'::bignum);
-- v1.5.5(稳定版)            → DOUBLE
-- v2.0.0-alpha49003(官方最新 alpha) → DOUBLE
-- 2.1 线 main 构建(自编译)    → BIGNUM   (修复在 main 上,尚未进入任何公开版本)
注意"静默"两个字:不报错、不告警,两个 bignum 相乘,结果悄悄变成 double。100 位数乘 100 位数,你拿到一个 1.2193263113702178e+59 ,精度早已经在某个看不见的地方丢了,而你的管线里没有任何信号告诉你这件事。分析型数据库里最危险的不是算错,是 算错了还显示得很正常 。 而且不止乘法。我在 1.5.5 和 2.0.0-alpha49003 上把四则全测了一遍:加法、减法返回 BIGNUM, 乘法、除法、取模三个全部静默降级 DOUBLE 。除法和取模这条坑,本文发布时(含最新 alpha)还踩得到。 (老读者可能记得我之前写过一篇 DuckDB没有的类型,我用Lua补上了 ,那篇演示的是 HUGEINT 装不下大数时的显式溢出,会报错;这次说的是 BIGNUM 类型明明存在、却悄悄降级,一个明枪一个暗箭,暗箭更疼。) 顺着摸下去还有第三个坑:原生 factorial 至今只支持 INTEGER → HUGEINT , factorial(10000::bignum) 在所有公开版本(含 2.1 线构建)里都是 Binder Error。任意精度类型给了你一半的算术,函数生态是空的。 ● ● ●

二、为什么原生路径慢:schoolbook 的天花板

2.1 线的原生乘法实现(main 分支 src/common/bignum.cpp )我逐行看过,L465 的注释自己就写着 "Schoolbook multiplication",核心是教科书式双重循环:
// result[i+j] += lhs[i] * rhs[j] + carry
它有三个"没有":
  1. 01 没有分治 。没有 Karatsuba、没有 Toom-Cook。复杂度钉死在 O(n²)。
  2. 02 没有操作数平衡 。schoolbook 对 a b 和 ba 完全对称,单次乘法交换左右零差别——听起来是"公平",但在多因子连乘场景里它意味着引擎 不会 主动帮你优化运算顺序。
  3. 03 没有连乘策略 。 1 2 3 ... N 这种链,引擎按它拿到的顺序老老实实从左往右乘:越乘越大的数 × 越乘越小的数,宽窄严重失衡,每一步的交叉项都被大的那个数拖着走。
● ● ●

三、红利一:10000! 的正确算法,是被浪费掉的 17 倍

大数连乘有个几乎免费的优化—— 按位宽配对 :
朴素:  ((((1×2)×3)×4)×5)...×N        巨型数 × 小数,步步失衡
配对:   (1×2)(3×4)(5×6)... → 两两结果再两两相乘 → ...
先让小数×小数(位宽平衡),结果再两两归并——就是大整数算法里 product tree 的思路。在同一个 GMP 实现内部实测 10000!:
方式 耗时(10000!,35660 位)
朴素左累加(大×小) 2.6 ms
两两归并平衡树 0.15 ms(GMP __gmpz_fac_ui ,内部为 product tree + 预计算奇数阶乘表)
同一算法内核,仅运算顺序不同, 17 倍 。位数越大,失衡的代价越接近平方级放大。 ● ● ●

四、红利二:让分析型数据库用上 GMP,只需要一行 SQL

原生 bignum 要追平 GMP,需要把乘法内核重写成分治算法,这是内核团队的事。但还有一条路今天就能走: 不重写内核,把成熟的大数库挂进来 。 DuckDB 的 duckdb-luajit 扩展(~1MB 自包含,零运行时依赖)内置 LuaJIT,可以 ffi.load 任意 C 库。GMP(GNU MP,三十多年工业级大数库,自动切换 Karatsuba/Toom 等算法)在 SQL 里长这样:
LOAD 'luajit';
SELECT luajit('local ffi = require("ffi")
ffi.cdef[[
  void __gmpz_init(void*); void __gmpz_clear(void*);
  int  __gmpz_set_str(void*, const char*, int);
  void __gmpz_mul(void*, void*, void*);
  char* __gmpz_get_str(char*, int, void*);
]]
local gmp = ffi.load("libgmp")
-- ... __gmpz_set_str / __gmpz_mul / __gmpz_get_str
return s');
热路径用注册式 UDF( luajit_module(mode:='compile') ,每会话只编译一次),冷查询直接匿名调用。数据不出库、逻辑可热更、无 Python UDF 的每行跨语言边界开销。 这套 FFI 范式的价值不止大数:任何"长尾格式 / 私有算法 / 冷门 C 库"都能在一条 SQL 里接进 DuckDB,不用等内核排期,不用编译 C++ 扩展。 ● ● ●

五、实测对拍:差距到底多大

同一台机器、同一个 2.1 线构建进程(1.5.5 的 luajit 扩展 -unsigned 直接加载进 2.1 CLI),同一组 case:
Case 原生 bignum (schoolbook) luajit + GMP 差距
单次 100 位×100 位 ~0.3 ms(含全查询开销) 纯乘法 0.005 ms 都亚毫秒,打平
1000 行×2 个被乘数 = 2000 次 100 位×100 位(另含每行 2 次加法防常量折叠) 1.38 µs/次 0.09 µs/次 ~15×
10000!(均为 35660 位,交叉验证一致) 朴素左累加 155 ms __gmpz_fac_ui 0.15 ms ~1000×
35660 位×35660 位(10000!²,71319 位) 38 ms* 0.13 ms(纯乘法,Karatsuba) ~290×
*原生 38ms 含 bignum→varchar 十进制转换,纯乘法占比未单独剥离,该行量级参考意义大于精确值。 两个机制要点,别只看倍数:
  • 位数小时差距不大 (100 位数都是亚毫秒级,schoolbook 的平方项还没涨起来)。大数库的红利在位数上去之后才指数级拉开,100 位约 15×,35660 位约 290×。
  • 10000! 的 1000× 混合了两个变量 (GMP 的平衡树策略 + Karatsuba),不能全归因于算法,但方向一致:原生路径"按给定顺序老实算",GMP 路径"自己挑最划算的算法和顺序"。
● ● ●

六、结论

  1. 01 **用 2.1.0 之前的 DuckDB 做 bignum 算术,先跑一句 typeof(a*b) **。如果显示 DOUBLE,你的"大数"一直是浮点数。顺手把 a/b 和 a%b 也测了,现在它们同样是 DOUBLE。
  2. 02 2.1 线的原生 bignum 从"没有"到"有",是重要的一步;但它目前是纯 schoolbook、无连乘优化、函数生态为空。
  3. 03 需要真任意精度(或任意长尾 C 库能力)的场景,duckdb-luajit + GMP 是当下可用的路径:一行 FFI,正确性由 GMP(三十多年生产验证)保证,性能由分治算法保证。
回到开头的场景:管线里没有任何信号告诉你精度丢了,这句话的反面才是本文的全部——信号要自己造,一行 typeof() 就是你的烟雾报警器;而当你真的需要跑 35660 位的大数时,别等内核排期,SQL 里一行 FFI 就能把三十年的工业级算力挂进来。

附录:复现

-- 坑的验证(1.5.5 / 2.0.0-alpha 上均复现;官方通道 curl install.duckdb.org | DUCKDB_VERSION=alpha bash 即可装到)
SELECT typeof('1'::bignum * '1'::bignum);   -- DOUBLE
SELECT typeof('1'::bignum / '1'::bignum);   -- DOUBLE(除法,同样静默)
SELECT typeof('1'::bignum % '1'::bignum);   -- DOUBLE(取模,同样静默)

-- GMP 单次乘法
LOAD 'luajit';
SELECT luajit('<上文 cdef + ffi.load("libgmp") 片段>');

-- 原生朴素 10000!
WITH RECURSIVE f(n, v) AS (
  SELECT 1, 1::bignum
  UNION ALL SELECT n+1, v * (n+1)::bigint::bignum FROM f WHERE n < 10000
) SELECT length(v::varchar) FROM f WHERE n = 10000;
-- → 35660,与 GMP __gmpz_fac_ui 结果位数一致
注:BIGNUM 乘法返回 BIGNUM 的修复目前在 DuckDB main 分支(2.1 线,release_version.txt = 2.1),尚未进入任何公开 release 或官方 alpha 通道;本文 2.1 侧数据来自 main 构建的自编译 CLI,需要复现该侧数字的话得自己从源码编译一版。
duckdb-luajit:自包含 LuaJIT UDF 扩展,MIT。libs 仓库覆盖长尾格式(DICOM/EXIF/私有 API),一条 SQL 安装。