Milos Stojko created SPARK-61368:
------------------------------------

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


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