[HIVE-22960] Approximate TopN Key Operator

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Won't Fix
• Fix Version/s: 4.0.0-alpha-2
• Component/s: Hive
• Target Version/s: 4.0.0
• Assignee: Attila Magyar
• Reporter: Attila Magyar
• Created: 02/Mar/20 16:11
• Updated: 16/Nov/22 13:50
• Resolved: 12/Jul/21 14:38

Description

"Different from other operators, top n operator demonstrates the notable “long tail” characteristics which makes it distinct from other operators like join, group by and etc. will saturate very quickly. Update is pretty frequent at the beginning and then diverges to a very slow update frequently.

The approximation can be implemented in two ways: one way is to stop the array/heap update after certain percentage of the data is been read, for example, 10% or 20%, if we know the table size. The other way is to set a frequency threshold of the array/heap update. After the threshold is met, then stop the top n processing"

rzhappy

Y: number of updates in every 100msec