This paper proposes and solves the min-dist optimal-location query in spatial databases. Given a set S of sites, a set O of weighted objects, and a spatial region Q, the min-dist optimal-location query returns a location in Q which, if a new site is built there, minimizes the average distance from each object to its closest site. This query can help a franchise (e.g. McDonald's) decide where to put a new store in order to maximize the benefit to its customers. To solve this problem is challenging, for there are theoretically infinite number of locations in Q, all of which could be candidates. This paper first provides a theorem that limits the number of candidate locations without losing the power to find exact answers. Then it provides a progressive algorithm that quickly suggests a location, tells the maximum error it may have, and keeps refining the result. When the algorithm finishes, the exact answer can be found. The intermediate result of early runs can be used to prune the search space for later runs. Crucial to the pruning technique are novel lower-bound estimators. The proposed algorithm, the effect of several optimizations, and the progressiveness are experimentally evaluated.