US 2019/0095487 A1Published application

Building heavy hitter summary for query optimization

AssigneeMicrosoft Technology Licensing, LLC

InventorsWangchao LE, Yongchul KWON, Marc Todd FRIEDMAN

Life of this patent

Estimating the term…

Loading patent…

Abstract

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.

Claims20

Dependent claims

A computing system comprising:

one or more processors;
and
one or more computer-readable media having thereon
computer-executable instructions that are structured such that, when executed by the one or more processors, cause the computing system to perform a method for building a heavy hitter summary for query optimization:
sampling each of a plurality of partitions of a dataset, wherein each of the plurality of partitions of the dataset comprises a plurality of data units, and each of the plurality of data units comprises a key;
for each of the plurality of partitions of the query dataset,
performing a two-stage heavy hitter estimation process comprising:
a first stage in which, for each of the sampled data units, determine whether an estimated frequency of a key of the sampled data units meets a first stage frequency threshold;
and
a second stage in which, for each of the keys of the sampled data units that has not been determined to satisfy the first stage frequency threshold, determine whether an estimated frequency of a key of the sampled data units meets a second stage frequency threshold;
and
constructing a partition-level heavy hitter summary for the corresponding partition of the dataset, wherein the partition-level heavy hitter summary comprises all the keys for the data units in the corresponding partition that satisfy the first stage frequency threshold in the first stage, and all the keys for the data units in the corresponding partition that satisfy the second stage frequency threshold in the second stage.

9 more elements

A method for building a heavy hitter summary for query optimization, using a computing device, the method comprising:

sampling each of a plurality of partitions of a dataset, wherein each of the plurality of partitions of the dataset comprises a plurality of data units, and each of the plurality of data units comprises a key;
for each of the plurality of partitions of the query dataset,
performing a two-stage heavy hitter estimation process comprising:
a first stage in which, for each of the sampled data units, determine whether an estimated frequency of a key of the sampled data units meets a first stage frequency threshold;
and
a second stage in which, for each of the keys of the sampled data units that has not been determined to satisfy the first stage frequency threshold, determine whether an estimated frequency of a key of the sampled data units meets a second stage frequency threshold;
and
constructing a partition-level heavy hitter summary for the corresponding partition of the dataset, wherein the partition-level heavy hitter summary comprises all the keys for the data units in the corresponding partition that satisfy the first stage frequency threshold in the first stage, and all the keys for the data units in the corresponding partition that satisfy the second stage frequency threshold in the second stage.

5 more elements

Dependencies are inferred from the claim text.