The Accuracy of Cardinality Estimators: Unraveling the Evaluation Result Conundrum

Download PDF

Abstract

Existing research on the accuracy of cardinality estimators generally suffers from a lack of diversity and sufficient quantity of their experimental datasets, particularly in relation to the claimed scope of the study and the generality of its conclusions. We argue that a sufficiently large number of varied datasets are essential for comprehensive evaluations. However, the prevailing per-dataset evaluation method (PDE), producing one result table per dataset, has so far hindered this necessary expansion of the experiments. Moreover, as we demonstrate, this evaluation method often leaves the reader with contradictory results, where one estimator excels on certain datasets or queries, while the other performs better elsewhere. To address these and similar limitations, we propose a multidimensional evaluation framework. This framework unravels the conundrum of analyzing the evaluation results across multiple datasets through the use of discretization. It establishes a robust foundation for aggregating the evaluation results and conducting pairwise comparisons between estimators. Furthermore, it facilitates informed decision making in the presence of conflicting results through a customizable ranking mechanism. To empirically highlight the shortcomings of the aforementioned per-dataset evaluation and demonstrate the advantages of our proposed framework, we conduct a benchmarking study of cardinality estimators, incorporating both learned and traditional approaches. We focus on a fundamental challenge: estimating the cardinality of range queries on a single 2-D geographical relation in a static environment. Despite the apparent simplicity of this task, our findings reveal that many estimators struggle to handle this challenge effectively. To further enhance the quality of our study, we provide valuable insights by addressing some critical aspects that were overlooked in previous benchmarking studies.