STATISTICS COLLECTION USING PATH-IDENTIFIERS FOR RELATIONAL DATABASES

• US 20100011030A1
• Filed: 09/11/2009
• Published: 01/14/2010
• Est. Priority Date: 05/16/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lim, Lipyecw, Wang, Min, Mihaila, George Andrei
• Granted Patent: US 8,229,924 B2
• Time in Patent Office: Days
• US Class Current: N/A
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/8365 Query optimisation
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Disclosed are a system, method, and computer readable medium for collecting statistics associated with data in a database. The method comprises determining an amount of memory needed to collect statistics for data associated with a defined data type in a relational database. The defined data type is based upon a mark-up language using a tree structure with one or more root-to-node paths therein. The amount of memory as determined is allocated for collecting the statistics for the data of the defined data type. A statistics collection is performed for the data of the defined data type in a single pass through the database and within the amount of memory which has been allocated.

Claims

1. A method, on an information processing system, for collecting statistics associated with data in a database, the method comprising:

determining an amount of memory needed to collect statistics for data associated with a defined data type in a relational database, wherein the defined data type is based upon a mark-up language using a tree structure with one or more root-to-node paths therein;

allocating the amount of memory as determined for collecting the statistics for the data of the defined data type; and

performing a collection of statistics for the data of the defined data type in a single pass through the database and within the amount of memory which has been allocated;

2. The method of claim 1, wherein the performing the collection of statistics, further comprises:

counting a total number of instances of at least one path-identifier within a given set of documents; and

determining at least one of a node count and a document count for the path-identifier based on the counting.

3. The method of claim 2, wherein the at least one path-identifier is one of a given number of most frequently occurring path-identifiers in the given set of documents.

4. The method of claim 1, wherein the performing the collection of statistics further comprises:

counting, for each document within a set of given documents, a total number of path-identifiers that are each associated with a unique path, thereby resulting in a total number of path-identifiers in the set of given documents that are associated with the unique path;

counting a total number of nodes within the set of given documents; and

counting, for each path-identifier that is associated with a unique path, a total number of documents in the set of given documents that include the path-identifier, thereby resulting in a sum of document counts.

5. The method of claim 1, wherein the performing the collection of statistics, further comprises performing at least one of:

sampling at a document level, wherein the sampling comprises at least one of a row level sampling and a page level sampling; and

sampling using at least one reservoir.

6. The method of claim 5, wherein the sampling using reservoirs comprises:

traversing through at least one of

sampled documents in a given set of documents; and

all documents in the set of given set of documents for identifying at least path-identifiers;

passing data associated with each path-identifier that has been identified to a first reservoir; and

passing data associated with each path-identifier that has been identified and is unique within a particular document in the given set of documents to a second reservoir.

7. The method of claim 6, further comprising:

applying a first bloom filter to each path-identifier prior to passing the path-identifier to the second reservoir, thereby preventing a duplicate path-identifier within the particular document from being passed to the second reservoir.

8. The method of claim 7, further comprising:

summarizing the first reservoir for identifying a node count for determining a given number of most frequently occurring path-identifiers; and

summarizing the second reservoir for identifying a document count for determining the given number of most frequently occurring path-identifiers.

9. A system for collecting statistics associated with data in a database, the system comprising:

at least one information processing system communicatively coupled to a database, the information processing system comprising;

a memory estimator for determining an amount of memory needed to collect statistics for data associated with a defined data type in the database, wherein the defined data type is based upon a mark-up language using a tree structure with one or more root-to-node paths therein;

a memory allocator for allocating the amount of memory as determined for collecting the statistics for the data of the defined data type; and

a statistics collector for performing a collection of statistics for the data of the defined data type in a single pass through the database and within the amount of memory which has been allocated.

10. The system of claim 9, wherein the statistics collector determines a total number of instances of at least one path-identifier within a given set of documents in the database and wherein the statistics collector determines at least one of a node count and a document count for the path-identifier based on the total number of instances, wherein the at least one path-identifier is one of a given number of most frequently occurring path-identifiers in the given set of documents.

11. The system of claim 9, wherein the statistics collector

counts, for each document within a set of given documents, a total number of path-identifiers that are each associated with a unique path, thereby resulting in a total number of path-identifiers in the set of given documents that are associated with the unique path;

counts a total number of nodes within the set of given documents; and

counts for each path-identifier that is associated with a unique path, a total number of documents in the set of given documents that include the path-identifier, thereby resulting in a sum of document counts.

12. The system of claim 9, wherein the information system further comprises at least one sampling reservoir, wherein the statistics collector

traverses through at least one of

sampled documents in a given set of documents;

and

all documents in the set of given set of documents

for identifying at least path-identifiers;

passes data associated with each path-identifier that has been identified to a first reservoir; and

passes data associated with each path-identifier that has been identified and is unique within a particular document in the given set of documents to a second reservoir, wherein the first reservoir is summarized for identifying a node count for determining a given number of most frequently occurring path-identifiers, and wherein the second reservoir is summarized for identifying a document count for determining the given number of most frequently occurring path-identifiers.

13. The system of claim 12, wherein the information processing system further comprises at least one bloom filter that is applied to each path-identifier prior to passing the path-identifier to the second reservoir, thereby preventing a duplicate path-identifier within the particular document from being passed to the second reservoir.

14. A computer readable medium for collecting statistics associated with data in a database, the computer readable medium comprising instructions for:

determining an amount of memory needed to collect statistics for data associated with a defined data type in a relational database, wherein the defined data type is based upon a mark-up language using a tree structure with one or more root-to-node paths therein;

allocating the amount of memory as determined for collecting the statistics for the data of the defined data type; and

performing a collection of statistics for the data of the defined data type in a single pass through the database and within the amount of memory which has been allocated.

15. The computer readable medium of claim 14, wherein the instructions for performing the collection of statistics, further comprise instructions for:

counting a total number of instances of at least one path-identifier within a given set of documents; and

determining at least one of a node count and a document count for the path-identifier based on the counting.

16. The computer readable medium of claim 15, wherein the at least one path-identifier is one of a given number of most frequently occurring path-identifiers in the given set of documents.

17. The computer readable medium of claim 15, wherein the instructions for performing the collection of statistics further comprise instructions for:

counting, for each document within a set of given documents, a total number of path-identifiers that are each associated with a unique path, thereby resulting in a total number of path-identifiers in the set of given documents that are associated with the unique path;

counting a total number of nodes within the set of given documents; and

counting, for each path-identifier that is associated with a unique path, a total number of documents in the set of given documents that include the path-identifier, thereby resulting in a sum of document counts.

18. The computer readable medium of claim 15, wherein the instructions for performing the collection of statistics further comprise instructions for:

sampling at a document level, wherein the sampling comprises at least one of a row level sampling and a page level sampling; and

sampling using at least one reservoir.

19. The computer readable medium of claim 18, wherein the instructions for sampling using reservoirs further comprise instructions for:

traversing through at least one of

sampled documents in a given set of documents; and

all documents in the set of given set of documents

for identifying at least path-identifiers;

passing data associated with each path-identifier that has been identified to a first reservoir; and

passing data associated with each path-identifier that has been identified and is unique within a particular document in the given set of documents to a second reservoir; and

applying a first bloom filter to each path-identifier prior to passing the path-identifier to the second reservoir, thereby preventing a duplicate path-identifier within the particular document from being passed to the second reservoir.

20. The computer readable medium of claim 19, further comprising instructions for:

summarizing the first reservoir for identifying a node count for determining a given number of most frequently occurring path-identifiers; and

summarizing the second reservoir for identifying a document count for determining the given number of most frequently occurring path-identifiers.