1. A computer implemented method for validating database table partitioning schemes using stratified random sampling, the method comprising: receiving, by a computer, an original workload comprising a plurality of queries; enumerating stratification buckets based on the plurality of queries; assigning the plurality of queries into one or more of the stratification buckets; sampling a number n of queries drawn from at least some of the stratification buckets to form a representative workload, wherein the number n of queries is based at least in part upon a selected confidence interval and a selected margin of error; and evaluating, using a computer, each of a plurality of partition schemes using the representative workload to determine a first optimal partition scheme.