Patent ID: 7120624
Filing Date: 2006-10-10
Classification: G06F,Y10S

Abstract:
1. 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, the method comprising the steps of: a) deriving an expected workload based on the given workload; b) constructing a sample by selecting 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.