A Cardinality Estimation Approach Based on Two Level Histograms

For the mainstream relational database management systems, histograms play im-portant roles in cardinality estimation. The main histogram-based cardinality estimation approaches can be classified into two categories: proactive approaches and reactive ap-proaches. For the former, histograms are constructed and updated by periodical data scan which is also the essential reason affecting the accuracy and performance of this kind of approaches. Data scan is avoided in the latter, as an alternative, query feedback records (QFRs) are collected to construct and update histograms. But some time-consuming al-gorithms such as the effective QFR set calculation, the hole drilling algorithm and the iterative scaling algorithm are used by reactive approaches, which makes it inefficient. In this paper, we address cardinality estimation issue with a new notion and propose a novel cardinality estimation approach by combining proactive approach with QFRs. In our approach, data scan will be executed only once to construct the initial first-level his-togram. And then, corresponding to all buckets of the first-level histogram, second-level histograms will be constructed and updated based on QFRs. The existence of sec-ond-level histograms and the elaborated mechanism dealing with the data update proble