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

Milos Stojko updated SPARK-61368:
---------------------------------
    Description: 
PR that adds this - [https://github.com/apache/spark/pull/60301]

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.
 * This can cause high instability in terms of memory, performance, and output 
accuracy: if the first sketch chosen is k=8, it will have high error bounds and 
use very little memory, but it's also possible that the very same query uses 
k=65000. Which k is chosen is non-deterministic (depends on first sketch 
encountered, which is undefined)

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}

  was:
PR that adds this - [https://github.com/apache/spark/pull/60301]

 

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}



> 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
>
> PR that adds this - [https://github.com/apache/spark/pull/60301]
> 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.
>  * This can cause high instability in terms of memory, performance, and 
> output accuracy: if the first sketch chosen is k=8, it will have high error 
> bounds and use very little memory, but it's also possible that the very same 
> query uses k=65000. Which k is chosen is non-deterministic (depends on first 
> sketch encountered, which is undefined)
> 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