Selectivity Estimation Using Frequent Itemset Mining

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. 쿼리 최적화기에 의해 선택된 쿼리 계획은 전체 쿼리 실행 속도에 지대한 영향을 미치기 때문에, 데이터 베이스관리시스템의 쿼리 최적화 기능은 쿼리 처리과정에 있어 중요하다. Cost 기반 최적화에서 쿼리 최적화기는 모든 가능한 쿼리 계획들의 비용을 데이터베이스의 데이터 분포 정보를 기반으로 추정한다. 일반적으로 상용화되고 있는 DBMS에서 가장 흔하게 사용되는 데이터 분포 통계 정보는 히스토그램 방식으로 구축된 형태이다. 그러나 각각의 데이터들에 상호현관성이 있는 경우, 일차원 히스트그램 방법은 형편없는 추정치를 계산해낸다. 본 논문에서는 쿼리 최적화 과정에서 보다 정확한 쿼리 비용을 계산하여 쿼리계획을 선출할 수 있도록 하기 위해 데이터마이닝의 기술 중 하나인 빈발항목 마이닝Frequent Itemsets Mining) 방법을 적용하였다. 실험을 통해 제안하는 방법이 상호 연관관계 있는 데이터들에 있어 히스토그램보다 좋은 추정치를 보여 줌을 확인하였다.