[ 
https://issues.apache.org/jira/browse/SPARK-61529?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
 ]

ASF GitHub Bot updated SPARK-61529:
-----------------------------------
    Labels: pull-request-available sql  (was: sql)

> approx_count_distinct undercounts arrays with trailing NULL elements
> --------------------------------------------------------------------
>
>                 Key: SPARK-61529
>                 URL: https://issues.apache.org/jira/browse/SPARK-61529
>             Project: Spark
>          Issue Type: Bug
>          Components: SQL
>    Affects Versions: 4.3.0
>         Environment: {code}
> Spark: 4.3.0 
> Commit: 98bc0212c94705434471627068f41e374ccab143
> Java: OpenJDK 17.0.17
> OS: macOS 15.7.4
> Master: local[2]
> {code}
>            Reporter: Yibo Dong
>            Priority: Major
>              Labels: pull-request-available, sql
>
> {{approx_count_distinct}} substantially underestimates the cardinality of 
> arrays that differ only by a trailing NULL element.
> For example, {{[0]}} and {{[0, NULL]}} are distinct SQL array values but 
> receive the same {{xxhash64}} value.
> When constructing 100 pairs of {{[i]}} and {{[i, NULL]}}, the input contains 
> 200 distinct arrays. However, {{approx_count_distinct}} estimates only 99 at 
> the default relative standard deviation and 100 with {{relativeSD = 0.01}}.
> h2. Steps to Reproduce
> Save the following SQL as {{tmp.sql}}:
> {code}
> WITH ids AS (
> SELECT id FROM range(100)
> ),
> input AS (
> SELECT array(CAST(id AS INT)) AS a FROM ids
> UNION ALL
> SELECT array(CAST(id AS INT), CAST(NULL AS INT)) AS a FROM ids
> )
> SELECT
> count(DISTINCT a) AS exact_count,
> approx_count_distinct(a) AS default_estimate,
> approx_count_distinct(a, 0.01) AS tighter_estimate,
> count(DISTINCT xxhash64(a)) AS hash_count
> FROM input;
> {code}
> Execute:
> {code}
> spark-sql --master 'local[2]' 
> --conf spark.ui.enabled=false -f tmp.sql
> {code}
> h2. Expected Result
> The input contains 200 distinct arrays. Both approximate aggregates should 
> estimate a cardinality near 200, subject to their configured approximation 
> errors.
> The {{relativeSD = 0.01}} configuration specifies a relative standard 
> deviation of 1%, making an estimate near 100 especially inconsistent with the 
> input cardinality.
> h2. Actual Result
> {code}
> exact_count | default_estimate | tighter_estimate | hash_count
> ------------+------------------+------------------+-----------
> 200         | 99               | 100              | 100
> {code}
> Both approximate aggregates underestimate the distinct count by approximately 
> 50%, even with the tighter accuracy setting.
> The hash-count result also shows that the 200 distinct arrays produce only 
> 100 distinct {{xxhash64}} values. Each {{[i]}} and {{[i, NULL]}} pair has the 
> same hash, demonstrating a systematic collision pattern.



--
This message was sent by Atlassian Jira
(v10.3.26#10030026)

---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to