1. An apparatus comprising: a processing device comprising a processor having an associated memory; wherein the processing device is operative: for a given record, to determine which of a plurality of sub-groups the given record is associated with; for each of the sub-groups associated with the given record, to check if a sampling rate of the sub-group is less than a specified sampling rate; if the sampling rate of each of the sub-groups is less than the specified sampling rate, to sample the given record, the given record otherwise not being sampled; and to repeat said determine, check and sample operations for each of a plurality of additional records; wherein samples resulting from the sample operations are processed to generate information characterizing a database comprising the sub-groups.