Approximate query processing using multiple samples
AssigneeMicrosoft Corporation
InventorsSurajit Chaudhuri, Gautam Das, Vivek Narasayya
Life of this patent
Estimating the term…
Abstract
A method for estimating the result of an aggregation query on a database using multiple sample tables. A given workload is divided into a set of workload partitions that include queries from the workload. A set of sample tables are constructed. Samples for each sample table are selected to reduce an estimation error for one of the partitions of queries. The most appropriate sample table in the set of sample tables is identified for a given query. The given query is executed on the most appropriate sample table and an estimated result for the given query is returned.
Claims48
A method for estimating the result of an aggregation query on a database wherein the database has data records arranged in one or more database tables, and wherein the database has a given workload comprising a set of queries, the method comprising:
- a) dividing said given workload into a set of workload partitions including queries from said workload;
- b) constructing a set of sample tables wherein samples of each sample table are selected to reduce an estimation error for one of said workload partitions;
- c) identifying a most appropriate sample table in said set of sample tables for a given aggregate query;
- d) executing the given aggregate query on the most appropriate sample table;
- and
- e) returning an estimated result for the given aggregate query.
A method for estimating the result of an aggregation query on a database wherein the database has data records arranged in a database table, and wherein the database has a given workload comprising a set of queries, the method comprising:
- a) dividing said workload into a set of workload partitions including queries from said workload;
- b) stratifying said database into regions of importance to the workload partitions in said set of partitions;
- c) constructing a set of sample tables wherein a sample table corresponds to a workload partition and samples in the sample table are allocated according to an importance of a region of said database that corresponds the sample table;
- d) identifying a most appropriate sample table in said set of sample tables for a given incoming query;
- e) executing the given query on the most appropriate sample table.
A method for estimating the result of an aggregation query on a database wherein the database has data records arranged in one or more database tables, and wherein the database has a given workload comprising a set of queries, the method comprising:
- a) determining an appropriate number of sample tables;
- b) determining an appropriate size for said sample tables;
- c) dividing said given workload into a number of workload partitions that corresponds to the appropriate number of sample tables, said workload being divided based on a similarity between queries in said workload;
- d) calculating a centroid query for each workload partition;
- e) stratifying said database into regions of varying importance to a workload partition for each partition in said set of partitions;
- f) constructing a set of sample tables wherein a sample table corresponds to a partition and samples in the sample table are allocated according to importance of a region of said one or more database tables to the partition that corresponds the sample table;
- g) comparing a given query to the centroid queries of the partitions;
- h) selecting a most appropriate sample table that corresponds to a partition having a centroid query that is most similar to said given query;
- i) replacing references in the given query to the database table with references to the most appropriate sample table;
- j) scaling aggregate expressions in said given query;
- and
- k) executing the query on the most appropriate sample table.
A computer readable medium having computer executable instructions stored thereon for performing a method for estimating the result of an aggregation query on a database wherein the database has data records arranged in one or more database tables, and wherein the database has a given workload comprising a set of queries, the method comprising:
- a) dividing said given workload into a set of workload partitions including queries from said workload;
- b) constructing a set of sample tables wherein samples of each sample table are selected to reduce an estimation error for one of said partitions of queries;
- c) identifying a most appropriate sample table in said set of sample tables for a given query;
- d) executing the given query on the most appropriate sample table;
- and
- e) returning an estimated result for the given query.
A computer readable medium having computer executable instructions stored thereon for performing a method for estimating the result of an aggregation query on a database wherein the database has data records arranged in one or more database tables, and wherein the database has a given workload comprising a set of queries, the method comprising:
- a) dividing said workload into a set of workload partitions including queries from said workload;
- b) stratifying said database into regions of importance to the workload partitions in said set of partitions;
- c) constructing a set of sample tables wherein a sample table corresponds to a workload partition and samples in the sample table are allocated according to an importance of a region of said database that corresponds the sample table;
- d) identifying a most appropriate sample table in said set of sample tables for a given incoming query;
- e) executing the given query on the most appropriate sample table.
A method for estimating the result of an aggregation query on a database wherein the database has data records arranged in one or more database tables, and wherein the database has a given workload comprising a set of queries, the method comprising:
- a) determining an appropriate number of sample tables;
- b) determining an appropriate size for said sample tables;
- c) dividing said given workload into a number of workload partitions that corresponds to the appropriate number of sample tables, said workload being divided based on a similarity between queries in said workload;
- d) calculating a centroid query for each workload partition;
- e) stratifying said database table into regions of varying importance to a workload partition for each partition in said set of partitions;
- f) constructing a set of sample tables wherein a sample table corresponds to a partition and samples in the sample table are allocated according to importance of a region of said one or more database tables to the partition that corresponds the sample table;
- g) comparing a given query to the centroid queries of the partitions;
- h) selecting a most appropriate sample table that corresponds to a partition having a centroid query that is most similar to said given query;
- i) replacing references in the given query to the database table with references to the most appropriate sample table;
- j) scaling aggregate expressions in said given query;
- and
- k) executing the query on the most appropriate sample table.
Dependencies are inferred from the claim text.