2021.10.29 分享纪要

分享人:朱道冰
关键词:数据库测试、优化器测试
Keywords: Database Testing, Optimizer Testing
分享PPT: 2022-02-25-数据库系统测试方法介绍

分享内容

问题描述

介绍了常用的测试数据库系统及其重要组件优化器的方法。

解决思路

一、测试数据库系统

模糊测试
- SQLsmith: Genaration-based，基于AST生成语法正确的 SQL 语句，不能确保其语义正确。github
- Google AFL: Mutation-based，不针对DBMS，具有反馈的 Mutation 机制，生成的 SQL 更具针对性。github
- SQUIRREL: Mixed，结合前两者优点，针对DBMS，提高了 SQL 的语法及语义正确率，并具有反馈的Mutation机制。 github
  
  Squirrel: Testing Database Management Systems with Language Validity and Coverage Feedback. pdf
逻辑正确性测试
- RAGS：比较相同SQL语句在不同DBMS上的执行结果。
  
  Massive Stochastic Testing of SQL. pdf
- SQLancer: 实现了一下三篇论文。github
  - PQS：以结果为导向，生成一定会包含某一行的SQL语句，在数据库中执行，如果不包含这行，则说明数据库由bug。
    
    Testing Database Engines via Pivoted Query Synthesis. pdf
  - NoREC：将一条优化的 Query，强制变成非优化的方式，然后对比查询结果，如果两种执行方式不一致，那就是有 bug。
    
    Detecting Optimization Bugs in Database Engines via Non-Optimizing Reference Engine Construction. pdf
  - TLP：将一个 Query 分成了三个 Query，执行结果分别为 TRUE，FALSE 和 NULL，然后再将这三个 Query 的结果合并，并且保证结果为 TRUE。
    
    Ternary Logic Partitioning: Detecting Logic Bugs in Database Management Systems. pdf

二、测试优化器

测试优化器主要有三个关键技术:定义优化器的性能指标；遍历执行计划空间；数据集以及查询生成。主要对下面4各测试工具的前两个方面的做法进行介绍。

OptMark: OptMark: A Toolkit for Benchmarking Query Optimizers. pdf
TAQO: Testing the Accuracy of Query Optimizers. pdf
Horoscope: 使用 Horoscope 测试 TiDB 优化器. doc
SQL Server testing tool: Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer. pdf

优化器性能指标
- Effectiveness:
  - OptMark：Performance Factor & Optimality Frequence
  - TAQO：rank 指标
- Efficiency:
  - OptMark：枚举的 logical plan 个数等
遍历执行计划方式
- OptMark: 随机生成。
- TAQO: 使用不同的Hint。
- Horoscope: nth_plan。
- SQL Server testing tool: 基于 Memo 的nth_plan。

其他参考文献

FAQ

无