[
https://issues.apache.org/jira/browse/SPARK-58731?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Wenchen Fan reassigned SPARK-58731:
-----------------------------------
Assignee: Joel Robin
> 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: 3.5.0, 4.1.0, 4.0.0, 4.2.0
> Reporter: Joel Robin
> Assignee: Joel Robin
> Priority: Major
> Labels: pull-request-available
>
> 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]
