动态数据库下，用在线学习估计查询选择性，更贴近真实场景。
Selectivity Estimation for Linear Queries via Online Learning
- 基于在线学习框架，适应数据库和查询的动态变化
- 对直方图类线性查询给出后悔值上下界，理论完备
- 适合数据库系统中实时查询优化与自适应索引设计
近年来，基于学习的数据库选择性估计方法受到广泛关注。然而，现有理论研究主要局限于静态数据库上的固定查询分布。实际上，数据库内容和查询负载可能随时间动态变化。本文提出一种算法框架，用于在更一般的动态设置下学习查询的选择性。受在线学习启发，我们以后悔值衡量算法性能，即学习算法累积损失与最优固定策略之差。针对点查询、范围查询和子集选择等基于直方图的线性查询，在标准损失函数下，建立了静态与动态数据库场景下的后悔值上下界。
原文摘要 · Abstract (English)
Learning-based approaches for selectivity estimation in databases have gained significant traction in recent years. However, theoretical studies of these learning-based approaches are essentially limited to fixed query distributions on static databases. In practice, both the underlying database and the query workload can dynamically change over time. In this work, we propose an algorithmic framework for learning selectivity of queries in this more general dynamic setup. Inspired by online learning, we measure the performance of the learning algorithm in this setting by its regret, which compares the cumulative loss incurred by the learning algorithm to that of the best fixed strategy. We establish upper and lower bounds on regret for histogram-based linear queries, such as point, range, and subset selection queries, under standard loss functions, in both static and dynamic database settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。