Constructing a heavy hitter summary for query optimization. The heavy hitter summary is constructed by sampling each of multiple partitions of a dataset using a uniformed sampling rate. For each partition, performing a two-stage heavy hitter estimation process to determine whether an estimated frequency of a key of the sampled data units may be included in a partition-level heavy hitter summary. Constructing a partition-level heavy hitter summary for each partition of the dataset based on the keys determined via the two-stage process, and constructing a dataset-level heavy hitter summary based on the partition-level heavy hitter summary. The dataset-level heavy hitter summary may be used to optimize query trees.