Optimization based method for estimating the results of aggregate queries

A method for estimating 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, the method comprising the steps of:

• 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 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.

A method for constructing a sample of records in a database table contained in a database having a given workload comprising a set of queries that has been accessed on the database, the method comprising the steps of:

• a) partitioning the database into regions based on the workload;
• b) assigning a number of records to be selected to at least a subset of the regions such that the estimation error is minimized;
• and
• c) selecting the assigned number of records from each of the regions to form the sample.

A method for constructing a sample of records in a database table contained in a database having a fixed workload comprising a set of queries that has been executed on the database, the method comprising the steps of:

• a) partitioning the database into regions based on the workload;
• b) selecting a single record from each region;
• and
• c) storing the record and additional information about the region to construct the sample.

A method for constructing a model of an expected database workload based on a given workload comprising a set of queries that have been executed on the database, the method comprising the steps of:

• a) examining the given workload;
• b) assigning a probability of occurrence to a query that is based on an amount of similarity between the query and the given workload;
• and
• c) deriving an expected workload model that assigns a probability of occurrence to each possible query.

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 the steps of:

• a) deriving an expected workload based on the given workload;
• b) constructing a sample by accessing the data records in a table to minimize an estimation error based on 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.

A computer readable medium containing computer executable instructions for constructing a model of an expected database workload based on a given workload comprising a set of queries that have been executed on the database, the instructions comprising the steps of:

• a) examining the given workload;
• b) assigning a probability of occurrence to a query that is based on an amount of similarity between the query and the given workload;
• and
• c) deriving an expected workload model that assigns a probability of occurrence to each possible query.

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) deriving an expected workload based on the given workload;
• b) a sample constructor for accessing the data records in a table to minimize an estimation error based on the expected workload to construct a sample;
• c) a query redirector for directing the query to access the sample;
• and
• d) a query estimator for returning an estimated query result
• e)

An apparatus for constructing a model of an expected database workload based on a given workload comprising a set of queries that have been executed on the database, the apparatus comprising:

• a) a monitoring means for logging the given workload;
• b) a modeling means for assigning a probability of occurrence to a query that is based on an amount of similarity between the query and the given workload;
• and
• c) a constructing means for constructing an expected workload model that assigns a probability of occurrence to each possible query.