Skip to main content

Approximate Query Answering using Histograms

Answering queries approximately has recently been proposed as a way to reduce query response times in on-line decision support systems, when the precise answer is not necessary or early feedback is helpful. In this article, we explore the use of precomputed histograms for approximate answering of aggregate queries. Histograms are used by most database systems for selectivity estimation within their optimizers. However, the use of histograms for approximate query answering raises several novel issues, which are addressed in this article. We present a histogram algebra for efficiently executing complex SQL queries on histograms within a DBMS without requiring any changes to the DBMS internals. We enhance histograms to estimate the quality of the approximate answers. Finally, we present an efficient technique for selecting a provably near-optimal set of histograms on the data cube, which minimizes the space needed when an upper bound on errors is given.

Viswanath Poosala, Venkatesh Ganti, Yannis Ioannidis, "Approximate Query Answering using Histograms ", IEEE Data Eng. Bull. 22(4), Dec 1999: 5-14, 1999
Published at
IEEE Data Eng. Bull. 22(4), Dec 1999: 5-14
Related research area
No related research area
Related Organizations
No related organizations