Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-12-16
2002-03-19
Mizrahi, Diane (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06360214
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to database systems, and more particularly to a system for automatically generating statistics for data stored in a database.
BACKGROUND OF THE INVENTION
A relational database is a collection of related data that is organized in related two-dimensional tables of columns and rows. The data stored in a relational database is typically accessed by way of a user-defined query that is constructed in a query language such as Structured Query Language (SQL). A SQL query is non-procedural in that it specifies the objective or desired result of the query in a language meaningful to a user but does not define the steps to be performed, or the order of the steps in order to accomplish the query.
When a SQL query is applied to a database, the relational database management system (RDBMS) processes the non-procedural query and develops a plurality of procedural execution plans, any one of which could be employed to implement the objectives of the SQL query. While each of the execution plans may fulfill the objectives of the SQL query, each has a different cost (in terms of processing cycles and logical I/Os) associated with it. The relational database management system attempts to select the execution plan which is most efficient, i.e. has the least overall cost. Generally, the selection is made on the basis of statistics that are derived from the data in the database and maintained by the RDBMS. For example, a database may record the number of distinct values in a pre-designated index column along with a histogram of the values distributed across the column. Using these and other statistics, the database system makes an educated guess of the cost associated with each execution plan, selects the most efficient plan, and stores the selected plan in an area of memory sometimes referred to as an execution plan cache. On subsequent invocations of the same SQL query, rather than re-traverse the process of identifying the most efficient execution plan, the database system refers to the execution plan cache and selects the previously identified optimal execution plan.
In existing database systems, statistics are generated only for specific tables that are pre-defined by a database administrator. As a consequence, the situation often arises that statistics have not been generated that would have been used in selecting an execution plan if available. In such cases, the database system relies upon rough estimates or “guesses” of the statistics. Relying upon guesses rather than actual statistics introduces inaccuracies to the process and can lead to the selection of a less than optimal execution plan. As a consequence, database queries may take longer and use more resources than optimally necessary.
In existing systems, it is theoretically possible to avoid guessing as to statistics by configuring the system to build statistics on every column in the database. In reality, however, such a configuration is impracticable due to the overhead associated with maintaining statistics on such a large group of statistics. Guessing as to statistics might also be avoided by configuring the system to collect statistics which cover all predicates submitted to the database. This task would be very complex as it requires that the database administrator know a-priori the complete set of queries (workload) which would be submitted to the system. In many database systems, this problem is intractable as many users of the database system rely on tools which automatically generate queries.
Thus, there is a need in the art for a system and method whereby statistics are automatically generated as needed for data that is accessed by an execution plan. The system should automatically remove selected portions of the automatically generated statistics to avoid the accumulation of statistics across all columns in the database.
SUMMARY OF THE INVENTION
The present invention is directed toward remedying these shortcomings by automatically generating statistics as needed. According to the invention, during the process of generating an execution plan, the names are accumulated of the columns which are processed by the execution plan but for which statistics do not exist. After checking that these columns are of a type for which statistics may be generated, the system generates the statistics. Thereafter, an optimal execution plan is selected based upon the actual statistics rather than guesses.
According to another aspect of the invention, a counter is maintained for each automatically generated statistic of the number of updates made to the statistic. When the counter reaches a threshold, the automatically generated statistic is deleted.
REFERENCES:
patent: 5630120 (1997-05-01), Vachey
patent: 5806061 (1998-09-01), Chaudhuri et al.
patent: 6012054 (2000-01-01), Seputis
patent: 6052689 (2000-04-01), Muthukrishnan et al.
patent: 6065007 (2000-05-01), Muthukrishnan et al.
A tool for nesting and clustering large objects of Dietker et al. (IEEE publication, 7-2000) from Scientific and statistical database management proc. 12th Intern. Confer., pp. 169-181.*
Automating statistics management for query optimizer by Chaudhuri et al. (IEEE publication 3-2000) from Knowledge and data engineering, vol. 13, No. 1, pp. 7-20.*
Soukup, R., “Inside SQL Server™ 6.5”, Microsoft® Programming Series, Microsoft® Press, 1997 pp. 1-32 (renumbered).
Ellis Nigel R.
Kline Rodger N.
Microsoft Corporation
Mizrahi Diane
Woodcock & Washburn LLP
LandOfFree
Automatic database statistics creation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automatic database statistics creation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic database statistics creation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2816563