SYSTEM AND METHOD FOR PARALLEL COMPUTATION OF FREQUENCY HISTOGRAMS ON JOINED TABLES

• US 20100250517A1
• Filed: 03/24/2009
• Published: 09/30/2010
• Est. Priority Date: 03/24/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Draese, Oliver, Bendel, Peter, Raman, Vijayshankar, Stolze, Knut
• Granted Patent: US 8,370,326 B2
• Time in Patent Office: Days
• US Class Current: 707/714
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

According to one embodiment of the present invention, a method for the parallel computation of frequency histograms in joined tables is provided. The method includes reading data in a table row-by-row from a database system using a coordinator unit and distributing each read row to separate worker units. Each worker unit computes a partial frequency histogram for each column in the table in parallel. The partial histograms from the worker units are then merged and the coordinator unit sends the merged frequency histograms to the worker units.

Claims

1. A method comprising:

reading data in a table row-by-row from a database system using a coordinator unit;

distributing each read row to separate worker units;

computing a partial frequency histogram for each column in said table using each worker unit in parallel;

merging partial histograms from said worker units; and

sending said merged frequency histograms to said worker units using said coordinator unit.

2. A method according to claim 1 wherein said table is at a first join depth, said method further comprising:

said coordinator unit reading rows from a table at a second join depth and distributing each said second join depth table to one of said worker units; and

said worker units computing frequency histograms for each column in said second join depth table using said merged frequency histograms from said first join depth tables.

3. A method according to claim 2 wherein said table at a first join depth is a fact table and said table at a second join depth is a dimension table.

4. A method according to claim 1 wherein said coordinator unit distributes rows evenly to worker units regardless of the data therein.

5. A method according to claim 1 wherein said coordinator unit distributes rows to worker units based on the data in each row.

6. A method according to claim 1 wherein said worker units begin said computing as soon as a first row is received from said coordinator unit.

7. A method according to claim 1 wherein aid worker units perform said computing before a join operation is performed on said table.

8. A method according to claim 1 wherein said computing further comprises, determining if a column value is already in said histogram, and if so, increasing a frequency count by one, and if not, adding said column value to said histogram value with a frequency count equal to one.

9. A method according to claim 1 wherein said merging comprises summing up the frequencies from said partial histograms.

10. A method according to claim 2 wherein said worker units compute frequency histograms for each column in said second join depth by determining if a value in said column is already in said histogram, and if so, then increasing the frequency count for the column value in the histogram by a dependent-frequency value, and if not, adding said column value to said histogram with a frequency count equal to said dependent-frequency value.

11. A method according to claim 10, wherein said dependent-frequency value is the frequency of a primary key value in a frequency histogram of a foreign key column in said first join depth table.

12. A method according to claim 1, wherein said table is at a second join depth, said method further comprising:

said coordinator unit reading rows from a table at a third join depth and distributing each said third join depth table to one of said worker units; and

said worker units computing frequency histograms for each column in said third join depth table using said merged frequency histograms from said second join depth tables.

13. A method comprising:

reading data in a table row-by-row from a database system using a coordinator unit, said table being at a first join depth;

distributing each read row to separate worker units;

computing a partial frequency histogram for each column in said table using each worker in parallel;

merging partial histograms from said worker units;

sending said merged frequency histograms to said worker units using said coordinator unit;

said coordinator unit reading rows from a table at a second join depth and distributing each said second join depth table to one of said worker units; and

said worker units computing frequency histograms for each column in said second join depth table using said merged frequency histograms from said first join depth tables.

14. A method according to claim 13 further comprising

determining column partitions based on said histograms;

determining a dictionary for each for each column partition;

making said dictionaries available to each worker units;

encoding data from which said frequency histograms were originally generated.

15. A method according to claim 14 wherein said table at a first join depth is a fact table and said table at a second join depth is a dimension table.

16. A method according to claim 14 wherein said coordinator unit distributes rows evenly to worker units regardless of the data therein.

17. A method according to claim 14 wherein said coordinator unit distributes rows to worker units based on the data in each row.

18. A database system comprising:

a coordinator unit;

a plurality of worker units;

a set of tables at a first join depth, each table having columns and rows, wherein said coordinator unit reads data in said tables row-by-row and distributes each row to separate worker units;

said worker units operating in parallel to compute a partial frequency histogram for each column in said table received from said coordinator unit; and

said coordinator unit merging partial histograms form said worker units and sending said merged frequency histograms to said worker units.

19. A system according to claim 18 wherein said computing further comprises, determining if a column value is already in said histogram, and if so, increasing a frequency count by one, and if not, adding said column value to said histogram value with a frequency count equal to one.

20. A system according to claim 18 wherein said worker units compute frequency histograms for each column in said second join depth by determining if a value in said column is already in said histogram, and if so, then increasing the frequency count for the column value in the histogram by a dependent-frequency value, and if not, adding said column value to said histogram with a frequency count equal to said dependent-frequency value.

21. A computer program product for computing frequency histograms, said computer program product comprising:

a computer usable medium having computer usable program code embodied therewith, said computer usable program code comprising;

computer usable program code configured to;

read data in a table row-by-row from a database system using a coordinator unit;

distribute each read row to separate worker units;

compute a partial frequency histogram for each column in said table using each worker unit in parallel;

merge partial histograms from said worker units; and

send said merged frequency histograms to said worker units using said coordinator unit.

22. A computer program product according to claim 21 wherein said coordinator unit distributes rows evenly to worker units regardless of the data therein.

23. A computer program product according to claim 21 wherein said coordinator unit distributes rows to worker units based on the data in each row.

24. A computer program product according to claim 21 wherein said worker units begin said computing as soon as a first row is received from said coordinator unit.

25. A method according to claim 21 wherein said worker units perform said computing before a join operation is performed on said table.