A block sampling approach to distinct value estimation

To process queries efficiently in a relational database it is often of value to estimate the number of distinct values occurring in a particular field. In contexts where complete enumeration is costly. estimators based on a subsample are an attractive alternative. Though many such estimators have already been proposed. most are based on a simple random sampling of records which is wasteful in a database where records are retrieved in blocks. This article seeks to develop estimators that perform well in contexts where blocks of records are sampled randomly. Building on a result of Good's we derive six such estimators and evaluate their performance.