Abstract
Cardinality estimation is a critical component of query optimization. Despite extensive research, achieving efficient and accurate estimation for join queries remains challenging. Estimating tight upper bounds for join cardinalities can help the query optimizer generate better and more robust query plans. However, existing methods fail to account for the high skewness of real data and produce loose upper bounds. In this paper, we propose a new framework BoundEst, which designs an upper bound formula that accounts for the presence of outliers in the data distribution and introduces the DBSCAN clustering algorithm to identify these outliers. Moreover, we incorporate the learning-based model to learn the correlation between attributes. Given queries, BoundEst efficiently estimates tight upper bounds for join cardinalities by applying separate calculation methods to outliers and other values. We evaluate our approach on real-world datasets, and the results show that BoundEst generates effective estimates for query optimizer.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Atserias, A., Grohe, M., Marx, D.: Size bounds and query plans for relational joins. In: 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 739–748. IEEE (2008)
Birant, D., Kut, A.: St-DBScan: an algorithm for clustering spatial-temporal data. Data Knowl. Eng. 60(1), 208–221 (2007)
Bruno, N., Chaudhuri, S., Gravano, L.: Stholes: a multidimensional workload-aware histogram. In: Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, pp. 211–222 (2001)
Cai, W., Balazinska, M., Suciu, D.: Pessimistic cardinality estimation: tighter upper bounds for intermediate join cardinalities. In: Proceedings of the 2019 International Conference on Management of Data, pp. 18–35 (2019)
Deshpande, A., Garofalakis, M., Rastogi, R.: Independence is good: dependency-based histogram synopses for high-dimensional data. ACM SIGMOD Rec. 30(2), 199–210 (2001)
Dutt, A., Wang, C., Nazi, A., Kandula, S., Narasayya, V., Chaudhuri, S.: Selectivity estimation for range predicates using lightweight models. Proc. VLDB Endow. 12(9), 1044–1057 (2019)
Gens, R., Pedro, D.: Learning the structure of sum-product networks. In: International Conference on Machine Learning, pp. 873–880. PMLR (2013)
Gunopulos, D., Kollios, G., Tsotras, V.J., Domeniconi, C.: Selectivity estimators for multidimensional range queries over real attributes. VLDB J. 14, 137–154 (2005)
Han, Y., et al.: Cardinality estimation in DBMS: a comprehensive benchmark evaluation. arXiv preprint arXiv:2109.05877 (2021)
Hasan, S., Thirumuruganathan, S., Augustine, J., Koudas, N., Das, G.: Deep learning models for selectivity estimation of multi-attribute queries. In: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 1035–1050 (2020)
Hertzschuch, A., Hartmann, C., Habich, D., Lehner, W.: Simplicity done right for join ordering. In: CIDR (2021)
Hilprecht, B., Schmidt, A., Kulessa, M., Molina, A., Kersting, K., Binnig, C.: DeepDB: learn from data, not from queries! arXiv preprint arXiv:1909.00607 (2019)
Kipf, A., Kipf, T., Radke, B., Leis, V., Boncz, P., Kemper, A.: Learned cardinalities: estimating correlated joins with deep learning. arXiv preprint arXiv:1809.00677 (2018)
Kraskov, A., Stögbauer, H., Grassberger, P.: Estimating mutual information. Phys. Rev. E 69(6), 066138 (2004)
Leis, V., Gubichev, A., Mirchev, A., Boncz, P., Kemper, A., Neumann, T.: How good are query optimizers, really? Proc. VLDB Endow. 9(3), 204–215 (2015)
Leis, V., Radke, B., Gubichev, A., Kemper, A., Neumann, T.: Cardinality estimation done right: index-based join sampling. In: CIDR (2017)
Li, F., Wu, B., Yi, K., Zhao, Z.: Wander join: online aggregation via random walks. In: Proceedings of the 2016 International Conference on Management of Data, pp. 615–629 (2016)
Muralikrishna, M., DeWitt, D.J.: Equi-depth multidimensional histograms. In: Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, pp. 28–36 (1988)
Tzoumas, K., Deshpande, A., Jensen, C.S.: Lightweight graphical models for selectivity estimation without independence assumptions. Proc. VLDB Endow. 4(11), 852–863 (2011)
Wu, P., Cong, G.: A unified deep model of learning from both data and queries for cardinality estimation. In: Proceedings of the 2021 International Conference on Management of Data, pp. 2009–2022 (2021)
Wu, Z., Negi, P., Alizadeh, M., Kraska, T., Madden, S.: FactorJoin: a new cardinality estimation framework for join queries (2023)
Wu, Z., Shaikhha, A., Zhu, R., Zeng, K., Han, Y., Zhou, J.: Bayescard: revitilizing Bayesian frameworks for cardinality estimation. arXiv preprint arXiv:2012.14743 (2020)
Wu, Z., et al.: FSPN: a new class of probabilistic graphical model. arXiv preprint arXiv:2011.09020 (2020)
Yang, Z., et al.: Neurocard: one cardinality estimator for all tables. arXiv preprint arXiv:2006.08109 (2020)
Yi, P., Li, J., Choi, B., Bhowmick, S.S., Xu, J.: Flag: towards graph query autocompletion for large graphs. Data Sci. Eng. 7(2), 175–191 (2022)
Yin, H., Gao, H., Wang, B., Li, S., Li, J.: Efficient trajectory compression and range query processing. World Wide Web 25(3), 1259–1285 (2022)
Yu, T., et al.: Zebra: a novel method for optimizing text classification query in overload scenario. World Wide Web 26(3), 905–931 (2023)
Zhao, Z., Christensen, R., Li, F., Hu, X., Yi, K.: Random sampling over joins revisited. In: Proceedings of the 2018 International Conference on Management of Data, pp. 1525–1539 (2018)
Zhu, R., et al.: Flat: fast, lightweight and accurate method for cardinality estimation. arXiv preprint arXiv:2011.09022 (2020)
Acknowledgement
The work is partially supported by the National Key Research and Development Program of China (2020YFB1707901), National Natural Science Foundation of China (Nos. U22A2025, 62072088, 62232007), Ten Thousand Talent Program (No. ZX20200035), Science and technology projects in Liaoning Province (No. 2023JH2/ 101300182), and 111 Project (No. B16009).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Yang, J., Zhang, Y., Wang, B., Yang, X. (2024). BoundEst: Estimating Join Cardinalities with Tight Upper Bounds. In: Song, X., Feng, R., Chen, Y., Li, J., Min, G. (eds) Web and Big Data. APWeb-WAIM 2023. Lecture Notes in Computer Science, vol 14331. Springer, Singapore. https://doi.org/10.1007/978-981-97-2303-4_29
Download citation
DOI: https://doi.org/10.1007/978-981-97-2303-4_29
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-2302-7
Online ISBN: 978-981-97-2303-4
eBook Packages: Computer ScienceComputer Science (R0)