基于TreeLSTM的查询基数估计

Query cardinality estimation based on TreeLSTM

针对传统的数据库管理系统无法很好地学习谓词之间的交互以及无法准确地估计复杂查询的基数问题,提出了一种树形结构的长短期记忆神经网络(Tree Long Short Term Memory, TreeLSTM)模型建模查询,并使用该模型对新的查询基数进行估计.所提出的模型考虑了查询语句中包含的合取和析取运算,根据谓词之间的操作符类型将子表达式构建为树形结构,根据组合子表达式向量来表示连续向量空间中的任意逻辑表达式.TreeLSTM模型通过捕捉查询谓词之间的顺序依赖关系从而提升基数估计的性能和准确度,将TreeLSTM与基于直方图方法、基于学习的MSCN和TreeRNN方法进行了比较.实验结果表明:TreeLSTM的估算误差比直方图、MSCN、TreeRNN方法的误差分别降低了60.41%,33.33%和11.57%,该方法显著提高了基数估计器的性能.

A tree-structured Long Short Term Memory model is proposed for modeling queries and estimating new query cardinality using a traditional database management system that cannot effectively learn the interactions between predicates and cannot accurately estimate the cardinality of complex queries.The proposed model considers the merge and disjunction operations contained in the query statements,constructs the subexpressions as tree structures based on the types of operators between the predicates,and represents arbitrary logical expressions in a continuous vector space based on the combination of subexpression vectors.The TreeLSTM model improves the performance and accuracy of cardinality estimation by capturing the sequential dependencies between query predicates.TreeLSTM is compared with histogram-based methods,learning-based MSCN,and TreeRN methods.The experimental results show that the estimation error of TreeLSTM is reduced by 60.41%,33.33%,and 11.57%than their errors respectively,and the method significantly improves the performance of the cardinality estimator.