Sampling statistics in a database system

• US 7,778,996 B2
• Filed: 09/25/2002
• Issued: 08/17/2010
• Est. Priority Date: 09/25/2002
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: Burger, Louis M.
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Ortiz; Belix M
• Application Number:
  US10/255,734
• Publication Number:
  US 20040059743A1
• Time in Patent Office: 2,883 Days
• Field of Search: None
• US Class Current: 707/713
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

A database system has the ability to perform sampled statistics collection, in which collection of statistics of a table is based on a sample (less than all rows of the table). The sample size is adjusted as the table is scanned in response to detecting a predetermined characteristic of the table (e.g., skewed data values are detected).

Claims

1. A computer-implemented database system, comprising:

a processor for receiving a query to be executed against a database table stored within a computer storage device, said processor executing the steps of;

scanning a sample of said table, the sample containing less than all rows of the table;

detecting whether data skew exists in a table column within the sample of said table;

adjusting a size of the sample as the table is scanned based on the detected data skew;

collecting statistics based on the adjusted sample; and

optimizing the performance of said query executed against said database table based upon said collected statistics.

2. The database system of claim 1, wherein detecting whether data skew exists in a table column within the sample of said table comprises detecting if a frequency of a data value within said table column within the sample of said table is greater than a predetermined threshold.

3. The database system of claim 1, wherein adjusting the size of the sample comprises increasing the size of the sample in response to detecting data skew in a table column within the sample of said table.

4. The database system of claim 3, wherein adjusting the size of the sample comprises successively increasing the size of the sample in response to plural instances of detecting data skew.

5. The database system of claim 1, wherein scanning the sample comprises reading one block, skipping N blocks, and then repeating the reading and skipping until complete.

6. The database system of claim 1, wherein adjusting the size of the sample comprises adjusting a value of N.

7. The database system of claim 1, wherein collecting the statistics comprises building a histogram.

8. The database system of claim 1, wherein said database table is stored on plural computer storage devices that are managed by respective processors, wherein the scanning, identifying, adjusting, and collecting are performed by each of the processors in parallel.

9. An article comprising at least one storage medium containing instructions that when executed cause a system to:

collect statistics of an attribute of a table based on a sample of the table, the sample having less than all rows of the table;

detect whether data skew exists in a table column within the sample of the table;

vary a size of the sample during statistics collection in response to detecting data skew;

collect statistics based on the size of said sample; and

optimize the performance of a query executed against said database based upon said collected statistics.

10. The article of claim 9, wherein varying the size of the sample comprises increasing the size of the sample in response to detecting data skew.

11. The article of claim 10, wherein detecting for data skew comprises determining if a number of duplicates of a data value within said table column within the sample of said table exceeds a predetermined threshold.

12. The article of claim 9, wherein the instructions when executed cause the system to skip rows of data to obtain the samples less than all rows of the table.

13. The article of claim 9, wherein the instructions when executed cause the system to read a block of data, skip N blocks, and repeat the reading and skipping until completed to obtain the sample less than all rows of the table.

14. A database system comprising:

a storage to store a table; and

a controller to;

read a sample of the table that is less than all rows of the table;

collect statistics based on the sample;

detect whether data skew exists in a table column within the sample of the table;

adjust a size of the sample in response to detecting data skew;

collect statistics based on the adjusted sample; and

optimize the performance of a query executed against said database based upon said collected statistics.

15. The database system of claim 14, the controller to collect statistics of an attribute of the table, the attribute being sorted by some predetermined algorithm.

16. The database system of claim 15, wherein the predetermined algorithm comprises a hash code.

17. The database system of claim 14, the controller to increase the size of the sample in response to detecting data skew.

18. The database system of claim 14, wherein the storage contains multiple storage modules, and the controller comprises plural access modules to manage access of the storage modules, wherein each of the access modules performs the reading, collecting, and adjusting in parallel.