Teaser for "Detecting Optimization Bugs in Database Engines via Non-Optimizing Reference Engine Construction" at ESEC/FSE '20

See https://www.reddit.com/r/ESECFSE/comments/jizgby/detecting_optimization_bugs_in_database_engines/.

Transcript

1. Detecting Optimization Bugs in Database Engines via Non-optimizing Reference Engine Construction Manuel Rigger Zhendong Su ETH Zurich, Switzerland ESEC/FSE 2020 @RiggerManuel @ast_eth https://people.inf.ethz.ch/suz/
2. 2 Database Management Systems (DBMSs) PostgreSQL
3. 3 Database Management Systems (DBMSs) PostgreSQL SQLite is used in mobile phones, web browsers, OSs, TVs, …
4. 4 PostgreSQL Database Management Systems (DBMSs) We found 159 unique bugs in these systems, 141 of which have been fixed
5. 5 Optimization Bugs CREATE TABLE t0(c0 UNIQUE); INSERT INTO t0 VALUES (-1) ; SELECT * FROM t0 WHERE t0.c0 GLOB '-*'; c0 -1 t0 {}  Optimizer https://www.sqlite.org/src/tktview?name=0f0428096f
6. 6 Optimization Bugs CREATE TABLE t0(c0 UNIQUE); INSERT INTO t0 VALUES (-1) ; SELECT * FROM t0 WHERE t0.c0 GLOB '-*'; c0 -1 t0 Optimizer -1 ✓ https://www.sqlite.org/src/tktview?name=0f0428096f
7. 7 Non-optimizing Reference Engine Construction (NoREC) NoREC Idea: Rewrite the query so that the DBMS cannot optimize it
8. 8 NoREC SELECT * FROM t0 WHERE t0.c0 GLOB '-*'; {} Optimizer
9. 9 SELECT t0.c0 GLOB '-*' FROM t0; NoREC SELECT * FROM t0 WHERE t0.c0 GLOB '-*'; {} Optimizer
10. 10 SELECT t0.c0 GLOB '-*' FROM t0; NoREC SELECT * FROM t0 WHERE t0.c0 GLOB '-*'; TRUE {} Optimizer Optimizer
11. 11 SELECT t0.c0 GLOB '-*' FROM t0; NoREC SELECT * FROM t0 WHERE t0.c0 GLOB '-*'; TRUE {} Result should contain one row Optimizer Optimizer
12. 12 SELECT t0.c0 GLOB '-*' FROM t0; NoREC SELECT * FROM t0 WHERE t0.c0 GLOB '-*'; TRUE {} Result should contain one row  Optimizer Optimizer
13. 13 Implementation https://github.com/sqlancer