A method, system and computer program product for a database management system to be operatively coupled to a data processing system. The data processing system includes memory for storing a data table. The method, system and computer program product for determining frequency of updating a histogram of the data table. The method includes determining sampled histograms for sample portions of the data table from time to time, computing a difference between at least two of the determined sampled histograms, and determining a frequency with which to update the histogram of the data table depending on the amount of the computed difference.