Join ordering of SQL optimization
1.1作业背景
连接优化是数据库领域最重要的研究问题之一。给一个特定查询，连接优化任务是确定关系的连接顺序，并将其转化为物理计划，使得查询任务能够高效执行。它是关系型数据库查询优化的关键问题。
数据库传统的寻找SQL查询时的最佳连接顺序的方法有：
动态规划算法，贪婪算法，QuickPick等等…
最近有两种基于强化学习的方法，分别是：
ReJOIN 和 Bao。
该项目的目的对这三种方法进行评估。
1.2 需要完成的部分
该项目共需要完成及实验评估5种方法：传统方法*3，ReJOIN*1和Bao*1。
5钟方法均已实现或找到源代码（在1.5可见），目前需要老师参照文献3中第四部分实验部分来对对这5种方法进行实验及评估。（主要是对比5种方法对JOB中不同的SQL查询语句所需要的搜索时间和执行时间）（搜索时间是指产生执行计划的时间，执行时间是指该join order执行所需的时间）
（使用（文献4）中基于 IMDB (Internet Movie Database) 真实数据集 (3.6 GB, 21 个表) 的 JOB 进行测试 ，评估该优化器在PostgreSQL中的性能如何。）
1.3 需要掌握的能力
数据库 与 强化学习
最好老师也懂得数据库的连接优化问题，不过问题不大，CSDN上有不少文章很好理解。
重要：目前ReJOIN是有源代码的，Bao和DQ可以2选1进行实验，具体选哪个看觉得哪个更容易做。
1.4 文献
文献1（ReJOIN）：
Deep Reinforcement Learning for Join Order Enumeration
深度强化学习，用于连接顺序枚举
https://www.cs.brandeis.edu/~olga/publications/ReJOIN_aiDM18.pdf
文献2（Bao）：
Bao: Learning to Steer Query Optimizers
Bao：学习引导查询优化器
https://arxiv.org/pdf/2004.03814.pdf
文献3（中文文献，实验方面可以借鉴）：
RLO：一个基于强化学习的连接优化方法
http://scis.scichina.com/cn/2020/SSI-2019-0179.pdf
文献4（IMDB连接顺序基准；关键是一个很好的评估报告例子）
How Good Are Query Optimizers, Really?
查询优化器到底有多好？
https://www.vldb.org/pvldb/vol9/p204-leis.pdf
文献5（DQ）
Learning to Optimize Join Queries With Deep Reinforcement Learning
通过深度强化学习来学习优化联接查询
https://arxiv.org/pdf/1808.03196.pdf
1.5 源代码
ReJOIN：
https://github.com/antonismand/ReJOIN
https://github.com/DelphianCalamity/ReJOIN
Bao（与DQ二选一）：
https://github.com/learnedsystems/baoforpostgresql
DQ（与Bao二选一）：
https://github.com/concretevitamin/spark/commits/dq