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]