According to one aspect of the invention, for a database statement that specifies rollup operations, a data distribution key may be selected among a plurality of candidate keys. Numbers of distinct values of the candidate keys may be monitored with respect to a particular set of rows. Hash values may also be generated by column values in the candidate keys. The data distribution key may be determined based on results of monitoring the numbers of distinct values of the candidate keys as well as the frequencies of hash values computed based on column values of the candidate keys. Rollup operations may be shared between different stages of parallel executing processes and data may be distributed between the different stages of parallel executing processes based on the selected data distribution key.