An apparatus in one embodiment comprises at least one processing device comprising a processor coupled to a memory. The processing device is configured to identify at least first and second datasets to be scanned to generate a data reduction estimate for a prospective combination of the first and second datasets, to designate a scan criterion to be utilized in the scan of each of the datasets, and for each of a plurality of pages of each of the datasets, to scan the page, where scanning the page comprises performing a computation on the page to obtain a page result, determining whether or not the page result satisfies the designated scan criterion, and responsive to the page result satisfying the designated scan criterion, updating a corresponding entry of a data reduction estimate table for the dataset. The processing device merges contents of the data reduction estimate tables, and generates the data reduction estimate based at least in part on the merged contents.