doc: add QPG (#663)

bajinsheng · web-flow · commit 327ac2976608 · 2022-12-19T08:58:40.000Z
diff --git a/README.md b/README.md
@@ -9,7 +9,7 @@ SQLancer (Synthesized Query Lancer) is a tool to automatically test Database Man
 
 SQLancer operates in the following two phases:
 
-1. Database generation: The goal of this phase is to create a populated database, and stress the DBMS to increase the probability of causing an inconsistent database state that could be detected subsequently. First, random tables are created. Then, randomly SQL statements are chosen to generate, modify, and delete data. Also other statements, such as those to create indexes as well as views and to set DBMS-specific options are sent to the DBMS.
+1. Database generation: The goal of this phase is to create a populated database, and stress the DBMS to increase the probability of causing an inconsistent database state that could be detected subsequently. First, random tables are created. Then, randomly SQL statements are chosen to generate, modify, and delete data. Also other statements, such as those to create indexes as well as views and to set DBMS-specific options are sent to the DBMS. **New: we support query plan guided generation now. See Generation Approaches below.**
 2. Testing: The goal of this phase is to detect the logic bugs based on the generated database. See Testing Approaches below.
 
 # Getting Started
@@ -40,6 +40,11 @@ If you launch SQLancer without parameters, available options and commands are di
 | Pivoted Query Synthesis (PQS)                        | PQS is the first technique that we designed and implemented. It randomly selects a row, called a pivot row, for which a query is generated that is guaranteed to fetch the row. If the row is not contained in the result set, a bug has been detected. It is fully described [here](https://arxiv.org/abs/2001.04174). PQS is the most powerful technique, but also requires more implementation effort than the other two techniques. It is currently unmaintained. |
 | Non-optimizing Reference Engine Construction (NoREC) | NoREC aims to find optimization bugs. It is described [here](https://www.manuelrigger.at/preprints/NoREC.pdf). It translates a query that is potentially optimized by the DBMS to one for which hardly any optimizations are applicable, and compares the two result sets. A mismatch between the result sets indicates a bug in the DBMS.                                                                                                                                                                                                        |
 | Ternary Logic Partitioning (TLP)                     | TLP partitions a query into three partitioning queries, whose results are composed and compare to the original query's result set. A mismatch in the result sets indicates a bug in the DBMS. In contrast to NoREC and PQS, it can detect bugs in advanced features such as aggregate functions.                                                                                                                                                                                                                                                  |
+# Generation Approaches
+| Approach | Description |
+|----------|-------------|
+| Random Generation | Random generation is the default test case generation approach in SQLancer. First, random tables are generated. Then queries are randomly generated based on the schemas of the tables. |
+| Query Plan Guidance (QPG) | QPG is a test case generation method guided by query plan coverage. Given a database state, we mutate it after no new unique query plans have been observed by randomly-generated queries on the database state aiming to cover more unique query plans for exposing more logics of DBMSs. This approach is enabled by option `--qpg-enable` and now supports TLP and NoREC oracles for SQLite, CockroachDB, and TiDB. |
 
 Please find the `.bib` entries [here](docs/PAPERS.md).
 
diff --git a/docs/PAPERS.md b/docs/PAPERS.md
@@ -1,6 +1,6 @@
 # Papers
 
-The testing approaches implemented in SQLancer are described in the three papers below.
+The testing approaches implemented in SQLancer are described in the four papers below.
 
 ## Testing Database Engines via Pivoted Query Synthesis
 
@@ -51,6 +51,20 @@ This paper describes TLP, a metamorphic testing approach that can detect various
 }
 ```
 
+## Testing Database Engines via Query Plan Guidance
+
+This paper describes Query Plan Guidance (QPG), a test case generation method guided by query plan coverage. This method can be paired with above three testing methods.
+
+```
+@inproceedings{Ba2023QPG,
+  author = {Ba, Jinsheng and Rigger, Manuel},
+  title = {Testing Database Engines via Query Plan Guidance},
+  booktitle = {The 45th International Conference on Software Engineering (ICSE'23)},
+  year = {2023},
+  month = may
+}
+```
+
 # Comparing SQLancer With Other Tools that Find Logic Bugs
 
 If you want to fairly compare other tools with SQLancer, we would be glad to provide feedback (e.g., feel free to send an email to manuel.rigger@inf.ethz.ch). We have the following general recommendations and comments:
