ADAPTIVE RESOLUTION HISTOGRAM

• US 20160239528A1
• Filed: 02/12/2015
• Published: 08/18/2016
• Est. Priority Date: 02/12/2015
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: PEMBERTON, NATHAN, AGGARWAL, VIKAS, AGARWAL, NIPUN, IDICULA, SAM
• Granted Patent: US 10,146,806 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

A method, apparatus, and system for determining a data distribution is provided by using an adaptive resolution histogram. In an embodiment, the adaptive resolution histogram is created using a trie, wherein node values in the trie represent frequency distributions and node positions define associated keys or key prefixes. Keys are derived from input data such as database records that are streamed from a record source. These keys may be processed as received to build the trie in parallel with the production of the input data. To provide adaptive resolution, new child nodes may only be created in the trie when a node value is incremented beyond a predetermined threshold. In this manner, the histogram adjusts the allocation of nodes according to the actual distribution of the data. The completed adaptive resolution histogram may be used for various tasks such as partitioning for balanced parallel processing of the input data.

Claims

1. A method comprising:

receiving a plurality of keys of a first data type having N elements of a second data type;

creating a trie and adding a root node, wherein nodes added to the trie are initialized to a value of zero;

defining a traverse procedure to process an input key at an input node of the trie, wherein the traverse procedure increments a value of one or more nodes, traversed according to the input key, until reaching a leaf node comprising at least one of a bottom node at a maximum depth corresponding to N and a halt node with a value not exceeding a predetermined threshold value, and wherein a new child node is added to the trie only when the value of a particular node is incremented beyond the predetermined threshold value; and

executing the traverse procedure to process each of the plurality of keys at the root node of the trie;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein the traverse procedure comprises:

incrementing a value of the input node;

returning from the traverse procedure when the input node is the leaf node;

determining a next node to traverse based on a most significant element of the input key, the most significant element being of the second data type;

determining a next key corresponding to the input key after the most significant element;

adding the next node as the new child node of the input node when the next node does not exist in the trie; and

executing the traverse procedure to process the next key at the next node.

3. The method of claim 1, further comprising:

creating one or more data partitions for the plurality of keys based on a depth first traversal of the trie to determine node groups each having a total value according to a target partition size.

4. The method of claim 3, wherein the target partition size is a maximum partition size.

5. The method of claim 3, wherein the depth first traversal is a modified depth first traversal that truncates search paths of subtrees in the trie that are included in the node groups.

6. The method of claim 1, wherein the plurality of keys is derived from a plurality of records streamed from a record source.

7. The method of claim 1, wherein the receiving of the plurality of keys and the executing of the traverse procedure to process each of the plurality of keys are performed in parallel.

8. A non-transitory computer-readable medium storing one or more sequences of instructions which, when executed by one or more processors, cause performing of:

receiving a plurality of keys of a first data type having N elements of a second data type;

creating a trie and adding a root node, wherein nodes added to the trie are initialized to a value of zero;

defining a traverse procedure to process an input key at an input node of the trie, wherein the traverse procedure increments a value of one or more nodes, traversed according to the input key, until reaching a leaf node comprising at least one of a bottom node at a maximum depth corresponding to N and a halt node with a value not exceeding a predetermined threshold value, and wherein a new child node is added to the trie only when the value of a particular node is incremented beyond the predetermined threshold value; and

executing the traverse procedure to process each of the plurality of keys at the root node of the trie.

9. The non-transitory computer-readable medium of claim 8, wherein the traverse procedure comprises:

incrementing a value of the input node;

returning from the traverse procedure when the input node is the leaf node;

determining a next node to traverse based on a most significant element of the input key, the most significant element being of the second data type;

determining a next key corresponding to the input key after the most significant element;

adding the next node as the new child node of the input node when the next node does not exist in the trie; and

executing the traverse procedure to process the next key at the next node.

10. The non-transitory computer-readable medium of claim 8, wherein the one or more sequence of instructions further cause performing of:

creating one or more data partitions for the plurality of keys based on a depth first traversal of the trie to determine node groups each having a total value according to a target partition size.

11. The non-transitory computer-readable medium of claim 10, wherein the target partition size is a maximum partition size.

12. The non-transitory computer-readable medium of claim 10, wherein the depth first traversal is a modified depth first traversal that truncates search paths of subtrees in the trie that are included in the node groups.

13. The non-transitory computer-readable medium of claim 8, wherein the plurality of keys is derived from a plurality of records streamed from a record source.

14. The non-transitory computer-readable medium of claim 8, wherein the receiving of the plurality of keys and the executing of the traverse procedure to process each of the plurality of keys are performed in parallel.

15. A system comprising one or more computing devices configured to:

receive a plurality of keys of a first data type having N elements of a second data type;

create a trie and add a root node, wherein nodes added to the trie are initialized to a value of zero;

define a traverse procedure to process an input key at an input node of the trie, wherein the traverse procedure increments a value of one or more nodes, traversed according to the input key, until reaching a leaf node comprising at least one of a bottom node at a maximum depth corresponding to N and a halt node with a value not exceeding a predetermined threshold value, and wherein a new child node is added to the trie only when the value of a particular node is incremented beyond the predetermined threshold value; and

execute the traverse procedure to process each of the plurality of keys at the root node of the trie.

16. The system of claim 15, wherein the traverse procedure comprises:

incrementing a value of the input node;

returning from the traverse procedure when the input node is the leaf node;

determining a next node to traverse based on a most significant element of the input key, the most significant element being of the second data type;

determining a next key corresponding to the input key after the most significant element;

adding the next node as the new child node of the input node when the next node does not exist in the trie; and

executing the traverse procedure to process the next key at the next node.

17. The system of claim 15, wherein the system is further configured to:

create one or more data partitions for the plurality of keys based on a depth first traversal of the trie to determine node groups each having a total value according to a target partition size.

18. The system of claim 17, wherein the target partition size is a maximum partition size.

19. The system of claim 17, wherein the depth first traversal is a modified depth first traversal that truncates search paths of subtrees in the trie that are included in the node groups.

20. The system of claim 15, wherein the plurality of keys is derived from a plurality of records streamed from a record source, and wherein the system is configured to receive the plurality of keys in parallel with the executing of the traverse procedure to process each of the plurality of keys.