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

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

> kll_merge_agg without k: add a conf to take the lowest k among inputs that 
> have started compacting
> --------------------------------------------------------------------------------------------------
>
>                 Key: SPARK-61368
>                 URL: https://issues.apache.org/jira/browse/SPARK-61368
>             Project: Spark
>          Issue Type: Improvement
>          Components: SQL
>    Affects Versions: 5.0.0
>            Reporter: Milos Stojko
>            Priority: Major
>              Labels: pull-request-available
>
> Problem - all regarding {{kll_merge_agg_bigint}}, {{kll_merge_agg_float}} and 
> {{kll_merge_agg_double}} without k:
>  * The result takes the k of the first input sketch that the aggregate reads.
>  * A small exact sketch that comes first decides k for all inputs. For 
> example, a 3-row sketch with k = 8 makes the result k = 8, though the other 
> input compacted at k = 200. An exact sketch has no compaction error, so its k 
> says nothing about accuracy.
>  * The empty k = 200 sketch of an empty partition or an all-NULL group also 
> decides k when it comes first.
>  * The first input depends on the order in which the aggregate reads its 
> inputs. So the same query can return a different k, size and accuracy from 
> run to run.
>  * A first input with a large k keeps a large sketch after an input that 
> compacted at a smaller k. The DataSketches library already uses the smaller k 
> for the error bounds, so the extra size gives no extra accuracy.
> Proposal:
>  * Add a SQL conf, off by default: 
> {{spark.sql.function.kllMergeAgg.lowestCompactingK.enabled}}.
>  * When it is on, a merge without k returns the lowest k among the input 
> sketches that have started compacting (estimation mode). If no input has 
> started compacting, it takes the k of the first non-empty input. An explicit 
> k does not change.
>  * BigQuery's KLL merge uses the same rule: with different precisions, "the 
> precision is downgraded to the lowest precision involved in the merge", 
> unless the inputs are small enough to stay exact 
> ([KLL_QUANTILES.MERGE_PARTIAL|https://cloud.google.com/bigquery/docs/reference/standard-sql/kll_functions#kll_quantilesmerge_partial]).
>  * Implementation: when such an input arrives, rebuild the merge buffer at 
> its k, like {{HllUnionAgg}} rebuilds an empty union.
> Repro:
> With the conf off, this query returns K = 8. If you swap the two UNION ALL 
> branches, it returns K = 200. With the conf on, both orders return K = 200.
> {code:sql}
> SET spark.sql.function.kllMergeAgg.lowestCompactingK.enabled = true;
> SELECT regexp_extract(kll_sketch_to_string_bigint(kll_merge_agg_bigint(s)), 
> 'K +: ([0-9]+)', 1) AS k
> FROM (SELECT /*+ COALESCE(1) */ s
>       FROM (SELECT kll_sketch_agg_bigint(id, 8) AS s FROM range(3)
>             UNION ALL
>             SELECT kll_sketch_agg_bigint(id) AS s FROM range(100000)));
> {code}



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