Joel Robin created SPARK-58731:
----------------------------------
Summary: hll_union_agg cannot re-merge the empty sketch it
produces for a group with no non-NULL input
Key: SPARK-58731
URL: https://issues.apache.org/jira/browse/SPARK-58731
Project: Spark
Issue Type: Bug
Components: SQL
Affects Versions: 4.2.0, 4.0.0, 4.1.0, 3.5.0
Reporter: Joel Robin
h2. Problem
{{hll_union_agg}} takes no {{lgConfigK}} argument; it infers precision from its
input sketches. For a group with no non-NULL sketch it has nothing to infer
from and emits an empty sketch at the DataSketches default
{{{}lgConfigK=12{}}}. Under default settings {{hll_union_agg}} then refuses to
merge that sketch against sketches of any other {{lgConfigK}} – so the function
produces a value that the function itself cannot read back.
The rejection is unnecessary. The sketch is empty: it holds no coupons, so
unioning it cannot lose information at any {{{}lgConfigK{}}}. DataSketches has
no objection – {{new Union(15).update(<empty lgConfigK=12 sketch>)}} returns
{{lgConfigK=15}} with the estimate intact. Only Spark's own check objects,
because it compares header values without regard to whether either sketch
carries data.
h2. Reproduction
{code:sql}
create or replace temp view stored_sketches as
with sketches as (
select 'has_data' as grp, hll_sketch_agg(cast(id as string), 15) as sketch
from (select explode(sequence(1, 1000)) as id)
union all
select 'all_null' as grp, cast(null as binary) as sketch
)
select grp, hll_union_agg(sketch) as sketch from sketches group by grp;
-- byte 3 of the serialized sketch is lgConfigK; 0x0F = 15, 0x0C = 12
select grp, substring(hex(sketch), 7, 2) as lg_config_k from stored_sketches;
-- all_null -> 0C <- emitted by hll_union_agg itself
-- has_data -> 0F
select hll_sketch_estimate(hll_union_agg(sketch)) from stored_sketches;
{code}
{noformat}
[HLL_UNION_DIFFERENT_LG_K] Sketches have different `lgConfigK` values: 12 and
15.
Set the `allowDifferentLgConfigK` parameter to true to call `hll_union_agg` with
different `lgConfigK` values. SQLSTATE: 22000
{noformat}
The scalar {{hll_union}} fails the same way:
{code:sql}
select hll_sketch_estimate(hll_union(a.sketch, b.sketch))
from (select sketch from stored_sketches where grp = 'all_null') a,
(select sketch from stored_sketches where grp = 'has_data') b;
{code}
h2. Impact
# A table that mixes an empty default-precision sketch with
explicitly-configured sketches cannot be rolled up under default settings, and
the empty sketch was produced by {{hll_union_agg}} itself. #
{{allowDifferentLgConfigK => true}} is not a sound workaround for the
aggregate. The buffer takes its {{lgConfigK}} from whichever non-NULL sketch it
happens to see first, so the result depends on row and partition arrival order.
Measured at 4.2.0 over the data above (true distinct count 1000):
{{lgConfigK=15}} and estimate 1000 when the populated sketch arrives first,
versus {{lgConfigK=12}} and estimates of 1005, 1001 or 998 depending on
execution path when the empty sketch arrives first. # The scalar {{hll_union}}
is worse: it builds {{{}new Union(Math.min(k1, k2)){}}}, so with
{{allowDifferentLgConfigK => true}} an empty {{lgConfigK=12}} sketch
deterministically drags a populated {{lgConfigK=15}} sketch down to 12, in both
argument orders.
h2. Root cause
In {{HllUnionAgg}}
({{{}sql/catalyst/.../expressions/aggregate/datasketchesAggregates.scala{}}}):
* {{createAggregationBuffer()}} returns {{{}None{}}};
* {{update()}} instantiates the {{Union}} from the first non-NULL sketch's
{{{}lgConfigK{}}};
* with no non-NULL input, {{eval()}} reaches {{{}case None => new
Union().toUpdatableByteArray{}}},
and the no-argument {{Union()}} constructor uses {{HllSketch.DEFAULT_LG_K}} =
12.
All three {{None}} branches carry the comment {{{}// unclear if these scenarios
can ever occur{}}}, so this path was believed unreachable. It is reached by any
{{GROUP BY}} in which one group's sketches are all NULL, and by a global
aggregate over zero rows.
Null handling was discussed on the original PR (apache/spark#40615) but only in
terms of the estimate being 0; the serialized {{lgConfigK}} of the empty result
was never considered. The same class of problem was raised there for register
size – "The union operation does not take a register size as input ... the
DataSketches default choice will be used ... problematic in terms of user
expectations" – and fixed in apache/spark#41021 by pinning {{{}HLL_8{}}}. The
{{lgConfigK}} analogue was missed.
{{hll_sketch_agg}} is unaffected because it takes {{lgConfigK}} as an argument
and builds its buffer eagerly; given all-NULL input it returns an empty sketch
at the requested precision.
h2. Fix
An empty sketch carries no precision, so it should neither take part in the
{{lgConfigK}} compatibility check nor decide the result's {{{}lgConfigK{}}}:
* {{{}HllUnionAgg{}}}: route {{update}} and {{merge}} through a single helper
that skips the check when either side is empty, and re-seeds an empty {{Union}}
at the {{lgConfigK}} of the first sketch that carries data. This also removes
the order dependence in impact #2.
* Scalar {{{}HllUnion{}}}: apply the same exemption, and use the non-empty
sketch's {{lgConfigK}} rather than {{Math.min}} when exactly one input is empty.
This is backward compatible: no signature change, no nullability change, no new
config. Queries that work today continue to work; queries that fail today start
working.
h2. Scope
This does not change the {{lgConfigK}} reported for the all-NULL group itself,
which remains 12 – the aggregate has no precision to report. It makes that
sketch harmless to merge, and is the only change that helps sketches already
persisted at the default precision.
Letting the caller choose the precision for an empty group requires an optional
{{lgConfigK}} parameter on {{{}hll_union_agg{}}}, aligning it with
{{theta_union_agg}} (added in 4.1.0), which takes {{lgNomEntries}} and builds
its buffer eagerly. That is a separate API change and will be filed as a
follow-up; it is not required to fix the failure above, and would not repair
already-written sketches.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
