In a database management system for managing data in a database, the database management system including a query optimizer that performs query optimization based on statistics related to the data in the database, a method for incrementally updating the statistics, the method comprising: an act of organizing the statistics related to the data in the database into a statistics tree structure having a root node that corresponds to one or more global statistics, one or more internal nodes that correspond to incremental summary statistics of descendant nodes, and one or more leaf nodes that correspond to one or more statistics related to disjoint data ranges in the database; and an act of rearranging contiguous ranges of physical partitions among leaf nodes based on a cost function, wherein rearranging contiguous ranges of physical partitions among leaf nodes based on a cost function comprises: an act of determining, based on the cost function, a recomputation cost for updating the statistics of each corresponding leaf node of the statistics tree structure; an act of splitting a leaf node with a high recomputation cost into two or more leaf nodes that each have a lower recomputation cost than the leaf nodes that are split; an act of merging two or more leaf nodes with a low recomputation cost into a new single leaf node that has a higher recomputation cost than the leaf nodes that are merged; and an act of continuing the acts of determining the recomputation cost, splitting and merging until a fixed point is reached where all the leaf nodes have a recomputation cost that is as close to equal as possible given a maximum number of children nodes per internal node and a maximum number of leaf nodes for the entire statistics tree structure. an act of organizing the statistics related to the data in the database into a statistics tree structure having a root node that corresponds to one or more global statistics, one or more internal nodes that correspond to incremental summary statistics of descendant nodes, and one or more leaf nodes that correspond to one or more statistics related to disjoint data ranges in the database; and an act of rearranging contiguous ranges of physical partitions among leaf nodes based on a cost function, wherein rearranging contiguous ranges of physical partitions among leaf nodes based on a cost function comprises: an act of determining, based on the cost function, a recomputation cost for updating the statistics of each corresponding leaf node of the statistics tree structure; an act of splitting a leaf node with a high recomputation cost into two or more leaf nodes that each have a lower recomputation cost than the leaf nodes that are split; an act of merging two or more leaf nodes with a low recomputation cost into a new single leaf node that has a higher recomputation cost than the leaf nodes that are merged; and an act of continuing the acts of determining the recomputation cost, splitting and merging until a fixed point is reached where all the leaf nodes have a recomputation cost that is as close to equal as possible given a maximum number of children nodes per internal node and a maximum number of leaf nodes for the entire statistics tree structure. an act of determining, based on the cost function, a recomputation cost for updating the statistics of each corresponding leaf node of the statistics tree structure; an act of splitting a leaf node with a high recomputation cost into two or more leaf nodes that each have a lower recomputation cost than the leaf nodes that are split; an act of merging two or more leaf nodes with a low recomputation cost into a new single leaf node that has a higher recomputation cost than the leaf nodes that are merged; and an act of continuing the acts of determining the recomputation cost, splitting and merging until a fixed point is reached where all the leaf nodes have a recomputation cost that is as close to equal as possible given a maximum number of children nodes per internal node and a maximum number of leaf nodes for the entire statistics tree structure.