FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation
FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation
复制标题
DOI：
10.14778/3461535.3461539
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Rong Zhu;Ziniu Wu;Yuxing Han;Kai Zeng;A. Pfadler;Zhengping Qian;Jingren Zhou;Bin Cui
中科院分区：
文献类型：
--
作者：
Rong Zhu;Ziniu Wu;Yuxing Han;Kai Zeng;A. Pfadler;Zhengping Qian;Jingren Zhou;Bin Cui
查询优化器依赖于准确的基数估计（CardEst）来生成良好的执行计划。CardEst的核心问题是如何以准确和紧凑的方式对丰富的属性联合分布建模。尽管经过几十年的研究，现有的方法要么只使用独立因子分解来简化模型，导致不准确的估计和次优的查询计划，要么通过无损条件因子分解而没有任何独立的假设，导致概率计算缓慢。在本文中，我们提出了FLAT，CardEst方法，同时是快速的概率计算，轻量级的模型大小和准确的估计质量。FLAT的核心思想是一种新的无监督图形模型，称为FSPN。它利用独立和条件因子分解自适应模型的不同层次的属性相关性，从而涵盖了所有现有的CardEst模型，并总结其优点。FLAT支持在底层FSPN模型上以接近线性的时间进行有效的在线概率计算，并提供有效的离线模型构造。它可以估计单表查询和多表连接查询的基数。广泛的实验研究表明，FLAT在知名基准测试中比现有的CardEst方法具有优越性：FLAT的准确性提高了1到5个数量级，概率计算速度提高了1到3个数量级（约0.2ms），存储成本降低了1到2个数量级（仅数十KB）。
Query optimizers rely on accurate cardinality estimation (CardEst) to produce good execution plans. The core problem of CardEst is how to model the rich joint distribution of attributes in an accurate and compact manner. Despite decades of research, existing methods either over simplify the models only using independent factorization which leads to inaccurate estimates and sub optimal query plans, or over-complicate them by lossless conditional factorization without any independent assumption which results in slow probability computation. In this paper, we propose FLAT, a CardEst method that is simultaneously fast in probability computation, lightweight in model size and accurate in estimation quality. The key idea of FLAT is a novel unsupervised graphical model, called FSPN. It utilizes both independent and conditional factorization to adaptively model different levels of attributes correlations, and thus subsumes all existing CardEst models and dovetails their advantages. FLAT supports efficient online probability computation in near liner time on the underlying FSPN model, and provides effective offline model construction. It can estimate cardinality for both single table queries and multi-table join queries. Extensive experimental study demonstrates the superiority of FLAT over existing CardEst methods on well-known benchmarks: FLAT achieves 1 to 5 orders of magnitude better accuracy, 1 to 3 orders of magnitude faster probability computation speed (around 0.2ms) and 1 to 2 orders of magnitude lower storage cost (only tens of KB).