Selectivity Estimation Using Frequent Itemset Mining
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In query processing, query optimization is an important function of a database management system since overall query execution time can be significantly affected by the quality of the plan chosen by the query optimizer. Under cost-based optimization, a query optimizer estimates the cost for every possible query plans based on the underlying data distribution in synopses of database relations. The most common synopses in commercial databases have been histograms. However, when there is correlation among datum, one-dimensional histograms can provide poor estimation quality. Motivated by this, we propose a new approach to perform more accurate selectivity estimation, even for correlated data. To deal with the correlation that may exist among datum, we adopt well-known techniques in data mining and extract attribute values that occur together frequently using frequent itemsets mining. Through experimentation, we found that our approach is effective in modeling correlations and that this method approximates intermediate relations more accurately. In fact, it gives precise estimates, particularly for the correlated data.
Abstract
In query processing, query optimization is an important function of a database management system since overall query execution time can be significantly affected by the quality of the plan chosen by the query optimizer. Under cost-based optimization, a query optimizer estimates the cost for every possible query plans based on the underlying data distribution in synopses of database relations. The most common synopses in commercial databases have been histograms. However, when there is correlation among datum, one-dimensional histograms can provide poor estimation quality. Motivated by this, we propose a new approach to perform more accurate selectivity estimation, even for correlated data. To deal with the correlation that may exist among datum, we adopt well-known techniques in data mining and extract attribute values that occur together frequently using frequent itemsets mining. Through experimentation, we found that our approach is effective in modeling correlations and that this method approximates intermediate relations more accurately. In fact, it gives precise estimates, particularly for the correlated data.
참고문헌 (19)
- G. Cormode, "Synopses for massive data:samples, histograms,wavelets,sketches", Foundations and Trends in Databases, 4 (2012)
- R. Kaushik, "Synopses for query optimization:A space-complexity perspective", ACM Transactions on Database Systems, 30(4), pp.1102~1127 (2005)
- V. Poosala, "Selectivity estimation without the attribute value independence assumption", The 23rd Conference on Very Large Data Bases, pp.486~495 (1997)
- R. Agrawal, "Fast algorithms for mining association rules in large databases", The 20th International Conference on Very Large Data Bases, pp.487~499 (1994)
- S. Brin, "Beyond market baskets: generalizing association rules to correlations", ACM SIGMOD International Conference on Management of Data, pp.265~276 (1997)
- N. Bruno, "Exploiting statistics on query expressions for optimization", The ACM SIGMOD, pp.263~274 (2002)
- P. Haas, "Discovering and exploiting statistical properties for query optimization in relational databases:A survey", Statistical Analysis and Data Mining, 1(4), pp.223~250 (2009)
- Y. Matias, "Optimal workload-based weighted wavelet synopses", Theoretical Computer Science, 371(3), pp.227~246 (2007)
- J. Gryz, "Query selectivity estimation via data mining", The international conference on intelligent information processing and web mining, pp.29~38 (2004)
- G. Cormode, "Probabilistic histograms for probabilistic data", PVLDB, 2(1), pp.526~537 (2009)
- D. Fuchs, "Compressed histograms with arbitrary bucket layouts for selectivity estimation", Information on Science, 177(3), pp.680~702 (2007)
- K. Chakrabarti, "Approximate query processing using wavelets", The 26th International Conference on Very Large Data Bases, pp.111~ (2000)
- A. Deligiannakis, "Extended wavelets for multiple measures", ACM Transactions on Database Systems, 32(2) (2007)
- A. Deligiannakis, "Extended wavelets for multiple measures", ACM Transactions on Database Systems, 32(2) (2007)
- P. Brown, "BHUNT: Automatic discovery of fuzzy algebraic constraints in relational data", The 29th International Conference on Very Large Data Bases, pp.668~ (2003)
- C. Jermaine, "Playing hide-and-seek with correlations", pp.559~564 (2003), KDD
- J. Ullman, "Database system implementation" (2000), Prentice Hall
- "TPC benchmark R. Decision Support"[URL]