Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning
Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning
复制标题
DOI：
10.14778/3436905.3436907
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Saravanan Thirumuruganathan
中科院分区：
文献类型：
--
作者：
Saravanan Thirumuruganathan
字符串谓词选择性的准确估计是数据库中一个长期存在的研究挑战。支持字符串（如前缀、子串和后缀）上的模式匹配使得这个问题更具挑战性，因此需要专门的研究。传统方法通常构建修剪的摘要数据结构，例如尝试，然后使用统计相关性进行选择性估计。但是，这会产生不够准确的基数估计，从而导致查询优化器选择次优计划。最近提出的基于深度学习的方法利用了自然语言处理技术，例如嵌入来编码字符串并使用它来训练模型。虽然这是对传统方法的改进，但仍有很大的改进余地。我们提出了Astrid，这是一个字符串选择性估计框架，它综合了传统方法和基于深度学习的方法的思想。我们做出两个互补的贡献。首先，我们提出了一个嵌入算法，是查询类型（前缀，子串和后缀）和选择性意识。考虑三个字符串'ab'，'abc'和'abd'，其前缀频率分别为1000，800和100。我们的方法将确保'ab'的嵌入更接近'abc'而不是'abd'。其次，我们描述了神经语言模型如何用于选择性估计。虽然它们对于前缀查询工作得很好，但是它们对于子字符串查询的性能不是最佳的。我们修改了神经语言模型的目标函数，使其可以用于估计模式匹配查询的选择性。我们还提出了一种新的和有效的算法优化新的目标函数。我们在基准数据集上进行了广泛的实验，并表明我们提出的方法达到了最先进的结果。
Accurate selectivity estimation for string predicates is a long-standing research challenge in databases. Supporting pattern matching on strings (such as prefix, substring, and suffix) makes this problem much more challenging, thereby necessitating a dedicated study. Traditional approaches often build pruned summary data structures such as tries followed by selectivity estimation using statistical correlations. However, this produces insufficiently accurate cardinality estimates resulting in the selection of sub-optimal plans by the query optimizer. Recently proposed deep learning based approaches leverage techniques from natural language processing such as embeddings to encode the strings and use it to train a model. While this is an improvement over traditional approaches, there is a large scope for improvement. We propose Astrid, a framework for string selectivity estimation that synthesizes ideas from traditional and deep learning based approaches. We make two complementary contributions. First, we propose an embedding algorithm that is query-type (prefix, substring, and suffix) and selectivity aware. Consider three strings 'ab', 'abc' and 'abd' whose prefix frequencies are 1000, 800 and 100 respectively. Our approach would ensure that the embedding for 'ab' is closer to 'abc' than 'abd'. Second, we describe how neural language models could be used for selectivity estimation. While they work well for prefix queries, their performance for substring queries is sub-optimal. We modify the objective function of the neural language model so that it could be used for estimating selectivities of pattern matching queries. We also propose a novel and efficient algorithm for optimizing the new objective function. We conduct extensive experiments over benchmark datasets and show that our proposed approaches achieve state-of-the-art results.