Workload-Aware Histograms for Remote Applications

Abstract. Recently several database-based applications have emerged that are remote from data sources and need accurate histograms for query cardinality es-timation. Traditional approaches for constructing histograms require complete access to data and are I/O and network intensive, and therefore no longer apply to these applications. Recent approaches use queries and their feedback to construct and maintain “workload aware ” histograms. However, these approaches either employ heuristics, thereby providing no guarantees on the overall histogram ac-curacy, or rely on detailed query feedbacks, thus making them too expensive to use. In this paper, we propose a novel, incremental method for constructing his-tograms that uses minimum feedback and guarantees minimum overall residual error. Experiments on real, high dimensional data shows 30-40 % higher estima-tion accuracy over currently known heuristic approaches, which translates to sig-nificant performance improvement of remote applications.