approx_percentile_cont return wrong result when scan multi parquet files.

[Ted-Jiang]

Describe the bug
I found in our env approx_percentile_cont return different result when running the same query.

❯ create external table line STORED AS PARQUET LOCATION '/Users/yangjiang/test-data/tpch-1g-oneFile' ;

❯  select o_orderstatus, approx_percentile_cont(o_totalprice, 0.5) from order group by o_orderstatus  order by 1 limit 5 ;

❯ create external table order stored as parquet location '/Users/yangjiang/test-data/tpch-1g/orders';
0 rows in set. Query took 0.043 seconds.
❯   select o_orderstatus, approx_percentile_cont(o_totalprice, 0.5) from order group by o_orderstatus  order by 1 limit 5 ;
+---------------+-------------------------------------------------------+
| o_orderstatus | APPROXPERCENTILECONT(order.o_totalprice,Float64(0.5)) |
+---------------+-------------------------------------------------------+
| F             | 143401.16095215187                                    |
| O             | 142955.62738411513                                    |
| P             | 181527.60330546615                                    |
+---------------+-------------------------------------------------------+
3 rows in set. Query took 0.719 seconds.
❯   select o_orderstatus, approx_percentile_cont(o_totalprice, 0.5) from order group by o_orderstatus  order by 1 limit 5;

+---------------+-------------------------------------------------------+
| o_orderstatus | APPROXPERCENTILECONT(order.o_totalprice,Float64(0.5)) |
+---------------+-------------------------------------------------------+
| F             | 143281.01048942824                                    |
| O             | 143237.76755123492                                    |
| P             | 181240.3599115534                                     |
+---------------+-------------------------------------------------------+
3 rows in set. Query took 0.684 seconds.
❯   select o_orderstatus, approx_percentile_cont(o_totalprice, 0.5) from order group by o_orderstatus  order by 1 limit 5;

+---------------+-------------------------------------------------------+
| o_orderstatus | APPROXPERCENTILECONT(order.o_totalprice,Float64(0.5)) |
+---------------+-------------------------------------------------------+
| F             | 143462.16658943877                                    |
| O             | 142949.42279252067                                    |
| P             | 181449.91485153142                                    |
+---------------+-------------------------------------------------------+
3 rows in set. Query took 0.595 seconds.
❯   select o_orderstatus, approx_percentile_cont(o_totalprice, 0.5) from order group by o_orderstatus  order by 1 limit 5;

+---------------+-------------------------------------------------------+
| o_orderstatus | APPROXPERCENTILECONT(order.o_totalprice,Float64(0.5)) |
+---------------+-------------------------------------------------------+
| F             | 143033.71820461476                                    |
| O             | 143033.13028498186                                    |
| P             | 181449.54772100857                                    |
+---------------+-------------------------------------------------------+
3 rows in set. Query took 0.705 seconds.
❯


 pwd
/Users/yangjiang/test-data/tpch-1g/orders
yangjiang@LM-SHC-15009782 orders % ll
total 123520
-rw-r--r--  1 yangjiang  110538165     0B May 10 11:58 _SUCCESS
-rw-r--r--  1 yangjiang  110538165    11M May 10 11:58 part-00000-e87df013-b3f8-493f-93c2-3da94f34e357-c000.snappy.parquet
-rw-r--r--  1 yangjiang  110538165    11M May 10 11:58 part-00001-e87df013-b3f8-493f-93c2-3da94f34e357-c000.snappy.parquet
-rw-r--r--  1 yangjiang  110538165    11M May 10 11:58 part-00002-e87df013-b3f8-493f-93c2-3da94f34e357-c000.snappy.parquet
-rw-r--r--  1 yangjiang  110538165    11M May 10 11:58 part-00003-e87df013-b3f8-493f-93c2-3da94f34e357-c000.snappy.parquet
-rw-r--r--  1 yangjiang  110538165    11M May 10 11:58 part-00004-e87df013-b3f8-493f-93c2-3da94f34e357-c000.snappy.parquet
yangjiang@LM-SHC-15009782 orders %

To Reproduce
Steps to reproduce the behavior:

Expected behavior
A clear and concise description of what you expected to happen.

Additional context
Add any other context about the problem here.

[Ted-Jiang]

Interesting when create table with the same data in one file the results are same. 🤔

pwd
/Users/yangjiang/test-data/tpch-1g-oneFile/orders
yangjiang@LM-SHC-15009782 orders % ll
total 104112
-rw-r--r--  1 yangjiang  110538165     0B Mar 24 16:13 _SUCCESS
-rw-r--r--  1 yangjiang  110538165    51M Mar 24 16:13 part-00000-0e58b960-37a0-44c9-8561-53f0c32cf038-c000.snappy.parquet


     Running `target/debug/datafusion-cli`
DataFusion CLI v10.0.0
❯ create external table order STORED AS PARQUET LOCATION '/Users/yangjiang/test-data/tpch-1g-oneFile/orders' ;
0 rows in set. Query took 0.007 seconds.
❯  select o_orderstatus, approx_percentile_cont(o_totalprice, 0.5) from order group by o_orderstatus  order by 1 limit 5 ;
+---------------+-------------------------------------------------------+
| o_orderstatus | APPROXPERCENTILECONT(order.o_totalprice,Float64(0.5)) |
+---------------+-------------------------------------------------------+
| F             | 143180.72188702895                                    |
| O             | 143193.2377466576                                     |
| P             | 181378.70468729443                                    |
+---------------+-------------------------------------------------------+
3 rows in set. Query took 1.190 seconds.
❯  select o_orderstatus, approx_percentile_cont(o_totalprice, 0.5) from order group by o_orderstatus  order by 1 limit 5 ;
+---------------+-------------------------------------------------------+
| o_orderstatus | APPROXPERCENTILECONT(order.o_totalprice,Float64(0.5)) |
+---------------+-------------------------------------------------------+
| F             | 143180.72188702895                                    |
| O             | 143193.2377466576                                     |
| P             | 181378.70468729443                                    |
+---------------+-------------------------------------------------------+
3 rows in set. Query took 1.127 seconds.
❯  select o_orderstatus, approx_percentile_cont(o_totalprice, 0.5) from order group by o_orderstatus  order by 1 limit 5 ;
+---------------+-------------------------------------------------------+
| o_orderstatus | APPROXPERCENTILECONT(order.o_totalprice,Float64(0.5)) |
+---------------+-------------------------------------------------------+
| F             | 143180.72188702895                                    |
| O             | 143193.2377466576                                     |
| P             | 181378.70468729443                                    |
+---------------+-------------------------------------------------------+
3 rows in set. Query took 1.128 seconds.
❯  select o_orderstatus, approx_percentile_cont(o_totalprice, 0.5) from order group by o_orderstatus  order by 1 limit 5 ;
+---------------+-------------------------------------------------------+
| o_orderstatus | APPROXPERCENTILECONT(order.o_totalprice,Float64(0.5)) |
+---------------+-------------------------------------------------------+
| F             | 143180.72188702895                                    |
| O             | 143193.2377466576                                     |
| P             | 181378.70468729443                                    |
+---------------+-------------------------------------------------------+
3 rows in set. Query took 1.123 seconds.
❯

[Ted-Jiang]

@alamb @andygrove PTAL

[Ted-Jiang]

and i repalaced 'approx_percentile_cont' with 'sum' and 'count(distinct)' , it works well.

[Ted-Jiang]

approx_distinct also works well 🤔

[alamb]

cc @domodwyer and @realno who did some work in this area

[domodwyer]

I wonder if this is something to do with serialisation/deserialisation of the TDigest state:

https://github.com/apache/arrow-datafusion/blob/929eb6d860fb60ba994b24397ad3c3eb7d839cdf/datafusion/physical-expr/src/aggregate/tdigest.rs#L577-L670

This is used when merging batches (Accumulator::merge_batch):

https://github.com/apache/arrow-datafusion/blob/929eb6d860fb60ba994b24397ad3c3eb7d839cdf/datafusion/physical-expr/src/aggregate/approx_percentile_cont.rs#L410

I know some changes were made to the approx_percentile_cont to support other parameters, perhaps some aren't carried over? I can take a look if this doesn't ring a bell with anyone 👍

[alamb]

I wonder if this could be related to "floating point error" error accumulation -- namely that floating point operations are approximations and can produce different values if executed in different order.

Given operations like repartitoning and thread ordering, I don't think there is any guarantee that a particular operator will see the same data in the same order if the same query is run more than once 🤔

[Ted-Jiang]

I have found after implement #3146 (comment)

select o_orderstatus, approx_percentile_cont(o_totalprice, 0.5, 100000) from order group by o_orderstatus  order by 1 limit 5 ;
+---------------+---------------------------------------------------------------------+
| o_orderstatus | APPROXPERCENTILECONT(order.o_totalprice,Float64(0.5),Int64(100000)) |
+---------------+---------------------------------------------------------------------+
| F             | 143289.44656666665                                                  |
| O             | 143178.60241111112                                                  |
| P             | 181459.53                                                           |
+---------------+---------------------------------------------------------------------+
3 rows in set. Query took 2.573 seconds.
❯ select o_orderstatus, approx_percentile_cont(o_totalprice, 0.5, 100000) from order group by o_orderstatus  order by 1 limit 5 ;
+---------------+---------------------------------------------------------------------+
| o_orderstatus | APPROXPERCENTILECONT(order.o_totalprice,Float64(0.5),Int64(100000)) |
+---------------+---------------------------------------------------------------------+
| F             | 143289.44656666665                                                  |
| O             | 143178.60241111112                                                  |
| P             | 181459.53                                                           |
+---------------+---------------------------------------------------------------------+
3 rows in set. Query took 2.497 seconds.
❯ select o_orderstatus, approx_percentile_cont(o_totalprice, 0.5, 100000) from order group by o_orderstatus  order by 1 limit 5 ;
+---------------+---------------------------------------------------------------------+
| o_orderstatus | APPROXPERCENTILECONT(order.o_totalprice,Float64(0.5),Int64(100000)) |
+---------------+---------------------------------------------------------------------+
| F             | 143289.44656666665                                                  |
| O             | 143178.60241111112                                                  |
| P             | 181459.53                                                           |
+---------------+---------------------------------------------------------------------+
3 rows in set. Query took 2.633 seconds.

it not change when centroids numbers are 100000🤔

❯ select count(*) from order;
+-----------------+
| COUNT(UInt8(1)) |
+-----------------+
| 1499999         |
+-----------------+
1 row in set. Query took 0.130 seconds.

[Ted-Jiang]

Given operations like repartitoning and thread ordering, I don't think there is any guarantee that a particular operator will see the same data in the same order if the same query is run more than once

Agree! this only happen in multi files which includes different partition finish order. I think T-digest merge in final aggregation is like "floating point error" different input order return different result.