A method and system to determine a q, θ-optimal histogram comprising a plurality of buckets over a data distribution where for any cardinality estimate made using the histogram the cardinality estimate is constrained to obey an acceptability criteria parameterized by q and θ that bounds a ratio error between the cardinality estimate and a true value of the cardinality, q being a factor by which the estimate deviates, at most, from a true value of the cardinality and θ being a threshold value which the cardinality does not exceed, wherein a maximum number of possible query intervals generated in determining the acceptability of the q, θ-optimal histogram is less than quadratic in the number of values.