Gathering Index Statistics Using Sampling

• US 20140115009A1
• Filed: 10/19/2012
• Published: 04/24/2014
• Est. Priority Date: 10/19/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lashley, Scott D., Miao, Bingjie
• Granted Patent: US 9,189,518 B2
• Time in Patent Office: Days
• US Class Current: 707/797
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/2453 Query optimisation

Abstract

An approach is provided in which a sample point system allocates sample point identifiers to a root node included an index tree that includes multiple leaf nodes. The sample point system distributes the sample point identifiers to the root node'"'"'s child nodes, and recursively traverses through the index tree'"'"'s hierarchical index levels and distributes the sample point identifiers from the child nodes to a subset of the index tree'"'"'s leaf nodes. In turn, the sample point system collects sample data from the subset of the plurality of leaf nodes corresponding to the distributed sample point identifiers.

Claims

1. A method comprising:

allocating, by one or more processors, a plurality of sample point identifiers to a root node included in an index tree corresponding to a database, the index tree including a plurality of leaf nodes;

distributing, by one or more of the processors, the plurality of sample point identifiers to a plurality of first nodes that are child nodes of the root node;

recursively traversing, by one or more of the processors, through a plurality of hierarchical index levels included in the index tree and distributing the plurality of sample point identifiers from the plurality of first nodes to a subset of the plurality of leaf nodes; and

collecting sample data, by one or more of the processors, from the subset of the plurality of leaf nodes corresponding to the distributed plurality of sample point identifiers.

2. The method of claim 1 wherein the allocating further comprises:

uniformly distributing the plurality of sample point identifiers across the plurality of first nodes; and

wherein the subset of the plurality of leaf nodes is uniformly distributed across the plurality of leaf nodes included in the index tree.

3. The method of claim 1 further comprising:

computing a collected sample standard deviation of the collected sample data;

determining that the collected sample standard deviation reaches a standard deviation threshold;

in response to determining that the collected sample deviation fails to reach a standard deviation threshold, determining whether a maximum number of iterations is reached;

in response to determining that the maximum number of iterations has not been reached;

invoking a subsequent recursive traversal through the plurality of hierarchical index levels and uniformly distributing the plurality of sample point identifiers to a subsequent subset of the plurality of leaf nodes; and

collecting subsequent sample data from the subsequent subset of the plurality of leaf nodes.

4. The method of claim 3 wherein, in response to determining that the maximum number of iterations has been reached, generating a message that indicates the collected sample data fails to meet the standard deviation threshold.

5. The method of claim 1 further comprising:

identifying a number of first nodes included in the plurality of first nodes;

computing a distribution average based upon the number of first nodes and a number of sample point identifiers included in the plurality of sample point identifiers;

generating a plurality of random numbers, wherein each of the plurality of random numbers identify one of the plurality of first nodes; and

wherein the distribution of the plurality of sample point identifiers is based upon the plurality of random numbers and the computed distribution average.

6. The method of claim 1 further comprising:

selecting one of the plurality of first nodes;

determining the number of sample point identifiers that were distributed to the selected first node;

identifying a plurality of second nodes that are child nodes of the selected first node;

computing a distribution average based upon the number of second nodes and the number of sample point identifiers that were distributed to the selected first node; and

re-distributing the sample point identifiers distributed to the selected first node to the plurality of second nodes based upon the computed distribution average.

7. The method of claim 6 further comprising:

determining that the plurality of second nodes are included in the plurality of leaf nodes; and

assigning the re-distributed sample point identifiers to the plurality of second nodes.

8. The method of claim 1 further comprising:

determining that the plurality of second nodes fail to be included in the plurality of leaf nodes;

in response to determining that the plurality of second nodes fail to be included in the plurality of leaf nodes;

selecting one of the plurality of second nodes;

determining the number of sample point identifiers that were re-distributed to the selected second node;

identifying a plurality of third nodes that are child nodes of the selected second node;

computing a different distribution average based upon the number of third nodes and the number of sample point identifiers that were distributed to the selected second node; and

re-distributing the sample point identifiers distributed to the selected second node to the plurality of third nodes based upon the computed different distribution average.

9. The method of claim 1 wherein the distribution includes utilizing a plurality of memory arrays to store the plurality of sample point identifiers during the recursive traversal, and wherein each one of the plurality of memory arrays corresponds to one of the plurality of hierarchical index levels, each one of the plurality of memory arrays utilized for each index node included in their corresponding hierarchical index level during the recursive traversal.

10. The method of claim 1 further comprising:

generating a query plan corresponding to the database based upon the collected sample data.

11. An information handling system comprising:

one or more processors;

a memory coupled to at least one of the processors;

one or more non-volatile storage areas coupled to at least one of the processors;

a set of computer program instructions stored in the memory and executed by at least one of the processors in order to perform actions of;

allocating a plurality of sample point identifiers to a root node included in an index tree corresponding to a database stored in one of the non-volatile storage areas, the index tree including a plurality of leaf nodes;

distributing the plurality of sample point identifiers to a plurality of first nodes that are child nodes of the root node;

recursively traversing through a plurality of hierarchical index levels included in the index tree and distributing the plurality of sample point identifiers from the plurality of first nodes to a subset of the plurality of leaf nodes; and

collecting sample data from the subset of the plurality of leaf nodes corresponding to the distributed plurality of sample point identifiers.

12. The information handling system of claim 11 wherein one or more of the processors perform additional actions comprising:

uniformly distributing the plurality of sample point identifiers across the plurality of first nodes; and

wherein the subset of the plurality of leaf nodes is uniformly distributed across the plurality of leaf nodes included in the index tree.

13. The information handling system of claim 11 wherein one or more of the processors perform additional actions comprising:

computing a collected sample standard deviation of the collected sample data;

determining that the collected sample standard deviation reaches a standard deviation threshold;

in response to determining that the collected sample deviation fails to reach a standard deviation threshold, determining whether a maximum number of iterations is reached;

in response to determining that the maximum number of iterations has not been reached;

invoking a subsequent recursive traversal through the plurality of hierarchical index levels and uniformly distributing the plurality of sample point identifiers to a subsequent subset of the plurality of leaf nodes; and

collecting subsequent sample data from the subsequent subset of the plurality of leaf nodes.

14. The information handling system of claim 13 wherein, in response to determining that the maximum number of iterations has been reached, one or more of the processors perform additional actions comprising:

generating a message that indicates the collected sample data fails to meet the standard deviation threshold.

15. The information handling system of claim 11 wherein one or more of the processors perform additional actions comprising:

identifying a number of first nodes included in the plurality of first nodes;

computing a distribution average based upon the number of first nodes and a number of sample point identifiers included in the plurality of sample point identifiers;

generating a plurality of random numbers, wherein each of the plurality of random numbers identify one of the plurality of first nodes; and

wherein the distribution of the plurality of sample point identifiers is based upon the plurality of random numbers and the computed distribution average.

16. The information handling system of claim 11 wherein one or more of the processors perform additional actions comprising:

selecting one of the plurality of first nodes;

determining the number of sample point identifiers that were distributed to the selected first node;

identifying a plurality of second nodes that are child nodes of the selected first node;

computing a distribution average based upon the number of second nodes and the number of sample point identifiers that were distributed to the selected first node; and

re-distributing the sample point identifiers distributed to the selected first node to the plurality of second nodes based upon the computed distribution average.

17. The information handling system of claim 16 wherein one or more of the processors perform additional actions comprising:

determining that the plurality of second nodes are included in the plurality of leaf nodes; and

assigning the re-distributed sample point identifiers to the plurality of second nodes.

18. The information handling system of claim 11 wherein one or more of the processors perform additional actions comprising:

determining that the plurality of second nodes fail to be included in the plurality of leaf nodes;

in response to determining that the plurality of second nodes fail to be included in the plurality of leaf nodes;

selecting one of the plurality of second nodes;

determining the number of sample point identifiers that were re-distributed to the selected second node;

identifying a plurality of third nodes that are child nodes of the selected second node;

computing a different distribution average based upon the number of third nodes and the number of sample point identifiers that were distributed to the selected second node; and

re-distributing the sample point identifiers distributed to the selected second node to the plurality of third nodes based upon the computed different distribution average.

19. The information handling system of claim 11 wherein the distribution includes utilizing a plurality of memory arrays to store the plurality of sample point identifiers during the recursive traversal, and wherein each one of the plurality of memory arrays corresponds to one of the plurality of hierarchical index levels, each one of the plurality of memory arrays utilized for each index node included in their corresponding hierarchical index level during the recursive traversal.

20. The information handling system of claim 11 wherein one or more of the processors perform additional actions comprising:

generating a query plan corresponding to the database based upon the collected sample data.

21. A computer program product stored in a computer readable storage medium, comprising computer program code that, when executed by an information handling system, causes the information handling system to perform actions comprising:

allocating a plurality of sample point identifiers to a root node included in an index tree of a database, the index tree including a plurality of leaf nodes;

distributing the plurality of sample point identifiers to a plurality of first nodes that are child nodes of the root node;

recursively traversing through a plurality of hierarchical index levels included in the index tree and distributing the plurality of sample point identifiers from the plurality of first nodes to a subset of the plurality of leaf nodes; and

collecting sample data from the subset of the plurality of leaf nodes corresponding to the distributed plurality of sample point identifiers.

22. The computer program product of claim 21 wherein the information handling system performs additional actions comprising:

uniformly distributing the plurality of sample point identifiers across the plurality of first nodes; and

wherein the subset of the plurality of leaf nodes is uniformly distributed across the plurality of leaf nodes included in the index tree.

23. The computer program product of claim 21 wherein the information handling system performs:

computing a collected sample standard deviation of the collected sample data;

determining that the collected sample standard deviation reaches a standard deviation threshold;

in response to determining that the collected sample deviation fails to reach a standard deviation threshold, determining whether a maximum number of iterations is reached;

in response to determining that the maximum number of iterations has not been reached;

invoking a subsequent recursive traversal through the plurality of hierarchical index levels and uniformly distributing the plurality of sample point identifiers to a subsequent subset of the plurality of leaf nodes; and

collecting subsequent sample data from the subsequent subset of the plurality of leaf nodes.

24. The computer program product of claim 21 wherein the information handling system performs:

identifying a number of first nodes included in the plurality of first nodes;

computing a distribution average based upon the number of first nodes and a number of sample point identifiers included in the plurality of sample point identifiers;

generating a plurality of random numbers, wherein each of the plurality of random numbers identify one of the plurality of first nodes; and

wherein the distribution of the plurality of sample point identifiers is based upon the plurality of random numbers and the computed distribution average.

25. The computer program product of claim 21 wherein the information handling system performs:

selecting one of the plurality of first nodes;

determining the number of sample point identifiers that were distributed to the selected first node;

identifying a plurality of second nodes that are child nodes of the selected first node;

computing a distribution average based upon the number of second nodes and the number of sample point identifiers that were distributed to the selected first node; and

re-distributing the sample point identifiers distributed to the selected first node to the plurality of second nodes based upon the computed distribution average.