Nondeterministic, incorrect result for symmetric aggregates

[colinmarc]

Describe the bug

Hi!

We're trying to support an unnamed BI tool on top of datafusion, which is fond of generating symmetric aggregates that look like this:

SELECT (
    COALESCE(
        (
                SUM(DISTINCT
                        (CAST(FLOOR(COALESCE( o_totalprice , 0) * 1000000) AS DECIMAL(65,0)))
                    +   _hex_to_bigint('x' || MD5( l_orderkey::varchar ))::DECIMAL(65,0)
                    *   18446744073709551616
                    +   _hex_to_bigint('x' || SUBSTR(MD5( l_orderkey::varchar ) , 17))::DECIMAL(65,0)
                )
            -   SUM(DISTINCT
                        _hex_to_bigint('x' || MD5( l_orderkey::varchar ))::DECIMAL(65,0)
                    *   18446744073709551616
                    +   _hex_to_bigint('x' || SUBSTR(MD5( l_orderkey::varchar ), 17))::DECIMAL(65,0)
                )
        ) / 1000000, 0) -- coalesce
) / COUNT(DISTINCT l_orderkey) as average_total
FROM orders left join lineitem on (l_orderkey = o_orderkey)

Here is some documentation from a totally different, 100% unrelated BI tool that explains why the above SQL is so cursed: https://cloud.google.com/looker/docs/best-practices/understanding-symmetric-aggregates

Roughly what it's doing is computing a really big sum twice, and subtracting it from itself. The numbers it's summing are hashes of a primary key. To generate big unique numbers, it's doing two md5 hashes and bitshifting the first to the left.

Unfortunately, the results from DF seem to be nondeterministic, and often negative. The issue seems to be with floating point math, related to the literal 18446744073709551616 (2^64). The BI tool seems to be expecting that the literal will be typed as a DECIMAL(65, 0), since the left hand side of the multiplication is also DECIMAL(65, 0), but DF is picking that up as a float:

<snip> AS Decimal256(65, 0)) * Float64(18446744073709552000) <snip>

This is especially weird because the literal in the plan is a completely different number. 😕

To aid in debugging, I've included a small reproducer here: https://github.com/colinmarc/df-symmetric-aggregate

Note that if you change the literal in the generated SQL to 18446744073709551615 (2^64 - 1), it gets picked up as a UInt64, which is still odd, but works, produces the correct value, and is deterministic.

Thanks in advance!

To Reproduce

git clone https://github.com/colinmarc/df-symmetric-aggregate
cd df-symmetric-aggregate
cargo test

[alamb]

rtunately, the results from DF seem to be nondeterministic, and often negative. The issue seems to be with floating point math, related to the literal 18446744073709551616 (2^64).

Sounds like an overflow issue to me

I wonder if the sum/distinct is being done with floating point arithmetic internally. I vaguely remember this has come up before

[drin]

I just want to note that I also tried the following syntax around the literal value:

(DECIMAL '18446744073709551616')::DECIMAL(65)

and I see this in the decoded logical plan:

CAST(CAST(Utf8("18446744073709551616") AS Decimal128(38, 10)) AS Decimal256(65, 0))

which still ends up with similar issues. I am pretty sure that if the literal were parsed to an integer rather than a float (e.g. DECIMAL128(38, 0)) this approach would also solve the issue.

I looked at #13806 and the source but couldn't figure out where parsing from a typical string to a bigdecimal then to a decimal128 or decimal256 is implemented

[drin]

Sounds like an overflow issue to me

then would functional behavior when using 2^64 - 1 (18446744073709551615) be an artifact of consistent overflow? and the use of 18446744073709551616 somehow results in inconsistent or inexact overflow?

[colinmarc]

Yeah, I also think it sounds like overflow, but it's not. Floating point math seems like the only thing that would be ordering dependent here.

[Omega359]

The initial string -> number conversion I think is handled in the sql module -

datafusion/datafusion/sql/src/expr/value.rs

Line 72 in 0f83c1d

pub(super) fn parse_sql_number(

The max u64 value in Rust is 18446744073709551615 which is being cast to uint64 in the function referenced above. Otherwise, it's being converted to float unless you have the SqlParserOptions.parse_float_as_decimal option set to true (default is false)

As to why it's non-deterministic with float, 🤷🏻‍♂️ If there is type coercion happening between the Decimal256(65, 0)) type and Float64 it's probably somewhere in the binary type converter

[colinmarc]

@Omega359 thanks, that's really helpful!

I think I was intuitively expected literals to be untyped, or to match the type of the expression to the left of the *. (I think the BI tool is also expecting that.)

[colinmarc]

Btw, enabling that option on the reproducer results in:

Error during planning: Cannot coerce arithmetic expression Decimal256(65, 0) * Decimal128(20, 0) to valid types

Am I correct in assuming that DF would like to support that? We could make a PR for that if so.

[Omega359]

It absolutely should work! A PR that fixes this would be definitely welcome

[colinmarc]

Even better - running the repro against main (0ffc433) works with datafusion.sql.parse_float_as_decimal! So I think we can close this.