Big Data

Improved Histograms for Selectivity Estimation of Range Predicates

Date Added: Jan 2011
Format: PDF

Many commercial database systems maintain histograms to summarize the contents of relations and permit efficient estimation of query result sizes and access plan costs. Although several types of histograms have been proposed in the past, there has never been a systematic study of all histogram aspects, the available choices for each aspect, and the impact of such choices on histogram effectiveness. In this paper, the authors provide taxonomy of histograms that captures all previously proposed histogram types and indicates many new possibilities.