Repository navigation
Description
What is the problem the feature request solves?
Decimal / and div run spark_decimal_div_internal. Integer div runs it too, because the serde casts integer operands to Decimal(19, 0) (CometIntegralDivide). When no rescaled operand passes 38 digits, the kernel runs its i128 branch (L147-L173), and integer div always does. Per row, that branch scales the dividend by one more power of ten than the result needs, divides by the divisor, and divides the quotient by 10. The last division drops the extra digit, rounding half away from zero for / and truncating for div.
Neither aarch64 nor x86_64 has a 128-bit divide instruction. In an aarch64 release build, the closure of the i128 branch calls __divti3 twice per row, once for the literal 10. The BigInt branch (L114-L145) has the same structure, with two BigInt divisions per row.
Describe the potential solution
Compute the quotient at the result's scale, without the extra digit, so that each row divides once.
- For
div, truncating twice is the same as truncating once:trunc(trunc(10a / b) / 10) = trunc(a / b). The division by 10 can go without changing any result. - For
/, compute the remainderrem = a - q * bfrom the truncated quotientq. Because|q * b| <= |a|, the product can't overflow. Roundqaway from zero when|rem| >= |b| - |rem|. That is the test2 * |rem| >= |b|without the overflow of2 * |rem|. It rounds the same rows as today's(q10 +/- 5) / 10, because both round the exact quotient half away from zero. perf: divide once per row inpmodanddiv_round_half_up#7690 makes the same change indiv_round_half_up. - The exponents lose the extra digit:
l_exp = (s2 + s3) - s1andr_exp = s1 - (s2 + s3), each saturating at zero. The precision check that picks theBigIntbranch then uses the new exponents. When the dividend is scaled, its precision drops by one, so some inputs move from theBigIntbranch to thei128branch. When the divisor is scaled, its precision rises by one, so some inputs move the other way. Both branches compute the same quotient, so this changes which branch runs, not the result. - For integer
div, all three scales are 0, so neither operand is scaled. A further step could divide ini64, which is a hardware divide, after a per-batch check that both operands fit.i64::MIN div -1stays on thei128path. The check is needed because aDecimal(19, 0)that comes from a decimal column can hold values up to 10^19 - 1.
Tests should compare the new kernel with today's on both branches. They should cover negative operands, quotients exactly halfway between two values at the result scale, scale combinations where either exponent is zero, and operands at the 38-digit bound on each side of the branch choice.
benches/decimal_div.rs measures / and div on Decimal(10, 4) and Decimal(10, 3). Its decimal_integral_div case passes Decimal128(10, 4) as the return type, while the serde sends scale 0 for div. Could it get a case with that return type, and one for integer div on Decimal(19, 0)?
Additional context
apache/arrow-rs#11421 adds precomputed divisors to arrow-buffer. They help this kernel only when the divisor is a scalar, such as x div 7 or price / 100, and the kernel expands a scalar to an array today (L87-L96). DivisorI64 from apache/arrow-rs#11467 is on arrow-rs main, and apache/arrow-rs#12232 adds DivisorI128. The changes above don't depend on them.
Activity