1. A method of configuring a database through a database configuration system, the database configuration system having a computing device, the method comprising: a) determining at least two configurations of a database system, each configuration containing one or more tables, indices, and/or views; b) sampling a first configuration and a second configuration from the at least two configurations; c) determining a representative workload containing at least one query executable against the database system; d) sampling a sample workload from at least a portion of the representative workload; e) estimating a cost of executing the sample workload based on the first configuration and the second configuration; f) determining a probability of correct selection of the first configuration and the second configuration; g) determining a probability of correct selection of the sample workload based at least in part on the probability of correct selection of the first configuration and the second configuration and a sensitivity parameter that represents an estimated difference in cost between the first configuration and the second configuration; h) updating the sample workload when the probability of correct selection of the sample workload does not exceed a target probability threshold; and i) when the probability of correct selection of the sample workload exceeds the target probability threshold, configuring the data store based on a best configuration of the first configuration and the second configuration based on the estimated cost.