1. At a computer system including a processor and a memory, in a computer networking environment including a plurality of computing systems, a computer-implemented method for determining optimal partition configurations for distributed database data, the method comprising: an act of accessing a portion of database data and one or more database queries for a given database; an act of determining, based on the accessed database data and database queries, a partition configuration search space which comprises a plurality of feasible partition configurations for the database data; an act of performing a branch and bound search in the partition configuration search space to determine which data partitioning path has the lowest cost, wherein the branch and bound search is performed according to one or more branch and bound search policies; and an act of outputting the partition configuration with the determined lowest cost.