1. At a computer system, the computer system including one or more processors and system memory, the computer system connected to a plurality of compute nodes configured in a shared-nothing architecture, a database table distributed across the plurality of compute nodes in accordance with a partitioning algorithm, each compute node in the plurality of compute nodes maintaining one or more portions of the database table in a local database instance, a method for formulating global statistics for a column of the table, the method comprising: accessing a plurality of histograms for the column, each histogram containing statistics for a portion of the database table maintained at a corresponding one of the plurality of compute nodes, for each of the plurality of histograms: each step in the histogram defined by step boundaries including a non-inclusive lower boundary value and an inclusive upper boundary value, data for each step in the histogram estimating: a number of occurrences of the upper boundary value and an average number of rows per distinct value within the step boundaries; merging the plurality of histograms into a global histogram for the column, the global histogram including global steps defined by step boundaries including a non-inclusive lower boundary value and an inclusive upper boundary value, data for each global step estimating: a number of occurrences of the upper boundary value and a global average number of rows per distinct value within the step boundaries, including for each global step: using knowledge of the partitioning algorithm when calculating the global average number of rows per distinct value for the global step; and storing the global histogram for use in query optimization.