A plurality of histograms are maintained with respect to a dataset. The dataset includes a plurality of data segments. In response to a query that includes a plurality of conditions ordered in an initial sequence, a plurality of corresponding rejection rates is determined for the plurality of conditions based at least in part on the plurality of histograms. The plurality of conditions are re-ordered according to the plurality of corresponding rejection rates associated with the plurality of conditions to form a reordered sequence for the plurality of conditions. The query is executed according to the reordered sequence of the plurality of conditions.