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 at least in part upon the plurality of queries of the original workload; assigning the plurality of queries into one or more of the stratification buckets; forming a representative workload for evaluating a plurality of partition schemes, wherein forming the representative workload comprises: calculating a standard deviation of an optimizer query cost of the original workload; selecting a desired confidence interval and a desired margin of error; calculating a number n of queries to be sampled from the original workload to form the representative workload, wherein the number n is calculated based at least in part upon the calculated standard deviation of the original workload, such that the representative workload will have the selected confidence interval and margin of error relative to the original workload; sampling the number n of queries drawn from at least some of the stratification buckets to form the representative workload; and evaluating, using a computer, each of the plurality of partition schemes using the representative workload to determine a first optimal partition scheme, wherein evaluating the plurality of partition schemes is performed only after the representative workload is formed.