SSCard：利用后缀树引导的学习型FM索引进行子串基数估计

《Proceedings of the ACM on Management of Data》：SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index

SSCard基于改进的FM-Index，结合剪枝后缀树和spline插值方法，在节省空间的同时实现高精度基数估计，支持多字符串查询，具有双向算法和增量更新特性，实验表明其平均q误差降低20%，最大误差降低80%，构建时间减少50%。

　　

摘要

对子字符串查询的准确基数估计至关重要，这类查询通常使用SQL的`LIKE`操作符来表示。虽然已经开发了基于规则的方法和基于机器学习的方法来优化基数估计的各个方面，但由于这些方法缺乏误差范围，可能会导致较大的估计误差，从而产生次优的执行计划。在本文中，我们提出了SSCard，这是一种新颖的子字符串基数估计器，它将空间效率高的FM-索引应用于灵活的数据库系统中。SSCard首先扩展了FM-索引以自然地支持多个字符串，然后使用剪枝后的后缀树来组织FM-索引。后缀树结构能够实现对短模式的精确基数估计，并通过“pushup”操作实现高压缩率，尤其是在字符分布不均衡的大字母表上。此外，SSCard结合了一种具有误差范围的样条插值方法，以平衡空间使用和估计精度。其他创新还包括双向估计算法和增量更新策略。在五个真实数据集上的广泛实验结果表明，与传统方法和最新的基于学习的方法相比，SSCard的平均q误差降低了20%，最大q误差降低了80%，构建时间减少了50%。