Abstract
Query optimizer uses a selectivity parameter for estimating the size of data that satisfies a query condition. Selectivity value calculations are based on some representation of attribute values distribution e.g. a histogram. In the paper we propose a query workload aware multi-histogram which contains a set of equi-width sub-histograms. The multi-histogram is designated for single-attribute-based range query selectivity estimating. Its structure is adapted to a 2-dimensional distribution of conditions of last recently processed range queries. The structure is obtained by clustering values of boundaries of query ranges. Sub-histograms’ resolutions are adapted to a variability of a 1-dimensional distribution of attribute values.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Augustyn, D.R.: Query-condition-aware histograms in selectivity estimation method. In: Czachórski, T., Kozielski, S., Stańczyk, U. (eds.) Man-Machine Interactions 2. AISC, vol. 103, pp. 437–446. Springer, Heidelberg (2011), http://dx.doi.org/10.1007/978-3-642-23169-8_47
Augustyn, D.R.: Query-condition-aware v-optimal histogram in range query selectivity estimation. Bulletin of the Polish Academy of Sciences. Technical Sciences 62(2), 287–303 (2014), http://dx.doi.org/10.2478/bpasts-2014-0029
Augustyn, D.R.: Query selectivity estimation based on improved V-optimal histogram by introducing information about distribution of boundaries of range query conditions. In: Saeed, K., Snášel, V. (eds.) CISIM 2014. LNCS, vol. 8838, pp. 151–164. Springer, Heidelberg (2014), http://dx.doi.org/10.1007/978-3-662-45237-0_16
Bezdek, J.C.: Pattern Recognition with Fuzzy Objective Function Algorithms. Kluwer Academic Publishers, Norwell (1981)
Bruno, N., Chaudhuri, S., Gravano, L.: Stholes: A multidimensional workload-aware histogram. SIGMOD Rec. 30(2), 211–222 (2001), http://doi.acm.org/10.1145/376284.375686
Chen, C.M., Roussopoulos, N.: Adaptive selectivity estimation using query feedback. SIGMOD Rec. 23(2), 161–172 (1994), http://doi.acm.org/10.1145/191843.191874
He, Z., Lee, B.S., Wang, X.S.: Proactive and reactive multi-dimensional histogram maintenance for selectivity estimation. J. Syst. Softw. 81(3), 414–430 (2008), http://dx.doi.org/10.1016/j.jss.2007.03.088
Ioannidis, Y.: The history of histograms (abridged). In: Proc. of VLDB Conference (2003)
Khachatryan, A., Müller, E., Stier, C., Böhm, K.: Sensitivity of self-tuning histograms: Query order affecting accuracy and robustness. In: Ailamaki, A., Bowers, S. (eds.) SSDBM 2012. LNCS, vol. 7338, pp. 334–342. Springer, Heidelberg (2012), http://dx.doi.org/10.1007/978-3-642-31235-9_22
Luo, J., Zhou, X., Zhang, Y., Shen, H.T., Li, J.: Selectivity estimation by batch-query based histogram and parametric method. In: Proceedings of the Eighteenth Conference on Australasian Database, ADC 2007, vol. 63, pp. 93–102. Australian Computer Society, Inc., Darlinghurst (2007), http://dl.acm.org/citation.cfm?id=1273730.1273741
Srivastava, U., Haas, P.J., Markl, V., Kutsch, M., Tran, T.M.: Isomer: Consistent histogram construction using query feedback. In: Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, pp. 39–51. IEEE Computer Society, Washington, DC (2006), http://dx.doi.org/10.1109/ICDE.2006.84
Zhang, T., Ramakrishnan, R., Livny, M.: Birch: An efficient data clustering method for very large databases. SIGMOD Rec. 25(2), 103–114 (1996), http://doi.acm.org/10.1145/235968.233324
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Augustyn, D.R. (2015). Query Workload Aware Multi-histogram Based on Equi-width Sub-histograms for Selectivity Estimations of Range Queries. In: Kozielski, S., Mrozek, D., Kasprowski, P., Małysiak-Mrozek, B., Kostrzewa, D. (eds) Beyond Databases, Architectures and Structures. BDAS 2015. Communications in Computer and Information Science, vol 521. Springer, Cham. https://doi.org/10.1007/978-3-319-18422-7_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-18422-7_4
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18421-0
Online ISBN: 978-3-319-18422-7
eBook Packages: Computer ScienceComputer Science (R0)