Yibo Dong created SPARK-61529:
---------------------------------

             Summary: 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


{{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