论文笔记 | Warper: Efficiently Adapting Learned Cardinality...

Warper: Efficiently Adapting Learned Cardinality Estimators to Data and Workload Drift 【SIGMOD 2022】

ABSTRACT | 摘要

Recent learned cardinality estimation (CE) models are vulnerable when query predicates or the underlying datasets drift from what the models were trained upon. We propose a system Warper that accelerates model adaptation to drifts; Warper generates additional queries when limited examples are available from the new workload and carefully picks which queries to use to update the CE model. We show that Warper can be used to adapt different CE models including ones that support queries over single tables and join expressions. Experiments with different drifts suggest that Warper has a small computational cost and adapts much faster compared to state-of-the-art solutions. We also show that faster model adaptation improves query performance by shortening the period for which imperfect query plans are picked by a query optimizer due to incorrect cardinality estimates.

背景：当查询谓语或者底层数据集相比模型训练内容发生偏移，基数估计模型性能会受到影响。

方法：提出一个模型无关的系统——Warper，用来加速模型对这种偏移的适应。当新的工作负载中可以使用的例子有限时，Warper额外生成查询，并从中选择部分查询用来更新基数估计模型。

结果：Warper与底层基数估计模型无关；适应速度快；计算成本低；通过加快模型适应性来提高查询优化性能。

INTRODUCTION | 概述

alt

BACKGROUND AND MOTIVATION | 背景&动机

底层所采用基数估计模型的范围
查询负载偏移和数据偏移
可视化查询负载偏移
适应性解决空间和warper应该放置的位置
问题描述

alt

DESIGN OF WARPER | 设计warper

alt

gen：当没有足够的新查询用来更新模型时，warper会模仿新的查询负载来合成额外的查询。
pick：当获取真实基数标签的速度跟不上时，warper会挑选有用的查询进行标注，来节省资源的使用。
update：warper使用带标签的查询来更新模型。

alt

c1：数据库数据改变（添加、删除、更新），导致的真实基数ground truth改变，这种情况需要重新获取基数标签。
c2：新到达的查询不足的情况，少于训练一个健壮的基数估计模型所需要的带标注的查询数量。
- 这种情况需要先生成足够的查询，再从中调训部分查询，用来生成gt标注。
c3：带有ground truth标注不足但查询数量足够的情况。
- 这种情况需要挑选部分查询，用来生成gt标注。
c4：当查询数量和ground truth标注都充足的情况。

...

c2和c3对应查询负载偏移，c2是新查询不充分，c3是注释成本过高
c4具备足够数量的带标签的查询，直接更新模型

alt

query pool：q表示一条查询（谓语），gt表示其真实基数，l表示谓语来源（训练负载、新负载、合成负载）。
GAN：生成器G、判别器D。l'是D预测的谓语来源，s'是该预测的置信度。
picker P：思路来源于主动学习，从给定的谓语集合中执行一次带权重的抽样。
encoder E：将谓语q嵌入一个不同的空间z。
warper不需要知道基数估计CE模型M。
annotator A：计算查询谓语的真实基数ground truth。

Detect, identify, and adapt to drifts | 检测、识别并适应偏移

检测偏移：通过误差增加来检测是否出现偏移。
识别偏移：识别具体的偏移模式。
- 识别数据偏移 c1
- 识别查询负载偏移 c2,c3,c4
适应单独的偏移：指的是具体模式的偏移的适应方案。
适应复杂的偏移：指的是几种模式的偏移的组合情况的适应方案。

alt

对于新到达的查询集，先通过 det_drit 模块，检测出具体的偏移模式
warper首先将新到达的查询注入到查询池中
如果模式中包括 c1,c2,c3
- 如果模式中包括 c2,则需要合成查询
- 否则挑选用于训练和标注的查询
使用查询池来更新模型

Using Warper Components | 使用warper组件

alt

Query Pool 查询池：用于存放查询及对应状态内容的主存数据结构。
CE Model 基数估计模型：用来拟合查询到基数估计结果的可学习的模型，并且能够使用带标注的查询来更新自己。
Encoder 编码器：将查询中的谓语转化为嵌入向量，用于表征。
Generator 生成器：使用查询池中的查询来合成新查询谓语。
Discriminator 判别器：输入查询，输出该查询的类别为训练集的、新到达的或者合成的。
Picker 挑选器：从查询池中挑选出指定数量的查询，这些查询需要对更新CE模型有用才行，从而减少标注成本。

Training Warper Components | 训练warper组件

warper中需要学习以下三个组件：

Encoder E
Generator G
Discriminator D

update_AutoEncoder() 用于在不需要生成新查询的情况下学习 Encoder E 和 Generator G。

update_MultiTask() 用于在需要生成新查询的情况下学习 Generator G 和 Discriminator D，即训练 GAN。

Robustness in Warper | warper鲁棒性

提前终止 warper：使用一次适应所带来的准确度增益作为停止指标。一旦增益少于阈值，则下一次调用 det_drft 将采用更大的 π 值。此时 warper 不更新 CE 模型而是使用之前的 CE 模型，直到下一次检测到更大的偏移。
鲁棒性和回馈选项：
- 偏移检测
- 偏移类型检测
- 适应区间和新负载的异常值