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.