Selectivity Estimation for String Predicates Based on Modified Pruned Count-Suffix Tree

作     者：LI Dong ZHANG Qixu LIANG Xiaochong GUAN Jida XU Yang 

作者机构：School of Software Engineering South China University of Technology 

出 版 物：《Chinese Journal of Electronics》 (电子学报(英文))

年 卷 期：2015年第24卷第1期

页      面：76-82页

核心收录：

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by National Natural Science Foundation of China(No.71090403) Education Ministry of Education of P.R.C(No.x2rj B7110020) Bureau of Science and Information Technology of Guangzhou(No.2011J4100061) Bureau of Science and Information Technology of Zhaoqing(No.2013C001) 

主　　题：Query optimization Selectivity estimation String predicate Oruned count-suffix tree. 

摘      要：The accuracy of predicates selectivity estimation is one of the important factors affecting query optimization performance. State-of-art selectivity estimation algorithms for string predicates based on Pruned countsuffix tree(PST) often suffer severe underestimating and overestimating problems, thus their average relative errors are not good. We analyze the main causes of the underestimating and overestimating prob-lems, propose a novel Restricted pruned count-suffix tree(RPST) and a new pruning strategy. Based on these, we present the EKVI algorithm and the EMO algorithm which are extended from the KVI algorithm and the MO algorithm respectively. The experiments compare the EKVI algorithm and the EMO algorithm with the traditional KVI algorithm and the MO algorithm, and the results show that the average relative errors of our selectivity estimation algorithms are significantly better than the traditional selectivity estimation algorithms. The EMO algorithm is the best among these algorithms from the overall view.