arXiv:2506.14034cs.DBcs.LG2025-06

用概率网络动态生成查询概要,提升数据库连接估算效率

Sketched Sum-Product Networks for Joins

  • 用求和-乘积网络分解数据分布,实时生成查询概要
  • 准确逼近已有高精度概要方法,节省构建成本
  • 适合需要快速响应新查询的数据库优化场景

概要技术在多路连接基数估计中表现出高精度,这是基于成本的查询优化中的关键问题。准确估计连接操作的基数(即计算成本)有助于优化关系数据库系统的查询执行开销。然而,尽管概要技术在查询优化中表现优异,它们通常针对预定义的选择条件构建,假设这些条件事先已知,限制了其对新查询的适用性。为此,我们提出利用求和-乘积网络(Sum-Product Networks)动态地在线近似概要。求和-乘积网络可将多变量分布(如表数据)分解为多个一元分布的线性组合。通过将这些一元分布表示为概要,求和-乘积网络可逐元素组合,高效近似任意查询选择的概要。这些近似概要可用于连接基数估计。特别地,我们实现了 Fast-AGMS 与 Bound Sketch 方法,二者虽在先前工作中已被证明有效,但其构建成本较高。通过精确近似它们,我们的方法为在查询优化中应用这些概要提供了实用替代方案。

原文摘要 · Abstract (English)

Sketches have shown high accuracy in multi-way join cardinality estimation, a critical problem in cost-based query optimization. Accurately estimating the cardinality of a join operation -- analogous to its computational cost -- allows the optimization of query execution costs in relational database systems. However, although sketches have shown high efficacy in query optimization, they are typically constructed specifically for predefined selections in queries that are assumed to be given a priori, hindering their applicability to new queries. As a more general solution, we propose for Sum-Product Networks to dynamically approximate sketches on-the-fly. Sum-Product Networks can decompose and model multivariate distributions, such as relations, as linear combinations of multiple univariate distributions. By representing these univariate distributions as sketches, Sum-Product Networks can combine them element-wise to efficiently approximate the sketch of any query selection. These approximate sketches can then be applied to join cardinality estimation. In particular, we implement the Fast-AGMS and Bound Sketch methods, which have successfully been used in prior work, despite their costly construction. By accurately approximating them instead, our work provides a practical alternative to apply these sketches to query optimization.

数据库优化基数估计概率模型

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。