Optimization based method for estimating the results of aggregate queries

A method that estimates the result of a query on a database wherein the database has data records arranged in tables, and wherein the database has a given workload comprising a set of queries that has been executed on the database, comprising:

• a) deriving an expected workload based on the given workload;
• b) constructing a sample of a table by partitioning the data records into regions based on the queries in the expected workload such that no query in the expected workload selects a proper subset of any region, expressing the estimation error as a function of a number of records selected per region, and allocating a number of records to each region in a manner that minimizes the estimation error;
• c) directing the query to access the sample;
• d) executing the query on the sample;
• and
• e) returning an estimated query result, wherein the sample is constructed by partitioning rows of the table into regions based on the queries in the expected workload and selecting records from the regions in a manner that minimizes estimation error over the expected workload, wherein records are selected from the regions by expressing the estimation error as a function of the number of records allocated to each region and allocating the number of allocated records to minimize the estimation error, rounding the number of records allocated to each region down to the nearest integer, accumulating remaining fractional values, and redistributing the accumulated fractional values to regions such that the estimation error is impacted the least.

A computer readable medium containing computer executable instructions for estimating the result of an aggregation query on a database wherein the database has data records arranged in tables, and wherein the database has a given workload comprising a set of queries that has been executed on the database, the instructions comprising:

• a) deriving an expected workload based on the given workload;
• b) constructing a sample by data records for inclusion in the sample such that an estimation error is minimized when the selected data records are acted upon by Queries in the expected workload to return estimated results;
• c) directing the query to access the sample;
• d) executing the query on the sample;
• and
• e) returning an estimated query result, wherein the sample is constructed by partitioning rows of the table into regions based on the queries in the expected workload and selecting records from the regions in a manner that minimizes estimation error over the expected workload, wherein records are selected from the regions by expressing the estimation error as a function of the number of records allocated to each region and allocating the number of allocated records to minimize the estimation error, rounding the number of records allocated to each region down to the nearest integer, accumulating remaining fractional values, and redistributing the accumulated fractional values to regions such that the estimation error is impacted the least.

An apparatus for estimating the result of an aggregation query on a database wherein the database has data records arranged in tables, and wherein the database has a given workload comprising a set of queries that has been executed on the database, the apparatus comprising:

• a) an expected workload derivation module that derives an expected workload based on the given workload;
• b) a sample constructor that selects data records for inclusion in the sample such that an estimation error is minimized when the selected data records are acted upon by queries in the expected workload to return estimated results;
• c) a query redirector that directs the query to access the sample;
• and
• d) a query estimator that returns an estimated query result, wherein the sample is constructed by partitioning rows of the table into regions based on the queries in the expected workload and selecting records from the regions in a manner that minimizes estimation error over the expected workload, wherein records are selected from the regions by expressing the estimation error as a function of the number of records allocated to each region and allocating the number of allocated records to minimize the estimation error, rounding the number of records allocated to each region down to the nearest integer, accumulating remaining fractional values, and redistributing the accumulated fractional values to regions such that the estimation error is impacted the least.

A method that estimates the result of an aggregation query on a database wherein the database has data records arranged in tables, and wherein the database has a given workload comprising a set of queries that has been executed on the database comprising:

• a) deriving an expected workload by specifying a degree of overlap between records selected by queries in the given workload and records selected by queries in the expected workload;
• b) constructing a sample by selecting data records for inclusion in the sample that minimize an estimation error with respect to queries in the expected workload;
• c) directing the query to access the sample;
• d) executing the query on the sample;
• and
• e) returning an estimated query result, wherein the sample is constructed by partitioning rows of the table into regions based on the queries in the expected workload and selecting records from the regions in a manner that minimizes estimation error over the expected workload, wherein records are selected from the regions by expressing the estimation error as a function of the number of records allocated to each region and allocating the number of allocated records to minimize the estimation error, rounding the number of records allocated to each region down to the nearest integer, accumulating remaining fractional values, and redistributing the accumulated fractional values to regions such that the estimation error is impacted the least.