David Mollitor created SPARK-59427:
--------------------------------------
Summary: Avoid a redundant map lookup in CollectFrequentItems
Key: SPARK-59427
URL: https://issues.apache.org/jira/browse/SPARK-59427
Project: Spark
Issue Type: Improvement
Components: SQL
Affects Versions: 4.1.0
Reporter: David Mollitor
h2. Summary
{{CollectFrequentItems}} (the {{collect_frequent_items}} aggregate behind
{{{}DataFrame.stat.freqItems{}}}) maintains an item -> count buffer
({{{}mutable.Map[Any, Long]{}}}) andupdates it once per input value via the
private {{add}} method (from both {{update}} and {{{}merge{}}}).
Its "already tracked" (hit) path was:
{code:scala}
if (map.contains(key)) {
map(key) += count
}
{code}
On a hit this performs three hash lookups on the same key: {{{}contains{}}},
then {{apply}} and
{{update}} (the desugaring of {{{}map(key) += count{}}}). Once the counter map
fills up – which is the steady state for a high-cardinality column – this runs
per input row.
h2. Change
Look the key up once and branch on the result:
{code:scala}
map.get(key) match {
case Some(existing) =>
map(key) = existing + count
case None =>
// unchanged: insert-if-room, else the bounded-counter eviction
...
}
{code}
The hit path now does two lookups ({{{}get{}}} + {{{}update{}}}) instead of
three. Two is the floor for
incrementing an existing key whose value is an immutable {{Long}} (a read plus
a write); the miss path is unchanged (one {{get}} in place of one
{{{}contains{}}}), and the eviction logic in the {{None }}branch is untouched.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
